Lambda calculus and it relation to LISP

Lambda calculus and it relation to LISP

[gnuist]

I read the following quote in a book on emacs and similar
things in a book on lisp.

"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."

I am interested in a little concrete elaboration
of this statement by any mathematicians, logicians
or practitioners/users of lisp and lisp in emacs.

This is an interdisciplinary topic and cross-posted.
Please beware of this and be undaunted in intellectual 
work just in case some rude individual jumps in and threatens
the discussion on this thread. This comment is in view
of a sad incident by a similar character on a valid 
interdisciplinary thread on comp.lang.lisp and gnu.emacs.help.
Previously this individual had also posted unbecoming
comments to Professor Fateman of UC Berkeley who is
actually a very nice and helpful individual in my experience
about two years ago from a phone conversation with me.

I think that it would be exciting and intellectually 
satisfying to know an answer to this question for many
of us in the math/logic/lisp/emacs community.

Re: Lambda calculus and it relation to LISP

[Luke A. Olbrish]

gnuist007@hotmail.com (gnuist) writes:

> "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."
> 
> I am interested in a little concrete elaboration
> of this statement by any mathematicians, logicians
> or practitioners/users of lisp and lisp in emacs.

((lambda (x) x x) (lambda (x) x x))

-- 
Luke Olbrish
<luke.olbrish@cc.gatech.edu>

Re: Lambda calculus and it relation to LISP

[Charles Matthews]

"gnuist" wrote

> I read the following quote in a book on emacs and similar
> things in a book on lisp.
>
> "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."
>
> I am interested in a little concrete elaboration
> of this statement by any mathematicians, logicians
> or practitioners/users of lisp and lisp in emacs.

There are a few obstacles in understanding what is going on here.  For
example:

- the lambda calculus may be a 'mathematical formalism', but it is not one
mathematicians usually have a feeling for, unless they have cause to use it
in some way: what it is really is a very basic piece of syntax for computer
science;

- the underlying programming theory of lambda calculus is functional
programming, so on the whole it might be more accurate to call lambda
calculus a mechanism for expressing accurately the substitution of one
function in another, rather than instantiation (an operational rather than a
mathematical difference);

- you can call LISP a functional programming language if you want - not
everybody would so want;

- the untyped lambda calculus written in the usual compressed way
abbreviates heavily, and going a couple of steps back to a more tree-like
representation of combinators is much more perspicuous.

So, this connection can be made ... but joining it all up required a fair
amount of background.

Charles

Re: Lambda calculus and it relation to LISP

[Gareth McCaughan]

gnuist wrote:

> I read the following quote in a book on emacs and similar
> things in a book on lisp.
> 
> "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."
> 
> I am interested in a little concrete elaboration
> of this statement by any mathematicians, logicians
> or practitioners/users of lisp and lisp in emacs.

Lambda calculus, as originally designed, is a formalism
for representing computations. A lambda-calculus
expression is either a variable "x", a lambda abstraction
"\x.E" (where "\" is a lambda and E is any lambda-calculus
expression), or an application "E F" where E and F are
expressions. There are three transformations you're
allowed to do, of which the most important is one that
takes (\x.E)F into whatever you get by substituting E
for every (free) occurrence of x in F.

What this means is that "\x.E" sort-of-means "the
function that maps x to E". E might be something
like "x x" (so that \x.(x x) is the function that
takes any argument and applies it to itself), or
something like "\y.x" (so that \x.(\y x) is the
function that takes any argument and returns the
constant function that always returns it), or
whatever.

The point of all this is that that is, in some sense,
*all* you need; within this system you can model all
of mathematics, or at least all the mathematics
Alonzo Church cared about. You have to "encode"
everything as a function. For instance, here's a
famous way of representing the non-negative integers:

    0 "is" \x.(\f.(\y.y))
    1 "is" \x.(\f.(\y.f y))
    2 "is" \x.(\f.(\y.f (f y)))
    3 "is" \x.(\f.(\y.f (f (f y))))
    etc.

So, we represent n by something that takes a function f
and returns a new function that just applies f n times
to its argument. Then addition is

    \m.\n.\f.\y.(m f) ((n f) y)

and multiplication is

    \m.\n.\f.m (n f)

and so on.

It's often claimed that the lambda calculus is the
theoretical basis for Lisp, or Scheme, or other
languages, but the truth behind this claim amounts
to the following things.

1. Those languages treat functions as first-class objects.
2. Some of those languages use the keyword "lambda"
   for building functions.
