// lambda interpreter support code: // booleans true = \x.\y.x; false = \x.\y.y; // pairs pair = \x.\y.\f.f x y; fst = \p.p (\x.\y.x); snd = \p.p (\x.\y.y); // sum types left = \a.\f.\g.f a; right = \b.\f.\g.g b; either = \x.\l.\r.x l r; // Church numerals succ = \n.\f.\x.f (n f x); 0 = \f.\x.x; 1 = succ 0; 2 = succ 1; 3 = succ 2; 4 = succ 3; + = \n.\m.n succ m; * = \n.\m.n (+ m) 0; ^ = \n.\m.m (* n) 1; ^ = \n.\m.m n; // this is equivalent to the definition above // S-expressions noreduce bot = (\x.x x)(\x.x x); noreduce nil = \n.\c.n; cons = \y.\ys.\n.\c.c y ys; noreduce car = \xs.xs bot (\y.\ys.y); // expect xs = cons y ys noreduce cdr = \xs.xs bot (\y.\ys.ys); // expect xs = cons y ys null? = \xs.xs true (\y.\ys.false); // Y combinator noreduce Y = \f.(\x.f(x x))(\x.f(x x));