Language4
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?