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