Programming Languages, UW, Part B - Racket Basic

Part A 深入的介绍了 ML —— 一个优美的 static typed functional language. 接下来的 Part B 我们将会引入一个 dynamic typed functional language，Racket；在很早之前我就听说过这个语言独特的括号语法。

这一节的一个很重要的主题应该是比较 versus。我们将学习编程语言中几个很重要的 comparisons:

• compiler v.s. interpreter.
• ML v.s. Racket.
• static typing (与重要的 static checking 机制) v.s. dynamic typing.

Part B 的内容比较多，于是分为 Part B-1 与 Part B-2 进行记录。第一部分将会介绍 Racket 语言基础与各种 idioms，而第二部分专注于 static 与 dynamic typing 的比较。

  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.

Syntax & Parentheses

Racket 脱胎于 Scheme，而 Scheme 是 LISP 的一个著名的 programming dialect。LISP 语系都采用独特的完全用圆括号的前缀符号表示法，这一优美的语法使得其被称之为“上帝的编程语言”。

Racket 中的语素仅仅有两种：

• atom: 例如 #t, #f, 34, "hi", null 等等。一种特别重要的 atom 被称为 identifier，它可能是：
  • variable: 例如 x 或 something-like-this!.
  • special form: define, lambda, if 等等。(类比关键字)
• A sequence of things in parentheses (t1 t2 ... tn).

在一个括号序列中，第一个 atom 决定了其余元素的含义。

• 第一个 atom 是某种 special form。举例来说，(define ...) means we have a variable definition or a sugared version of function definitions.
• 第一个 atom 不是任何 special form。此时括号序列是一个 function call。

对 Racket 的每一条语句，我们可以轻松的解析 parsing 并建立对应的语法树。sequence 则代表一颗颗子树，子树的根为 sequence 的第一个 atom。可以看出语法树的前序遍历对应的就是 Racket 的程序结构。这样的结构使得 Racket 的语法是 unambiguous 的，不用考虑优先级问题。

In Racket, parentheses change the meaning of your program. You cannot add or remove them because you feel like it. They are NEVER optional or meaningless.

与其他语言不同，Racket 中的括号有举足轻重的地位，不能随便增删。举例来说，(e) means evaluate e and call the resulting function with 0 arguments. 所以 (42) 将会导致 run-time error。

Dynamic Typing

Racket 是一个 dynamic typed language；也就是说，Racket does not use a static type system to reject programs before they run. 在 Racket 中，一切类型错误都是 run-time error。

(define f (lambda () (+ 1 "hello")))

在 Racket 中，定义一个这样的函数不会出现任何错误。只有当调用它时 (f)，Racket 才会弹出 contract violation 的 run-time error。

(list 2 (list 4 5) (list (list 1 2) (list 6)) 19 (list 14 0))

舍弃 static type system 带来的是更加灵活的语法：在 Racket 中，定义拥有不同类型元素的 list 显得非常的 trivial；而这样的定义方式在 ML 中会因为无法 type checked 而被 reject。

非常自然的，we may want to compute something over such lists. Again this is no problem. 举例来说，我们可以定义一个函数来计算该数据结构中所有数之和：

