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.
From: Luke A. Olbrish
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <7vbs69b9wr.fsf@gehennom.net>
·········@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
<············@cc.gatech.edu>
On 5 Oct 2002, Luke A. Olbrish wrote:
> ·········@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! =-----
William Elliot <····@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.
On 11 Oct 2002, Alfred Einstead wrote:
> William Elliot <····@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! =-----
············@cc.gatech.edu (Luke A. Olbrish) writes:
> ·········@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: ·············@t-online.de
David Kastrup <·············@t-online.de> 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!
Just being curious: What definition of "itself" did you use to arrive
at that conclusion?
--
Marcus Breiing
···················@breiing.com (will expire)
Marcus Breiing <············@breiing.com> writes:
> David Kastrup <·············@t-online.de> 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!
>
> Just being curious: What definition of "itself" did you use to arrive
> at that conclusion?
Well, for clarity rephrase that as
((lambda (g n) (g g n))
(lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
The first of those functions does not call itself, but merely calls a
function passed into it as an argument. The function passed into it
as an argument does not call itself, but calls a function passed into
it as an argument.
So both of those calls are not explicitly recursive, and they could
not be because they are anonymous lambda expressions, anyway.
Still, recursion happens. Personally, I find this a bit G�delian.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
David Kastrup <·············@t-online.de> wrote in message news:<··············@tupik.goethe.zz>...
> Marcus Breiing <············@breiing.com> writes:
>
> > David Kastrup <·············@t-online.de> 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!
> >
> > Just being curious: What definition of "itself" did you use to arrive
> > at that conclusion?
>
> Well, for clarity rephrase that as
> ((lambda (g n) (g g n))
> (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
> The first of those functions does not call itself, but merely calls a
> function passed into it as an argument. The function passed into it
> as an argument does not call itself, but calls a function passed into
> it as an argument.
``A function passed into it as an argument'' is a meta-variable; when
the call actually takes place, a concrete instance is substituted for
this meta-variable. Some specific function is called. In the above
system, that instance is the closure itself.
> So both of those calls are not explicitly recursive, and they could
> not be because they are anonymous lambda expressions, anyway.
>
> Still, recursion happens. Personally, I find this a bit G�delian.
So what you are saying is that your notion of ``itself'' centers on
statically determined symbolic references, ruling out consideration of
the dynamically established instantiations and their relationships.
David Kastrup <·············@t-online.de> wrote:
> Marcus Breiing <············@breiing.com> writes:
>> Just being curious: What definition of "itself" did you use to arrive
>> at that conclusion?
> Well, for clarity rephrase that as
> ((lambda (g n) (g g n))
> (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
Thanks, although it was perfectly clear already. I guess my question
was a bit unclear. For more clarity, let's rephrase your expression
equivalently using let:
(let ((f (lambda (f n)
(if (= 0 n) 1 (* n (f f (- n 1))))))
(n 5))
(f f n))
You call f, passing it the very same f. Now, in what way is this f
calling f not calling "itself"? To me, it would require a special
notion of "itself". That's why I asked what I asked.
--
Marcus Breiing
···················@breiing.com (will expire)
From: Thien-Thi Nguyen
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <kk9u1k0d8qm.fsf@glug.org>
Marcus Breiing <············@breiing.com> writes:
> (let ((f (lambda (f n)
> (if (= 0 n) 1 (* n (f f (- n 1))))))
> (n 5))
> (f f n))
>
> You call f, passing it the very same f. Now, in what way is
> this f calling f not calling "itself"? To me, it would require
> a special notion of "itself". That's why I asked what I asked.
you have introduced an antecedent (the "it") for the self to call.
the previous formulations did not have this, thus the function is
said not to call itself. the distinction is very minor or very
major depending on how much (and when) you value the binding act.
[newsgroups trimmed.]
thi
Marcus Breiing <············@breiing.com> writes:
> David Kastrup <·············@t-online.de> wrote:
> > Marcus Breiing <············@breiing.com> writes:
>
> >> Just being curious: What definition of "itself" did you use to arrive
> >> at that conclusion?
>
> > Well, for clarity rephrase that as
> > ((lambda (g n) (g g n))
> > (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
> Thanks, although it was perfectly clear already. I guess my question
> was a bit unclear. For more clarity, let's rephrase your expression
> equivalently using let:
>
> (let ((f (lambda (f n)
> (if (= 0 n) 1 (* n (f f (- n 1))))))
> (n 5))
> (f f n))
Better do it renamed:
(let ((g (lambda (f n)
(if (= 0 n) 1 (* n (f f (- n 1))))))
(n 5))
(g g n))
> You call f, passing it the very same f.
Yes.
> Now, in what way is this f calling f not calling "itself"?
It would not know it. f is not written as a recursive function,
since it does not call itself explicitly. It just calls what it
passed into it as argument.
f is calling itself, but not via an explicit recursion.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
David Kastrup <·············@t-online.de> wrote:
> f is calling itself, but not via an explicit recursion.
Funny:) Your original claim was:
Recursion without a function actually calling itself!
Looks like this discussion is leaving you slightly confused. I think
the post by Kaz Kylheku is a good guess at where you went wrong.
Specifically, it is certainly true that looking at
(lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1)))))
you can say that you don't see an explicit call to the function
itself. It is also true that in
((lambda (g n) (g g n))
(lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
you get recursive calls by the inner function to itself. You just
can't combine these two statements about two different Scheme
expressions into one in the way you did.
--
Marcus Breiing
···················@breiing.com (will expire)
Marcus Breiing <············@breiing.com> writes:
> David Kastrup <·············@t-online.de> wrote:
>
> > f is calling itself, but not via an explicit recursion.
>
> Funny:) Your original claim was:
>
> Recursion without a function actually calling itself!
>
> Looks like this discussion is leaving you slightly confused. I think
> the post by Kaz Kylheku is a good guess at where you went wrong.
> Specifically, it is certainly true that looking at
>
> (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1)))))
>
> you can say that you don't see an explicit call to the function
> itself. It is also true that in
>
> ((lambda (g n) (g g n))
> (lambda (f n) (if (= 0 n) 1 (* n (f f (- n 1))))) 5)
>
> you get recursive calls by the inner function to itself. You just
> can't combine these two statements about two different Scheme
> expressions into one in the way you did.
Well, so shame me more: tell me your wisdom about the following ditty
in Scheme I just came up with:
((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)
Ok, the last line is the function that is doing the work. Its
arguments are a function and a number, and what it calls is just a
function receiving a number as its argument. So it can't even call
itself (different argument lists). The way this is wrapped up, it
does call a function which has been fabricated by using a different
incarnation of itself as one ingredient.
So wise master, have pity on the poor confused ones: we have four
times written lambda in the above expression: which functions are
called recursively?
Oh, and since we are also posting in comp.lang.lisp, here the same in
that language:
((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: ·············@t-online.de
David Kastrup <·············@t-online.de> wrote:
> Well, so shame me more: tell me your wisdom
If you post something that might look interesting to somebody, don't
be surprised if people actually get interested. Then, if these
interested people hit a snag in trying to make sense of what you have
on offer, don't be surprised if they ask and start a discussion. And
finally, if your amazing discovery turns out not to be that amazing
after all, please don't act surprised or hurt if that fact gets some
airtime during the show. Instead of acting hurt and coming up with
yet another piece of Scheme (as if that'd prove anything about what
you asserted in the original posting about a different Scheme
expression) you would have better spent the time contemplating the
points raised in Kaz's posting, which is basically what you also found
and ignored in my own latest posting in this thread.
> about the following ditty in Scheme I just came up with:
> ((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)
OK, so you invented mutual recursion, which gets you "recursion
without a function calling itself" after all, if only given suitable
definitions of the various terms used. Of course you can have *that*
without the obfuscatory gimmicks:
(define (g n) (f n))
(define (f n) (if (< n 1) 1 (* n (g (- n 1)))))
(f 5)
> Oh, and since we are also posting in comp.lang.lisp, here the same
> in that language:
> ((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)
If only you had play-tested your ditty a bit longer before proceeding
to Release 1.0... Hint: Backquote syntax doesn't do what you seem to
think it does.
--
Marcus Breiing
···················@breiing.com (will expire)
Marcus Breiing <············@breiing.com> writes:
> David Kastrup <·············@t-online.de> wrote:
>
>
> > ((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)
>
> OK, so you invented mutual recursion, which gets you "recursion
> without a function calling itself" after all, if only given suitable
> definitions of the various terms used.
> Of course you can have *that* without the obfuscatory gimmicks:
>
> (define (g n) (f n))
> (define (f n) (if (< n 1) 1 (* n (g (- n 1)))))
> (f 5)
Which is not lambda-calculus as it is not side-effect free. And so
is completely missing the point. The point was to have a function
that is basically getting a one-argument function as its argument to
call itself in pure lambda-calculus.
If we get out of lambda calculus, we could do this easily by using
the function "recurse" defined in the following way:
(define (recurse g . args)
(let ((f (lambda (f g) (lambda args (apply g (f f g) args)))))
(apply (f f g) args)))
And then a simple
(recurse (lambda (f n) (if (< n 1) 1 (* n (f (- n 1))))) 5)
will thwart the given function to recurse on itself instead of a
different function. But the point, which you have missed completely,
was to do this in lambda calculus.
> > Oh, and since we are also posting in comp.lang.lisp, here the same
> > in that language:
>
> > ((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)
>
> If only you had play-tested your ditty a bit longer before proceeding
> to Release 1.0...
Release? Who is talking releases here?
> Hint: Backquote syntax doesn't do what you seem to think it does.
Oh, it works perfectly well, thank you, and does quite what I seem to
think it does, as can easily be shown by decompiling it and running
it through the Lisp debugger.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
David Kastrup <·············@t-online.de> wrote:
> But the point, which you have missed completely, was to do this in
> lambda calculus.
Sigh. Maintaining a coherent conversation with you is somewhat
exasperating. This subthread is a discussion of an excited claim of
yours about "recursion without a function actually calling itself,"
and the whole thing was quite clearly placed within the context of the
programming language *Scheme* by none other than yourself:
| 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!
You really have no grounds for acting surprised or hurt when people
take seriously what you write. How are we to know that you don't?
While on the topic of thin skin, looking back into your first post in
this sideline of discussion we find you commenting on another poster's
contribution with the charming line:
| That's gibberish.
I'd have thought that someone dishing it out like that would know how
to deal with a not nearly as bluntly put critique of his own work.
[Backquote syntax]
> Oh, it works perfectly well, thank you, and does quite what I seem
> to think it does, as can easily be shown by decompiling it and
> running it through the Lisp debugger.
I just did run it in (Common) Lisp, and it bombed spectacularly.
Which flavor of Lisp were you using there?
--
Marcus Breiing
···················@breiing.com (will expire)
Marcus Breiing <············@breiing.com> writes:
> OK, so you invented mutual recursion, which gets you "recursion
> without a function calling itself" after all, if only given suitable
> definitions of the various terms used. [...]
It is easy to check if any of these versions ends up calling "itself"
in any way, where itself is defined as the dynamic identity of the
generated run-time object (switching to Lisp due to NG):
CL-USER(1): (setq funcs '())
NIL
CL-USER(2): (funcall (lambda (g n) (funcall g g n))
(lambda (f n)
(push f funcs)
(if (= 0 n) 1 (* n (funcall f f (- n 1)))))
3)
6
CL-USER(3): funcs
(#1=#<Interpreted Function (unnamed) @ #x4451252a> #1# #1# #1#)
CL-USER(4): (setq funcs '())
NIL
CL-USER(5): (funcall (lambda (f g n) (funcall g (funcall f f g) n))
(lambda (f g)
(lambda (n) (funcall g (funcall f f g) n)))
(lambda (f n)
(push f funcs)
(if (< n 1) 1 (* n (funcall f (- n 1)))))
3)
6
CL-USER(6): funcs
(#<Interpreted Closure (unnamed) @ #x445175f2>
#<Interpreted Closure (unnamed) @ #x44516902>
#<Interpreted Closure (unnamed) @ #x44515c12>
#<Interpreted Closure (unnamed) @ #x44514f22>)
> > ((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)
>
> If only you had play-tested your ditty a bit longer before
> proceeding to Release 1.0... Hint: Backquote syntax doesn't do what
> you seem to think it does.
As a side note,
CL-USER(7): ((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)
120
(this is on Allegro CL 6).
--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://www.barzilay.org/ Maze is Life!
From: Vassil Nikolov
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <ufzvgdola.fsf@poboxes.com>
(Followups to comp.lang.lisp only.)
On 09 Oct 2002 03:01:12 -0400, Eli Barzilay <···@barzilay.org> said:
[...]
EB> CL-USER(7): ((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)
EB> 120
Funny: the value of `(LAMBDA (N) ...) is a list, so it should not
be suitable as an argument to FUNCALL.
---Vassil.
--
Garbage collection is charged at 0.19e-9 cents a cons. Bulk rates
are also available: please contact memory management for details.
Vassil Nikolov <········@poboxes.com> writes:
> (Followups to comp.lang.lisp only.)
>
> On 09 Oct 2002 03:01:12 -0400, Eli Barzilay <···@barzilay.org> said:
>
> [...]
> EB> CL-USER(7): ((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)
> EB> 120
>
> Funny: the value of `(LAMBDA (N) ...) is a list, so it should not
> be suitable as an argument to FUNCALL.
Probably depends on the Lisp dialect. Emacs has no problem with
that. How does one create ad-hoc function objects in more standard
variants of Lisp?
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
David Kastrup <·············@t-online.de> wrote:
> How does one create ad-hoc function objects in more standard
> variants of Lisp?
In ANSI Common Lisp, you just write (lambda ...) much as you would in
Scheme.
--
Marcus Breiing
···················@breiing.com (will expire)
From: Vassil Nikolov
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <usmzfoi07.fsf@poboxes.com>
On 09 Oct 2002 11:26:04 +0200, Marcus Breiing <············@breiing.com> said:
DK> How does one create ad-hoc function objects in more standard
DK> variants of Lisp?
MB> In ANSI Common Lisp, you just write (lambda ...) much as you would in
MB> Scheme.
This is only when the lambda form is a compile-time literal (note
that in a for-evaluation position, (LAMBDA ...) expands into
(FUNCTION (LAMBDA ...)), and FUNCTION is a special form which does
not evaluate its argument.
If you want to create function objects at run-time, you say (COERCE
expression 'FUNCTION) or (COMPILE NIL expression), where expression
is any expression that evaluates to a lambda expression. Note,
however, that all such functions will have a null lexical
environment.
---Vassil.
--
Garbage collection is charged at 0.19e-9 cents a cons. Bulk rates
are also available: please contact memory management for details.
Marcus Breiing <············@breiing.com> writes:
> David Kastrup <·············@t-online.de> wrote:
>
> > How does one create ad-hoc function objects in more standard
> > variants of Lisp?
>
> In ANSI Common Lisp, you just write (lambda ...) much as you would in
> Scheme.
Compiled GCL for trying this out. How does one call such stuff?
funcall is not too happy:
((lambda (f g n) (funcall (funcall f f g) n))
(lambda (f g) `(lambda (n) (funcall ,g (funcall ,f ,f ,g) n)))
(lambda (f n) (if (zerop n) 1 (* n (funcall f (1- n)))))
5)
Error: The function LAMBDA-CLOSURE is undefined.
Fast links are on: do (si::use-fast-links nil) for debugging
Error signalled by LAMBDA.
Backtrace: system:universal-error-handler > evalhook > lambda-closure > funcall > funcall > lambda > FUNCALL
Or perhaps the question is how to build a lambda expression from
variable components. The
`(lambda (n) (funcall ,g (funcall ,f ,f ,g) n)
does not seem to cut it.
Actually, I just tried leaving off the quoting folderol like in
Scheme, and
((lambda (f g n) (funcall (funcall f f g) n))
(lambda (f g) (lambda (n) (funcall g (funcall f f g) n)))
(lambda (f n) (if (zerop n) 1 (* n (funcall f (1- n)))))
5)
works just fine in GCL. It won't work in Emacs Lisp however, due to
Emacs' dynamic scoping that implies that the lambda object returned by
the second line contains references to the symbols f and g which at
the time of call of course are no longer bound to what the second line
was called with.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
From: Erik Naggum
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <3243164309543923@naggum.no>
* David Kastrup
| How does one create ad-hoc function objects in more standard variants of
| Lisp?
You got to be kidding. The only purpose of the horrid complexity of
(lambda (f g) `(lambda (n) (,g (funcall ,f ,f ,g) n)))
is to capture the values of the `f� and `g� bindings. In Common Lisp, we
have closures and write
(lambda (f g) (lambda (n) (g (funcall f f g) n)))
| Emacs has no problem with that.
Emacs Lisp has serious problems with closures. That is why you think you
need this nonsense to begin with.
One question remains: Why are you programming in Emacs Lisp while
claiming to be programming in Lisp without being aware of the serious
limitations of Emacs Lisp? I mean, you /got/ to be kidding when you
imply that you do not know that every other modern Lisp has closures.
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Erik Naggum <····@naggum.no> writes:
> * David Kastrup
> | How does one create ad-hoc function objects in more standard variants of
> | Lisp?
>
> You got to be kidding. The only purpose of the horrid complexity of
>
> (lambda (f g) `(lambda (n) (,g (funcall ,f ,f ,g) n)))
>
> is to capture the values of the `f� and `g� bindings. In Common Lisp, we
> have closures and write
>
> (lambda (f g) (lambda (n) (g (funcall f f g) n)))
>
> | Emacs has no problem with that.
>
> Emacs Lisp has serious problems with closures. That is why you
> think you need this nonsense to begin with.
Oh, I don't just think I need it. I actually do need it when working
in Emacs.
> One question remains: Why are you programming in Emacs Lisp while
> claiming to be programming in Lisp without being aware of the
> serious limitations of Emacs Lisp? I mean, you /got/ to be
> kidding when you imply that you do not know that every other
> modern Lisp has closures.
Not every other Lisp is modern (Allegro CL apparently did get the
meaning of what I wrote, BTW). But you are right in that I should
have mentioned the variant of Lisp I had tried this out with.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
Eli Barzilay <···@barzilay.org> wrote:
> CL-USER(7): ((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)
> 120
> (this is on Allegro CL 6).
I originally tried it on LispWorks. So Allegro seems to have eval
hidden within funcall. Do you know whether this is specific to
Allegro, or whether it is something that historically many Lisps did?
--
Marcus Breiing
···················@breiing.com (will expire)
From: Vassil Nikolov
Subject: Re: Lambda calculus and it relation to LISP
Date:
Message-ID: <un0pnohb9.fsf@poboxes.com>
On 09 Oct 2002 11:20:31 +0200, Marcus Breiing <············@breiing.com> said:
[...]
MB> So Allegro seems to have eval
MB> hidden within funcall. Do you know whether this is specific to
MB> Allegro, or whether it is something that historically many Lisps did?
Historically, all Lisps used to accept a lambda expression as a
datum of type function.
Even Common Lisp had it originally, i.e. you could say something
like (FUNCALL '(LAMBDA ...) ...) with CLtL. Then at one point (I
forget exactly when, but in the course of preparing the ANSI
standard), the definition of function became stricter, and lists
became invalid for those purposes, so you can only say something
like (FUNCALL #'(LAMBDA ...) ...) or, using the somewhat
controversial LAMBDA macro (a rather late addition), something like
(FUNCALL (LAMBDA ...) ...), both of which are read as/expanded into
(FUNCALL (FUNCTION (LAMBDA ...)) ...).
It is probably needless to note that in a lambda form,
i.e. something like ((LAMBDA ...) ...) which is to be evaluated,
the lambda expression which is the first element of that form is
not evaluated, so the LAMBDA macro has no relevance to lambda
forms (I said it was controversial).
---Vassil.
--
Garbage collection is charged at 0.19e-9 cents a cons. Bulk rates
are also available: please contact memory management for details.
Marcus Breiing <············@breiing.com> writes:
> Eli Barzilay <···@barzilay.org> wrote:
>
> > CL-USER(7): ((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)
> > 120
>
> > (this is on Allegro CL 6).
>
> I originally tried it on LispWorks. So Allegro seems to have eval
> hidden within funcall. Do you know whether this is specific to
> Allegro, or whether it is something that historically many Lisps did?
Probably historic. Historically, Lisp was interpreted lists, and
typically dynamically scoped. In the above, write funcall ,g instead
of just ,g. And then throw out all quoting folderol, and the thing
will run in "modern" Lisp but will fail in Emacs Lisp, for example.
Sorry for that.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Email: ·············@t-online.de
>
> 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.
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! =-----
> "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 ······@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
"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
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 ················@pobox.com
.sig under construc
················@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! =-----
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 ················@pobox.com
.sig under construc
················@pobox.com (Gareth McCaughan) wrote in message news:<·······························@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.
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! =-----
In article <····························@posting.google.com>,
·········@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 |
-----------------------------
···@sig.below (Barb Knox) writes:
> In article <····························@posting.google.com>,
> ·········@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: ·············@t-online.de
On 7 Oct 2002, David Kastrup wrote:
> ···@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! =-----
In article <····························@agora.rdrop.com>, William Elliot
<····@xx.com> wrote:
> On 7 Oct 2002, David Kastrup wrote:
> > ···@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 |
-----------------------------
···@sig.below
William Elliot <····@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! =-----
David Kastrup <·············@t-online.de> writes:
> ···@sig.below (Barb Knox) writes:
>
> > In article <····························@posting.google.com>,
> > ·········@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, <·······@aixonix.de>, http://www.clemburg.com/
Money is the root of all evil, and man needs roots
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
In article <··············@tupik.goethe.zz>, David Kastrup
<·············@t-online.de> wrote:
> ···@sig.below (Barb Knox) writes:
>
> > In article <····························@posting.google.com>,
> > ·········@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 |
-----------------------------
···@sig.below (Barb Knox) writes:
> In article <··············@tupik.goethe.zz>, David Kastrup
> <·············@t-online.de> wrote:
>
> > ···@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: ·············@t-online.de
"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 ················@pobox.com
.sig under construc
················@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! =-----
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 ················@pobox.com
.sig under construc
················@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! =-----
[removing g.e.help, as it's totally inappropriate ]
William Elliot <····@xx.com> writes:
> ················@pobox.com:
> > 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.
I don't see why you should be surprised. Go look at the work of
Leibniz, and now open a modern Calculus textbook.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
·········@hotmail.com (gnuist) wrote in message news:<····························@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.
On 4 Oct 2002 20:20:49 -0700, ·········@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.
Thaddeus L Olczyk <······@interaccess.com> scribbled the following
on sci.math:
> On 4 Oct 2002 20:20:49 -0700, ·········@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 (·······@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
·········@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).