标签: lambda-calculus

我无法解释lambda立方体这个术语比维基百科更好:

[...]λ-cube是一个框架,用于探索Coquand构造计算中的细化轴,从简单类型的lambda演算开始,作为放置在原点的立方体的顶点,以及构造的微积分(更高阶)依赖型多态lambda演算作为其完全相反的顶点.立方体的每个轴代表一种新的抽象形式:

• 术语取决于类型或多态性.系统F,又名二阶lambda演算,仅通过强加此属性获得.
• 类型取决于类型或类型运算符.简单地键入lambda-calculus与类型运算符λω,只通过强加此属性获得.与系统F结合,产生系统Fω.
• 类型取决于术语或依赖类型.仅施加此属性会产生λΠ,这是一种与LF密切相关的类型系统.

所有八个计算都包括最基本的抽象形式,术语取决于术语,普通函数与简单类型的lambda演算一样.立方体中最富有的微积分,包括所有三个抽象,是结构的微积分.所有八个结石都强烈正常化.

是否有可能在Java,Scala,Haskell,Agda,Coq等语言中找到代码示例,以便在缺少此优化的结石中无法实现每个细化？

我正在研究Lambda微积分并且我坚持减少....可以用这个例子来解释减少的类型,特别是以最简单的方式减少beta.也不介意一个易于理解的教程.

(?xyz .xyz )(?x .xx )(?x .x )x

我必须实现haskell map函数来处理教会列表,其定义如下:

type Churchlist t u = (t->u->u)->u->u

在lambda演算中,列表编码如下:

[] := ?c. ?n. n
[1,2,3] := ?c. ?n. c 1 (c 2 (c 3 n))

本练习的示例解决方案是:

mapChurch :: (t->s) -> (Churchlist t u) -> (Churchlist s u)
mapChurch f l = \c n -> l (c.f) n

我不知道这个解决方案是如何工作的,我不知道如何创建这样的功能.我已经体验过lambda演算和教堂数字,但是这个练习对我来说是一个很大的问题,我必须能够在下周的考试中理解并解决这些问题.有人可以给我一个很好的消息来源,我可以学习如何解决这些问题,或者给我一些关于它是如何工作的指导？

我试图更好地掌握类型如何在lambda演算中发挥作用.不可否认,许多类型理论的东西都在我的头上.Lisp是一种动态类型语言,大致对应于无类型lambda演算？还是有一种我不知道的"动态类型的lambda演算"？

在Agda中,a的类型forall以这样的方式确定:以下都具有类型Set1(where Set1的类型Set和A类型Set):

Set ? A
A ? Set
Set ? Set

但是,以下类型Set:

A ? A

我明白,如果Set有类型Set,就会有矛盾,但我没有看到,如果上述三个术语中的任何一个有类型Set,我们就会有矛盾.那些可以用来证明是假的吗？它们可以用来表明Set : Set吗？

我正在实现一种简单的依赖类型语言,类似于Lennart Augustsson描述的语言,同时还使用绑定来管理绑定.

当检查依赖的lambda术语时,例如?t:* . ?x:t . x,我需要:

1. "Enter"键外的λ粘结剂,通过实例t来的东西
2. Typecheck ?x:t . x,屈服?x:t . t
3. Pi抽象t,屈服?t:* . ?x:t . t

如果lambda是非依赖的,我可以在步骤1中t使用它的类型实例化,因为类型是我在第2步的类型检查时需要知道的变量.但是在第3步我缺乏决定哪些变量的信息摘要.

我可以引入一个新的名称供应并t使用Bound.Name.Name包含类型和唯一名称的实例化.但我认为,bound我不应该生成新的名字.

有缺点的替代解决方案吗？

(我确信这个必须已经在这个网站上得到了解答,但搜索被C语言中的变量调用free()的概念所淹没.)

我遇到了"eta reduction"这个术语,它被定义为f x = M x ==> M如果x"不是M中的自由".我的意思是,我认为我理解它试图说的内容的主旨,看起来就像你将一个函数转换为无点样式时所做的那样,但我不知道关于x的限定符不是自由的意思.

我试图在Haskell中实现教堂数字,但我遇到了一个小问题.Haskell抱怨无限类型

发生检查:无法构造无限类型:t =(t - > t1) - >(t1 - > t2) - > t2

当我尝试做减法时.我99%肯定我的lambda演算是有效的(虽然如果不是,请告诉我).我想知道的是,我能做些什么来让haskell与我的功能一起工作.

module Church where

type (Church a) = ((a -> a) -> (a -> a))

makeChurch :: Int -> (Church a)
makeChurch 0 = \f -> \x -> x
makeChurch n = \f -> \x -> f (makeChurch (n-1) f x)

numChurch x = (x succ) 0

showChurch x = show $ numChurch x

succChurch = \n -> \f -> \x -> f (n f x) …

我正在通过SICP工作,问题2.6让我陷入了困境.在处理教会数字时,将零和1编码为满足某些公理的任意函数的概念似乎是有意义的.另外,使用零的定义导出单个数字的直接公式,并且add-1函数是有意义的.我不明白如何形成一个加号运算符.

到目前为止,我有这个.

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

通过wikipedia条目查看lambda演算,我发现plus的定义是PLUS:=λmnfx.mf(nfx).使用该定义,我能够制定以下程序.

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

我不明白的是,如何仅使用先前派生的程序给出的信息直接导出该过程.任何人都可以用某种严格的证明形式回答这个问题吗？直觉上,我想我明白发生了什么,但正如Richard Feynman曾经说过的那样,"如果我不能建造它,我就无法理解......"

我正在阅读有关Hindley-Milner Type Inference的维基百科文章,试图从中找出一些意义.到目前为止,这是我所理解的:

1. 类型分为单型或多型.
2. Monotype进一步分为类型常量(如int或string)或类型变量(如?和?).
3. 类型常量可以是具体类型(如int和string)或类型构造函数(如Map和Set).
4. 类型变量(如?和?)表现为具体类型(如int和string)的占位符.

现在我在理解多类型方面遇到了一些困难,但在学习了一些Haskell之后,我就是这样做的:

1. 类型本身有类型.正式类型的类型称为种类(即,存在不同类型的类型).
2. 具体类型(如int和string)和类型变量(如?和?)都是实物*.
3. 类型构造函数(如Map和Set)是类型的lambda抽象(例如Set,种类* -> *和Map类型* -> * -> *).

我不明白的是限定词表示什么.例如,什么??.?代表？我似乎无法做出它的正面或反面,我阅读下面的段落越多,我得到的就越混乱:

相反,具有多型∀α.α - >α的函数可以将相同类型的任何值映射到其自身,并且该同一性函数是该类型的值.另一个例子是∀α.(Setα) - > int是将所有有限集映射到整数的函数的类型.成员数是此类型的值.注意,限定符只能出现在顶级,即类型 …