Like Jeff M, I'm working my way through Paul Graham's ANSI Common
LISP. One of the exercises asks the reader to write a (recursive)
function that takes a positive integer and prints that many dots.
I want to use a tail-recursive function with an accumulator parameter,
but don't want to expose the accumulator argument - it's a hack and
not part of how the function should be called. The best I could come
up with is below. Two questions:
1) Is there a way to avoid naming a recursive function in this
situation? It seems a waste of a name to name a function that will
only be called once (not counting the recursive call)
2) Am I wrong trying to hide the implementation details, coming as I
am form a non-lisp background? Is it common in this situation in
lisp to just define the global function to have two arguments and
document that the second argument sould not be normally used?
Should an optional default parameter be used instead?
(defun dots (n)
(labels
((dots-local (n accum)
(if (eq 0 n)
accum
(dots-local (- n 1)
(concatenate 'string accum ".")))))
(dots-local n "")))
Ari.
--
Elections only count as free and trials as fair if you can lose money
betting on the outcome.
K. Ari Krupnikov wrote:
> Like Jeff M, I'm working my way through Paul Graham's ANSI Common
> LISP. One of the exercises asks the reader to write a (recursive)
> function that takes a positive integer and prints that many dots.
>
> I want to use a tail-recursive function with an accumulator parameter,
> but don't want to expose the accumulator argument - it's a hack and
> not part of how the function should be called. The best I could come
> up with is below. Two questions:
>
> 1) Is there a way to avoid naming a recursive function in this
> situation? It seems a waste of a name to name a function that will
> only be called once (not counting the recursive call)
>
There is a way, but it's not pretty (or practical):
(defun dots (n)
(funcall ((lambda (F)
((lambda (future)
(funcall F #'(lambda (&rest args)
(apply (funcall future future) args))))
#'(lambda (future)
(funcall F #'(lambda (&rest args)
(apply (funcall future future)
args)))) ))
#'(lambda (recur)
#'(lambda (n accum)
(if (zerop n)
accum
(funcall recur (1- n)
(concatenate 'string "." accum)))) ))
n ""))
This mess is derived from a theoretical idea known as the (applicative
order) Y-combinator. In a nutshell, the function Y can be used to
generate anonymous recursive functions:
(defun Y (F)
((lambda (future)
(funcall F #'(lambda (arg)
(funcall (funcall future future) arg))))
#'(lambda (future)
(funcall F #'(lambda (arg)
(funcall (funcall future future) arg)))) ) )
The function Y is a function-making function. The functions it produces
don't know their own names (they don't have names), but they know how to
make copies of themselves to perform recursive computations. For
example, this function finds the length of a list:
(setf (symbol-function 'len)
(Y #'(lambda (recur)
#'(lambda (l)
(if (null l)
0
(1+ (funcall recur (cdr l)))) ))))
(len '(a b c)) => 3
It gets a little trickier if the function must take multiple args:
(defun Y2 (F)
((lambda (future)
(funcall F #'(lambda (&rest args)
(apply (funcall future future) args))))
#'(lambda (future)
(funcall F #'(lambda (&rest args)
(apply (funcall future future) args)))) ) )
In my DOTS function above I simply embedded this Y2 function rather than
calling it separately and storing its result.
> 2) Am I wrong trying to hide the implementation details, coming as I
> am form a non-lisp background? Is it common in this situation in
> lisp to just define the global function to have two arguments and
> document that the second argument sould not be normally used?
> Should an optional default parameter be used instead?
>
> (defun dots (n)
> (labels
> ((dots-local (n accum)
> (if (eq 0 n)
> accum
> (dots-local (- n 1)
> (concatenate 'string accum ".")))))
> (dots-local n "")))
Your solution here is perfectly reasonable. You present a certain
interface to the outside and hide the details inside the LABELS form.
Another approach would be to create a package and define the two
functions separately. You would then only export the DOTS function. The
auxiliary function would remain internal:
(defpackage dots (:use common-lisp) (:export "DOTS"))
(in-package dots)
(defun dots (n)
(dots-aux n ""))
(defun dots-aux (n accum)
(if (zerop n)
accum
(dots-aux (1- n)
(concatenate 'string accum "."))))
Now the rest of your code can do this:
(use-package 'dots)
(dots 3) => "..."
The function DOTS-AUX is only accessible outside the package as
DOTS::DOTS-AUX, which warns you that it should not be used that way.
Defining the functions separately this way makes it easier to debug. You
can't use TRACE on functions defined in LABELS.
Also it's a better idea to test for numerical equality using the
predicate '=':
(= n 0)
or use ZEROP as I have. EQ doesn't work on numbers of different types,
e.g., (eq 1 1.0), and may not work on bignums or floats.
David Sletten
David Sletten <·····@slytobias.com> writes:
> K. Ari Krupnikov wrote:
>
> > 1) Is there a way to avoid naming a recursive function in this
> > situation? It seems a waste of a name to name a function that will
> > only be called once (not counting the recursive call)
> >
>
> There is a way, but it's not pretty (or practical):
Yeah. I can see how it is both.
> > 2) Am I wrong trying to hide the implementation details, coming as I
> > am form a non-lisp background? Is it common in this situation in
> > lisp to just define the global function to have two arguments and
> > document that the second argument sould not be normally used?
> > Should an optional default parameter be used instead?
>
> Your solution here is perfectly reasonable. You present a certain
> interface to the outside and hide the details inside the LABELS
> form. Another approach would be to create a package and define the two
> functions separately. You would then only export the DOTS
> function. The auxiliary function would remain internal:
>
> The function DOTS-AUX is only accessible outside the package as
> DOTS::DOTS-AUX, which warns you that it should not be used that way.
Again, maybe it's my non-lisp background, but a slight difficulty I see
with this approach is that when one is reading the code, there is
nothing in the definition for DOTS-AUX to suggest that it is an
implementation detail -- one would have to look at the :EXPORT to know
if it was. Or is -AUX a conventional suffix for "private" functions?
> Defining the functions separately this way makes it easier to
> debug. You can't use TRACE on functions defined in LABELS.
Point taken.
> Also it's a better idea to test for numerical equality using the
> predicate '=':
> (= n 0)
> or use ZEROP as I have. EQ doesn't work on numbers of different types,
> e.g., (eq 1 1.0), and may not work on bignums or floats.
Thanks, I'm having a blast trying to memorize the different equality
predicates in CL.
Ari.
--
Elections only count as free and trials as fair if you can lose money
betting on the outcome.
···@lib.aero (K. Ari Krupnikov) writes:
>> Also it's a better idea to test for numerical equality using the
>> predicate '=': (= n 0) or use ZEROP as I have. EQ doesn't work on
>> numbers of different types, e.g., (eq 1 1.0), and may not work on
>> bignums or floats.
>
> Thanks, I'm having a blast trying to memorize the different equality
> predicates in CL.
You can make your life a bit easier by just forgetting about EQ. For
user-level (i.e. not implementing Lisp itself) there is no reason to
ever use EQ instead of EQL. If you insist on using EQ you should think
of it as "like EQL but can't ever be used with values that might be
numbers or characters".
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> ···@lib.aero (K. Ari Krupnikov) writes:
>
> >> Also it's a better idea to test for numerical equality using the
> >> predicate '=': (= n 0) or use ZEROP as I have. EQ doesn't work on
> >> numbers of different types, e.g., (eq 1 1.0), and may not work on
> >> bignums or floats.
> >
> > Thanks, I'm having a blast trying to memorize the different equality
> > predicates in CL.
>
> You can make your life a bit easier by just forgetting about EQ. For
> user-level (i.e. not implementing Lisp itself) there is no reason to
> ever use EQ instead of EQL. If you insist on using EQ you should think
> of it as "like EQL but can't ever be used with values that might be
> numbers or characters".
And otherwise, the longer the name, the easier it is to be equal.
eql = the same
equal = the same attributes
equalp = about the same attributes
#1="Hello" is the same as #1#, they're eql.
"Hello" has the same characters as (copy-seq "Hello"), they're equal
(string=), but their not eql.
"Hello" is not the same than "HELLO", but they're equalp (string-equal).
And similar examples for the other types.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
K. Ari Krupnikov wrote:
>>
>>The function DOTS-AUX is only accessible outside the package as
>>DOTS::DOTS-AUX, which warns you that it should not be used that way.
>
>
> Again, maybe it's my non-lisp background, but a slight difficulty I see
> with this approach is that when one is reading the code, there is
> nothing in the definition for DOTS-AUX to suggest that it is an
> implementation detail -- one would have to look at the :EXPORT to know
> if it was. Or is -AUX a conventional suffix for "private" functions?
>
>
Based on my (limited) experience, I would say that the use of AUX as a
suffix for a helper function is not necessarily widespread and certainly
does not imply a private function. I think I picked it up from
Winston/Horn's Lisp book.
From what I understand, Lisp doesn't provide the same sort of
encapsulation as Java for instance. Packages can be used to control
namespace access as long as conventions are respected. Namely, an
internal symbol from another package, e.g., DOTS::DOTS-AUX, should not
be accessed directly even though it CAN be accessed directly--the
language doesn't stop you. Once a symbol is exported it can be accessed
as DOTS:DOTS, or once you USE a package it can be accessed simply as
DOTS. So I guess the answer is, yes, you need to look at the :EXPORT to
see what is legitimately available.
>>Also it's a better idea to test for numerical equality using the
>>predicate '=':
>>(= n 0)
>>or use ZEROP as I have. EQ doesn't work on numbers of different types,
>>e.g., (eq 1 1.0), and may not work on bignums or floats.
>
>
> Thanks, I'm having a blast trying to memorize the different equality
> predicates in CL.
>
All of the equality predicates can be tricky at first, but they're not
so bad if you keep a few things in mind. First, there are type-specific
and generic predicates. The generic predicates essentially become more
liberal as their names get longer: EQ -> EQL -> EQUAL -> EQUALP
EQ tests for identical objects in memory. This is the simplest (and most
efficient) test, but it usually isn't what you want. Since symbols have
a unique representation in a package testing whether two symbols are
equal, i.e., whether two things refer to the identical symbol, is
usually where you would use EQ.
EQL is similar to EQ, but it is guaranteed to return T for characters,
floats, and bignums, which may have distinct representations. EQL is
also the default equality predicate for most Lisp operators such as
MEMBER, ASSOC, etc...
EQUAL basically says that things which print the same are equal. And
EQUALP extends EQUAL to disregard case-sensitivity and different numeric
types:
(eq '(a b c) '(a b c)) => NIL
(equal '(a b c) '(a b c)) => T
(equal 1 1.0) => NIL
(equalp 1 1.0) => T
(equal #\a #\A) => NIL
(equalp #\a #\A) => T
On the other hand, frequently you don't want to use the generic
predicates. You have numeric predicates: =, /=, <, <=, >, >=. These are
generally cooler than in other languages in that they accept multiple
arguments:
(< 1 2 3 4 5) => T
(<= 3 3 4 5) => T
There are also character and string predicates which come in two
flavors--case-sensitive and case-insensitive:
(string= "pung" "Pung") => NIL
(string-equal "pung" "Pung") => T
(char< #\a #\B) => NIL
(char-lessp #\a #\B) => T
David Sletten
K. Ari Krupnikov wrote:
>
> Again, maybe it's my non-lisp background, but a slight difficulty I
see
> with this approach is that when one is reading the code, there is
> nothing in the definition for DOTS-AUX to suggest that it is an
> implementation detail -- one would have to look at the :EXPORT to
know
> if it was. Or is -AUX a conventional suffix for "private" functions?
I think it's not a standard convention. There are several
semi-standard conventions which you see: another one is the use of a
trailing `1' ir `-1' as in:
FOO: do something
FOO-1: helper for FOO
However, I think it is just *fine* to define a local function for this
sort of thing. In my own code I almost always do this: if I have a
bunch of functions which are only ever called from one place and which
I may also want to skimp on (because I know they will only ever be
called from one place, so I can be very lazy about argument
conventions for instance), then I very frequently define them as local
functions. Even more so if they need to share state, of course.
>
> > Defining the functions separately this way makes it easier to
> > debug. You can't use TRACE on functions defined in LABELS.
>
> Point taken.
Well, of course, many high-quality implementations *do* allow tracing
of local functions. I'm fairly sure that at least ACL and LispWorks
do.
--tim
···@lib.aero (K. Ari Krupnikov) wrote:
> Like Jeff M, I'm working my way through Paul Graham's ANSI Common
> LISP. One of the exercises asks the reader to write a (recursive)
> function that takes a positive integer and prints that many dots.
> I want to use a tail-recursive function with an accumulator parameter,
> but don't want to expose the accumulator argument - it's a hack and
> not part of how the function should be called. The best I could come
> up with is below. Two questions:
why do you want to use an accumulator? A simple solution would be this:
(defun dots (n) (when (> n 0) (princ ".") (dots (1- n))))
(defun dots-string (n)
(if (= n 0) "" (concatenate 'string "." (dots-string (1- n)))))
Of course, you don't need a recursion or loop at all :-)
(defun dots (n) (make-sequence 'string n :initial-element #\.))
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> why do you want to use an accumulator? A simple solution would be this:
>
> (defun dots-string (n)
> (if (= n 0) "" (concatenate 'string "." (dots-string (1- n)))))
Because the object of the exercise was to learn the LISP idiom for
tail recursion, not to get a string of dots :=)
> Of course, you don't need a recursion or loop at all :-)
>
> (defun dots (n) (make-sequence 'string n :initial-element #\.))
But I appreciate your pointing this out.
Thanks for everyone who replied, especially about equality predicates.
Ari.
--
Elections only count as free and trials as fair if you can lose money
betting on the outcome.
···@lib.aero (K. Ari Krupnikov) writes:
> Like Jeff M, I'm working my way through Paul Graham's ANSI Common
> LISP. One of the exercises asks the reader to write a (recursive)
> function that takes a positive integer and prints that many dots.
>
> I want to use a tail-recursive function with an accumulator parameter,
> but don't want to expose the accumulator argument
In this case (you accumultate to string):
(defun dots (n)
(with-output-to-string (s)
(labels ((dots-local (n)
(when (zerop n)
(return-from dots-local))
(princ "." s)
(dots-local (1- n))))
(dots-local n))))
> - it's a hack and
> not part of how the function should be called. The best I could come
> up with is below. Two questions:
>
> 1) Is there a way to avoid naming a recursive function in this
> situation?
No. Google for 'The Why of Y' by Richard P. Gabriel. Nice article.
One thing you can do is use three LAMBDAs instead of LABELS...
...or use iteration:
(defun dots (n) ; (make-string n :initial-element #\.)
(with-output-to-string (s)
(loop repeat n do (princ "." s))))
> It seems a waste of a name to name a function that will
> only be called once (not counting the recursive call)
>
> 2) Am I wrong trying to hide the implementation details, coming as I
> am form a non-lisp background?
I don't know, I'm newbie (1y) too.
> Is it common in this situation in lisp to just define the global
> function to have two arguments and document that the second argument
> sould not be normally used? Should an optional default parameter be
> used instead?
>
> (defun dots (n)
> (labels
> ((dots-local (n accum)
> (if (eq 0 n)
(zerop n)
> accum
> (dots-local (- n 1)
(1- n)
> (concatenate 'string accum ".")))))
> (dots-local n "")))
Regards, Szymon
Szymon <···@bar.baz> writes:
> No. Google for 'The Why of Y' by Richard P. Gabriel. Nice article.
>
> One thing you can do is use three LAMBDAs instead of LABELS...
You can wrote anaphoric macro and use it. Search for 'alambda'.
(message (Hello 'K.)
(you :wrote :on '(08 Oct 2004 23:25:32 -0700))
(
KAK> 2) Am I wrong trying to hide the implementation details, coming as
KAK> I am form a non-lisp background? Is it common in this situation
KAK> in lisp to just define the global function to have two arguments
KAK> and document that the second argument sould not be normally
KAK> used?
KAK> Should an optional default parameter be used instead?
i use optional params in such situations and had no problems with them so
far 8-]
maybe it's wrong if you're doing library or part of some big project, but if
you're working with that function internally it's ok, i think..
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))
···@lib.aero (K. Ari Krupnikov) writes:
> 1) Is there a way to avoid naming a recursive function in this
> situation? It seems a waste of a name to name a function that will
> only be called once (not counting the recursive call)
>
> (defun dots (n)
> (labels
> ((dots-local (n accum)
> (if (eq 0 n)
> accum
> (dots-local (- n 1)
> (concatenate 'string accum ".")))))
> (dots-local n "")))
Well since it's not called twice, you could as well name it with an
anonymous symbol:
(defun dots (n)
(labels
((#1=#:anonymous (n accum)
(if (eq 0 n)
accum
(dots-local (- n 1)
(concatenate 'string accum ".")))))
(#1# n "")))
(Just to get silly, sorry).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
Pascal Bourguignon <····@mouse-potato.com> writes:
> ···@lib.aero (K. Ari Krupnikov) writes:
> > 1) Is there a way to avoid naming a recursive function in this
> > situation? It seems a waste of a name to name a function that will
> > only be called once (not counting the recursive call)
> >
> > (defun dots (n)
> > (labels
> > ((dots-local (n accum)
> > (if (eq 0 n)
> > accum
> > (dots-local (- n 1)
> > (concatenate 'string accum ".")))))
> > (dots-local n "")))
>
> Well since it's not called twice, you could as well name it with an
> anonymous symbol:
>
> (defun dots (n)
> (labels
> ((#1=#:anonymous (n accum)
> (if (eq 0 n)
> accum
> (dots-local (- n 1)
> (concatenate 'string accum ".")))))
> (#1# n "")))
>
>
>
> (Just to get silly, sorry).
I guess yes, I was looking for something like this. Now that you've
shown it to me, I don't know which one's worse, my original or this :=)
Ari.
--
Elections only count as free and trials as fair if you can lose money
betting on the outcome.