词法或动态作用域 - 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

坦率地说，这是一个非常难的问题。从代码中不难看出，该语言实现的是“call-by-name”还是“call-by-value”（本例中为“call-by-value”）。但是分析是动态作用域还是词法作用域就是另外一回事了

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。

那么意思就变成了，在环境env中评估body，扩展了成对的参数和实参。

当前环境，env。不是创建函数时的那个。

这意味着动态范围。

要修复它，我们可以使用 FUNARG 设备：在创建函数（因此闭包）时将定义环境与主体和形式参数一起存储。然后在 definitional 环境中评估正文扩展，就像现在一样，在 current 环境 env.

另请参阅：此相关。

你甚至可以同时拥有动态和词法作用域，例如从 (lambda ...) 形式创建一个普通的 lambda，它将在动态范围内进行评估，并使 lambda 的闭包及其定义环境来自，例如，(function (lambda ...)) 形式（用 Lisp 说话），用于词法范围。因此必须在 eval 中处理这两种情况，就像在上面提到的我的另一个答案中所做的那样。

词法或动态作用域 - Haskell 实现的求值器

Lexical or Dynamic scope - Haskell implemented evaluator

haskell

lexical-scope

dynamic-scope