最外层评估如何在柯里化函数的应用程序上工作？

Question

mult 定义为柯里化函数：

mult    ::  Int ->  Int ->  Int
mult    x   =   \y  ->  x   *   y

在mult (1+2) (2+3)、

redex 是什么。他们是 mult(1+2)、1+2 和 2+3 吗？
最外层的redex是什么，是2+3吗？

根据 Hutton 在 Haskell 中的编程，最内层的计算对表达式的作用如下：

mult    (1+2)   (2+3)
= { applying    the first   +   }
mult    3   (2+3)
= { applying    mult    }
(\y ->  3   *   y)  (2+3)
= { applying    +   }
(\y ->  3   *   y)  5
= { applying    the lambda  }
3   *   5
= { applying    *   }
15

最外层的评估如何在 mult (1+2) (2+3) 上工作？最外层评估是否按以下方式工作？

mult (1+2) (2+3)
= mult (1+2) 5
= (\y -> (1+2) * y) 5
= (1+2) * 5  // Is (1+2) evaluated before (1+2) * 5, because builtin function "*" is strict, i.e. application of builtin function always happen after evaluation of its args?
= 3*5
= 15

谢谢。

Answer 1

mult (1+2) (2+3) 中最外层的 redex，即

          mult
       /        \
      +          +
    1   2      2   3

是 mult x y，其中 x = (1+2) 和 y = (2+3)。

有两个内部索引，(1+2) 和 (2+3)。因此最左边最里面的 redex 是 (1+2).

通过最左边最里面的 redex 减少如下：

mult (1+2) (2+3)
=
mult 3 (2+3)
=
mult 3 5
= {- mult x = \y -> x * y -}
(let x = 3 in (\y -> x * y)) 5
=
let x = 3 in let y = 5 in x * y
=
3 * 5
=
15

按如下方式减少最顶层的 redex：

mult (1+2) (2+3)
= {- mult x = \y -> x * y -}
(let x = (1+2) in (\y -> x * y)) (2+3)
=
let x = (1+2) in let y = (2+3) in x * y
=
(1+2) * (2+3)
=
3 * (2+3)
=
3 * 5
=
15

Answer 2

写下解析树：

         o
       /   \
     o       o
    / \     /|\
mult   o   2 + 3
      /|\
     1 + 2

（为了简单起见，我将二进制中缀 + 运算符视为单个应用程序，它也可能是 ((+) 1) 2）

现在最外层的函数应用是 mult (1+2) 对参数 2+3 的应用，但它不可简化，因为该函数不是单个值而是应用程序本身。我们必须先评估一下：

(mult (1+2)) (2+3)
((\x->\y->x*y) (1+2)) (2+3) -- the value that `mult` refers to
(\y->(1+2)*y) (2+3) -- evaluate the application of `\x->`

现在我们可以评估根函数应用：

(1+2) * (2+3) -- application of `\y->`

现在最外层的表达式是 *，但如您所知，这些整数运算符是严格的，因此它们需要先计算其参数 (left-to-right, IIRC):

3 * (2+3)
3 * 5
15

最外层评估如何在柯里化函数的应用程序上工作？

How does outermost evaluation work on an application of a curried function?

haskell

functional-programming

evaluation

currying