标签: lambda-calculus

谁能告诉我学习lambda演算的先决条件是什么(如果有的话)？

我开始学习lambda演算,我需要在Erlang中实现I,S,K组合器.当然,S,K,我代表:

S =λxyz.xz(yz)K =λxy.xI=λx.x

我在纸上理解I = SKK转换没有问题(如此处所示:为了证明SKK和II是beta等价的,lambda演算)但似乎在功能语言和高阶函数时我不理解它. ..

我设法做了我和K(让我们说在模块中test):

i(X) -> X.
k(X) -> fun(Y) -> X end.

我也知道如何运行K x(K x)(SKK x = K x(K x))

kxk(X) -> (k(X))(k(X)).

但我无法理解它编写S组合器.我试过了:

s(X) -> fun (Y) -> fun(Z) -> X,Z (Y,Z) end end.

但是,我仍然无法将SKK x转换为x

我尝试像这样运行它:

skkx(X) ->  s((k((k(X))))).

任何帮助将不胜感激,因为我完全迷失了.

是否有无类型lambda演算的解释器(或编译器)？(根据这个帖子,它是可能的.)我认识到它作为一种编程语言几乎没有用处,特别是如果大部分语言(例如数字和布尔运算符)是由用户或库实现的.语言本身.但是,我仍然认为这对学习和探索微积分很有用.对于这个,解释器比编译器更可取,因为它们可以工作.有谁知道这样的节目？

我想测试一下我针对相当大的Lambda Calculus表达式测试集编写的Lambda Calculus解释器。有谁知道我可以使用的Lambda Calc表达式生成器（在Google上进行首次搜索后找不到任何内容）？这些表达显然必须适当地形成。

更好的是，尽管我自己创建了多个示例并制定了解决方案，以便可以检查结果，但是有人知道（很好）解决了Lambda微积分减少问题的方法吗？我可以自己输入表达式，因此拥有多种更简单（更大）的lambda演算表达式来测试我的解释器（目前可以建模正常顺序和按名称调用评估策略）更为重要。

任何帮助或指导将不胜感激。

是否可以在不使用add1等语言原语的情况下将教堂数字转换为整数表示？

我遇到的所有例子都使用了一个原语来降级到int

例:

 plus1 = lambda x: x + 1
 church2int = lambda n: n(plus1)(0)

例2:

 (define (church-numeral->int cn)
    ((cn add1) 0))

我正在尝试使用微型lisp内部解释器(仅使用John McCarthy的10条规则),并且想要了解是否可以在不添加原语的情况下完成.

在这篇论文中，作者建议在 lambda 术语之间进行翻译：

data Term = Zero | Succ Term | App Term Term | Lam Term

和交互网络：

data Net = -- if I understood correctly
    Apply Net Net Net 
    | Abstract Net Net Net
    | Delete Net Net Int
    | Duplicate Net Net Net Int
    | Erase Net

不幸的是我无法理解他的编译算法。似乎缺少实际的算法，我不知道他对第三页上的图像是什么意思。我已经尝试通过查看已发布的源代码来理解它，但是作者使用他自己的图形重写 DSL 来定义它，所以我必须先学习它。翻译是如何作为普通 Haskell 函数实现的？

我对计划函数式编程真的很陌生。我最近在 lambda 演算中遇到了 Y-combinator 函数，就像这样Y ? (?y.(?x.y(xx))(?x.y(xx)))。我想在方案中实现它，我搜索了很多，但我没有找到任何与上面给出的结构完全匹配的实现。我发现的其中一些如下：

(define Y
(lambda (X)
  ((lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg))))
   (lambda (procedure)
     (X (lambda (arg) ((procedure procedure) arg)))))))

和

(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

如您所见，它们与此Y ? (?y.(?x.y(xx))(?x.y(xx)))组合器函数的结构不匹配。如何以完全相同的方式在方案中实现它？

我尝试了以下代码,但它会生成类型错误.

sa f = f f

• Occurs check: cannot construct the infinite type: t ~ t -> t1
• In the first argument of ‘f’, namely ‘f’
  In the expression: f f
  In an equation for ‘sa’: sa f = f f
• Relevant bindings include
    f :: t -> t1
      (bound at fp-through-lambda-calculus-michaelson.hs:9:4)
    sa :: (t -> t1) -> t1
      (bound at fp-through-lambda-calculus-michaelson.hs:9:1)

Run Code Online (Sandbox Code Playgroud)

假设我们有一种编程语言ℤ,它具有以下语法:

? := 0 | 1 | (+ ? ?) | (* ? ?) | (- ? ?) | (max ? ?)

为方便起见,我们可以使用以下语言定义新的绑定表单:

1. (not x) = (- 1 x)
2. (abs x) = (- (max 0 (+ x x)) x)
3. (min x y) = (- 0 (max (- 0 x) (- 0 y)))
4. (nil x) = (not (min 1 (abs x)))

这种语言足以表达分支和比较运算符:

5. (if x y z) = (+ (* x y) (* (not x) z))
6. (eq x y) = (nil (- …

我最近一直在学习β微积分。我了解未类型化和类型化的α演算之间的区别。但是，我对Hindley-Milner类型系统和类型化α-微积分之间的区别还不太清楚。是关于参数多态性还是其他差异？

谁能清楚指出两者之间的差异（和相似之处）？