SKI 变换，如何用函数式语言编程

发布于 2024-10-13 07:39:51 字数 876 浏览 2 评论 0原文

我面临以下 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 表达式吗直接用函数式编程语言？或者我必须回归到一些元编程工具？

最好的问候

P.S.：上面的代码不是导致非常短的 SKI 转换滑雪表达。可以使用更好的代码来检查是否发生 lambda 表达式主体中的绑定变量。

原文

I am facing the following Prolog code. The expression [X]>>Y stands
for the lambda expression lambda X.Y. The code eliminates the lambda
and gives a combinatory expression over S, K and 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)).

Here is an example how it works:

 ?- 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'))

Suppose I would like to code the same conversion in Haskell, ML, or
the like. How can I do this? Can I use the lambda expressions available
in the functional programming language directly? Or do I have to
regress to some meta programming facilities?

Best Regards

P.S.: The code above is not the SKI conversion that leads to very short
SKI expressions. Better code is possible that checks for occurence of
the bound variable in the lambda expression body.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

雨后咖啡店 2024-10-20 07:39:51

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

回复收藏 0 原文

儭儭莪哋寶赑 2024-10-20 07:39:51

可以直接使用lamdba表达式。在 Haskell 中：（

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；它可以工作，但请检查它在概念上是否正确）

You can directly use lamdba expressions. In Haskell:

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

(note that I didn't know of SKI up to know, this snippet is a direct conversion of the definitions on Wikipedia into Haskell; it works, but do check if it's conceptually right)

回复收藏 0 原文

~没有更多了~