标签: lambda-calculus

我正在努力理解lambda演算和教会数字的基础知识.我一直在做很多阅读和练习,但我似乎一直在试图看看一些功能是如何工作的.

我坚持的例子如下.也许有人可以解释我哪里出错了.

1号教堂的数字可以表示为:

?f. ?x. f x

教会数字(m ⁿ)的取幂函数可以表示为:

?m. ?n. n m

我想要做的就是通过将指数函数应用于1和1,我得到1,因为1 ¹ = 1.我这样做,所以我更好地理解这些函数是如何工作的.我的工作如下,每次都卡住了:

// Exp (1 1)
(?m. ?n. n m) (?f1. ?x1. f1 x1) (?f2. ?x2. f2 x2)
// Substitute for m
(?n. n (?f1. ?x1. f1 x1)) (?f2. ?x2. f2 x2)
// Substitute for n
(?f2. ?x2. f2 x2) (?f1. ?x1. f1 x1)
// Substitute for f2
(?x2. (?f1. ?x1. f1 x1) x2)
// Substitute for f1
?x2. (?x1. x2 x1)

在那里我被卡住了.我失去了两个f …

这是我遇到问题的代码:

{-# LANGUAGE GADTs, LANGUAGE DataKinds #-} 

-- * Universe of Terms * -- 

type Id = String 

data Term a where 
   Var :: Id -> Term a
   Lam :: Id -> Type -> Term b -> Term (a :-> b)
   App :: Term (a :-> b) -> Term a -> Term b 
   Let :: Id -> Term a -> Term b -> Term b 

   Tup :: Term a -> Term b -> Term (a :*: b)   -- * existing …

现在是lambda演算的一个众所周知的定理,任何带有两个或多个参数的函数都可以通过currying作为一个带有一个参数的函数链来编写:

# Pseudo-code for currying
f(x,y) -> f_curried(x)(y)

事实证明,这不仅在研究函数的行为方面,而且在实际应用中都非常强大(Haskell等).

但是,似乎没有讨论返回值的函数.程序员通常通过返回一些元对象(R中的列表,C++中的结构等)来处理它们无法从函数返回多个值.它总是让我觉得有点像一个kludge,但它是一个有用的.

例如:

# R code for "faking" multiple return values
uselessFunc <- function(dat) {
   model1 <- lm( y ~ x , data=dat )
   return( list( coef=coef(model1), form=formula(model1) ) )
}

问题

1. lambda演算有多少关于多重返回值的说法吗？如果是这样,会得出任何令人惊讶的结论吗？
2. 同样,任何语言都允许真正的多重返回值吗？

我正在考虑像Ruby这样的纯面向对象语言,其中包括数字,int,浮点数和字符串在内的所有内容本身就是对象.这与纯函数式语言是一回事吗？例如,在Haskell中,Numbers和Strings是否也起作用？

我知道Haskell基于lambda演算,它将所有内容(包括数据和操作)表示为函数.对我来说,"纯粹的函数式语言"将所有内容都作为一个函数进行建模,并且保持一个函数最常返回相同输出且具有相同输入且没有状态的定义,这似乎是合乎逻辑的.

我最近在lambda演算中编写了很多程序,我希望我可以实时运行其中一些程序.然而,尽管趋势功能范例基于lambda演算和B减少规则,但我找不到一个不是玩具的单一评估者,而不是效率.功能语言应该很快,但我知道的那些实际上并不提供对普通表单的访问(参见Haskell的惰性求值程序,Scheme的闭包等),因此不能用作LC求值程序.

这让我想知道:只是不可能有效地评估lambda演算术语,它只是一个历史事故/缺乏兴趣,没有人决定为它创建一个快速评估者,或者我只是缺少一些东西？

我们偶尔会有人询问在Haskell中实现无类型的lambda演算.[当然,我现在找不到任何这些问题,但我确定我已经看过了!]只是为了咯咯笑,我以为我会花一些时间玩这个.

做一些像这样的事情是微不足道的

i = \ x -> x
k = \ x y -> x
s = \ f g x -> (f x) (g x)

这非常有效.但是,只要你尝试做类似的事情

s i i

类型检查员正确地抱怨无限类型.基本上,无类型lambda演算中的所有东西都是一个函数 - 这实际上意味着所有函数都具有无限的特征.但是Haskell只允许有限度的函数.(因为,真的,为什么你想要无限的灵魂？)

好吧,事实证明我们可以很容易地采取这种限制:

data Term = T (Term -> Term)

T f ! x = f x

i = T $ \ x -> x
k = T $ \ x -> T $ \ y -> x
s = T $ \ …

假设您想要找到T满足以下等式的λ演算程序:

(T (? f x . x))            = (? a t . a)
(T (? f x . (f x)))        = (? a t . (t a))
(T (? f x . (f (f x))))    = (? a b t . (t a b))
(T (? f x . (f (f (f x)))) = (? a b c t . (t a b c))

在这种情况下,我手动找到了这个解决方案:

T = (? t . (t (? b c d . (b (? …

我采用了AndrásKovács的DBIndex.hs,这是一个非常简单的依赖类型核心的实现,并且尽可能地进一步简化它,而不是"破坏"类型系统.经过几次简化后,我留下了更小的东西:

{-# language LambdaCase, ViewPatterns #-}

data Term
  = V !Int
  | A Term Term
  | L Term Term
  | S
  | E
  deriving (Eq, Show)

data VTerm
  = VV !Int
  | VA VTerm VTerm
  | VL VTerm (VTerm -> VTerm)
  | VS
  | VE

type Ctx = ([VTerm], [VTerm], Int)

eval :: Bool -> Term -> Term
eval typ term = err (quote 0 (eval term typ ([], [], 0))) where

  eval :: Term -> …

我想知道,在Java-8中实现alpha等价比较是否有任何好的方法(如果可能的话)？

显然,这两个lambda-s是α等价的.让我们假设在某些情况下我们想要发现这个事实.如何实现？

Predicate<Integer> l1 = x -> x == 1;
Predicate<Integer> l2 = y -> y == 1;

通过查看代码而不是阅读冗长的解释,我更喜欢学习.这可能是我不喜欢长篇学术论文的原因之一.代码是明确的,紧凑的,无噪音的,如果你没有得到的东西,你可以玩它 - 不需要问作者.

这是Lambda微积分的完整定义:

-- A Lambda Calculus term is a function, an application or a variable.
data Term = Lam Term | App Term Term | Var Int deriving (Show,Eq,Ord)

-- Reduces lambda term to its normal form.
reduce :: Term -> Term
reduce (Var index)      = Var index
reduce (Lam body)       = Lam (reduce body)
reduce (App left right) = case reduce left of
    Lam body  -> reduce (substitute (reduce right) body)
    otherwise -> App (reduce left) (reduce …