'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