'42 (def '0 '()) (def '1 '(1)) (def '+ append) (def 'sub1 cdr) (defun - (a b) (if (eq b 0) a (- a (cdr b)))) (defun * (a b) (if (eq a 0) 0 (+ b (* b (cdr a))))) (defun == (a b) (if (null a) (null b) (if (null b) 'nil (== (cdr a) (cdr b))))) (assert (== '(7 6 5 4 3 2 1) (+ '(3 2 1) '(4 3 2 1)))) (assert (== '(12 11 10 9 8 7 6 5 4 3 2 1) (* '(3 2 1) '(4 3 2 1)))) (fn 'Y '(g) '(let a (lambda (f) (f f)) (a (lambda (f) (g (lambda (x) (let c (f f) (c x)))))))) ;; -- traditional fixed-point operator from functional programming ;; Y = function (g) ;; local a = function (f) return f(f) end ;; return a(function (f) ;; return g(function (x) ;; local c=f(f) ;; return c(x) ;; end) ;; end) ;; end (fn 'F-tri '(f) '(lambda (n) (if (eq n 0) 0 (+ n (f (sub1 n)))))) (fn 'F-fact '(f) '(lambda (n) (if (eq n 0) 1 (* n (f (sub1 n)))))) ;; -- factorial without recursion ;; F = function (f) ;; return function (n) ;; if n == 0 then return 1 ;; else return n*f(n-1) end ;; end ;; end (def 'triangle (Y F-tri)) (def 'factorial (Y F-fact)) (assert (== 0 (triangle 0))) (assert (== 1 (triangle 1))) (assert (== '(1 2 2) (triangle '(1 2)))) (assert (== '(1 2 2 3 3 3) (triangle '(1 2 3)))) (assert (== '(1 2 2 3 3 3 4 4 4 4) (triangle '(1 2 3 4)))) ;; factorial = Y(F) -- factorial is the fixed point of F ;; ;; -- now test it ;; function test(x) ;; io.write(x,"! = ",factorial(x),"\n") ;; end ;; ;; for n=0,16 do ;; test(n) ;; end