Programming Languages Part B Week 2笔记

这次回顾Part B Week 2的内容，主要介绍了Racket基本语法。

课程主页：

https://www.coursera.org/learn/programming-languages-part-b/home

B站搬运：

https://www.bilibili.com/video/BV1tZ4y1D7

Week 2

Racket简介

Racket

• 下面两节将使用Racket语言（不是ML）和DrRacket编程环境（不是Emacs）:
  • 安装/基本使用说明见课程网站
• 和ML一样，以函数式为重点，具有命令式的特点
  • 匿名函数、闭包、无返回语句，等等
  • 但我们将不使用模式匹配
• 与ML不同，没有静态类型系统：接受更多的程序，但大多数错误在运行时才会发生
• 真正的极简主义语法
• 先进的功能，如宏、模块、quoting/eval、continuations、contracts
  • 只介绍其中的几个

Racket vs. Scheme

• Scheme和Racket是非常相似的语言
  • Racket在2010年”改名”了
  • 请原谅我发言时的任何错误
• Racket做了一些不向后兼容的改变…
  • 空列表是如何写的
  • Cons单元不可变
  • 模块如何工作
  • 还有很多补充
• 结果：一种用于建立真实系统的现代语言
  • 更多内容查看在线文档，特别是”Racket指南”

开始

• DrRacket的”定义窗口”和”交互窗口”与我们使用Emacs和REPL的方式非常相似，但更便于使用：
  • DrRacket一直专注于良好的教学
  • 关于如何使用REPL、测试文件等，请看使用说明
  • 易于自己学习使用，但讲座的演示会有帮助
• 免费的、精心编写的文档：
  • http://racket-lang.org/
  • 特别是Racket指南，http://docs.racket-lang.org/guide/index.html

文件结构

• 在每个文件的开头，都有一行只包含 #lang racket（在这之前可以有注释，但不能有代码）
• 一个文件是一个模块，包含定义（绑定）的集合…

Racket定义、函数、条件表达式

例子

; always make this the first (non-comment, non-blank) line of your file
#lang racket

; not needed here, but a workaround so we could write tests in a second file
; see getting-started-with-Racket instructions for more explanation
(provide (all-defined-out))

; basic definitions
(define x 3)
(define y (+ x 2)) ; function call is (e1 e2 ... en): parens matter!

; basic function
(define cube1 
  (lambda (x)
    (* x (* x x))))

; many functions, such as *, take a variable number of arguments
(define cube2
  (lambda (x)
    (* x x x)))

; syntactic sugar for function definitions
(define (cube3 x)
  (* x x x))

; conditional
(define (pow1 x y)
  (if (= y 0)
      1
      (* x (pow1 x (- y 1)))))

一些好性质

• 许多内置函数（又称程序）可以接受任意数量的args：

  • 是的，*只是一个函数

  • 是的，你可以定义函数：

    (define cube
      (lambda (x)
        (* x x x)))

• 对非匿名的函数定义有更好的风格（只是语法糖）：

  ; syntactic sugar for function definitions
  (define (cube3 x)
    (* x x x))
  
  ; conditional
  (define (pow1 x y)
    (if (= y 0)
        1
        (* x (pow1 x (- y 1)))))

一个老朋友：Currying

• Currying是一个在任何有闭包的语言中都适用的习语

  • 在Racket中不太常见，因为它有真正的多个args

    ; currying
    (define pow2 
      (lambda (x)
        (lambda (y)
          (pow1 x y))))
    
    ; sugar for currying (fairly new to Racket)
    (define ((pow2b x) y) (pow1 x y))
    
    (define three-to-the (pow2 3))
    (define eightyone (three-to-the 4))
    (define sixteen ((pow2 2) 4)) ; need exactly these parens

