《小阴谋家》中的 Y 组合器讨论

2023-12-14

所以,我花了很多时间阅读并重新阅读第9章的结尾小阴谋家,其中应用 Y 组合器是为length功能。我认为我的困惑可以归结为一个对比两个版本长度的语句(在组合器被分解之前):

A:
  ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     (lambda (l)
       (cond
         ((null? l) 0 )
         (else (add1
                ((mk-length mk-length)
                 (cdr l))))))))

B:
((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (mk-length mk-length))))

第 170 页(第 4 版)指出 A

当我们将函数应用于参数时返回一个函数

while B

不返回函数

从而产生自我应用的无限回归。我对此感到困惑。如果B被这个问题困扰,我不知道A如何避免它。


Great question. For the benefit of those without a functioning DrRacket installation (myself included) I'll try to answer it.

首先,让我们使用一些合理的(短的)变量名称,易于人眼/思维跟踪:

((lambda (h)     ; A.   
     (h h))            ; apply h to h
 (lambda (g)
     (lambda (lst)
       (if (null? lst) 0
         (add1 
               ((g g) (cdr lst)))))))

第一个 lambda 项被称为小欧米茄,或者U组合器。当应用于某事物时,它会导致该术语的自我应用。因此上式等价于

(let ((h (lambda (g)
           (lambda (lst)
             (if (null? lst) 0
               (add1 ((g g) (cdr lst))))))))
  (h h))

When h应用于h,新的绑定形成:

(let ((h (lambda (g)
           (lambda (lst)
             (if (null? lst) 0
               (add1 ((g g) (cdr lst))))))))
  (let ((g h))
    (lambda (lst)
            (if (null? lst) 0
              (add1 ((g g) (cdr lst)))))))

现在已经没有什么可以应用的了,所以内部lambda返回形式 -​​ 以及与环境框架的隐藏链接(即那些let绑定)位于其上方。

lambda 表达式与其定义环境的这种配对称为closure。对于外界来说,它只是一个参数的另一个函数,lst。目前没有更多的减少步骤需要执行。

现在,当关闭时——我们的list-lengthfunction — 将被调用,执行最终会到达(g g)自行应用,并且将再次执行与上述相同的减少步骤(重新计算the same关闭)。但不是更早。


现在,该书的作者想要达到Y组合器,因此他们对第一个表达式应用一些代码转换,以某种方式安排该自我应用(g g)自动执行 - 因此我们可以以正常方式编写递归函数应用程序,(f x),而不必将其写为((g g) x)对于所有递归调用:

((lambda (h)     ; B.
     (h h))            ; apply h to h
 (lambda (g)
   ((lambda (f)           ; 'f' to become bound to '(g g)',
      (lambda (lst) 
        (if (null? lst) 0
          (add1 (f (cdr lst))))))  ; here: (f x) instead of ((g g) x)!
    (g g))))                       ; (this is not quite right)

现在经过几个简化步骤我们得到

(let ((h (lambda (g)
           ((lambda (f)    
              (lambda (lst) 
                (if (null? lst) 0
                  (add1 (f (cdr lst))))))
            (g g)))))
  (let ((g h))
    ((lambda (f)
       (lambda (lst)
            (if (null? lst) 0
              (add1 (f (cdr lst))))))
     (g g))))

这相当于

(let ((h (lambda (g)
           ((lambda (f)    
              (lambda (lst) 
                (if (null? lst) 0
                  (add1 (f (cdr lst))))))
            (g g)))))
  (let ((g h))
    (let ((f (g g)))           ; problem! (under applicative-order evaluation)
       (lambda (lst)
            (if (null? lst) 0
              (add1 (f (cdr lst))))))))

麻烦来了:自我应用(g g)执行得太早,before内部 lambda 甚至可以作为闭包返回到运行时系统。我们只希望当执行到那个点时减少它inside拉姆达表达式,after宣布关闭。在关闭之前就减少它是荒谬的。 Asubtle错误。 :)

当然,自从g一定会h, (g g)减少为(h h)我们又回到了开始的地方,申请h to h。循环播放。


作者们当然意识到了这一点。他们要us也去理解它。

所以罪魁祸首很简单——就是评估的应用顺序: 评估论证before绑定由函数的形式参数及其参数组成value.

那么,代码转换不太正确。它会在下面工作正常秩序其中参数没有提前评估。

这很容易通过“eta 扩展”,这会将应用程序延迟到实际调用点:(lambda (x) ((g g) x))实际上说:“will call ((g g) x)当被要求提出论据时x".

这实际上是代码转换首先应该做的:

