问题标签 [combinatory-logic]

我正在尝试在 scala 中对组合微积分进行非常轻量级的编码。最初，我只是实现 S 和 K 组合器、应用程序和常量值。后来我希望提升 scala 函数并允许将表达式评估为 scala 函数。不过，那是以后的事了。这是我到目前为止所拥有的。

现在我想对此做一些类型推断。为了简单地实现小步和大步减少，数据模型是无类型的，所以我希望类型在这个结构之外。让我们介绍一些东西来保存类型信息。

值类型很简单。

应用有点棘手，但基本上归结为功能应用。让我们为组合应用程序引入一个类型 ⊃，以避免与普通的 scala 应用程序混淆。

这就是我卡住的地方。我需要表示 S 和 K 组合子的类型。但是，它们是普遍量化的类型。在您开始应用它们之前，您不知道它们的实际类型。我们以 K 为例。

前几次我尝试使用它，我将 K 参数化为 K[X, Y]，但这（灾难性地）多态性不足。K 的类型应该等待第一个参数的类型，然后是下一个参数的类型。如果您只将 K 应用于一个值，则下一个参数的类型不应该是固定的。您应该能够获取 (K x:X) 并将其应用于字符串、int 或任何您喜欢的类型。

所以我的问题是如何编写为 S 和 K 生成 typeOf 的隐式，以及如何正确处理∀量化类型。也许我想要这样的东西？

但是，我不确定我应该如何编写 ∀ 类型来完成管道。我有一种感觉，除了让 ∀ 正确之外，除了现有的 A#typeOf =:= ⊃[ ...] 一。

谢谢，

马修

当我偶然发现 Wikipedia 说：“Y 组合子可以在 SKI 演算中表示为：Y = S (K (SII)) ( S（S（KS）K）（K（SII）））”，所以我不得不尝试：

我究竟做错了什么？我没有正确翻译那个表达吗？我的处理方式有问题吗？它甚至有意义吗？大部分关于此类内容的阅读内容只会让我的大脑想要爆炸，所以这个练习的重点对我来说主要是看看我是否理解了这个符号（从而能够将它翻译成 JavaScript）。

哦，顺便说一句：让我再次阅读和摆弄的是prototype.js作为Prototype.K实现的实际上是I组合子。有没有人注意到？

考虑这个组合器：

将其应用于参数 XY：

它签订合同：

我将 S (SK) 转换为相应的 Lambda 项并得到以下结果：

我使用 Haskell WinGHCi 工具获取 (\xy -> xy) 的类型签名并返回：

这对我来说很有意义。

接下来，我使用 WinGHCi 获取 s (sk) 的类型签名并返回：

这对我来说没有意义。为什么类型签名不同？

注意：我将 s、k 和 i 定义为：

我现在了解的类型签名s (s k)：

我可以在 Haskell WinGHCi 工具中创建可以正常工作的示例：

示例：

返回2。

示例：

返回4。

其中successor定义为：

尽管如此，我仍然没有直观的感觉s (s k)。

组合s (s k)器采用任意两个函数f和g。和s (s k)有什么作用？你能给我大局观吗？fgs (s k)

我正在尝试在 Haskell 中实现组合逻辑，并且我想为该语言编写解析器。我无法让解析器通过 Parsec 工作。基本问题是我需要一种方法来确保解析器返回的对象类型正确。有没有人对如何做到这一点有任何创造性的想法？

Ruby 有一个方法允许我们观察值的管道，而无需修改底层值：

Scala中有这样的方法吗？我相信这被称为 Kestrel Combinator，但不能确定。

我想知道这段代码在 Scheme 中的含义：

整个文件在这里。

这是合法的计划吗？(K x) 是参数化函数，类似于 Java 中的泛型函数吗？我查了MIT Scheme 参考，似乎没有提到这种定义。

给定一个可调用对象（一个函数）a和一个参数b（或一系列参数），我想从f考虑到f多个签名重载的情况下推断返回的类型。

我的许多尝试之一是

和 2 个模板选项被注释掉并包含在前面的代码中。

我正在使用declval result_of auto decltype没有任何运气。

重载解析过程在编译时如何工作？

如果有人想知道我为什么要尝试对此进行创意，那是我正在尝试以可行/简洁的方式在 C++11 中实现一些 Currying。

在搜索有关 Raymond Smullyan 的To Mock a Mockingbird的信息时，我偶然发现了Stephen Tetley 的基本组合器的 Haskell 代码。我认为这是一个有趣的想法，并决定使用这些组合器来实现To Mock a Mockingbird第 24 章中的“可以做算术的鸟”。我已经定义了真、假、继任者、前任和零校验组合器，以及将组合布尔值更改为 Haskell 布尔值的函数，反之亦然。但是当我尝试创建一个接受组合数字并返回整数的函数时，我一直遇到问题。我想知道如何使这个功能工作。这是我到目前为止所得到的：

这是我对代码问题的粗略猜测：“cnhn”函数将任何组合数字作为参数。但是不同的组合数有不同的类型，比如

零）id'​​ :: a -> a

一）vr(ke id')id' :: ((a -> b -> b) -> (c -> c) -> d) -> d

二）vr(ke id')(vr(ke id')id') :: ((a -> b -> b) -> (((c -> d -> d) -> (e -> e ) -> f) -> f) -> g) -> g

等等。因此，将任何组合数作为参数的函数必须能够采用无限多种类型的参数。但是 Haskell 不允许这样的功能。

简而言之，这是我的 3 个主要问题：

1) 'cnhn' 函数有什么问题？（我上面的猜测正确吗？）

2）可以修复吗？

3）如果不是，我可以使用什么其他语言来实现 Smullyan 的算术鸟？

感谢您阅读一个很长的问题。

作为练习，我将以下组合器转换为无点表示法：

f, g,h作为函数, x, y,z作为表达式的通常约定。（这不是作业问题，只是为了好玩，看看我是否理解无点转换。）

在 的帮助下进行了漫长的手动重写过程后ghci，我得到了以下结果：

我注意到h它只包含两个组合器， "compose"(.)和 "reverse compose" flip (.)。有了这个，原始的组合子可以简洁地写成：

“组合”和“反向组合”操作的结构（数量和顺序）似乎与原始组合器的结构有某种关联。

我认为这与组合逻辑和 SKI 演算直接相关。我的问题是：

1. 有更多洞察力的人可以解释这里发生了什么：无点组合器中“组合”和“反向组合”的结构与有点组合器中的函数和表达式结构有什么关系？

2. 这可以推广到任意组合器（即，函数的数量，表达式的数量，它们的顺序是任意的）吗？更具体地说，每个组合子都可以用“compose”和“reverse compose”来表达吗，有没有一种方案可以直接从pointful combinator的结构中推导出“compose”和“reverse compose”的组合（即，没有经历完整的重写过程）？例如，是否可以直接\ f g x y z -> (f x y) g z从函数结构中得出无点版本？

3. c和的组合逻辑叫什么名字r？

更新：

这似乎c是B组合子，r来自CBB 、C、K、W 系统。但我仍然很乐意更深入地了解我的问题，尤其是问题 1 和问题 2。