freearth\'s blog: 系统技术与分布式计算freearth.blog.chinaunix.net

如果你是个木匠,正在打造一个漂亮的五斗柜,你是不会在柜子后面用三合板的,哪怕那一面对着墙,永远没人看到它。你知道它在那里,所以即使是柜子后面,你也会用上好的木材。为了能在晚上睡个好觉,你会在审美和质量上自始至终争取做到最好。

  • 博客访问: 712338
  • 博文数量: 129
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1867
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(129)

文章存档

2013年(1)

2012年(9)

2011年(43)

2010年(3)

2009年(4)

2008年(51)

2007年(18)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题
Church计数的简单实现 2012-07-14 11:01:06

分类: Python/Ruby

上午看到别人的一个实现,一时来了兴趣,就自己也实现了一个。

第一部分对curry-2的定义表明,任何多参数的函数都可以实现为单参数的。这样,在后面可以定义多參函数,更清晰些。

附带额外的boolean值和条件分支的定义,很容易看出来图灵完全性。

PS:其实,在上一篇的“一个简单的元循环解释器”博文给出了图灵完全的最小定义,只是看起来不明显。本文对church计数、boolean以及分支判断的实现,完全可以在那个解释器中实现,而无需扩展解释器,也说明了它确实是图灵完全的。

  1. #lang racket

  2. ;; macro for easy testing
  3. ;; (test 'utname target-expr expectation)
  4. (define-syntax test
  5.   (syntax-rules (===)
  6.     ((_ name expr === expect)
  7.      (let ((val-expr expr) (val-expect expect))
  8.        (if (equal? val-expr val-expect)
  9.            (printf "Test ~a\tDone\n" name)
  10.            (eprintf "Test ~a\tFailed: expecting ~a, got ~a\n"
  11.                     val-expect
  12.                     val-expr))))))

  13. ;; multi-argument functions
  14. ;; curry it into a set of single argument functions
  15. (define (curry-2 f)
  16.   (lambda (x)
  17.     (lambda (y)
  18.       (f x y))))

  19. (test 'curry-add
  20.       (((curry-2 +) 1) 2) === (+ 1 2))
  21. (test 'curry-sub
  22.       (((curry-2 -) 2) 1) === (- 2 1))

  23. ;; void value
  24. ;; for functions without arguments,
  25. ;; we use a single argument function with void as its argument.
  26. (define void (lambda (x) x))

  27. (define (no-arg f)
  28.   (lambda (arg)
  29.     (f)))

  30. (test 'no-arg-current-error-port
  31.       ((no-arg current-error-port) void) === (current-error-port))
  32. (test 'no-arg-pi
  33.       ((no-arg (lambda () pi)) void) === ((lambda () pi)))

  34. ;; use non-termination to signal error
  35. (define (error . args)
  36.   ((lambda (x) (x x)) (lambda (x) (x x))))

  37. ;; boolean encoded into a choosing lambda
  38. ;; bwt: yes multiple arguments function, remember the curry-2 trick?
  39. (define true (lambda (on-true on-false) (on-true)))
  40. (define false (lambda (on-true on-false) (on-false)))

  41. ;; if expression
  42. (define iff (lambda (condition on-true on-false)
  43.               (condition on-true on-false)))

  44. (test 'boolean-if-true
  45.       (iff true
  46.           (lambda () 42)
  47.           (lambda () 43))
  48.       ===
  49.       42)
  50. (test 'boolean-if-false
  51.       (iff false
  52.            (lambda () 42)
  53.            (lambda () 43))
  54.       ===
  55.       43)

  56. ;; church numbers
  57. ;; every number is a two argument lambda,
  58. ;; n applies the first argument n times on the second.
  59. (define zero (lambda (f x) x))

  60. ;; define +1 operation
  61. (define (add1 n)
  62.   (lambda (f x)
  63.     (f (n f x))))

  64. (define one (add1 zero))
  65. (define two (add1 one))

  66. ;; define add num num
  67. (define (addd n1 n2)
  68.   (lambda (f x)
  69.     (n2 f (n1 f x))))

  70. ;; testing Church number
  71. (define (inc x) (+ x 1)) ;; this is our f for counting applications
  72. (test 'number-zero
  73.       (zero inc 0) === 0)
  74. (test 'number-one
  75.       (one inc 0) === 1)
  76. (test 'number-two
  77.       (two inc 0) === 2)
  78. (test 'number-add
  79.      ((addd two (add1 two)) inc 0) === 5)

  80. ;; from the number with add-operation and conditional branch, we can define any thing.

阅读(20259) | 评论(0) | 转发(0) |
0

上一篇:一个简单的元循环解释器

下一篇:没有了

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册