((lambda (h)     ; C.
     (h h))            ; apply h to h
 (lambda (g)
   ((lambda (f)           ; 'f' to become bound to '(lambda (x) ((g g) x))',
      (lambda (lst) 
        (if (null? lst) 0
          (add1 (f (cdr lst))))))  ; here: (f x) instead of ((g g) x)
    (lambda (x) ((g g) x)))))

现在可以执行下一个减少步骤:

(let ((h (lambda (g)
           ((lambda (f)    
              (lambda (lst) 
                (if (null? lst) 0
                  (add1 (f (cdr lst))))))
            (lambda (x) ((g g) x))))))
  (let ((g h))
    (let ((f (lambda (x) ((g g) x))))       ; here it's OK
      (lambda (lst)
            (if (null? lst) 0
              (add1 (f (cdr lst))))))))

和关闭(lambda (lst) ...)形成并毫无问题地返回,并且当(f (cdr lst))被称为(在闭包内)它被简化为((g g) (cdr lst))正如我们所希望的那样。


最后,我们注意到(lambda (f) (lambda (lst ...))表达于C.不依赖于任何h and g。所以我们可以把它拿出来,让它成为一个论点,然后剩下……Y组合器:

( ( (lambda (rec)            ; D.
      ( (lambda (h) (h h))  
        (lambda (g)
          (rec  (lambda (x) ((g g) x))))))   ; applicative-order Y combinator
    (lambda (f)
        (lambda (lst) 
          (if (null? lst) 0
            (add1 (f (cdr lst)))))) )
  (list 1 2 3) )                            ; ==> 3

所以现在,打电话Y在函数上相当于对其进行递归定义:

( y (lambda (f) (lambda (x) .... (f x) .... )) ) 
===  define f = (lambda (x) .... (f x) .... )

...但是使用letrec(或命名为let)是better- 更高效,在自参照环境框架中定义闭包。整体Y这是对系统的理论练习,但这是不可能的——即不可能name事物,创造bindings有名字“指点”对事物,指称对事物。

顺便说一句,有能力 point 对事物的认识是高等灵长类动物与动物王国其他生物的区别,至少我是这么听说的。 :)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

