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)))
)
)