SKI in TS

An implementation of a parser, evaluator, printer, and visualizer for SKI.

Project Dependencies

• TypeScript
• Deno
• AssemblyScript

Development Setup

VS Code Extensions

This project includes VS Code workspace settings that require the following extensions:

• Deno - Official Deno extension for TypeScript support, linting, and IntelliSense

The .vscode/settings.json file configures:

• Enables the Deno extension for this workspace
• Disables the built-in TypeScript language server to avoid conflicts
• Configures Deno linting and import suggestions

Installation

1. Install the Deno extension in VS Code
2. Clone the repository
3. Open the project in VS Code - the workspace settings will automatically apply

Artifacts

• JSR

Testing

Run the test suite:

deno run --allow-read --allow-run scripts/test.ts

Interactive Development

You can experiment with the library interactively using Deno's REPL:

deno repl --allow-read

Quick Start

import {
  parseSKI,
  prettyPrintSKIExpression,
  symbolicEvaluator,
} from "jsr:@maxdeliso/typed-ski";

const expr = parseSKI("(K S) I");
const result = symbolicEvaluator.reduce(expr);
console.log(prettyPrintSKIExpression(result)); // "S"

For a comprehensive library of curated examples, see the JSR module documentation.

Works Referenced

Books

• Combinators: A Centennial View, Stephen Wolfram
• To Mock a Mockingbird, Raymond Smullyan
• Combinatory Logic Volume I, Haskell Brooks Curry & Robert Feys

Papers

• D. A. Turner, "A new implementation technique for applicative languages," Software: Practice and Experience, vol. 9, no. 1, pp. 31-49, 1979. DOI: 10.1002/spe.4380090105
• W. Stoye, T. J. W. Clarke, and A. C. Norman, "Some practical methods for rapid combinator reduction," in Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (LFP '84), ACM, New York, NY, USA, pp. 159-166, 1984. DOI: 10.1145/800055.802038
• H. G. Baker, "CONS should not CONS its arguments, or, a lazy alloc is a smart alloc," ACM SIGPLAN Notices, vol. 27, no. 3, pp. 24-34, 1992. DOI: 10.1145/130854.130858

Status