I was fiddling around with catch and throw in Lisp as a prelude to using
exceptions in Java as a way to manually do tail call elimination, when I
reinvented the wheel and realized you can do it with delay and force:
(defmacro delay (expr)
`#'(lambda () ,expr))
(defmacro force (expr)
`(funcall ,expr))
(defun fact (n &optional (res 1))
(if (< n 2)
(delay res)
(delay (force (fact (- n 1) (* n res))))))
CL-USER> (force (fact 40))
815915283247897734345611269596115894272000000000
CL-USER>
Is there a way to get the same effect using catch and throw w/o the thunks?
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Fri, 03 Feb 2006 02:37:22 -0600, Matthew D Swank wrote:
> (defmacro force (expr)
> `(funcall ,expr))
Though I suppose funcall, even as a primitive operator, can
introduce overhead of its own. Perhaps:
(defmacro force-all (expr)
(let ((ex (gensym)))
`(let ((,ex ,expr))
(do ((current ,ex (funcall (cdr current))))
((null (cdr current)) (car current))))))
(defmacro delay (expr)
`(cons nil #'(lambda () ,expr)))
(defmacro base (expr)
`(cons ,expr nil))
(defun fact (n &optional (res 1))
(if (< n 2)
(base res)
(delay (fact (- n 1) (* n res)))))
In abcl (no TCE, not even a little bit):
CL-USER(67): (force-all (fact 40000))
(something with a lot of zeros elided....)
CL-USER(68):
Still can't seem to figure it out with catch and throw though...
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: catch, throw and tail call elimination
Date:
Message-ID: <87psm4qx3q.fsf@qrnik.zagroda>
Matthew D Swank <·······································@c.net> writes:
> (defmacro delay (expr)
> `#'(lambda () ,expr))
>
> (defmacro force (expr)
> `(funcall ,expr))
>
> (defun fact (n &optional (res 1))
> (if (< n 2)
> (delay res)
> (delay (force (fact (- n 1) (* n res))))))
This doesn't run in constant stack space if the underlying Lisp
implementation doesn't already perform tail calls in constant
stack space.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
On Fri, 03 Feb 2006 16:29:45 +0100, Marcin 'Qrczak' Kowalczyk wrote:
> Matthew D Swank <·······································@c.net> writes:
>
(code elided)
>
> This doesn't run in constant stack space if the underlying Lisp
> implementation doesn't already perform tail calls in constant
> stack space.
Yes, that is why I posted the other implementation
(http://makeashorterlink.com/?C5552549C). I apologize for not copping to
my mistake more clearly. The question remains: Is it possible to do this
w/o the thunk?
Thanks,
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> On Fri, 03 Feb 2006 16:29:45 +0100, Marcin 'Qrczak' Kowalczyk wrote:
>>Matthew D Swank <·······································@c.net> writes:
> (code elided)
>>This doesn't run in constant stack space if the underlying Lisp
>>implementation doesn't already perform tail calls in constant
>>stack space.
>
> Yes, that is why I posted the other implementation
> (http://makeashorterlink.com/?C5552549C). I apologize for not copping to
> my mistake more clearly. The question remains: Is it possible to do this
> w/o the thunk?
It depends on the rules of the game.
The transformation you used, is to be applied on the whole program,
so in principle one could use the normal techniques to support
an infinite number of active tail calls within finite stack space.
There are some papers on the subject at <http://readscheme.org>.
Related to your snippet is the paper "Trampolined Style",
by Steven E. Ganz, Daniel P. Friedman and Mitchell Wand, which
if you haven't read it already, probably will enjoy.
Another example to test besides FACT is an infinite loop
between two mutually recursive functions, such as:
(defun loop-inc (n)
(loop-dec (+ n 1)))
(defun loop-dec (n)
(loop-dec (- n 1)))
(defun loop-inc+ (n)
(delay (loop-dec+ (+ n 1))))
(defun loop-dec+ (n)
(delay (loop-dec+ (- n 1))))
--
Jens Axel Søgaard
On Fri, 03 Feb 2006 23:10:25 +0100, Jens Axel Søgaard wrote:
> (defun loop-dec+ (n)
> (delay (loop-dec+ (- n 1))))
exhausts memory as n -> inf :)
But this seems to work:
(defun loop-dec+ (n)
(delay (loop-inc+ (- n 1))))
> Related to your snippet is the paper "Trampolined Style",
> by Steven E. Ganz, Daniel P. Friedman and Mitchell Wand, which
> if you haven't read it already, probably will enjoy.
I have read it. Though, having used trampolines in the past before I
knew what they were called, it seems like they are something that
gets reinvented frequently* for tasks that might otherwise use
continuations.
Matt
* At least in my brain trampolined style is a natural extension of a
knowledge of closures.
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> On Fri, 03 Feb 2006 23:10:25 +0100, Jens Axel Søgaard wrote:
>
>
>>(defun loop-dec+ (n)
>> (delay (loop-dec+ (- n 1))))
>
>
> exhausts memory as n -> inf :)
>
> But this seems to work:
>
> (defun loop-dec+ (n)
> (delay (loop-inc+ (- n 1))))
That was indeed the intention...
--
Jens Axel Søgaard
On Fri, 03 Feb 2006 23:10:25 +0100, Jens Axel Søgaard wrote:
> Another example to test besides FACT is an infinite loop
> between two mutually recursive functions, such as:
(code elided)
This one is also a useful test as it uses a partial CPS xform to turn a
non-tail call into a tail call.
From:
(defun fold (fun lst init)
(if (null lst)
init
(funcall fun
(car lst)
(fold fun (cdr lst) init))))
To:
(defun fold (fun lst init &optional (k #'(lambda(val) (base val))))
(if (null lst)
(delay (funcall k init))
(delay (fold fun (cdr lst) init
#'(lambda (rest)
(delay (funcall k
(funcall fun (car lst) rest))))))))
in abcl:
CL-USER(6): (force-all (fold #'cons '(a b c) nil))
(A B C)
CL-USER(7): (defun make-nils (length &optional (lst nil))
(if (< length 1)
(base lst)
(delay (make-nils (- length 1) (cons nil lst)))))
MAKE-NILS
CL-USER(8):(force-all (fold #'(lambda (a b) a) (make-nils 1000000) nil)))
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL ...)
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Sat, 04 Feb 2006 00:54:57 -0600, Matthew D Swank wrote:
> CL-USER(8):(force-all (fold #'(lambda (a b) a) (make-nils 1000000) nil)))
of course this should be:
CL-USER(8): (force-all (fold #'cons (force-all (make-list 1000000)) nil)
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.