From: Andy Reiter
Subject: Newbie: How does a lambda recurse?
Date: 
Message-ID: <d4b78695.0205162021.25844217@posting.google.com>
Say I have a little lambda function

(lambda ()
  (do-something))

If I want an infinite loop of do-somethings, and I decided to do it via recursion,
how would I go about it?
is there some sort of "this" pointer, like in C++ classes. How does an unnamed
function realize itself?

From: Gabe Garza
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <wuu3qshw.fsf@anubis.kynopolis.org>
·······@flop.co.uk (Andy Reiter) writes:

> Say I have a little lambda function
> 
> (lambda ()
>   (do-something))
> 
> If I want an infinite loop of do-somethings, and I decided to do it
> via recursion, how would I go about it?  is there some sort of
> "this" pointer, like in C++ classes. How does an unnamed function
> realize itself?

How does something with no name refer to itself?  That's rather
philosophical 8).  You can always cheat and give it a name:

(lambda ()
  ((lambda (this)
     (funcall this this))
   (lambda (this)
    (sleep 1)
    (write-line "I'm doing something!")
    (funcall this this))))

Of course, using recursion to implement an infinite loop is a pretty
bad idea in Common Lisp: you're likely to overflow the stack!  A
more preferable way to do something foerver in an anonmyous function
would be to use LOOP, like so:

(lambda ()
  (loop 
    (do-something)))

It's even easier to read!

Gabe Garza

 
From: Paul F. Dietz
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <3CE4F29D.128C4B77@interaccess.com>
Andy Reiter wrote:
> 
> Say I have a little lambda function
> 
> (lambda ()
>   (do-something))
> 
> If I want an infinite loop of do-somethings, and I decided to do it via recursion,
> how would I go about it?

This isn't Scheme; don't use recursion when iteration will do.

If you really need recursion in a lambda, use a LABELS form
instead and return #'<function name>, or include an anaphoric
lambda package (Graham?) and use the alambda macro, which
would look something like this:

   (alambda (...)
	... (%self ...) ...)

	Paul
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <tu9F8.6495$Bn5.2895393@typhoon.ne.ipsvc.net>
"Paul F. Dietz" <·····@interaccess.com> wrote in message ······················@interaccess.com...
>
> This isn't Scheme; don't use recursion when iteration will do.
>

