Lambda Calculus Interpreter

lcalc.min.hy

(eval-and-compile(defmacro D[&rest e]`(defn ~@e))(D €[a b](.extend a b)a)(D §[a](.reverse a)a)(D ¤[a](first a))(D ?[e](instance? F e))(D £[e](if(coll? e)(if(?(¤ e))(£(apply(¤ e)(rest e)))(if(? e)e(do(def x(list(map £ e)))(if(?(¤ x))(£ x)x))))e))(D $[a b c](if(coll? c)(if(? c)(if(=(¤ c)a)c(F[(¤ c)($ a b(second c))]))((type c)(genexpr($ a b d)[d c])))(if(= a c)b c)))(defclass V[HySymbol](D --call--[self &rest v](€[self]v)))(defclass F[HyExpression](D --call--[self a &rest b](def e(£($(¤ self)a(second self))))(if b(def e(apply e b)))e)))(defmacro L[&rest e](reduce(fn[y x]`((fn[](def ~x(V(gensym'~x)))(F[~x ~y]))))(§(list e))))

Lambda calculus interpreter in Hy, 630 chars (648 bytes) minified. Supports multiary argument notation and multiple parameter passing. No need for dot because the last element of the function is taken as the body of the function.

Calculating the fourth triangular number by Lambda calculus using ycombinator:

; int to church number generator
(defmacro NUM [n &rest args]
  `(L x y ~(reduce (fn [x y] (hy.HyExpression ['x x])) (range n) 'y) ~@args))

; reverse church number to int
(defn MUN [n]
  (def x (n 1 0))
  (if (numeric? x) x
    (sum (flatten x))))

; lambda forms
(def COND (L a b c (a b c))
     TRUE (L a b a)
     FALSE (L a b b)
     ZERO? (L s (s (L a FALSE) TRUE))
     SUM (L m n x y (m x (n x y)))
     IDENT (L x x)
     PRED (L n x y (n (L g h (h (g x))) (L x y) IDENT))
     SELF (L f x (f f x))
    ; note the usage of coll body to prevent too early evaluation of the ycombinator
     YCOMB (L f [(L x (x x)) (L x (f (x x)))])
)

(MUN (YCOMB (L f n (COND (ZERO? n) n (SUM n (f (PRED n))))) (NUM 4)))

should yield: 10