CODEWITHSUNDEEP
haskellfunctional-programming
Peter Braun
Peter Braun

Reputation: 45

Haskell - functions as an input to a function

I am looking at this code for a small step WHILE interpreter, and I am trying to understand how to run it. Specifically, I am confused about the State type. It seems to be a type of function - Does that mean that a function that is of type State = Var->Val has to be defined somewhere, and that function needs to be passed to the functions that require it?

At the same time, I see that the state should be modifiable by variable assignments. How does the upd function work, if it is only passed in a function that is of type Var->Val?

Thanks for your help! I can't seem to find anything about this on the tutorials or on stackoverflow.

type Var = Integer
type Val = Integer
type State = Var -> Val


--takes a var, returns a val. Here, we use an integer to describe a
-- variable as opposed to a string.
lkp :: Var -> State -> Val
lkp x s = s x

upd :: Var -> Val -> State -> State
upd x v s = \y -> if x == y then v else s y

data AExp = N Integer | V Var
            | AExp :+ AExp | AExp :- AExp | AExp :* AExp
   deriving (Show)

aexp :: AExp -> State -> Integer
aexp (N z) _ = z
aexp (V x) s = lkp x s
aexp (a0 :+ a1) s = aexp a0 s + aexp a1 s
aexp (a0 :- a1) s = aexp a0 s - aexp a1 s
aexp (a0 :* a1) s = aexp a0 s * aexp a1 s

data BExp = TT | FF | AExp :== AExp | AExp :<= AExp
            | Not BExp | BExp :&& BExp | BExp :|| BExp
   deriving (Show)

bexp :: BExp -> State -> Bool
bexp TT _ = True
bexp FF _ = False
bexp (a0 :== a1) s = aexp a0 s == aexp a1 s
bexp (a0 :<= a1) s = aexp a0 s <= aexp a1 s
bexp (Not b) s = not (bexp b s)
bexp (a0 :&& a1) s = bexp a0 s && bexp a1 s
bexp (a0 :|| a1) s = bexp a0 s || bexp a1 s

data Stmt = Skip | Stmt :\ Stmt | Var := AExp
            | If BExp Stmt Stmt | While BExp Stmt

data Trace = Nil State | Delay State Trace

--reduces the statement by one step.
red :: Stmt -> State -> Maybe (Stmt, State)
red Skip s = Nothing
red (x := a) s = Just (Skip, upd x v s) where v = aexp a s
red (stmt0 :\ stmt1) s =
    case red stmt0 s of
        Just (stmt0', s') -> Just (stmt0' :\ stmt1, s')
        Nothing -> red stmt1 s
red (If b stmt0 stmt1) s =
    if bexp b s then
        Just (stmt0, s)
    else Just (stmt1, s)
red (While b stmt0) s =
    if bexp b s then
        Just (stmt0 :\ While b stmt0, s)
    else Just (Skip, s)

norm :: Stmt -> State -> Trace
norm stmt s =
    case red stmt s of
        Nothing -> Nil s
        Just (stmt', s') -> Delay s (norm stmt' s')

Upvotes: 2

Views: 118

Answers (1)

Ingo
Ingo

Reputation: 36339

You can think of the State type as an environment where you can look up variables. You can start with an "empty" environment like so:

emptyState v = error ("variable " ++ show v ++ " is unknown")

As far as I can see, the environment is updated every time the interpreter sees a

var := value

construct. That is, after

V 23 := 42

the state function that is used in subsequent statements will look like:

state1 v = if v == 23 then 42 else emptyState v

Interestingly, the set up of the emptyState function determines important semantic properties of the interpreted language. The emptyState above, for example, forbids undefined variables. But it would be as well possible to come up with a variant that treats all undefined variables as 0, or 1, or 42.

Upvotes: 2

Related Questions