I wouldn't go *that* far.  One should use the right tool for the
job, be it recursion or iteration.  One should first write the
code in the most perspicuous manner possible (keeping in mind
that Lisp has a far richer set of `iteration' constructs than
Scheme) and *then* if a recursive construct is causing problems,
change it to an iterative construct (keeping in mind that Lisp
does not require tail-recursive calls to use constant space).

That being said, Paul's solution of wrapping your call to
(do-something) in a LOOP is the clearest way to go about it.
From: P.C.
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <3ce7da9c$0$97282$edfadb0f@dspool01.news.tele.dk>
Hi.

"Paul F. Dietz" <·····@interaccess.com> skrev i en meddelelse
······················@interaccess.com...

> This isn't Scheme; don't use recursion when iteration will do.

Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack
overflow can ocour, within a well known number of data.
Please understand me right, but as everyone know, there are some old rules we
just agrea, without even asking if the caurse we say so, is a tiny chance, that
occoured in compleatly different situasions than the one in count.  Reson I say
so, is that this "rule" have been there since we all had 8k mem to work with,
but today, ---- Eh , don't computers carry a bit more mem, than when this rule
was documentet with Pi making stack overflow.
_When_ do a recursive function cause this problem, --- and do this still justify
that saying recursion, we emidiatly say "no-no, you just overflow the stack " ;
I don't need to overflow any stack, if I know what I do, and if I know that this
function working on this known set of data ,will _never_ overflow any
stack. ------ or are we just stubbern old fanatics ,that just react from the
rules, settled under compleatly different circumstances ,back then in the
stoneage ?
Do these old rules still rule, or is this also a matter about ideology ,that if
anyone accept that you _can_ use recurtion, everyone have to give up their pony,
and start riding another one.
P.C.
http://groups.yahoo.com/group/skuespilhus/
From: Coby Beck
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <LZUF8.13832$Ka.860308@news2.calgary.shaw.ca>
P.C. <··········@privat.dk> wrote in message
······························@dspool01.news.tele.dk...
> "Paul F. Dietz" <·····@interaccess.com> skrev i en meddelelse
> ······················@interaccess.com...
>
> > don't use recursion when iteration will do.
>
[SNIP]
> " if I know what I do, and if I know that this
> function working on this known set of data ,will _never_" <insert
anything>

Every time a programmer in the dungeons of M$ says these words to himself,
yet another blue screen appears on my monitor...

> ------ or are we just stubbern old fanatics ,that just react from the
> rules, settled under compleatly different circumstances ,back then in the
> stoneage ?

I never programmed in the stone ages, but I still think it is a good rule
though even more for readability and intuitiveness than safety.


--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <kD_F8.8026$Bn5.3943865@typhoon.ne.ipsvc.net>
"P.C." <··········@privat.dk> wrote in message ······························@dspool01.news.tele.dk...

 [A little editing for readability applied]

> *When* does a recursive function cause this [stack overflow] problem?

The `problem' is that Common Lisp allows *any* recursive form to use as
much stack as the implementors choose.  So conforming code cannot make
any assumptions about whether it will cause stack overflow.

However, all `industrial strength' implementations of Common Lisp can do
tail-recursion under certain circumstances.  These vary from vendor to vendor,
but there are generally declarations and implementation switches that can
be set to cause the compiler to recognize and optimize tail-recursive calls.

> Are we just stubbern old fanatics, just reacting from the
> rules settled under completely different circumstances back in the
> stone age?

Back in the 80's when Common Lisp was developed (wait a second.  Is he implying
that I am a fossil?!) there were several important Lisp implementations that
did *not* support tail recursion at all.  If you were attempting to write
portable Lisp code, you simply could not rely on the compiler optimizing stack
usage.

These days, I think you are justified in rejecting a Lisp implementation if
there isn't some way to persuade it to optimize stack usage.

In general, I ignore the issue of tail recursion during development.  If the
obvious way to code is using tail recursion, then I use it.  If it is with a DO
or LOOP, I use them.  Once it is written, if it is trivial to replace a
tail-recursive call with a iteration, I'll do it, otherwise I'll just ensure
that the compiler takes care of it.

> Do these old rules still apply, or is this a matter of ideology?

I'd say that the old rules are considerably relaxed, but not completely
irrelevant.  There are pragmatic reasons to distinguish between recursion
and iteration; it isn't just ideology.  For instance, it is often very
hard to debug tail-recursive code because the path of execution immediately
prior to the bug may have been discarded.

In a language that *requires* a tail recursive implementation, the onus is
upon the implementor of the language to ensure that the compiler correctly
optimizes stack usage in all cases.  If you write code in Common Lisp that
depends upon tail recursion, then the onus is upon *you* to make sure it works
properly for the intended use.  (I.e., you ought to know what options and
settings are necessary for the implementions you intend to support.)
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-3938AA.16203120052002@copper.ipg.tsnz.net>
In article <······················@typhoon.ne.ipsvc.net>,
 "Joe Marshall" <·············@attbi.com> wrote:

> I'd say that the old rules are considerably relaxed, but not completely
> irrelevant.  There are pragmatic reasons to distinguish between recursion
> and iteration; it isn't just ideology.  For instance, it is often very
> hard to debug tail-recursive code because the path of execution immediately
> prior to the bug may have been discarded.

That's *exactly* the same as iteration.

With a recursive formulation, if you turn off the tail call elimination 
then the whole history of the computation is right there, sitting on the 
stack for you to examine.  There's no easy way to do the same for 
iteration.

-- Bruce
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <nG0G8.8328$Bn5.3981700@typhoon.ne.ipsvc.net>
"Bruce Hoult" <·····@hoult.org> wrote in message ································@copper.ipg.tsnz.net...
> In article <······················@typhoon.ne.ipsvc.net>,
>  "Joe Marshall" <·············@attbi.com> wrote:
>
> > I'd say that the old rules are considerably relaxed, but not completely
> > irrelevant.  There are pragmatic reasons to distinguish between recursion
> > and iteration; it isn't just ideology.  For instance, it is often very
> > hard to debug tail-recursive code because the path of execution immediately
> > prior to the bug may have been discarded.
>
> That's *exactly* the same as iteration.

Yes, but for one subtle difference:
Forms specifically designed for iteration do not span function call boundaries.

(And languages that enforce tail-recursion optimization can keep a record
of some fixed amount of stack frame info to aid debugging, too.)
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-5BE0FC.18560220052002@copper.ipg.tsnz.net>
In article <······················@typhoon.ne.ipsvc.net>,
 "Joe Marshall" <·············@attbi.com> wrote:

> "Bruce Hoult" <·····@hoult.org> wrote in message 
> ································@copper.ipg.tsnz.net...
> > In article <······················@typhoon.ne.ipsvc.net>,
> >  "Joe Marshall" <·············@attbi.com> wrote:
> >
> > > I'd say that the old rules are considerably relaxed, but not 
> > > completely irrelevant.  There are pragmatic reasons to 
> > > distinguish between recursion and iteration; it isn't just 
> > > ideology.  For instance, it is often very hard to debug 
> > > tail-recursive code because the path of execution immediately 
> > > prior to the bug may have been discarded.
> >
> > That's *exactly* the same as iteration.
> 
> Yes, but for one subtle difference:
> Forms specifically designed for iteration do not span function call 
> boundaries.

Why would that make any difference?

In tail-recursion, each time you enter the function again you get new 
bindings to the formal arguments and lexical variables of the function 
disappear.  You can still access and modify the previous values of 
variables in an enclosing lexical scope.

In iteration, each time you enter the loop you get new bindings of the 
loop control variable(s) and lexical variables within the body of the 
loop disappear.  You can still access and modify the previous values of 
variables in an enclosing lexical scope.

The situations are totally identical with respect to maintaining state 
and debugging.

-- Bruce
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <vf8G8.9014$Bn5.4113095@typhoon.ne.ipsvc.net>
"Bruce Hoult" <·····@hoult.org> wrote in message ································@copper.ipg.tsnz.net...
> In article <······················@typhoon.ne.ipsvc.net>,
>  "Joe Marshall" <·············@attbi.com> wrote:
>
> > "Bruce Hoult" <·····@hoult.org> wrote in message
> > ································@copper.ipg.tsnz.net...
> > > In article <······················@typhoon.ne.ipsvc.net>,
> > >  "Joe Marshall" <·············@attbi.com> wrote:
> > >
> > > > I'd say that the old rules are considerably relaxed, but not
> > > > completely irrelevant.  There are pragmatic reasons to
> > > > distinguish between recursion and iteration; it isn't just
> > > > ideology.  For instance, it is often very hard to debug
> > > > tail-recursive code because the path of execution immediately
> > > > prior to the bug may have been discarded.
> > >
> > > That's *exactly* the same as iteration.
> >
> > Yes, but for one subtle difference:
> > Forms specifically designed for iteration do not span function call
> > boundaries.
>
> Why would that make any difference?

Iteration forms are more restrictive than general tail recursion.  There
is usually a single entry point.  A set of tail recursive functions, however,
have many entry points.  It can be difficult to find out which one was
the one actually used.

>
> The situations are totally identical with respect to maintaining state
> and debugging.

I agree that they are totally identical with respect to maintaining state,
but I think debugging a program where the entire function call history
is available is easier than debugging one where only some are available.
From: Erik Naggum
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <3230861121663553@naggum.net>
* "P.C." <··········@privat.dk>
| Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack
| overflow can ocour, within a well known number of data.
| Please understand me right, but as everyone know, there are some old rules we
| just agrea, without even asking if the caurse we say so, is a tiny chance, that
| occoured in compleatly different situasions than the one in count.  Reson I say
| so, is that this "rule" have been there since we all had 8k mem to work with,
| but today, ---- Eh , don't computers carry a bit more mem, than when this rule
| was documentet with Pi making stack overflow.
| _When_ do a recursive function cause this problem, --- and do this still justify
| that saying recursion, we emidiatly say "no-no, you just overflow the stack " ;
| I don't need to overflow any stack, if I know what I do, and if I know that this
| function working on this known set of data ,will _never_ overflow any
| stack. ------ or are we just stubbern old fanatics ,that just react from the
| rules, settled under compleatly different circumstances ,back then in the
| stoneage ?
| Do these old rules still rule, or is this also a matter about ideology ,that if
| anyone accept that you _can_ use recurtion, everyone have to give up their pony,
| and start riding another one.

  Per, please take an English course.  This stuff is just too hard to read.

  After considerable study of your garbled language and thinking, I believe
  you may be satisfied with replies to different questions than you appear
  to ask:

  Is recursion always bad?  No, it is not.

  When is recursion bad and iteration good?  When iteration requires no new
  storage per iteration, or less storage per iteration than recursion.

  When is recursion good and iteration bad?  When (1) you traverse the list
  forwards and backwards and maintain some state for each iteration that
  you unwind or something in the backward pass, and (2) your algorithm
  requires that you be able to backtrack if you make a mistake.

  There is never enough memory for all tasks.  You do in fact run out of
  memory every once in a while even without recursion.  However, most
  systems are set up allow for a bigger heap than stack, and you can run
  out of stack faster than you run out of heap.  Stack is not garbage-
  collected until you return from the allocating frame.  However, there is
  no _fundamental_ difference between using heap or stack space, so what
  you think is a rule against recursion is a rule against recursion where
  iteration is clearly more efficient.

  Since Scheme has a chosen a syntax and a culture using it that reinforce
  recursion at the cost of understanding iteration, many Scheme freaks fail
  to grasp that the iteration that results from their tail recursion has a
  number of internal language requirements.  E.g., the named let, however,
  can easily be implemented in Common Lisp, since it is a local phenonmenon
  and a simple rewriting of the apparently recursive form to iteration is
  fairly trivial.  However, mutually recursive functions are harder to
  rewrite, and that is where the Scheme solution requires language support.
  Failure to understand that this requires language support for making a
  tail call into a tail jump and reusing the caller's call frame causes
  massively wasteful programming styles.

  So, over time, Scheme has come stand for the community of people who do
  not care about memory consumption and think it is somebody else's fault
  when they run out of memory, because they are religious about their
  recursion and are probably not sufficientl skilled to rewrite them to
  iterative form, to boot.

  Ignorance of the real machine is never a good thing for a programmer.
  For that matter, ignorance of the real world is never a good thing.
-- 
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.

  70 percent of American adults do not understand the scientific process.
From: William D Clinger
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <b84e9a9f.0205201517.5a03ec9@posting.google.com>
Concerning Scheme and tail recursion, Erik Naggum wrote:
>   Failure to understand that this requires language support for making a
>   tail call into a tail jump and reusing the caller's call frame causes
>   massively wasteful programming styles.

I am not aware of anything in the Scheme language that would require
reuse of the caller's call frame.  It seems to me that a Scheme compiler
is more likely to reuse frames for non-tail calls than for tail calls.

I have no idea what Erik might mean by "massively wasteful programming
styles".

>   Ignorance of the real machine is never a good thing for a programmer.

It's better to be ignorant than misinformed.

Will
From: Erik Naggum
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <3230927243550741@naggum.net>
* William D Clinger
| I have no idea what Erik might mean by "massively wasteful programming
| styles".

  Really?  I thought you had hung around here for a while...

  E.g., the classic Scheme mistake: Using recursion where absolutely no
  state information is retained between iterations, such as traversing down
  a list with recursive calls.
-- 
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.

  70 percent of American adults do not understand the scientific process.
From: Kaz Kylheku
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <slrnael1b1.sbg.kaz@localhost.localdomain>
On Sun, 19 May 2002 19:02:02 +0200, P.C. <··········@privat.dk> wrote:
>Hi.
>
>"Paul F. Dietz" <·····@interaccess.com> skrev i en meddelelse
>······················@interaccess.com...
>
>> This isn't Scheme; don't use recursion when iteration will do.
>
>Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack
>overflow can ocour, within a well known number of data.

A stack overflow can easily occur if your recursion has a requirement
for space that is linear, O(N), in the input size. Recursion can be used
if you know N to be small, or if the consumption is better than linear,
say O(log N). Many divide-and-conquer algorithms fall into this category.

If you *indiscriminately* use recursion as a substitute for iteration,
as students of the language Scheme are taught to do, chances are that
you will eventually write something which doesn't satisfy the rational
conditions for the use of recursion.
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-7D4395.16473617052002@copper.ipg.tsnz.net>
In article <····························@posting.google.com>,
 ·······@flop.co.uk (Andy Reiter) wrote:

> Say I have a little lambda function
> 
> (lambda ()
>   (do-something))
> 
> If I want an infinite loop of do-somethings, and I decided to do it 
> via recursion, how would I go about it? is there some sort of "this" 
> pointer, like in C++ classes.

No.

> How does an unnamed function realize itself?

Read this page:

  http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

-- Bruce
From: Paul Foley
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <m2it5nnte4.fsf@mycroft.actrix.gen.nz>
On Fri, 17 May 2002 16:47:36 +1200, Bruce Hoult wrote:

>> How does an unnamed function realize itself?

> Read this page:

>   http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

Spelled "labels" in CL.

-- 
If that makes any sense to you, you have a big problem.
                                      -- C. Durance, Computer Science 234
(setq reply-to
  (concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-FA8936.19343717052002@copper.ipg.tsnz.net>
In article <··············@mycroft.actrix.gen.nz>,
 Paul Foley <···········@actrix.gen.nz> wrote:

> On Fri, 17 May 2002 16:47:36 +1200, Bruce Hoult wrote:
> 
> >> How does an unnamed function realize itself?
> 
> > Read this page:
> 
> >   http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
> 
> Spelled "labels" in CL.

Why doesn't that count as a name?

-- Bruce
From: Robert Maas
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <ef5aa6c5.0205221231.5b7fa8f1@posting.google.com>
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@copper.ipg.tsnz.net>...
> In article <··············@mycroft.actrix.gen.nz>,
>  Paul Foley <···········@actrix.gen.nz> wrote:
> > Spelled "labels" in CL.
> Why doesn't that count as a name?

Because it's one of the tools provided by CL, used by you to build
expressions, just like CDR and PROGN and LET, rather than some name you
have to make up when you define a function. It's in the LISP package
rather than in your own package, and implementors have already made sure
it doesn't have the same name as any other tool in that package.
The main problem with names is you run out of them or accidently step
on something else by the same name that did something different or you
have to use really long names to avoid those two problems.
Consider this example: You need to make ten thousand different functions,
each of which does something slightly different. With named functions,
you have to make up ten thousand different names, and then try to remember
which name did which task as you tried to call them by name as appropriate.
But with unnamed functions you just make up ten thousand different
task-expressions, each of which includes a LAMBDA at the top and LABELS
somewhere inside. LAMBDA and LABELS are already defined in CL and are just
two names instead of ten thousand names so they aren't a problem.
The difference is especially important, and I assume here, when these
ten thousand functions are designed by a program, i.e. you don't even
know ahead of time how many of them there will be and what they will do
so it's a pain to try to design a general purpose way to name them all
before you even start running the program that makes them all. Think of a
"smart system" or "neural net" implemented as a large number of cooperating
functions, each of which is automatically adapted to the test data or
real-life environmental data, and new functions (neurons) are created
as needed, perhaps by some kind of replication and natural selection.
Sure, you can GENSYM a new name as needed, but on a distributed system how
can you synchronize GENSYM?? Imagine a gigantic array of computers linked
across the InterNet, each containing enough space to store a hundred
thousand of these evolving and competing functions, and you need to
constantly move functions from one machine to another so that they can
"breed" with non-siblings for better genetic diversity.

By comparison, if you're defining just a few functions, or you have
careful control over the namespace in which you're developing one
function at a time, named functions are just fine, and unnamed functions
are mostly a fun class exercise. But actually a very common practical
use of an unnamed function is to have a parameterized function used
in a mapping function. For example, to add a given (not constant)
number to each element of a list, do this:

(defun add-a-to-each-b (a blist)
  (mapcar
    (function (lambda (b) (+ a b))) ;lexical reference to local variable a
    blist))

In principle, each time that add-a-... function is called, it builds
a brand-new unnamed function containing the current value of a frozen
into it, calls that function a whole bunch of times, then discards it
before returning the list of return values from that function. Of course an
optimizing compiler might replace the unnamed function with some inline
code, but at least in principle that's what we're doing.
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-568D07.14015023052002@copper.ipg.tsnz.net>
In article <····························@posting.google.com>,
 ···@netmagic.net (Robert Maas) wrote:

> Bruce Hoult <·····@hoult.org> wrote in message 
> news:<···························@copper.ipg.tsnz.net>...
> > In article <··············@mycroft.actrix.gen.nz>,
> >  Paul Foley <···········@actrix.gen.nz> wrote:
> > > Spelled "labels" in CL.
> > Why doesn't that count as a name?
> 
> Because it's one of the tools provided by CL, used by you to build
> expressions, just like CDR and PROGN and LET, rather than some name you
> have to make up when you define a function. It's in the LISP package
> rather than in your own package, and implementors have already made sure
> it doesn't have the same name as any other tool in that package.

You have mistaken my meaning.  It is not that "labels" itself is a name, 
but that the recursive function(s) defined in it is given a name so it 
can call itself.

For the previous poster ... I'd thought that "labels" wasn't an 
equivilent to the Y combinator because it couldn't be used to create a 
first-class function.  But it seems that it can:

  (mapcar
   (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
           #'fact)
   '(1 2 3 4 5))

=> (1 2 6 24 120)

Would this be considered to be good style in CL?

-- Bruce
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <GsYG8.494$d51.527153@typhoon.ne.ipsvc.net>
"Bruce Hoult" <·····@hoult.org> wrote in message ································@copper.ipg.tsnz.net...
>>
> For the previous poster ... I'd thought that "labels" wasn't an
> equivilent to the Y combinator because it couldn't be used to create a
> first-class function.  But it seems that it can:
>
>   (mapcar
>    (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
>            #'fact)
>    '(1 2 3 4 5))
>
> => (1 2 6 24 120)
>
> Would this be considered to be good style in CL?

I'd certainly consider it odd and wonder why you didn't write
this:

(labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
  (mapcar #'fact '(1 2 3 4 5)))
From: Bruce Hoult
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <bruce-921A0C.15423123052002@copper.ipg.tsnz.net>
In article <····················@typhoon.ne.ipsvc.net>,
 "Joe Marshall" <·············@attbi.com> wrote:

> "Bruce Hoult" <·····@hoult.org> wrote in message 
> ································@copper.ipg.tsnz.net...
> >>
> > For the previous poster ... I'd thought that "labels" wasn't an
> > equivilent to the Y combinator because it couldn't be used to create a
> > first-class function.  But it seems that it can:
> >
> >   (mapcar
> >    (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
> >            #'fact)
> >    '(1 2 3 4 5))
> >
> > => (1 2 6 24 120)
> >
> > Would this be considered to be good style in CL?
> 
> I'd certainly consider it odd and wonder why you didn't write
> this:
> 
> (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
>   (mapcar #'fact '(1 2 3 4 5)))

Because that's not the same thing.  The mapcar is just an example of one 
reason that you might want a first class anonymous recursive function.  
You might be returning it, or storing it in a data structure or doing 
any number of other things with it that might not be convenient to 
entirely contain within the body of the (labels ...).

It's a question of which thing is structurally nested within the other 
-- the same reason, for example, that it's useful to have available both 
a "collect" clause within the loop macro, and standalone collect macros.

-- Bruce
From: Joe Marshall
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <ZZZG8.517$d51.566237@typhoon.ne.ipsvc.net>
"Bruce Hoult" <·····@hoult.org> wrote in message ································@copper.ipg.tsnz.net...
> In article <····················@typhoon.ne.ipsvc.net>,
>  "Joe Marshall" <·············@attbi.com> wrote:
>
> > "Bruce Hoult" <·····@hoult.org> wrote in message
> > ································@copper.ipg.tsnz.net...
> > >>
> > > For the previous poster ... I'd thought that "labels" wasn't an
> > > equivilent to the Y combinator because it couldn't be used to create a
> > > first-class function.  But it seems that it can:
> > >
> > >   (mapcar
> > >    (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
> > >            #'fact)
> > >    '(1 2 3 4 5))
> > >
> > > => (1 2 6 24 120)
> > >
> > > Would this be considered to be good style in CL?
> >
> > I'd certainly consider it odd and wonder why you didn't write
> > this:
> >
> > (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1))))))
> >   (mapcar #'fact '(1 2 3 4 5)))
>
> Because that's not the same thing.  The mapcar is just an example of one
> reason that you might want a first class anonymous recursive function.
> You might be returning it, or storing it in a data structure or doing
> any number of other things with it that might not be convenient to
> entirely contain within the body of the (labels ...).

Right.  But when you *can* conveniently put it in the body of the labels,
it seems less odd looking (and you did ask a style question).
From: Robert Maas
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <ef5aa6c5.0205271850.6efa7b92@posting.google.com>
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@copper.ipg.tsnz.net>...
> It's a question of which thing is structurally nested within the other
> -- the same reason, for example, that it's useful to have available both
> a "collect" clause within the loop macro, and standalone collect macros.

Indeed, you're thinking outside the box, seeing how you really do
want to organize the same functionality (*) different ways at different
times.

* (meaning ability to do tasks, not having anything to do with a "function"
in the computer or mathematics sense)

One generally useful way to think of software pieces is in terms of
transactions performed on data, either to modify that data in place
or to create new data "dependent" (**) on the old data.

** (meaning that for different input data you might get different
output data, so the output function is not constant i.e. independent
of the input; Not meaning that there's some dynamic linkage from input
to output such that if *later* the input is changed then the output
will magically change accordingly)

If a programming task is broken down into small "transactions", and the
code for each different kind of transaction encapsulated into a function
or macro definition (***), then it becomes straightforward to combine
these single-transaction functions in several ways, as a state machine
to handle interrupts, or as co-routines on a multi-processing machine,
or as a mainline calling a function, or as what was the function there
sitting on top calling what was the mainline, without having to re-write
any of the single-transaction functions to fit into these very
different overall-program models. The key term is "data processing",
and if you realize your software is just processing data, you can more
easily think of breaking that processing up into very small pieces.

*** (Not necessarily a *named* function or macro!!i By 'definition' I mean
the body of the lambda form, not the assignment of a name to the resultant
function or macro.)

For example, if you want to map down a list, you have these primitives:
- Establish position at start of list;
- Step to next of list;
- Check if at end of list yet;
- Perform an action at the current location.
Those same primitives apply to any kind of sequence.
For some kinds of sequences, it's possible/reasonable/efficient
to define additional primitives:
- Search forward/backward from some point to satisfy some test.
- Insert/delete elements in the sequence.
- Establish position at end of sequence;
- Step backward to previous of sequence;
The built-in mapping functions in LISP presume that the mapping down
the list is the main program and the thing you do there is some subroutine
you call from there. But what if you want it inverted, a main program that
is commanded from a human using a mouse for example, where clicking on
the NEXT button moves to the next thing in sequence? If you wrote your
primitives the right way, you can handle this environment just as well
as mapping down a list. Instead of calling a mapping function that
does essentially this:
  (prog (start) lp (if (endp) (return)) (process-here) (next) (go lp))
:you have an event handler that does this:
  (on-event start-process (start))
  (on-event click-next (if (endp) (beep) (next)))
  (on-event click-do (process-here))
  (on-event click-top (start))
You don't have to rewrite any of those primitives, just call them from
different places in the world. Actually I see one tiny inconsistency
there, anyone else see it?
From: P.C.
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <3cedeabb$0$18623$edfadb0f@dspool01.news.tele.dk>
Hi.

"Robert Maas" <···@netmagic.net> skrev i en meddelelse
·································@posting.google.com...
> Bruce Hoult <·····@hoult.org> wrote in message
news:<···························@copper.ipg.tsnz.net>...
> > In article <··············@mycroft.actrix.gen.nz>,
> >  Paul Foley <···········@actrix.gen.nz> wrote:
> > > Spelled "labels" in CL.
> > Why doesn't that count as a name?
>
> Because it's one of the tools provided by CL, used by you to build
> expressions, just like CDR and PROGN and LET, rather than some name you
> have to make up when you define a function. It's in the LISP package
> rather than in your own package, and implementors have already made sure
> it doesn't have the same name as any other tool in that package.
> The main problem with names is you run out of them or accidently step
> on something else by the same name that did something different or you
> have to use really long names to avoid those two problems.
> Consider this example: You need to make ten thousand different functions,
> each of which does something slightly different. With named functions,
> you have to make up ten thousand different names, and then try to remember
> which name did which task as you tried to call them by name as appropriate.
> But with unnamed functions you just make up ten thousand different
> task-expressions, each of which includes a LAMBDA at the top and LABELS
> somewhere inside. LAMBDA and LABELS are already defined in CL and are just
> two names instead of ten thousand names so they aren't a problem.
> The difference is especially important, and I assume here, when these
> ten thousand functions are designed by a program, i.e. you don't even
> know ahead of time how many of them there will be and what they will do
> so it's a pain to try to design a general purpose way to name them all
> before you even start running the program that makes them all. Think of a
> "smart system" or "neural net" implemented as a large number of cooperating
> functions, each of which is automatically adapted to the test data or
> real-life environmental data, and new functions (neurons) are created
> as needed, perhaps by some kind of replication and natural selection.
> Sure, you can GENSYM a new name as needed, but on a distributed system how
> can you synchronize GENSYM?? Imagine a gigantic array of computers linked
> across the InterNet, each containing enough space to store a hundred
> thousand of these evolving and competing functions, and you need to
> constantly move functions from one machine to another so that they can
> "breed" with non-siblings for better genetic diversity.
>
> By comparison, if you're defining just a few functions, or you have
> careful control over the namespace in which you're developing one
> function at a time, named functions are just fine, and unnamed functions
> are mostly a fun class exercise. But actually a very common practical
> use of an unnamed function is to have a parameterized function used
> in a mapping function. For example, to add a given (not constant)
> number to each element of a list, do this:
>
> (defun add-a-to-each-b (a blist)
>   (mapcar
>     (function (lambda (b) (+ a b))) ;lexical reference to local variable a
>     blist))
>
> In principle, each time that add-a-... function is called, it builds
> a brand-new unnamed function containing the current value of a frozen
> into it, calls that function a whole bunch of times, then discards it
> before returning the list of return values from that function. Of course an
> optimizing compiler might replace the unnamed function with some inline
> code, but at least in principle that's what we're doing.

Now this is maby just a comment from another amature, but my experience have
been, that simply having a few functions defined like ;
(defun a(b c d)
(b c d))
(defun b (a b c)
(c b a))
Aso.  solve a lot of naming problems. Also you can use (a b c) in a number of
fifferent situasions and for each task make a any function with two parameters .
P.C.
http://groups.yahoo.com/group/skuespilhus/
http://groups.yahoo.com/group/3D-Honeycomb-open/
From: Kaz Kylheku
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <slrnael13c.sbg.kaz@localhost.localdomain>
On 16 May 2002 21:21:42 -0700, Andy Reiter <·······@flop.co.uk> wrote:
>Say I have a little lambda function
>
>(lambda ()
>  (do-something))
>
>If I want an infinite loop of do-somethings, and I decided to do it via recursion,
>how would I go about it?
>is there some sort of "this" pointer, like in C++ classes. How does an unnamed
>function realize itself?

One way is to pass a reference to itself as an argument.

(let ((func #'(lambda (self) 
                (do-something)
		(funcall self self))))
  (funcall func func))

Note that in the programming language Lisp, recursion is not considered a
substitute for iteration. Implementations of Lisp are not required to optimize
tail recursion into iteration, so deep recursions might consume too much
storage.  Lisp has plenty of useful iteration constructs, from the simple to
the complex.

Take a look at do, dolist, dotimes and the loop macro.

If you want a local function that supports recursion, look at the labels
construct:

  (labels ((function-1 (lambda-list-1) (do-something-1))
           (function-2 (lambda-list-2) (do-something-2))
	   ...
	   (function-N ...))
    ;; call functions from here; they can mutually recurse
    (function-1 ...))

Lisp also supports unconditional control transfers, i.e. goto:

   (tagbody
     :infinite-loop
     (do-something)
     (go :infinite-loop))

Lisp is not Scheme.
From: Christopher Browne
Subject: Re: Newbie: How does a lambda recurse?
Date: 
Message-ID: <acp69n$rk5qm$7@ID-125932.news.dfncis.de>
Oops! ·······@flop.co.uk (Andy Reiter) was seen spray-painting on a wall:
> Say I have a little lambda function
>
> (lambda ()
>   (do-something))
>
> If I want an infinite loop of do-somethings, and I decided to do it via recursion,
> how would I go about it?
> is there some sort of "this" pointer, like in C++ classes. How does an unnamed
> function realize itself?

This would be a natural place for the use of the LABELS form, which is
a pretty usual way of declaring a local self-referencing function.

In the spot where you want to use it, you do:

..  some code ...

   (labels
      (iloop (lambda ()
                (do-something)
                (iloop)))
    (set-up-stuff)
    (iloop))

Why was it that you felt you wanted to use recursion for this?  

Recursion is liable to consume some stack space if your favorite CL
doesn't do some form of tail-call optimization.

And it's just as easy to do:
   (loop
      (do-something))
which has the merit of being at least two characters shorter than
anything that would have "lambda" in it.
-- 
(reverse (concatenate 'string ····················@" "454aa"))
http://www3.sympatico.ca/cbbrowne/linuxxian.html
Signs  of a   Klingon  Programmer  #6: "Debugging?   Klingons  do  not
debug. Our software does not coddle the weak."