(define (sum xs)
  (cond [(null? xs) 0]
        [(number? (car xs)) (+ (car xs) (sum (cdr xs)))]
        [#t (+ (sum (car xs)) (sum (cdr xs)))]))

Delayed Evaluation & Thunks

A key semantic issue for a language construct is when are its subexpressions evaluated. 在 Racket (与包括 ML 的绝大多数语言) 中，对于一个函数调用 (e1 e2 ... en)，我们先对参数 e2, ... en 进行求值再执行函数体中的内容。见下例：

(define (my-if-bad x y z) (if x y z))

与直觉相反，my-if-bad 并不能完全替换 if：这是因为作为函数的 my-if-bad 与作为 special-form atom 的 if 有着完全不同的 rules for evaluating subexpressions.

• (my-if-bad e1 e2 e3)，作为函数，当被调用时，需要对所有参数 e1,e2,e3 进行求值。
• (if x y z)，作为括号序列，if 的规则是先对 e1 求值，如果结果为 true，则对 e2 求值。反之对 e3 求值。也就是说，与函数不同，我们无需同时对 e2 与 e3 进行求值。

(define (factorial-wrong x)
  (my-if-bad (= x 0)
             1
             (* x (factorial-wrong (- x 1)))))

我们使用 my-if-bad 来替换经典阶乘算法中的 if：这个程序会因为无限递归而无法终止。原因是因为由于 my-if-bad 是函数，无论 x 是否等于 0，程序都会继续对函数体中的 (factorial-wrong (-x 1)) 进行求值。

可以看出问题的关键在于推迟对参数的求值；我们可以利用 function bodies are not evaluated until the function gets called 这一特性来实现一个可行的 my-if：

(define (my-if x y z) (if x (y) (z)))

(define (factorial x)
  (my-if (= x 0)
         (lambda () 1)
         (lambda () (* x (factorial (- x 1)))))

将所有 (if e1 e2 e3) 替换成 (my-if e1 (lambda () e2) (lambda () e3))。这样，使用 my-if 函数定义的阶乘算法不会产生无限递归的错误。

可以发现，由于我们用 lambda 创建无参匿名函数将 e2 和 e3 包了起来，在调用 my-if 时并不会对 e2 和 e3 进行求值。直到执行 my-if 的函数体并对 either y or z 进行调用时，我们才需要对 e2 或 e3 其中之一进行求值。这一逻辑与 if 本质是相同的。

e                            ; e will be evaluated immediately
(define x (lambda () e))     ; wrap e in a thunk
(x)                          ; e won't be evaluated until x is called

利用 function bodies are not evaluated until the function gets called 的特性，将表达式 e 封装在一个无参函数中推迟其求值的做法称为 delayed evaluation。这个无参函数被称为 thunk。

thunk.

• noun. the zero-argument function wrapping e.
• verb. we use "thunk the argument" to mean "use lambda () e instead of e" to delay the evaluation of e.

使用 thunk 进行表达式的延时求值是一个常见且强大的 functional programming idiom。这并不是 Racket 特有的 —— 实际上这一部分完全可以在学习 ML 的时候进行介绍。

Mutable Bindings

Racket 支持使用 assignment statement set! (set-bang) 来 mutate bindings。

注意区分 mutate 与 shadow：若 x 在环境中，使用 (set! x 13) 将 mutate the binding so that x maps to the value 13. Doing so affects all code that has this x in its environment. 这也就是说，在 mutate x 之后，在所有的环境中 (而不仅仅是 mutate 之后的环境)，x 都将与 13 对应。

(define b 3)
(define f (lambda (x) (* 1 (+ x b))))
(define c (+ b 4))
(set! b 5)
(define z (f 4))
(define w c)

在上例中，我们依次对 bindings 进行求值 (就和在 ML 中一样)：

• b bound to 3.
• f bound to (lambda (x) (* 1 (+ x b))): 正如之前强调的，在 f 被调用之前不会执行函数体。
• c: 在环境中寻找 b => b bound to 3 => c bound to 7.
• mutate b: 此时在所有环境中 b bound to 5.
• z: 调用函数 f => 参数 x bound to 4 => 在环境中寻找 b => b bound to 5 => z bound to 9.
• w: 在环境中寻找 c => c bound to 7 => w bound to 7.

在 functional programming 中，使用 mutation 通常是非常 error-prone 的。举例来说，可能函数 f 在定义时想要使用的是 b 之前的值。然而 b 在之后发生了 mutate，这时调用 f 结果会与预期不一致。

General technique in software development. If something might get mutated and you need the old value, make a copy before mutation can occur.

(define f
  (let ([b b])
    (lambda (x) (* 1 (+ x b)))))

This code makes the b in the function body refer to a local b that is initialized to the global b.

Lazy Evaluation

在实际使用 thunk 的过程中，我们常常会遇到重复计算的情况：

(define my-mult x y-thunk
  (cond [(= x 0) 0]
        [(= x 1) (y-thunk)]
        [#t (+ (y-thunk) (my-mult (- x 1) y-thunk))]))

在这个递归实现的乘法函数中，每递归一层都需要调用一次 y-thunk。一种可行的解决方案是，在调用函数时我们使用 let 定义本地变量对调用 y-thunk 的结果进行储存。

(my-mult x (lambda () (+ 3 4)))                  ; ordinary call
(my-mult x (let ([z (+ 3 4)]) (lambda () z)))    ; store the result in z
(my-mult x (lambda () (let ([z (+ 3 4)]) z)))    ; wrong: the same as ordinary call

注意第三种写法是错误的；它本质上与第一种相同，因为在 let 中计算的过程仍然被包含在 thunk 中。

这种优化方式操作性不强。在这里我们介绍一个更普适的优化方案：lazy-evaluation/call-by-need/promises. 惰性求值的基本思路是利用 mutation 来对 thunk 进行记忆化，仅在需要时才对表达式进行求值。

惰性求值 (lazy evaluation) 包含两个操作：delay 与 force：

(define (my-delay f)
  (mcons #f f))

(define (my-force th)
  (if (mcar th)
      (mcdr th)
      (begin (set-mcar! th #t)
             (set-mcdr! th ((mcdr th)))
             (mcdr th))))

• delay: 对于 thunk f，delay 返回一个 pair。这个 pair 被称为 promise。注意，在创建 promise 的过程中 thunk 并没有被调用，所以表达式不会被计算。
  • first field 用来标记我们是否对 thunk f 进行过求值。
  • second field 初始存储 thunk f 本身。
• force: 替换朴素的 (thunk) 操作。查看 promise 的 first field，判断我们是否对 thunk f 进行过求值。
  • 若为假，对 thunk f 进行求值并将 second field mutate 为求值的结果；再将 first field 设为真。
  • 若为真，直接返回 second field 中储存的值。

接下来我们利用惰性求值对上例进行优化：

(define (my-mult x y-promise)
  (cond [(= x 0) 0]
        [(= x 1) (my-force y-promise)]
        [#t (+ (my-force y-promise) (my-mult (- x 1) my-promise))]))

(my-mult e1 (my-delay (lambda () e2)))    ; calling

在一些编程语言例如 Haskell 中，惰性求值被运用到所有的函数调用中：也就是说，对于所有的函数参数，我们要么从不对其进行求值，要么仅仅对其进行一次求值。这样的机制又被称为 call-by-need。而传统的在函数体被执行之前保证对所有的函数参数进行求值的机制被称为 call-by-value。

Streams

A stream is an infinite sequence of values.

We obviously cannot create such a sequence explicitly as it would literally take forever, but with delayed evaluation we can create the code that knows how to produce the infinite sequence.

stream 是以 thunk 的形式表示的，当调用该 thunk 时将返回一个 pair <val, next-thunk>。其中，val 为序列中当前元素的值，而 next-thunk 为接下来的元素序列形成的 stream。

无限序列由 cons 单元的嵌套结构表示，cons 单元的 car 与 cdr 分别为当前值与被延时求值的对象 (promise)。序列的后一个 cons 单元通过求值 cdr 部分产生。这个过程不断重复，从而形成无限序列。

Using Streams

powers-of-two 是 Racket 中的一个 built-in stream，它是一个由 2 的幂次方组成的无限值序列。注意 stream 本质上是一个包含 pair 的 thunk；因此在取值之前需要进行调用。

> (car (power-of-two))
2
> (car (cdr (power-of-two)))
4

自然的，我们想要定义函数 that operates over streams 来获得某些信息。下面的 number-until 函数将会计算满足条件的元素在给定 stream 中的位置。

(define (number-until stream tester)
  (letrec ([f (lambda (stream ans)
                (let ([pr (stream)])
                  (if (tester (car pr))
                      ans
                      (f (cdr pr) (+ ans 1)))))])
    (f stream 1)))

> (number-until powers-of-two (lambda (x) (= x 16)))
4

Defining Streams

按照 stream 的定义，我们尝试定义一个无限长的全 1 序列。

(define ones (lambda () (cons 1 (lambda () (cons 1 ...)))))) ; infinite def. (not realistic)

这是一种朴素的无限定义；但我们能够很容易发现其中隐藏的递归规律：后面重复的部分就是 ones 本身。

(define ones (lambda () (cons 1 ones)))                      ; correct def.

需要注意的是，对 stream 的定义，核心在于利用了延时求值 (delayed evaluation) 的 idiom。使用定义本身来进行定义，这被称作递归定义 (recursive definition)。递归定义的完整性需要借助延时求值来保证。

例如在上述定义中，我们在对 ones 的定义中使用了 ones 本身，但由于 thunk 的存在，主体部分的求值过程被延迟了，这保证了递归定义的完整性。如果不这样做的话 (见下例)：

(define ones (cons 1 ones))                                  ; wrong def.

> ones: undefined. cannot reference an identifier before its definition

由于没有 thunk 来对 ones 定义的主体部分的求值过程进行延迟，程序在定义 ones 的过程将立即对主体部分的递归定义进行求值，但它将会发现 ones 的定义并未完成，于是 undefined 错误将会产生。

接下来我们尝试自己定义一个 powers-of-two:

(define powers-of-two
  (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2))))])
              (lambda () (f 2))))

注意到在 stream 与 stream 操作函数的定义中，我们常常需要一个辅助函数 f。在上例中，辅助函数 f 对于某个参数 x，输出一个 pair <x, thunk>。其中 thunk 包装的是 f 对于参数 2x 计算的结果；那么整个 stream 就可以表示为 (lambda () (f 2))：一个封装 f(2) 的 thunk。

Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info:

Programming Languages, Part B, University of Washington, Lecturer: Professor Dan Grossman.