pathterminuspages/projects/aboutcontactabout me


Untyped Lambda Calculus #6 :: 18-03-2019

 -Untyped Lambda Calculus in JavaScript

The final language can be found in the github repo. Version notes right here:

  • 1.1 : All reminiscent of calling strategies has been removed, since it is unlikely that I will extend on those in this language. Closures have been heavily modified and thus optimized significantly. The interface of the language has been changed, specifically the outf parameter has been removed, and a evalPrg(input) method has been added that returns a record of {error : Bool,res : String, msg : String}. Furthermore for all abstractions the body is reduced. For example we have: $$ \lambda\ a . id\ a\ \rightarrow\ \lambda\ a . a $$ this is done so in order to ease up reading the output.
  • 1.0 : Only call-by-value. Closures seems to work.


  • Done:
    • Closures have been modified. Instead of storing the whole closure within every abstraction, the binder in each abstraction is dealt an address, and each bound variable is dealt a pointer to the given address. Now closures do not accumulate, that is an abstractions closure contains other abstractions and their closures and so on. Instead a single object can contain all pointers and closures. We can do the dealing of addresses and pointers between parsing and evaluating since scopes and closures in this programming language are static.
  • Pending:
    • Closures : The current version is very eager in evaluation. A function like fix needs more lazy evaluation in order to not fire right away.
    • Closures: In order to avoid mutating closures in sub trees values are cloned when obtained from scope/closure. For programs that use recursion, like Church Numerals, this is quite slow. I might optimize when I have time.

Use the app online

You can use this application online in the tools section here.

Use the app on you webpage

You have created your own super cool webpage and so on ... Copy both lcalc.js and stack.js into some directory of you webpage. Include them or copy the code. Remember that stack.js is used by lcalc.js - that is insert the former first. Now say the program you want to evaluate is placed in prg.innerHTML. First define a printing function like this. Define a new instance of llang as so

var llang = new LambdaLang(); var tval = llang.evalPrg(prg.innerHTML); if(tval.error){ document.write("error!"); // in this case tval.msg contains error msg document.write(tval.msg); } else { document.write("success"); // in this case tval.res contains the result document.write(tval.res); }

You might benefit from encapsulating the second line in a try ... catch statement in order to report infinite recursion and other internal errors.

Along with pulling the repo comes the file lcalc.html - this contains a full version of the above you can play around with. Furthermore the file tests.html comes along. In this a series of tests is executed.


You can compress the .js files using some compressor. If you care about the size, you can erase the error message strings found in the actionTable near line 182. Just replace them with empty strings.

CommentsGuest Name:Comment: