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 的列表,解释如下:

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

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

    (list 1 2 3 4 5)
    

    (1 2 3 4 5)

原子 Atom

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

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

Number 数

包括整数,浮点数等

11.21e-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 中的函数式编程范式。

循环操作

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

但是在函数式编程中,变量的使用是要被避免的。接下来我们以对 [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 语言中,也可以通过其他的方法实现面向对象的一些特性。)

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