Lisp 的语言特点和价值浅析

Lisp 简介

  • Lisp 于 1958 年由 John McCarthy 基于 Lambda 表达式创建。
  • Lisp 是第二古老的高级语言。（第一古老的是 Fortran）
  • Lisp 也是第一个函数式编程语言。
  • Lisp 是 List Processing 的缩写，由此可见 List 在 Lisp 中的重要性。
  • Lisp 从 1958 年开始发展出了许许多多的方言
    • 古老的 Lisp 1.5 是由 McCarthy 及其 MIT 同事实现的第一个被广泛使用的 Lisp 实现
    • 现在比较流行的 Lisp 方言有 Scheme，Common Lisp，Clojure，Emacs Lisp
  • 本文用 Scheme 和 Emacs Lisp 作例子，简要地介绍 Lisp 的基本元素与思想，以及函数式编程和面向对象编程在 Lisp 中的简单实践。

基本元素

符号表达式（Symbolic Expressions，或 S-Expressions）

  • 是一种复合的列表结构
  • 既能用来表示数据，也能表示程序结构
  • 是 Lisp 语言的基本结构
  • 最初被用来设计为 M-Expression (Meta Expression) 的一种编码，但是由于最初的 Lisp 实现为 S-Expression 的解释器，程序员们马上习惯了这种表示方式，与 M-Expression 的区别也不大，便没有实现 M-Expression 了

  • M-Expression 与 S-Expression 的对比

    M-Expression S-Expression
    (A B C) (QUOTE (A B C))
    car[x] (CAR X)
    car[append[(A B C); (D E F)]] (CAR (APPEND (QUOTE (A B C)) (QUOTE (D E F))))

基本数据类型

Lisp 中几乎只有两种基本的数据类型，即 S-Expression 的两种格式：Atom 和 List

列表 List

List 是 Lisp 中最重要的概念，可以看作只有两个节点（ 表头 car, 表尾 cdr ）的链表。

  • car 和 cdr 的名字来源于 IBM 704 计算机，分别对应了该计算机的以下两个操作
    car
    Contents of the Address part of Register number
    cdr
    Contents of the Decrement part of Register number

  • cons cons 是 construct 的缩写，是 List 的构建方法，将传入的两个参数组合为一个列表。 

    (cons 1 2)

    (1 . 2)

  • car car 的返回值是传入的列表元素在由 cons 方法创建时的第一个参数。 

    (car (cons 1 2))

    1

  • cdr cdr 的返回值是传入的列表元素在由 cons 方法创建时的第二个参数。 

    (cdr (cons 1 2))

    2

  • 多元素列表解释 

    (cons 1 (cons 2 3))

    (1 2 . 3)

    Lisp 中可以有如上所示的长度大于 2 的列表，解释如下：

    • car 和 cdr 都是指向某一对象的指针
    • 多元素列表即是一个如下结构的列表：
      • car 指向表头元素
      • cdr 指向去掉表头的剩余列表
      • 如此递归直到 cdr 为原子元素

    当然，Lisp 中也有其他形式的多元素列表。主要取决于不同解释器的实现，在此不多讨论。如： 

    (list 1 2 3 4 5)

    (1 2 3 4 5)

原子 Atom

Atom 这个名字的由来是因为被称为 Atom 的元素都是不能够再被分解的元素（indivisible），即 Atom 这个单词的一个最初的含义。

以下几个元素在 Lisp 中被称为 Atom

Number 数

包括整数，浮点数等

如 1 ， 1.2 ， 1e-10 等

Symbol 符号

相当于一般语言中的 variable 变量或函数名等概念。又因为在使用中与字符串比较接近，容易混淆。其实可以理解为指针，指向某一内存地址，比较两个 Symbol 时即比较地址是否相同。

如 a_variable ， + ， Foo 等

String 字符串

被双引号括起来的元素为字符串。

如 "foo_bar"

nil
表示空列表 () ，是 Lisp 中唯一一个既是 Atom 也是 List 的元素
t

常用来表示 true 

