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

B站搬运：

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

# Coursera编程语言课程 第6节总结

## 目录

• 不使用数据类型的数据类型编程
• 改变我们对算术表达式数据类型的评估方式
• 通过Racket列表的递归数据类型
• 通过Racket的struct实现递归数据类型
• 为什么struct方法更好
• 实现一般的编程语言
• 在另一种语言中实现一种编程语言
• 关于合法AST的假设和非假设
• 有变量的语言的解释器需要环境
• 实现闭包
• 可选：更有效地实现闭包
• 通过元语言中的函数定义”宏”

## 不使用数据类型的数据类型编程

datatype int_or_string = I of int | S of string

fun funny_sum xs =
case xs of
[] => 0
| (I i)::xs' => i + funny_sum xs'
| (S s)::xs' => String.size s + funny_sum xs'

(define (funny-sum xs)
(cond [(null? xs) 0]
[(number? (car xs)) (+ (car xs) (funny-sum (cdr xs)))]
[(string? (car xs)) (+ (string-length (car xs)) (funny-sum (cdr xs)))]))

datatype exp = Const of int | Negate of exp | Add of exp * exp | Multiply of exp * exp

## 改变我们对算术表达式数据类型的评估方式

fun eval_exp_old e =
case e of
Const i => i
| Negate e2  => ~ (eval_exp_old e2)
| Add(e1,e2) => (eval_exp_old e1) + (eval_exp_old e2)
| Multiply(e1,e2) => (eval_exp_old e1) * (eval_exp_old e2)

eval_exp_old的类型是exp->int。特别是，返回类型是int，一个ML整数，然后我们可以使用ML的算术运算符进行加法、乘法等。

exception Error of string

fun eval_exp_new e =
let
fun get_int e =
case e of
Const i => i
| _ => raise (Error "expected Const result")
in
case e of
Const _ => e
| Negate e2  =>
Const (~ (get_int (eval_exp_new e2)))
Const ((get_int (eval_exp_new e1)) + (get_int (eval_exp_new e2)))
| Multiply(e1,e2) =>
Const ((get_int (eval_exp_new e1)) * (get_int (eval_exp_new e2)))
end

## 通过Racket列表的递归数据类型

