anonymous function recursion

[Alex Parshikov]

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?

[Peter Seibel]

"Alex Parshikov" <irrel...@nowhere.com> writes:

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 pe...@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

[Fred Gilham]

"Alex Parshikov" <irrel...@nowhere.com> writes:

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 gil...@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

[Lieven Marchand]

"Alex Parshikov" <irrel...@nowhere.com> writes:

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]

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.

[Wolfhard Buß]

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)

[Steven M. Haflich]

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.

[Pascal Bourguignon]

"Alex Parshikov" <irrel...@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.

[Marco Baringer]

"Alex Parshikov" <irrel...@nowhere.com> writes:

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

[Fred Gilham]

> 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 gil...@csl.sri.com
When trying to reach the lowest common denominator, you have to be
prepared for the occasional division by zero.

[Madhu]

Helu

* Lieven Marchand <87of2bb...@wyrd.be> :

| 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

Same thing, in a more atrocious (repl) form:

* ((lambda (x f) (if (zerop x) 1 (* x (funcall f (1- x) f))))
5 (coerce (car -) 'function))

120

Regards
Madhu <:

--