Eta 转换改变了严格语言的语义

Question

接受这个 OCaml 代码：

let silly (g : (int -> int) -> int) (f : int -> int -> int) =
        g (f (print_endline "evaluated"; 0))

silly (fun _ -> 0) (fun x -> fun y -> x + y)

它打印 evaluated 和 returns 0。但是如果我 eta-expand f 得到 g (fun x -> f (print_endline "evaluated"; 0) x)，evaluated 就不再打印了。

同样适用于此 SML 代码：

fun silly (g : (int -> int) -> int, f : int -> int -> int) : int =
        g (f (print "evaluated" ; 0));

silly ((fn _ => 0), fn x => fn y => x + y);

另一方面，此 Haskell 代码即使使用严格的 pragma 也不会打印 evaluated：

{-# LANGUAGE Strict #-}

import Debug.Trace

silly :: ((Int -> Int) -> Int) -> (Int -> Int -> Int) -> Int
silly g f = g (f (trace "evaluated" 0))

main = print $ silly (const 0) (+)

（不过，我可以通过使用 seq 做到这一点，这对我来说非常有意义）

虽然我知道 OCaml 和 SML 在理论上做的是正确的事情，但是否有任何实际理由更喜欢这种行为而不是 "lazier" 那种行为？ Eta-contraction 是一种常见的重构工具，我非常害怕在严格的语言中使用它。我觉得我应该偏执地 eta-expand 一切，因为否则可以在不应该评估部分应用函数的参数时评估它们。 "strict" 行为何时有用？

Haskell 为什么以及如何在 Strict pragma 下表现不同？是否有任何参考可以让我自己熟悉以更好地理解设计 space 以及现有方法的优缺点？

Answer 1

为了解决您问题的技术部分，eta-conversion 还更改了惰性语言中表达式的含义，您只需要考虑不同类型构造函数的 eta-rule，例如 + 而不是 ->。

这是二进制和的 eta 规则：

(case e of Lft y -> f (Lft y) | Rgt y -> f (Rgt y))  =  f e    (eta-+)

这个等式在热切的求值下成立，因为 e 两边总是会减少。然而，在懒惰评估下，r.h.s。仅在 f 也强制执行时才减少 e。这可能会使l.h.s。在 r.h.s 的地方发散。不会。所以这个等式在惰性语言中不成立。

在Haskell中具体化：

f x = 0
lhs = case undefined of Left y -> f (Left y); Right y -> f (Right y)
rhs = f undefined

在这里，尝试打印 lhs 会产生分歧，而 rhs 会产生 0.

关于这个还有更多可以说的，但本质是两种评估制度的方程理论有点对偶。

潜在的问题是，在惰性机制下，每种类型都存在 _|_（非终止），而在急切机制下则不然。这会产生严重的语义后果。特别是，Haskell 中没有归纳类型，你无法证明结构递归函数的终止，例如列表遍历。

类型论中有一系列研究将数据类型（严格）与余数据类型（非严格）区分开来，并以双重方式提供两者，从而兼顾两全其美。

编辑： 至于为什么编译器不应该 eta-expand 函数的问题：那会彻底破坏所有语言。在具有最明显效果的严格语言中，因为通过多个函数抽象 stage 效果的能力是一项功能。最简单的例子可能是这样的：

let make_counter () =
  let x = ref 0 in
  fun () -> x := !x + 1; !x

let tick = make_counter ()
let n1 = tick ()
let n2 = tick ()
let n3 = tick ()

但效果并不是唯一的原因。 Eta 扩展也可以极大地改变程序的性能！以同样的方式，你有时想要舞台效果，你有时也想要舞台 work:

match :: String -> String -> Bool
match regex = \s -> run fsm s
  where fsm = ...expensive transformation of regex...

matchFloat = match "[0-9]+(\.[0-9]*)?((e|E)(+|-)?[0-9]+)?"

请注意，我在这里使用了 Haskell，因为这个例子表明隐式 eta 扩展在急切或懒惰的语言中都是不可取的！

Answer 2

关于你的最后一个问题（为什么 Haskell 这样做），"Strict Haskell" 与真正严格的语言表现不同的原因是 Strict 扩展并不真正将评估模型从惰性更改为严格。默认情况下，它只是将绑定的一个子集变成 "strict" 绑定，并且仅在 有限的 Haskell 意义上 强制评估为弱头部范式。此外，它只影响在打开扩展的模块中进行的绑定；它不会追溯影响其他地方的绑定。（此外，如下所述，严格性在部分函数应用中不生效。在强制任何参数之前，需要完全应用该函数。）

在您的特定 Haskell 示例中，我相信 Strict 扩展的唯一效果就好像您在 silly 的定义中明确编写了以下 bang 模式：

silly !g !f = g (f (trace "evaluated" 0))

没有其他作用。特别是，它不会使 const 或 (+) 的参数变得严格，也不会通常更改函数应用程序的语义以使它们变得急切。

因此，当 silly (const 0) (+) 项被 print 强制执行时，唯一的影响是将其参数评估为 WHNF 作为 silly 函数应用程序的一部分。效果类似于写法（非StrictHaskell）：

let { g = const 0; f = (+) } in g `seq` f `seq` silly g f

显然，强制 g 和 f 到它们的 WHNF（即 lambda）不会有任何副作用，当应用 silly 时，const 0 在剩余的参数中仍然是惰性的，所以结果项类似于：

(\x -> 0) ((\x y -> <defn of plus>) (trace "evaluated" 0))

（应该在没有 Strict 扩展名的情况下进行解释——这些都是这里的惰性绑定），这里没有任何东西会强制产生副作用。

如上所述，此示例还掩盖了另一个微妙的问题。即使您已将眼前的一切都变得严格：

{-# LANGUAGE Strict #-}

import Debug.Trace

myConst :: a -> b -> a
myConst x y = x

myPlus :: Int -> Int -> Int
myPlus x y = x + y

silly :: ((Int -> Int) -> Int) -> (Int -> Int -> Int) -> Int
silly g f = g (f (trace "evaluated" 0))

main = print $ silly (myConst 0) myPlus

这仍然不会打印 "evaluated"。这是因为，在 silly 的评估中，当 myConst 的严格版本强制其第二个参数时，该参数是 myPlus 的严格版本的部分应用，并且 myPlus 在完全应用之前不会强制其任何参数。

这也意味着，如果您将 myPlus 的定义更改为：

myPlus x = \y -> x + y   -- now it will print "evaluated"

然后您将能够在很大程度上重现 ML 行为。因为 myPlus 现在已完全应用，它将强制其参数，这将打印 "evaluated"。您可以在 silly:

的定义中再次抑制它 eta-expanding f

silly g f = g (\x -> f (trace "evaluated" 0) x)  -- now it won't

因为现在当 myConst 强制其第二个参数时，该参数已经在 WHNF 中（因为它是一个 lambda），我们永远不会得到 f 的应用程序，无论是否完整。

最后，我想我不会把"Haskell plus the Strict extension and unsafe side effects like trace"当成设计中的一个好点space。它的语义可能（勉强）连贯，但它们确实很奇怪。我认为唯一严肃的用例是当你有一些代码，其语义 "obviously" 不依赖于惰性与严格评估，但通过大量强制可以提高性能。然后，您只需打开 Strict 即可提升性能，而无需费心思考。

Eta 转换改变了严格语言的语义

Eta-conversion changes semantics in a strict language

lambda

ocaml

haskell

ml

lazy-evaluation