C. *_*ann 62
这取决于你的意思是最小的.
首先,函数式语言的祖先首先是数学逻辑.某些逻辑的计算使用是在事后发生的.从某种意义上说,许多数学系统(其核心通常非常小)可以称为函数式语言.但我怀疑这就是你所追求的!
最着名的是Alonzo Church的lambda演算,其中有变体和后代:
最简单的形式是所谓的无类型lambda演算 ; 这里只包含lambda抽象,对它们的使用没有任何限制.仅使用匿名函数创建数据结构是通过所谓的Church编码完成的,并通过基本操作来表示数据; 数字5变成"重复5次",依此类推.
Lisp族语言只不过是无类型的lambda演算,增加了原子值,cons细胞和其他一些东西.我怀疑Scheme在这里是最简约的,好像记忆为我服务它首先是作为教学语言创建的.
当无类型表格被证明是不一致时,lambda演算的原始目的,即描述逻辑证明的原始目的失败,这是"允许你证明虚假是真实的"的礼貌用语.(历史琐事:证明这一点的论文,当时是一个重要的事情,通过编写一个逻辑证明,在计算方面,进入一个无限循环.)无论如何,通过引入类型恢复作为逻辑的用途lambda演算.然而,这些不一定直接用作编程语言,特别是因为逻辑上合理使得语言不是图灵完整的.
然而,类似于Lisps从无类型lambda演算中得到的结果,使用内置递归,代数数据类型和其他一些东西扩展的类型化lambda演算可以获得扩展的ML系列语言.这些内容往往非常简单,语法结构在很多情况下都可以直接翻译成lambda术语.除了明显的ML方言,这还包括Haskell和一些其他语言.但是,我不知道任何特别简约的类型化函数语言; 这种语言的可用性可能比极简主义的无类型语言差得多.
因此,就lambda演算变量而言,纯粹的无类型lambda演算没有额外的特征是Turing-complete,并且尽可能小!
然而,可以说更小的是完全消除"变量"的概念 - 事实上,这最初是为了简化关于逻辑系统的元数学证明,如果内存为我服务 - 并且只使用称为组合器的高阶函数.我们在这里:
组合逻辑本身,最初由MosesSchönfinkel发明并由Haskell Curry广泛开发.例如,每个组合器由简单的替换规则定义Sxyz = xz(yz).小写字母与此定义中的变量一样使用,但请记住,组合逻辑本身不使用变量,或根本不为任何名称指定名称.可以肯定的是,组合逻辑很小,但不像编程语言那么友好.最着名的是SK组合基地.S的定义如上例所示; K是Kxy = x.仅这两个组合器足以让图灵完成!这几乎是极其微不足道的.
Unlambda是一种基于SK组合器的语言,通过一些具有特殊属性的额外组合器扩展它.较少,但让你写"Hello World".
但是,即使是两个组合器也比你需要的多.存在各种单组合基础; 也许最着名的是iota Combinator,定义为?x = xSK,用于极简主义语言,也称为Iota
另外一些值得注意的是Lazy K,它与Unlambda的区别在于不引入额外的组合子,没有副作用,并且使用惰性评估.基本上,它是基于组合器的深奥语言世界的Haskell.它既支持SK基础,也支持iota组合.
你认为最"微不足道"中的哪一个可能是品味问题.
可以说是最简单的函数式语言是iota和Jot,因为它们只使用一个组合器(而unlambda需要两个).这是一个简短的解释:http://web.archive.org/web/20061105204247/http: //ling.ucsd.edu/~barker/Iota/