《小阴谋家》中的 Y 组合器讨论 的相关文章

  • 学习一种 Lisp 有助于学习另一种 Lisp 吗?

    学习不同的 Lisp 语言之间有协同作用吗 我目前正在学习 Emacs Lisp 因为它在我的日常 Emacs 使用中立即有用 但是我对所有 Lisp 都很着迷 所以也许有一天我会学习和使用其他语言 当我开始深入研究 Common Lisp
  • 编码霍夫曼树方案[关闭]

    Closed 这个问题需要调试细节 help minimal reproducible example 目前不接受答案 我正在尝试编写一个函数 codeWords t 它遍历霍夫曼树 添加 0当它向左移动时 添加 1当它向右时 并以叶子上的
  • 这些嵌套向量是如何连接的?

    我编写了一段代码 它创建了一个向量 记分板 其中包含 3 个大小为 3 的独立向量 所有向量都包含符号 在所有索引 0 2 处 当我现在执行 向量集 时在记分牌的第一个向量上 要将其第一个元素更改为 X 向量 2 和 3 也会更改 这是如何
  • 毛里求斯国旗问题

    我已经为该问题制定了解决方案荷兰国旗问题 http en wikipedia org wiki Dutch national flag problem已经 但这一次 我想尝试一些更困难的事情 毛里求斯国旗问题 4 种颜色 而不是 3 种 对
  • eq 之间的区别?和 = 在方案中?

    gt eq 1 1 t gt eq 1 1 1 1 f gt 1 1 1 1 t 这是DrScheme 中的交互窗口 有人可以解释一下 和 eq 之间的区别吗 在计划中 比较数字 等式 测试参数是否表示内存中的同一数据对象 当量 应该在第二
  • 本地球拍

    我正在书中阅读有关本地定义的内容 并且遇到了这个例子 local define f x x 5 define g alon cond empty alon empty else cons f first alon g rest alon g
  • 使用foldr实现zip

    我目前正在阅读 Real World Haskell 的第 4 章 我正在努力理清思路根据foldr 实现foldl http book realworldhaskell org read functional programming ht
  • 在 SimpleHTTPServer.py 中重定向浏览器?

    我部分通过实现功能简单HTTP服务器 py http hg python org cpython file tip Lib SimpleHTTPServer py在方案中 我对 HTTP 请求 响应机制很感兴趣 在查看上面的文件时 我遇到了
  • 有没有办法检查一个列表的所有元素是否都包含在球拍的另一个列表中?

    我想要一个执行类似操作的函数 gt function 1 2 3 4 1 2 3 4 5 t 在这种情况下返回 t 因为第一个列表的所有元素都包含在第二个列表中 有没有一个函数可以做到这一点而不必担心顺序 在这种情况下 您不会将列表进行比较
  • 在Scheme中编写一个自动记忆器。有关宏和包装器的帮助

    我在Scheme中编写自动记忆器时遇到了一些问题 我有一个有效的 memoize 函数 它创建一个哈希表并检查该值是否已经计算出来 如果之前已经计算过 则返回值 否则调用该函数 define memoizer fun let a table
  • 删除重复项并对列表进行排序

    我正在尝试编写一个过程 该过程采用一个可能包含或不包含重复项的列表 然后按排序顺序返回没有重复项的列表 到目前为止我想到的是 define remove duplicated list if null list if car list ca
  • 在Scheme中插入二叉树

    我想知道如何将列表中的元素插入二叉搜索树 我想知道为什么下面的代码不能按我的预期工作 输出是 4 1 5 13 6 我的下一个问题是对列表中的元素进行排序 但现在我只想插入它们 我的输出对于我所说的问题是否正确 我的代码如下 define
  • 方案/球拍:画布操作

    1 正如标题所述 当我调整窗口大小时 我绘制的对象消失 但矩形保持原样 2 原点从左上角开始 但我希望它在左下角 3 除了绘图库之外 我找不到任何缩放功能 所以如果我希望实现这样的功能 一个选项是通过绘制更大的对象并刷新画布来 缩放 def
  • 展开方案中的函数

    Goal 实施unfold仅使用两个参数的函数 论据 第一个参数是 f 它接受某种类型 I 的初始值并返回 nil 或两个元素的 cons 对 这两个元素中的第一个是某种类型 A 的列表中的下一个元素 下一个初始值又是某些类型 I 第二个参
  • 方案:为什么内部定义比外部定义快?

    我尝试运行下面的程序 define odd internal x define even x if zero x t odd internal sub1 x if zero x f even sub1 x define odd extern
  • Racket 中的“match”可以具有带有来自外部作用域的变量的模式吗?

    考虑以下示例 lang racket match cat doge a b match b a t f Not a pair 如果我想匹配头部和尾部相同的对 我可能会这样写 但这不起作用 因为第二个a被绑定为一个新变量 并且匹配任何内容 是
  • 大括号 {} 替换 Racket 中的“开始”

    是否可以有一个宏 使用大括号 来表示一个语句块 从而替换 begin 关键字 因此 代替 if condition begin statement1 statement2 statement3 statement4 else stateme
  • Lisp 中的 (定义 (平均 ....))

    我只是在玩scheme lisp 并正在考虑如何纠正我自己的定义average 我不确定如何做一些我认为需要的事情 定义一个接受任意数量参数的过程 计算这些参数 将参数列表传递给 以将它们加在一起 有人有定义的例子吗average 我似乎对
  • 从when语句内的函数返回

    我想做的就是使用 when 语句返回一个值 我想要以下功能 if x return y 我正在尝试使用 when x y 但是when语句并没有以退出函数并返回y的方式进行计算 它只是愉快地继续下一行 有没有办法做到这一点而不需要制作一个看
  • Emacs Lisp 可以将 lambda 形式分配给像Scheme 这样的变量吗?

    在研究 Emacs Lisp 的符号单元时 我发现像这样的示例函数 defun a rest x x 我可以打电话 symbol function a 返回 lambda rest x x 如果我愿意的话我可以使用它 gt lambda r

