Transcript Structure & Interpretation of Computer Programs

Structure & Interpretation of
Computer Programs
Xiao Xiao
Ben Charrow
电脑程序的结构和编译
萧潇
陈斌
Who We Are

Xiao Xiao
MIT, Junior, Majoring in Computer Science
[email protected]

Ben Charrow
MIT, Senior, Majoring in Computer Science
[email protected]
What We Want to Cover
The "Scheme" programming language
 Data Abstraction / 数据抽象
 Iterative and recursive processes /
重复和递归进程
 Data structures / 数据结构
 Basic algorithms / 算法

Our Bible / 我们的圣经
 电脑程序的
结构和编译

SICP (sick-pea)

Wizard Book /
巫师书
Scheme

Language features
 Simple
(syntax /语法 & specification /规格)
 Prefix notation /前缀表示法
 Interpreted / 解释器
 Tail-recursive /尾递归
 Weakly typed /弱类型
 Functional
Simplicity

The Scheme specification is 50 pages
long

The Java specification is 684 pages long

Scheme is designed to be as simple and
small as possible
Interpreters / 解释器

Characteristics
 Each
line of code is only examined at runtime
/ 运行时间
 Works on all computer architectures /
计算机体系结构
 Easy to fix problems
 Slower than compiled / 编译器 code
Scheme Keywords
• Keywords: Words that have a 'special
meaning' to the scheme interpreter
• They are what allow you to make
programs
Prefix Notation / 前缀表示法

The function (函数) always comes before its
arguments

(+ 3 4)
(- 5 3)
(* 5 4)
7
2
20
Keyword Example: define

(define x y)
 Makes
the value of x the value of y
 Does not work if y does not have a value

(define x 3)
x
3
Combining Ideas

(define x 12)
(+ x 3)
15
(define x 5)
(define y x)
(* x y)
25
Defining Procedures

Want to define a function that squares
its argument
 Call
the function 'square'
 Call the argument 'arg'

How do we write it in scheme?
Defining Procedures (cont.)

(define (square arg)
(* arg arg))
(square 4)
16
Weakly Typed

Unlike C++ and Java, scheme does not
worry about types!
 Don't
need to declare variables as 'int' or 'char'
 Makes generalizing code easier
 Be careful what you pass!

(define (add arg1 arg2)
(+ arg1 arg2))
(add 'a 'b)
Another Keyword: cond

cond
 Similar
to the 'if' statement in C++ or Java
 If predicate is #t / true, then it evaluates the
statement
 If predicate is #f / false, then it moves on

(define (sign? arg)
(cond ((> 0 arg) ’negative)
((< 0 arg) ’positive)
(else 'zero)))
Recursion (next lecture)

A 'recursive procedure' calls itself

Factorial(n) = n!
 If
n > 0, Factorial(n) = n*Factorial(n-1)
 otherwise factorial(n) = 1
 Factorial is a recursive procedure