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

Small step semantics

Small step semantics is another way to define the operational semantics of a program. In contrast to the big step semantics, where one is allowed to evaluate multiple things at a time, with small step semantics, you have to evaluate only a single item per rule. Essentially, you continue to apply rules until you reach a final expression.

For example evaluating if expr1 then expr2 else expr3 in big step semantics, one would say that if bigStep(expr1) evaluates to true and if bigStep(expr2) evaluates to val1 then if expr1 then expr2 else expr3 evaluates to val1; if bigStep(expr1) evaluates to false and if bigStep(expr3) evaluates to val2 then if expr1 then expr2 else expr3 evaluates to val3.

In small step semantics, that would be if smallStep(expr1) results in b1 then if expr1 then expr2 else expr3 results in if b1 then expr2 else expr3; similarly if true then expr2 else expr3 results in expr2, and if false then expr2 else expr3 results in expr3;

Can you convert our big step semantics to small step semantics?