; just helper functions that make lists where first element is a symbol
; Note: More robust could check at run-time the type of thing being put in
(define (Const i) (list 'Const i))
(define (Negate e) (list 'Negate e))
(define (Multiply e1 e2) (list 'Multiply e1 e2))

; just helper functions that test what "kind of exp"
; Note: More robust could raise better errors for non-exp values
(define (Const? x) (eq? (car x) 'Const))
(define (Negate? x) (eq? (car x) 'Negate))
(define (Multiply? x) (eq? (car x) 'Multiply))

; just helper functions that get the pieces for "one kind of exp"
; Note: More robust could check "what kind of exp"
(define (Const-int e) (car (cdr e)))
(define (Negate-e e) (car (cdr e)))
(define (Add-e1 e) (car (cdr e)))
(define (Add-e2 e) (car (cdr (cdr e))))
(define (Multiply-e1 e) (car (cdr e)))
(define (Multiply-e2 e) (car (cdr (cdr e))))

(作为说明，我们以前没有见过'foo这个语法。这是一个Racket符号。就我们的目的而言，符号'foo很像字符串"foo"，你可以使用任何字符序列，但符号和字符串是不同的东西。比较两个符号是否相等是一个快速的操作，比字符串相等要快。你可以用eq?来比较符号，而你不应该将eq?用于字符串。我们可以用字符串来做这个例子，用equal?而不是eq?)。

(define (eval-exp e)
(cond [(Const? e) e] ; note returning an exp, not a number
[(Negate? e) (Const (- (Const-int (eval-exp (Negate-e e)))))]
(Const (+ v1 v2)))]
[(Multiply? e) (let ([v1 (Const-int (eval-exp (Multiply-e1 e)))]
[v2 (Const-int (eval-exp (Multiply-e2 e)))])
(Const (* v1 v2)))]
[#t (error "eval-exp expected an exp")]))

(define test-exp (Multiply (Negate (Add (Const 2) (Const 2))) (Const 7)))
(define test-ans (eval-exp test-exp))

## 通过Racket的struct定义递归数据类型

(struct foo (bar baz quux) #: transparent) 

• foo是一个接收三个参数并返回一个值的函数，该值是一个具有容纳第一个参数的bar字段、容纳第二个参数的baz字段和容纳第三个参数的quux字段的foo
• foo?是一个接受一个参数的函数，对于通过调用foo创建的值返回#t，对于其他的值返回#f
• foo-bar是一个函数，它接收foo，并返回bar字段的内容，如果传递的不是foo，则引发错误。
• foo-baz是一个函数，它接收foo并返回baz字段的内容，如果传递的不是foo，则引发错误。
• foo-quux是一个函数，它接收foo并返回quux字段的内容，如果传递的不是foo，则引发错误。

(struct const (int) #:transparent)
(struct negate (e) #:transparent)
(struct multiply (e1 e2) #:transparent)

(define (eval-exp e)
(cond [(const? e) e] ; note returning an exp, not a number
[(negate? e) (const (- (const-int (eval-exp (negate-e e)))))]
(const (+ v1 v2)))]
[(multiply? e) (let ([v1 (const-int (eval-exp (multiply-e1 e)))]
[v2 (const-int (eval-exp (multiply-e2 e)))])
(const (* v1 v2)))]
[#t (error "eval-exp expected an exp")]))

(define test-exp (multiply (negate (add (const 2) (const 2))) (const 7)))
(define test-ans (eval-exp test-exp))

## 为什么struct方法更好

(struct add (e1 e2) #: transparent)

## 在另一种语言中实现一种编程语言

(negate (add (const 2) (const 2))) 

## 关于合法AST的假设和非假设

(struct const (int) #:transparent) ; int should hold a number
(struct negate (e1) #:transparent) ; e1 should hold an expression
(struct add (e1 e2) #:transparent) ; e1, e2 should hold expressions
(struct multiply (e1 e2) #:transparent) ; e1, e2 should hold expressions
(struct bool (b) #:transparent) ; b should hold #t or #f
(struct if-then-else (e1 e2 e3) #:transparent) ; e1, e2, e3 should hold expressions
(struct eq-num (e1 e2) #:transparent) ; e1, e2 should hold expressions

• 一个整数，如(const 17)
• 一个布尔值，如(bool true)
• 不存在，因为当我们试图评估程序时，我们会得到一个”运行时类型错误”，试图把布尔值当作数字，反之亦然

; eval-exp-wrong
(let ([i1 (const-int (eval-exp-wrong (add-e1 e)))]
(const (+ i1 i2)))]
; eval-exp
(if (and (const? v1) (const? v2))
(const (+ (const-int v1) (const-int v2)))
(error "add applied to non-number")))]

• constint字段应该保存一个Racket数字。
• boolb字段应该保存一个Racket布尔值。
• 所有其他表达式的字段应该持有其他合法的AST。(是的，这个定义是递归的）。

## 有变量的语言的解释器需要环境

• 为了评估一个变量表达式，它在环境中查找该变量的名称（即字符串）。
• 为了评估大多数子表达式，例如加法运算的子表达式，解释器向递归调用传递评估外部表达式所传递的相同环境。
• 为了评估像let-expression的主体这样的东西，解释器会向递归调用传递一个稍微不同的环境，比如传递给它的环境中多了一个绑定（即字符串和值的pair）。

## 实现闭包

• 我们使用当前的环境来评估e1。结果应该是一个闭包（否则就是一个运行时错误）。
• 我们使用当前的环境来评估e2。其结果将是闭包的参数。
• 我们使用闭包的环境部分来评估闭包的代码部分的主体，并将代码部分的参数扩展到调用地的参数。

## 通过元语言中的函数来实现”宏”

(define (double e) ; takes language-implemented syntax and produces language-implemented syntax
(multiply e (const 2)))

(define (list-product es)
(if (null? es)
(const 1)
(multiply (car es) (list-product (cdr es)))))