A humane tooling for inhuman logic
This package contains a combinatory logic and lambda calculus parser and interpreter focused on traceability and inspectability.
It is written in TypeScript and JavaScript and can be used in Node.js or in the browser.
A playground and a quest page containing interactive combinatory logic exercises of increasing difficulty are included.
5 x y evaluates to x(x(x(x(x y)))). They must also be space-separated from other terms;x y z is the same as (x y) z or x(y)(z) but not x (y z);x->y->z->expr, which is equivalent to
x->(y->(z->expr)) (aka right associative). Free variables in a lambda expression I x ↦ x // identity;K x y ↦ x //constant;S x y z ↦ x z (y z) // fusion;B x y z ↦ x (y z) // composition;C x y z ↦ x z y // swapping;W x y ↦ x y y //duplication;The special combinator + will increment Church numerals,
if they happen to come directly after it:
+ 0 // 12 + 3 // -> +(+(3)) -> +(4) -> 5The term + 0 idiom may be used to convert
numbers obtained via computation (e.g. factorials)
back to human readable form.
Applications and native terms use leftmost-outermost strategy, i.e. the first term in the tree that has enough arguments is executed and the step ends there.
Lambda terms are lazy, i.e. the body is not touched whatsoever until all the free variables are bound. This is consistent with combinator behavior under LO order.
This page contains small combinatory logic exercises of increasing (hopefully) difficulty. Each task requires the user to build a combinator with specific properties. New combinators are unlocked as the user progresses.
npm install @dallaylaen/ski-interpreter
bin/ski.js - also available as npx ski - contains several subcommands:
repl - Start an interactive REPL
--verbose - Show all evaluation steps!help in REPL):
!ls - List all defined terms!help - Show available commandseval <expression> - Evaluate a single expression
--verbose - Show all evaluation stepsski eval "S K K x"file <filepath> - Evaluate expressions from a file
--verbose - Show all evaluation stepsski file script.skiinfer <expression> - try to find equivalent lambda expression and display its properties if found.
extract <expression> <known term> ... -
Replace parts of the expression that are equivalent to the known terms with the respective terms. Known terms must be normalizable.
search <expression> <known term> ... -
Attempt to brute force an equivalent of the expression using only the known terms.
Only normalizable terms are currently supported.
quest-lint <files...> - Validate quest definition files
--solution <file> - Load solutions from a JSON file for verificationski quest-lint quest1.json quest2.json --solution solutions.jsonIf no subcommand is provided, help is displayed.
Running SKI_REPL=1 node -r @dallaylaen/ski-interpreter/bin/ski.js
will start a node shell with the SKI class available as a global variable.
See the complete API reference for gory details.
#!node
const { SKI } = require('@dallaylaen/ski-interpreter');
// Create a parser instance
const ski = new SKI();
// Parse an expression
const expr = ski.parse(process.argv[2]);
// Evaluate it step by step
for (const step of expr.walk({max: 100})) {
console.log(`[${step.steps}] ${step.expr}`);
}
const { SKI } = require('@dallaylaen/ski-interpreter');
const ski = new SKI();
const expr = ski.parse(src);
// evaluating expressions
const next = expr.step(); // { steps: 1, expr: '...' }
const final = expr.run({max: 1000}); // { steps: 42, expr: '...' }
const iterator = expr.walk();
// applying expressions
const result = expr.run({max: 1000}, arg1, arg2, ...);
// same as
expr.apply(arg1).apply(arg2).run();
// or simply
expr.apply(arg1, arg2).run();
// equality check
ski.parse('x->y->x').equals(ski.parse('a->b->a')); // true
ski.parse('S').equals(SKI.S); // true
ski.parse('x').apply(ski.parse('y')).equals(ski.parse('x y')); // also true
// defining new terms
ski.add('T', 'CI'); // T x y = C I x y = I y x = y
ski.add('M', 'x->x x'); // M x = x x
// also with native JavaScript implementations:
ski.add('V', x=>y=>f=>f.apply(x, y), 'pair constructor');
ski.getTerms(); // all of the above as an object
// converting lambda expressions to SKI
const lambdaExpr = ski.parse('x->y->x y');
const steps = [...lambdaExpr.toSKI()];
// steps[steps.length - 1].expr only contains S, K, I, and free variables, if any
// converting SKI expressions to lambda
const skiExpr = ski.parse('S K K');
const lambdaSteps = [...skiExpr.toLambda()];
// lambdaSteps[lambdaSteps.length - 1].expr only contains lambda abstractions and applications
expr.format(options?) converts an expression to a string with fine-grained
control over notation. Called without arguments it is equivalent to
expr.toString().
const expr = ski.parse('S K K');
expr.format() // 'S K K' (default, terse)
expr.format({ terse: false }) // 'S(K)(K)' — every argument gets parentheses
expr.format({ html: true }) // HTML-safe: free vars wrapped in <var>,
// '->' becomes '->', fancyName used when set
// Custom lambda notation
expr.format({ lambda: ['', '=>', ''], terse: false }) // JavaScript style
expr.format({ lambda: ['λ', '.', ''] }) // math style
expr.format({ lambda: ['(', '->', ')'], around: ['(', ')'], brackets: ['', ''] })
// Lisp style, still parseable
// Redex highlighting (e.g. for step-by-step HTML output)
ski.parse('I x').format({ html: true, redex: ['<b>', '</b>'] })
// '<b>I</b> <var>x</var>'
// inventory: show listed aliases by name, expand everything else
const { T } = ski.getTerms();
expr.format({ inventory: { T } }) // keeps T as 'T', expands any other aliases
The brackets, var, around, and redex options each take a [open, close]
pair of strings; lambda takes a [prefix, separator, suffix] triple.
expr.diag() will instead output an indented expression tree (breadth-first)
with class information and variables labeled for disambiguation.
By default, parsed free variables are global and equal to any other variable with the same name. Variables inside lambdas are local to said lambda and will not be equal to anything except themselves.
A special scope argument may be given to parse to limit the scope. It can be any object.
const scope1 = {};
const scope2 = {};
const expr1 = ski.parse('x y', {scope: scope1});
const expr2 = ski.parse('x y', {scope: scope2}); // not equal
const expr3 = ski.parse('x y'); // equal to neither
const expr4 = ski.parse('x', {scope: scope1}).apply(ski.parse('y', {scope: scope1})); // equal to expr1
Variables can also be created using magic SKI.vars(scope) method:
const scope = {};
const {x, y, z} = SKI.vars(scope); // no need to specify names
Expressions are trees, so they can be traversed.
expr.any(e => e.equals(SKI.S)); // true if any subexpression is S
expr.traverse(e => e.equals(SKI.I) ? SKI.S.apply(SKI.K, SKI.K) : null);
// replaces all I's with S K K
// here a returned `Expr` object replaces the subexpression,
// whereas `null` means "leave it alone and descend if possible"
expr.fold(0, (acc, e) => acc + (e.equals(SKI.K) ? acc+1 : acc));
// counts the number of K's in the expression
The Quest class may be used to build and execute test cases for combinators.
const { Quest } = require('@dallaylaen/ski-interpreter');
const q = new Quest({
name: 'Test combinator T',
description: 'T x y should equal y x',
input: 'T',
cases: [
['T x y', 'y x'],
],
});
q.check('CI'); // pass
q.check('a->b->b a'); // ditto
q.check('K'); // fail
q.check('K(K(y x))') // nope! The variable scopes won't match
See also the quest guide for more details on building your own quests or even interactive quest pages.
lib/ski-interpreter.cjs.js - main entry point for Node.js;lib/ski-interpreter.esm.js - main entry point for ES modules;lib/ski-interpreter.min.js - minified version for browsers;lib/ski-quest.min.js - script with the interpreter
plus QuestBox, QuestChapter, and QuestPage classes
for building interactive quest pages from JSON-encoded quest data;bin/ski.js - a CLI REPL;types - TypeScript type definitions.traverse prototype.This software is free and available under the MIT license.
© Konstantin Uvarin 2024–2026