haskell - 词法或动态范围 - Haskell 实现的评估器

Question

我的教授在讨论了词法作用域和动态作用域之间的区别后给了我们一个问题。他向我们展示了一个用 Haskell 编码的简单评估器(一种虚构语言)。以下是代码:

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

问题问:

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

坦率地说，这是一个非常难的问题。从代码中很容易看出，这种语言是实现“按名称调用”还是“按值调用”(在这种情况下，它是“按值调用”)。但是分析它是动态作用域还是词法作用域是另一回事

Answer 1

您的代码不完整:

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
                                         ^^^^^

缺少一个参数。但是你只有一个选择来修复它，添加 env那里。
那么意思就变成，在环境中求值 body env扩展了参数和参数的配对。
当前环境，env .不是函数创建时的那个。
这意味着动态范围。
要修复它，我们可以使用 FUNARG device:在创建函数(即闭包)时将定义环境与主体和形式参数一起存储。然后在扩展的定义环境中评估主体，就像现在一样，在当前环境中评估形式参数和实际参数的配对 env .
另请参阅:此相关 answer by me .
您甚至可以同时拥有动态和词法范围，例如从 (lambda ...) 生成一个普通的 lambda。形式，将在动态范围下进行评估，并从 (function (lambda ...)) 中创建 lambda 及其定义环境的闭包。形式(在 Lisp 中)，用于词法范围。因此必须在 eval 中处理这两种情况，就像在我上面提到的另一个答案中所做的那样。