Abstraction (or, Lambda Calculus for Dummies)

[David E. Manifold]

On Fri, 12 Dec 1997, Fare Rideau wrote:

> Dear Tril,
> 
> > What are the semantics of the abstraction function?
> The abstraction is not a function, but a meta-operator,
> that takes variables (parameter names), and an expression (the body),
> and makes a function that takes arguments, binds the parameters to them,
> then evaluate the body in the environment of definition of the function
> enriched by these new bindings.

Why is a meta-operator different from a function?  Doesn't higher-order
mean functions can be meta-operators? 

Let me just make sure: when you say lambda you are talking about
abstraction.  When you say abstraction, to do it you would use lambda.  I
was using the words as if they were the same thing.  Or at least that
lambda is the symbol used to denote abstraction (I believe you said this
somewhere, I'm just checking).

> Hence, the function lambda(f,x).f(x) is a function that takes
> a pair (f,x) of arguments, then applies function f with argument x,
> and returns the result.

Is this true:
The difference between starting function f, and the unnamed returned
function, is described by:

f was not a function until it was abstracted.  The act of abstraction
created the function by placing future values into an expression. 

In other words lambda's expression argument is taken as parts, X is
inserted into the parts, then the whole is simplified as much as it can
without knowing the value of X.  Am I getting close?

You didn't answer my question: are all functions initially created by
abstraction?

> > Something
> > like "lambda f(x).sin(2*x+1)"  Or is this just evaluating an expression
> > that has 'x' in it?  Is the abstraction function taking x out of the
> > expression 2*x+1 or putting it in?
> It delays the evaluation of sin(2*x+1) in a environment where x will
> be bound to the argument of the function.

If evaluation is just substituting the argument wherever x occurs in the
function body, then abstraction is the creation of an incomplete structure
(expression) that will be evaluated as soon as the value of placeholder x
is known.  Is that right?

The semantics for handling typed abstraction... is the type simply passed
through:  given f is the result of abstracting x and sin(2*x+1), then any
type valid for x in sin(2*x+1), is also valid as an argument for f?


 
> > I don't know what a lambda calculus is, and I tried looking at
> > the "standard reference" but it didn't make much sense because
> > I'm not familiar with set theory or notation.
> >
> Hum. Anyone knows any good intros to \lambda-calculus on the Web?
> [BTW, was the "standard reference" the Barendregt book?]
Yes.

Finally, an example of where abstraction would be useful.  I thought of
this:  You have function f that takes type int for argument.  But you want
to make a generic function that takes any numeric type for an argument.
So you do lambda(f,generic_numeric_type) and it results in a new function.
I wondered how you can be sure the new function will work?  Will it work
in this case because numeric type is more general than integer type?  What
if you wanted to go the other way?  The C++ers would call it
specialization or inheritance to take a function a that handled any number
and to derive a new function b that handled only integers.  However
intentional programming would call it one aspect (a different
implementation of the function a).   So am I talking about abstraction in
the first case (int to general number), and is this the opposite of
another operation (general number to int) and how does this relate to C++
and other languages that do not have abstraction or are not reflective.
Is C++ not reflective because you can not access definitions of a function
by other functions?  Is abstraction the key function that accesses the
internals of functions, or is it just one?
 
David E. Manifold <tril@bespin.ml.org> http://www.pacificrim.net/~dem/
"...there is no such thing as reality.  Reality only exists in someone's
perceptions, attitudes, beliefs...and nowhere else."
"The world's apparent chaos is only a reflection of our own inner turmoil."
--Michael Gerber, _The_E-Myth_