在 MIT Scheme/Racket 中，一个值可以同时是运算符和操作数吗？即 (lambda (y) (y y))

Question

对于函数 foo6，给出计算结果为 3 的过程的 Curried 应用程序。

(define foo6
  (lambda (x)
    (x (lambda (y) (y y)))))

我已经定义了一个 foo7 来查看最后一行是如何工作的

(define foo7 (lambda (y) (y y)))

是否有一些"y"既可以是操作符又可以是操作数？

编辑：问题应为：

有没有一些"y"既可以是运算符又可以是操作数而不会导致错误或无限循环的？

问题取自计算机程序的结构和解释 (SICP) 示例编程作业： https://mitpress.mit.edu/sicp/psets/index.html

来自 "Introductory assignment," 练习 11：

PDF 版本：https://github.com/yangchenyun/learning-sicp/raw/master/practices/assignments/01.introductory-assignment/ps1_1.pdf
PS（原版）： https://mitpress.mit.edu/sicp/psets/ps1/ps1_1.ps

Answer 1

是的。 Scheme 和 Racket 都是 Lisp1，这意味着它们只有一个命名空间，因此。变量 v 可以是任何值，包括过程。

第二次您看到类似 (lambda (y) (y y)) 的内容时，很明显 y 是一种类型的过程，因为它正在被应用。对于过程之外的任何其他值，它将以应用程序错误结束：

((lambda (y) (y y)) 5)
; ERROR: application: 5 is not a procedure

过程本身可能期望自己作为参数，因此我们可以假设某种 omega 或 z 组合子。

我们有高阶过程，您可以将函数作为操作数位置的值传递，并使用它们，只需将 then 放在运算符位置即可：

(define (times n p)
  (lambda (arg)
    (let loop ((n n) (acc arg))
      (if (<= n 0)
          acc
          (loop (sub1 n) (p acc))))))

(define double (lambda (v) (+ v v)))
(define test (times 3 double))
(test 5) ; ==> 40

并非只有 Scheme 拥有此功能。与上面相同的代码可以在 JavaScript 中同样容易地表达，因为它也只有一个命名空间，并且 parseInt(x) 将变量 parseInt 计算为一个值，该值将应用您从中获得的参数评估变量 x。它们只是两个变量，没什么特别的。

编辑

这是一个示例，其中 (lambda (y) (y y)) 用于一些有用的地方。

;; the Z combinator 
(define Z
  (lambda (f)
    ((lambda (y)
       (y y))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

(define (fib n)
  ((Z (lambda (helper)
        (lambda (n a b)
          (if (zero? n)
              a
              (helper (- n 1) b (+ a b))))))
   n 0 1))

(fib 10) ; ==> 55

Z 组合子是 eager 语言的 Y 组合子。它可以在不改变环境的情况下进行自我引用。

Answer 2

是的，

(define (foobar n)
  ((foo6
    (lambda (u) (u (lambda (y)
                     (lambda (n)
                       (if (zero? n)
                           1
                           (* n ((y y) (- n 1)))))))))
   n))

是吗？我的意思是，为什么？因为

  (foo6 x)
=
  (x (lambda (y) (y y))
=
  (x u)             where u = (lambda (y) (y y))
                    i.e. (u y) = (y y)

所以 foo6 的参数应该是一个函数 x 期望 u 使得 u y = y y。所以我们给它这样的功能

  (foobar n)
=
   ((foo6 x) n)
=
    ((x u) n)               
=
     ((u y) n)                 so, x = (lambda (u) (u (lambda (y) (lambda (n) ...))))
=
      ((y y) n)              so, y = (lambda (y) (lambda (n) ...))
=
       ((lambda (n)
          (if (zero? n)
            1
            (* n ((y y) (- n 1)))))
        n)

及以后，当/如果((y y) (- n 1))需要计算时，相同的(lambda (n) ...)函数作为(y y)应用的结果再次到达，并在/时再次使用如果 ((y y) (- (- n 1) 1)) 需要评估。

试试吧！ (foobar 5) 评估的是什么？ _{(ʎʇuǝʍʇpuɐpǝɹpunɥǝuo)}

所以，一切都合适。你看到了吗？

(lambda (y) (y y))其实有一个名字：它是“U组合子”。

在 MIT Scheme/Racket 中，一个值可以同时是运算符和操作数吗？即 (lambda (y) (y y))

In MIT Scheme/Racket, can a value be both the operator and operand? i.e. (lambda (y) (y y))

scheme

sicp

currying

racket