This folder contains experiments used to guide Element development. Currently the focus is on an Element interpreter, written in Python to prioritize quick iteration over run-time performance.
This file defines the language’s keywords, punctuation, and built-in syntax.
The Ast class defines an abstract syntax tree (AST) node and its pretty-printer.
An Ast node is a (required) name and (optional) children.
These are accessible by field names (Ast.name and Ast.children) or by tuple index (x.name is x[0]).
This duality enables pattern matching Ast nodes as tuples.
This module breaks an input string into a list of values, where each value is either a string or a tuple of strings. When the scanner encounters strand notation, it groups all the elements of the strand into a list of strings:
2+3⇒['2', '+', '3']1 2+3 4⇒[['1', '2'], '+', ['3', '4']]2+`a`b``c⇒['2', '+', ['`a', '`b', '`', '`c']]"a" "hello""""world"⇒['"a"', '"hello"', '""', '"world"']
Numbers separated by spaces form strands, but spaces are optional in symbol or string strands.
A backtick (`) not followed by a letter or double-quote is equivalent to `"".
Stranding two strings without spaces as in “hi”“world” results in the list ["hi", "world"].
Strands are lightweight and optional syntax to create 1-dimensional lists.
You can create a 1-d list without stranding with the “join” primitive function: 1,2 ⇒ ['1', '2'], while nested lists always require parentheses as in (1;(2;3);4).
This parser is a bottom-up style parser originally inspired by the Double-E method. After a while I removed the operator precedence logic from this parser since K operators have uniform precedence.
A large portion of this parser now deals with juxtaposition, projection, and composition within the context of the usual application of values to operators, function calls, and parentheses.
- juxtaposition (implied application)
a b c⇒(a (b c))()()⇒((lst NIL) (lst NIL))f[x][y]⇒((f (prg x)) (prg y))a 2-b 3⇒(a (- 2 (b 3)))
- projection (partial application)
2+⇒(prj + 2)"a",⇒(prj , "a")
- composition
+-⇒(cmp + (prj -))(note-treated as a partial application with both arguments missing)a+*b-⇒(cmp (prj + a) (cmp * (prj - b)))
- infix and prefix application
a+*b-1⇒(+ a (* (- b 1)))+-^a⇒(+ (- (^ a)))
The job of the parser is to disambiguate the number of arguments to operators.
For example +2*b- contains 3 operators (“+”, “*”, and “-“), each of which has either a unary/prefix meaning or a binary/infix meaning depending on context.
However, the above results in the AST (cmp + (cmp (prj * 2) (prj - b))) because the “rule” is that a trailing operator is infix, and so we can recognize the suffix b- as a projection (prj - b).
From there we work backward and see *, which is infix because it has a left operand 2, resulting in another projection (prj * 2).
The goal of the parser in this situation is to preserve the fact that - is missing an argument, so any time a prj node is composed with other operators, the parent node becomes a composition.
These two projections form a composition, and finally the leading + must be a prefix operator because it has no left argument.
Again we preserve the partial application information by making the root node a cmp.
One thing the parser does not do is validate the shape or type of arguments to operands.
For example "ab"/3 is not defined by the language but still parses as ((fld "ab") 3).
The evaluator will handle this task.
Semantic analysis passes are in this file. Type inference occurs here, as do a few assorted odds and ends like converting projections into lambdas to make the internal representation more uniform. For now, these passes are implemented in the traditional recursive style. One day I would like to try a more data-oriented approach (e.g. using Apter trees), but as I’m more familiar with the recursive formulation it’s going to be my first attempt. Walk before you run, right?
This section is TBD.
- Interesting paper: https://arxiv.org/pdf/1109.0781
- Interesting statically typed compiled language: https://aardappel.github.io/lobster/README_FIRST.html
This file aims to include unit tests for the major parts of the prototype. Currently it has about 100 parser tests comparing a string input with expected Ast output.
This section is TBD but here are some potentially useful links: