sicp习题试解 (2.16)

; ======================================================================

;

; Structure and Interpretation of Computer Programs

; (trial answer to excercises)

;

; 计算机程序的构造和解释(习题试解)

;

; created: code17 07/14/05

; modified:

; (保持内容完整不变前提下，可以任意转载)

; ======================================================================

;; SICP No.2.16

;; 注意： 对于本题，本人目前尚无完全之解答(代码)，但基本思路如下：

;; 采用原有的思路肯定是行不通的，当(operator partA partB)以后， 其结果总是一个

;; 绝对的区间值，而partA和partB中所含的自由变元(设为x,y,...)的信息则全部丢失。

;; 如果将这个结果与其他操作数(partC等)继续运算，则partC具有的同样的自由变元x,y...

;; 将无法与(operator partA partB)中同一个自由变元同步——因为前者已经成为绝对

;; 区间值的一部分，因而同样的x,y...在不同部分中，已经成为互相独立的变元。因此，

;; 原来的思路是行不通的。

;; 一个可行的思路是这样的：

;; （因我目前尚欠缺scheme语法知识——比如高级抽象数据类型等，仅用现有的pair等结构

;; 实现起来代码过于笨拙，所以暂时没有给出代码）

;; 具体思路是: 当一个op作用于两个part的时候，我们并不是立即求值，而是

;; 1. 将其操作存入抽象数据结构，以后再计算

;; 2. 检查两个part各自存在的自由变元，然后合并成一份

;; 3. 利用最终得出的自由变元列表和抽象数据类型的表达式，对各个变量的范围求导，

;; 从而获得各个区间的极大极小，然后比较这些极大极小，获取最终的范围。

;;

;; 抽象数据类型递归定义：

;; TYPE Part = Exp and (Name List)

;;

;; TYPE Exp = VAR (Name)

;; or CONST (float)

;; or ADD EXP EXP

;; or MIN EXP EXP

;; or MUL EXP EXP

;; or DIV EXP EXP

;;

;; 其中单个自由变量"x"对应的Part为(VAR("x"), ["x"])

;; 单个常数"c"对应的Part为(CONST(c), [])

;; 其他part中的Exp和Name List则由对各种操作的递归定义可得， 比如

;; add-interval part1 part2 =

;; match part1 as (exp1, namelist1)

;; match part2 as (exp2, namelist2)

;; ==> (ADD exp1 exp2, combine namelist1 namelist2)