Download Day2-func

April 18, 2018 | Author: Anonymous | Category: , Social Science, Anthropology, Human Evolution
Share Embed


Short Description

Download Download Day2-func...

Description

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

View more...

Comments

Copyright © 2017 HUGEPDF Inc.