Scheme编程：输出、解释器、抽象对象与快速傅里叶变换

### Scheme编程：输出、解释器与抽象对象的深度探索 #### 1. 输出相关操作 在Scheme编程中，输出操作是常见需求。最初，数字打印借助`number->string`，但对于精确整数和有理数，可直接打印以提高效率。 ##### 1.1 输出函数的基础设定 `write`和`display`函数分别以不同方式输出内容，`write`调用`wr`时`d?`设为`#f`，`display`调用`wr`时`d?`设为`#t`。代码如下： ```scheme (set! write (lambda (x . rest) (if (null? rest) (wr x #f (current-output-port)) (wr x #f (car rest))))) (set! display (lambda (x . rest) (if (null? rest) (wr x #t (current-output-port)) (wr x #t (car rest))))) ``` ##### 1.2 优化数字输出 为了优化输出，可修改代码直接打印精确整数和有理数，而对不精确和复数继续使用`number->string`。 ##### 1.3 实现对象转字符串 将`wr`及其辅助函数的输出导向内部缓冲区，实现`object->string`过程，该过程返回包含输入对象打印表示的字符串。例如： ```scheme (object->string '(a b c)) ; 输出 "(a b c)" (object->string "hello") ; 输出 "\"hello\"" ``` #### 2. 格式化输出 格式化输出能简化包含Scheme对象打印表示的字符串输出。例如，原本需要多次调用输出例程的操作，可通过`fprintf`简化。 ##### 2.1 `fprintf`和`printf`的使用 `fprintf`期望一个端口参数、一个控制字符串和不定数量的额外参数，这些参数按控制字符串的指定插入输出。`printf`与`fprintf`类似，但不期望端口参数，输出发送到当前输出端口。例如： ```scheme (fprintf p "~s ~a~%" (tree-count node) (tree-word node)) (printf "The string ~s displays as ~~.~%" "~") ; 输出 "The string \"~\" displays as ~." ``` ##### 2.2 格式化指令 - `~s`：通过`write`将控制字符串后的第一个未使用参数打印到输出。 - `~a`：通过`display`将第一个未使用参数打印到输出。 - `~%`：打印换行符。 - `~~`：插入波浪号。 ##### 2.3 格式化输出的实现 ```scheme (let () (define dofmt (lambda (p cntl args) (let ((nmax (- (string-length cntl) 1))) (let loop ((n 0) (a args)) (if (<= n nmax) (let ((c (string-ref cntl n))) (if (and (char=? c #\~) (< n nmax)) (case (string-ref cntl (+ n 1)) ((#\a #\A) (display (car a) p) (loop (+ n 2) (cdr a))) ((#\s #\S) (write (car a) p) (loop (+ n 2) (cdr a))) ((#\%) (newline p) (loop (+ n 2) a)) ((#\~) (write-char #\~ p) (loop (+ n 2) a)) (else (write-char c p) (loop (+ n 1) a))) (begin (write-char c p) (loop (+ n 1) a))))))))) (set! printf (lambda (control . args) (dofmt (current-output-port) control args))) (set! fprintf (lambda (p control . args) (dofmt p control args)))) ``` ##### 2.4 扩展格式化指令 可通过`number->string`的可选基数参数，为`printf`和`fprintf`添加新的格式化指令： - `~b`或`~B`：以二进制打印下一个未使用的数字参数。 - `~o`或`~O`：以八进制打印下一个未使用的数字参数。 - `~x`或`~X`：以十六进制打印下一个未使用的数字参数。 例如： ```scheme (printf "#x~x #o~o #b~b~%" 16 8 2) ; 输出 "#x10 #o10 #b10" ``` 还可添加“间接”格式化指令`~@`，将下一个未使用的字符串参数视为拼接到当前格式字符串中。 #### 3. 元循环解释器 元循环解释器是用Scheme编写的Scheme解释器，它展示了Scheme核心结构的简洁性，也说明了解释技术可应用于其他语言。 ##### 3.1 解释器的简单性原因 - 尾调用由宿主实现正确处理，解释器本身只需尾递归。 - 解释代码中的一等过程由解释器中的一等过程实现，由宿主实现支持。 - 由`call/cc`创建的一等延续由宿主实现提供。 - 原始过程和存储管理等服务由宿主实现提供。 ##### 3.2 解释器的实现 解释器将词法绑定存储在环境中，环境是一个关联列表。评估`lambda`表达式会在持有环境和`lambda`体的变量作用域内创建一个过程。后续应用该过程会将新绑定与保存的环境结合。 ```scheme (define interpret #f) (let () (define primitive-environment `((apply . ,apply) (assq . ,assq) (call/cc . ,call/cc) (car . ,car) (cadr . ,cadr) (caddr . ,caddr) (cadddr . ,cadddr) (cddr . ,cddr) (cdr . ,cdr) (cons . ,cons) (eq? . ,eq?) (list . ,list) (map . ,map) (memv . ,memv) (null? . ,null?) (pair? . ,pair?) (read . ,read) (set-car! . ,set-car!) (set-cdr! . ,set-cdr!) (symbol? . ,symbol?))) (define new-env (lambda (formals actuals env) (cond ((null? f ```