标签: lambda-calculus

我知道:

(cons [p] [q]) is ((s ((s i) (k [p]))) (k [q]))
(car [lst]) is ([lst] k)
(cdr [lst]) is ([lst] (k i))

我想写一个这样的列表

(cons [a] (cons [b] (cons [c] [nil])))

,这将是这样的:

((s ((s i) (k [a]))) (k ((s ((s i) (k [b]))) (k ((s ((s i) (k [c]))) (k [nil]))))))

但我不知道如何将'nil'编译成S,K和I组合器.有人知道吗？

在此先感谢Edwin Jose Palathinkal

我在理解lambda演算运算符优先级时遇到了问题.

例如,以下代码:

lambda x.x z lambda y.x y

将是:

lambda x. (x (z lambda y. x y))

要么

lambda x. ((x z) (lambda y. x y))

？

更复杂的例子:

(lambda x.x z) lambda y.w lambda w.w x y z

在上面的例子里,括号去了哪里？

我知道lambda应用程序是左关联的,但lambda值是否优先于应用程序？

许多功能可以简化为自由形式 - 但这对所有人来说都是如此吗？

例如,我不知道如何做到:

apply2 f x = f x x 

我必须为>,<和!=创建一些Lambda函数

我不知道如何,有人可以帮助我吗？PS:我们刚开始使用Lambda Calculus,所以请不要假设任何先前的知识.

谢谢你的期待!

编辑 - 我的意思是Lambda微积分中的算术

编辑2 - 更准确:寻找教会编码(lambda演算)来定义 < , > , !=

编者注:我认为这是OP试图提出的问题:

我试图使用Church编码在无类型lambda演算中实现以下操作:

1. 大于(GT或>).
2. 小于(LT或<).
3. 不等于(NE或!=).

我已经知道如何实现以下内容:

1. 布尔值true(TRUE或?x.?y.x).
2. 布尔值false(FALSE或?x.?y.y).
3. 逻辑和(AND或?p.?q.p q p).
4. 逻辑或(OR或?p.?q.p p q).
5. 逻辑不(NOT或?p.?a.?b.p b a).

你会怎么写的GT,LT并且NE在无类型演算的功能呢？

我希望你们都没事.我正在海港实施定点Y-combinator,我遇到了一些麻烦.嗯,Y-组合子可以由lambda演算定义为:

Y = (?h.?F.F(? x.((h(h))(F))(x))) (?h.?F.F(? x.((h(h))(F))(x)))

我正试图通过性能问题对Y-combinator应用memoization.我目前的实施是:

Function YMem( bF, aCache )
   Local xAnswer
    If !lCache ; lCache := { } ; EndIf
    Return { |Arg| Iif( aCache[ Arg ] ;
        , /* then      */ aCache[ Arg ];
        , /* otherwise */ aCache[ Arg ] := ;
            Eval( Eval( bF, { |N| Eval( Eval( YMem, bF, aCache ), N ) } ), Arg ) ) }

基本上,我不能在块内使用语句,但我可以使用表达式,它工作得很好.我正在避免无限递归,并且限制通过0到无限.

直到这个时候,它编译得很好,但是当我试图访问外部块的变量时,Harbour在Face中踢我!

为了测试的Y组合子的实现,我尝试应用斐波那契序列的简单implemetation,但是当我返回接收参数的块G,隐式返回接收参数的块N,Gbecames对我来说不可用,编译器说我说"外部代码块变量是遥不可及的". …

让纯粹的λ函数成为除了抽象和应用之外的任何术语.在JavaScript上,可以通过将所有抽象应用于收集其参数列表的可变参数函数来推断纯函数的源代码.也就是说,这是可能的:

lambdaSource(function(x){return x(x)}) == "?x.(x x)"

请参阅此要点上的lambdaSource代码.这个函数对我的兴趣特别有用,因为它允许我使用现有的JS引擎来标准化无类型的lambda演算表达式,比我自己编写的任何天真评估器快得多.此外,我知道λ-calculus函数可以在Haskell中用以下方式表示unsafeCoerce:

(let (#) = unsafeCoerce in (\ f x -> (f # (f # (f # x)))))

lambdaSource由于缺乏可变参数函数,我不知道如何在Haskell中实现.是否有可能在Haskell上推断出纯λ函数的归一化源,这样:

lambdaSource (\ f x -> f # (f # (f # x))) == "? f x . f (f (f x))"

？

据我所知,在Haskell等语言中,以及作为lambda演算的一部分,每个lambda表达式都有自己的作用域,所以如果我有嵌套的lambda表达式,例如:\x -> (\x -> x)那么第一个\x参数与第二个参数不同\x.

在Java中,如果执行此操作,则会出现编译错误,就像您x再次使用作为参数名称或lambda中的局部变量名称一样,如果它已在封闭范围内使用,例如作为方法参数.

有没有人知道为什么Java以这种方式实现了lambda表达式 - 为什么不让它们引入一个新的作用域级别并且表现得像一个匿名类呢？我假设是因为某些限制或优化,或者可能是因为lambdas必须被黑客入侵现有语言？

我开始感兴趣,并没有在一个地方找到相应术语的列表:

Map <-> Morphism

Foldable <-> Catamorphism

...

谁可以补充术语列表

有没有人知道如何在java中编写(无类型)lambda演算的基本表达式？即

• 身份(λx.x),
• 自我应用(λx.xx)和
• 功能应用(λx.λarg.xarg)

Java不是无类型的,所以我想任何解决方案都必须适应类型.但我只发现以下内容,请阅读解决方案:

static<T> Function<T,T> identity() {
    return x->x;
}

static<T> Function<? extends Function<? super Function,T>,T> self() {
    return x->x.apply(x);
}

static <B,C> Function<? extends Function<B,C>, Function<B,C>> apply() {
   return x -> arg -> x.apply(arg);
}

我甚至不确定它们是否正确(!).任何人都可以提出更好的选择吗？

编辑:注意,我试图尽可能少地使用语法糖或现成函数来应用lambda演算的基本概念.例如,我知道有identity(),BiFunction等.我试图实现上面只有基本的lambda结构可用,这意味着基本上只有函数应用程序

假设我有两个以下类型的Haskell函数,并激活了ExplicitForAll,

f :: forall a. (a -> Int)
g :: forall a. (Int -> a)

在我看来,该类型g是同构Int -> (forall a. a)的,因为例如类型g(2)为forall a. a.

但是,类型f看起来并不是同构的(forall a. a) -> Int.f是一个多态函数,它知道在每个输入类型上计算什么a,在数学中我想它宁可是一系列函数; 但我认为它不能处理具有所有类型的单个参数.

是类型lambda演算的规则,类型量词分布在函数目标类型上,而不是函数源类型上吗？

该类型是否(forall a. a) -> Int存在于Haskell中,可能限制为类型类(forall a. SomeClass a => a) -> Int？它有用吗？