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:
(defun my-length (lst)
(let cnt ((len 0))
(if (null lst)
len
(progn (setf lst (cdr lst))
(cnt (+ 1 len))))))
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 <····@underlevel.net> | Mind the gap
In article <··············@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:
>
>(defun my-length (lst)
> (let cnt ((len 0))
^^^^^^^
Bad syntax here. You want
(let (cnt (len 0))
> (if (null lst)
> len
> (progn (setf lst (cdr lst))
> (cnt (+ 1 len))))))
^^^^^^
This is still a problem, because cnt is not a function.
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:
(defun my-length (lst)
(if (null lst)
0
(1+ (my-length (rest lst)))))
>I realize the best way to do this would be a tail-recursive function
>using `do' but that's not the point.
You mean either recursion, or iteration with do?
···@ashi.footprints.net (Kaz Kylheku) writes:
> In article <··············@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:
> >
> >(defun my-length (lst)
> > (let cnt ((len 0))
>
> ^^^^^^^
> Bad syntax here. You want
>
> (let (cnt (len 0))
>
>
> > (if (null lst)
> > len
> > (progn (setf lst (cdr lst))
> > (cnt (+ 1 len))))))
> ^^^^^^
>
> This is still a problem, because cnt is not a function.
I mistakingly thought that named leti is the same in Scheme and CL.
In Scheme it's valid to write:
(define (my-length (lst)
(let cnt ((len 0))
(if (null? lst)
len
(begin (set! lst (cdr lst))
(cnt (+ 1 len)))))))
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:
>
> (defun my-length (lst)
> (if (null lst)
> 0
> (1+ (my-length (rest lst)))))
>
> >I realize the best way to do this would be a tail-recursive function
> >using `do' but that's not the point.
^^^^ I meant dolist
> You mean either recursion, or iteration with do?
An iterative version, as in:
(defun my-length (lst)
(let ((len 0))
(dolist (elem lst)
(setf len (1+ len)))
len))
--
Jordan Katz <····@underlevel.net> | Mind the gap
Jordan Katz <····@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:
>
> (defun my-length (lst)
> (let cnt ((len 0))
> (if (null lst)
> len
> (progn (setf lst (cdr lst))
> (cnt (+ 1 len))))))
>
> 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:
(defun my-length (list)
(flet ((count-length (list length-so-far)
(if (null list)
length-so-far
(count-length (cdr length) (1+ length-so-far)))))
(count-length list 0)))
> 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.
>
> (defun my-length (list)
> (flet ((count-length (list length-so-far)
> (if (null list)
> length-so-far
> (count-length (cdr length) (1+ length-so-far)))))
> (count-length list 0)))
could it be that you have had a bad day? The above code does not work
what is (cdr length)? And what about the usage for flet?
So here's a hopefully working version:
(defun my-length (list)
(labels ((count-length
(list length-so-far)
(if (null list)
length-so-far
(count-length (cdr list) (1+ length-so-far)))))
(count-length list 0)))
Regards
Friedrich
"Friedrich Dominicus" <·····@q-software-solutions.com> writes:
> > (defun my-length (list)
> > (flet ((count-length (list length-so-far)
> > (if (null list)
> > length-so-far
> > (count-length (cdr length) (1+ length-so-far)))))
> > (count-length list 0)))
>
> could it be that you have had a bad day? The above code does not work
> what is (cdr length)? And what about the usage for flet?
funny, i had labels in an earlier edit and it got changed. c'est la vie.
thanks for catching it, and the other typo too. sigh.
> So here's a hopefully working version:
> (defun my-length (list)
> (labels ((count-length
> (list length-so-far)
> (if (null list)
> length-so-far
> (count-length (cdr list) (1+ length-so-far)))))
> (count-length list 0)))
Kent M Pitman <······@world.std.com> writes:
> 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.
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > 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.
* 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.
--tim
* Tim Bradshaw <···@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.
Allegro CL's features is known as compiler:tail-call-self-merge-switch
and it is easy to see when it is true.
#:Erik
--
Travel is a meat thing.
Erik Naggum <····@naggum.net> writes:
> * Tim Bradshaw <···@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)
Jordan Katz <····@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:
>
> (defun my-length (lst)
> (let cnt ((len 0))
> (if (null lst)
> len
> (progn (setf lst (cdr lst))
> (cnt (+ 1 len))))))
>
> 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
(defmacro named-let (name bindings &body forms)
`(labels ((,name ,(mapcar #'first bindings)
,@forms))
(,name ,@(mapcar #'second bindings))))
Hence your code becomes
(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'.
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Jordan Katz <····@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:
> >
> > (defun my-length (lst)
> > (let cnt ((len 0))
> > (if (null lst)
> > len
> > (progn (setf lst (cdr lst))
> > (cnt (+ 1 len))))))
> >
> > 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
>
> (defmacro named-let (name bindings &body forms)
> `(labels ((,name ,(mapcar #'first bindings)
> ,@forms))
> (,name ,@(mapcar #'second bindings))))
>
> Hence your code becomes
>
> (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'.