Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

13 Feb 2021

The Scheme Programming Language读书笔记【一】

The Scheme Programming Language 读书笔记,chapter 1,2.

Chapter 1 Introduction

scheme支持结构化的数据类型,比如strings, lists以及vectors,还有传统的数据类型,比如numbers和characters。

scheme是一个简单的语言,只有少数的语法格式和语义概念。但是掌握scheme却是具有挑战性的。

scheme的标准化是通过Revised Report来进行的。

scheme中的数据值(objects)的存储控件是动态按需分配的,并且通过垃圾回收机制自动回收。所有的objects都是第一级别的数据值。其他语言中的复合类型值,比如书数组,则可能是静态分配,或者在进出block的时候分配释放,或者是程序员负责。

表面上scheme是传值调用的语言。但实际上scheme有可能调用的时候传的是指针。不过这个不需要用户操心,只需把它当作传值即可。

scheme的常见数据结构是symbol(符号,也就是atom)或者lists(列表)。

scheme的变量具有文本作用域。其程序是按部块(block)组织的。内层部块中的变量会遮盖外层部块的同名变量。

在大多数语言中,一个过程是一个被命名了的代码部块。在有些语言中,过程内部可以嵌套其他过程,但是只能在过程内部执行。另外的语言中,过程只能在最外层定义。scheme中的过程可以在另一个过程中定义,也可以在定义过程之外的地方执行,并且会携带相应的本地变量。

schemd中的过程并不总是需要名字。而且可以递归执行。尾递归则用来表示迭代或者循环。scheme实现的一个要求是必须用跳转(goto)来实现尾递归。

scheme通过continuation来实现各种控制结构。continuation是一个程序的执行点,可以在程序执行过程的任意时候获得。同其他的过程一样,continuation是第一级别的对象,可以在创建之后的任意时间的执行。continuation可以用来实现backtracking,multithreading,以及coroutine。

通过语法扩展,scheme运行自定义语法格式。

scheme从Lisp演化而来,通常被看作Lisp的一个分支。但是文法作用域和部块结构是从Algol 60借鉴的。Scheme是第一个支持以下特性的scheme方言: 文法作用域,部块结构,第一级别过程,尾递归跳转,continuation,支持文法作用域的语法扩展。

同为Lisp现代方言的还有Common Lisp。Common Lisp和Scheme互相影响和学习。但是Common Lisp不支持文法作用域的语法扩展、没有将过程和其他数据对象一视同仁,不支持continuation,没有强制以跳转实现尾递归。但是Common Lisp则实现了很多Scheme不具有的控制结构。

略过下面章节

  • Section 1.1. Scheme Syntax
  • Section 1.3. Typographical and Notational Conventions

Section 1.2. Scheme Naming Conventions

  • 判定语以?结尾,例如eq?,zero?,string=?等等。常用比较操作符例外
  • 类型判定语的命名方式是类型加上?
  • character, string, 以及vector相关过程以char-, string-, vector-开头,例如string-append
  • 类型转换用的方法以type1->type2方式命名,如vector->list
  • 带副作用的过程或者语法格式会以感叹号结尾,如set!以及vector-set!

Chapter 2. Getting Started

scheme支持repl(read-evaluate-print loop)。大多数scheme可以通过load加载文件中的代码。

下面的代码可以通过(load "reciprocal.ss")加载。

; reciprocal.ss

(define reciprocal
  (lambda (n)
    (if (= n 0)
      "oops!"
      (/ 1 n))))

Section 2.2. Simple Expressions

scheme的数字类型支持精确(exact)或者不精确(inexact)的整数、有理数、实数以及复数。精确类型的整数和有理数支持任意精度。非精确的数字类型通常采用IEEE的浮点数表示。

在很多语言中,数组是默认的聚合类型,但在scheme中列表是默认的聚合类型。list的形式是(obj1 obj2 ...),默认情况下list会被当作过程执行。可以通过quote关键字来转义,例如(quote (obj1 obj2 ...))。quote也可以通过'简化。list的这个特性可以看作是代码和数据一体化的一种表现形式。

但是数字和字符串不会被当作代码,只会白当作数据,所以quote和不quote效果是一样的。

list上的两个基本操作:car和cdr出场了。这两个的操作对象都是非空list。list的每个节点可以看作一个pair,pair包含当前数据,以及后续pair的引用。car取当前数据,cdr取后续pair。cons则用来构建一个pair。

list的最后一个pair指定cdr时必须返回一个空list,否者这个list就是一个improper list。具体的定义是,空list是一个proper list,任何cdr返回proper list的list都是proper list。

不适list可以通过下面方法构建:

  • '(a . b)
  • (cons 'a 'b)

一个对子(pair)的cdr如果不是一个list,那么这个对子叫做点戳对(dotted pair)。合适list也可以写成点戳形式,但编译器会自动去掉点戳:

(a . (b . (c . ()))) => (a b c)

可以用list过程来构建连对,返回的一定是合适的连对。

Section 2.3. Evaluating Scheme Expressions

常量对象,操诀施行,quote表达式只是scheme提供的三种主要语法形式。scheme包括核心语法形式,以及许多语法扩展。

操诀施行的有两点需要注意,首先对于各部求值的次序可以是任意的。同一个scheme实现在不同的时候都有可能采取不同的次序。其次,procedure和args1…argsn是按同样的方式求值的。

Section 2.4. Variables and Let Expressions

let语法形式(let ((var expr) ...) body1 body2 ...)可以为值赋名:

(let ((x 2))
    (+ x 3))
=> 5

具体的说法let使变量被绑定到这些值之上。let定义的变量。在语法上,绑定通常使用方括号来表示:

