项目作者: luohaha

项目描述 :
lambda calculus interpreter
高级语言: Scheme
项目地址: git://github.com/luohaha/lambda-calculus.git
创建时间: 2016-08-25T15:55:53Z
项目社区:https://github.com/luohaha/lambda-calculus

开源协议:GNU General Public License v3.0

下载


lambda-calculus

This is a lambda calculus interpreter.

Usage

  1. cd lambda/
  2. ./run [filename]

Need chezscheme

Grammar

  1. <expression> ::= <id>
  2. <expression> ::= (lambda <id> <expression>)
  3. <expression> ::= (<expression> <expression>)

概念介绍

更多关于lambda演算的解释在这里可以看到。

辅助函数

  1. (Tag <id> <expression>)

id为expression的缩写。

  1. (display <expression>)

打印规约之后的结果。

  1. (display-integer <expression>)

打印规约之后结果的整数值。

  1. (display-boolean <expression>)

打印规约之后结果的布尔值。

例子

  1. ;;Y combination
  2. (Tag Y (lambda f ((lambda x (f (x x))) (lambda x (f (x x))))))
  3. ;;integer
  4. (Tag 0 (lambda p (lambda x x)))
  5. (Tag 1 (lambda p (lambda x (p x))))
  6. (Tag 2 (lambda p (lambda x (p (p x)))))
  7. (Tag 3 (lambda p (lambda x (p (p (p x))))))
  8. ;;boolean
  9. (Tag true (lambda x (lambda y x)))
  10. (Tag false (lambda x (lambda y y)))
  11. ;;condition
  12. (Tag if (lambda x x))
  13. (Tag zero? (lambda x ((x (lambda y false)) true)))
  14. ;;data structure
  15. (Tag cons (lambda x (lambda y (lambda f ((f x) y)))))
  16. (Tag car (lambda f (f (lambda x (lambda y x)))))
  17. (Tag cdr (lambda f (f (lambda x (lambda y y)))))
  18. ;;operator
  19. (Tag increment (lambda n (lambda p (lambda x (p ((n p) x))))))
  20. (Tag decrement (lambda n (lambda f (lambda x (((n (lambda g (lambda h (h (g f))))) (lambda u x)) (lambda u u))))))
  21. (Tag + (lambda m (lambda n (lambda f (lambda x ((m f) ((n f) x)))))))
  22. (Tag - (lambda m (lambda n ((n decrement) m))))
  23. (Tag * (lambda m (lambda n (lambda f (m (n f))))))
  24. (Tag pow (lambda m (lambda n ((n (* m)) 1))))
  25. (Tag >= (lambda m (lambda n (zero? ((- n) m)))))
  26. (Tag <= (lambda m (lambda n (zero? ((- m) n)))))
  27. (Tag and (lambda m (lambda n ((m n) false))))
  28. (Tag or (lambda m (lambda n ((m true) n))))
  29. (Tag not (lambda m ((m false) true)))
  30. (Tag mod (lambda f (lambda m (lambda n (((if ((<= n) m))
  31. ((f ((- m) n)) n))
  32. m)))))
  33. (Tag add-list (lambda f (lambda n (((if (zero? n)) 0) ((+ (f (decrement n))) n)))))
  34. ;;求规约之后的结果
  35. (display ((pow 3) (cdr ((cons 2) 3))))
  36. ;; => (lambda f (lambda x4 (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f x4)))))))))))))))))))))))))))))
  37. ;;求规约之后的结果,转化为integer
  38. (display-integer ((add-list (Y add-list)) (increment 3)))
  39. ;; => 10
  40. ;;求规约后的结果
  41. (display (((mod (Y mod)) (increment (increment 3))) 3))
  42. ;; => (lambda f1793 (lambda x1894 (f1793 (f1793 x1894))))
  43. ;;求规约之后的结果,转化为boolean
  44. (display-boolean (((if ((and true) true)) ((or false) false)) true))
  45. ;; => #f