module Main where
...

Our standard library.

initlib = "[succ 1 +]. [even? odd? not]. [double dup +]. [half dup odd? [succ 2 /] [2 /] if]."
-- TODO expand the initlib.

Read and Parse a Nest expression, returing the Nest data structure. We now allow a standard library.

readLine :: String -> Nest
eval :: String -> [Nest]
eval str = bigStep [] e []
  where  Nested e = readLine (initlib ++ " " ++ str)

Our semantics

bigStep :: Env -> [Nest] -> Stack -> [Nest]

Base case. Nothing on execution stack.

bigStep _ [] r = r

BigStep semantics for literals. i.e integers, floats strings and nests evaluate to themselves.

bigStep env (Nested n: xs) ys = bigStep env xs (Nested n: ys)
bigStep env (I i: xs) ys = bigStep env xs (I i: ys)

implement the same for Float, Boolean, and String

BigStep Semantics for addition.

bigStep env (W "+": xs) (I i: I j: ys) = bigStep env xs (I (i+j): ys)
bigStep env (W "*": xs) (I i: I j: ys) = bigStep env xs (I (i*j): ys)
bigStep env (W "-": xs) (I i: I j: ys) = bigStep env xs (I (i-j): ys)
bigStep env (W "/": xs) (I i: I j: ys) = bigStep env xs (F ((fromIntegral i)/(fromIntegral j)): ys)
bigStep env (W ">": xs) (I i: I j: ys) = bigStep env xs (B (i > j): ys)
bigStep env (W "<": xs) (I i: I j: ys) = bigStep env xs (B (i < j): ys)

bigStep env (W "=?": xs) (I i: I j: ys) = bigStep env xs (B (i == j): ys)
bigStep env (W "=?": xs) (S i: S j: ys) = bigStep env xs (B (i == j): ys)
bigStep env (W "=?": xs) (B i: B j: ys) = bigStep env xs (B (i == j): ys)
bigStep env (W "=?": xs) (F i: F j: ys) = bigStep env xs (B (i == j): ys)
bigStep env (W "=?": xs) (Nested i: Nested j: ys) = bigStep env xs (B (i == j): ys)

bigStep env (W "odd?": xs) (I i: ys) = bigStep env xs (B (odd i): ys)

bigStep env (W "and": xs) (B a:B b:ys) = bigStep env xs (B (a && b):ys)
bigStep env (W "or": xs) (B a:B b:ys) = bigStep env xs (B (a || b):ys)
bigStep env (W "not": xs) (B a:ys) = bigStep env xs (B (not a):ys)

implement the same for - : if you have - a b , then the result of (a - b) should be on the stack. same for *. Can you implement it for division? (hint, remember to use F Float for result)

implement the same for dup : duplicate the topmost element.

bigStep env (W "dup": xs) (y:ys) = bigStep env xs (y:y:ys)

implement the same for swap : swap the two topmost elements.

bigStep env (W "swap": xs) (y:y':ys) = bigStep env xs (y':y:ys)

implement the same for pop : remove the topmost element.

bigStep env (W "pop": xs) (y:ys) = bigStep env xs ys

implement cons operator – a:as in haskell

bigStep env (W "cons": xs) (y:Nested y':ys) = bigStep env xs (Nested (y:y'):ys)

implement concat operator – ++ in haskell

bigStep env (W "concat": xs) (Nested y:Nested y':ys) = bigStep env xs (Nested (y ++ y'):ys)

implement empty? for a list.

bigStep env (W "empty?": xs) (Nested y:ys) = bigStep env xs (B (length y == 0):ys)

Remember the i combinator? that is

[1 2] i + == 3
[1 2 +] i == 3

implement the i. - pull out the topmost nesting out of the stack and push it into the execution queue

if then else

bigStep env (W "if":xs) (Nested v2:Nested v1:B c:ys) = bigStep env (res ++ xs) ys
  where res = if c then v1 else v2

Implementing definitions.

bigStep env (W ".":xs) (Nested ((W w):as):ys) = bigStep ((w,as):env) xs ys

bigStep env (W x :xs) ys = bigStep env (def ++ xs) ys
  where Just def = lookup x env

Final case Nothing else matches.

bigStep _ x res = res