New version page

UW CSE 341 - Function-Closure Idioms

Documents in this Course
Macros

Macros

6 pages

Macros

Macros

6 pages

Macros

Macros

3 pages

Mutation

Mutation

10 pages

Macros

Macros

17 pages

Racket

Racket

25 pages

Scheme

Scheme

9 pages

Macros

Macros

6 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-19-20 out of 20 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

CSE341: Programming Languages Lecture 9 Function-Closure Idioms Dan Grossman Fall 2011More idioms • We know the rule for lexical scope and function closures – Now what is it good for A partial but wide-ranging list: • Pass functions with private data to iterators: Done • Combine functions (e.g., composition) • Currying (multi-arg functions and partial application) • Callbacks (e.g., in reactive programming) • Implementing an ADT with a record of functions Fall 2011 2 CSE341: Programming LanguagesCombine functions Canonical example is function composition: • Creates a closure that “remembers” what g and h are bound to • Type ('b -> 'c) * ('a -> 'b) -> ('a -> 'c) but the REPL prints something equivalent • ML standard library provides this as infix operator o • Example (third version best): Fall 2011 3 CSE341: Programming Languages fun compose (g,h) = fn x => g (h x) fun sqrt_of_abs i = Math.sqrt(Real.fromInt(abs i)) fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i val sqrt_of_abs = Math.sqrt o Real.fromInt o absLeft-to-right or right-to-left As in math, function composition is “right to left” – “take absolute value, convert to real, and take square root” – “square root of the conversion to real of absolute value” “Pipelines” of functions are common in functional programming and many programmers prefer left-to-right – Can define our own infix operator – This one is very popular (and predefined) in F# Fall 2011 4 CSE341: Programming Languages val sqrt_of_abs = Math.sqrt o Real.fromInt o abs infix |> fun x |> f = f x fun sqrt_of_abs i = i |> abs |> Real.fromInt |> Math.sqrtAnother example • “Backup function” • As is often the case with higher-order functions, the types hint at what the function does ('a -> 'b option) * ('a -> 'b) -> 'a -> 'b • More examples later to “curry” and “uncurry” functions Fall 2011 5 CSE341: Programming Languages fun backup1 (f,g) = fn x => case f x of NONE => g x | SOME y => yCurrying and Partial Application • Recall every ML function takes exactly one argument • Previously encoded n arguments via one n-tuple • Another way: Take one argument and return a function that takes another argument and… – Called “currying” after famous logician Haskell Curry • Example, with full and partial application: – Notice relies on lexical scope Fall 2011 6 CSE341: Programming Languages val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x val true_ans = ((sorted3 7) 9) 11 val is_non_negative = (sorted3 0) 0Syntactic sugar Currying is much prettier than we have indicated so far – Can write e1 e2 e3 e4 in place of ((e1 e2) e3) e4 – Can write fun f x y z = e in place of fun f x = fn y => fn z => e Result is a little shorter and prettier than the tupled version: Fall 2011 7 CSE341: Programming Languages fun sorted3 x y z = z >= y andalso y >= x val true_ans = sorted3 7 9 11 val is_non_negative = sorted3 0 0 fun sorted3 (x,y,z) = z >= y andalso y >= x val true_ans = sorted3(7,9,11) fun is_non_negative x = sorted3(0,0,x)Return to the fold  In addition to being sufficient multi-argument functions and pretty, currying is useful because partial application is convenient Example: Often use higher-order functions to create other functions Fall 2011 8 CSE341: Programming Languages fun fold f acc xs = case xs of [] => acc | x::xs’ => fold f (f(acc,x)) xs’ fun sum_ok xs = fold (fn (x,y) => x+y) 0 xs val sum_cool = fold (fn (x,y) => x+y) 0The library’s way • So the SML standard library is fond of currying iterators – See types for List.map, List.filter, List.foldl, etc. – So calling them as though arguments are tupled won’t work • Another example is List.exists: Fall 2011 9 CSE341: Programming Languages fun exists predicate xs = case xs of [] => false | x::xs’ => predicate xs orelse exists predicate xs’ val no = exists (fn x => x=7) [4,11,23] val has_seven = exists (fn x => x=7)Another example Currying and partial application can be convenient even without higher-order functions Fall 2011 10 CSE341: Programming Languages fun zip xs ys = case (xs,ys) of ([],[]) => [] | (x::xs’,y::ys’) => (x,y)::(zip xs’ ys’) | _ => raise Empty fun range i j = if i>j then [] else i :: range (i+1) j val countup = range 1 (* partial application *) fun add_number xs = zip (countup (length xs)) xsMore combining functions • What if you want to curry a tupled function or vice-versa? • What if a function’s arguments are in the wrong order for the partial application you want? Naturally, it’s easy to write higher-order wrapper functions – And their types are neat logical formulas Fall 2011 11 CSE341: Programming Languages fun other_curry1 f = fn x => fn y => f y x fun other_curry2 f x y = f y x fun curry f x y = f (x,y) fun uncurry f (x,y) = f x yThe Value Restriction Appears  If you use partial application to create a polymorphic function, it may not work due to the value restriction – Warning about “type vars not generalized” • And won’t let you call the function – This should surprise you; you did nothing wrong  but you still must change your code – See the written lecture summary about how to work around this wart (and ignore the issue until it arises) – The wart is there for good reasons, related to mutation and not breaking the type system – More in the lecture on type inference Fall 2011 12 CSE341: Programming LanguagesEfficiency So which is faster: tupling or currying multiple-arguments? • They are both constant-time operations, so it doesn’t matter in most of your code – “plenty fast” – Don’t program against an implementation until it matters! • For the small (zero?) part where efficiency matters: – It turns out SML NJ compiles tuples more efficiently – But many other functional-language implementations do better with currying (OCaml, F#, Haskell) • So currying is the “normal thing” and programmers read t1 -> t2 -> t3 -> t4 as a 3-argument function Fall 2011 13 CSE341: Programming LanguagesCallbacks A common idiom: Library takes functions to apply later, when an event occurs – examples: – When a key is pressed, mouse moves, data arrives – When the program enters some state (e.g., turns in a game) A library may accept multiple callbacks –


View Full Document
Download Function-Closure Idioms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Function-Closure Idioms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Function-Closure Idioms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?