"Alex Parshikov" <··········@nowhere.com> writes:
> Given I have the following:
> (maplist #'(lambda(y)(print y)) '(1 2 3 4 5)),
>
> how would I go about making a recursive call to lambda(y) from inside it?
You can use the Y combinator.
Here's something that Christian Jullien posted here back in 2000:
;;; 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)))
Here's a couple of simpler examples that Tim Bradshaw posted:
(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))))))
Tim pointed out that the above is "tail recursive".
Here's the second example Tim gave, probably more directly applicable
to your question:
((lambda (c)
(funcall c c))
(lambda (c)
(funcall c c)))
This one is just an infinite loop. You can put stuff in the lambda
bodies if you want to actually do something.
"You are in a maze of twisty little passages, all the same."
--
Fred Gilham ······@csl.sri.com
America does not know the difference between sex and money. It treats
sex like money because it treats sex as a medium of exchange, and it
treats money like sex because it expects its money to get pregnant and
reproduce. --- Peter Kreeft
Could you elaborate on this one ( I am new to LISP and didn't find any
pertinent material in "Common Lisp the Language", which I heard was one of
the best books on LISP):
((lambda (c)
(funcall c c))
(lambda (c)
(funcall c c)))
in order to use funcall c, your initial call to this lambda should already
contain function as a parameter, right? and it calls that function passing
its body to it. Is it therefore okay to say:
(setq funct '(lambda(c)(funcall c c 0)))
(funcall 'funct (lambda(self counter)(cond((not(= counter 100))(print
c)(funcall self self (+ counter 1)))(t nil))))
in order to print numbers from 0 to 100 ? Of course, practicality is not the
question here.
> Could you elaborate on this one ( I am new to LISP and didn't find
> any pertinent material in "Common Lisp the Language", which I heard
> was one of the best books on LISP):
Here's the way I would do your example (of counting up to 100) using
the
((lambda (c)
(funcall c c))
(lambda (c)
(funcall c c)))
example:
((lambda (func)
(funcall func func 0))
(lambda (continuation count)
(cond ((= count 100)
count)
(t
(print count)
(funcall continuation continuation (1+ count))))))
To break it down a little, you can see that the first lambda
expression takes a function as its argument. All it does is call that
function, passing it two arguments. The first argument is the
function itself, and the second is 0.
The second lambda expression is actually a function that gets created
"dynamically". So it becomes the functional argument to the first
lambda expression. It doesn't get executed until the first lambda
executes the (funcall func func 0) statement.
The second lambda does the work. It expects two arguments, a function
and a count.
This function argument is actually a "continuation". It says "what to
do next", or "how to continue". I think that's why in Tim Bradshaw's
original example it was named "c".
The second lambda has a cond. The first clause of the cond is the
base case of the recursion. The second is the recursive case. The
recursion is accomplished by calling the continuation. The trick is
that the continuation itself is passed as one of the arguments to the
continuation, so that the continuation becomes its own continuation.
This allows the recursion.
OK, now looking at your version, you have
(setq funct
'(lambda (c)
(funcall c c 0)))
(funcall funct
(lambda (self counter)
(cond ((not (= counter 100))
(print c)
(funcall self self (+ counter 1)))
(t nil))))
(Proper indentation really helps me see what's going on.)
Now you can see that something's fishy. There's a (print c) in there
that looks wrong, because there's no c anywhere except in the setq
expression where it's lexical, and its scope is the lambda expression
so it's invisible everywhere else.
You probably meant
(funcall funct
(lambda (self counter)
(cond ((not (= counter 100))
(print counter)
(funcall self self (+ counter 1)))
(t nil))))
Next, if you run the above, you'll probably get an error. That's
because you set funct to a list, not a function. So we make this
change:
(setq funct
(lambda (c) ; No quote.
(funcall c c 0)))
This seems to work.
--
Fred Gilham ······@csl.sri.com
When trying to reach the lowest common denominator, you have to be
prepared for the occasional division by zero.
"Alex Parshikov" <··········@nowhere.com> writes:
> Could you elaborate on this one ( I am new to LISP and didn't find any
> pertinent material in "Common Lisp the Language", which I heard was one of
> the best books on LISP):
>
> ((lambda (c)
> (funcall c c))
> (lambda (c)
> (funcall c c)))
( (lambda (c) (funcall c c)) (lambda (c) (funcall c c)) )
-------------------------- --------------------------
^ ^
| |
| +---- argument
+---- function
substitute the argument into the body of the function:
(funcall (lambda (c) (funcall c c)) (lambda (c) (funcall c c))))
-------------------------- --------------------------
^ ^
| |
| +---- argument
+---- function
repeat.
> in order to use funcall c, your initial call to this lambda should already
> contain function as a parameter, right? and it calls that function passing
> its body to it. Is it therefore okay to say:
>
> (setq funct '(lambda(c)(funcall c c 0)))
> (funcall 'funct (lambda(self counter)(cond((not(= counter 100))(print
> c)(funcall self self (+ counter 1)))(t nil))))
>
> in order to print numbers from 0 to 100 ? Of course, practicality is not the
> question here.
Make it:
(setq funct '(lambda(c)(funcall c c 0)))
(funcall (coerce funct 'function)
(lambda (self counter)
(cond ((not(= counter 100))
(print counter)
(funcall self self (+ counter 1)))
(t nil))))
Or:
(setq funct (lambda(c)(funcall c c 0)))
(funcall funct
(lambda (self counter)
(cond ((not(= counter 100))
(print counter)
(funcall self self (+ counter 1)))
(t nil))))
With:
(funcall 'funct
(lambda (self counter)
(cond ((not(= counter 100))
(print counter)
(funcall self self (+ counter 1)))
(t nil))))
funcall will try to call (symbol-function 'funct), but with the (setq
funct ...) you set (symbol-value 'funct), not (symbol-function
'funct).
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
"Alex Parshikov" <··········@nowhere.com> writes:
> Given I have the following:
> (maplist #'(lambda(y)(print y)) '(1 2 3 4 5)),
>
> how would I go about making a recursive call to lambda(y) from
> inside it?
You can't. But you can create a local non-anonymous function with
LABELS:
(labels ((fn (x)
(unless (null x)
(cons (car x)
(cons (car x) (fn (cdr x)))))))
(maplist #'fn '(1 2 3 4)))
Evaluates to:
((1 1 2 2 3 3 4 4) (2 2 3 3 4 4) (3 3 4 4) (4 4))
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
Peter Seibel wrote:
> You can't. But you can create a local non-anonymous function with
> LABELS:
You can. For those who prefer a lower-wattage solution than the Y
combinator, a simple closure will do:
(let (f)
(setf f
(lambda (x) (if (zerop x) :yes (funcall f (print (1- x))))))
(funcall f 3))
2
1
0
:yes
This isn't so different in semantics from the Y combinator, of course,
given the transformability between let and lambda.
"Alex Parshikov" <··········@nowhere.com> writes:
> Given I have the following:
> (maplist #'(lambda(y)(print y)) '(1 2 3 4 5)),
>
> how would I go about making a recursive call to lambda(y) from inside it?
This is probably cheating.
CL-USER 7 > (funcall #1=#'(lambda (n f) (if (zerop n) 1 (* n (funcall f (1- n) f)))) 5 #1#)
120
--
Jane - Daria? Come on, the neighbors are starting to talk.
Daria - Um... good. Soon they'll progress to cave drawings and civilization
will be on its way.
Alex Parshikov writes:
>
> Given I have the following:
> (maplist #'(lambda(y)(print y)) '(1 2 3 4 5)),
>
> how would I go about making a recursive call to lambda(y) from inside it?
Label it!
Example:
(funcall (labels ((foo (list)
(unless (endp list)
(cons (print list)
(foo (rest list))))))
#'foo)
'(1 2 3 4 5))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
From: Marco Baringer
Subject: Re: anonymous function recursion
Date:
Message-ID: <m2llxepzs1.fsf@bese.it>
"Alex Parshikov" <··········@nowhere.com> writes:
> Given I have the following:
> (maplist #'(lambda(y)(print y)) '(1 2 3 4 5)),
>
> how would I go about making a recursive call to lambda(y) from inside it?
fake it :)
(defmacro rec-lambda (name args &body body)
'(labels ((,name ,args ,@body))
#',name))
(mapcar (rec-lambda fact (y)
(if (zerop y)
1
(* y (fact (1- y)))))
'(1 2 3 4 5))
=>
(1 2 6 24 120)
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen