'&$%CSE 341:Programming LanguagesWinter 2006Lecture 5— Type synonyms, more pattern-matching, accumulatorsCSE341 Winter 2006, Lecture 5 1'&$%Goals• Contrast type synonyms with new types• See pattern-matching for built-in “one of” types (not really aconcept, but important for ML programming) and “each of” types• Investigate why accumulator-style recursion can be more efficientCSE341 Winter 2006, Lecture 5 2'&$%Type synonymsYou c an bind a type name to a type. Example:type intpair = int * int(We c all somet hing else a type variable.)In ML, t his creates a synonym, also known as a transparent typedefinition. Recursion not allowed.So a type name is equivalent to its definition.To contrast, the type a datatype binding introduces is not equivalentto any other type (until possibly a later type binding).CSE341 Winter 2006, Lecture 5 3'&$%Review: datatypes and p attern-matchingEvaluation rules for datatype bindings and case expressions:datatype t = C1 of t1 | C2 of t2 | ... | Cn of tnAdds constructors Ci where Ci v is a value (and Ci has type ti->t).case e of p1 => e1 | p2 => e2 | ... | pn => en• Evaluate e to v• If pi is the first pattern to match v, then result is evaluation of eiin environment extended by the match.• If C is a constructor of type t1 * ... * tn -> t, thenC(x1,...,xn) is a pattern that matches C(v1,...,vn) and thematch extends the environment with x1 to v1 ... xn to vn.• Coming soon: many more pattern forms.CSE341 Winter 2006, Lecture 5 4'&$%Why patterns?Even without more pattern forms, this design has advantages overfunctions for “testing and destructing” (e.g., null, hd, and tl):• easier to check for missing and redundant cases• more conc ise s yntax by combining “test, destruct, and bind”• you can easily define te sting and destructing in terms ofpattern-matchingIn fact, c ase express ions are the preferred way to test variants andextract values from all ML’s “one-of” types, including predefined ones([] and :: just funny syntax).So: Do not use functions hd, tl, null, isSome, valOfTeaser: These functions are use ful for passing as valuesCSE341 Winter 2006, Lecture 5 5'&$%Tuple/record patternsYou c an also use patterns to e xtract fields from tuples and records:pattern {f1=x1, ..., fn=xn} (or (x1,...,xn)) matches{f1=v1, ..., fn=vn} (or (v1,...,vn)).For record-patterns, field-order does not matter.This is better style than #1 and #foo, and it means you do not (ever)need to write function-argument types.Instead of a case with one pattern, better sty le is a pattern directly ina val binding.Next time: “deep” (i.e., nested) patterns.CSE341 Winter 2006, Lecture 5 6'&$%RecursionYou s hould now have the hang of recursion:• It’s no harder than using a loop (whatever that is)• It’s much easier when you have multiple recursive calls (e.g., withfunctions over ropes or trees)But there are idioms you should learn for elegance, efficiency, andunderstandability.Today: using an accumulator.CSE341 Winter 2006, Lecture 5 7'&$%Accumulator lessons• Accumulators can avoid data-structure copying• Accumulators can reduce the depth of recursive calls that are nottail calls• Key idioms:– Non-accumulator: compute recursive results and combine– Accumulator: use re cursive res ult as new accumulator– The base case becomes the initial accumulatorYou w ill use rec ursion in non-functional languages—this lesson stillapplies.Let’s investigate the evaluation of to_list_1 and to_list_2.CSE341 Winter 2006, Lecture 5 8'&$%Tail callsIf the result of f(x) is the result of the enclosing function body, thenf(x) is a tail call.More precisely, a tail call is a call in tail position:• In fun f(x) = e, e is in tail position.• If if e1 then e2 else e3 is in tail position, then e2 and e3 arein tail position (not e1). (Similar for case).• If let b1 ... bn in e end is in tail position, t hen e is in tailposition (not any binding expressions).• Function arguments are not in tail position.• ...CSE341 Winter 2006, Lecture 5 9'&$%So what?Why does this matter?• Implementation takes space proportional to depth of function calls(“call stack” must “remember what to do next”)• But in functional languages, implementation must ensure tail callseliminate the caller’s space• Accumulators are a systematic way to make some functions tailrecursive• “Self” tail-recursive is very loop-like because space does not grow.CSE341 Winter 2006, Lecture 5
View Full Document
Unlocking...