Lecture22
写一个名为power_set的函数, 它将生成包含输入集合所有子集的集合.
例:
> ( power_set '(1 2 3) )
( () (2) (3) (2 3) (1) (1 2) (1 3) (1 2 3)) // 注意: 是组合, 不是排列.
以上结果可以看成是由两部分组成：cons '(() (2) (3) (2 3)) '((1) (1 2) (1 3) (1 2 3))
另 外：
> (power_set '())
(())
定义：
(define (ps set)
( if (null set) '(())
( append ( ps (cdr set ) ) // 1
( map ( lambda ( subset)
( cons (car set) subset ) ) // lambda中的函数用于map 操作时, 对列表中每个元素进行运算．
( ps ( cdr set ) ) ) ) ) ) // 2 本行产生map操作的列表
以上代码中, 1/2两处的set指向同一个集合对象 Scheme中通过变量名来向对象是唯一的方法．
//--------------------------------------------------------
写递归函数的技巧：
A. 最简值中抽出规则：1. 尾元素+ 剩余元素 2. 列出几个头元素的具体生成
B. 给出最简时的值：初值． 采用A中获得的递归规则进行叠加．
C. 写递归函数时往往是从给定的n开始，反向递减．
在Scheme语言中, 没有循环, 一般用递归函数来代替循环．
//--------------------------------------------------------
( define ( ps set )
( if ( null set) '(())
( let ( ( ps_rest ( ps ( cdr set ) ) ) ) // 使得只作一次cdr运算, 运算结果可以在let 范围内各处使用, 从而节省时间.
( append ps_rest
( map ( lambda ( subset)
( cons ( car set) subset ) )
ps_rest ) ) ) ) )
此定义与上定义等价，但运行效率高许多.
//--------------------------------------------------------
let 表达式：
( let ( ( x expv1)
( y expv2)
( z expv3) )
... )
实际上：
( let ( ( x ...)
( y ...) )
( a x y ) )
等价于：
(( lambda ( x y )
( a x y )) ... ...)
let 是换一种不同的方式将一些应用函数表示成一些有待评估的表达式．
//------------------------------------------------------------------------
写一个名为permate 的函数．它能输出列表的全部6种排列．
> (permate '( 1 2 3))
( ( 1 2 3 ) ( 1 3 2 ) // 以1 打头
( 2 1 3 ) ( 2 3 1) // 以2打头
( 3 1 2 ) ( 3 2 1) ) // 以3打头
接收一个长度为n的列表，输出的是一个长度为 n! 的列表．
( define ( permate items)
( if ( null items ) '(())
( apply append
( map ( lambda (elem)
( map ( lambda ( permatation )
( cons elem permatation ) )
( permatation ( remove items elem ) ) ) )
items ) )
//------------------------------------------------
Scheme程序编写技巧：
其程序可看作由一部分一部分拼起来，在写的过程中，可以不按程序运算的逻辑顺序来写．( 可以先写后面的再写前面的, 先写中间的再写两头的等等. )
Scheme的许多内置函数后面都维护着一个数据结构，因此用户只需要调用内置函数，而无需自已再根据应用来分配、调度和管理内存；无需用户自已来维护相应的数据结构。
Scheme的程序运行的执行过程，可以分为三个步骤：输入－评估－打印.
不论用户输入的数据是什么类型，Scheme都会在后台产生一个链表，接收输入的数据后将其填写到链表相应的结点中，并标明数据类型，最后返回这个链表的首地址，为后面的评估过程作准备。
> '(1 2 3)
( 1 2 3 )
> ( cons 1 ( cons 2 ( cons 3 '() ) ) )
( 1 2 3 )
以上两段代码是等价的。
cons作为Scheme的一个符号是依附在一段代码上的，解释器很熟悉，解释器遇到cons后就知道怎么分配一段内存给相关的数据，分配好后，它还要知道在各已分配内存空间中需要放入什么数据。
以上为Scheme的基本工作原理，可以用C++模拟写一个min版的Scheme解释器。
Lecture23
Scheme的内存分配和管理
> ( define seq '(1 2 3) ) // 此定义将名为seq的变量与结点值域分别为1, 2, 3的链表关联起来. seq 为一个全局变量.
> ( car seq ) // car 评估并获取全局变量seq 所指身的链表的首结点的数据域的值.
> ( cons '(1 2 3) '(4 5 6) )
((1 2 3 ) 4 5 6)
在cons运算之前, 系统会生成两个链表,一个链表的结点分别为: 1 2 3. 另一个链表的结点分别为 : 4 5 6. cons运算后, 会生成一个新结点. 结点的值域保存链表 1 2 3 的首地址, 结点的指针域保存链表 4 5 6 的首地址.
> ( cons '(1 2) '(1 2) ) // 1
( ( lambda (x) ( cons x x ) ) '( 1 2 ) ) // 2
由于打印函数对内存管理视若无睹. 打印函数只简单地要求打印列表的car部分和cdr部分. 所以以上两个函数的打印结果是一样的. 但实际上,两个函数的内存分布是不一样的.第二个函数产生的只有三个结点的链表,第二和第三个结点分别保存值1 2. 而首结点的值域和指针域同时指向第二结点.
//--------------------------------------------------------------
> ( map car '( (1 2) (3 4) (5 6 7) ) ) // map 可带任意个参数
(1 3 5)
> ( map + '(1 2) '(10 20) '(100 400) )
(111 422)
> ( map * '(1) '(2) '(3) '(4) '(5) )
(120)
实现:
( define ( unary-map fn seq ) ) // 比较Lecture21中的my_unary_map
( if ( null seq) ()
( cons ( fn (car seq) )
( unary-map fn ( cdr seq ) ) ) ) )
因为:
( define ( bar a b c . d)
( list a b c d ) )
> ( bar 1 2 3 4 5 6 )
( 1 2 3 ( 4 5 6 ))
> ( bar 1 2 3 )
( 1 2 3 ())
也就是说点"." 表示其后无论有多少个参数, 都将被收集起来放到参数列表中.
所以map的定义为:
( define ( map fn first-list other-list)
( if ( null first-list) '()
( cons ( apply fn
( cons ( car first-list )
( unary-map car other-list ) ) )
( apply map
( cons fn
( cons ( cdr first-list )
(