@thi.ng/sexpr v0.5.39

This project is part of the @thi.ng/umbrella monorepo.

• About
  • Status
  • Related packages
• Installation
• Dependencies
• Usage examples
• API
  • Tokenize only (iterator)
  • AST generation
  • Interpreter
  • Custom syntax
• Authors
• License

About

Basic, but configurable and extensible S-Expression tokenizer, parser, AST builder and runtime / interpreter skeleton for custom, sandboxed DSL implementations.

The following default syntax rules are used:

• whitespace: space, tab, newline, comma
• expression delimiters: (, )
• numbers: any float notation valid in JS, hex ints prefixed w/ 0x
• string delimiters: "

Everything else is parsed as is, i.e. as symbol.

Status

ALPHA - bleeding edge / work-in-progress

Search or submit any issues for this package

Related packages

• @thi.ng/parse - Purely functional parser combinators & AST generation for generic inputs

Installation

yarn add @thi.ng/sexpr

ES module import:

<script type="module" src="https://cdn.skypack.dev/@thi.ng/sexpr"></script>

Skypack documentation

For Node.js REPL:

# with flag only for < v16
node --experimental-repl-await

> const sexpr = await import("@thi.ng/sexpr");

Package sizes (gzipped, pre-treeshake): ESM: 818 bytes

Dependencies

• @thi.ng/api
• @thi.ng/checks
• @thi.ng/defmulti

Usage examples

Several demos in this repo's /examples directory are using this package.

A selection:

API

Generated API docs

Tokenize only (iterator)

The tokenize function returns an iterator of tokens incl. location details. Any whitespace is skipped and whitespace characters are configurable.

[...tokenize(`(* (+ 3 5) 10)`)];
// [
//   { value: '(', line: 0, col: 0 },
//   { value: '*', line: 0, col: 1 },
//   { value: '(', line: 0, col: 3 },
//   { value: '+', line: 0, col: 4 },
//   { value: '3', line: 0, col: 6 },
//   { value: '5', line: 0, col: 8 },
//   { value: ')', line: 0, col: 9 },
//   { value: '10', line: 0, col: 11 },
//   { value: ')', line: 0, col: 13 }
// ]

AST generation

The parse function takes a source string or iterable of tokens and parses it into an AST.

parse(tokenize(`(* (+ 3 5) 10)`));
// or directly from string
parse(`(* (+ 3 5) 10)`);

{
  "type": "root",
  "children": [
    {
      "type": "expr",
      "value": "(",
      "children": [
        {
          "type": "sym",
          "value": "*"
        },
        {
          "type": "expr",
          "value": "(",
          "children": [
            {
              "type": "sym",
              "value": "+"
            },
            {
              "type": "num",
              "value": 3
            },
            {
              "type": "num",
              "value": 5
            }
          ]
        },
        {
          "type": "num",
          "value": 10
        }
      ]
    }
  ]
}

Interpreter

import { Fn2 } from "@thi.ng/api";
import { defmulti, DEFAULT } from "@thi.ng/defmulti";
import { ASTNode, Implementations, Sym } from "@thi.ng/sexpr";

// multi-dispatch fn for DSL builtins
// we will call this function for each S-expression
// and will delegate to the actual implementation based on
// the expression's first item (a symbol name)
const builtins = defmulti<Sym, ASTNode[], any>((x) => x.value);

// build runtime w/ impls for all AST node types
// the generics are the types of: the custom environment (if used)
// and the result type(s)
const rt = runtime<Implementations<any,any>, any, any>({
    // delegate to builtins
    expr: (x, env) => builtins(<Sym>x.children[0], x.children, env),
    // lookup symbol in environment
    sym: (x, env) => env[x.value],
    // strings and numbers evaluate verbatim
    str: (x) => x.value,
    num: (x) => x.value
});

// helper HOF for math ops
const op = (fn: Fn2<number, number, number>) =>
    (_: ASTNode, vals: ASTNode[], env: any) =>
        vals.slice(2).reduce(
            (acc, x) => fn(acc, rt(x, env)),
            rt(vals[1], env)
        );

// add builtins
builtins.addAll({
    "+": op((acc, x) => acc + x),
    "*": op((acc, x) => acc * x),
    "-": op((acc, x) => acc - x),
    "/": op((acc, x) => acc / x),
    count: (_, [__, x]) => rt(x).length
});

// add default/fallback implementation
// to allow calling functions stored in environment
builtins.add(DEFAULT, (x, [_, ...args], env) => {
    const f = env[(<Sym>x).value];
    assert(!!f, "missing impl");
    return f.apply(null, args.map((a) => rt(a, env)));
});

// evaluator
const $eval = (src: string, env: any = {}) =>
    rt(parse(src).children[0], env);

// evaluate expression w/ given env bindings
$eval(`(* foo (+ 1 2 3 (count "abcd")))`, { foo: 10 });
// 100
// i.e. 100 = 10 * (1 + 2 + 3 + 4)

// call env function
$eval(
    `(join (+ 1 2) (* 3 4))`,
    { join: (...xs: any[]) => xs.join(",") }
);
// "3,12"

See test/ for a more in-depth version of this example...

Custom syntax

// define syntax overrides (keep default whitespace rules)
const syntax = {
    scopes: [["<", ">"], ["{", "}"]],
    string: "'"
};

parse(`<nest { a '2' b 3 }>`, syntax);

{
  "type": "root",
  "children": [
    {
      "type": "expr",
      "value": "<",
      "children": [
        {
          "type": "sym",
          "value": "nest"
        },
        {
          "type": "expr",
          "value": "{",
          "children": [
            {
              "type": "sym",
              "value": "a"
            },
            {
              "type": "str",
              "value": "2"
            },
            {
              "type": "sym",
              "value": "b"
            },
            {
              "type": "num",
              "value": 3
            }
          ]
        }
      ]
    }
  ]
}

Authors

Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

@misc{thing-sexpr,
  title = "@thi.ng/sexpr",
  author = "Karsten Schmidt",
  note = "https://thi.ng/sexpr",
  year = 2019
}

License

© 2019 - 2021 Karsten Schmidt // Apache Software License 2.0