Я ☞ Tutorials ☞ Stack machine interpeter - 1

Stack machine is a processor that uses stack data structure to store operands. Here we are going to implement a simple interpreter first and gradually adding new features we and up with something interesting.

Our interpreter consumes two types of commands:

type Immediate v = v
type Operation v = v `LM` v `AR_` v

type Command v = Immediate v `ML` Operation v

pattern Operation x = This x
pattern Immediate x = That x

For this program we need to use effects:

• State for storing a List of operands and pushing back results
• Halts in case if there are not enough operands to perform an operaton

type Processing v = State `WR` List v `JNT` Halts

We either immediately push a value to the stack or evaluate an operation. Operation instruction consumes two operands by taking topmost values from the stack, evaluate operation itself and push result back to the stack. Yes, we are going to use methods of Stack interface here:

load value = enter @(State `WR` List _ `JNT` Halts)
 `yuk_` New `ha` State `ha` Transition `hv` push @List value

eval binop = enter @(State `WR` List _ `JNT` Halts)
 `yuk_` New `ha` State `ha` Transition `hv` pop @List
 `lu'yp` New `ha` State `ha` Transition `hv` pop @List
 `yok_` Try `ha` Maybe `ha` (`yip'yo` binop)
 `yok_` New `ha` State `ha` Transition `ha` push @List

As an example, we can provide a sequence of commands that should be performed without errors:

initial = Construct
 `ha` (Item `hv` Immediate 1) `ha` Maybe `ha` Next
 `ha` (Item `hv` Immediate 2) `ha` Maybe `ha` Next
 `ha` (Item `hv` Operation ((+) `hj`)) `ha` Maybe `ha` Next
 `ha` (Item `hv` Immediate 4) `ha` Maybe `ha` Next
 `ha` (Item `hv` Operation ((+) `hj`)) `ha` Maybe `hv` Last

We are ready to test it now.

main = error `la` this `he'ho` trace
 `hv_______` initial `yokl` Forth `ha` Run `ha__` load `la` eval
 `he'he'hv___` Empty @List Unit where

Full source code is available here.