TS-Expression

TypeScript constructor of symbolic expressions.

_{<1kB | no deps | tree-shakeable | side-effect free}

This library provides a minimal yet powerful implementation of Lisp's symbolic expressions (s-expressions) for TypeScript. By starting with these fundamental building blocks, you can create immutable, composable data structures that work well with functional programming patterns. The library's simplicity makes it easy to understand and extend, while its type-safety ensures reliability in larger applications.

Installation

Via npm:

# npm
npm install ts-expression

You can also use your favorite package manager:

# deno
deno add jsr:@lambda/ts-expression

# pnpm
pnpm add ts-expression

# bun
bun add ts-expression

# yarn
yarn add ts-expression

Examples

Representing 2D Points

import { car, cdr, cons } from "ts-expression";

type Point = typeof makePoint;

const makePoint = (x: number, y: number) => cons(x, y);
const getX = (point: Point) => car(point);
const getY = (point: Point) => cdr(point);

const getSymmetricalPoint = (point: Point) => {
  const x = getX(point);
  const y = getY(point);
  return makePoint(-x, -y);
};

const calculateDistance = (point1: Point, point2: Point) => {
  const [x1, y1] = [getX(point1), getY(point1)];
  const [x2, y2] = [getX(point2), getY(point2)];
  return Math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2);
};

const point1 = makePoint(3, 4);
const point2 = makePoint(0, 0);

getX(point1); // 3
getY(point2); // 0
getSymmetricalPoint(makePoint(1, 5)); // makePoint(-1, -5)
calculateDistance(makePoint(-2, -3), makePoint(-4, 4)); // ≈ 7.28

Building a Binary Tree

import { cons, car, cdr } from "ts-expression";

const leaf = <T>(value: T) => cons(value, cons(null, null));

const node = <N, L, R>(value: N, left: L, right: R) => {
  return cons(value, cons(left, right));
};

const tree = node(
  "root",
  node("left", leaf("left-left"), leaf("left-right")),
  node("right", leaf("right-left"), leaf("right-right")),
);

car(tree); // "root"
car(car(cdr(tree))); // "left"

File System path representation

import { cons, car, cdr } from "ts-expression";

const node = <A, B>(a: A, b: B) => cons(a, b);

const fs_tree = node(
  "dir:root",
  node(
    node("dir:usr", node("dir:bin", node("dir:etc", "file:readme.txt"))),
    node("dir:opt", node("dir:vol", node("dir:tmp", "file:script.sh"))),
  ),
);

const cdaar = car(car(cdr(fs_tree)));
const cdadar = car(cdr(car(cdr(fs_tree))));
const cdadddr = cdr(cdr(cdr(car(cdr(fs_tree)))));
const cddar = car(cdr(cdr(fs_tree)));

Mnemonic

The general rule for c[a/d][a/d][a/d][a/d]r functions:

• read from right to left (just like function composition)
• a stands for car (access the first element)
• d stands for cdr (drop the first element)

Basic Patterns

Function	Equivalent Expression	Meaning
(car X)	(first X)	First element
(cdr X)	(rest X)	Everything except the first element
(cadr X)	(car (cdr X))	Second element
(cddr X)	(cdr (cdr X))	Drops first two elements
(caddr X)	(car (cdr (cdr X)))	Third element
(cdddr X)	(cdr (cdr (cdr X)))	Drops first three elements

Origin

This library provides a TypeScript implementation of symbolic expressions (S-expressions), which are a fundamental data structure in Lisp programming languages. S-expressions originated in the 1950s with John McCarthy's work on Lisp and have since become an elegant foundation for functional programming.

The core of S-expressions is the cons cell - a simple pair that holds two values. This primitive structure can be used to build complex data structures like lists, trees, and graphs. The operations to access the parts of a cons cell are traditionally called:

• car (Contents of Address Register) - retrieves the first/left element
• cdr (Contents of Decrement Register) - retrieves the second/right element

These peculiar names are historical artifacts from the IBM 704 computer on which Lisp was first implemented.

License

Made by a human being, not LLM.

Copyright © 2024 Roman Hnatiuk

Licensed under MIT.