For Fun: Clojure-style Tail Recursion in newLISP
Posted: Tue Apr 02, 2013 10:03 pm
Today, I just read an old blog post by Mike Ivanov where he explains how he implemented Clojure-style (loop/recur) tail recursion in Emacs Lisp. My first thought was, "Hey, that's cool!" My second thought was, "Hey, I think we can do this in newLISP too!" :)
So, just for fun, here is my newLISP port of Mike's implementation. [EDIT: I updated the code in the following block after my original posting to fix a bug. The details of the bug (error) are described in a TL;DR reply of mine further down in this discussion.]
You can't use Mike's (Emacs Lisp) applications examples verbatim, but here they are in newLISP.
They work like a charm!
Please let me know if you spot an error or if it can be accomplished better in any way. Thanks and happy hacking! :)
So, just for fun, here is my newLISP port of Mike's implementation. [EDIT: I updated the code in the following block after my original posting to fix a bug. The details of the bug (error) are described in a TL;DR reply of mine further down in this discussion.]
Code: Select all
(constant '[loop/recur-marker] '[loop/recur-marker])
(define (loop- BODY-FN)
(let (.args (args) .res nil)
(while (begin
(setq .res (apply BODY-FN .args))
(when (and (list? .res) (not (empty? .res))
(= [loop/recur-marker] (first .res)))
(setq .args (rest .res)))))
.res))
(define (recur) (cons [loop/recur-marker] (args)))
(define (flat-shallow-pairs LIST)
(let (i 0 acc '())
(dolist (e LIST)
(cond ((even? i) ; Indicator i is even = abscissa
(cond ((and (list? e) (not (empty? e)))
(extend acc (0 2 (push nil e -1))))
((symbol? e)
(push e acc -1)
(inc i))))
((odd? i) ; Indicator i is odd = ordinate
(push e acc -1)
(inc i))))
acc))
(define (parms<-bindings BINDINGS)
(map first (explode (flat-shallow-pairs BINDINGS) 2)))
(define-macro (loop INIT)
(letn (.parms (parms<-bindings INIT)
.body-fn (letex ([body] (args)
[parms] .parms)
(append '(fn [parms]) '[body]))
.loop-call (letex ([body-fn] .body-fn
[parms] .parms)
(append '(loop- [body-fn]) '[parms])))
(letex ([init] INIT [loop-call] .loop-call)
(letn [init] [loop-call]))))
You can't use Mike's (Emacs Lisp) applications examples verbatim, but here they are in newLISP.
Code: Select all
(define (factorial x)
(loop (x x acc 1)
(if (< x 1)
acc
(recur (- x 1) (* x acc)))))
(define (fibo x)
(loop (x x curr 0 next 1)
(if (= x 0)
curr
(recur (- x 1) next (+ curr next)))))
Code: Select all
> (factorial 10)
3628800
> (fibo 10)
55