(let ([list 1 '( a b c)] [list2 '(d e f)]))
  (cons (cons (car list1)
              (car list2))
        ...))

但实际上,方括号和圆括号没有本质上的区别。

let语法形式可以嵌套:

(let ([a 4] [b -3]))
  (let ([a-squared (* a a)]
        [b-squared (* b b)])
    (+ a-squared b-squared)))

嵌套的时候,内层的let中的变量会遮蔽外层let中的变量:

> (let ([x 1])
    (let ([x (+ x 1)])
      (+ x x)))
4

Section 2.5. Lambda Expressions

lambda表达式的形式是:(lambda (var ...) body1 body2 ...)。可以把lambda表达式施用到参数上:((lambda (x) (+ x x)) (* 3 4 ))

lambda在scheme里面和数字啊,字符一样,都是对象而已,第一级别的数据类型。

不在lambda的定义中的出现的变量是可以在lambda中使用的,如下所示:

(let ([x 'a])
  (let ([f (lambda (y) (list x y))])
    (f 'b)))

上面的x不在lambda f中定义,所以术语上叫做x occurs free in lambda f。在调用lambda f的时候,x必须由外部定义好。

貌似没有办法在调用的是在绑定x的值:

 (let ([x 'a])
    (f 'b))

在chez中的错误:

Exception: variable x is not bound
Type (debug) to enter the debugger.

这说明绑定在lambda定义的时候就确认好了。或者之后只能在全局范围内查找。

这应该是scheme区别于早期的lisp的一个特性吧,lexical scoping。lisp会使用当前环境中可以获取的x。

实际上,let这种语法形式,只是lambda的一种变体,(let ([x 'a]) (cons x x))等价于((lambda (x) (cons x x)) 'a)

实际上(let ((var expr) ...) body1 body2 ...)是一个语法扩展,其展开形式是((lambda (var ...) body1 body2 ...) expr ...)

lambda的形参(var ...)可以是下面几种类型:

  • 一个合适连对
  • 一个单个变量,可以接受任意数目的形参,这些形参会构成一个连对,绑定到那个变量中
  • 一个不适连对,上面两者的结合体,指定数目的形参,加上不定数目的形参

Section 2.6. Top-Level Definitions

可以使用define来定义一个顶层的对象:

(define double-any
  (lambda (f x)
     (f x x)))

顶层的对象定义可以被lambda绑定中的定义所遮蔽。

list竟然是这样定义的:(define list (lambda x x))

scheme提供有两个快捷方式cadr和cddr,顾名思义,应该能判断出它们的用途。

任何下面的形式:

(define var0 
  (lambda (var1 ... varn)
    e1 e2 ...))

可以缩写成

(define (var0 var1 ... varn)
  e1 e2 ...)

下面的形式:

(define var0
  (lambda varr
    e1 e2 ...))

可以被简写成:

(define (var0 . varr) 
  e1 e2 ...)

list的定义可以简写成(define (list . x) x)

这种简化的描述在lisp里面被称为defun语法格式。

Exercise 2.6.2

> (define compose
    (lambda (p1 p2)
      (lambda (x)
        (p1 (p2 x)))))
> (define cadr0
    (compose car cdr))
> (cadr0 '(1 2 3))

Scheme also provides caar, cdar, caaar, caadr, and so on, with any combination of up to four a’s (representing car) and d’s (representing cdr) between the c and the r (see Section 6.3)

Section 2.7. Conditional Expressions

if是一个语法形式,而不是一个过程。or是一个与if相似的语法形式。

所有scheme对象都可以进行布尔测试,只有当其值为#f的时候才返回假值,其他时候都为真值。

and也是一个语法格式,可以用and来定义reciprocal:

(define reciprocal
  (lambda (n)
    (and (not (= n 0))
    (/ 1 n))))

(reciprocal 0)会返回#f。

=, <, >, <=, =>这些过程叫做判定诀,返回的结果要么真要么假。其他判定诀会议?结尾,比如null?,null?会在连对为空的时候返回假值,其他时候返回真值。

lisp中的cdr在连对为空的时候返回空连对。

其他判定诀包括: eqv?, pair?, symbol?, number?, string?等等。

assertion-violation可以用来报告异常。

也可以用cond来替代if。cond也是一个语法形式,其格式如下:(cond (test expr) ... (else expr))。最后的else子句是可以省略的。

atom?也是一个判定诀。如果对象不是连对,则返回#f;如果对象是连对,但是为空,也返回#f;其他情况下返回#t。也就是说atom?其实是not pair?。

length返回一个连对的长队。

Section 2.8. Simple Recursion

递归是一个比loop更强大的概念,具有更强的表达能力。通常递归需要两个东西,一个是基础测试,另一个是递归步进。递归的过程可以看成是步进到基础测试的过程。

下面是一个例子:

(define length
  (lambda (ls)
    (if (null? ls)
      0
      (+ (length (cdr ls)) 1))))

通过(trace name)可以开启对名字为name的执行诀的跟踪。

对于mapping类型的递归,scheme提供有map函数来帮助简化实现:

(define abs-all
 (lambda (ls)
  (map abs ls)))

map支持对多个连对同时运行指定操作,但这些连对必须等长。例子:(map cons '(a b c) '(1 2 3))

这一章的很多练习还是不错的,有空要回头看下。

Section 2.9. Assignment

可以用set!来重新绑定define定义的值。许多程序语言要求使用赋值来初始化本地变量,并用来区分声明和变量绑定。在Scheme中,所有本地变量都需要在绑定的时候提供一个值。

可以用set-car!和set-cdr!来设置一个对子的car和cdr。

本章有很多练习,暂且跳过。

(未完待续)

Categories