Re: Lambda calculus and it relation to LISP

[Alfred Einstead]

gnuist007@hotmail.com (gnuist) wrote:
> "The lambda calculus is a mathematical formalism 
> having to do with the way functions instantiate
> their arguments. To some extent it is the theoretical
> basis for Lisp and plenty of other computer languages."

A computer language is, for the most part, a notation
for the family of numeric functions known as the
recursive functions.  The Lambda Calculus can represent
all recursive functions, with respect to a suitable
coding of numbers as lambda expressions.

The Lambda Calculus extended to include infinitary
expressions has the power to directly embody and
represent the control flow structures of an imperative
programming language, and to do so in such a way that
the variables in the imperative language, under this
representation, are all referentially transparent.

A control flow structure is just a finitary "rolled up"
representation of an infinitary branching/conditional
expression.  So, the actual structure is directly
represented by expression/subexpression ordering of
the infinitary expression.  Basically, each subexpression
corresponds to what, in an imperative language, would be
an address, and each expression-subexpression relation
to a "goto".

This is described in some detail under the section
dealing with the Infinitary Lambda Calculus and programming
languages currently at
              www.csd.uwm.edu/~whopkins/functional/index.html

(Or look under www.csd.uwm.edu/~whopkins for a broader range
of topics including this one).