ruby - 在 Lisp/Ruby 中将 IF-ELSE 实现为过程

Question

我正在阅读 Understanding Computation 的 lambda 演算部分(第 4 章) .此代码尝试使用 Ruby 中的 lambda 演算构建 MOD:

MOD = -> m { -> n { CONTROL_IF[
            IS_LESS_OR_EQUAL[n][m]
            ][
                MOD[SUBTRACT[m][n]][n]
            ][
                m
            ]
        }}

CONTROL_IF = -> b { b }
IS_LESS_OR_EQUAL = -> m { -> n { IS_ZERO[SUBTRACT[m][n]] }}
IS_ZERO = -> n { n[-> x { B_FALSE }][B_TRUE] }
#Full code would listed below

irb 失败并打印 SystemStackError: stack level too deep

当输入 to_integer(MOD[THREE][TWO])

根据书上的说法，MOD 不工作，因为它未能实现 Ruby if-else 控制逻辑的惰性求值，并不断递归调用自身。

并且修改后有效:

#working one
MOD = -> m { -> n { CONTROL_IF[
            IS_LESS_OR_EQUAL[n][m]
            ][
              -> x { MOD[SUBTRACT[m][n]][n][x]}
            ][
              m
            ]
        }}

据说 -> x { ...[x]} 延迟了 MOD 的递归调用，但我不明白。

此外，我想到了 SICP 中的类似练习(1.6):

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
        (else else-clause)))

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x) x)))

作为用户定义的过程，sqrt-iter 会遇到无限递归，因为 (sqrt-iter (improve guess x) x) 每次都作为参数求值过程new-if。

所以现在我明白了将 IF-ELSE 作为过程实现的关键点是惰性求值，我的问题是:

1. 为什么 MOD 修改后可以正常工作？
2. new-if 能否以 Ruby 方式进行改进 (-> x { ...[x]} ) 以便延迟递归调用？

Ruby 的完整代码:

ZERO  = -> proc { -> x {                          x      } }
ONE   = -> proc { -> x {                     proc[x]     } }
TWO   = -> proc { -> x {                proc[proc[x]]    } }
THREE = -> proc { -> x {           proc[proc[proc[x]]]   } }
FOUR  = -> proc { -> x {      proc[proc[proc[proc[x]]]]  } }
FIVE  = -> proc { -> x { proc[proc[proc[proc[proc[x]]]]] } }

def to_integer(proc)
    proc[-> n { n + 1 }][0]
end

CONTROL_IF = -> b { b }

B_TRUE  = -> x { -> y { x }}
B_FALSE = -> x { -> y { y }}
IS_ZERO = -> n { n[-> x { B_FALSE }][B_TRUE] }

IS_LESS_OR_EQUAL = -> m { -> n { IS_ZERO[SUBTRACT[m][n]] }}

ADD      = -> m { -> n { n[INCREMENT][m] } }
SUBTRACT = -> m { -> n { n[DECREMENT][m] } }

PAIR  = -> x { -> y { -> f { f[x][y] } } }
LEFT  = -> p { p[-> x { -> y { x } } ] }
RIGHT = -> p { p[-> x { -> y { y } } ] }

INCREMENT = -> n { -> p { -> x { p[n[p][x]] } } }

SLIDE     = -> p { PAIR[RIGHT[p]][INCREMENT[RIGHT[p]]] }
DECREMENT = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] }

=begin
#failed one
MOD = -> m { -> n { CONTROL_IF[
            IS_LESS_OR_EQUAL[n][m]
            ][
                MOD[SUBTRACT[m][n]][n]
            ][
                m
            ]
        }}
=end

#working one
MOD = -> m { -> n { CONTROL_IF[
            IS_LESS_OR_EQUAL[n][m]
            ][
              -> x { MOD[SUBTRACT[m][n]][n][x]}
            ][
              m
            ]
        }}

#to_integer(MOD[THREE][TWO])

Answer 1

我不太熟悉 Ruby 语法，但您似乎将匿名函数放置在表达式所在的位置。匿名函数确实会产生所需的延迟，因为它在调用之前不会计算函数体。问题是如何调用它以及在何处调用它。引入这样的“就地”延迟通常会导致非常困惑的代码。

在 Scheme 中你可以制作一个延迟版本的 if 但语义略有不同:

(define (new-if test consequent alternative)
       (cond (test (consequent))
             (else alternative)))
> (new-if (= (+ 1 2) 3) 
                 (lambda () (display "Yay"))
                 (lambda () (display "Nei")))
Yay

因此，后项和替代项需要作为匿名函数传递。注意，这个版本仍然使用特殊形式 cond。如果你想一直深入到基础知识并通过 lambda 函数在一种具有应用评估顺序的语言中定义 if(即像 Scheme 一样严格)，那么你将面临一项非常艰巨的任务控制表达式在何处延迟和不延迟。