• 用于定义curried函数的语法糖：(define ((pow x) y) (if ...(调用curried函数时没有糖)

Racket列表

又是一个老朋友了：列表处理

• 空列表：null
• Cons构造函数：cons
• 访问列表的头部：car
• 访问列表的尾部：cdr
• 检查是否为空：null?
• 注意：
  • 与Scheme不同，()对null不起作用，但'()可以
  • (list e1 ... en)用于建立列表
  • 名称car和cdr是一个历史性的意外

例子

; list processing: null, cons, null?, car, cdr
; we won't use pattern-matching in Racket
(define (sum xs)
  (if (null? xs)
      0
      (+ (car xs) (sum (cdr xs)))))

(define (my-append xs ys) ; same as append already provided
  (if (null? xs)
      ys
      (cons (car xs) (my-append (cdr xs) ys))))

(define (my-map f xs) ; same as map already provided
  (if (null? xs)
      null
      (cons (f (car xs)) (my-map f (cdr xs)))))

语法和括号

Racket的语法

• 忽略了一些”钟声和口哨”
  • Racket有一个非常简单的语法
• 一个术语（语言中的任何东西）要么是：
  • 一个原语，例如：#t, #f, 34, "hi", null, 4.0, x, ...
  • 一个特殊的形式，例如，define, lambda, if
    • 宏会让我们定义自己的
  • 一个用圆括号表示的术语序列：(t1 t2 ... tn)
    • 如果t1是一个特殊的形式，那么序列的语义就是特殊的
    • 否则就是一个函数调用
• 例子：(+ 3 (car xs))
• 例子：(lambda (x) (if x "hi" #t))

括号

注意到：

• 可以在任何使用(的地方使用[，但必须与]匹配
  • 很快就会看到[...]是常见样式的地方
  • DrRacket可以让你输入)，并将其替换为]来匹配

为什么这样好？

• 通过对所有内容进行括号化处理，将程序文本转换为代表程序的树状结构（解析）是非常简单和明确的

  • 原子操作是叶子
  • 序列以元素为子节点
  • （没有其他规则）

• 也使缩进变得容易

• 例子：

  (define cube
    (lambda (x)
      (* x x x)))

  

• 不需要讨论”运算符优先级”（例如，x + y * z）

小括号的偏差

• 如果你看一下网页的HTML，它也采取同样的方法：
  • (foo写成<foo>
  • )写成</foo>
• 但由于某些原因，LISP/Scheme/Racket是主观上抨击小括号的目标
  • 奇怪的是，常常是由那些认为HTML没有问题的人所为
  • 你有权对语法发表意见，但一个好的历史学家不会拒绝研究一个他/她不喜欢人们口音的国家

为了娱乐

https://xkcd.com/297/

括号很重要! (调试实践)

圆括号很重要

• 对于Racket，你必须打破自己的一个习惯：
  • 不要因为自己喜欢而添加/删除括号
  • 圆括号不是可有可无的，也不是毫无意义的！！！
  • 在大多数地方，(e)意味着对e调用0个参数。
  • 所以((e))意味着用对e调用0个参数，并用对结果调用0个参数
• 如果没有静态类型化，经常会出现难以诊断的运行时错误

例子

正确：

(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

把1当作一个零参数的函数（运行时错误）：

(define (fact n) (if (= n 0) (1) (* n (fact (- n 1)))))

给予if 5个参数（语法错误）：

(define (fact n) (if = n 0 1 (* n (fact (- n 1)))))

定义3个参数（包括(n)）（语法错误）：

(define fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))

将n视为一个函数，将*传递给它（运行时错误）：

(define (fact n) (if (= n 0) 1 (n * (fact (- n 1)))))

动态类型

动态类型

• 以后的主要话题：静态类型（如ML）与动态类型（如Racket）的对比
• 目前来说：
  • 在你测试你的函数之前，抓不到像(n * x)这样的”小错误”是很令人沮丧的
  • 但可以使用非常灵活的数据结构和代码，而不需要说服类型检查器认为它有意义
• 例子
  • 一个可以包含数字或其他列表的列表
  • 假设列表或数字”all the way down”，对所有的数字进行求和……

例子

(define (sum1 xs)
  (if (null? xs)
      0
      (if (number? (car xs))
          (+ (car xs) (sum1 (cdr xs)))
          (+ (sum1 (car xs)) (sum1 (cdr xs))))))

• 不需要花哨的数据类型绑定和构造函数等
• 无论列表有多深，都可以使用
• 但假设每个元素都是一个列表或一个数字
• 如果遇到其他情况，会出现运行时错误

条件表达式

更好的风格

• 当你可以使用条件表达式时，避免嵌套的if表达式
  • 可以认为一个是另一个的语法糖
• 一般的语法：(cond [e1a e1b] [e2a e2b] ... [eNa eNb])
• 良好的风格：eNa应该是#t

例子

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

一个变体

• 像以前一样，我们可以改变我们的规范，说在非数字上的错误，我们应该直接忽略它们
• 所以这个版本可以适用于任何列表（或者只是一个数字）
  • 仔细比较一下，我们不只是添加了一个分支

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

真实情况？

• 对于if和cond，测试表达式可以评估为任何东西
  • 如果结果不是#t或#f，就不是错误
• if和cond的语义：
  • “将#f以外的任何东西都视为真”
  • （在某些语言中，其他东西是假的，在Racket中不是）
• 这个特性在静态类型语言中是没有意义的
• 有些人认为使用这个特性的风格不好，但它可以很方便地使用

局部绑定

局部绑定

• Racket有4种方法来定义局部变量
  • let
  • let*
  • letrec
  • define
• 多样性是好的：它们有不同的语义
  • 使用对你的需求最方便的一种，这有助于向阅读你的代码的人传达你的意图
    • 如果任何一个都能工作，就用let
  • 可以帮助我们更好地学习范围和环境
• 就像在ML中，这3种let表达式可以出现在任何地方

Let

• 一个let表达式可以绑定任意数量的局部变量

  • 注意所有的括号在哪里？

• 这些表达式都是在let表达式之前的环境中被评估的

  • let主体可以使用所有的局部变量

  • 这不是ML let表达式的工作方式

  • 对于像(let ([x y][y x]) ...)这样的形式很方便：

    (define (silly-double x) 
      (let ([x (+ x 3)] 
            [y (+ x 2)]) 
         (+ x y -5)))

Let *

• 在语法上，let*表达式是多了一个字符的let表达式

• 表达式在前面的绑定产生的环境中被评估

  • 可以重复绑定（后面的是shadow）

  • 这就是ML let-表达式的工作方式

    (define (silly-double x) 
      (let* ([x (+ x 3)] 
             [y (+ x 2)]) 
         (+ x y -5)))

Letrec

• 在语法上，letrec表达式也是一样的

• 表达式是在包括所有绑定的环境中进行评估的

  (define (silly-triple x) 
    (letrec ([y (+ x 2)] 
             [f (lambda(z) (+ z y w x))] 
             [w (+ x 7)]) 
       (f -9)))

  • 相互递归需要使用
  • 但是表达式仍然按顺序被评估：访问未初始化的绑定会产生一个错误
    • 记住函数体在被调用前不会被评估

更多letrec

• Letrec是递归的理想选择（包括相互递归）

  (define (silly-mod2 x) 
    (letrec 
      ([even? (lambda (x) (if (zero? x) #t (odd? (- x 1))))] 
       [odd? (lambda (x) (if (zero? x) #f (even? (- x 1))))]) 
        (if (even? x) 0 1)))

• 除了在函数内部，不要使用后面的绑定

  • 如果x不是#f，这个例子会产生一个错误

    (define (bad-letrec x) 
      (letrec ([y z] 
               [z 13]) 
         (if x y z)))

局部定义

• 在某些位置，比如函数体的开头，你可以放置define。

  • 用于定义局部变量，与letrec的语义相同。

  (define (silly-mod2 x) 
    (define (even? x)(if (zero? x) #t (odd? (- x 1))))         
    (define (odd? x) (if (zero? x) #f (even?(- x 1)))) 
    (if     (even? x) 0 1))

• 局部定义是首选的Racket风格，但教材会避免使用它们，以强调let、let*、letrec的区别。

  • 你可以选择在家庭作业中使用或不使用它们。

顶层绑定

顶层

• 文件中的绑定像本地定义一样工作，即letrec
  • 像ML一样，你可以引用早期的绑定
  • 与ML不同，你也可以引用后来的绑定
    • 但只能在函数体中引用较晚的绑定
      • 因为绑定是按顺序计算的
      • 如果你访问一个未初始化的变量，将会得到一个错误
  • 与ML不同，不能在模块中两次定义同一个变量
    • 这没有意义：环境中不能有这两个变量

REPL

不幸的细节：

• REPL的工作方式略有不同
  • 不完全是let*或letrec
• 在REPL中最好避免递归函数定义或前向引用
  • 实际上是可以的，除非shadow你可能不知道的东西，然后就会出现奇怪的情况
  • 当然，调用递归函数也是可以的

可选：实际情况

• Racket有一个模块系统，与ML有有趣的区别

  • 每个文件都隐含着一个模块
    • 不是真正的”顶层”

  • 一个模块可以shadow它使用的其他模块的绑定

    • 包括Racket标准库

  • 所以我们可以重新定义+或任何其他函数

    • 但风格不佳
    • 只在我们的模块中才使用shadow（否则会弄乱标准库的其他部分）

• (可选说明：Scheme是不同的)

使用set!突变

Set!

• 与ML不同，Racket真的有赋值语句

  • 但只在真正合适的时候使用！

    (set! x e)

• 对于当前环境中的x，x的后续查找会得到表达式e的评估结果

  • 任何使用这个x的代码都会受到影响
  • 就像Java、C、Python中的x = e一样

• 一旦你有了副作用，序列就会很有用：

  (begin e1 e2 … en)

例子

例子在顶层使用set!；突变局部变量是类似的：

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

这里没有多少新东西：

• 闭包的环境是在定义函数时确定的，但主体是在函数被调用时评估的
• 一旦一个表达式产生了一个值，那么这个值是如何产生的就不重要了

顶层

• 突变顶层定义是特别有问题的

  • 如果任何代码都可以对任何东西进行set!，那该怎么办？
  • 我们怎样才能抵御这种情况呢？

• 一般的原则：如果你不需要改变的东西可能会改变，那就给它做一个本地拷贝。例子：

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

• 可以为局部副本使用不同的名字，但不需要

但是等等…

• 简单优雅的语言设计：

  • 像+和*这样的原语只是与函数绑定的预定义变量

  • 但也许这意味着它们是可变的

  • 例子继续：

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

• 如果f使用了其他函数，而这些函数使用了可能会被突变的东西，那么即使这样也是不行的

  • 所有的函数都需要复制它们使用的所有可能突变的东西

没有这么疯狂

• 在Racket中，你不需要像这样编程
  • 每个文件都是一个模块
  • 如果一个模块没有在顶层变量上使用set!，那么Racket就会把它变成常量，并禁止在模块外使用set!
  • 像+, *, cons这样的原语在一个模块中是不会突变的
• 向你展示了复制以防止突变的概念
  • 更简单的防御：不允许突变
  • 可变的顶层绑定是一个值得怀疑的想法

关于cons的真相

关于cons的真相

cons只是生成了一个pair

• 通常被称为cons单元
• 根据惯例和标准库，列表是嵌套的pair，最终以null结束

(define pr (cons 1 (cons #t "hi"))) ; '(1 #t . "hi")
(define lst (cons 1 (cons #t (cons "hi" null))))
(define hi (cdr (cdr pr)))
(define hi-again (car (cdr (cdr lst))))
(define hi-another (caddr lst))
(define no (list? pr))
(define yes (pair? pr))
(define of-course (and (list? lst) (pair? lst)))

向length等函数传递一个不恰当的列表是一个运行时错误。

那么为什么允许不恰当的列表？

• pair是有用的
• 没有静态类型，为什么要区分(e1,e2)和e1::e2？

风格：

• 对于未知大小的集合使用恰当的列表
• 但可以自由地使用cons来建立一个pair。
  • 尽管结构体（如记录）可能更好一些

内置原语：

• list?对恰当的列表返回true，包括空列表
  • 对由cons构成的东西返回true
    • 除空列表外，所有不恰当的和恰当的列表都返回true

用于可变pair的mcons

cons单元是不可变的

如果你想改变cons单元的内容怎么办？

• 在Racket中，你不能这样做（与Scheme相比的重大改变）
• 这很好
  • 列表别名无关紧要
  • 由于在创建cons单元时就已经确定了列表的重要性，所以list?实现起来非常快

Set!不改变列表内容

如下方式不会改变cons单元的内容：

(define x (cons 14 null))
(define y x)
(set! x (cons 42 null))
(define fourteen (car y))

• 像Java的x = new Cons(42,null)，而不是x.car = 42

mcons单元是可变的

由于可变对有时很有用（很快就会用到），Racket也提供了它们：

• mcons
• mcar
• mcdr
• mpair?
• set-mcar!
• set-mcdr!

在cons单元上使用mcar或在mcons单元上使用car会产生运行时错误。

延迟评估和Thunks

延迟评估

对于每一种语言结构，语义都规定了子表达式何时被评估。在ML、Racket、Java、C中：

• 函数参数是eager（call-by-value）
  • 在调用函数之前评估一次

• 条件分支不是eager

  这很重要：调用factorial-bad永远不会终止：

(define (my-if-bad e1 e2 e3)
  (if e1 e2 e3))

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

Thunks延迟

我们知道如何延迟求值：把表达式放在一个函数中！

• 多亏了闭包，以后可以使用所有相同的变量

一个用于延迟求值的零参数函数被称为thunk

• 作为一个动词：thunk表达式

这样做是可行的（但如果这样包装就太傻了）：

(define (my-if-strange-but-works e1 e2 e3)
  (if e1 (e2) (e3)))

(define (factorial-okay x)
  (my-if-strange-but-works (= x 0)
			   (lambda () 1)
			   (lambda () (* x (factorial-okay (- x 1))))))

关键点

• 对一个表达式e进行求值，得到结果。

• 一个函数，当被调用时，对e进行评估并返回结果

  • 用于”thunking”的零参数函数

    (lambda () e)

• 将e求值为某个thunk，然后调用该thunk

  (e)

• 下一步：与延迟评估和/或避免重复或不必要的计算有关的强大的习语

避免不必要的计算

避免昂贵的计算

• 如果不需要昂贵的计算，thunks可以让你跳过这些计算

• 如果你采用真正的分支，那就太好了

  (define (f th)
    (if (…) 0 (… (th) …)))

• 但如果你最终不止一次地使用thunk，那就更糟了

  (define (f th)
    (… (if (…) 0 (… (th) …))
       (if (…) 0 (… (th) …))
       …
       (if (…) 0 (… (th) …))))

• 一般来说，可能不知道结果需要被使用多少次

两全其美

• 假设一些昂贵的计算没有副作用，理想情况下我们会：
  • 在需要之前不计算它
  • 记住答案，以便将来使用时立即完成
  • 被称为惰性评估
• 大多数构造（包括函数参数）以这种方式工作的语言是惰性语言
  • Haskell
• Racket预先定义了对promise的支持，但我们可以自己完成
  • thunks和可变pair已经足够了

Delay和Force

两全其美

• 假设一些昂贵的计算没有副作用，理想情况下我们会：
  • 在需要之前不计算它
  • 记住答案，以便将来使用时立即完成
• 称为惰性评估

delay和force

(define (my-delay th) 
  (mcons #f th)) ;; a one-of "type" we will update /in place/

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

一个ADT由一个可变pair表示：

• #car中的#f意味着cdr是未评估的thunk
  • 实际上是一个单一的类型：thunk或thunk的结果
• 理想情况下隐藏在模块中

使用promises

(define (f th)
  (… (if (…) 0 (… (th) …))
     (if (…) 0 (… (th) …))
     …
     (if (…) 0 (… (th) …))))
     
(f (my-delay (lambda () e)))

从例子中得到的教训

请看代码文件，该例子使用一个非常慢的加法辅助函数做乘法：

• 第二个参数很重要
  • 如果第一个参数为0，则很好
  • 如果第一个参数为1，也ok
  • 否则就很糟糕
• 使用预先计算的第二个参数
  • 所有情况下都是好的
• 如果thunk的第二个参数使用了promise
  • 如果第一个参数为0，则很好
  • 其他情况也ok

使用Stream

流

• 流是有无限个值的序列
  • 所以不能通过生成所有的值来制造一个流
  • 关键思想：使用thunk来延迟创建大部分的序列
  • 这只是一个编程的习语
• 强大的分工概念
  • 流生产者知道如何创建任何数量的值
  • 流的消费者决定要求多少个值
• 你可能（不）熟悉的一些流示例：
  • 用户行为（鼠标点击等）
  • UNIX管道：cmd1 | cmd2让cmd2从cmd1“提取”数据
  • 序列反馈电路的输出值

使用流

• 我们将使用pair和thunks来表示流

• 让一个流成为一个thunk，当被调用时返回一个对：

  '(next-answer . next-thunk) 

• 因此，给定一个流s，客户端可以得到任何数量的元素

  • 第一：(car (s))
  • 第二：(car ((cdr (s)))))
  • 第三：(car ((cdr ((cdr (s))))))
  • (通常将(cdr (s))绑定到一个变量或传递给一个递归函数)

使用流的例子

这个函数返回需要多少个流元素才能找到一个tester不返回#f的元素

• 恰好是用一个尾递归辅助函数编写的

  (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)))

• (stream)生成了pair

  • 所以递归地传递(cdr pr)

定义Stream

Stream

• 在你的程序中编写流的代码是很容易的

  • 我们将使用pair和thunk来实现函数流

• 让流成为thunk，当被调用时返回一个pair：

  '(next-answer . next-thunk) 

• 看到了如何使用它们，现在该如何产生它们……

  • 不可否认的是，这个方法很费脑筋，但它使用了我们知道的东西

制作流

• 一个thunk如何能创造出正确的下一个thunk？递归！

  • 制作一个thunk，产生pair，其中cdr是下一个thunk的数据

  • 递归函数可以返回一个thunk，在thunk被调用之前，递归调用不会发生

(define ones (lambda () (cons 1 ones)))

(define nats
  (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))])
    (lambda () (f 1))))

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

错误

• 这是在定义变量之前就使用了它

  (define ones-really-bad (cons 1 ones-really-bad))

• 这将进入一个无限循环，产生一个无限长的列表

  (define ones-bad (lambda () cons 1 (ones-bad)))
  (define (ones-bad) (cons 1 (ones-bad)))

• 这是stream: thunk，返回pair, cdr是thunk的数据

  (define ones (lambda () (cons 1 ones)))
  (define (ones) (cons 1 ones))

记忆

记忆

• 如果一个函数没有副作用，也不读取易变的内存，那么对于相同的参数就没有必要计算两次。
  • 可以保留先前结果的缓存
  • 如果(1)维护缓存比重新计算更便宜，(2)缓存的结果被重复使用，则带来很大收益。
• 类似于promise，但如果函数需要参数，那么就有多个”先前的结果”
• 对于递归函数，这种记忆化可以带来指数级的程序速度
  • 与动态规划算法技术有关

如何进行记忆化：见示例

• 需要一个（可变）缓存，所有使用该缓存的调用都共享该缓存
  • 所以必须在使用它的函数之外定义
• 参见代码，以斐波那契数为例
  • 因为很短，所以很好地展示了这个想法，但是，正如代码中所示，也有更简单的不太一般的方法来使斐波那契有效
  • 关联列表（成对的列表）是一个简单但次优的缓存数据结构；对我们的例子来说是可以的）

assoc

• 示例使用assoc，这只是一个库函数，你可以在Racket参考手册中查找：
  • (assoc v lst)接收pair的列表，根据is-equal?定位lst中第一个car等于v的元素。如果存在这样的元素，则返回该pair（即lst的一个元素）。否则，结果是#f。
• 如果没有找到，则返回#f，以区别于在cdr中找到一个带有#f的pair。

宏：关键点

其余部分

• 本节：宏的高层次概念
  • 本节作业不需要
  • 需要在下一节中稍加发挥
• 然后：Racket的宏系统和宏的误区
  • 定义一个宏是本节的挑战作业
  • “正确的宏”是Racket与其他宏系统（如C/C++）相比的关键特征
• 这一节之后的部分是可选的
  • 节约时间，不会在此基础上进行。

什么是宏

• 宏的定义描述了如何将一些新的语法转化为源语言中的不同语法。
• 宏是实现语法糖的一种方式
  • “用if e1 then e2 else false替换任何e1 andalso e2形式的语法”
• 宏系统是一种用于定义宏的语言（或大语言的一部分）。
• 宏扩展是为每个宏的使用重写语法的过程
  • 在程序运行（或甚至编译）之前

使用Racket宏

• 如果你在Racket中定义了一个宏m，那么m就变成了一个新的特殊形式：
  • 使用(m ...)根据定义得到扩展
• 示例定义：
  • 将(my-if e1 then e2 else e3)扩展为(if e1 e2 e3)
  • 将(comment-out e1 e2)扩展到e2
  • 将(my-delay e)扩展为(mcons #f (lambda () e))

例子使用

这就像在我们的语言中加入了关键词一样

• 其他关键词只在该宏的使用中才是关键词
• 如果关键词被误用，则语法错误
• 重写（”扩展”）发生在执行之前

(my-if x then y else z) ; (if x y z)
(my-if x then y then z) ; syntax error
(comment-out (car null) #f)
(my-delay (begin (print "hi") (foo 15)))

过度使用

• 宏的名声往往不好，因为它们经常被过度使用，或者在使用函数的时候，会有更好的效果。
• 在有疑问的时候，不要去定义一个宏？
• 但它们可以被很好地使用，可选材料应该有帮助。

可选的内容

• 任何宏系统必须如何处理标记、小括号和范围
• 如何在Racket中定义宏
• 宏定义必须如何仔细处理表达式的评估问题
  • 表达式评估的顺序以及评估的次数
• 宏中的变量绑定的关键问题和hygiene的概念
  • Racket在这方面优于大多数语言

可选：tokenization化、括号化和范围

Tokenization

宏系统的第一个问题。它是如何进行标记化的？

• 宏系统通常在token层面上工作，而不是在字符序列层面上工作。
  • 所以必须知道编程语言是如何标记文本的
• 举例来说：例如：”宏扩展head为car“
  • 不会将(+ headt foo)改写为(+ cart foo)
  • 不会将head-door改写为car-door

括号内的内容

• 宏观系统的第二个问题：结合性是如何工作的？

• C/C++的基本例子：

  #define ADD(x,y) x+y

• 可能不是你想的那样：

  • ADD(1,2/3)*4意味着1 + 2 / 3 * 4，而不是(1 + 2 / 3) * 4

• 所以C语言宏的使用者使用大量的括号：

  #define ADD(x,y) ((x)+(y))

• Racket就没有这个问题了：

  • 宏的使用：

    (macro-name …)

  • 扩展后：

    (something else in same parens)

本地绑定

• 宏系统的第三个问题：变量可以shadow宏吗？

• 假设宏也适用于变量绑定，那么：

  (let  ([head 0] [car 1]) head) ; 0 
  (let* ([head 0] [car 1]) head) ; 0

  将成为

  (let  ([car 0] [car 1]) car) ; error
  (let* ([car 0] [car 1]) car) ; 1

• 这就是为什么C/C++的惯例是全大写的宏，而其他都是非全大写的。

• Racket不是这样工作的——它的范围是”正确的”!

可选：用define-syntar定义宏

Racket宏定义示例

两个简单的宏：

;; a cosmetic macro -- adds then, else
(define-syntax my-if 
  (syntax-rules (then else)
    [(my-if e1 then e2 else e3)
     (if e1 e2 e3)]))

;; a macro to replace an expression with another one
(define-syntax comment-out
  (syntax-rules ()
    [(comment-out ignore instead) instead]))

如果使用的模式匹配，就做相应的扩展

• 在这些例子中，可能的使用形式列表的长度为1
• 语法错误

重新审视delay和force

回顾我们前面对承诺的定义

• 我们是否应该用一个宏来代替，以避免客户的明确thunk？

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

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

(f (my-delay (lambda () e)))

(define (f p) 
  (… (my-force p) …))

一个延迟宏

• 一个宏可以把一个表达式放在一个thunk下面

  • 在没有明确thunk的情况下延迟计算
  • 不能用一个函数来实现这一点

• 现在客户端不应该使用thunk（这将是双重thunk）。

  • Racket的预定义延迟是一个类似的宏

  (define-syntax my-delay
    (syntax-rules ()
      [(my-delay e)
       (mcons #f (lambda () e))]))
  
  (f (my-delay e))

那么force的宏呢？

• 我们也可以用一个宏来定义my-force

  • 好的宏风格是精确地评估一次参数（使用下面的x，而不是对e进行多次评估）

  • 这表明在这里使用宏的风格是很糟糕的

  • 当函数能做你想做的事时，不要使用宏

    (define-syntax my-force
      (syntax-rules ()
        [(my-force e)
         (let ([x e])
           (if (mcar x)
               (mcdr x)
               (begin (set-mcar! x #t)
                      (set-mcdr! x ((mcdr x)))
                      (mcdr x))))]))

可选：变量、宏和hygiene

另一个糟糕的宏

• 任何使其参数double的函数对客户来说都是好的

  (define (dbl x) (+ x x)) 
  (define (dbl x) (* 2 x))

  • 这些都是相互等价的

• 所以翻倍的宏是不好的风格，但有指导意义：

  (define-syntax dbl (syntax-rules() [(dbl x) (+ x x)])) 
  (define-syntax dbl (syntax-rules() [(dbl x) (* 2 x)]))

  • 这些并不是相互等同的。考虑一下：

    (dbl (begin (print "hi") 42))

更多的例子

• 有时一个宏应该重新评估它所传递的参数

  • 如果不是这样，如dbl，那么根据需要使用局部绑定：

    (define-syntax dbl 
      (syntax-rules () 
         [(dbl x) 
          (let ([y x]) (+ y y))]))

• 对于宏来说，没有评估顺序也是一种好的风格

  • 保持从左到右的良好经验法则

  • 不好的例子（用局部绑定来解决）

    (define-syntax take 
      (syntax-rules (from) 
         [(take e1 from e2) 
          (- e2 e1)]))

宏中的局部变量

• 在C/C++中，在宏中定义局部变量是不明智的

  • 当需要使用像__strange_name34这样的名称

• 下面是一个愚蠢的例子来说明原因：

  • 宏：

    (define-syntax dbl 
      (syntax-rules () 
         [(dbl x) (let ([y 1]) 
                     (* 2 x y))]))

  • 使用：

    (let ([y 7]) (dbl y))

  • 朴素的扩展：

    (let ([y 7]) (let ([y 1]) 
                     (* 2 y y)))

  • 但是Racket反而”做对了”，这就是hygiene的一部分

hygiene的另一面

• 这看起来也会做”错误”的事情

  • 宏：

    (define-syntax dbl 
      (syntax-rules () 
         [(dbl x) (* 2 x)]))

  • 使用：

    (let ([* +]) (dbl 42))

  • 朴素的扩展：

    (let ([* +]) (* 2 42))

  • 但是，Racket的hygiene宏又一次得到了正确的结果。

hygiene宏的工作原理

一个hygiene宏系统：

1. 秘密地将宏中的局部变量重新命名为新名称
2. 在定义宏的地方查找宏中使用的变量

大多数宏系统使用的”朴素扩展”都没有遵循这两条规则

• 如果不使用hygiene，宏就会更加脆弱（非模块化）。

在少数情况下，hygiene不是你想要的东西

• Racket对此有一些复杂的支持

可选：更多的宏例子

更多例子

请看以下宏的代码：

• 一个用于执行某个body的固定次数的for循环
  • 显示一个故意重新评估某些表达式而不评估其他表达式的宏
• 允许0、1或2个局部绑定，其括号比let*少
  • 展示一个有多种情况的宏*
• 利用let重新实现let*
  • 展示一个接受任意数量参数的宏
  • 展示一个递归宏