2 Common Lisp Questions
wan...@exploited.barmy.army
Hey all,
I've got 2 questions about Common Lisp as defined by the standard.
1) From reading Cltl2 and the standard it seems that
Common Lisp is not properly tail recursive. Is this true?
If so, what's with books recommending that one program
in a functional (heavily recursive) style?
2) What was the reasoning behind forcing programmers to
use a special quote form and function call to deal with
higher order functions? For example, I have to do the
following:
(mapcar #'+ '(1 2 3))
Instead of the more intuitive:
(mapcar + '(1 2 3))
And:
(defun f (p)
(funcall p x y z))
Instead of the more intuitive:
(defun f (p)
(p x y z))
Where I am assuming that x, y, and z were defined (of
course). Why is this so? I can't see being forced to
use this awkward notation as anything but a detriment.
Is there some benefit to doing things this way, is
it some kind of historical baggage, or did the standards
committee just screw up?
Thanks in advance.
BTW, my email address has been altered to avoid spam.
Sunil Mishra
In article <6ct032$qo7$1...@Masala.CC.UH.EDU> wan...@exploited.barmy.army writes:
Hey all,
I've got 2 questions about Common Lisp as defined by the standard.
1) From reading Cltl2 and the standard it seems that
Common Lisp is not properly tail recursive. Is this true?
If so, what's with books recommending that one program
in a functional (heavily recursive) style?
Others will answer this question better, probably, but I am fairly certain
that lisp can handle tail call elimination quite effectively. Is there a
specific instance you can point to where this would not happen?
2) What was the reasoning behind forcing programmers to
use a special quote form and function call to deal with
higher order functions? For example, I have to do the
following:
(mapcar #'+ '(1 2 3))
Instead of the more intuitive:
(mapcar + '(1 2 3))
And:
(defun f (p)
(funcall p x y z))
Instead of the more intuitive:
(defun f (p)
(p x y z))
Where I am assuming that x, y, and z were defined (of
course). Why is this so? I can't see being forced to
use this awkward notation as anything but a detriment.
Is there some benefit to doing things this way, is
it some kind of historical baggage, or did the standards
committee just screw up?
Lisp allows a symbol to simultaneously have a value as well as a function
value, distinct from one another. #' accesses the function value, while
without the #' we get the symbol value. So, if you just say
(mapcar + '(1 2 3))
you get the value of +, rather than the function value. You could do
something as goofy as
(let ((+ #'-))
(mapcar + '(1 2 3)))
but I have no idea why you would want to do so. I suppose you can see the
ambiguity from simply using +.
The same applies to the funcall situation.
I think it's historical baggage that symbols have a value as well as a
function value, the rest just follows from it.
Sunil
Barry Margolin
In article <efy7m6l...@peachtree.cc.gatech.edu>,
Sunil Mishra <smi...@peachtree.cc.gatech.edu> wrote:
>Others will answer this question better, probably, but I am fairly certain
>that lisp can handle tail call elimination quite effectively. Is there a
>specific instance you can point to where this would not happen?
While Lisp implementations may perform tail call elimination, the original
poster is correct that they're not required to, as they are for Scheme.
The philosophy of Common Lisp is that optimizations are up to implementors,
not to be specified by the language design, and market forces will direct
them appropriately.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
wan...@exploited.barmy.army
In article <NBpI.16$us2.2...@cam-news-reader1.bbnplanet.com>,
Barry Margolin <bar...@bbnplanet.com> wrote:
[Snip]
>While Lisp implementations may perform tail call elimination, the original
>poster is correct that they're not required to, as they are for Scheme.
>
>The philosophy of Common Lisp is that optimizations are up to implementors,
>not to be specified by the language design, and market forces will direct
>them appropriately.
>
That's unfortunate because tail call optimization happens to be the
key to programming in Lisp using the functional paradigm (it's already
suited to this paradigm in other ways).
I take it that the standards committee isn't reconsidering this
unfortunate decision?
>--
>Barry Margolin, bar...@bbnplanet.com
>GTE Internetworking, Powered by BBN, Cambridge, MA
>Support the anti-spam movement; see <http://www.cauce.org/>
>Please don't send technical questions directly to me, post them to newsgroups.
Thanks for your prompt reply.
Barry Margolin
In article <6cteri$t9r$1...@Masala.CC.UH.EDU>,
<wan...@exploited.barmy.army> wrote:
>In article <NBpI.16$us2.2...@cam-news-reader1.bbnplanet.com>,
>Barry Margolin <bar...@bbnplanet.com> wrote:
>>The philosophy of Common Lisp is that optimizations are up to implementors,
>>not to be specified by the language design, and market forces will direct
>>them appropriately.
>
>That's unfortunate because tail call optimization happens to be the
>key to programming in Lisp using the functional paradigm (it's already
>suited to this paradigm in other ways).
Somehow we've been programming that way for decades in Lisp without this
requirement.
Additionally, many recursive functions aren't tail-recursive when written
in the most natural style. It's often necessary to contort code in order
to make it tail recursive. For instance, a natural implementation of
factorial is:
(defun fact (n)
(if (< n 2) 1
(* n (fact (1- n)))))
whereas the tail-recursive version requires a helper function that
accumulates the result in a parameter:
(defun fact (n)
(labels ((fact-internal (n result)
(if (< n 2) result
(fact-internal (1- n) (* n result)))))
(fact-internal n 1)))
Yes, I know that it's possible to automate this transformation, but that's
asking for even more than just tail-call elimination.
>I take it that the standards committee isn't reconsidering this
>unfortunate decision?
The standard is already published, so the committee isn't reconsidering
anything. Work on the next version of the standard won't begin for a few
years.
And it wasn't actually a decision of the standards committee, it never
really came up IIRC. Most of the Lisps that Common Lisp was derived from
didn't require tail call elimination, and we never considered adding that
requirement.
Erik Naggum
* Barry Margolin
| While Lisp implementations may perform tail call elimination, the
| original poster is correct that they're not required to, as they are for
| Scheme.
|
| implementors, not to be specified by the language design, and market
| forces will direct them appropriately.
* Some Anonymous Wanker
| That's unfortunate because tail call optimization happens to be the key
| to programming in Lisp using the functional paradigm (it's already suited
| to this paradigm in other ways).
Barry is telling you that if you need it, you go to a Lisp vendor that
has made a point of making tail-call optimizations. that's what the
market is all about. you don't program in a standard, you program in an
actual implementation. if you are conscientious and show sufficient
attention to detail, you document the parts of your application that
depend on the implementation and make requirements on your users to
satisfy those requirements, much like memory size and CPU speed and such
when specifying minimal hardware configurations. of course, this should
not be construed to mean that you ignore the standard. an implementation
is supposed to conform to a standard and you should consult the standard
for the proper behavior of the implemention. in that sense, you are
programming according to the standard, but still _in_ the implementation.
lots of issues are deferred to implementors in Common Lisp, because it
was impossible to get sufficient agreement on the Only Right Thing. in
Scheme, the committee refused to include many features if no such
consensus could be reached. I very much appreciate the Common Lisp folks
for choosing not to force me to implement stuff myself that I cannot yet,
if ever, do as well as the implementors of my Common Lisp. (this is what
Scheme requires of all programmers who want one of those features.)
incidentally, tail call optimization has its downsides, such as making
code much harder to debug. however, most real Common Lisp systems allow
you to request it, and do as best as they can. implementation issues can
make different tail calls optimizable in different implementations.
| I take it that the standards committee isn't reconsidering this
| unfortunate decision?
which "unfortunate" decision? to leave decisions like that to the market
forces, or not forcing a very complex requirement on all implementations?
your two questions actually have the same one answer: Common Lisp is not
Scheme. or more generally for Lisp: Lisp is a family of sometimes very
different languages, not one language with dialects with minor variations
that someone from one dialect can call flaws in another. or even more
generally: judge a language on its own merits, not those of some other
language. this latter point holds for _all_ languages.
#:Erik
--
God grant me serenity to accept the code I cannot change,
courage to change the code I can, and wisdom to know the difference.
Jens Kilian
wan...@exploited.barmy.army writes:
> I've got 2 questions about Common Lisp as defined by the standard.
>
> 1) From reading Cltl2 and the standard it seems that
> Common Lisp is not properly tail recursive. Is this true?
> If so, what's with books recommending that one program
> in a functional (heavily recursive) style?
The Common Lisp standard doesn't *require* tail recursion optimization
(like the Scheme standard does), but it doesn't *forbid* it, either.
> 2) What was the reasoning behind forcing programmers to
> use a special quote form and function call to deal with
> higher order functions?
Common Lisp is a 2-Lisp, i.e., every symbol can have two values, one of which
is used when the symbol occurs in a function position (or whatever they call
it):
(defun foo ...) ; defines the function value
(defvar foo ...) ; defines the, um, value value :-)
(foo ...) ; accesses the function value
(bar foo ...) ; accesses the other one
So, to access the function value anywhere else than in a function position,
some kind of special notation is needed:
(bar (function 'foo) ...) ; passes function value of foo to bar
And #'... is just syntactic sugar for (function '...).
Scheme is an example of a 1-Lisp: every symbol can have only a single value.
No syntactic contortions needed.
HTH,
Jens.
--
mailto:j...@acm.org phone:+49-7031-14-7698 (HP TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-14-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
Erik Naggum
* Jens Kilian
| And #'... is just syntactic sugar for (function '...).
#'x is equivalent to (function x), not (function 'x).
#:Erik, picking nits for my big nit collection
Marco Antoniotti
wan...@exploited.barmy.army writes:
> In article <NBpI.16$us2.2...@cam-news-reader1.bbnplanet.com>,
> Barry Margolin <bar...@bbnplanet.com> wrote:
>
> [Snip]
>
> >While Lisp implementations may perform tail call elimination, the original
> >poster is correct that they're not required to, as they are for Scheme.
> >
> >The philosophy of Common Lisp is that optimizations are up to implementors,
> >not to be specified by the language design, and market forces will direct
> >them appropriately.
> >
>
> That's unfortunate because tail call optimization happens to be the
> key to programming in Lisp using the functional paradigm (it's already
> suited to this paradigm in other ways).
AFAIK (and I might be wrong), the following compilers are "fully
tail-recursive": CMUCL, ACL, LispWorks and MCL. GCL is not (i.e. it
is only partially). I do not remember the status of CLISP, but Bruno
Haible is surely ready to answer this :)
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 80 79 23, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
Jens Kilian
Erik Naggum <cle...@naggum.no> writes:
> * Jens Kilian
> | And #'... is just syntactic sugar for (function '...).
>
> #'x is equivalent to (function x), not (function 'x).
In that case, my (function 'foo) also was in error. Sorry, it's been some time
since I last used Lisp (sigh...).
Bye,
Jens (I'd rather be Lisping) Kilian.
Kent M Pitman
Marco Antoniotti <mar...@galvani.parades.rm.cnr.it> writes:
> AFAIK (and I might be wrong), the following compilers are "fully
> tail-recursive": CMUCL, ACL, LispWorks and MCL. GCL is not (i.e. it
> is only partially). I do not remember the status of CLISP, but Bruno
> Haible is surely ready to answer this :)
Right, it's indeed a widespread feature BUT... Be careful, too,
because (just as an example) although LispWorks will at your request
handle tail call elimination efficiently, it doesn't do this in the
highest debug settings. Hence, if your concern is writing programs
that iterate over large data sets using tail recursive style, youc an
do that with appropriate OPTIMIZE declarations. But unless you are
prepared to always set the OPTIMIZE declarations that way, it isn't a
good idea to program that way.
Personally, I like that it's a switch I can turn on and off lexically
at various points in the program. I'd be extremely uncomfortable with
it otherwise. I wouldn't mind seeing the particular optimization
declaration details made standard so every vendor controlled it the
same way. I'd very much mind seeing it be required even in heavy debug
mode.
But what Barry and Erik and others have said is essentially correct
on two important points I want to underscore:
(1) The standards committee is NOT a design committee. It settles on
things that the community acknowledges are or need to be standard.
But DESIGN happens at the vendor level and only later percolates to
the standards level when there is community-wide consensus. If
anyone has a concern about a product, they can join the committee
(it's open to anyone world-wide, I believe) or work through their
vendor. But either way, always realize that you've got a hard
battle ahead when promoting an idea not already a "de facto
standard" in some or all implementations.
(2) There are many things one can gripe at Lisp about, but this
seems an odd one that surely is a personal preference issue.
If this is REALLY what will make or break a sale of Lisp to someone,
then they should tell the sales person. I bet the sales person
will say "gee, no one ever said they cared" because I bet no one
ever did. People have been getting work done in CL for decades
and the ones who are up against a wall are not waiting for tail
call optimization. They need portable multitasking, better
system definition tools, portable FFI or RPC support, a CORBA
binding, a sockets library, and on and on. Without these more
important things, the issue of tail recursion seems to me almost
a total irrelevance because without them no one can connect to Lisp
from another program to find its opinion (tail recursive or
otherwise) on something.
Disclaimer: This is all just my personal opinion and observations, and
not the official posture of any company or standards organization I'm
affiliated with.
Kent M Pitman
Jens Kilian <Jens_...@bbn.hp.com> writes:
> Common Lisp is a 2-Lisp,
Uh, that's Lisp2, not 2-lisp.
The term Lisp<N> is something I coined in a paper I wrote with Gabriel
to talk about a Lisp with <N> namespaces. (Truly, Lisp has more than
thanks to TAGBODY and BLOCK and other quasi-namespaces like the class
and package namespace. But it's common and reasonable to refer to it
as a Lisp2 for simplicity. Scheme is in the Lisp1 partition.)
The term <n>-Lisp was invented by Brian Smith to discuss the strength
of a Lisp needed to handle introspection in a reflective lisp. If
memory serves me, 0-lisp is a sort of kernel of compiled code that no
longer knows why it does what it does and has no sense of lispiness
left in it, 1-lisp is a model of interpreted code with no
introspective capabiliity at all, 2-lisp models some partly
introspective situations needed to bootstrap 3-lisp, and 3-lisp is
powerful enough that it can be replicated to whatever depth needed to
satsify the illusion of an infinite tower. I might be wrong on the
details, but I mention them only to say that they particular numbers
have particular associated semantices that are nothing to do with
namespaces.
And, more genrally, my real point is that 2-lisp and lisp2 are not
equivalent terms.
Jens Kilian
Kent M Pitman <pit...@world.std.com> writes:
> And, more genrally, my real point is that 2-lisp and lisp2 are not
> equivalent terms.
OK. As I said, I've been out of practice for some time.
Jens.