CODEWITHSUNDEEP
haskell
user224567893
user224567893

Reputation: 656

Interpreter for Forth

I recently started learning Haskell, and I'm trying to write an interpreter for the FORTH language using Haskell. But I'm having problems trying to run the most basic of operations. For example, a simple program in FORTH (taken as a string in Haskell) would be as follows: "1 2 +" returns a stack containing the integer 3, which in Haskell can be represented a list of ints: [3].

I also have functions to push, drop, and pop elements from the stack. I have an addition function to add two elements from the stack.

Now, having these functions at hand, how can I parse the simple program "1 2 +" in order to return [3]? I would expect the example to look like this:

forthInterpreter "1 2 +"
[3]

Any help would be really appreciated. Please let me know if you have any clarification questions. Thanks.

Upvotes: 1

Views: 750

Answers (2)

Cirdec
Cirdec

Reputation: 24156

Every command you have is a function from Stack -> Stack. This makes it easy to interpret commands. I'm using a [Int] as the type of the Stack, with the number on top of the stack at the head of the list.

interpretCommand :: String -> [Int] -> [Int]
interpretCommand "+" = lift2 (+)
interpretCommand "-" = lift2 (-)
interpretCommand "*" = lift2 (*)
interpretCommand "/" = lift2 div
interpretCommand "MOD" = lift2 mod
interpretCommand number = \zs -> read number : zs

where lift2 lifts a 2 argument function to a function on the first 2 elements of a list. The arguments x and y are swapped since forth seems to have the convention that the first argument pushed onto the stack is the first argument to the function and the argument on top of the stack is the second argument to the function.

lift2 :: (a -> a -> a) -> [a] -> [a]
lift2 f (x:y:zs) = f y x:zs
lift2 f _ = error "not enough data on the stack"

To interpret multiple commands, we break them apart with words, which splits a string at whitespace, interpret each command, and compose them all together.

composition :: [a -> a] -> a -> a
composition = foldl (flip (.)) id

interpretCommands :: String -> [Int] -> [Int]
interpretCommands = composition . map interpretCommand . words

Then we can interpret a string of commands by calling interpretCommands and passing it the initial (empty) stack. Here are both of your examples.

main = do
    print $ interpretCommands "1 2 +" []
    print $ interpretCommands "1 2 + 4 - 3" []
    print $ interpretCommands "10 5 / 3" []
    print $ interpretCommands "13 7 MOD 2 / 4 *" []

The output is

[3]
[3,-1]
[3,2]
[12]

Notice that [3,-1] is in the opposite order than you suggested, since 3 is on top of the stack and is therefore at the beginning of the list. (This is the behavior you predicted in your comment in fourthadd.)

Upvotes: 5

Luis Casillas
Luis Casillas

Reputation: 30227

Same answer as Cirdec, but maybe this is a bit easier for a beginner to read:

-- Data type to represent a command.
data Command = Push Int | Add | Subtract deriving Show

-- Type synonym: a Program is a list of commands.
type Program = [Command]

-- Type synonym: a Stack is a list of Int.
type Stack = [Int]

-- The interpreter entry point.
interpretCommands :: String -> Int
interpretCommands str = runProgram (parseProgram str)

-- Parse a string and turn it into the corresponding Program.
parseProgram :: String -> Program
parseProgram str = map toCommand (words str)
    where toCommand "+" = Add
          toCommand "-" = Subtract
          toCommand x = Push (read x)

-- Run a Program on the empty stack, return the result at the top of the result stack.
runProgram :: Program -> Int
runProgram program = head (runProgram' program [])

-- Run a program on a given stack, return the result stack.
runProgram' :: Program -> Stack -> Stack
runProgram' [] stack = stack
runProgram' (command:rest) stack = runProgram' rest (runCommand command stack)

-- Run an individual command.
runCommand :: Command -> Stack -> Stack
runCommand (Push n) stack = n:stack
runCommand Add (n:m:stack) = n+m:stack
runCommand Subtract (n:m:stack) = n-m:stack

I've split out the program into two pieces: parser and runProgram. The first takes the string and converts it into an abstract representation of the program to be run. The second interprets this abstract representation. This is a good separation to use in problems like this; for example, when you desire to write better parsing logic you can modify parser without having to worry about breaking the runProgram logic.

Upvotes: 1

Related Questions