From 3641a9827575d2eba30d316395eb3db7c45a1477 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Mon, 4 Oct 2010 08:09:08 -0400 Subject: [PATCH] added more combinators to parser Signed-off-by: Jim Pryor --- code/lambda.js | 35 ++--------------------------------- code/parse.js | 10 +++++++++- lambda_evaluator.mdwn | 2 +- 3 files changed, 12 insertions(+), 35 deletions(-) diff --git a/code/lambda.js b/code/lambda.js index 50880fc6..0eea4c92 100644 --- a/code/lambda.js +++ b/code/lambda.js @@ -450,42 +450,11 @@ try { } } catch (e) {} -/* -let true = K in -let false = \x y. y in -let and = \l r. l r false in -let or = \l r. l true r in -let pair = \u v f. f u v in -let triple = \u v w f. f u v w in -let succ = \n s z. s (n s z) in -let pred = \n s z. n (\u v. v (u s)) (K z) I in -let ifzero = \n. n (\u v. v (u succ)) (K 0) (\n withp whenz. withp n) in -let add = \m n. n succ m in -let mul = \m n. n (\z. add m z) 0 in -let mul = \m n s. m (n s) in -let sub = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in -let min = \m n. sub m (sub m n) in -let max = \m n. add n (sub m n) in -let lt = (\mzero msucc mtail. \n m. n mtail (m msucc mzero) true (\x. true) false) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in -let leq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in -let eq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 (K (pair 1 I))) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in -let divmod = (\mzero msucc mtail. \n divisor. - (\dhead. n (mtail dhead) (\sel. dhead (sel 0 0))) - (divisor msucc mzero (\a b c. c x)) - (\d m a b c. pair d m) ) - (triple succ (K 0) I) - (\d. triple I succ (K d)) - (\dhead d. d (\dz mz df mf drest sel. drest dhead (sel (df dz) (mf mz)))) in -let div = \n d. divmod n d true in -let mod = \n d. divmod n d false in -let Y = \f. (\y. f(y y)) (\y. f(y y)) in -let Z = (\u f. f(u u f)) (\u f. f(u u f)) in -let fact = \y. y (\f n. ifzero n (\p. mul n (f p)) 1) in -fact Z 3 -*/ +// Chris's original + // // Basic data structure, essentially a LISP/Scheme-like cons // // pre-terminal nodes are expected to be of the form new cons(null, "string") // function cons(car, cdr) { diff --git a/code/parse.js b/code/parse.js index e3940b49..08ac5f04 100644 --- a/code/parse.js +++ b/code/parse.js @@ -208,8 +208,16 @@ var make_parse = function () { constant("I", make_lam(x, xx)); constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx)))); constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv))); - constant("W", make_lam2(u, v, make_app3(uu, vv, vv))); + + // trush \uv.vu = CI constant("T", make_lam2(u, v, make_app(vv, uu))); + // mockingbird \u.uu = SII + constant("M", make_lam(u, make_app(uu, uu))); + // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I + constant("W", make_lam2(u, v, make_app3(uu, vv, vv))); + // lark \uv.u(vv) = CBM = BWB + constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv)))); + // Y is SLL } make_constants(); diff --git a/lambda_evaluator.mdwn b/lambda_evaluator.mdwn index 4a5b9dc0..c9e21644 100644 --- a/lambda_evaluator.mdwn +++ b/lambda_evaluator.mdwn @@ -19,7 +19,7 @@ Blank lines are fine. *Abbreviations*: In an earlier version, you couldn't use abbreviations. `\x y. y x x` had to be written `(\x (\y ((y x) x)))`. We've upgraded the parser though, so now it should be able to understand any lambda term that you can. -*Constants*: The combinators `S`, `K`, `I`, `C`, `B`, `W`, and `T` are pre-defined to their standard values. Also, integers will automatically be converted to Church numerals. (`0` is `\s z. z`, `1` is `\s z. s z`, and so on.) +*Constants*: The combinators `S`, `K`, `I`, `C`, `B`, `W`, `T`, `M` (aka ω) and `L` are pre-defined to their standard values. Also, integers will automatically be converted to Church numerals. (`0` is `\s z. z`, `1` is `\s z. s z`, and so on.) -- 2.11.0