`ast`

Generic abstract syntax tree - node creation, children, visitor, map transform, filter, depth, size, and pretty-print.

Load with: use ast

What this module does

ast gives you a simple, general-purpose tree structure for building and working with abstract syntax trees or any other recursive tree of typed nodes. Each node has a type string (t), optional extra properties, and an optional ch list of child nodes.

The module provides the standard tree primitives: visit every node depth-first, map a function over the whole tree producing a new tree, filter nodes by a predicate, measure depth and total node count, and pretty-print with indentation.

Both raw function names (astnd, astvi, etc.) and clean ast.* aliases are available.

Quick example

use ast

# Build a small expression tree
root = ast.nd("add", {})
left = ast.nd("num", {val: 1})
right = ast.nd("num", {val: 2})
root = ast.add(root, left)
root = ast.add(root, right)

# Visit every node
ast.vis(root, \(n) prn(n.t))
# add
# num
# num

# Count nodes
prn(ast.sz(root))   # 3
prn(ast.dep(root))  # 1

# Pretty-print
prn(ast.pp(root, 0))

Functions

Node construction

astnd(tp, props) / ast.nd(t, p)

Creates a new node with type string tp and properties from the props object. If props is nil, the node has only a t field. Returns the node object.

astad(node, child) / ast.add(n, c)

Appends child to node's ch list. Creates the ch list if it doesn't exist yet. Returns the updated node.

astch(node)

Returns the node's children list, or an empty list if the node has no ch field.

Tree traversal

astvi(node, fn) / ast.vis(n, f)

Visits every node in the tree depth-first (pre-order), calling fn(node) on each. Returns the root node unchanged. Use this for side effects - reading values, printing, accumulating into an outer variable.

astmp(node, fn) / ast.map(n, f)

Maps a transform function over every node, producing a new tree. fn receives a node and returns a (possibly different) node. Children are recursively mapped after the parent is transformed. Returns the new root.

astfl(node, pred) / ast.flt(n, p)

Returns a flat list of all nodes in the tree (via astvi) for which pred(node) is truthy.

astfn(node, tp) / ast.find(n, t)

Returns all nodes whose type string t matches tp. Shorthand for astfl with a type-equality predicate.

Tree metrics

astdp(node) / ast.dep(n)

Returns the depth of the deepest path in the tree. A leaf node has depth 0; a node with one level of children has depth 1.

astsz(node) / ast.sz(n)

Returns the total number of nodes in the tree, including the root and all descendants.

Pretty-printing

astpp(node, indent) / ast.pp(n, i)

Returns the tree as an indented string. Each node is printed as its type followed by any non-t, non-ch properties as key=value pairs. Children are indented 2 spaces further. Pass 0 (or nil) for indent at the root.

Notes

Nodes store their type in field t and children in field ch. All other fields are your own properties.
astvi is pre-order (parent before children). There is no post-order traversal in the current implementation.
astmp transforms the parent node first, then recursively maps over the (possibly new) children.
Use the ast.* aliases for clarity in larger programs: ast.nd, ast.add, ast.vis, ast.map, ast.flt, ast.find, ast.dep, ast.sz, ast.pp.