Just curious: is it possible for a lambda (unnamed) function to call itself?

Regards,
Piotr

You could give the function to itself as a parameter.
Although then it isn't really unnamed any more...

  (let ((unnamed (lambda (me obj)
                   (if (atom obj)
                       obj
                     (cons (funcall me me (cdr obj))
                           (funcall me me (car obj)))))))
    (funcall unnamed unnamed '(a b c)))

I'm not aware of a syntax for getting the innermost enclosing function.
I'd be surprised if there was one, as LET is almost a LAMBDA too.
&WHOLE arguments spring to mind, but IIRC those are for macros only.

Kalle Olavi Niemitalo <k...@iki.fi> writes:

Or use Ugly Macros. I have (once or twice) used something along the
lines of:
(defmacro fakelambda (args &body body)
 `(lambda ,args (labels ((me ,args ,@body)) (me ,@args))))

This lets you get to call "the unnamed lambda" as ME within its body.

//Ingvar
--
When C++ is your hammer, everything looks like a thumb
        Latest seen from Steven M. Haflich, in c.l.l

This can't handle lambda list keywords.  A simple workaround would be:

  (defmacro fakelambda (lambda-list &body body)
    (let ((args (gensym)))
      `(lambda (&rest ,args)
         (labels ((me ,lambda-list ,@body))
           (apply #'me ,args)))))

but then the returned function can't be usefully inspected.  I wonder
if this can be made to work with supplied-p parameters and all that...
ah, now I get it!

  (defmacro fakelambda (lambda-list &body body)
    `(labels ((me ,lambda-list ,@body))
       #'me))

Functions made with LABELS have indefinite extent, right?  :-)

Kalle Olavi Niemitalo <k...@iki.fi> writes:

There is none.  It's not really very well-defined.  It would defeat the
ability of other macros surrounding any given form to insert additional
layers of function-boundary for dataflow purposes.  Consider the problem
of introducing extra unnamed blocks around something.  RETURN returns to
the innermost block NIL, but we had to add BLOCK and RETURN-FROM in order
to have a transparent way to add extra blocks around a form without
interfering with people's expectations about where BLOCK boundaries would
be.  If we had the facility you're talking about, there would have to be
named and unnamed versions of "enclosing functions" in order to not
violate referential transparency.  Anyway, it's not done.

I'm not sure what that means or why it's relevant, but see below.

Yes, &whole is of no help here.  It would only point back to the source
form, not to the resulting function.  Forms are not callable.  A lambda
expression evaluates to a function, it is not itself a function.

The implementation in most Scheme implementations is the same as how
you'd do it in Lisp, they just don't tell you.

 (defmacro letrec (bindings &body forms)
   `(let ,(mapcar #'car bindings)
      (setq ,@(mapcan #'copy-list bindings))
       ,@forms))

The only difference is that in Common Lisp, because we have two namespaces,
you call a variable's value with funcall instead of like a function.

 (letrec ((fact (lambda (x)
                  (if (zerop x) 1
                      (* x (funcall fact (- x 1)))))))
   (funcall fact 6))
 => 720

Not that you couldn't put some syntactic sugar around that if
you wanted to.  Consider:

 (defmacro fletrec (bindings &body forms)
   (let ((temp (gensym)))
     `(let ,(mapcar #'car bindings)
       (flet ,(mapcar #'(lambda (binding)
                          (let ((name (car binding)))
                            `(,name (&rest ,temp)
                                (declare (dynamic-extent ,temp))
                                (apply ,name ,temp))))
                      bindings)
          (setq ,@(mapcan #'copy-list bindings))
         ,@forms))))

 (fletrec ((fact (lambda (x)
                   (if (zerop x) 1
                       (* x (fact (- x 1)))))))
   (fact 6))
 => 720

Kent M Pitman <pit...@world.std.com> writes:

I meant (LET ((VAR VAL)) BODY) = ((LAMBDA (VAR) BODY) VAL);
making LAMBDA also save the function for retrieval with
ENCLOSING-FUNCTION (or whatever it would be called) would break
the equivalence.

You can COERCE the lambda expression to a function... but then
you lose local bindings.  Hm.  Perhaps with &ENVIRONMENT and
EVAL...  except that's restricted to macros too.

The indentation of ,@forms confused me for several minutes.

When you write macros in production code, do you make them
strictly check the syntax of arguments and signal errors for
things like (LETREC ((VAR 'VAL EXTRA)))?  Is DESTRUCTURING-BIND
good for that?

Is there a function like MAPCAN that would use APPEND rather than
NCONC, so that COPY-LIST wouldn't be needed?  I didn't find such
a thing in the HyperSpec.

Kalle Olavi Niemitalo <k...@iki.fi> writes:

Sometimes I check, sometimes not.  The user is obliged, regardless,
not to put stuff there, so I consider it "helpful but optional" to
do that checking.

There isn't any.

But there are about 117 other ways to win, so it's not like you're stuck.

LOOP has an appending collection mechanism.

And (reduce #'append lists) or (apply #'append lists) probably would have
done it.  I just used the first thing that came into my head.
In spite of what you've perhaps been told, NCONC is not evil nor to be
avoided, nor are all cases of COPY-LIST wasteful.
Note that these calls to COPY-LIST are (mostly) not doing extra copying--those
cons cells WILL be copied anyway even if
you use APPEND.  MAPCAN+COPY-LIST just makes the copying explicit...

I said "mostly" above in one place because my version did copy the last
pair of bindings "unnecessarily" ... but that seemed small matter.

Kent M Pitman <pit...@world.std.com> writes:

I was thinking that COPY-LIST scans each list, and MAPCAN must
scan it again to find the end.  The slowdown pales to the time
spent compiling the result, but if there were an easy-to-use
operator that did the same thing with only one scan, I'd rather
use it.

I see.  It's a bit verbose to use, though.

The first one needs :FROM-END T to avoid quadratic complexity.
Unfortunately, CMUCL 2.5.1 implements that by reversing the list
first, and consing is even worse than scanning.  Does any
implementation behave otherwise?  I don't see any obvious
algorithm.

The second one is bounded by CALL-ARGUMENTS-LIMIT.  (Is there any
such limit for the number of variables bound in a LET?)

    PK> Just curious: is it possible for a lambda (unnamed) function
    PK> to call itself?

The short answer is: not really. That's what labels or defun are for.

~ESP

P.S. I like to say "applicative order Y combinator", because it's such a
cool word. So, I will do so here.

--
Evan Prodromou
e...@prodromou.san-francisco.ca.us

Kalle Olavi Niemitalo <k...@iki.fi> writes:

This doesn't add materially to the algorithmic complexity of the operation.
An O(n) operation plus another O(n) operation is still O(n).

It's true that it adds a tiny amount of extra work in the rescan, but
really not worth fussing over unless this is the inner loop of some very
long computation.  In the case at hand, it just isn't, and any time spent
trying to fuss over further optimization is time wasted from your life.
Take the same time you would have spent optimizing such things and be home
for dinner just a little earlier, and you'll be happier all around.

You could make one.  But the number of times you'd use it in your lifetime
might not add up to the time it takes you to write it.  Seriously, the time
to do optimizations of this nitpicking level (that is, operations that don't
improve the algorithmic complexity of code, but merely change tiny constant
factors in code that is hardly ever called) is when you have a product
delivered or about to be delivered and you think it's going to be unsuitable
for some customer if its speed is not enough.

Programmers waste too much of their lives optimizing things that do not
matter.  This means they are home late for dinner unnecessarily too often,
and it also means that even when they'd not be going home but would be
staying to work more, they're working more on the wrong things.  Computer
science has bigger problems than making this little piece of code fast.

Learn to live with it.

I am not kidding.

Common Lisp is about doing things in practical ways.  LOOP, for all
its syntactic weirdness, is often the most practical in a number of
circumstnaces.  It really needs to be in your arsenal of things you're
willing to try, or you're crippling yourself.

If you really, really want to spend your whole life nitpicking about small
details and not ever getting on to the problems that are holding mankind
back, no one is stopping you.  But I can't stress strongly enough how little
I think this kind of thing matters and how important it is to learn to tell
the difference between things that do warrant careful scrutiny and things
that do not.

(It's not like I myself never obsess on things that don't matter, mind you.
I'm just hugely conscious of it, and waste a lot of time needlessly obsessing
about that, too...)

Right.   But even so, I was assuming this set of lists would be quite small
and so I just didn't worry a lot about that...

APPLY is probably the cheapest in this case if you know the set of
lists will always be short enough for it to work.  (There's a
limitation of how many lists you can use in APPLY because of
CALL-ARGUMENTS-LIMIT, as you note below.)

Well, it's possible to stack-allocate such a reversed list, so the gc
issue can be made a non-issue. Also, one can use real recursion (stacks)
to simulate the effect, again if you dont' mind pushing LOTS of stack.
Most gc experts will tell you, though, that consing that is immediately
dropped is gc'd quite efficiently by generational systems (which a lot
of people use), so the cost of just heap-allocating the reversed list and
discarding it isn't as great as you might think.

And, btw, optimization is almost always a per-vendor activity.  Each vendor
does it a different way.  It's good to talk here if a vendor says something
can't be optimized and you disagree and want suggestions.  But the standard
can't and doesn't specify optimizations.

Incidentally, even keyword calling (the :FROM-END T) can introduce extra
time into your calculation, but I recommend you also not worry about that
unless it gets out of hand.  In principle, an implementation can optimize
that out.  In practice, most just focus on the common cases and leave the
others for a rainy day.

No.  The compiler is supposed to split the LET if it needs to, though
you might find implementations with bugs.  I've certainly seen compilers
with little notes in them saying "I'll fix this when someone first
reports the bug".

-- -- --

To be clear:

 * I think it's good for vendors to care about this kind of speed issue.

 * I think it's ok for users to care about this kind of speed issue
   if it is a known bottleneck in a real application.

 * I think the rest of the time, users should mostly program as if
   something is going to be fast and send bug reports when it doesn't
   turn out to be.

Kent M Pitman <pit...@world.std.com> writes:

Oh, I do use LOOP.  In this situation however, I feel the
verbosity of LOOP outweighs the minimal speedup.

"Piotr Kuchta" <pi...@itam.zabrze.pl> wondered in message
news:9i48u8$d7h$1@kapsel.intranet...
itself?

If I understand you correctly, yes.  The Y operator does just that for you.

 (defun Y (f)
   (  (lambda (g) #'(lambda (h) (funcall (funcall f (funcall g g)) h)))
    #'(lambda (g) #'(lambda (h) (funcall (funcall f (funcall g g)) h)))))

 (funcall (Y #'(lambda (myself)
                #'(lambda (n) (if (zerop n) 1 (* n (funcall myself (- X
1)))))))
          10)

But, as you can see, this is rather out of style for a Lisp2 such as Common
Lisp, so one would not normally do this.  In a Lisp1 this is more natural,
and in a normal order Lisp more natural again.

--
Biep
Reply via http://www.biep.org

"Biep @ http://www.biep.org/" <reply-...@my-web-site.com> writes:

Well, in practice, there's very little reason to do this at all.

In my entire Lisp career, I've never had any need for the Y operator
other than to help people with homework.

That's not to say it has no theoretical interest, nor that theory has no
purpose, but it's just not much of an indictment of a language designed
for commercial use...

On Tue, 10 Jul 2001 12:08:35 +0200, Biep @ http://www biep org/ wrote:

But why on earth would you *want* to do that?  Even if you correct the
error (replace X with N),

  (funcall (Y (lambda (myself) (lambda (n) ...))) 10)

can be spelled

  (labels ((myself (n) ...)) (myself 10))

which is more concise and far easier to understand.  And you get to
use (myself ...) rather than (funcall myself ...), just in like in a
Lisp-1.

--
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>"))

[...]

I wanted to write sth. like that:

(mapcar #'(lambda(n) (if (< n 2) 1 (* n (callme (- n 1)))))  '(1 2 3 4 5 6))

OK, I am joking. I was *just curious*. Can't I? ;)

Regards,
Piotr

Kent M Pitman <pit...@world.std.com> writes:

Hmm.  Due to a conversation I am having on the side (with Biep, in fact),
I am curious:  Are you saying then that you consider CL to be designed for
commercial use _only_?  What do mean by "designed for commercial use"?
Do you exclude academic application here?

--
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   du...@Franz.COM (internet)

This solution doesn't seem to have been given in so many words.  I
think it's quite simple and the syntax is painless.

The basic thing you want to do is give the function a name by which it
can be called, and make it syntactically pleasant to call it (no
(FUNCALL x ...) in the body of the function).

This is what LABELS does, so this does that for your case:

    (mapcar (labels ((me (n)
                       (if (< n 2)
                           1
                           (* n (me (- n 1))))))
              #'me)
            '(1 2 3 4 5 6))

If you really do this a lot (which I think would be unusual style in
CL), then you can write a macro to hide the LABELS:

    (defmacro lambda-named (name args &body body)
      `(labels ((,name ,args ,@body))
         #',name))

And now:

    (mapcar (lambda-named me (n)
              (if (< n 2)
                  1
                  (* n (me (- n 1)))))
            '(1 2 3 4 5 6))

--tim

:
:
:

In Paul Graham's On Lisp you'll find the anaphoric macro alambda.

 (defmacro alambda (parms &body body)
   `(labels ((self ,parms ,@body))
      #'self))

Examples:

 (mapcar (alambda (n) (if (< n 2) 1 (* n (self (1- n))))) '(0 1 2 3 4))
 => (1 1 2 6 24)

 (mapcar (alambda (m n)
           (cond ((zerop m) (1+ n))
                 ((zerop n) (self (1- m) 1))
                 (t (self (1- m) (self m (1- n))))))
  '(1 2 3) '(2 2 2))
  => (4 7 29)

-Wolfhard

A little second-hand scholarship:

"Logical completeness required that notation used to express
functions used as functional arguments be extended to provide
for recursive functions, and the LABEL notation was invented by
Nathaniel Rochester for this purpose. D.M.R. Park pointed out
that LABEL was logically unnecessary since the result could be
achieved using only LAMBDA -by a construction annalogous to
Church's Y-operator, albeit in a more complicated way" (1)
McCarthy, J. (1981): "History of LISP (2)". In Wexelbalt, R. (ed.):
"History of Programming Languages", Academic Press.

(1) By the way, Turing's T operator could be also use(ful/less)
for this purpose.
(2) Please forgive Prof. McCarthy for using capital letters,
after all it is his language.

---------------------
Jose-Luis Perez-de-la-Cruz
ETSI Informatica
POB 4114
MALAGA 29080 SPAIN
Tlf +34 952 132801
Fax +34 952 131397
--------------------

Both Tim Bradshaw's version and Paul Graham's are anaphoric.  Tim's is
more flexible, however.  For example, the following (really stupid)
way of creating a new tree of numbers, with each number multiplied by
10, would not be possible with Graham's version:
   * (mapcar (lambda-named for-nums (thing)
               (if (consp thing)
                   (funcall (lambda-named for-conses (cons)
                              (mapcar #'for-nums cons))
                            thing)
                 (* 10 thing)))
             '(1 2 (3 4 (5 6) 7) 8 ((((9) 10)))))
   => (10 20 (30 40 (50 60) 70) 80 ((((90) 100))))

A less stupid case might occur in the body of a method, if the
programmer is used to smalltalk, and names one of the parameters
`self'.  Personally, I (almost) never hardwire the names of bindings
in my macros -- I figure I'll be happiest deciding what to name the
variable to be bound when I'm using the macro.

I didn't mean anything deep, just that "academic use" was not a stated
priority of design.  In particular, as a matter of history, it was noted
that every professor usually has a different theory of how to teach, so
there is no canonical notion of "academic" anyway.  But in the local
context of this conversation, I meant that people seem obsessed with
teaching the Y operator to Lispers, which I think does more damage than
good, becuase it scares people into thinking you'd have to understand
this to do Lisp.  Lisp DOES make writing the Y operator hard, but since
Lisp was not designed to support the writing of Y operators and their ilk
(whatever that might be), it doesn't matter.

Lisp was designed for commercial use means, to me, it didn't get caught
up in pedantic issues of religion over The One True Right Way or
Cleanliness to the Nth Degree.  We tried to be graceful, but we also tried
to force discussions known to be unsolvable in general to terminate in
finite time by just sometimes making arbitrary decisions, by tolerating
expressional/naming inconsistencies, by admitting more than one way of
doing things, and so on.  Academics tend to hate that, but then, they aren't
being paid to get a project done on schedule.  People who have work to do
and need it done on time are less critical of LOOP, of having both WHEN
and UNLESS when one might be argued to be computationally redundant, don't
mind using THROW instead of continuations (maybe even like it), etc.

Kent M Pitman <pit...@world.std.com> writes:

OK, thanks.  This matches the position you seemed to have always taken,
but I wanted to be sure.  One of the problems we run into in placing
CL into universities is the occasional statement "Oh, we already teach
a lisp course here; we have <name-a-scheme-implementation>".  It would
be a shame if CL users did not themselves think that CL has as good
or better potential in academia than Scheme.  I personally believe
that it has better potential, since it allows so many options, and,
if taught well, can lead to instant marketability in the Lisp
job market (where CL is, after all, the "commercial" lisp...)

--
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   du...@Franz.COM (internet)

I agree.

Note that in a trivial sense, anything of commercial value is of academic
interest since some schools teach trades.

It's ironic that the truly "academic" issues are the things with no
commercial value.  MIT filled my head with tons of that.  There are
times when I wish I could trade some of that academic stuff they laid
on me for practical stuff like other colleges teach.

Kent M Pitman <pit...@world.std.com> writes:

        Hm. Note that colleges/universities with a "practical" focus
are more likely to teach C++ and Java (and possibly even MicroSoft
platform programming and applications).

        Edsger Dijkstra said "The use of COBOL cripples the mind; its
teaching should, therefore, be regarded as a criminal offense." This
needs to be updated...

--
Raymond Wiker
Raymond.Wi...@fast.no

[I re-ordered somewhat..]

Kent M Pitman <pit...@world.std.com> writes:

Oh, I fully agree, but I (rightly or wrongly) didn't interpret the question
as practice-oriented.
(I could well imagine a Lisp where something like labels reduces to Y,
however, but that is something different.)

"Kent M Pitman" <pit...@world.std.com> wrote in message
news:sfwy9pwh913.fsf@world.std.com...

Their ilk?  Would this do (in Scheme)?
  ((call/cc call/cc)(call/cc call/cc))

:-)

Kent M Pitman <pit...@world.std.com> writes:

Kent M Pitman <pit...@world.std.com> writes:

Thanks for unwittingly supporting my statement to Duane :-)

(And oh, Duane, I didn't mean MY (emailed) statement in an "absolute
knowledge" sense, but simply in the way that e.g. a carpenter may "know
wood", and know that it tends to have certain characteristics.  Sorry for
not being clear.)

--
Biep
Reply via http://www.biep.org