Sa souvraya niende misain ye · Source
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.
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.
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)
The syntax of Patrim is generally inspired by Modal's, but adds support for various Javascript primitive values:
1
or 2.3
.true
and false
have the expected meanings.null
and undefined
have the expected meanings.?
or !
.\n
.In addition, you can create structured terms -- namely arrays and objects:
(
and )
; terms within are separated by spaces. For instance,
the array [1, 2, "Hello"]
is written (1 2 "Hello")
.{
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.
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.
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.
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.
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
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.