At the beginning of my last Lisp course, I said to my students that typical lisp
programming involves recursion.
Later when they were able to handle lambda expressions,
I said to them that pure Lisp programming involves lambda expressions
(instead of named functions).
Then a student asked me : Is it possible to make typical pure programs,
i.e. recursive programming with lambda expressions ?
What is your feeling ?
For instance, try to compute factorial 5 in such a way.
Alain Grumbach
Alain Grumbach wrote:
>
> At the beginning of my last Lisp course, I said to my students that typical lisp
> programming involves recursion.
> Later when they were able to handle lambda expressions,
> I said to them that pure Lisp programming involves lambda expressions
> (instead of named functions).
> Then a student asked me : Is it possible to make typical pure programs,
> i.e. recursive programming with lambda expressions ?
>
> What is your feeling ?
This was answere around 4 weeks ago. Yes it works. I do not have the
thread subject on my mind, please check dejanews
Regards
Friedrich
In article <············@menuisier.enst.fr>, ········@golicha.enst.fr
(Alain Grumbach) wrote:
> Then a student asked me : Is it possible to make typical pure programs,
> i.e. recursive programming with lambda expressions ?
>
> What is your feeling ?
>
> For instance, try to compute factorial 5 in such a way.
You are looking for the Y-Combinator?
Rainer Joswig, ISION Internet AG, Harburger Schlossstra�e 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/
Rainer Joswig:
> In article <············@menuisier.enst.fr>, ········@golicha.enst.fr
> (Alain Grumbach) wrote:
>
> > Then a student asked me : Is it possible to make typical pure programs,
> > i.e. recursive programming with lambda expressions ?
[...]
> You are looking for the Y-Combinator?
A gentle step by step introduction of the (applicative order) Y
combinator:
http://www.cs.rice.edu/~matthias/TLS/tls-sample.ps
This is Matthias Felleisen's lecture on The_Why_of_Y turned into
a chapter of The_Little_Schemer, a new edition of The_Little_Lisper.
rthappe
Alain Grumbach <········@golicha.enst.fr> wrote in message
·················@menuisier.enst.fr...
> At the beginning of my last Lisp course, I said to my students that
typical lisp
> programming involves recursion.
> Later when they were able to handle lambda expressions,
> I said to them that pure Lisp programming involves lambda expressions
> (instead of named functions).
> Then a student asked me : Is it possible to make typical pure programs,
> i.e. recursive programming with lambda expressions ?
Y not?
> What is your feeling ?
Y do you ask?
* Alain Grumbach wrote:
> Then a student asked me : Is it possible to make typical pure programs,
> i.e. recursive programming with lambda expressions ?
> What is your feeling ?
yes it is. The Y combinator is the general way of doing this.
> For instance, try to compute factorial 5 in such a way.
(defun fact (n)
((lambda (f)
(funcall f f n 1))
(lambda (c i a)
(if (<= i 1)
a
(funcall c c (1- i) (* a i))))))
This is even tail recursive.
--tim
From: Christian Jullien
Subject: Re: typical pure programs
Date:
Message-ID: <8508ab$gb1$1@wanadoo.fr>
With my ISO/IEC 31816 ISLISP implementation called OpenLisp (see
www.eligis.com)
I use this code to stress my compiler.
;;; Fib using the lambda-calculus fixpoint Y-combinator.
(defconstant Y-combinator
(lambda (f)
(funcall (lambda (g) (funcall g g))
(lambda (x) (funcall f (lambda () (funcall x x)))))))
(defun yfib (n)
(let ((fib (funcall Y-combinator
(lambda (fg)
(lambda (n)
(cond
((= n 1) 1)
((= n 2) 1)
(t
(+ (funcall (funcall fg) (- n 1))
(funcall (funcall fg) (- n 2))))))))))
(funcall fib n)))
From: Christian Jullien
Subject: Re: typical pure programs
Date:
Message-ID: <8508ac$gb1$2@wanadoo.fr>
With my ISO/IEC 31816 ISLISP implementation called OpenLisp (see
www.eligis.com)
I use this code to stress my compiler.
;;; Fib using the lambda-calculus fixpoint Y-combinator.
(defconstant Y-combinator
(lambda (f)
(funcall (lambda (g) (funcall g g))
(lambda (x) (funcall f (lambda () (funcall x x)))))))
(defun yfib (n)
(let ((fib (funcall Y-combinator
(lambda (fg)
(lambda (n)
(cond
((= n 1) 1)
((= n 2) 1)
(t
(+ (funcall (funcall fg) (- n 1))
(funcall (funcall fg) (- n 2))))))))))
(funcall fib n)))
* I wrote:
> yes it is. The Y combinator is the general way of doing this.
> [...]
> (defun fact (n)
> ((lambda (f)
> (funcall f f n 1))
> (lambda (c i a)
> (if (<= i 1)
> a
> (funcall c c (1- i) (* a i))))))
I should perhaps have added that this is not Y (as far as I know).
In article <············@menuisier.enst.fr>, Alain Grumbach wrote:
>Then a student asked me : Is it possible to make typical pure programs,
>i.e. recursive programming with lambda expressions ?
You mean, is it possible to enter a recursive function directly using
lambda without giving it a name? Not directly with lambda; you can't
call the function recursively since there is no name to call it by! But
I defined this macro that I call rlambda (r for recursive):
(defmacro rlambda (lambda-list &rest body)
`(labels ((self ,lambda-list ,@body))
#'self))
When using rlambda, the function can be called recursively under the name
SELF.
>For instance, try to compute factorial 5 in such a way.
(funcall (rlambda (n)
(if (zerop n)
1
(* n (self (1- n)))))
5)
I don't know if this is particularly useful, but it is certainly possible,
and maybe a bit simpler than the solutions involving the Y combinator.
--
- Fredrik Sandstrom ·······@infa.abo.fi http://infa.abo.fi/~fredrik -
Computer Science at Abo Akademi University --
* Fredrik Sandstrom wrote:
> You mean, is it possible to enter a recursive function directly using
> lambda without giving it a name? Not directly with lambda; you can't
> call the function recursively since there is no name to call it by!
Yes you can!
((lambda (c)
(funcall c c))
(lambda (c)
(funcall c c)))
--tim