-
Notifications
You must be signed in to change notification settings - Fork 37
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Tail call optimization does not seem to work? #15
Comments
I think you're right and it is because I never bothered to update tinylisp after writing the other lisp (lisp in 1K lines of C). Those small lisp interpreters do perform full TC optimization:
Tinylisp does a bit of TC, but not full TC. What is missing is a TC classification of lisp primitives to TC-optimize them ( We can (should) do the same for tinylisp. |
The TC classification seems to be in place, though: There is a |
Yes, but it doesn't work the same way as the eval loop in the "big brother" lisp. Perhaps it's not the
because However, there may be a way to get around this and use a corrected ABC, I'm thinking. |
I've added a clarification of TC optimization limitations to the PDF page 35 related to argument evaluations that will accumulate in memory. I'm thinking that there should be a way fix "ABC" garbage collection to make it work. But it is not just sufficient for data structures to be acyclic as the SectorLisp author presents it. Acyclic forms like |
Thank you for the clarification! I was actually following along your PDF with my own implementation, and was scratching my head why tail calls do not get optimized. I had made a couple of customizations, but hadn't yet gotten to implementing a full garbage collection, so I wasn't sure if I made a mistake in the evaluator implementation or not. Good to know the underlying reason, thanks a lot! |
Hello, I've been experimenting with the tail call-optimized version of tinylisp (
tinylisp-opt.c
), but it doesn't seem to optimize tail calls. Specifically, I've been testing it with a tail call-optimized factorial computation:The following shows a session of me compiling
tinylisp-opt.c
and running the abovefactorial
function with the value of 1000:I'd have expected the computation to finish successfully and return
inf
, since the result exceeds the validdouble
range.When I compare it with your full LISP implementation which is also tail call-optimized, I'm getting the correct results:
I've even tried to increase the available memory of
tinylisp
by settingN
to larger values, but there is always a value that makes the code run out of memory. Compared with the full LISP implementation which happily calculates(factorial 100000)
(though again producinginf
, of course), this makes me think that there is something missing fromtinylisp-opt.c
to make it fully tail call-optimized.The text was updated successfully, but these errors were encountered: