这次回顾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、测试文件等,请看使用说明
    • 易于自己学习使用,但讲座的演示会有帮助
  • 免费的、精心编写的文档:

文件结构

  • 在每个文件的开头,都有一行只包含 #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)用于建立列表
    • 名称carcdr是一个历史性的意外

例子

; 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))]))

真实情况?

  • 对于ifcond,测试表达式可以评估为任何东西
    • 如果结果不是#t#f,就不是错误
  • ifcond的语义:
    • “将#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)
  • 对于当前环境中的xx的后续查找会得到表达式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 | cmd2cmd2cmd1“提取”数据
    • 序列反馈电路的输出值

使用流

  • 我们将使用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层面上工作,而不是在字符序列层面上工作。
    • 所以必须知道编程语言是如何标记文本的
  • 举例来说:例如:”宏扩展headcar
    • 不会将(+ 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*
    • 展示一个接受任意数量参数的宏
    • 展示一个递归宏