随机推荐

  • tvOS UITextField 编辑后为空

    Editing UITextFieldtvOS 中显示了一个新视图 用户可以在其中输入文本 完成文本输入后 用户将返回到之前的视图 但是 我发现当我从文本编辑器返回时 我编辑的文本不会显示在我的文本字段中 这是怎么回事 电视操作系统版本9
  • MySQL,多行分隔字段

    我有一个 MySQL 表 其中包含如下字段和数据 PartNumber Priority SupName a1 0 One a2 0 One a2 1 Two a3 0 One a4 1 Two a5 2 Three 我正在尝试创建一个视图
  • C# 无协议 SuperSocket

    问题很简单 我已阅读全文超级插座文档 但我不明白是否有一种方法可以在不实现协议的情况下使用它 我不需要发送特定的命令 而只需发送可能是一个或数百个字节 具体取决于许多因素 我需要更新一个使用简单套接字的旧 TCP 服务器 它是我在 4 年前
  • 如何使用 webpack 混淆 js 文件

    我想在 public js 中混淆我的 js 文件 但在混淆之前 是否可以先在我的 public 文件夹外部的其他目录中传输 然后混淆的结果将在 public js 中 先感谢您 我的回答来得很晚 但我建议https obfuscator
  • 值类型何时存储在堆栈中(C#)?

    当我阅读下一本书的 值和引用类型 一章时 我想到了一个问题 值类型何时存储在堆栈中 因为程序员无法在类外初始化任何值类型 因为当我们在类中初始化一些值类型的变量时 变量就会存储在堆中 我的问题是 值类型什么时候存储在堆栈中 好吧 首先 您很
  • CMake 无法与 Google Protobuf 配合使用

    无法使用 CMake 链接 protobuf 库 我的 CMakeLists 是 cmake minimum required VERSION 3 6 project addressbook set CMAKE CXX STANDARD 1
  • 不带计数器的自定义周期函数

    我在用ode45求解一个简单的 ODE function dCdt u vent t C if t gt 600 t lt 720 Q Q2 elseif t gt 1320 t lt 1440 Q Q2 elseif t gt 2040
  • 获取日期时间之间的时间差

    如何求2次之间的差值 例子 var now 04 09 2013 15 00 00 var then 04 09 2013 14 20 30 expected result 00 39 30 I tried var now moment 0
  • JavaScript 监听器不断增加

    我实现了一个网络应用程序并使用谷歌开发人员工具监控了性能 我注意到听众不断增加 听众数量也在不断增加 听众增加的部分看起来像这样 let ival interval function http get someurl this call i
  • 使用 ffmpeg 进行转换,无需执行

    我的 Windows XP Apache PHP 5 3 和 ffmpeg 工作正常 我需要将 flv 转换为 avi 或反之亦然 而不使用exec 命令 这可能吗 谢谢 编辑 我希望有人可以编辑 ffmpeg 源代码并在 php 扩展中实
  • csh 上的自连接字符串

    我需要将 argv 中的部分内容连接到我的变量之一 我将向您展示我的代码 bin csh set stringList foreach param argv if param TEST then set stringList stringL
  • 为什么不使用 IoC 容器来解决实体/业务对象的依赖关系?

    我了解 DI 背后的概念 但我只是在学习不同的 IoC 容器可以做什么 似乎大多数人都主张使用 IoC 容器来连接无状态服务 但是将它们用于实体等有状态对象呢 无论是对还是错 我通常都会用行为填充我的实体 即使该行为需要外部类 例子 pub
  • CSS3:检测 iPhone 的设备方向

    所以这个声明适用于 iOS 4 和 4 1 但不适用于旧版本 有什么建议吗 media screen and device width 320px and orientation portrait iPhone Portrait Style
  • 当值改变时MySQL增加用户变量

    我有一个由组组成的表 例如 每组五行 每组中的每一行都拥有一个date该群体独有的价值 我想要在查询中执行的操作是遍历表 并在执行此操作时增加用户变量 count date值变化 也就是说 count 应该等于组数 而不是行数 我当前的查询
  • 将集合 S 公平划分为 k 个分区

    存在一个集合 S 其中包含 N 个整数 每个整数的值为 1fair还需要定义 例如 目标可能是最小化分区值与集合 S 平均值的标准偏差 即 sum S k 例如S 10 15 12 13 30 5 k 3 一个好的分区是 30 10 15
  • 如何通过Selenium和Webdriver提高执行速度

    测试脚本执行过程中速度非常慢 不知道原因 这是我的脚本 driver Navigate GoToUrl url driver Manage Timeouts ImplicitWait TimeSpan FromSeconds 20 driv
  • QOMX_COLOR_FormatYUV420PackedSemiPlanar64x32Tile2m8ka 转换器

    我需要处理YUVAndroid 上 H W 解码输出的数据 实际上 我使用的是Nexus4 解码输出格式是QOMX COLOR FormatYUV420PackedSemiPlanar64x32Tile2m8ka type 但是我需要YUV
  • 防止 MS-SQL 表中的循环引用

    我有一个包含 ID 和 ParentAccountID 的帐户表 以下是重现这些步骤的脚本 如果 ParentAccountID 为 NULL 则该帐户被视为顶级帐户 每个帐户最终应以顶级帐户结束 即 ParentAccountID 为 N
  • Google Apps脚本中的持久变量[重复]

    这个问题在这里已经有答案了 以下始终显示 0 var gNumber 0 function myTest Browser msgBox gNumber gNumber 当然 我可以使用 ScriptProperties 或 UserProp
  • 《小阴谋家》中的 Y 组合器讨论

    所以 我花了很多时间阅读并重新阅读第9章的结尾小阴谋家 其中应用 Y 组合器是为length功能 我认为我的困惑可以归结为一个对比两个版本长度的语句 在组合器被分解之前 A lambda mk length mk length mk len