Erlang Programming Exercise: 3-8-4 & 3-8-5
I enjoyed coding up 3-8-4 and 3-8-5. It took just a couple hours to finish the pair. In the first one you implement a compiler for a stack machine, in the second you implement the stack machine. There is a lot to think about. How does a stack machine work? What will you be generating? How do the instructions for (3+4)+5 differ from 3+(4+5)? How will the stack machine differ from the evaluator in 3-8-2?
Starting out I looked up stack machine on Wikipedia and found a link to "0-operand" instruction sets that had enough information for me to get going. I decided to keep all of my instructions one token long for simplicity. I have 'add' and 'sub' which use the first two arguments off of the stack, 'umin' (unary minus) only uses the the first item off of the stack. I don't have a need for a 'pop' instruction and decided that 'push' was the default. As an example, adding 1+2 would look like: [1, 2, add]. The numbers would get pushed onto the stack, and then add would take the first two items off of the stack, add them together and place the results back onto the stack.
I may at a later time go back and change the instruction set to have proper push and pop instructions, but for now, this worked.
-module(threeeightyfour).
-export([compile/1]).
translateInstruction(unary_minus) -> umin;
translateInstruction(minus) -> sub;
translateInstruction(plus) -> add.
compileExpression(Instructions, []) ->
Instructions;
compileExpression(Instructions, [{num, Value}|Expressions]) ->
compileExpression([Value|Instructions], Expressions);
compileExpression(Instructions, [{Operator, Value}|Expressions]) ->
Op = translateInstruction(Operator),
OpInstructions = [Op|Instructions],
ValueExp = [Value|Expressions],
compileExpression(OpInstructions, ValueExp);
compileExpression(Instructions, [{Operator, LHS, RHS}|Expressions]) ->
Op = translateInstruction(Operator),
OpInstructions = [Op|Instructions],
RightExp = [RHS|Expressions],
LeftExp = [LHS|RightExp],
compileExpression(OpInstructions, LeftExp).
compileExpression(Expression) ->
compileExpression([], [Expression]).
compile(Results, []) ->
lists:reverse(Results);
compile(Results, [CurrentExpression|Expressions]) ->
Result = compileExpression(CurrentExpression),
compile([Result|Results], Expressions).
compile(Expressions) ->
compile([], Expressions).
And the stack simulator:
-module(threeeightyfive). -export([simulate/1]). simulator([Value|_Stack], []) -> Value; simulator([Value|Stack], [umin|Instructions]) -> UminValue = -1 * Value, simulator([UminValue|Stack], Instructions); simulator([FirstValue|Stack], [sub|Instructions]) -> [SecondValue|MoreStack] = Stack, simulator([FirstValue - SecondValue|MoreStack], Instructions); simulator([FirstValue|Stack], [add|Instructions]) -> [SecondValue|MoreStack] = Stack, simulator([FirstValue + SecondValue|MoreStack], Instructions); simulator(Stack, [Number|Instructions]) -> simulator([Number|Stack], Instructions). simulator(Instructions) -> simulator([], Instructions). simulate(Results, []) -> lists:reverse(Results); simulate(Results, [Instructions|ArraysOfInstructions]) -> Result = simulator(Instructions), simulate([Result|Results], ArraysOfInstructions). simulate(ArraysOfInstructions) -> simulate([], ArraysOfInstructions).
Cheers,
-Halzy
