L2 hof

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Higher-Order Functions: 

Higher-Order Functions

Higher-Order Functions: 

Higher-Order Functions A function that takes a function as argument and/or returns a function as result is called a higher-order function or a functional. ML/Scheme treat functions as first-class (primitive) values. Can be supplied as input to functions. Not allowed in Ada. Can be created through expression evaluation. Not allowed in C++/Java/LISP. Can be stored in data structures.

Nested Functional + Static Scoping: 

Nested Functional + Static Scoping fun f x = let val g = fn y =andgt; 8 * x + y in g end; val h = f 5; h 2; Breaks stack-based storage allocation; Requires heap-based storage allocation and garbage collection (Closures)

ML function definitions: 

ML function definitions fun elem_to_list [] = [] | elem_to_list (h::t) = [h] :: (elem_to_list t) elem_to_list ['a'] = [['a']] fun inc_each_elem [] = [] | inc_each_elem (h::t)= (h+1) :: (inc_each_elem t) inc_each_elem [1,2,3] = [2,3,4]

Abstracting Patterns of Recursion: 

Abstracting Patterns of Recursion fun map f [] = [] | map f (h::t) = (f h)::(map f t) fun elem_to_list x = map (fn x =andgt; [x]) x val inc_each_elem = map (fn x =andgt; x+1)

Functionals : Reusable modules: 

Functionals : Reusable modules Libraries usually contain functionals that can be customized. sort order list Can be used for: descending_order_sort ascending_order_sort sort_on_length sort_lexicographically sort_on_name sort_on_salary ...

Orthogonality: 

Orthogonality Instead of defining related but separate functions such as remove-if remove-if-not process_till_p process_till_not_p define one generalized functional complement. Refer to: CommonLISP vs Scheme

Currying: 

Currying fun plus (x, y) = x + y fun add x y = x + y plus (5,3) = 8 add 5 3 = 8 add 5 = (fn x =andgt; 5+x) Curried functions are higher-order functions that consume their arguments lazily. All ML functions are curried !

Significance of Curried Functions: 

Significance of Curried Functions Supports partial evaluation. Useful for customizing (instantiating) general purpose higher-order functions (generics). Succinct definitions. Denotational (Semantics) Specifications. One-argument functions sufficient. All ML functions are unary.

Slide10: 

fun curry f = fn x =andgt; (fn y =andgt; f(x,y)) fun uncurry f = fn (x,y) =andgt; (f x y) curry (uncurry f) = f uncurry (curry f) = f (Higher-order functions)

Classification of functions: 

Classification of functions Primitive + , * , - , etc. Higher-order Hierarchical (sort order list),(filter pred list) Self-applicable map , id (E.g., (map (map f)) ) fun double f = f o f; composition

From Spec. to Impl.: 

From Spec. to Impl. Spec: (sqrt x) andgt;= 0 /\ (sqrt x)^2 = x Computable Spec: (sqrt x) andgt;= 0 /\ abs((sqrt x)^2 - x) andlt; eps Improving Approximations (Newton’s method): y(n+1) = (y(n) + [x / y(n)]) / 2

Slide13: 

fun improve x y = ( y + x / y) / 2.0 ; val eps = 1.0e~5; fun satis x y = abs( y*y - x) andlt; eps ; fun until p f y = if p y then y else until p f (f y) ; fun sqrt x = until (satis x) (improve x) 1.0;

ML : Meta Language: 

ML : Meta Language Initial Domains of Application Formal Specification of Languages Theorem Proving Theorems are values (terms) of an ADT. Theorems can only be constructed using the functions supported by the ADT ('no spoofing'). ML is a mathematically clean modern programming language for the construction of readable and reliable programs. Executable Specification.

Slide15: 

Symbolic Values Recursive Definitions Higher-Order Functions Strongly Typed Static Type Inference Polymorphic Type System Automatic Storage Management Pattern Matching ADTs; Modules and Functors Functional + Imperative features

Slide16: 

fun len [] = 0 | len (x::xs) = 1 + len xs (define (len xs) (if (null? xs) 0 (+ 1 (len (cdr xs))) ) )

authorStream Live Help