The Evolution of Programming Languages Day 2 Lecturer: Xiao Jia
[email protected]
The Evolution of PLs
1
The Functional Paradigm
The Evolution of PLs
2
High Order Functions • zeroth order: only variables and constants • first order: function invocations, but results and parameters are zeroth order • n-th order: results and parameters are (n1)-th order • high order: n >= 2
The Evolution of PLs
3
LISP • f(x, y) (f x y) • a + b (+ a b) • a – b – c (- a b c) • (cons head tail) • (car (cons head tail)) head • (cdr (cons head tail)) tail The Evolution of PLs
4
• It’s straightforward to build languages and systems “on top of” LISP • (LISP is often used in this way)
The Evolution of PLs
5
Lambda • f = λx.x2 (lambda (x) (* x x)) • ((lambda (x) (* x x)) 4) 16
The Evolution of PLs
6
Dynamic Scoping int x = 4; Static Scoping f() { printf(“%d”, x); } main() { int x = 7; Dynamic Scoping f(); } Describe a situation in which dynamic scoping is useful The Evolution of PLs
7
Interpretation Defining car (cond ((eq (car expr) ’car) (car (cadr expr)) ) …
The Evolution of PLs
8
Scheme • corrects some errors of LISP • both simpler and more consistent (define factorial (lambda (n) (if (= n 0) 1 (* n (factorial (- n 1)))))) The Evolution of PLs
9
Factorial with actors (define actorial (alpha (n c) (if (= n 0) (c 1) (actorial (- n 1) (alpha (f) (c (* f n)))))))
The Evolution of PLs
10
Static Scoping (define n 4) (define f (lambda () n)) (define n 7) (f)
LISP: 7 Scheme: 4 The Evolution of PLs
11
Example: Differentiating
The Evolution of PLs
12
Example: Differentiating
(define derive (lambda (lambda (x) (/ (- (f (+ x dx)) (define square (lambda (define Dsq (derive sq
(f dx) (f x)) dx)))) (x) (* x x))) 0.001))
-> (Dsq 3) 6.001 The Evolution of PLs
13
SASL • St. Andrew’s Symbolic Language
The Evolution of PLs
14
Lazy Evaluation nums(n) = n::nums(n+1)
infinite list
second (x::y::xs) = y second(nums(0)) = second(0::nums(1)) = second(0::1::nums(2)) = 1 The Evolution of PLs
15
Lazy Evaluation if x = 0 then 1 else 1/x In C: X && Y if X then Y else false X || Y if X then true else Y if (p != NULL && p->f > 0) … The Evolution of PLs
16
Standard ML (SML) • MetaLanguage
The Evolution of PLs
17
Function Composition - infix o; - fun (f o g) x = g (f x); val o = fn : (’a -> ’b) * (’b -> ’c) -> ’a -> ’c
- val quad = sq o sq; val quad = fn :
real -> real
- quad 3.0; val it = 81.0 :
real
The Evolution of PLs
18
List Generator infix --; fun (m -- n) = if m < n then m :: (m+1 -- n) else []; 1 -- 5 [1,2,3,4,5] : int list The Evolution of PLs
19
Sum & Products fun sum [] = 0 | sum (x::xs) = x + sum xs; fun prod [] = 1 | prod (x::xs) = x * prod xs; sum (1 -- 5); 15 : int prod (1 -- 5); 120 : int The Evolution of PLs
20
Declaration by cases fun fac n = if n = 0 then 1 else n * fac(n1); fun fac 0 = 1 | fac n = n * fac(n-1);
The Evolution of PLs
21