3

据我所知，如果您想编写递归函数而不显式使用递归，则 y 组合器很有用。C 预处理器不支持递归。我们可以在 C 预处理器中实现 y 组合器以支持递归吗？

谢谢。

4

2 回答 2

3

事实上这是完全可能的，请看我的项目CSP Git Repo，这是一个完全在 C 宏预处理器上实现的 LISP 解释器，当然你也可以在它上面实现 Y 组合器。

如果您对它感兴趣，希望您能和一些测试/示例。

这是最相关的部分。（来自 csp.h）它成功地实现了闭包和 lambda，这为实现定点组合器提供了支持。

#define EVAL_e(x) x
#define _be(y) y)
#define ZIP(x)   _n() (x,_be

#define _PAIR(x,y) _e( __PAIR(x,y))
#define __PAIR(x,y) _E COND((NULL SAFE_CDR(x)((SAFE_CAR(x) SAFE_CAR(y))))((T)((SAFE_CAR (x) SAFE_CAR (y)) _e(_PAIR2(_e SAFE_CDR(x),_e SAFE_CDR(y))))))

#define _PAIR2(x,y)  _E COND((NULL SAFE_CDR(x)((SAFE_CAR(x) SAFE_CAR(y))))((T)((SAFE_CAR (x) SAFE_CAR (y)) _e(_PAIR3(_e SAFE_CDR(x),_e SAFE_CDR(y))))))

#define _PAIR3(x,y)  _E COND((NULL SAFE_CDR(x)((SAFE_CAR(x) SAFE_CAR(y))))((T)((SAFE_CAR (x) SAFE_CAR (y)) _e(_PAIR4(_e SAFE_CDR(x),_e SAFE_CDR(y))))))

#define _PAIR4(x,y)  _E COND((NULL SAFE_CDR(x)((SAFE_CAR(x) SAFE_CAR(y))))((T)((SAFE_CAR (x) SAFE_CAR (y)) _e(DELAY_INT_54(__PAIR_R) ()(SAFE_CDR(x) SAFE_CDR(y))))))
#define __PAIR_R() _$pair
#define TEST_R() TEST
#define TEST(x) test
#define _PAIR_e(x) x
#define _$pair(x) _PAIR_e(_PAIR ZIP x)
#define PAIR_EVAL(...) PAIR_EVAL2(PAIR_EVAL2(PAIR_EVAL2(__VA_ARGS__)))
#define PAIR_EVAL2(...) PAIR_EVAL3(PAIR_EVAL3(PAIR_EVAL3(__VA_ARGS__)))
#define PAIR_EVAL3(...) PAIR_EVAL4(PAIR_EVAL4(PAIR_EVAL4(__VA_ARGS__)))
#define PAIR_EVAL4(...) PAIR_EVAL_E(PAIR_EVAL_E(PAIR_EVAL_E(__VA_ARGS__)))
#define PAIR_EVAL_E(...) __VA_ARGS__
#define $pair(x) PAIR_EVAL(_$pair(x))

#define $zipped_evlis_R() $zipped_evlis
#define EVLIS_e_R() EVLIS_e
#define EVLIS_e(x) x
#define _EVLIS_ZIP(...) _n() (__VA_ARGS__,_BE
#define _BE(...) __VA_ARGS__)
#define _EVLIS_R() _EVLIS
#define _EVLIS_E(...) __VA_ARGS__
#define _EVLIS_N(...)
#define _EVLIS_B _EVLIS_E (_EVLIS_N,_EVLIS_E(_EVLIS_N,_EVLIS_N))
#define ___EVLIS(a,b,k,...) k($zipped_eval((b),(a)) DELAY_INT_2(_EVLIS_R)()(a))
#define __EVLIS(a,b,...) ___EVLIS(a,b,__VA_ARGS__ _EVLIS_E)
#define _EVLIS_EVAL_E(...) __VA_ARGS__
#define _EVLIS_EVAL_5(...) _EVLIS_EVAL_E(_EVLIS_EVAL_E(_EVLIS_EVAL_E(__VA_ARGS__)))
#define _EVLIS_EVAL_4(...) _EVLIS_EVAL_5(_EVLIS_EVAL_5(_EVLIS_EVAL_5(__VA_ARGS__)))
#define _EVLIS_EVAL_3(...) _EVLIS_EVAL_4(_EVLIS_EVAL_4(_EVLIS_EVAL_4(__VA_ARGS__)))
#define _EVLIS_EVAL_2(...) _EVLIS_EVAL_3(_EVLIS_EVAL_3(_EVLIS_EVAL_3(__VA_ARGS__)))
#define _EVLIS_EVAL(...) _EVLIS_EVAL_2(_EVLIS_EVAL_2(_EVLIS_EVAL_2(__VA_ARGS__)))

#define _EVLIS(x) __EVLIS _EVLIS_ZIP(x)
#define $zipped_evlis(x,y) _EVLIS_EVAL(_EVLIS y x (_EVLIS_B))

#define $zipped_eval_R() $zipped_eval
#define $zipped_eval(e,a) /**sth irrelevant**/
        ($eq(SAFE_CAR SAFE_CAR e (lambda))\
        (DELAY_INT_26(EVAL_e_R)() DELAY_INT_23($zipped_eval_R)()(\
        EVAL_e(EVAL_e(EVAL_e(EVAL_e(SAFE_CAR SAFE_CDR SAFE_CDR SAFE_CAR e)))),\
        EVAL_e(APPEND DELAY_INT_13($pair_R)()(EVAL_e(EVAL_e(EVAL_e(SAFE_CAR SAFE_CDR SAFE_CAR e)))\
                                              (DELAY_INT_19($zipped_evlis_R)()(EVAL_e(_e EVAL_e(SAFE_CDR e)), a)))a)))\
        /**end of eval recursion**/

#define $pair_R() $pair
#define EVAL_e_R() EVAL_e
#define $eval_E(...) __VA_ARGS__
#define $eval_expand5(...) $eval_E($eval_E($eval_E(__VA_ARGS__)))
#define $eval_expand4(...) $eval_expand5($eval_expand5($eval_expand5(__VA_ARGS__)))
#define $eval_expand3(...) $eval_expand4($eval_expand4($eval_expand4(__VA_ARGS__)))
#define $eval_expand2(...) $eval_expand3($eval_expand3($eval_expand3(__VA_ARGS__)))
#define $eval_expand(...) $eval_expand2($eval_expand2($eval_expand2(__VA_ARGS__)))
#define $zeval(x,y) $eval_expand($zipped_eval(x,y))
于 2018-03-29T03:24:54.383 回答
1

Y 组合器是一个高阶函数，它需要语言中的高阶函数支持来实现显式递归替换。因此，对于特定任务，这可以用 Scheme、SML 和其他功能语言完成。

我们稍后再谈 C 预处理器，但 C 本身呢？可以在 C 中使用高阶函数，因为我们可以将函数引用作为函数参数传递并返回它们以模拟高阶函数。然而，语言中缺乏对闭包的支持不允许实现 Y 组合器。

由于预处理器比 C 更具限制性，因此无法实现基于 lambda 演算概念的 Y 组合器。Y组合子的应用只能在完全支持高阶函数的函数式编程语言中实现。

C 预处理器非常简单，因为它只在文本中进行字符串替换。我不会尝试将 lambda 演算和函数式编程中的任何概念应用于它。

于 2013-01-18T21:53:56.283 回答