VictorTaelin/lambda-calculus

---

VictorTaelin/lambda-calculus.json

{
  "createdAt": "2016-10-16T15:56:05Z",
  "defaultBranch": "master",
  "description": "A simple, clean and fast implementation of the λ-calculus on JavaScript. ",
  "fullName": "VictorTaelin/lambda-calculus",
  "homepage": "",
  "language": "JavaScript",
  "name": "lambda-calculus",
  "pushedAt": "2020-05-11T19:52:48Z",
  "stargazersCount": 45,
  "topics": [],
  "updatedAt": "2025-03-01T09:51:48Z",
  "url": "https://github.com/VictorTaelin/lambda-calculus"
}

Lambda Calculus

Note: there is a cleaner implementation on the issues, will merge eventually…

A simple, clean and fast implementation of the λ-calculus on JavaScript. It has zero dependencies and only 2.65KB gzipped. It evaluates terms very efficiently by using native JS functions, which is possible thanks to a clever compile/readback algorithm based on JS semantics. It includes the most relevant IO formats - bruijn-indices, binary, base64 and the usual “Wikipedia syntax” - so you can easily export to/from other tools. You can also convert native JS functions to terms and back.

Install

npm install lambda-calculus

Example

const lam = require("lambda-calculus");

// Parses an input with the "Wikipedia syntax". The lambdas are optional
const input = lam.fromString("(λa.λb.(a (a b)) λa.λb.(a (a b)))");

// Computes the result using native JS functions
const output = lam.reduce(input);

// Print the result
console.log("Result: "+lam.toString(output));

// Print the result as bruijn
console.log("Result (in bruijn): "+lam.toBruijn(output));

// Print the result as binary
console.log("Result (in binary): "+lam.toBLC(output));

// Print the result as base64
console.log("Result (in base64): "+lam.toBLC64(output));

// There is a corresponding `lam.fromFormat(str)` for all functions above

Output:

Result: a.b.(a (a (a (a b))))
Result (in bruijn): LL(1 (1 (1 (1 0))))
Result (in binary): 00000111001110011100111010
Result (in base64): EHOc6

API

-- To/from native JS functions
fromFunction : Function -> Term
toFunction   : Term -> Function

-- To/from JS numbers (using the church-encoding)
fromNumber : Number -> Term
toNumber   : Term -> Number

-- To/from the "Wikipedia syntax"
fromString : String -> Term
toString   : Term -> String

-- To/from bruijn-indices
fromBruijn : String -> Term
toBruijn   : Term -> String

-- To/from binary lambda calculus
fromBLC : String -> Term
toBLC   : Term -> String

-- To/from base64-encoded binary lambda calculus
fromBLC64 : String -> Term
toBLC64   : Term -> String

-- Reduces a term to normal form
reduce : Term -> Term
reduce = fromFunction . toFunction