I get the error: CNT is not of type LIST. I don't understand what's causing this; as far as I can tell my usage of the named let and the rest of the constructs is correct. Can someone explain?
P.S. I realize the best way to do this would be a tail-recursive function using `do' but that's not the point.
Thanks a lot, -- Jordan Katz <k...@underlevel.net> | Mind the gap
In article <m38zhnt4ef....@underlevel.underlevel.net>, Jordan Katz wrote: >Hi,
> I was thinking of the possible ways to define my own length function > (to get a better understanding of the language) and decided to use a > named let:
k...@ashi.footprints.net (Kaz Kylheku) writes: > In article <m38zhnt4ef....@underlevel.underlevel.net>, Jordan Katz wrote: > >Hi,
> > I was thinking of the possible ways to define my own length function > > (to get a better understanding of the language) and decided to use a > > named let:
and I thought this same concept would work in CL (after fixing all the minor differences such as null?, begin, define, etc. of course.) I'll look into some of my Lisp manuals for their explanation of named let.
> Also, you are going to need some kind of iteration or recursion to > actually find the length of the list. ;) Easily done without any > local variables:
Jordan Katz <k...@underlevel.net> writes: > I was thinking of the possible ways to define my own length function > (to get a better understanding of the language) and decided to use a > named let:
> I get the error: CNT is not of type LIST. I don't understand what's > causing this; as far as I can tell my usage of the named let and the > rest of the constructs is correct. Can someone explain?
Yes, you're apparently using Lisp and not Scheme.
Scheme has named LET, Lisp does not.
First, let's correct your use of Scheme. Then we'll translate to Lisp. You should be recursing on both the list and the count, or neither. That is, either (let cnt ((len 0) (lst lst)) (if (null? lst) len (cnt (1+ len) (cdr lst)))) or (let ((len 0)) (let cnt () (if (null? lst) len (begin (setf len (1+ len)) (setf lst (cdr lst)) (cnt))))) Obviously, the latter is a little silly, but I point it out as an option. The former would translate into Common Lisp as:
> P.S. > I realize the best way to do this would be a tail-recursive function > using `do' but that's not the point.
No, that's not right. DO is certainly a good thing to use but in Common Lisp it works by iteration, not "tail recursion". In general, Common Lisp (unlike Scheme) does not guarantee to use constant stack even on tail calls, so you don't want to use it for things that might iterate for an arbitrarily large distance. Use iteration (DO, DOLIST, LOOP, etc.) or some lower level operator (TAGBODY or PROG) that does not make new stack on every iteration.
> I was thinking of the possible ways to define my own length function > (to get a better understanding of the language) and decided to use a > named let:
> I get the error: CNT is not of type LIST. I don't understand what's > causing this; as far as I can tell my usage of the named let and the > rest of the constructs is correct. Can someone explain?
You are using a "named let", a Scheme feature that is needed to deal with the lacks of the Scheme standard.
Alas, the "named let" feature is nice. In CL a good approximation is
(defun my-length (list) ; In CL you can use meaningful names :) (named-let cnt ((len 0)) (if (null list) len (progn (setf list (rest list)) (cnt (1+ len))))))
This is also tail-recursive. If your underlying CL does tail-call elimination you are home free,
Cheers
-- Marco Antoniotti ======================================================== NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 719 Broadway 12th Floor fax +1 - 212 - 995 4122 New York, NY 10003, USA http://bioinformatics.cat.nyu.edu "Hello New York! We'll do what we can!" Bill Murray in `Ghostbusters'.
> No, that's not right. DO is certainly a good thing to use but in Common Lisp > it works by iteration, not "tail recursion". In general, Common Lisp > (unlike Scheme) does not guarantee to use constant stack even on tail calls, > so you don't want to use it for things that might iterate for an arbitrarily > large distance. Use iteration (DO, DOLIST, LOOP, etc.) or some lower level > operator (TAGBODY or PROG) that does not make new stack on every iteration.
However, it wouldn't hurt to find out if/when your implementation optimizes tail calls. Once in a long while, I'll find a tail-recursive version of a function to be easier to read than the iterative version (mind you, this is quite infrequent). In those cases, I'm glad to know how to ensure that my implementation will optimize it correctly.
> > No, that's not right. DO is certainly a good thing to use but in > > Common Lisp it works by iteration, not "tail recursion". In > > general, Common Lisp (unlike Scheme) does not guarantee to use > > constant stack even on tail calls, so you don't want to use it for > > things that might iterate for an arbitrarily large distance. Use > > iteration (DO, DOLIST, LOOP, etc.) or some lower level operator > > (TAGBODY or PROG) that does not make new stack on every iteration.
> However, it wouldn't hurt to find out if/when your implementation > optimizes tail calls. Once in a long while, I'll find a > tail-recursive version of a function to be easier to read than the > iterative version (mind you, this is quite infrequent). In those > cases, I'm glad to know how to ensure that my implementation will > optimize it correctly.
Well, IMO, then you are not programming in Common Lisp. You are programming in a vendor-specific dialect since your code may not port.
I guess people can disagree on the value of doing this, but personally I don't recommend it when there's an equally good portable solution available.
Personally, I've never met a tail recursive definition that I felt was any more clear than an iterative one, properly expressed.
Marco Antoniotti <marc...@cs.nyu.edu> writes: > Jordan Katz <k...@underlevel.net> writes:
> > Hi,
> > I was thinking of the possible ways to define my own length function > > (to get a better understanding of the language) and decided to use a > > named let:
> > I get the error: CNT is not of type LIST. I don't understand what's > > causing this; as far as I can tell my usage of the named let and the > > rest of the constructs is correct. Can someone explain?
> You are using a "named let", a Scheme feature that is needed to deal > with the lacks of the Scheme standard.
> Alas, the "named let" feature is nice. In CL a good approximation is
> (defun my-length (list) ; In CL you can use meaningful names :) > (named-let cnt ((len 0)) > (if (null list) > len > (progn (setf list (rest list)) > (cnt (1+ len))))))
> This is also tail-recursive. If your underlying CL does tail-call > elimination you are home free,
Incidentally.....
Using the above macro would produce much much much better and more readable CL code as a result of the Scheme->CL translator that has been floating around (and which does a terrible job at translating all the 'let loop' appearing in the typical Scheme program).
Cheers
-- Marco Antoniotti ======================================================== NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 719 Broadway 12th Floor fax +1 - 212 - 995 4122 New York, NY 10003, USA http://bioinformatics.cat.nyu.edu "Hello New York! We'll do what we can!" Bill Murray in `Ghostbusters'.
* I wrote: > However, it wouldn't hurt to find out if/when your implementation > optimizes tail calls. Once in a long while, I'll find a > tail-recursive version of a function to be easier to read than the > iterative version (mind you, this is quite infrequent). In those > cases, I'm glad to know how to ensure that my implementation will > optimize it correctly.
So long as you don't mind your code blowing up in exciting ways when you port it, I guess.
> So long as you don't mind your code blowing up in exciting ways when > you port it, I guess.
Is there a portable way to determine whether you have a tail-recursive function or one that allocates a new stack frame for each recursion? Or is this intended to be a true, i.e., completely transparent, optimization that is only semi-determinable by crashes? It would be nice if there were a portably implemented at best, portably interfaced at least, function that would return the set of optimize declarations that would cause a class of function calls that are statically and portably determinable to merit tail-recursive calls.
Allegro CL's features is known as compiler:tail-call-self-merge-switch and it is easy to see when it is true.
Erik Naggum <e...@naggum.net> writes: > * Tim Bradshaw <t...@cley.com> > > So long as you don't mind your code blowing up in exciting ways when > > you port it, I guess.
> Is there a portable way to determine whether you have a tail-recursive > function or one that allocates a new stack frame for each recursion? Or > is this intended to be a true, i.e., completely transparent, optimization > that is only semi-determinable by crashes? It would be nice if there > were a portably implemented at best, portably interfaced at least, > function that would return the set of optimize declarations that would > cause a class of function calls that are statically and portably > determinable to merit tail-recursive calls.
At the risk of sounding like a broken record, please do `join' the common-lisp-utilities process[1]. I suppose (still having failed to check my reference library) that this is the kind of thing that was being referred to in the CLtL2 environment functionality that didn't make it into the specification.
Christophe
[1] Yeech. That sounds all bureaucratic. Basically, there are three stages: "It would be nice"; "Here's a reference implementation"; "Here's a reference implementation and specification". Community standards, you know you like them... of course, this particular "it would be nice" is of the more introspective nature, and so might involve grovelling in the internals of implementations. -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar)
