3

我正面临以下 Prolog 代码。表达式 [X]>>Y 代表 lambda 表达式 lambda XY 代码消除了 lambda 并给出了 S、K 和 I 的组合表达式：

convert([X]>>Y,'I') :- X==Y, !.
convert([X]>>Y,apply('K',Y)) :- var(Y), !.
convert([X]>>([Y]>>Z),R) :-
     convert([Y]>>Z,H), convert([X]>>H,R).
convert([X]>>apply(Y,Z),apply(apply('S',S),T)) :-
     convert([X]>>Y,S), convert([X]>>Z,T).
convert([_]>>Y,apply('K',Y)).

这是一个示例，它是如何工作的：

 ?- convert([X]>>([Y]>>apply(Y,X)),R).
 R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
  apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))

假设我想在 Haskell、ML等中编写相同的转换代码。我怎样才能做到这一点？我可以直接使用函数式编程语言中可用的 lambda 表达式吗？还是我必须回归到一些元编程工具？

此致

PS：上面的代码不是SKI转换导致的SKI表达式很短。更好的代码可能会检查 lambda 表达式主体中绑定变量的出现。

4

2 回答 2

3

您的序言代码几乎可以逐字翻译成 ML 或 Haskell 的模式匹配。当然，您需要为 lambda 表达式定义自己的 ADT。对于该组的最佳组合器和转换，我建议参考http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

于 2011-01-21T11:50:34.870 回答
1

您可以直接使用 lamdba 表达式。在哈斯克尔：

i x = x
k x = \y -> x
s x y z = x z $ y z

r = s (s (k s) (k i)) (s (k k) i)

-- r 3 (+5) -> 8

（请注意，我不知道 SKI，这个片段是将 Wikipedia 上的定义直接转换为 Haskell；它有效，但请检查它在概念上是否正确）

于 2011-01-21T08:31:10.813 回答