java输入字符串 函数式编程简介(2)

而最后一个问题，数学是确定的吗？也就是说，存在一个算法判定一个给定的命题是否是不确定的吗（Entscheidungsproblem 确定性问题）？这个问题引起了阿隆佐·邱奇和年轻的阿兰·图灵的兴趣。阿隆佐·邱奇的lambda calculus和图灵的图灵机构造出了可计算数，图灵的那篇论文 ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM 的意义不在于证明可计算数是否可数，而在于证明可判定性是否成立。在1936年他们对判定性问题分别独立给出了否定的答案。也就是现在被我们熟知的图灵停机问题：不存在这样一个程序（算法），它能够计算任何程序（算法）在给定输入上是否会结束（停机）。图灵借此发明了通用图灵机的概念，为后来的冯·诺依曼体系的计算机体系提供了理论基础。

Lambda 表达式包含三个要素

变量

lambda 抽象

lambda 应用

据此我们可以用函数给出布尔值的定义

data BOOL = FALSE | TRUE
TRUE = λx.λy.x
FALSE = λx.λy.y

not = λb.b FALSE TRUE
and = λb1.λb2.b1 b2 FALSE
or  = λb1.λb2.b1 TRUE b2
xor = λb1.λb2.b1 (not b2) b2

自然数的定义

data NAT = Z | S NAT
0 = λf.λs.s
1 = λf.λs.f s
2 = λf.λs.f f s

succ n = λf.λs.f (n f s)
zero? n = n (λb.FALSE) TRUE
add = succ n1 n2

在这之后，随着通用计算机的产生，人们发觉使用机器码写程序太没有效率。所以1956年左右，John Buckus发明了Fortran（FORmula TRANslating 的缩写）语言，如果对编译原理有了解，那么对BNF范式就不陌生了。与此同时，John McCarthy 发明了Lisp语言，现代的Clojure就是Lisp的方言之一。1966年，Niklaus Wirth发明了Pascal。1969年，Ken Thompson和Dennis Ritchie发明了C语言，过程式语言由于其高效和可移植性迅速崛起。1973年，Robin Milner 发明了ML（Meta Language），后来演变成了OCaml和Stardard ML。1977年，John Buckus在其图灵奖的演讲中创造了 Functional Programming 这个词。1990年，惰性求值的函数式编程语言 Haskell 1.0 发布。

(def Y (fn [f]
         ((fn [x] (x x))
          (fn [x]
            (f (fn [y]
                 ((x x) y)))))))

Lisp是动态语言，使用S表达式

ML和Haskell都是静态强类型函数式语言

ML是第一个使用Hindley-Milner type inference algorithm的语言

Lisp和ML都是call-by-value，但是Haskell则是call-by-name

Lisp和ML都是不纯的编程语言，但是Haskell是side effect free的

函数是一等公民，指的是你可以将函数作为参数、返回值、数据结构存在，而且不仅可以用函数名引用，甚至可以匿名调用。java输入字符串

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-83096-2.html