My professor has given us a question after talking about the difference between lexical and dynamic scope. He presented us a simple evaluator (of a fictional language) coded in Haskell. The following is the code:
type Var = ...
type Env = ...
data Val = Vnum Int
| Vfun Var Exp
data Exp = Enum Int
| Evar Var
| Efun Var Exp
| Ecall Exp Exp
| Elet Var Exp Exp
-- Predefined. Find the correspondent value of a variable
env_lookup :: Env -> Var -> Val
...
-- Predefined. Add the variable and its associated value to the environment
env_add :: Env -> Var -> Val -> Env
...
eval env (Enum n) = Vnum n
eval env (Evar x) = env_lookup x env
eval env (Ecall fun actual)
= case (eval env fun) of
Vnum n -> error "Not a Function!"
Vfun formal body ->
eval (env_add env formal (eval env actual)) body
-- To be completed --
The question asks:
Does this implemented language use lexical scope or dynamic scope? And how should we change the code so it will has another type of scope
Frankly, this is a very hard question. It is easy to see, from the code, whether this language implements "call-by-name" or "call-by-value" (Which in this case, it is "call-by-value"). But analyzing whether it is dynamic or lexical scope is another story
Your code is incomplete:
eval env (Ecall fun actual)
= case fun of
Vnum n -> error "Not a Function!"
Vfun formal body ->
eval (env_add env formal (eval actual)) body
^^^^^
An argument is missing. But you have only one option to fix it, to add env there.
Then the meaning becomes, evaluate body in the environment env extended with pairings of parameters and arguments.
The current environment, env. Not the one from the time when the function was created.
This means dynamic scoping.
To fix it, we can use the FUNARG device: store the definitional environment together with body and formal parameters when the function (thus closure) is created. Then evaluate the body in the definitional environment extended as it is now with pairings of formal parameters and actual arguments evaluated in the current environment env.
See also: this relevant answer by me.
You can even have both dynamic and lexical scoping, making a plain lambda from, say, (lambda ...) forms, which will be evaluated under dynamic scoping, and making the closure of lambda and its definitional environment from, say, (function (lambda ...)) forms (speaking in Lisp), for the lexical scoping. Thus having to handle both cases in eval, like it is done in that other answer of mine, mentioned above.