X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=lambda_evaluator.mdwn;h=d39086fd257131bb012c1fa5f71191c387c23927;hp=d46fc78577d3884c031e3f8446185283ddb3568a;hb=a9fc616a72a86be53a9ce7289fa3608799b44956;hpb=eb2a14f6c7111e6c308b72dd0e8567e4296fcfe0 diff --git a/lambda_evaluator.mdwn b/lambda_evaluator.mdwn index d46fc785..d39086fd 100644 --- a/lambda_evaluator.mdwn +++ b/lambda_evaluator.mdwn @@ -1,6 +1,3 @@ -Lambda Evaluator ----------------- - This lambda evaluator will allow you to write lambda terms and evaluate (that is, normalize) them, and inspect the results. (This won't work in Racket, because Racket doesn't even try to represent the internal structure of a function in a human-readable way.) @@ -22,8 +19,9 @@ 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.) +*Variables*: Variables must start with a letter and can continue with any sequence of letters, numbers, `_`, `-`, or `/`. They may optionally end with `?` or `!`. When the evaluator does alpha-conversion, it may change `x` into `x'` or `x''` and so on. But you should not attempt to use primed variable names yourself. +do eta-reductions too @@ -78,7 +77,7 @@ Object.prototype.error = function (message, t) { var parse = make_parse(); function go(source) { - var string, tree, expr; + var string, tree, expr, eta; try { tree = parse(source); // string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4); @@ -86,7 +85,8 @@ Object.prototype.error = function (message, t) { // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4); // string = expr.to_string() + "\n\n~~>\n\n"; string = ''; - string = string + reduce(expr, false, false).to_string(); + eta = document.getElementById('ETA').checked; + string = string + reduce(expr, eta, false).to_string(); } catch (e) { string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4); @@ -120,6 +120,25 @@ The code is based on: * [Oleg Kiselyov's Haskell lambda calculator](http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell). * The top-down JavaScript lexer and parser at . -Improvements we hope to add soon: the ability to reduce Combinatory Logic combinators and report the result as combinators, rather than in lambda forms. +Improvements we hope to add: + +* detecting some common cases of non-normalizing terms (the problem of determining in general whether a term will normalize is undecidable) +* returning results in combinator form (the evaluator already accepts combinators as input) +* displaying reductions one step at a time +* specifying the reduction order and depth +* allow other binders such as ∀ and ∃ (though these won't be interpreted as doing anything other than binding variables) + + +Other Lambda Evaluators/Calculutors +----------------------------------- + +* [Peter Sestoft's Lambda Calculus Reducer](http://www.itu.dk/people/sestoft/lamreduce/index.html): Very nice! Allows you to select different evaluation strategies, and shows stepwise reductions. +* [Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda) +* [Penn Lambda Calculator](http://www.ling.upenn.edu/lambda/): Pedagogical software developed by Lucas Champollion, Josh Tauberer and Maribel Romero. Linguistically oriented. Requires installing Java (Mac users will probably already have it installed). +* [Mike Thyer's Lambda Animator](http://thyer.name/lambda-animator/): Graphical tool for experimenting with different reduction strategies. Also requires installing Java, and Graphviz. +* [Matt Might's Lambda Evaluator](http://matt.might.net/articles/implementing-a-programming-language/) in Scheme (R5RS and Racket). + +See also: +* [Jason Jorendorff's Try Scheme](http://tryscheme.sourceforge.net/about.html): Runs a miniature Scheme interpreter in Javascript, in your browser.