3. Some of those languages allow functions to carry around
   their "environment", which sort-of corresponds to how
   lambda abstractions behave in the lambda calculus.
   (Note that this was *not* a feature of the very first
   Lisps. It is also not a feature of Emacs Lisp. The
   key words here are "lexical scoping" versus "dynamic
   scoping".)
4. Er, that's it.

Important features of the lambda calculus that aren't
reflected in any version of Lisp that I know:

1. In the lambda calculus, *everything* is a function.
   We don't need no stinkin' numbers!
2. In so far as the lambda calculus has a preferred "order
   of evaluation", it's "normal order", which amounts to
   evaluating things as you need them, which is basically
   what "lazy languages" like Haskell do. I don't think
   any Lisp variant is lazy.
3. The lambda calculus has no notion of "object identity".
   Indeed, it has no notion of "objects". When I say
   "objects", I don't mean "instances of classes in a
   system with inheritance and polymorphism and
   encapsulation"; I just mean "things we can compute
   with". The lambda calculus is purely syntactic; two
   expressions are "equal" if you can transform one to
   the other by the standard transformations. No notion
   of identity here.
4. Evaluation in the lambda calculus works by repeated
   textual substitution. You can build toy interpreters
   that way (I think it's done in SICP, but I may be
   misremembering), but you can't really build a practical
   programming language on that foundation. Especially
   not an "impure" one (i.e., one with mutable state),
   which includes every variety of Lisp I know of.

It is likely that some Lisp pioneers have been inspired
by the lambda calculus, with its vision of the power of
functions, but calling it the theoretical basis for Lisp
is in my opinion rather misleading.

The most lambda-calculus-y languages are the lazy pure
functional languages. Some of them are even implemented
(I think) in a way that's reminiscent of the lambda
calculus and its "reduction rules" (the things I called
transformations, earlier).

> This is an interdisciplinary topic and cross-posted.
> Please beware of this and be undaunted in intellectual 
> work just in case some rude individual jumps in and threatens
> the discussion on this thread. This comment is in view
> of a sad incident by a similar character on a valid 
> interdisciplinary thread on comp.lang.lisp and gnu.emacs.help.
> Previously this individual had also posted unbecoming
> comments to Professor Fateman of UC Berkeley who is
> actually a very nice and helpful individual in my experience
> about two years ago from a phone conversation with me.

This sort of remark essentially never has a positive effect.
(Meaning the "rude individual" stuff, not the compliment
to Richard Fateman.)

> I think that it would be exciting and intellectually 
> satisfying to know an answer to this question for many
> of us in the math/logic/lisp/emacs community.

Emacs Lisp is less lambda-y than any other version of Lisp
I am familiar with. (I am not familiar with AutoLisp.)

-- 
Gareth McCaughan  Gareth.McCaughan@pobox.com
.sig under construc

Re: Lambda calculus and it relation to LISP

[William Elliot]

On 5 Oct 2002, Luke A. Olbrish wrote:
> gnuist007@hotmail.com (gnuist) writes:
>
> > "The lambda calculus is a mathematical formalism
> > having to do with the way functions instantiate
> > their arguments.
> ((lambda (x) x x) (lambda (x) x x))
>
(Lx.xx)(Lx.xxx)



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[David Kastrup]

luke.olbrish@cc.gatech.edu (Luke A. Olbrish) writes:

> gnuist007@hotmail.com (gnuist) writes:
> 
> > "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."
> > 
> > I am interested in a little concrete elaboration
> > of this statement by any mathematicians, logicians
> > or practitioners/users of lisp and lisp in emacs.
> 
> ((lambda (x) x x) (lambda (x) x x))

That's gibberish.  You probably mean

((lambda (x) (x x)) (lambda (x) (x x)))

which will (in Scheme, not Lisp) lead to infinite recursion.

While we are on the topic of Scheme and recursion:
((lambda (f n) (f f n))
 (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)

Recursion without a function actually calling itself!

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: David.Kastrup@t-online.de

Re: Lambda calculus and it relation to LISP

[Fred Gilham]

> "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."
>
> I am interested in a little concrete elaboration of this statement
> by any mathematicians, logicians or practitioners/users of lisp and
> lisp in emacs.

From a Lisp point of view you should read the early Scheme material.
There is a page I just found that has a lot of good stuff on it that
will help.

    http://library.readscheme.org

My impression is that the ideas are all fairly old (in modern terms)
and if you are interested in the ideas themselves you'll do better to
read the older material.

> This is an interdisciplinary topic and cross-posted.

Interdisciplinary is fine but... gnu.emacs.help???


-- 
Fred Gilham gilham@csl.sri.com || His word is a creative word, and
when he speaks the good exists as good.  God is neither arbitrary nor
tyrannical.  He is love, and when he expresses his will it is a will
of love.  Hence the good given by God is good for us.-- Jacques Ellul

Re: Lambda calculus and it relation to LISP

[Kaz Kylheku]

gnuist007@hotmail.com (gnuist) wrote in message news:<9e8ebeb2.0210041920.2e480123@posting.google.com>...
> I read the following quote in a book on emacs and similar
> things in a book on lisp.

I see you dedicated more than half of your article to expressing your
anticipation of a rebuke for your sociopathic behavior from me. Well,
here it is.

> This is an interdisciplinary topic and cross-posted.
> Please beware of this and be undaunted in intellectual 
> work just in case some rude individual jumps in and threatens
> the discussion on this thread. This comment is in view
> of a sad incident by a similar character on a valid 
> interdisciplinary thread on comp.lang.lisp and gnu.emacs.help.
> Previously this individual had also posted unbecoming
> comments to Professor Fateman of UC Berkeley who is
> actually a very nice and helpful individual in my experience
> about two years ago from a phone conversation with me.

You are actually quite eloquent; that is to say, remarkably so for yet
another a piece of trolling excrement hiding behind a throwaway e-mail
address (which probably doesn't even exist). Presumably, you are
intelligent enough to realize that if one types ``lambda calculus''
into a search engine such as Google, it will come up with quote a
number of useful hits. The last time I performed this very search, I
recall finding a page with a very good and quite detailed introduction
to lambda calculus which could serve as a tutorial, and which quite
clearly established the relationship between lambda calculus and the
origins of functional programming. Though such information is no
substitute for debate, absorbing it constitutes the minimum required
effort for genuine participation in a debate---but of course, that is
the last thing that you want.

> I think that it would be exciting and intellectually 
> satisfying to know an answer to this question for many
> of us in the math/logic/lisp/emacs community.

And for those of you in the trolling community, it is undoubtedly
exciting and emotionally satisfying to obtain *any* kind of response.
Well, there it is, so enjoy your temporary high.

Re: Lambda calculus and it relation to LISP

[William Elliot]

Gareth.McCaughan@pobox.com
Using L for lambda and convention (Lxy.M) for (Lx.(Ly.M))
and = for transform or converts to.

wwf:  variables
	wwf N,M ==> wwf (Lx.N), (NM)

 _ There are three transformations you're allowed to do, of which the
 _ most important is one that takes (Lx.E)F into whatever you get by
 _ substituting E for every (free) occurrence of x in F.
Provided no free variable of F falls within the scope of a
bound variable of E.  What are the other two transformations?

 _ The point of all this is that that is, in some sense,
 _ *all* you need; within this system you can model all
 _ of mathematics, or at least all the mathematics
 _ Alonzo Church cared about. You have to "encode"
 _ everything as a function. For instance, here's a
 _ famous way of representing the non-negative integers:
 _     0 "is" Lx.(Lf.(Ly.y))
 _     1 "is" Lx.(Lf.(Ly.f y))
 _     2 "is" Lx.(Lf.(Ly.f (f y)))
 _     3 "is" Lx.(Lf.(Ly.f (f (f y))))
 _     etc.
What??  Maybe this is add 0, add 1, etc.

0 = (Lfx.x)
1 = (Lfx.fx)
2 = (Lfx.f(fx))
3 = (Lfx.f(f(fx)))
...
0f = I				0fx = x
1f = (Lx.fx)		1fx = fx
2f = (Lx.f(f(x))	2fx = f(f(x))
3f = (Lx.f(f(f(x)))	3fx = f(f(f(x)))
...

 _ So, we represent n by something that takes a function f
 _ and returns a new function that just applies f n times
 _ to its argument. Then addition is
 _     Lm.Ln.Lf.Ly.(m f) ((n f) y)
Ok.  By my definition for 1.
	+11 = Lf.Ly.(1f)(1fy) = Lf.Ly.f(f(y)) = 2

By your definition Lx.(Lf.(Ly.f y))
	+11 = Lf.Ly.(1f)(1fy) = something complicated

 _ and multiplication is
 _     Lm.Ln.Lf.m (n f)
Ok

Lnfx.nf(fx) successor function.
Lmn.nm exponetation m^n

 _ Important features of the lambda calculus
 _ 1. In the lambda calculus, *everything* is a function.
 _ 2. In so far as the lambda calculus has a preferred "order
 _    of evaluation", it's "normal order", which amounts to
 _    evaluating things as you need them.
What's this normal order?

 _ 3. The lambda calculus is purely syntactic; two
 _    expressions are "equal" if you can transform one to
 _    the other by the standard transformations.
 _ 4. Evaluation in the lambda calculus works by repeated textual
 _ substitution.

Other questions:
 _ ((lambda (g n) (g g n))
 _  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)

(Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5)

What's the lambda formula for
	= as in =0n
	if as in if(=0n)1
	- as in -n1 ?
and finally, let as in

(let ((f (lambda (f n)
            (if (= 0 n) 1 (* n (f f (- n 1))))))
      (n 5))
   (f f n))

 _ Recursion without a function actually calling itself!

----





-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[Thaddeus L Olczyk]

On 4 Oct 2002 20:20:49 -0700, 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."

To really see a PL that "implements lambda calculus"
lok at Haskel, not Lisp.

Re: Lambda calculus and it relation to LISP

[Joona I Palaste]

Thaddeus L Olczyk <olczyk@interaccess.com> scribbled the following
on sci.math:
> On 4 Oct 2002 20:20:49 -0700, 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."

> To really see a PL that "implements lambda calculus"
> lok at Haskel, not Lisp.

Haskell, not Haskel. In Haskell the backslash \ means the lambda
operator. For example it's possible to say:

(\f. (f 1)) (\x. x + 1), which means:
(\x. x + 1) 1, which means:
1 + 1, which means:
2

Haskell gets its name from Haskell Curry, who has also been attributed
for the concept of "currying", which I'm told should really be called
"schönfinkeling".

-- 
/-- Joona Palaste (palaste@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/
"To doo bee doo bee doo."
   - Frank Sinatra

Re: Lambda calculus and it relation to LISP

[Gareth McCaughan]

William Elliot wrote:

[I said:]
>  _ There are three transformations you're allowed to do, of which the
>  _ most important is one that takes (Lx.E)F into whatever you get by
>  _ substituting E for every (free) occurrence of x in F.
> Provided no free variable of F falls within the scope of a
> bound variable of E.  What are the other two transformations?

Alpha-conversion (rename a variable) and eta-reduction
(turn \x.(f x) into f, when that's safe). The one I
mentioned above is beta-reduction. Yes, the proviso
you quote is correct. I was simplifying.

>  _ The point of all this is that that is, in some sense,
>  _ *all* you need; within this system you can model all
>  _ of mathematics, or at least all the mathematics
>  _ Alonzo Church cared about. You have to "encode"
>  _ everything as a function. For instance, here's a
>  _ famous way of representing the non-negative integers:
>  _     0 "is" Lx.(Lf.(Ly.y))
>  _     1 "is" Lx.(Lf.(Ly.f y))
>  _     2 "is" Lx.(Lf.(Ly.f (f y)))
>  _     3 "is" Lx.(Lf.(Ly.f (f (f y))))
>  _     etc.
> What??  Maybe this is add 0, add 1, etc.

Argle. I'm not quite sure what I was thinking when
I wrote those down. No, it's not add-0, add-1, etc;
it's just a mangled version of what I actually meant.
What I actually meant, coincidentally enough, is ...

> 0 = (Lfx.x)
> 1 = (Lfx.fx)
> 2 = (Lfx.f(fx))
> 3 = (Lfx.f(f(fx)))

... what you wrote.

>  _ Important features of the lambda calculus
>  _ 1. In the lambda calculus, *everything* is a function.
>  _ 2. In so far as the lambda calculus has a preferred "order
>  _    of evaluation", it's "normal order", which amounts to
>  _    evaluating things as you need them.
> What's this normal order?

Always reduce the leftmost thing available.
In particular, when you have an application "f x",
you always prefer to reduce things in f before
things in f. In particular, if it turns out that
you don't need x then you'll never bother reducing
any of its bits.

> Other questions:
>  _ ((lambda (g n) (g g n))
>  _  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
> 
> (Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5)
> 
> What's the lambda formula for
> 	= as in =0n
> 	if as in if(=0n)1
> 	- as in -n1 ?

I believe you know the answers to all these questions :-).

> and finally, let as in
> 
> (let ((f (lambda (f n)
>             (if (= 0 n) 1 (* n (f f (- n 1))))))
>       (n 5))
>    (f f n))
> 
>  _ Recursion without a function actually calling itself!

(let ((x y)) E) === ((lambda (x) E) y).

-- 
Gareth McCaughan  Gareth.McCaughan@pobox.com
.sig under construc

Re: Lambda calculus and it relation to LISP

[gnuist]

Gareth.McCaughan@pobox.com (Gareth McCaughan) wrote in message news:<slrnaq13ce.nmd.Gareth.McCaughan@g.local>...
> William Elliot wrote:

> I believe you know the answers to all these questions :-).

You guys obviously are very talented in lisp. For me to benefit from
your posts, which certainly seem of great promise to me due to my inability
to actually analyze them, I need to bridge the gap from where I am and
what they propound. It will require me to put more effort. Here is what I
have to show and then perhaps you can fill in with your explanations and
what I most request is a concrete example to be able to run on emacs via
its interpreter. Even if you answer one question in depth, it is better
than many superficially.

OK. I have gotten a bibliography of lisp papers. I drove to a library and
got hold of a section of lisp in honor of jm which has a micro-manual for
lisp and a single page eval on p712. I know basic car/cdr/cons and the
notion of list being isomorphic to binary tree. Probably the idea is to have
pre-parsed expression just as the emacs' delimited prefix notation is
pre-associated and precedence-explicit, making interpreter simple and less
on the BNF notation and FiniteStateMachine formalism. I am not a CS so please
do not throw indigestible theoretical rocks w/o concrete examples at me.

Now I have seen examples of lambda where it is used to associate a hook with
the anonymous function. I do not see what advantage this gives over defun
other than saving a name in the name-space. Is there any other advantage
of lambda? Or is defun defined using lambda and name associating function?
The Lisp papers talk of "LABEL" function. But where is it in emacs or what
is its emacs counterpart called?

Here is a lambda function that I know for starters.

( (lambda(x y) (- x y))  1 2)

I can write more complicated defuns, single recursion, gcd, and all classic
stuff. But I am looking for a particularly instructive and clear example
of a double recursion and then probably a tricky one.

In the same way I ask for GRADED examples of use of lambda. I am sure many
of you can just cut and paste from your collection. Examples to illustrate
recursion, etc. And how will you do recursion without/with "LABEL"?

One last question at this stage: I know how you "add-hook" but how do you
create a hook variable in the first place? Is it something particular to
emacs or is it only a lispy object? And a little aside: Can one create
something close to this in C/C++/Java?

There are many kind souls out there with a lot of material and I am going
through it as best as I can. Help from kind souls like you would be very beneficial.

Please answer atleast one question in depth rather than many superficially.

Many thanks again.

And I will be looking how to set the preferred reply group header on
google and implement it if they make that possible.

Re: Lambda calculus and it relation to LISP

[William Elliot]

On 6 Oct 2002, gnuist wrote:
> Here is a lambda function that I know for starters.
>
> ( (lambda(x y) (- x y))  1 2)
>
What the lambda calculus expression for - ?

> I can write more complicated defuns, single recursion, gcd, and all classic
> stuff. But I am looking for a particularly instructive and clear example
> of a double recursion and then probably a tricky one.

What's the lambda calculus expression for = ?
Is it designed to work effectively only for the lambda calculus
expressions for 0,1,2 ... ?




-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[Barb Knox]

In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
gnuist007@hotmail.com (gnuist) wrote:
[snip]

> In the same way I ask for GRADED examples of use of lambda. I am sure many
> of you can just cut and paste from your collection. Examples to illustrate
> recursion, etc. And how will you do recursion without/with "LABEL"?

Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE.  Recursion
is done via the "Y combinator", which is a very interesting
self-referential hack (in the good sense).

For example, here is a recursive factorial function in lambda calculus in
Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
and '1').  It takes one argument (which gets bound to 'n') and returns its
factorial.

    ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
     (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )

Intense, eh?  If you can get your head around this then you're most of the
way towards understanding lambda calculus.  Try desk-checking a few
examples (starting with n=0).  If you want, post the trace of your
desk-checks here and we'll double-check them.

The first line computes the fixed-point of the second line (ound to 'f')
and passes this fixed point to 'f' (as 'ff').  If you want to understand
recursion in lambda calculus (as opposed to in Lisp) then you really do
need learn about fixed-points; see a textbook on recursive function
theory.

Note that it is critical that evaluation be done in "normal order"
(outermost first) rather than in Lisp's "applicative order" (innermost
first); otherwise the Y combinator never terminates.

[snip]

-- 
---------------------------
|  BBB                b    \    barbara minus knox at iname stop com
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   
|  B  B  a  a   r     b  b  |   
|  BBB    aa a  r     bbb   |   
-----------------------------

Re: Lambda calculus and it relation to LISP

[David Kastrup]

see@sig.below (Barb Knox) writes:

> In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
> gnuist007@hotmail.com (gnuist) wrote:
> [snip]
> 
> > In the same way I ask for GRADED examples of use of lambda. I am sure many
> > of you can just cut and paste from your collection. Examples to illustrate
> > recursion, etc. And how will you do recursion without/with "LABEL"?
> 
> Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE.  Recursion
> is done via the "Y combinator", which is a very interesting
> self-referential hack (in the good sense).
> 
> For example, here is a recursive factorial function in lambda calculus in
> Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
> and '1').  It takes one argument (which gets bound to 'n') and returns its
> factorial.
> 
>     ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
>      (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
> 
> Intense, eh?

Also wrong.  This is "Lispish Syntax", actually Scheme.  So we can
check it out:

guile> ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))(lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
standard input:1:27: In expression (f (Y Y)):
standard input:1:27: Wrong number of arguments to #<procedure (ff n)>
ABORT: (wrong-number-of-args)

Type "(backtrace)" to get more information.
guile> (backtrace)

Backtrace:
0* [#<procedure (f)> #<procedure (ff n)>]
1  [#<procedure (Y)> #<procedure (Y)>]
2  (f (Y Y))

Type "(debug-enable 'backtrace)" if you would like a backtrace
automatically if an error occurs in the future.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: David.Kastrup@t-online.de

Re: Lambda calculus and it relation to LISP

[William Elliot]

Gareth.McCaughan@pobox.com
Conventions:  L for lambda;  xyz for (xy)z;  (Lxy.M) for (Lx.(Ly.M))
	N(x/M) for N with every free occurrence of x replaced by M

alpha-conversion:  Lx.N -> Ly.N(x/y), provided no free occurrence of
	x in N falls within the scope of a bound occurrence of y in N.

beta-reduction:  (Lx.N)M -> N(x/M), provided no free occurrence of
	x in N falls within the scope of a bound variable of N that's
	also free in M.

 _ Alpha-conversion (rename a variable) and eta-reduction
 _ (turn \x.(f x) into f, when that's safe). The one I
 _ mentioned above is beta-reduction. Yes, the proviso
 _ you quote is correct. I was simplifying.
When's an eta-reduction safe?  Lx.Nx -> N, provided no free x in N ?
Was this actually used by Alanzo Church or did he merely mention it?

>  _ Important features of the lambda calculus
>  _ 1. In the lambda calculus, *everything* is a function.
>  _ 2. In so far as the lambda calculus has a preferred "order
>  _    of evaluation", it's "normal order", which amounts to
>  _    evaluating things as you need them.
> What's this normal order?
 _ Always reduce the leftmost thing available.
 _ In particular, when you have an application "f x", you
 _ always prefer to reduce things in f before things in f.
What about conversion rules like:
	N -> M ==> NK -> MK
	N -> M ==> KN -> KM
	N -> M ==> Lx.N -> Lx.M ?

 _ In particular, if it turns out that you don't need
 _ x then you'll never bother reducing any of its bits.
Irreducible wff's are all the same bunch of rascals.

> Other questions:
>  _ ((lambda (g n) (g g n))
>  _  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
> (Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5)
>
> What's the lambda formula for
> 	= as in =0n
> 	if as in if(=0n)1
> 	- as in -n1 ?
 _ I believe you know the answers to all these questions :-).
Conclusion jumper.  Alanzo didn't define a - I know of.
His = was rather complicated as I recall, being effective to
	to work just for his numbers.  What I know not.
As for 'if', where did that come from?  Again just for Church numbers?

> and finally, let as in
>
> (let ((f (lambda (f n)
>             (if (= 0 n) 1 (* n (f f (- n 1))))))
>       (n 5))
>    (f f n))
>
>  _ Recursion without a function actually calling itself!
 _ (let ((x y)) E) === ((lambda (x) E) y).

Doesn't make sense.  Are there expressions A,B for which
	A(xy) -> x and B(xy) -> y ?
I don't see how 'let' could be a wwf of the L-calculus.

----





-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[William Elliot]

On 7 Oct 2002, David Kastrup wrote:
> see@sig.below (Barb Knox) writes:
> > For example, here is a recursive factorial function in lambda calculus in
> > Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
> > and '1').  It takes one argument (which gets bound to 'n') and returns its
> > factorial.
> >
> >     ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
> >      (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
>
> Also wrong.  This is "Lispish Syntax", actually Scheme.  So we can
> check it out:
>
> guile> ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
    (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )

What's lambda calculus expressions for -, <, if, = ?



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[Christian Lemburg]

David Kastrup <David.Kastrup@t-online.de> writes:

> see@sig.below (Barb Knox) writes:
> 
> > In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
> > gnuist007@hotmail.com (gnuist) wrote:
> > [snip]
> > 
> > > In the same way I ask for GRADED examples of use of lambda. I am sure many
> > > of you can just cut and paste from your collection. Examples to illustrate
> > > recursion, etc. And how will you do recursion without/with "LABEL"?
> > 
> > Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE.  Recursion
> > is done via the "Y combinator", which is a very interesting
> > self-referential hack (in the good sense).

For a good introduction to this very topic, read Essentials of
Programming Languages, Daniel P. Friedman, Mitchell Wand, and
Christopher T. Haynes, MIT Press, 1992.  An in-depth study of
programming language structure and features. Discusses fundamental
concepts by means of a series of interpreters that are developed in
Scheme, using a formal approach that derives the interpreters from a
formal specification of the language and its features. In-depth
discussion of parameter-passing techniques, continuations,
object-oriented languages, and derivation of a compiler from an
interpreter. This is one of a trio I heartily recommend to any
programmer: SICP, Essentials of Programming Languages, Paradigms of
Artificial Intelligence Programming: Case Studies in Common Lisp.

I think Lambda calculus is covered in Chapter 4 of EOPL.

For those who may understand Perl, but not Lisp, here is the
applicative Y combinator in Perl, maybe it helps.


sub Y {
    my $f = shift;
    sub {
	my $x = shift;
	$f->(sub { my $y = shift; return ($x->($x))->($y)});
    }->(
	sub {
	    my $x = shift;
	    $f->(sub { my $y = shift; return ($x->($x))->($y)});
	});
}

sub countdown {
    my $x = shift;
    return Y(sub { 
		 my $f = shift; 
		 return sub {
		     my $x = shift;
		     if ($x) {
			 print "$x\n";
			 $f->($x - 1);
		     } else {
			 print "yeah!\n";
		     }
		 }})->($x);
}


sub fact {
    my $x = shift;
    return Y(sub { 
		 my $f = shift; 
		 return sub {
		     my $x = shift;
		     if ($x < 2) {
			 return 1;
		     } else {
			 return $x * $f->($x - 1);
		     }
		 }})->($x);
}



countdown(10);
print "fact(5) = ", fact(5), "\n";



-- 
Christian Lemburg, <lemburg@aixonix.de>, http://www.clemburg.com/


 Money is the root of all evil, and man needs roots

Re: Lambda calculus and it relation to LISP

[Barb Knox]

In article <x5bs66h9sx.fsf@tupik.goethe.zz>, David Kastrup
<David.Kastrup@t-online.de> wrote:

> see@sig.below (Barb Knox) writes:
> 
> > In article <9e8ebeb2.0210062058.5c7ab267@posting.google.com>,
> > gnuist007@hotmail.com (gnuist) wrote:
> > [snip]
> > 
> > > In the same way I ask for GRADED examples of use of lambda. I am sure many
> > > of you can just cut and paste from your collection. Examples to illustrate
> > > recursion, etc. And how will you do recursion without/with "LABEL"?
> > 
> > Lambda calculus does not have Lisp's LABEL/LABELS or DEFUN/DE.  Recursion
> > is done via the "Y combinator", which is a very interesting
> > self-referential hack (in the good sense).
> > 
> > For example, here is a recursive factorial function in lambda calculus in
> > Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
> > and '1').  It takes one argument (which gets bound to 'n') and returns its
> > factorial.
> > 
> >     ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
> >      (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
> > 
> > Intense, eh?
> 
> Also wrong.  This is "Lispish Syntax", actually Scheme.

No, not wrong.  It's *lambda calculus* with a Lispish (or Schemish if you
prefer) syntax.  It is not Scheme.  The original question was about lambda
calculus.

> So we can check it out:
> 
> guile> ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y
Y)))))(lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
> standard input:1:27: In expression (f (Y Y)):
> standard input:1:27: Wrong number of arguments to #<procedure (ff n)>
> ABORT: (wrong-number-of-args)
> 
> Type "(backtrace)" to get more information.
> guile> (backtrace)
> 
> Backtrace:
> 0* [#<procedure (f)> #<procedure (ff n)>]
> 1  [#<procedure (Y)> #<procedure (Y)>]
> 2  (f (Y Y))
> 
> Type "(debug-enable 'backtrace)" if you would like a backtrace
> automatically if an error occurs in the future.

I never claimed it would run in Scheme.  IIRC, Scheme does
applicative-order evaluation, not normal-order.  Also IIRC, Scheme does
not do "currying", whereby, e.g., ((lambda (a b) (+ a b)) 3) --> (lambda
(b) (+ 3 b)).

You can get around the currying by changing the second line to:
     (lambda (ff) (lambda (n) ... )) )
but that doesn't help with the evaluation order.

-- 
---------------------------
|  BBB                b    \    barbara minus knox at iname stop com
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   
|  B  B  a  a   r     b  b  |   
|  BBB    aa a  r     bbb   |   
-----------------------------

Re: Lambda calculus and it relation to LISP

[Barb Knox]

In article <20021007025544.G57236-100000@agora.rdrop.com>, William Elliot
<mars@xx.com> wrote:

> On 7 Oct 2002, David Kastrup wrote:
> > see@sig.below (Barb Knox) writes:
> > > For example, here is a recursive factorial function in lambda calculus in
> > > Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
> > > and '1').  It takes one argument (which gets bound to 'n') and returns its
> > > factorial.
> > >
> > >     ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
> > >      (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
[snip]

> What's lambda calculus expressions for -, <, if, = ?

'-' and '<' are a bit tricky, as is most LC arithmetic using Church
numerals -- see a textbook that covers LC.

'if' is usually
  (lambda (test) (lambda (ifTrue) (lambda (ifFalse) ((test ifTrue) ifFalse))))
or
  (lambda (test ifTrue ifFalse) (test ifTrue ifFalse))

where the value for TRUE is
  (lambda (ifTrue ifFalse) ifTrue)
and the value for FALSE is
  (lambda (ifTrue ifFalse) ifFalse)

As you can see, raw LC makes a pretty horrible programming language, which
is why useable functional languages (1) are strongly typed, and (2) have
primitives for numbers, strings, etc. so that one does not have to deal
with Church numerals, etc.

-- 
---------------------------
|  BBB                b    \    barbara minus knox at iname stop com
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   
|  B  B  a  a   r     b  b  |   
|  BBB    aa a  r     bbb   |   
-----------------------------

Re: Lambda calculus and it relation to LISP

[William Elliot]

see@sig.below
William Elliot <mars@xx.com> wrote:

Using L for lambda with Church's old notion and -> for reduces

factorial n
 > ((lambda (f) ( (lambda (Y) (f (Y Y)) ) (lambda (Y) (f (Y Y)) )))
 >  (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
! -> Ln.(Lf.(Ly.f(yy))(Ly.f(yy))) (Lfn.if(<n1)1(*n(f(-n1)))

Why not just use
	Lfn.(<n1)1(*n(f-n1))
instead of
	Lfn.if(<n1)1(*n(f(-n1)) ?

> What's lambda calculus expressions for -, <, if, = ?
 _ '-' and '<' are a bit tricky, as is most LC arithmetic using Church
 _ numerals -- see a textbook that covers LC.
It looks like <nm reduces to false or true for Church numerals n,m.
Likely -0n -> 0;  -n0 -> n;  -(+n1)1 -> n

 _ 'if' is usually
 _   (lambda (test ifTrue ifFalse) (test ifTrue ifFalse))
if -> Lxyz.xyz
if true -> Lyz.y -> true
if false -> Lyz.z -> false
if true NM -> N
if false NM -> M

 _ where the value for TRUE is
 _   (lambda (ifTrue ifFalse) ifTrue)
 _ and the value for FALSE is
 _   (lambda (ifTrue ifFalse) ifFalse)
True is Lxy.x
False is Lxy.y which is Church numeral 0.

Glancing with Google, yicks, the Calculi of Lambda conversion is
unreconizable mutant of Alanzo Church's original work.

----





-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[Gareth McCaughan]

William Elliot wrote:

>  _ Alpha-conversion (rename a variable) and eta-reduction
>  _ (turn \x.(f x) into f, when that's safe). The one I
>  _ mentioned above is beta-reduction. Yes, the proviso
>  _ you quote is correct. I was simplifying.
> When's an eta-reduction safe?  Lx.Nx -> N, provided no free x in N ?
> Was this actually used by Alanzo Church or did he merely mention it?

I am not (nor have I claimed to be) an expert on the
work of Church, although I do know that his first name
is spelt "Alonzo". When I say "lambda calculus", I do not
necessarily mean "exactly what Church wrote about, with
no consideration of anything developed later".

> >  _ Important features of the lambda calculus
> >  _ 1. In the lambda calculus, *everything* is a function.
> >  _ 2. In so far as the lambda calculus has a preferred "order
> >  _    of evaluation", it's "normal order", which amounts to
> >  _    evaluating things as you need them.
> > What's this normal order?
>  _ Always reduce the leftmost thing available.
>  _ In particular, when you have an application "f x", you
>  _ always prefer to reduce things in f before things in f.
> What about conversion rules like:
> 	N -> M ==> NK -> MK
> 	N -> M ==> KN -> KM
> 	N -> M ==> Lx.N -> Lx.M ?

What about them?

> > Other questions:
> >  _ ((lambda (g n) (g g n))
> >  _  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
> >
> > (Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5)

I'd just like to mention that it was not I who wrote
the _-quoted material there.

> > What's the lambda formula for
> > 	= as in =0n
> > 	if as in if(=0n)1
> > 	- as in -n1 ?
>  _ I believe you know the answers to all these questions :-).
> Conclusion jumper.

The obvious conclusion, when someone alternates between
saying "that's obviously wrong, you mean X" and "what
does Y mean?" (with Y usually being something rather
elementary) is that the latter question is not sincere,
but is intended to be a lightly veiled disagreement,
a suggestion that Y is really nonsense, or an attempt
to make the reader reconsider. Maybe I should be more
explicit: I believe that for each of those questions,
you either know a good answer or believe with some reason
that there is no good answer.

(I happen to find being addressed in this way rather
disagreeable, but that's not your problem. :-))

>                     Alanzo didn't define a - I know of.
> His = was rather complicated as I recall, being effective to
> 	to work just for his numbers.  What I know not.
> As for 'if', where did that come from?  Again just for Church numbers?

I would expect = to be quite complicated.
I have no idea whether Church defined subtraction,
but it's not especially hard (though you'd want to
take some care about the domain, if working generally
with only non-negative integers). (Note that "quite
complicated" and "not especially hard" are consistent;
I would expect = and - to be roughly equally hard.)

I don't understand what you mean by "just for Church
numbers?" regarding "if"; it would be "just for Church
booleans", which IIRC are

  T ::= \xy.x
  F ::= \xy.y

or perhaps the other way around. Then "if" is almost
trivial:

  if ::= \xyz.xyz

but you don't actually need an "if", since the boolean
itself will do the work for you. So you can translate
"if C then X else Y" into CXY.

> > and finally, let as in
> >
> > (let ((f (lambda (f n)
> >             (if (= 0 n) 1 (* n (f f (- n 1))))))
> >       (n 5))
> >    (f f n))
> >
> >  _ Recursion without a function actually calling itself!

Note, again, that I didn't write any of that.

>  _ (let ((x y)) E) === ((lambda (x) E) y).
> 
> Doesn't make sense.  Are there expressions A,B for which
> 	A(xy) -> x and B(xy) -> y ?
> I don't see how 'let' could be a wwf of the L-calculus.

I never suggested that "let" is a wff of the lambda
calculus. I don't think the person who wrote the "let"
stuff did, either. However, expressions using "let"
are readily translated into ones using "lambda" instead,
and neat tricks like Y are expressible in the lambda
calculus even if they're nicer to read when written
using "let". (For people used to "let", anyway.)

-- 
Gareth McCaughan  Gareth.McCaughan@pobox.com
.sig under construc

Re: Lambda calculus and it relation to LISP

[Gareth McCaughan]

"gnuist" wrote:

> You guys obviously are very talented in lisp. For me to benefit from
> your posts, which certainly seem of great promise to me due to my inability
> to actually analyze them, I need to bridge the gap from where I am and
> what they propound. It will require me to put more effort. Here is what I
> have to show and then perhaps you can fill in with your explanations and
> what I most request is a concrete example to be able to run on emacs via
> its interpreter. Even if you answer one question in depth, it is better
> than many superficially.

Lambda calculus was never particularly intended to be
a thing for running on computers in general, or in Emacs
in particular. There *were* no computers, I think, when
Church started working on the lambda calculus.

> OK. I have gotten a bibliography of lisp papers. I drove to a library and
> got hold of a section of lisp in honor of jm which has a micro-manual for
> lisp and a single page eval on p712. I know basic car/cdr/cons and the
> notion of list being isomorphic to binary tree. Probably the idea is to have
> pre-parsed expression just as the emacs' delimited prefix notation is
> pre-associated and precedence-explicit, making interpreter simple and less
> on the BNF notation and FiniteStateMachine formalism. I am not a CS so please
> do not throw indigestible theoretical rocks w/o concrete examples at me.

Yes, the idea is as you say. (But I think it would be
a little more accurate to say: originally, parsing wasn't
even a part of McCarthy's concern, any more than when
you talk about arithmetic you're usually thinking about
how to convert strings of decimal digits into actual
numbers.)

> Now I have seen examples of lambda where it is used to associate a hook with
> the anonymous function. I do not see what advantage this gives over defun
> other than saving a name in the name-space. Is there any other advantage
> of lambda? Or is defun defined using lambda and name associating function?

Hmm, OK. At this point what you're talking about really
isn't "the lambda calculus"; that was one of the points
I was making (and William Elliot too, I think). It's just
a notation for functions that happens to use the word
"lambda". This isn't a problem, by the way, but it's
worth being aware of it.

The advantage of making anonymous functions is threefold.

1. As you say, it saves a name which would otherwise
   clutter up some namespace or other.

2. It's more compact.

3. It lets you define the function where it's being used,
   rather than putting it somewhere else and making the
   reader check back for the definition.

As for how DEFUN is defined: I'm not sure about Emacs,
and I'm too lazy to check :-), but in the Common Lisp
implementation I use, DEFUN is a macro whose uses expand
to things like

    (C::%DEFUN 'F #'(LAMBDA () (BLOCK F 123)) NIL '(DEFUN F () 123))

where C::%DEFUN is a plain ol' function, which associates
a function (and a bit of other stuff) with a name.

> The Lisp papers talk of "LABEL" function. But where is it in emacs or what
> is its emacs counterpart called?

Emacs doesn't have LABELS. There's a "cl" package -- do
(require 'cl) -- that probably defines it for you.

> Here is a lambda function that I know for starters.
> 
> ( (lambda(x y) (- x y))  1 2)
> 
> I can write more complicated defuns, single recursion, gcd, and all classic
> stuff. But I am looking for a particularly instructive and clear example
> of a double recursion and then probably a tricky one.
> 
> In the same way I ask for GRADED examples of use of lambda. I am sure many
> of you can just cut and paste from your collection. Examples to illustrate
> recursion, etc. And how will you do recursion without/with "LABEL"?

There are ways to do recursion using just LAMBDA; see the
bizarre-looking things a few people have posted earlier
in the thread. They've usually used LET, which elisp
has, but in any case the LETs can be replaced with LAMBDAs
by rearranging a little. I think you'd need to insert
FUNCALL in quite a lot of places to make that trick work
in elisp. Anyway, it's the Wrong Answer (tm).

The Right Answer (tm) is: If you want recursion, then
either (require 'cl) and use the LABELS macro defined
there, or else give your functions names using DEFUN.

> One last question at this stage: I know how you "add-hook" but how do you
> create a hook variable in the first place? Is it something particular to
> emacs or is it only a lispy object? And a little aside: Can one create
> something close to this in C/C++/Java?

The word "hook" has more than one meaning.

1. Anything that lets you specify something that should
   happen on particular occasions, thus extending the
   functionality of a system someone else has built.

   Hooks in *this* sense can be found all over the place;
   certainly not only in Lisp and similar languages. For
   instance, the atexit function in C's standard library
   is for defining hooks.

2. A variable containing a list of functions or function names,
   which will be called in particular circumstances.

   This meaning is, I think, peculiar to Emacs, though
   it's a straightforward enough way to do hooks (in
   sense 1) that I won't be surprised if it's found
   elsewhere.

Yes, you can create hook-y things in C or C++ or Java.
Here it is in C, for instance:

    typedef struct Hook Hook;
    struct Hook {
      void (*f)(void *);
      Hook * next;
    };

    void run_hook_functions(const Hook * h, void * context) {
      while (h) {
        h->f(context);
        h = h->next;
      }
    }

    Hook * add_to_hook(Hook * h, void (*f)(void *)) {
      Hook * result = safe_malloc(sizeof(Hook));
      result->f = f;
      result->next = h;
      return result;
    }

    #define ADD_HOOK(h,f) ((h)=add_to_hook((h),(f)))

It's more pleasant to do this sort of thing in Lisp-like
languages, though. Partly because you have anonymous
functions, partly because -- at least in better Lisps
than elisp -- your functions are actually closures (which
means, e.g., that you don't need the context argument
nonsense found above).

-- 
Gareth McCaughan  Gareth.McCaughan@pobox.com
.sig under construc

Re: Lambda calculus and it relation to LISP

[ozan s yigit]

Christian Lemburg:

> For a good introduction to this very topic, read Essentials of
> Programming Languages, Daniel P. Friedman, Mitchell Wand, and
> Christopher T. Haynes, MIT Press, 1992. [description elided]

i should point out that there is a second edition published in 2001.
its chapter on types now includes type inferencing that i think used
to float about in the ftp area of their code directory. [the book is
now somewhat thinner, but i cannot tell if it now excludes some
material, or just has thinner pages]

oz
---
if you do not work on important problems
how can you expect to do important work? -- richard w. hamming

Re: Lambda calculus and it relation to LISP

[David Kastrup]

see@sig.below (Barb Knox) writes:

> In article <x5bs66h9sx.fsf@tupik.goethe.zz>, David Kastrup
> <David.Kastrup@t-online.de> wrote:
> 
> > see@sig.below (Barb Knox) writes:
> > 
> > > For example, here is a recursive factorial function in lambda calculus in
> > > Lispish syntax (assuming apprioriate definitions for 'if', '<', '*', '-',
> > > and '1').  It takes one argument (which gets bound to 'n') and returns its
> > > factorial.
> > > 
> > >     ((lambda (f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
> > >      (lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )
> > > 
> > > Intense, eh?
> > 
> > Also wrong.  This is "Lispish Syntax", actually Scheme.
> 
> > So we can check it out:
> > 
> No, not wrong.  It's *lambda calculus* with a Lispish (or Schemish if you
> prefer) syntax.  It is not Scheme.  The original question was about lambda
> calculus.
> 
> 
> I never claimed it would run in Scheme.  IIRC, Scheme does
> applicative-order evaluation, not normal-order.  Also IIRC, Scheme does
> not do "currying", whereby, e.g., ((lambda (a b) (+ a b)) 3) --> (lambda
> (b) (+ 3 b)).
> 
> You can get around the currying by changing the second line to:
>      (lambda (ff) (lambda (n) ... )) )
> but that doesn't help with the evaluation order.

Lambda calculus is an abtract concept.  An abstract concept with
"currying"?

Anyhow, here is how to do a factorial in Scheme:
((lambda (f n) (f f n))
 (lambda (f n) (if (< n 1) 1 (* n (f f (- n 1)))))
 5)

If we want to start from a function that does not look
self-referential (namely, does not have (f f ...) in its core
definition from where we want to have it recurse), things get more
intricate:
((lambda (f g n) (g (f f g) n))
 (lambda (f g) (lambda (n) (g (f f g) n)))
 (lambda (f n) (if (< n 1) 1 (* n (f (- n 1)))))
5)

No curry involved here, but still rather spicy.  Don't get burned.
Anybody see a simpler solution for cranking up recursion on the last
lambda-line?

Oh, since we are here also in the Emacs groups: the equivalents would
be
((lambda (f n) (funcall f f n))
 (lambda (f n) (if (zerop n) 1 (* n (funcall f f (1- n)))))
 5)

((lambda (f g n) (funcall g (funcall f f g) n))
 (lambda (f g) `(lambda (n) (,g (funcall ,f ,f ,g) n)))
 (lambda (f n) (if (zerop n) 1 (* n (funcall f (1- n)))))
 5)


-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: David.Kastrup@t-online.de

Re: Lambda calculus and it relation to LISP

[William Elliot]

Gareth.McCaughan@pobox.com retorted:
> William Elliot wrote:
>  _ Alpha-conversion (rename a variable) and eta-reduction
>  _ (turn \x.(f x) into f, when that's safe). The one I
>  _ mentioned above is beta-reduction. Yes, the proviso
>  _ you quote is correct. I was simplifying.
> When's an eta-reduction safe?  Lx.Nx -> N, provided no free x in N ?
> Was this actually used by Alanzo Church or did he merely mention it?
 _ I am not (nor have I claimed to be) an expert on the
 _ work of Church, although I do know that his first name
 _ is spelt "Alonzo".
Good to know as I'd like to locate a copy of his original work.

 _ When I say "lambda calculus", I do not necessarily mean "exactly
 _ what Church wrote about, with no consideration of anything
 _ developed later".
Briefly looking thru Google, I discovered what's become of his work is
nearly unrecognizable.

> >  _ Important features of the lambda calculus
> >  _ 1. In the lambda calculus, *everything* is a function.
> >  _ 2. In so far as the lambda calculus has a preferred "order
> >  _    of evaluation", it's "normal order", which amounts to
> >  _    evaluating things as you need them.
> > What's this normal order?
>  _ Always reduce the leftmost thing available.
>  _ In particular, when you have an application "f x", you
>  _ always prefer to reduce things in f before things in f.
> What about conversion rules like:
> 	N -> M ==> NK -> MK
> 	N -> M ==> KN -> KM
> 	N -> M ==> Lx.N -> Lx.M ?
 _ What about them?
Are they allowed or prevented by the normal order of -> reductions?

> > Other questions:
> >  _ ((lambda (g n) (g g n))
> >  _  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
> >
> > (Lgn.ggn)(Lfn.if(=0n)1 (*n(ff(-n1))))5)
 _ I'd just like to mention that it was not I who wrote
 _ the _-quoted material there.
Correct, I was hoping you'd know or others in the thread would notice.

> > What's the lambda formula for
> > 	= as in =0n
> > 	if as in if(=0n)1
> > 	- as in -n1 ?
>  _ I believe you know the answers to all these questions :-).
> Conclusion jumper.
 _ I believe that for each of those questions, you either know a good
 _ answer or believe with some reason that there is no good answer.
Not so.

 _ (I happen to find being addressed in this way rather
 _ disagreeable, but that's not your problem. :-))
I too felt poorly addressed by an abrupt uninformative response.

>                     Alanzo didn't define a - I know of.
> His = was rather complicated as I recall, being effective to
> 	to work just for his numbers.  What I know not.
> As for 'if', where did that come from?  Again just for Church numbers?
 _ I would expect = to be quite complicated.
I'd expect so too.  I remember something vaguely so.

 _ I have no idea whether Church defined subtraction,
I'm not sure he did.  Nor dare I vouch he didn't.

 _ but it's not especially hard (though you'd want to
 _ take some care about the domain, if working generally
 _ with only non-negative integers). (Note that "quite
 _ complicated" and "not especially hard" are consistent;
 _ I would expect = and - to be roughly equally hard.)
I'd expect the usefulness of the expression would be limited
to Church numbers.

 _ I don't understand what you mean by "just for Church
 _ numbers?" regarding "if"; it would be "just for Church
 _ booleans", which IIRC are
 _   T ::= \xy.x
 _   F ::= \xy.y
That I'm beginning to find out.  F by the way is Church numeral 0.

 _ or perhaps the other way around. Then "if" is almost
 _ trivial:
 _   if ::= \xyz.xyz
 _ but you don't actually need an "if", since the boolean
 _ itself will do the work for you. So you can translate
 _ "if C then X else Y" into CXY.
Yes, I was thinking that.  So if ::= Lxyz.xyz is mostly for
	ease in reading and understanding expressions.

> > and finally, let as in
> > (let ((f (lambda (f n)
> >             (if (= 0 n) 1 (* n (f f (- n 1))))))
> >       (n 5))
> >    (f f n))
> >  _ Recursion without a function actually calling itself!
 _ Note, again, that I didn't write any of that.
Your comments have been are helpful.

>  _ (let ((x y)) E) === ((lambda (x) E) y).
> Doesn't make sense.  Are there expressions A,B for which
> 	A(xy) -> x and B(xy) -> y ?
> I don't see how 'let' could be a wwf of the L-calculus.
 _ I never suggested that "let" is a wff of the lambda
 _ calculus. I don't think the person who wrote the "let"
 _ stuff did, either. However, expressions using "let"
 _ are readily translated into ones using "lambda" instead,
 _ and neat tricks like Y are expressible in the lambda
 _ calculus even if they're nicer to read when written
 _ using "let". (For people used to "let", anyway.)
Thanks for confirming that.  When it comes to lambda calculi I feel like
I'm speaking ye olde King's English.

--
 _ There *were* no computers, I think, when
 _ Church started working on the lambda calculus.
I read his work in the late fifties and was much enamored by it.
As I recall, it was published in the late 1930's

 _ Hmm, OK. At this point what you're talking about really
 _ isn't "the lambda calculus"; that was one of the points
 _ I was making (and William Elliot too, I think). It's just
 _ a notation for functions that happens to use the word
 _ "lambda". This isn't a problem, by the way, but it's
 _ worth being aware of it.
Indeed.

 _ The advantage of making anonymous functions is threefold.
Yes, one notation I've seen is (x_i)_i or (x_i)_(i in I).
For example (2^n)_n or (2^n)_(n in N);
	also (2^r)_r or to be exact (2^r)_(r in R)
is the function f(x) = 2^x

 _ 1. As you say, it saves a name which would otherwise
 _    clutter up some namespace or other.
 _ 2. It's more compact.
 _ 3. It lets you define the function where it's being used,
 _    rather than putting it somewhere else and making the
 _    reader check back for the definition.

-- recursion from afar
>   ((lambda (g n) (g g n))
>    (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
So it's ok to understand that by thinking about
((lambda (g n) (g g n))
(lambda (f n) ((= 0 n) 1 (* n (f f (- n 1))))) 5)

(Lfn.ffn) (Lfn.(=0n)1(*n(ff(-n1)))) 5

Have I decipher 5 correctly as the number of iterations?
Well then, what happens with (my conclusion at end)
(Lfn.ffn) (Lfn.(=0n)1(*n(ff(-n1)))) 0 ?

(Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) 0
(=00)1(*0((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) (-01)))
1

Hm... What about
(Lfn.ffn) (Lfn.(=0n)1(*n(ff(-n1)))) 1 ?

(Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) 1
(=01)1(*1((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) (-11)))
*1((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) (-11))
*1((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) 0)
*11
1

(Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) 2
(=02)1(*2((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) (-21)))
*2((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) (-21))
*2((Lfn.(=0n)1(*n(ff(-n1)))) (Lfn.(=0n)1(*n(ff(-n1)))) 1)
*2(*11)

Ah, the factorial function, 5! in the case of the orginal example.

----





-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[James Wong]

>
> While we are on the topic of Scheme and recursion:
> ((lambda (f n) (f f n))
>  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
> Recursion without a function actually calling itself!
>

This was an "Extra for Experts" hw problem for us in Berkeley. I didn't get
it, so I tip my hat to you.

Re: Lambda calculus and it relation to LISP

[William Elliot]

On Wed, 9 Oct 2002, James Wong wrote:

> > While we are on the topic of Scheme and recursion:
> > ((lambda (f n) (f f n))
> >  (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
> >
> > Recursion without a function actually calling itself!
>
> This was an "Extra for Experts" hw problem for us in Berkeley. I didn't get
> it, so I tip my hat to you.
>
It reduces to factorial 5.



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: Lambda calculus and it relation to LISP

[Alfred Einstead]

William Elliot <mars@xx.com> wrote:
> > ((lambda (x) x x) (lambda (x) x x))
> (Lx.xx)(Lx.xxx)

That one, however, DOES has a normal form: the
rational infinite expression
              DT -> ((((...)T)T)T)T
where
           D = lambda x. xx
           T = lambda x. xxx

In GNUese, this is the rational infinite lambda
expression Z, where Z is the GNUbreviation of ZT.

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).

Re: Lambda calculus and it relation to LISP

[William Elliot]

On 11 Oct 2002, Alfred Einstead wrote:

> William Elliot <mars@xx.com> wrote:
> > > ((lambda (x) x x) (lambda (x) x x))
> > (Lx.xx)(Lx.xxx)
>
> That one, however, DOES has a normal form: the
> rational infinite expression
>               DT -> ((((...)T)T)T)T
> where
>            D = lambda x. xx
>            T = lambda x. xxx
>
> In GNUese, this is the rational infinite lambda
> expression Z, where Z is the GNUbreviation of ZT.
>
dd -> dd -> dd -> dd -> dd -> ...
dt -> ttt -> tttt -> ttttt -> ...

Neither reduces to stable form without further reductions to be made.



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----