I'm a newbie trying to teach himself CL by working through the
beginner's books and coming up with silly little problems to use as
coding challenges to develop my CL instincts.
So here's a silly problem that I thought would make a good excuse to
write some code: how many multiples of either 3 or 7 are there between
1 and n?
In the imperative languages I'm used to, the approach (putting aside
any direct algorithms) would be something like (in pseudocode)
foreach i in (1..n)
if (multiple(i,3) or multiple(i,7)) count++
So, I thought I'd try a recursive approach in Lisp.
Not having any real instincts for how to approach problems
recursively, I thought I'd start with some definitions, like:
; is x a multiple of n?
(defun multp (x n)
(zerop (mod x n)))
; if a multiple of 3 or 7, return 1, else 0
(defun incr37 (x)
(if (or (multp x 3) (multp x 7)) 1
0))
That worked, and gave me something I could use to increment a counter.
If I were then to go iteratively, I would just add up all the "(incr37
x)" for all x's from 1 to n. I believe that's a perfectly acceptable
approach in CL, but I'm trying to expand my horizons by doing it
recursively to develop recursive "instincts" as well.
In order to keep it from overflowing the stack, I wanted to make it
tail recursive. The beginners' books (Touretzky & Graham) usually seem
to break up f(x) into two functions, the f(x) and a helper that takes
two arguments, x and a counter. f(x) calls its helper with arguments x
and 0, then the helper passes the count as an argument to make it
unnecessary for the function to return. At least that's my impression
of what's going on.
So I wrote it this way
; recursive counter, i.e., the helper function
(defun m37-a (x n)
(if (zerop x) n
(m37-a (- x 1) (+ n (incr37 x)))))
; call the counter (m37 means "multiples of 3 or 7")
(defun m37 (x)
(m37-a x 0))
This works. When I input
> (m37 21) => 9 (correct)
> (m37 2100) => 900 (correct
but
> (m37 21000) => stack overflow!
I get a stack overflow using CLISP on WinXP (Cygwin).
I'm pretty shaky on how you write functions to make them tail
recursive, so I don't understand why this fails. I'm not wondering how
to allocate more memory to CLISP, I'm wondering why the stack for (m37
21000) would need to be any bigger than the stack for (m37 2100). If
this were properly tail recursive, (m37 21billion) ought to work just
fine, with time being the only limitation.
Any recommendations regarding what I'm doing wrong and what the rules
are for writing properly tail recursive algorithms would be
appreciated.
Thanks.
········@hotmail.com (Tuang) writes:
> I'm a newbie trying to teach himself CL by working through the
> beginner's books and coming up with silly little problems to use as
> coding challenges to develop my CL instincts.
>
> So here's a silly problem that I thought would make a good excuse to
> write some code: how many multiples of either 3 or 7 are there between
> 1 and n?
>
> In the imperative languages I'm used to, the approach (putting aside
> any direct algorithms) would be something like (in pseudocode)
>
>
> So, I thought I'd try a recursive approach in Lisp.
While it may be instructive and interesting to play around with
recursion and tail recursion, in my opinion it is quite bad practice
to use recursion as an iteration construct. There are recursive
problems where a recursive solution is appropriate, but in such cases
you will not need to worry about tail-recursion. A typical example of
this is quick-sort, where the maximum stack depth is O(log2 N).
The exact definition of when tail-recursion is possible is quite
difficult to pin down, especially when taking dynamically scoped
mechanisms into account (dynamic bindings, unwind-protect, and so
on). And, not to forget, the ANSI CL standard does not require
tail-call merging in any circumstance (unlike Scheme). So if you rely
on tail-call merging, you rely on implementation-specific details.
> foreach i in (1..n)
> if (multiple(i,3) or multiple(i,7)) count++
In Common Lisp, this is preferrably expressed like so:
(loop for i from 1 to n
counting (or (multiple i 3) (multiple i 7)))
> Not having any real instincts for how to approach problems
> recursively, I thought I'd start with some definitions, like:
>
> ; is x a multiple of n?
> (defun multp (x n)
> (zerop (mod x n)))
The typical way to go (when recursion for some reason is preferred)
from this is like so:
(defun count37 (n)
(cond
((zerop n) 0)
((or (multiple n 3)
(multiple n 7))
(1+ (count37 (1- n))))
(t (count37 (1- n)))))
This function has one tail-recursive path (the third, default clause)
and one path that is not tail-recursive (the second clause). That's
not quite good enough, and we employ the standard re-writing rule you
mentioned to convert the function to be fully tail-recursive:
(defun count37 (n count)
(cond
((zerop n) count)
((or (multiple n 3)
(multiple n 7))
(count37 (1- n) (1+ count)))
(t (count37 (1- n) count))))
Now both paths are tail-recursive. But, again, remember that no
implementation is required by the standard to actually merge the
tail-recursive calls. And do compare the readability of the above to
that of the loop version above (and we have yet to hide the
initialization of the counter to zero).
> (defun m37-a (x n)
> (if (zerop x) n
> (m37-a (- x 1) (+ n (incr37 x)))))
This is in fact tail-recursive so far as I can tell. My guess is that
you simply have not compiled m37-a, and that CLISP's evaluator (of
uncompiled code) doesn't implement tail-call merging (another case
against relying on this feature). And did I mention that even CLISP's
compiler is not obliged to provide tail-call merging?
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> wrote in message news:<··············@vserver.cs.uit.no>...
> ········@hotmail.com (Tuang) writes:
>
> > I'm a newbie trying to teach himself CL by working through the
> > beginner's books and coming up with silly little problems to use as
> > coding challenges to develop my CL instincts.
> >
> > So here's a silly problem that I thought would make a good excuse to
> > write some code: how many multiples of either 3 or 7 are there between
> > 1 and n?
> >
> > In the imperative languages I'm used to, the approach (putting aside
> > any direct algorithms) would be something like (in pseudocode)
> >
> >
> > So, I thought I'd try a recursive approach in Lisp.
>
> While it may be instructive and interesting to play around with
> recursion and tail recursion, in my opinion it is quite bad practice
> to use recursion as an iteration construct.
That appears to be a somewhat controversial position among users of
functional-leaning languages, but thanks for bringing it up. I don't
know enough yet to have an opinion of my own, but this sounds
reasonable to me.
I need more practice with recursive techniques, and recursion over a
flat (non-nested) structure is a good stepping stone to recursion over
real trees, but I'll keep your advice in mind for real work.
> There are recursive
> problems where a recursive solution is appropriate, but in such cases
> you will not need to worry about tail-recursion.
Why is that? Are real-world recursion problems very unlikely to
overflow the stack or have performance problems that tail-call
optimization would help with significantly?
> A typical example of
> this is quick-sort, where the maximum stack depth is O(log2 N).
Is it generally the case that in real-world problems that are
appropriate for recursion that tail-call optimization doesn't matter
much and that problems where such optimization would matter aren't
appropriate for recursion?
> The exact definition of when tail-recursion is possible is quite
> difficult to pin down, especially when taking dynamically scoped
> mechanisms into account (dynamic bindings, unwind-protect, and so
> on). And, not to forget, the ANSI CL standard does not require
> tail-call merging in any circumstance (unlike Scheme). So if you rely
> on tail-call merging, you rely on implementation-specific details.
I was under the impression that even though CL doesn't require
tail-call optimization, that all major implementations did it because
it was so fundamental to supporting a functional programming style.
>
> > foreach i in (1..n)
> > if (multiple(i,3) or multiple(i,7)) count++
>
> In Common Lisp, this is preferrably expressed like so:
>
> (loop for i from 1 to n
> counting (or (multiple i 3) (multiple i 7)))
Thanks! The beginners' books don't get to simple iteration until after
recursion, so I'm not even there yet. This is the first time I've seen
this pattern, but it already feels as comfortable as an old shoe. ;-)
> [other useful comments...]
>
> > (defun m37-a (x n)
> > (if (zerop x) n
> > (m37-a (- x 1) (+ n (incr37 x)))))
>
> This is in fact tail-recursive so far as I can tell. My guess is that
> you simply have not compiled m37-a, and that CLISP's evaluator (of
> uncompiled code) doesn't implement tail-call merging (another case
> against relying on this feature). And did I mention that even CLISP's
> compiler is not obliged to provide tail-call merging?
Yes, I believe you mentioned that. ;-)
CLISP is the only free Lisp for Win32 that's even close to real CL
that I've found so far. (Yes, I'm aware of the demo versions with
their carrot and stick features, but I'm hoping it won't have to come
to that.)
CLISP doesn't have a compiler, AFAIK, but I was thinking that, given
the dearth of competitors on Windows, it was probably one of the
"major CL implementations" that I've heard "all provide tail-call
optimization", even though the standard doesn't actually require it.
Thanks for all the tips.
········@hotmail.com (Tuang) writes:
>> There are recursive problems where a recursive solution is
>> appropriate, but in such cases you will not need to worry about
>> tail-recursion.
Most problems that are recursive along one branch can be easily turned
into an iteration, while most problems that are recursive along more
than one branch grow very slowly.
> Why is that? Are real-world recursion problems very unlikely to
> overflow the stack or have performance problems that tail-call
> optimization would help with significantly?
Tail-call optimization does not have a great impact upon performance.
It does, however, enable more programs to run.
>> A typical example of
>> this is quick-sort, where the maximum stack depth is O(log2 N).
>
> Is it generally the case that in real-world problems that are
> appropriate for recursion that tail-call optimization doesn't matter
> much and that problems where such optimization would matter aren't
> appropriate for recursion?
>
>> The exact definition of when tail-recursion is possible is quite
>> difficult to pin down, especially when taking dynamically scoped
>> mechanisms into account (dynamic bindings, unwind-protect, and so
>> on). And, not to forget, the ANSI CL standard does not require
>> tail-call merging in any circumstance (unlike Scheme). So if you rely
>> on tail-call merging, you rely on implementation-specific details.
>
> I was under the impression that even though CL doesn't require
> tail-call optimization, that all major implementations did it because
> it was so fundamental to supporting a functional programming style.
Allegro CL will do it with the appropriate declarations.
Xanalys will do it with the appropriate declarations.
Corman Common Lisp will *not* do tail-call optimization.
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
>> While it may be instructive and interesting to play around with
>> recursion and tail recursion, in my opinion it is quite bad practice
>> to use recursion as an iteration construct.
········@hotmail.com (Tuang) writes:
> That appears to be a somewhat controversial position among users of
> functional-leaning languages, but thanks for bringing it up. I don't
> know enough yet to have an opinion of my own, but this sounds
> reasonable to me.
You are right that it is probably somewhat controversial.
>> There are recursive problems where a recursive solution is
>> appropriate, but in such cases you will not need to worry about
>> tail-recursion.
>
> Why is that? Are real-world recursion problems very unlikely to
> overflow the stack or have performance problems that tail-call
> optimization would help with significantly?
I believe so, for problems that are naturally recursive, like
divide-and-conquer algorithms. Iterating over a list does not fall
into this category, even if it is possible to do this (tail)
recursively by subtract-and-conquer.
>> A typical example of this is quick-sort, where the maximum stack
>> depth is O(log2 N).
>
> Is it generally the case that in real-world problems that are
> appropriate for recursion that tail-call optimization doesn't matter
> much and that problems where such optimization would matter aren't
> appropriate for recursion?
Well, at least I would be genuinely interested to see a real-world
counter-exaple.
> I was under the impression that even though CL doesn't require
> tail-call optimization, that all major implementations did it
> because it was so fundamental to supporting a functional programming
> style.
While tail-call merging is arguably a part of lisp tradition, so is
the concept of having an symbolic interpreter (eval) that is
equivalent to running compiled code.
In general I think that "functional programming style" is a concept
that is often misunderstood, infusing irrational fear of certain
"dirty", non-functional constructs. Obsessive use of recursion is part
of this. A parallel example is the massive over-use of "object
orientation" in technologies like Java. But I'm digressing.
I mostly use Allegro CL, which does implement tail-call merging. I
know this, because every so often I try to debug or trace a recursive
function and find it doesn't quite work the way I expect because it's
been tail-call merged. It's just an annoyance, and presumably it can
be turned off, but so far I haven't bothered to look it up.
> CLISP is the only free Lisp for Win32 that's even close to real CL
> that I've found so far. (Yes, I'm aware of the demo versions with
> their carrot and stick features, but I'm hoping it won't have to
> come to that.)
Hm.. do you also need a rant against irrational fear of commercial
software? :-) Anyways, I believe Corman Lisp provides a rather
unrestricted free version (and a quite affordable non-free version,
too).
Actually, I did check that CLisp's compiler indeed does provide
tail-call merging. Every compliant implementation must implement some
form or another of the compiler. It's called "minimal compilation" in
the standard, I believe.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> wrote in message news:<··············@vserver.cs.uit.no>...
> ········@hotmail.com (Tuang) writes:
> > CLISP is the only free Lisp for Win32 that's even close to real CL
> > that I've found so far. (Yes, I'm aware of the demo versions with
> > their carrot and stick features, but I'm hoping it won't have to
> > come to that.)
>
> Hm.. do you also need a rant against irrational fear of commercial
> software? :-)
Most of the dev tools I've used over the years have been commercial,
so I probably don't need the rant, but if it would do your heart good,
feel free (pardon the pun). ;-)
I've been spoiled by great free software tools in recent years, and
the freedom is addictive. I'm willing to sacrifice some features for
the freedom to do what I want with it -- install it on any machine,
upgrade whenever I feel like it, take it with me when I leave a job,
etc., all without paying anything. I'm not one of those with a moral
objection to commercial software. It's just a practical preference.
The "features" in the free versions of commercial products that are
designed to annoy me until I give up and pay for the unrestricted
product are...annoying.
I still use some commercial software products, but fewer and fewer
every year as I find viable open source replacements. I'm probably not
an exceptional case, and I suspect that the future of most
less-commonly-used programming languages will be determined to some
extent by the quality of their open source implementations.
> Anyways, I believe Corman Lisp provides a rather
> unrestricted free version (and a quite affordable non-free version,
> too).
Thanks for the tip. I don't hear about Corman as often as others.
> Actually, I did check that CLisp's compiler indeed does provide
> tail-call merging. Every compliant implementation must implement some
> form or another of the compiler. It's called "minimal compilation" in
> the standard, I believe.
Hmm. Then I wonder why my function was overflowing the stack. Maybe,
as you suggested, there is some difference between the way it works
when interacting with the toplevel and when it is running in some
other form. (Perhaps compiled bytecode, if you can save chunks of
compiled bytecode. I don't know yet. I've just installed it and 2/3rds
of the docs may as well be written in Greek, so it will take a while
before I understand it.)
········@hotmail.com (Tuang) writes:
> Then I wonder why my function was overflowing the stack.
Well, did you do (compile 'my-function)? It also works to do
(compile (defun my-function (...) ...))
because defun returns the function's name.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> ········@hotmail.com (Tuang) writes:
>
>> Is it generally the case that in real-world problems that are
>> appropriate for recursion that tail-call optimization doesn't matter
>> much and that problems where such optimization would matter aren't
>> appropriate for recursion?
>
> Well, at least I would be genuinely interested to see a real-world
> counter-exaple.
Two come to mind. One is a state machine implemented by several
mutually recursive functions. It is possible to implement this as
driver loop and state transition functions, but sometimes it is more
convenient to pass the state around between functions.
The second is continuation-passing-style. It simply won't work on a
non-tail-recursive implementation except for small problems.
"Frode Vatvedt Fjeld" <······@cs.uit.no> wrote in message
···················@vserver.cs.uit.no...
> Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
>
[snip]
> I mostly use Allegro CL, which does implement tail-call merging. I
> know this, because every so often I try to debug or trace a recursive
> function and find it doesn't quite work the way I expect because it's
> been tail-call merged. It's just an annoyance, and presumably it can
> be turned off, but so far I haven't bothered to look it up.
Without altering your optimization settings, I believe want to define such a
function with the following declaration:
(defun foo (x)
(declare (notinline foo)
...)
- R. Scott McIntire
Frode Vatvedt Fjeld <······@cs.uit.no> wrote in message news:<··············@vserver.cs.uit.no>...
> ········@hotmail.com (Tuang) writes:
> >
> > foreach i in (1..n)
> > if (multiple(i,3) or multiple(i,7)) count++
>
> In Common Lisp, this is preferrably expressed like so:
>
> (loop for i from 1 to n
> counting (or (multiple i 3) (multiple i 7)))
>
I tried your suggestion (I may as well experiment with iteration while
I'm at it), as follows, which worked fine:
(defun m37 (n)
(loop for i from 1 to n
counting (or (multiple i 3) (multiple i 7))))
So naturally now I'm wondering how this might be generalized to count
multiples of any list of numbers in any range. This seems like a very
Lispy thing to do, but I can't even guess at the syntax for doing
this:
(defun mult-list (start end nums-list)
(loop for i from start to end
counting (or (multiple i ??) (multiple i ??) (multiple i ??)
...))))
where the '??' are the elements of the list 'nums-list'. There must be
something like mapcar that allows you to insert the elements of a list
into a pattern like this. Then I'd be able to count all the multiples
of 3, 5, or 7 between 1 and 1000 by entering
> (mult-list (1 1000 '(3 5 7)))
What is the proper CL way to write that (defun mult-list....) above?
(It's not that the problem is interesting, of course. It's that Common
Lisp's ability to write its own code is. ;-) )
Thanks.
········@hotmail.com (Tuang) writes:
> Frode Vatvedt Fjeld <······@cs.uit.no> wrote in message news:<··············@vserver.cs.uit.no>...
> > ········@hotmail.com (Tuang) writes:
> > >
> > > foreach i in (1..n)
> > > if (multiple(i,3) or multiple(i,7)) count++
> >
> > In Common Lisp, this is preferrably expressed like so:
> >
> > (loop for i from 1 to n
> > counting (or (multiple i 3) (multiple i 7)))
> >
>
> I tried your suggestion (I may as well experiment with iteration while
> I'm at it), as follows, which worked fine:
>
> (defun m37 (n)
> (loop for i from 1 to n
> counting (or (multiple i 3) (multiple i 7))))
>
>
> So naturally now I'm wondering how this might be generalized to count
> multiples of any list of numbers in any range. This seems like a very
> Lispy thing to do, but I can't even guess at the syntax for doing
> this:
>
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> ...))))
>
>
> where the '??' are the elements of the list 'nums-list'. There must be
> something like mapcar that allows you to insert the elements of a list
> into a pattern like this. Then I'd be able to count all the multiples
> of 3, 5, or 7 between 1 and 1000 by entering
>
> > (mult-list (1 1000 '(3 5 7)))
>
(defun any-multiple-p (num nums-list)
(loop for n in nums-list thereis (multiple num n)))
(defun mult-list (start end nums-list)
(loop for i from start to end
counting (any-multiple-p i nums-list)))
CL-USER(680): (mult-list 1 1000 '(3 5 7))
543
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> (defun any-multiple-p (num nums-list)
> (loop for n in nums-list thereis (multiple num n)))
"thereis"? Damn, LOOP is hilarious. I have decided to go through all my
code and check every do and map and try them in LOOP as a fun way of
learning the beast. After eight years I am convinced.
I just wich there was a good reference with good real-world examples
that covered both the simple and the hairy.
I doubt THEREIS one. :)
kenny
>
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (any-multiple-p i nums-list)))
>
>
> CL-USER(680): (mult-list 1 1000 '(3 5 7))
> 543
>
>
> -Peter
>
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> writes:
> Peter Seibel wrote:
>
> > (defun any-multiple-p (num nums-list)
> > (loop for n in nums-list thereis (multiple num n)))
>
> "thereis"? Damn, LOOP is hilarious. I have decided to go through all
> my code and check every do and map and try them in LOOP as a fun way
> of learning the beast. After eight years I am convinced.
>
> I just wich there was a good reference with good real-world examples
> that covered both the simple and the hairy.
>
> I doubt THEREIS one. :)
Well, this is more along the lines of systematic exposition but you
might find it useful. And if not, I'd welcome your comments as to why:
<http://www.gigamonkeys.com/book/appendix-loop-for-black-belts.html>
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
<·····@javamonkey.com> wrote:
>Well, this is more along the lines of systematic exposition but you
>might find it useful. And if not, I'd welcome your comments as to why:
>
> <http://www.gigamonkeys.com/book/appendix-loop-for-black-belts.html>
One useful detail that I didn't see mentioned in that chapter is the
loop keyword "it". I find that it pops up often in code like
(let ((x ...))
...
(loop for e in list when (foo-bar e x) collect it))
, where foo-bar returns nil on failure and some sort of state object
otherwise. Yes, you could also do it with mapcar and remove but the
loop version is IMHO clearer, especially if you'd end up using a
lambda otherwise.
But then again, when isn't loop the clearest option? ;-)
--
Juho Snellman
······@iki.fi (Juho Snellman) writes:
> <·····@javamonkey.com> wrote:
> >Well, this is more along the lines of systematic exposition but you
> >might find it useful. And if not, I'd welcome your comments as to why:
> >
> > <http://www.gigamonkeys.com/book/appendix-loop-for-black-belts.html>
>
> One useful detail that I didn't see mentioned in that chapter is the
> loop keyword "it". I find that it pops up often in code like
>
> (let ((x ...))
> ...
> (loop for e in list when (foo-bar e x) collect it))
Yup. I forgot that one. Thanks.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> > <·····@javamonkey.com> wrote:
> > >Well, this is more along the lines of systematic exposition but you
> > >might find it useful. And if not, I'd welcome your comments as to why:
> > >
> > > <http://www.gigamonkeys.com/book/appendix-loop-for-black-belts.html>
> >
That did a nice job of decomposing the multitude of loop keywords into
more reasonable-sized chunks. I've gone back to other books here and
they make sense now. :)
I was going to whine about having more examples, but then I looked at
the TOC and was reminded how big this language is. :)
Thanks,
kenny
--
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"[If anyone really has healing powers,] I would like to call
them about my knees."
-- Tenzin Gyatso, the Fourteenth Dalai Lama
>>>>> "KT" == Kenny Tilton <·······@nyc.rr.com> writes:
[...]
KT> I just wich there was a good reference with good real-world
KT> examples that covered both the simple and the hairy. [...]
Just play around with it, how did you learn to walk for heavens sake?
B<just ignore me>M
Bulent Murtezaoglu wrote:
>>>>>>"KT" == Kenny Tilton <·······@nyc.rr.com> writes:
>
> [...]
> KT> I just wich there was a good reference with good real-world
> KT> examples that covered both the simple and the hairy. [...]
>
> Just play around with it, how did you learn to walk for heavens sake?
You mean like the Adventure game where you guess at words it might
understand? Bad news: it sure sounded like fun, but it left me cold.
I have an exercise for anyone confused on this: ask your favorite Lisp
IDE to show you the signatures of first SUBSITUTE and then LOOP.
See why I need a reference?
(Should I just get the source?)
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
On 16 Oct 2003 23:55:40 +0300, Bulent Murtezaoglu <··@acm.org> wrote:
>>>>>> "KT" == Kenny Tilton <·······@nyc.rr.com> writes:
>[...]
> KT> I just wich there was a good reference with good real-world
> KT> examples that covered both the simple and the hairy. [...]
>
>Just play around with it, how did you learn to walk for heavens sake?
>
>B<just ignore me>M
>
By watching other people set an example!
Jeff Kish
"Tuang" wrote:
> (defun m37 (n)
> (loop for i from 1 to n
> counting (or (multiple i 3) (multiple i 7))))
>
> So naturally now I'm wondering how this might be generalized to count
> multiples of any list of numbers in any range. This seems like a very
> Lispy thing to do, but I can't even guess at the syntax for doing
> this:
There are several ways to do this. The easiest is probably
to use the SOME function.
(defun count-multiples (start end numbers)
(loop for i from start to end
count (some (lambda (n) (zerop (mod i n))) numbers)))
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> ...))))
You *could* use macros to build code that looks like that.
(defmacro multiple-of-one-of (var numbers)
(cons 'or
(loop for number in numbers collecting `(multiple ,var ,number))))
(defmacro count-multiples (start end numbers)
`(loop for i from start to end counting
(or ,@(loop for number in numbers collect `(multiple i ,number)))))
and so on. But that's almost certainly not best: what if the
list of numbers isn't known at compile time?
--
Gareth McCaughan
.sig under construc
Tuang wrote:
>
> ...
> So naturally now I'm wondering how this might be generalized to count
> multiples of any list of numbers in any range. This seems like a very
> Lispy thing to do, but I can't even guess at the syntax for doing
> this:
>
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> ...))))
>
> where the '??' are the elements of the list 'nums-list'. There must be
> something like mapcar that allows you to insert the elements of a list
> into a pattern like this. Then I'd be able to count all the multiples
> of 3, 5, or 7 between 1 and 1000 by entering
>
is it not strange, to first say "i can't even guess" in one sentence and then
use the next to not only guess, but to also propose an avenue of approach?
perhaps that is the subconscious as work, since as it happens, this is a
situation where tacking back onto a recursive approach for the counting clause
might have much to recommend it.
> > (mult-list (1 1000 '(3 5 7)))
(mult-list 1 1000 '(3 5 7))
or are we trying to get back to macros here?
...
james anderson <··············@setf.de> wrote in message news:<·················@setf.de>...
> Tuang wrote:
> >
> > ...
> > So naturally now I'm wondering how this might be generalized to count
> > multiples of any list of numbers in any range. This seems like a very
> > Lispy thing to do, but I can't even guess at the syntax for doing
> > this:
> >
> > (defun mult-list (start end nums-list)
> > (loop for i from start to end
> > counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> > ...))))
> >
> > where the '??' are the elements of the list 'nums-list'. There must be
> > something like mapcar that allows you to insert the elements of a list
> > into a pattern like this. Then I'd be able to count all the multiples
> > of 3, 5, or 7 between 1 and 1000 by entering
> >
>
> is it not strange, to first say "i can't even guess" in one sentence and then
> use the next to not only guess, but to also propose an avenue of approach?
I don't think so. I'm not proposing an approach with my (defun ...)
above. I'm just trying to explain my question as clearly as I can. I
don't have any idea how to get the equivalent effect of having (length
num-list) copies of the(multiple i ??) predicates, with the list
elements inserted where the "??"s are, one in each, and or'ed
together. That's hard to describe in English, which is why I wrote the
question in a sort of pseudocode.
I was imagining that this is probably something for which Lisp had a
built-in approach, along the lines of mapcar, but fancier.
> perhaps that is the subconscious as work, since as it happens, this is a
> situation where tacking back onto a recursive approach for the counting clause
> might have much to recommend it.
>
>
> > > (mult-list (1 1000 '(3 5 7)))
>
> (mult-list 1 1000 '(3 5 7))
>
> or are we trying to get back to macros here?
If macros are the solution, that would be interesting, too, but I'm
certainly not "trying to get back" somewhere I've never been. ;-)
Tuang wrote:
>
> james anderson <··············@setf.de> wrote in message news:<·················@setf.de>...
> > Tuang wrote:
> > >
> > > ...
> > > So naturally now I'm wondering how this might be generalized to count
> > > multiples of any list of numbers in any range. This seems like a very
> > > Lispy thing to do, but I can't even guess at the syntax for doing
> > > this:
> > >
> > > (defun mult-list (start end nums-list)
> > > (loop for i from start to end
> > > counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> > > ...))))
> > >
> > > where the '??' are the elements of the list 'nums-list'. There must be
> > > something like mapcar that allows you to insert the elements of a list
> > > into a pattern like this. Then I'd be able to count all the multiples
> > > of 3, 5, or 7 between 1 and 1000 by entering
> > >
> >
> > is it not strange, to first say "i can't even guess" in one sentence and then
> > use the next to not only guess, but to also propose an avenue of approach?
>
> I don't think so. I'm not proposing an approach with my (defun ...)
> above. I'm just trying to explain my question as clearly as I can. I
> don't have any idea how to get the equivalent effect of having (length
> num-list) copies of the(multiple i ??) predicates, with the list
> elements inserted where the "??"s are, one in each, and or'ed
> together. That's hard to describe in English, which is why I wrote the
> question in a sort of pseudocode.
>
i intended no judgement. i was being rhetorical, in the hope that you might
continue down the path, realize why it would not work, and eventually get to
something which would.
the exact form suggested above would be difficult to realize as the length of
the list is not known when the function is defined.
a more direct expression would require either an iterative or a recursive
expression. the iterative expressions would need to be chosen carefully, in
order to avoid unnecessary #'multiple computations.
a recursive expression, on the other hand, might require more thought, but
could be readily depth-limited.
> I was imagining that this is probably something for which Lisp had a
> built-in approach, along the lines of mapcar, but fancier.
take a look at the definitions for the sequence functions. you may be
surprised at what you find.
if i might step back for a second, i have a concrete suggestion for you. i
suspect that you may not find it immediately productive, and that in this
regard you will likely not be alone. despite that i offer it for you consideration.
find a concise description of the language. _all_ of the operators, and _all_
of the syntax. read it. the _whole_ thing. do not try to comprehend it, just
read it. don't even try to remember it. just trust your subconsious. then
start to try to learn how to use it. my experience has been that with this
approach one can proceed much faster and with much less frustration than if
one starts to set out formations on the playing field without yet knowing
where the goal posts are.
yes, i overstate, and i intend in no way to judge your experience, but your
posts do not give the impression that you are aware of some of the things
which are readily available.
>
> > perhaps that is the subconscious as work, since as it happens, this is a
> > situation where tacking back onto a recursive approach for the counting clause
> > might have much to recommend it.
> >
> >
> > > > (mult-list (1 1000 '(3 5 7)))
> >
> > (mult-list 1 1000 '(3 5 7))
> >
> > or are we trying to get back to macros here?
>
> If macros are the solution, that would be interesting, too, but I'm
> certainly not "trying to get back" somewhere I've never been. ;-)
well, if one _really_ wants a "1" in what would otherwise be an operator
position, one should consider defining a macro to that end.
...
james anderson <··············@setf.de> wrote in message news:<·················@setf.de>...
> Tuang wrote:
> >
> > james anderson <··············@setf.de> wrote in message
> if i might step back for a second, i have a concrete suggestion for you. i
> suspect that you may not find it immediately productive, and that in this
> regard you will likely not be alone. despite that i offer it for you consideration.
>
> find a concise description of the language. _all_ of the operators, and _all_
> of the syntax. read it. the _whole_ thing. do not try to comprehend it, just
> read it. don't even try to remember it. just trust your subconsious. then
> start to try to learn how to use it. my experience has been that with this
> approach one can proceed much faster and with much less frustration than if
> one starts to set out formations on the playing field without yet knowing
> where the goal posts are.
I think that's an excellent approach, and something that I routinely
do. I just hadn't gotten to it yet, but I started yesterday.
> yes, i overstate, and i intend in no way to judge your experience, but your
> posts do not give the impression that you are aware of some of the things
> which are readily available.
Very diplomatic. Thanks. ;-) Actually, I had only intended to ask
about why my tail recursion experiment was overflowing the stack,
since I'm at the recursion part of Touretzky's tutorial book. Since I
had heard that all modern CL implementations did tail-call
optimization, even though the spec didn't require it, I thought that I
must not be writing a proper tail call and wanted to know what I was
doing wrong.
I wasn't really ready to discuss anything else, but some people
answered my question with iterative solutions. That wasn't really what
I was asking, but it *was* interesting and led to questions that I
hadn't originally planned to ask.
As I said above, though, I'm working through the tutorials and
references. They'll no doubt answer most of my questions.
> > > > > (mult-list (1 1000 '(3 5 7)))
> > >
> > > (mult-list 1 1000 '(3 5 7))
> > >
> > > or are we trying to get back to macros here?
> >
> > If macros are the solution, that would be interesting, too, but I'm
> > certainly not "trying to get back" somewhere I've never been. ;-)
>
> well, if one _really_ wants a "1" in what would otherwise be an operator
> position, one should consider defining a macro to that end.
>
Oops. Yes, putting parens around my argument list in the function call
was a typo. Ironically, a function call in Lisp actually *omits*
parens in one place where most other languages I'm used to use them.
james anderson wrote:
>
> Tuang wrote:
>
>>...
>>So naturally now I'm wondering how this might be generalized to count
>>multiples of any list of numbers in any range. This seems like a very
>>Lispy thing to do, but I can't even guess at the syntax for doing
>>this:
>>
>>(defun mult-list (start end nums-list)
>> (loop for i from start to end
>> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
>>...))))
>>
>>where the '??' are the elements of the list 'nums-list'. There must be
>>something like mapcar that allows you to insert the elements of a list
>>into a pattern like this. Then I'd be able to count all the multiples
>>of 3, 5, or 7 between 1 and 1000 by entering
>>
>
>
> is it not strange, to first say "i can't even guess" in one sentence and then
> use the next to not only guess, but to also propose an avenue of approach?
Gosh, it struck me as doing everyone the courtesy of narrowing down his
point of unguessability to the location of the ??s. I read an implicit
"this much I can guess at, but when I get to the ??s I am stumped."
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
········@hotmail.com (Tuang) writes:
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> ...))))
I'd do it like this:
(defun mult-list (start stop factors)
(loop for i from start to stop
count (some (lambda (factor) (multiple i factor))
factors)
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> wrote in message news:<··············@vserver.cs.uit.no>...
> ········@hotmail.com (Tuang) writes:
>
> > (defun mult-list (start end nums-list)
> > (loop for i from start to end
> > counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> > ...))))
>
> I'd do it like this:
>
> (defun mult-list (start stop factors)
> (loop for i from start to stop
> count (some (lambda (factor) (multiple i factor))
> factors)
Thanks to everyone for suggesting these various approaches. I'll
remember these patterns for future use.
········@hotmail.com (Tuang) writes:
> (defun mult-list (start end nums-list)
> (loop for i from start to end
> counting (or (multiple i ??) (multiple i ??) (multiple i ??)
> ...))))
I'd do it like this:
(defun mult-list (start stop factors)
(loop for i from start to stop
count (some (lambda (factor) (multiple i factor))
factors)))
--
Frode Vatvedt Fjeld
"Tuang" wrote:
> So here's a silly problem that I thought would make a good excuse to
> write some code: how many multiples of either 3 or 7 are there between
> 1 and n?
(defun count37 (n)
(- (+ (floor n 3) (floor n 7)) (floor n 21)))
:-)
--
Gareth McCaughan
.sig under construc
"Gareth McCaughan" <················@pobox.com> schrieb im Newsbeitrag
···················@g.mccaughan.ntlworld.com...
> "Tuang" wrote:
>
> > So here's a silly problem that I thought would make a good excuse to
> > write some code: how many multiples of either 3 or 7 are there between
> > 1 and n?
>
> (defun count37 (n)
> (- (+ (floor n 3) (floor n 7)) (floor n 21)))
>
> :-)
Now you just have to build the recursion into this. :-))
> --
> Gareth McCaughan
> .sig under construc
Yr nws-clnt rds chrctrs. :-)
Cheers
robert
"Robert Klemme" <········@gmx.net> writes:
> "Gareth McCaughan" <················@pobox.com> schrieb im Newsbeitrag
> ···················@g.mccaughan.ntlworld.com...
> > "Tuang" wrote:
> >
> > > So here's a silly problem that I thought would make a good excuse to
> > > write some code: how many multiples of either 3 or 7 are there between
> > > 1 and n?
> >
> > (defun count37 (n)
> > (- (+ (floor n 3) (floor n 7)) (floor n 21)))
> >
> > :-)
>
> Now you just have to build the recursion into this. :-))
Sure.
(defun count37 (n)
(if (zerop (random 1000))
(- (+ (floor n 3) (floor n 7)) (floor n 21)))
(count37 n))
It's even tail-recursive!
--
Gareth McCaughan
.sig under construc
········@hotmail.com (Tuang) wrote in message news:<····························@posting.google.com>...
> I'm a newbie trying to teach himself CL by working through the
> beginner's books and coming up with silly little problems to use as
> coding challenges to develop my CL instincts.
>
> So here's a silly problem that I thought would make a good excuse to
> write some code: how many multiples of either 3 or 7 are there between
> 1 and n?
(defun how-many (n)
(let ((3s (truncate n 3))
(7s (truncate n 7))
(21s (truncate n 21)))
(- (+ 3s 7s) 21s)))
Why count something that occurs regularly?
> ; is x a multiple of n?
> (defun multp (x n)
> (zerop (mod x n)))
Another possibility:
(defun multp (x n)
(/= (gcd x n) 1))
> In order to keep it from overflowing the stack, I wanted to make it
> tail recursive.
To keep from overflowing the stack, choose algorithms with a small
stack growth, or code iteratively. Common Lisp does not require
implementations to optimize tail recursion, so if you write functions
whose stack requirement is some big function of the input size, and
pass them big input, your program is in the hands of the
implementation, so to speak. Avoid writing anything that needs O(N)
stack frames in the input size N; or if you do, be careful to feed it
only small inputs.
When you expect large inputs, only use recursion with
divide-and-conquer type algorithms which achieve a lot of breadth with
little depth.
> I'm pretty shaky on how you write functions to make them tail
> recursive, so I don't understand why this fails.
To write functions that are tail recursive, have them call themselves
as the last step. But don't expect every Common Lisp compiler to
optimize them into iterative code, that is all!
Tail recursion is not the same thing as tail recursion optimization.
In some programming language camps, they confuse the two: they say
things like ``this language is properly tail recursive'', when they
really mean ``implementations of this language are required to
recognize certain instances of tail recursion and turn them into
iterative code''.
No such set of situations is defined for Common Lisp, nor is there any
requirement to do such an optimization. It's up to the compiler
implementors. It may even be the case within one Lisp implementation
that tail recursion is optimized when a function is compiled, yet
allowed to generate stack frames when the same function is not
compiled. Moral: before you conclude that your Lisp implementation is
failing to do tail call elimination, make sure you are compiling the
code!
In article <····························@posting.google.com>,
Kaz Kylheku <···@ashi.footprints.net> wrote:
>········@hotmail.com (Tuang) wrote in message
>news:<····························@posting.google.com>...
>> I'm a newbie trying to teach himself CL by working through the
>> beginner's books and coming up with silly little problems to use as
>> coding challenges to develop my CL instincts.
>>
>> So here's a silly problem that I thought would make a good excuse to
>> write some code: how many multiples of either 3 or 7 are there between
>> 1 and n?
>
>(defun how-many (n)
> (let ((3s (truncate n 3))
> (7s (truncate n 7))
> (21s (truncate n 21)))
> (- (+ 3s 7s) 21s)))
>
>Why count something that occurs regularly?
Because he's trying to learn tail recursion, not solve a mathematical
problem.
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <··············@level3.com> wrote in message news:<···············@news.level3.com>...
> In article <····························@posting.google.com>,
> Kaz Kylheku <···@ashi.footprints.net> wrote:
> >········@hotmail.com (Tuang) wrote in message
> >news:<····························@posting.google.com>...
> >> I'm a newbie trying to teach himself CL by working through the
> >> beginner's books and coming up with silly little problems to use as
> >> coding challenges to develop my CL instincts.
> >>
> >> So here's a silly problem that I thought would make a good excuse to
> >> write some code: how many multiples of either 3 or 7 are there between
> >> 1 and n?
> >
> >(defun how-many (n)
> > (let ((3s (truncate n 3))
> > (7s (truncate n 7))
> > (21s (truncate n 21)))
> > (- (+ 3s 7s) 21s)))
> >
> >Why count something that occurs regularly?
>
> Because he's trying to learn tail recursion, not solve a mathematical
> problem.
That's right. I'm not doing this because the math problem is
interesting but because it's easy to tell when it's working and when
it's not. I was just trying to do something easy (a toy problem) using
a functional/recursion approach instead of the iterative approach I'm
used to from other languages. I could have just used a problem like
"count the even numbers between a and b", but by making it multiples
of two (or more) numbers, I made it a slightly more difficult coding
challenge, but I can still figure out the right answer in my head for
test cases.
Kaz Kylheku wrote:
> Tail recursion is not the same thing as tail recursion optimization.
> In some programming language camps, they confuse the two: they say
> things like ``this language is properly tail recursive'', when they
> really mean ``implementations of this language are required to
> recognize certain instances of tail recursion and turn them into
> iterative code''.
Not quite, it really means that _all_ instances of tail recursion are
required to be translated into iterative code.
Pascal
Pascal Costanza wrote:
> Kaz Kylheku wrote:
>
>> Tail recursion is not the same thing as tail recursion optimization.
>> In some programming language camps, they confuse the two: they say
>> things like ``this language is properly tail recursive'', when they
>> really mean ``implementations of this language are required to
>> recognize certain instances of tail recursion and turn them into
>> iterative code''.
>
>
> Not quite, it really means that _all_ instances of tail recursion are
> required to be translated into iterative code.
Sorry that some of my postings appear twice although they have already
been refuted. It's because of a technical problem...
Sorry again.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Kaz Kylheku wrote:
> Tail recursion is not the same thing as tail recursion optimization.
> In some programming language camps, they confuse the two: they say
> things like ``this language is properly tail recursive'', when they
> really mean ``implementations of this language are required to
> recognize certain instances of tail recursion and turn them into
> iterative code''.
Not quite, it really means that _all_ instances of tail recursion are
required to be translated into iterative code.
Pascal
Pascal Costanza <········@web.de> writes:
> Kaz Kylheku wrote:
>
> > Tail recursion is not the same thing as tail recursion optimization.
> > In some programming language camps, they confuse the two: they say
> > things like ``this language is properly tail recursive'', when they
> > really mean ``implementations of this language are required to
> > recognize certain instances of tail recursion and turn them into
> > iterative code''.
>
>
> Not quite, it really means that _all_ instances of tail recursion are
> required to be translated into iterative code.
Kaz Kylheku is closer to the truth on this. R5RS enumerates the
conditions where tail recursion is required, but, for example,
(let ((x (compute-something)))
x)
which can obviously tail recurse on to (compute-something), is
*not* required to be tail recursive.
Joe Marshall wrote:
> Pascal Costanza <········@web.de> writes:
>
>
>>Kaz Kylheku wrote:
>>
>> > Tail recursion is not the same thing as tail recursion optimization.
>> > In some programming language camps, they confuse the two: they say
>> > things like ``this language is properly tail recursive'', when they
>> > really mean ``implementations of this language are required to
>> > recognize certain instances of tail recursion and turn them into
>> > iterative code''.
>>
>>
>>Not quite, it really means that _all_ instances of tail recursion are
>>required to be translated into iterative code.
>
>
> Kaz Kylheku is closer to the truth on this. R5RS enumerates the
> conditions where tail recursion is required, but, for example,
>
> (let ((x (compute-something)))
> x)
>
> which can obviously tail recurse on to (compute-something), is
> *not* required to be tail recursive.
...so that an implementation of the language isn't actually required to
do extensive program analysis to determine all instances of tail
recursion. OK, I haven't thought of this before - thanks for clarification.
Pascal
Pascal Costanza <········@web.de> writes:
> Joe Marshall wrote:
>
>> Pascal Costanza <········@web.de> writes:
>>
>>>Kaz Kylheku wrote:
>>>
>>> > Tail recursion is not the same thing as tail recursion optimization.
>>> > In some programming language camps, they confuse the two: they say
>>> > things like ``this language is properly tail recursive'', when they
>>> > really mean ``implementations of this language are required to
>>> > recognize certain instances of tail recursion and turn them into
>>> > iterative code''.
>>>
>>>
>>>Not quite, it really means that _all_ instances of tail recursion are
>>>required to be translated into iterative code.
>> Kaz Kylheku is closer to the truth on this. R5RS enumerates the
>> conditions where tail recursion is required, but, for example,
>> (let ((x (compute-something)))
>> x)
>> which can obviously tail recurse on to (compute-something), is
>> *not* required to be tail recursive.
>
> ...so that an implementation of the language isn't actually required
> to do extensive program analysis to determine all instances of tail
> recursion. OK, I haven't thought of this before - thanks for
> clarification.
Right. It only needs to find the `obvious' ones.
Joe Marshall <···@ccs.neu.edu> wrote:
+---------------
| Pascal Costanza <········@web.de> writes:
| > ...so that an implementation of the language isn't actually required
| > to do extensive program analysis to determine all instances of tail
| > recursion. ...
|
| Right. It only needs to find the `obvious' ones.
+---------------
Specifically, it only needs to find the specific (sub)expressions
required by R5RS "3.5 Proper tail recursion":
<URL:http://www.schemers.org/Documents/Standards/R5RS/HTML/
r5rs-Z-H-6.html#%_sec_3.5>
Though as it says there, an implementation *may* do more:
Note: Implementations are allowed, but not required, to recognize
that some non-tail calls, such as the call to H above, can be
evaluated as though they were tail calls. In the example above,
the LET expression could be compiled as a tail call to H.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Tuang wrote:
>
> I'm a newbie trying to teach himself CL by working through the
> beginner's books and coming up with silly little problems to use as
> coding challenges to develop my CL instincts.
>
> So here's a silly problem that I thought would make a good excuse to
> write some code: how many multiples of either 3 or 7 are there between
> 1 and n?
Uh, that's a one-liner. Well, okay, a two liner if you count
the defun header.
(defun (mult3_7 n)
(- (+(mod 3 n)(mod 7 n))(mod 21 n)))
> So, I thought I'd try a recursive approach in Lisp.
Not the best approach for this problem, but you're studying the
approach rather than solving the problem, right?
You know CL doesn't absolutely require tailcall optimization, right?
Some other lisps do, but not Common Lisp. So the proper CL approach
here would be to use some iterator (which is guaranteed space-safe)
rather than to use a tailcall.
That said, I think all the major implementations provide tailcall
optimization, at least in the simple "self tail call" case you're
looking at, so there ought to be a way to do what you're attempting.
Bear
Ray Dillinger wrote:
>
> Tuang wrote:
> >
> > So here's a silly problem that I thought would make a good excuse to
> > write some code: how many multiples of either 3 or 7 are there between
> > 1 and n?
>
> Uh, that's a one-liner. Well, okay, a two liner if you count
> the defun header.
>
> (defun (mult3_7 n)
> (- (+(mod 3 n)(mod 7 n))(mod 21 n)))
>
Doh! The above function is wrong. I used mod where I meant quotient.
Sorry for any confusion.
Bear