An educational project focused on designing and implementing a custom programming language, written entirely in Racket and based on the PLAI-Typed dialect.
The main objective is to write a Turing-Complete programming language.
By "Turing-Complete," we mean the language must theoretically be capable of performing any computation that a Universal Turing Machine can. In this project this is achieved through the presence of these core computational features:
- State and Sequence: The ability to store and mutate data (variables/memory) and execute a sequence of operations.
- Conditional Branching: The mechanism to perform different actions based on conditions (e.g.,
if-then-elselogic). - Iteration/Recursion: The capacity for unbounded repetition, typically implemented via recursion or loops, enabling the possibility of an infinite loop.
- Unbounded Memory: The theoretical capability to access an unlimited amount of memory (ignoring the practical limitations of physical hardware).
The computational pipeline of the werk-lang interpreter follows these steps:
- Parsing (S-Expressions): Racket’s parser reads the input text, breaks it down into S-expressions, and transforms them into the initial Sugar Surface Language (SSL) abstraction.
- Desugaring: The SSL representation undergoes desugaring (or "de-harification"), where all complex, syntactic sugar constructs are translated into a minimal set of core expressions.
- Core Grammar Representation: The resulting minimal language conforms to the tightly defined Core Grammar (Kernel) of the language.
- Interpretation: The expression in the Core Grammar is evaluated by the interpreter to produce a final resulting value (e.g., an integer, a boolean, etc.).