COMP302: Programming Languages and Paradigms
Prof. (Sec 01) Francisco Ferreira (Sec 02)
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Week 4-1, Fall 2017
Higher-order functions are super cool!
COMP302: Programming Languages and Paradigms 2 / 13
Higher-order functions are super cool!
Question: Do you know what the functions in the picture mean?
COMP302: Programming Languages and Paradigms 2 / 13
Functional Tidbit: Church and the Lambda-Calculus
• Logician and Mathematician
• June 14, 1903 – August 11, 1995
• Most known for the Lambda-Calculus:
– a simple language consisting of variables, functions (written as λx.t) and function application
– we can define all computable functions in the Lambda-Calculus!
Church Encoding of Booleans: T = λx.λy.x
F = λx.λy.y
COMP302: Programming Languages and Paradigms 3 / 13
Functional Tidbit: Church and the Lambda-Calculus
Playing detective:
• Logician and Mathematician
• June 14, 1903 – August 11, 1995
• Most known for the Lambda-Calculus:
– a simple language consisting of variables, functions (written as λx.t) and function application
– we can define all computable functions in the Lambda-Calculus!
Church Encoding of Booleans: T = λx.λy.x
F = λx.λy.y
Find out how your instructors are related to !
Hint: Check http://www.genealogy.ams.org/ COMP302: Programming Languages and Paradigms
Slogan – Revisited
Functions are first-class values!
• Pass functions as arguments (Done) • Return them as results (Today)
COMP302: Programming Languages and Paradigms 4 / 13
What does it mean to return a function?
Let’s go back to the beginning … from the 1. week
1 2 3 4 5 6
(* We can also bind variable to functions. *)
let area : float -> float = function r -> pi *. r *. r
(* or more conveniently, we write usually *)
let area (r:float) = pi *. r *. r
• The variable name area is bound to the value
function r -> pi *. r *. r which OCaml prints simply as
• The type of the variable area is float -> float. COMP302: Programming Languages and Paradigms
Switching your viewpoint
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
1 2 3 4 5 6 7
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
let curry_version2 f x y = f (x,y)
let curry_version3 = fun f -> fun x -> fun y -> f (x,y)
. OMP302: Programming Languages and Paradigms
Switching your viewpoint
1 2 3 4 5 6 7
Write a function curry that
• takes as input a function f:(’a * ’b) -> ’c
• returns as a result a function ’a -> ’b -> ’c.
(* curry : ((’a * ’b) -> ’c) -> ’a -> ’b -> ’c *) (* Note : Arrows are right-associative. *) let curry f = (fun x y -> f (x,y))
let curry_version2 f x y = f (x,y)
let curry_version3 = fun f -> fun x -> fun y -> f (x,y)
. OMP302: Programming Languages and Paradigms
Let’s play!
COMP302: Programming Languages and Paradigms 7 / 13
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
COMP302: Programming Languages and Paradigms 8 / 13
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
COMP302: Programming Languages and Paradigms 8 / 13
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
COMP302: Programming Languages and Paradigms 9 / 13
Bonus: Approximating the Derivative
f′(x) = df = lim f(x +ε)−f(x) dxε→0 ε
Implement a function deriv : (float -> float) * float -> float -> float which
• given a function f:float -> float and an epsilon dx:float
• returns a function float -> float describing the derivative of f.
1 let deriv (f, dx) = fun x -> (f (x +. dx) -. f x) /. dx
COMP302: Programming Languages and Paradigms 9 / 13
COMP302: Programming Languages and Paradigms 10 / 13
Partial Evaluation
• A technique for optimizing and specializing programs
• Generate programs from other programs!
• Produce new programs which run faster than the originals while being guaranteed to behave in the same way!
COMP302: Programming Languages and Paradigms 11 / 13
What is the result of evaluation?
1 2 3 4 5 6
(* plus : int -> int -> int *)
letplusSqxy= x*x+y*y
(* plus3 : int -> int *)
let plus3 = (plusSq 3)
COMP302: Programming Languages and Paradigms
What is the result of evaluation?
1 2 3 4 5 6
(* plus : int -> int -> int *)
letplusSqxy= x*x+y*y
(* plus3 : int -> int *)
let plus3 = (plusSq 3)
=⇒ fun y -> 3 * 3 + y * y
COMP302: Programming Languages and Paradigms
What is the result of evaluation?
1 2 3 4 5 6
(* plus : int -> int -> int *)
letplusSqxy= x*x+y*y
(* plus3 : int -> int *)
let plus3 = (plusSq 3)
=⇒ fun y -> 3 * 3 + y * y
OK – OCaml actually just shows you:
val plusSq : int -> int -> int =
COMP302: Programming Languages and Paradigms
What is the result of evaluation?
1 2 3 4 5 6
(* plus : int -> int -> int *)
letplusSqxy= x*x+y*y
(* plus3 : int -> int *)
let plus3 = (plusSq 3)
=⇒ fun y -> 3 * 3 + y * y
What is important to remember:
• We do not evaluate inside function bodies
• We only evaluate the function body when we have all arguments
The operational semantics (i.e. how your program is executed) matters!
COMP302: Programming Languages and Paradigms 12 / 13
Let’s see how to take advantage of it!
COMP302: Programming Languages and Paradigms 13 / 13
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com