[swarthmore cs75] Lab 0 Warmup & Basic OCaml

课程回顾

Swarthmore学院16年开的编译系统课，总共10次大作业。本随笔记录了相关的课堂笔记以及第1次大作业。

什么是编译

编译就是执行Program->Program’转换的过程，如下图所示：

这个过程需要满足两个条件：

The input and output program mean the same thing.
The output is executable in a context we care about.

编译执行过程：

不可变数据结构（persistent data structure）

例1：下图是两个列表在内存中的表示：

xs = [0, 1, 2]
ys = [3, 4, 5]

执行了连接操作，zs在内存中的表示：
“`haskell
zs = xs ++ ys
“`

注意到，xs被复制了一份，但是ys被共享了。最终xs和ys都没有被改变。其中xs被复制是因为，xs中最后一个元素2不能够指向ys的起始地址，因为这样的话xs就被改变了。

例2：假设下面的数据代表下图的二叉搜索树

xs = [a, b, c, d, f, g, h]

在执行插入操作后，内存中的数据结构变为下图：
“`haskell
ys = insert (“e”, xs)
“`

可以看到两个指针xs和ys，其中ys共享了xs中的节点。

编程作业

*OSX安装Ocaml

brew install ocaml opam
opam init
opam install extlib ounit

1.Implement fibonacci as an OCaml function that takes an integer n and returns the nth fibonacci number. Write out the evaluation of (fibonacci 3) in substitution style.

递归计算fibonacci数列

let rec fibonacci (n : int) : int =
  if n <= 2 then 1
  else (fibonacci (n - 1)) + (fibonacci (n - 2));;

The evaluation of (fibonacci 3) in substitution style is ：

=> (if 3 <= 2 then 1 else (fibonacci (3 – 1)) + (fibonacci (3 – 2)))

=> (if false then 1 else (fibonacci (3 – 1)) + (fibonacci (3 – 2)))

=> ((fibonacci (3 – 1)) + (fibonacci (3 – 2)))

=> ((fibonacci 2) + (fibonacci (3 – 2)))

=> …

=> (1 + (fibonacci (3 – 2)))

=> (1 + (fibonacci 1))

=> …

=> (1 + 1)

=> 2

2.Write tests for max and fibonacci using t_int.

测试用例

(* a helper for testing integers *)
let t_int name value expected = name>::
  (fun _ -> assert_equal expected value ~printer:string_of_int);;let max_test = t_int "" (max 4 5) 5;;
let fibonacci_test = t_int "fibonacci_test" (fibonacci 10) 55;;let suite = "suite">:::[max_test; fibonacci_test;];;
run_test_tt_main suite

>:: is a function that creates a TestLabel for a TestCase

val (>: