I'm playing around with doing some Haskell-ish parameter matching in
Lisp for fun, but I'm getting an interesting stack overflow. Here's
some code snippets:
;; return a list of numbers from 1..n
(defun nums (n) (loop for i from 1 to n collect i))
;; sum all the numbers in a list
(defun sum (x) (if (null x) 0 (+ (first x) (sum (rest x))))
This works just fine, of course:
(sum (nums 100)) => 5050
However, if I redefine "sum" to the following:
(defmethod sum ((x null)) 0)
(defmethod sum ((x list)) (+ (first x) (sum (rest x)))
Now it works for small data:
(sum (nums 6)) => 21
But blows up on larger sets that worked earlier:
(sum (nums 100)) => Stack overflow.
I was hoping someone could toss some insight my way as to why this is.
Are the beginnings of defmethods prefixed with recursive code (eg, sum
null fails to match and recursively calls the next test in the list)?
Best wishes,
Jeff M.
Jeff M. wrote:
> ;; return a list of numbers from 1..n
> (defun nums (n) (loop for i from 1 to n collect i))
...
>
> However, if I redefine "sum" to the following:
>
> (defmethod sum ((x null)) 0)
> (defmethod sum ((x list)) (+ (first x) (sum (rest x)))
...
> But blows up on larger sets that worked earlier:
>
> (sum (nums 100)) => Stack overflow.
>
What implementation are you using?
Have you tried using the defmethod version on a freshly started Lisp
image? (I don't think it should make any difference, but just in case).
Have you compiled the code?
Also, while this is probably a useful exercise, for practical purposes
you should also make sure you know about REDUCE.
If you really want to do Haskell-ish pattern matching, you should look
at descructuring-bind and some of the pattern matching code in On Lisp
<http://www.paulgraham.com/onlisptext.html>. Or, if you want something
a little more production quality, you should have a look at Marco
Antoniotti's cl-unification library
<http://common-lisp.net/project/cl-unification/>.
And I'd like to point out that, in addition to the methods others have
already recommended, you could get the effect of (sum (nums 100)),
without the stack overflow, with (/ (* n (1+ n)) 2). ;-)
-Peter
"Jeff M." <·······@gmail.com> writes:
> (defun nums (n) (loop for i from 1 to n collect i))
>
> (defmethod sum ((x null)) 0)
> (defmethod sum ((x list)) (+ (first x) (sum (rest x)))
>
> (sum (nums 100)) => Stack overflow.
>
> I was hoping someone could toss some insight my way as to why this is.
The recursion is simply too deep.
If you're blowing out at 100 deep, you are probably running
the code interpreted, which would add a bunch of additional
stack frames. If you compile the methods, you'll probably
get an order of magnitude farther.
But you could just write instead:
(reduce #'+ (nums 100))
or
(loop for i from i to n summing i)
and not have to worry about the stack.
cheers,
Chris
"Jeff M." <·······@gmail.com> writes:
> I'm playing around with doing some Haskell-ish parameter matching in
> Lisp for fun, but I'm getting an interesting stack overflow. Here's
> some code snippets:
>
> ;; return a list of numbers from 1..n
> (defun nums (n) (loop for i from 1 to n collect i))
>
> ;; sum all the numbers in a list
> (defun sum (x) (if (null x) 0 (+ (first x) (sum (rest x))))
>
> This works just fine, of course:
>
> (sum (nums 100)) => 5050
>
> However, if I redefine "sum" to the following:
>
> (defmethod sum ((x null)) 0)
> (defmethod sum ((x list)) (+ (first x) (sum (rest x)))
>
> Now it works for small data:
>
> (sum (nums 6)) => 21
>
> But blows up on larger sets that worked earlier:
>
> (sum (nums 100)) => Stack overflow.
>
> I was hoping someone could toss some insight my way as to why this is.
> Are the beginnings of defmethods prefixed with recursive code (eg, sum
> null fails to match and recursively calls the next test in the list)?
Tail call removal is not mandatory in Common-Lisp.
I assume your implementation is able to remove tail-calls in the case
of a single function (for the explicit test), but not in the case of
methods (for the implicit dispatch).
For example, in clisp:
[79]> (load(compile-file "/tmp/s.lisp"))
Compiling file /tmp/s.lisp ...
Wrote file /tmp/s.fas
0 errors, 0 warnings
;; Loading file /tmp/s.fas ...
;; Loaded file /tmp/s.fas
T
[80]> (disassemble 'sum)
Disassembly of function SUM
(CONST 0) = 0
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0 (LOAD&JMPIF 1 L9)
3 L3
3 (CONST 0) ; 0
4 (SKIP&RET 2)
6 L6 <------------+
6 (LOAD&JMPIFNOT 1 L3) |
9 L9 |
9 (LOAD&CAR&PUSH 1) |
11 (LOAD&CDR&PUSH 2) |
13 (JSR&PUSH L6) ------------+
15 (CALLSR 2 53) ; +
18 (SKIP&RET 2)
NIL
[91]> (disassemble (find-method (function summ) '() (list (find-class 'list))))
Disassembly of function #:|(DEFMETHOD SUMM (#) ...)-4-1-1|
(CONST 0) = SUMM
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
5 byte-code instructions:
0 (LOAD&CAR&PUSH 1)
2 (LOAD&CDR&PUSH 2)
4 (CALL1&PUSH 0) ; SUMM --------> dispatch
6 (CALLSR 2 53) ; +
9 (SKIP&RET 2)
Disassembly of function #:|(DEFMETHOD SUMM (#) ...)-4-1|
(CONST 0) = #<COMPILED-CLOSURE #:|(DEFMETHOD SUMM (#) ...)-4-1-1|>
(CONST 1) = (T)
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0 (CONST&PUSH 0) ; #<COMPILED-CLOSURE #:|(DEFMETHOD SUMM (#) ...)-4-1-1|>
1 (CONST 1) ; (T)
2 (CONS)
3 (SKIP&RET 2)
NIL
[92]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pascal Bourguignon <···@informatimago.com> writes:
>> (defmethod sum ((x null)) 0)
>> (defmethod sum ((x list)) (+ (first x) (sum (rest x)))
> Tail call removal is not mandatory in Common-Lisp.
This is not a tail call.
OTOH I think it's better for implementations to support a large stack
than to force programmers to write awkward code which simulates a
stack on the heap instead of using deep recursion.
Large stack means resizable stack when threads can be involved.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/