(atom 12) ; => t
(atom 12.3) ; => t
(atom 'hello) ; => t
(atom "hello") ; => t
(atom [1 2 3]) ; => t
(atom '(1 2 3)) ; => nil
(atom '(1 . 2)) ; => nil

变量、函数定义

Lisp 中变量与函数的定义都通过 define 操作来实现。函数可以理解为一种特殊的变量，是通过 Lambda 函数实现的。

变量

  • 定义变量的格式为 

    (define <argument-name> <value>)

  • Example 

    (define x 10)
x

    10

Lambda 函数

  • Lisp 中 lambda 也是一个基本操作，格式如下 

    (lambda (x)
  (+ x 1))
  • 即接收一个列表为函数参数表，剩下的参数为函数体
  • 返回一个匿名函数实例

函数

  • 定义函数的格式为 

    (define (<method-name> <argument1> <argument2> ... <argumentN>)
  <method-steps>)

  • 这个格式实际上是一种语法糖，是将一个匿名函数绑定到 method-name 上的缩写，展开后的格式为 

    (define <method-name>
  (lambda (<argument1> <argument2> ... <argumentN>)
    <method-steps>))
    • 由此可见，函数在 Lisp 中也是一种对象，可以作为其他函数的参数。

  • Example 

    (define (inc x)
  (+ x 1))

(inc 3)

    4

分支操作

Lisp 中主要有两种分支操作

  • cond

    • 基本结构 

      (cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>)
      (else <e>))

    • 执行顺序

      依次执行 pi，直到某一 pi 为真（t），再执行对应的 ei，并将 ei 的返回值作为 cond 的返回值。

    • else

      else 是 Lisp 中的特殊符号，在所有 pi 都不为真的情况下执行 else 对应的 expression。相当于一个恒为真的 Symbol。

  • if

    • 基本结构 

      (if <predicate>
    <consequent>
    <alternative>)

      • 相当于如下 cond 语句 

        (cond (<predicate> <consequent>)
      (else <alternative>))

Lisp 函数调用的两种解释顺序

对 S-表达式表示的函数 (define (<method-name> <argument1> <argument2> ... <argumentN>)) ，我们有两种不同的解释顺序，分别是 Applicative order 和 Normal order。

Applicative order

Applicative order 是 Scheme 采用的策略。解释顺序如下：

  • 先依次求出 argument 的值
  • 将求出的值代入函数体中求出结果返回

Normal order

Normal order 又称为 Lazy Evaluation。解释顺序如下：

  • 延迟 argument 的求值
  • 将 argument 的表达式代入函数体中
  • 直到 argument 被基本操作（如 +，-，*，if 等）调用才对 argument 进行求值

Example

(define (try a b)
  (if (= a 0) 1 b))

(try 0 (/ 1 0))
  • Applicative order
    • 对 0 和 (/ 1 0) 进行求值，此时会抛出异常
  • Normal order
    • 将 0 和 (/ 1 0) 代入 try 函数中
    • 得 (if (= 0 0) 1 (/ 1 0)) ， if 为基本语句
    • 根据 if 语句的解释顺序， (= 0 0) 成立，返回 1

Lisp 中的函数式编程简介

Lisp 是第一个采用函数式编程范式的语言。从上述的介绍中我们也可以发现 Lisp 并没有提供循环操作，本节将解释 Lisp 中的循环操作的递归实现和迭代实现，并介绍 map, reduce, filter 等常用函数，以简单介绍 Lisp 中的函数式编程范式。

循环操作

在我们常用的编程语言中，循环操作通常是通过对一个变量的迭代来实现的，常见的关键词为 for 和 while 。

但是在函数式编程中，变量的使用是要被避免的。接下来我们以对 [a, b] 区间内的整数求和函数为例，来看看如何使用函数来实现循环。

递归实现

(define (sum a b)
  (if (> a b)
      0
      (+ a (sum (+ a 1) b))))

(sum 1 10)

55

迭代实现

(define (sum a b)
  (define (sum-helper a b s)
    (if (> a b)
        s
        (sum-helper (+ 1 a) b (+ a s))))
  (sum-helper a b 0))

(sum 1 10)

55

递归实现与迭代实现的区别

  • 参考对 Lisp 函数调用的两种解释顺序，采用 Applicative order 对两种实现进行解释。
  • 递归实现
    • 经过 Applicative order 解释后得到的 S-表达式是逐渐变长的
    • 以 sum 为例，最终的 S-表达式为 (+ a (+ a 1) (+ (+ a 1) 1) ... b)
  • 迭代实现
    • 经过 Applicative order 解释后得到的 S-表达式长度与最初的调用几乎一致
    • 以 sum 为例，最终的 S-表达式为 (sum-helper b b sum)
  • 这与其他语言的实现是一致的，即：
    • 递归调用通过堆栈实现，堆栈随着调用的深度加深而变长
    • 迭代调用通过变量实现，没有变长的堆栈结构

Map, Reduce, Filter

使用递归的思想可以实现 Map, Reduce, Filter 等函数式编程中的常用函数。

Map

  • Implementation 

    (define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

Reduce

  • Implementation 

    (define (reduce op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (reduce op initial (cdr sequence)))))

Filter

  • Implementation 

    (define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

Lisp 中的面向对象编程

  • Lisp 中的面向对象特性通过闭包（Closure）和消息传递（Message Passing）来实现
  • 本节将介绍闭包和 Scheme 中类和子类的几个例子
  • 类似的思想在之后的程序语言中得到广泛应用
    • 如：在 Ruby 中闭包和消息传递是元编程（Meta Programming）的重要技术

Lisp 中的子程序环境

闭包

  • Lisp 有一个基础环境（全局环境，Global Environment）
  • 在每个环境中的变量和函数名都可看作指针，指向某一对象
  • 在调用函数时：
    1. 在当前环境的基础上构造一个子环境
    2. 将函数参数变量指向传入的参数值
    3. 依次执行函数体
    4. 遇到当前环境中未绑定的变量时，向上到父环境中查找，直到找到或到全局环境中依然未找到为止
  • 其中，第 4 步可用来构造闭包（Closure）

  • 用闭包实现 cons, car, cdr 

    (define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

let 语句

在函数定义中可用 let 语句定义局部变量： 

(define (f a b c ... z)
  (let ((<var1> <exp1>)
        (<var2> <exp2>)
        ...
        (<varn> <expn>))
    <body>)

面向对象编程

封装

  • 通过定义一个初始化函数来定义新的类
    • 该函数返回一个函数对象
    • 通过闭包的特性调用类内的函数

  • 以平面上的坐标点（point）为例 

    (define (send message obj . par)
  (let ((method (obj message)))
    (apply method par)))

(define (point x y)
  (define (getx) x)
  (define (gety) y)
  (define (add p)
    (point (+ x (send 'getx p)) (+ y (send 'gety p))))
  (define (type-of) 'point)

  (define (dispatch message)
    (cond
     ((eq? message 'getx) getx)
     ((eq? message 'gety) gety)
     ((eq? message 'add) add)
     ((eq? message 'type-of) type-of)
     (else (error "Message not understood"))))
  dispatch)

(define p (point 1 2))

(display (send 'getx p))
(newline)
(display (send 'gety p))
(newline)
(display (send 'type-of p))

    1
2
point

继承

  • 通过加入 super 实现
  • 子类在初始化时实例化一个父类对象
  • 在遇到无法处理的调用时 Fallback 到父类调用

  • 以有颜色的坐标点为例 

    (define (method-lookup object selector)
  (cond ((procedure? object) (object selector))
        (else
         (error "Inappropriate object in method-lookup: "
                object))))

(define (color-point x y color)
  (let ((super (point x y))
        (self 'nil))
    (let ((color color))

      (define (get-color)
        color)

      (define (type-of) 'color-point)

      (define (dispatch message)
        (cond ((eq? message 'get-color) get-color)
              ((eq? message 'type-of) type-of)
              (else (method-lookup super message))))

      dispatch)))

(define cp (color-point 10 20 'black))

(display (send 'getx cp))
(newline)
(display (send 'gety cp))
(newline)
(display (send 'get-color cp))

    10
20
black

不要让程序语言限制自己的编程

虽然 Lisp 是一门函数式编程语言，但是通过上面的例子我们也能在 Lisp 中实现面向对象的特性。

（另外在 C 语言中，也可以通过其他的方法实现面向对象的一些特性。）

因此，不要让程序语言成为我们编程时的枷锁，通过充分利用语言中的某些特性，我们也可以实现该语言本没有的功能。