(This page might be a bit more readable if you enable 1st-party CSS.)

Patrim is a goofy little term rewriting language, implemented in Typescript.

Patrim was written for fun, and to learn a bit more about term rewriting systems. Perhaps a production quality term rewriting language that was well integrated with the wider JS/web ecosystem could be useful; Patrim is not that language.

Installation

You can install the Patrim interpreter from NPM:

$ npm -g install patrim

There's also a VS Code extension the provides some simple syntax highlighting.

Language

Let's get started with the canonical example, Hello, world!

// Define a symbol for the string "Hello, world!"
:: hello "Hello, world!"

// Repeat something `n` times.
:: (repeat 0 ?s) undefined
:: (repeat ?n:number ?s) (
  ?s ;
  repeat (?n - 1) ?s
)

repeat 3 (#print hello)

Syntax

The syntax of Patrim is generally inspired by Modal's, but adds support for various Javascript primitive values:

• Numbers, like 1 or 2.3.
• true and false have the expected meanings.
• null and undefined have the expected meanings.
• Registers, which are prefixed with ? or !.
• Strings are surrounded by double quotes, and support simple escapes like \n.
• All other words are treated as strings as well (but escapes aren't supported).

In addition, you can create structured terms -- namely arrays and objects:

• Arrays are created using ( and ); terms within are separated by spaces. For instance, the array [1, 2, "Hello"] is written (1 2 "Hello").
• Objects are created using { and }; key/value pairs are separated by spaces, as are keys and their associated values. So the object { a: 1, b: "Two" } is written { a 1 b Two }.

At the top-level of a program, terms are separated by newlines and are implicitly wrapped in parens when that would be necessary. Hence each of the lines in the following program represent the same term:

Hello, world 42
"Hello," "world" 42
(Hello, world 42)
("Hello," "world" 42)

Because the first lines implicitly create an array, as they consist of multiple terms, whereas the second two lines are each a simple term, and do not require an implicit array to be valid. This means if you want to write a 1 element array at the top-level of your program, you must wrap it in explicit parens, but otherwise top-level terms should mostly "just work".

A program, therefore, is an array of terms, some of which may be primitive, and others structures like arrays or objects.

Semantics

Patrim evaluation proceeds by repeatedly rewriting the terms comprising a program using a set of rules, until no rules apply, at which point evaluation terminates. As a program consists of an array of terms, we rewrite each top-level term in a program in order.

By default Patrim comes with a number of "builtin" rules. The most important of these is #add-rule, which adds a new rule to the evaluation context:

#add-rule answer 42
#add-rule (question ?r) answer

question "Life, the universe, and everything."

Other useful builtins include #global, which rewrites to globalThis, #get and #set for working with object properties, #try and #throw for working with exceptions, and various binary operators like + and -:

// Gets `globalThis.navigator.version`.
#get (#get #global navigator) version

// Evaluates to the thrown exception, `TypeError`.
#try (#get undefined "invalidProperty")

// Evaluates to 3.
1 + 2

The set of builtin rules can be customized when instantiating the execution Context; see "Typescript Interface".

In addition to the builtins, by default the prelude is loaded as well, which provides a number of additional conveniences, including line comments (which are in fact not part of the syntax of Patrim), and shorthands for defining rules and accessing object properties, and invoking methods.

#global . alert ( "Hello, world!" )

Patrim uses the leftmost-outermost reduction strategy by default. This can be changed to leftmost-innermost by instantiating a Context manually; see "Typescript Interface". Rules are matched in order that they were added to the context.

Registers

Like Modal, rules can contain registers that bind subterms. By default, simple registers (of the form ?a or ?foo, for instance) match any term. They can be restricted to instead match only terms of a particular primitive type -- ?n:number -- or terms of a particular prototype -- ?node:DOMNode.

Registers by default are lazy, but can also be eager, written !r instead of ?r. Eager registers completely evaluate matching terms if the entire rule matches. They can be used to enforce a particular evaluation order.

Registers generally match a single term. In an array one can use a splat register, which matches "the rest of the array", using ?* or !* instead of ? or !. Currently splats are only supported as the last element of an array, and are unsupported in object literals.

Interfacing with Javascript

The builtins include the implicit invocation builtin, which looks something like the following, in pseudo-syntax:

:: (?fn:function ?args:array) <call fn(...args)>

(Of course the < ... > bit is not valid Patrim).

This allows straightforward integration with Javascript functions. For instance, as shown in the previous alert example, one can invoke alert as simply as #global . alert ("Oh no!") -- because #global . alert is rewritten to the JS function alert, and then the implicit invocation rule matches a function followed by an array, and invokes the function with the array as arguments.

Interpreter

The main way to run Patrim programs is with pc, the Patrim interpreter.

Use pc --help for complete usage information.

$ pc --help
Usage: pc [options] <file>...
Options:
  -i, --interactive       start an interactive session
  -H, --history           path to the history file for interactive mode
  --showDerivation        show final derivation
  --noPrelude             do not include the prelude
  --noBuiltins            do not include built-in rules
  --debug                 enable debug mode
  -v, --version           show version information
  -h, --help              show this help message

Typescript Interface

The Patrim library exposes a few key functions and classes:

declare function parse(input: string): Program;
declare function evaluate(program: Program, context?: Context): Term[];
declare function execute(program: Program, context?: Context): Term;

Runtime terms are simply arbitrary JS values. The only terms that are treated specially at runtime are instances of the Register class, which handles pattern binding during term rewriting.