We present a minimal interpreter for a tiny Forth-like language in a handful of rules. Wolfram Language’s built-in Dispatch and FixedPointList give us exceptionally simple and effective ways to execute little programs written in this little language.
Etude: Functions as Lists of Rules
Etude: Functions as Lists of Rules
We're very accustomed to writing:
ClearAll[square];square[x_]:=x*x;square[42]
1764
But we can write the same thing this way, with square as a list of rules:
ClearAll[square];square={x_x*x};42/.square
1764
That /. thing is just syntax for ReplaceAll:
ReplaceAll[42,square]
1764
There are two kinds of rules: one where the right-hand side is evaluated at definition time, another where the right-hand side is evaluated at application time. The first kind uses a -> arrow, like this:
ClearAll[myRules];myRules={bar"Cocktail Time!"};bar/.myRules
Cocktail Time!
It's ok to evaluate "Cocktail Time!" when myRules is defined because it doesn't depend on inputs that change at application time. But the second kind uses the :> arrow:
ClearAll[myRules];myRules={x_x*x};42/.myRules
1764
Toccata and Fugue: A Forth Interpreter
Toccata and Fugue: A Forth Interpreter
Forth is one of the grandes dames of programming languages. Along with Lisp and Fortran, it is old yet thriving.
I first heard about Forth as a quick way to bootstrap new control computers for astronomical telescopes. In the 1980’s, I saw a programmer sit down at the console of a new control computer and keyboard in the machine code for a minimal Forth interpreter from her memory. Before lunchtime, she had enough running that she could burp the stepper motors for moving the telescope around. Of course, the “Forth” she keyboarded in was her personal variant, probably not documented anywhere outside her own brain.
The following is a tiny interpreter for a tiny variant of Forth that does a few operations on a stack of values, just like an RPN calculator. It can easily be beefed up into a much more serious programming language. The purpose, here, is to show the technique for implementing such things in the Wolfram Language, to show how short and sweet it can be.
The interpreter consists entirely of lists of rules for stack-to-stack transformations. The stack is an argument to every rule, so they can operate on many stacks at once. Wolfram’s Pattern sub-language suffices to partition the stack into its top one or two elements and the rest of the stack. The first five rules, pushR, popR, dupR, rotR, and swapR, comprise more than enough to get things going. That’s why we claim Forth in Five Lines.
ClearAll[pushR,popR,dupR,swapR,rotR,topR,nextR];(*stack-to-stacktransforms*)pushR={{{stack___},datum_}{datum,stack}};popR={{top_,rest___}{rest}};dupR={{top_,rest___}{top,top,rest}};rotR={{top_,rest___}{rest,top}};swapR={{top_,next_,rest___}{next,top,rest}};(*stack-to-valuetransforms*)topR={{top_,___}top,{}Throw["topR: empty stack"]};nextR={{top_,next_,___}next,({a_}|{})Throw["nextR: deficient stack"]};
Toccata
Toccata
To actually do stuff, we’ll need an actual stack, an instruction stream, and a threaded-code interpreter called microcode. Let’s just do some arithmetic operations along with the rules above. The instruction set will consist of plus, minus, times, div, along with pop, dup, rot, and swap. Push will be implicit, meaning that mentioning an atomic number or symbol will automatically push it. We could do a variant with an explicit push instruction, but it’s not more interesting. We’ll have Mathematica’s Dispatch optimize the list of rules for microcode, and we’ll have Fold and FoldList run a List of microcode instructions until the given program — list of instructions — is exhausted. Grid will display results. Exec, execTrace, execAll, and execAllTrace will be ways to take a stack and a program and run one or more instructions.
ClearAll[instructionSet];instructionSet={plus,times,minus,div,pop,dup,rot,swap};ClearAll[exec,execTrace,execAll,execAllTrace,gridStack,microcode];ClearAll/@instructionSet;microcode=Dispatch@{(*BINARIES*){stack_,plus}With[{r=(stack/.nextR)+(stack/.topR)},{stack/.popR/.popR,r}/.pushR],{stack_,times}With[{r=(stack/.nextR)*(stack/.topR)},{stack/.popR/.popR,r}/.pushR],{stack_,minus}With[{r=(stack/.nextR)-(stack/.topR)},{stack/.popR/.popR,r}/.pushR],{stack_,div}With[{r=(stack/.nextR)/(stack/.topR)},{stack/.popR/.popR,r}/.pushR],(*NULLARIES*){stack_,pop}(stack/.popR),{stack_,dup}(stack/.dupR),{stack_,rot}(stack/.rotR),{stack_,swap}(stack/.swapR),(*UNARY--DEFAULT*){stack_,x_}({stack,x}/.pushR)};exec[stack_,instr_]:={stack,instr}/.microcode;exec[___]:=Throw["bad exec: "<>ToString@{___}];execTrace[stack_,instr_]:=gridStack@exec[stack,instr];execAll[stack_,instrs_]:=gridStack@Fold[exec,stack,instrs];execAllTrace[stack_,instrs_]:=With[{history=FoldList[exec,stack,instrs]},Grid[Partition[Join[{start},Riffle[history,instrs]],2],FrameAll]];gridStack[stack_]:=Grid[{stack},FrameAll]
Top of stack is displayed on the LEFT, bottom on the RIGHT. Here’s a program to subtract two symbols: . Here it is, running.
{a,b,minus}
execAllTrace[{},{a,b,minus}]
start | {} |
a | {a} |
b | {b,a} |
minus | {a-b} |
here are a bunch more of self-explaining programs, now that you’ve got the idea.
execAllTrace[{},{a,b,times}]
start | {} |
a | {a} |
b | {b,a} |
times | {ab} |
execAllTrace[{},{a,b,div}]
start | {} |
a | {a} |
b | {b,a} |
div | a b |
execAllTrace[{},{x,y,z,t,rot,rot,rot}]
start | {} |
x | {x} |
y | {y,x} |
z | {z,y,x} |
t | {t,z,y,x} |
rot | {z,y,x,t} |
rot | {y,x,t,z} |
rot | {x,t,z,y} |
execAllTrace[{},{x,y,z,swap}]
start | {} |
x | {x} |
y | {y,x} |
z | {z,y,x} |
swap | {y,z,x} |
execAllTrace[{3,4},{plus}]
start | {3,4} |
plus | {7} |
execAllTrace[{},{a,b,3,4,plus,rot,div,plus}]
start | {} |
a | {a} |
b | {b,a} |
3 | {3,b,a} |
4 | {4,3,b,a} |
plus | {7,b,a} |
rot | {b,a,7} |
div | a b |
plus | 7+ a b |
Expect exceptions from the next two
Fugue
Fugue
We cheated, above. We used function notation for exec and friends. Now, we don’t cheat. Here it is with rules only — no function notation except in the argument to Mathematica’s built-in FixedPointList.
Top of stack is displayed on the LEFT, bottom on the RIGHT.
Expect exceptions from the next two
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Forth in Five Lines: minimal interpreter for a Forth-like language
by Brian Beckman
Wolfram Community, STAFF PICKS, December 23, 2023
https://community.wolfram.com/groups/-/m/t/3089664
by Brian Beckman
Wolfram Community, STAFF PICKS, December 23, 2023
https://community.wolfram.com/groups/-/m/t/3089664