'&$%CSE 341:Programming LanguagesDan GrossmanWinter 2008Lecture 6— Nested pattern-matching; course motivationDan Grossman CSE341 Winter 2008, Lecture 6 1'&$%PatternsWhat we know:• case-expre sssions do pattern-matching to choose branch• val-bindings and fun-arguments also do pattern-matching– All functions take one argument• Can match datatypes (including lists, options) and records(including tuples)The full story is more generalDan Grossman CSE341 Winter 2008, Lecture 6 2'&$%Deep patternsPatterns are much richer than we have let on. A pattern can be:• A variable (matches everything, introduces a binding)• _ (matches everything, no binding)• A constructor and a pattern (e.g., C p) (matches a value if thevalue “is a C” and p matches the value it carries)• A pair of patterns ((p1,p2)) (matches a pair if p1 matches thefirst component and p2 matches the second component)• A record pattern...• ...Dan Grossman CSE341 Winter 2008, Lecture 6 3'&$%Can you handle the truth?It’s really:• val p = e• fun f p1 = e1 | f p2 = e2 ... | f pn = en• case e of p1 => e1 | ... | pn => enInexhaustive matches may raise exceptions and are bad style.Example: could write Rope pr or Rope (r1,r2)So: The definition of pattern-matching is recursive over thevalue-being-matched and the pattern.Binding a variable is just a base case.Dan Grossman CSE341 Winter 2008, Lecture 6 4'&$%Some function examples• fun f1 () = 34• fun f2 = 34• fun f3 (x,y) = x + y• fun f4 pr = let val (x,y) = pr in x + y endIs there any difference to callers between f3 and f4?In most languages, “argument lists” are syntactically separate,second-class constructs.Can be useful: f3 (if e1 then (3,2) else pr)• (This was my answer to Jill’s question on Wednesday.)See lec6.sml for a few examples where nested patterns are quite nice.Dan Grossman CSE341 Winter 2008, Lecture 6 5'&$%Course MotivationI owe you an answer to why 341 has material worth learning.1. Why learn programming languages that are quite different fromJava, C, C++?2. Why learn the fundamental concepts that appear in all (most?)programming languages?3. Why focus on functional programming (avoiding mutation,embracing recursion, and writing functions that take/return otherfunctions)?Dan Grossman CSE341 Winter 2008, Lecture 6 6'&$%A couple questions...What’s the best car?What are the be st kind of shoe s?Dan Grossman CSE341 Winter 2008, Lecture 6 7'&$%Aren’t all languages the same?Yes: Any input-output behavior you can program in language X youcan program in language Y• Java, ML, and a language with one loop and three infinitely-largeintegers are “equal”• This is called the “Turing tarpit”Yes: Certain fundamentals appear in most languages (variables,abstraction, one-of types, inductive definitions, ...)• Travel to learn more about where you’re from• ML, Scheme, Ruby well-suited for letting these fundamentals shineNo: Most cars have 4 tires, 2 headlights, ...• Mechanics learn general principles and what’s differentDan Grossman CSE341 Winter 2008, Lecture 6 8'&$%Aren’t the semantics my least concern?Admittedly, there are many important considerations:• What libraries are available?• What can get me a summer internship?• What does my boss tell me to do?• What is the de facto industry standard?• What do I already know?Technology leaders affect the answers to these questions.Sound reasoning about programs, interfaces, and compilers requiresknowledge of sem antics.And there is a place in universities for learning deep truths andbeautiful insights as an end in itself.Dan Grossman CSE341 Winter 2008, Lecture 6 9'&$%Aren’t languages somebody el se’s problem?If you design an extensible software system, you’ll end up designing a(small?) programming language!Examples: VBScript, JavaScript, PHP, ASP, QuakeC, Renderman,bash, AppleScript, emacs, Eclipse, AutoCAD, ...Dan Grossman CSE341 Winter 2008, Lecture 6 10'&$%Functional programmingOkay, so w hy ML and Scheme whe re:• Mutation is discouraged• Datatype-based one-of types• Higher-order functions (next week)Because:1. These features are invaluable for correct, elegant, efficientsoftware (great way to think about computation).2. Functional languages have a history of being ahead of their time3. They are well-suited to where computing is going (multicore anddata centers)Much of the c ourse is (1), so let’s give an infomercial for (2) and (3)...Dan Grossman CSE341 Winter 2008, Lecture 6 11'&$%Ahead of their time• Garbage collection (Java didn’t exist in 1995, SML and Schemedid)• Generics (List<T> in Java, C#), much more like SML than C++• XML for universal data representation (like Schem e / Lisp)• Function closures in Python, Ruby, etc .• Ruby’s iterators lifted from CLU (another “useless language”)• ...All features dismissed as, “fine for academics, but will never make it inthe real world”.• Maybe datatypes or currying or multimethods will be next...• “Conquering” vs. “assimilation”Dan Grossman CSE341 Winter 2008, Lecture 6 12'&$%Recent Surge• F#• C# 3.0• Multicore computing (Burton Smith quotation)• MapReduce / Hadoop (first published in 2004)• Small companies (Jane Street, Galois, many others)– And not so small (Ericson’s Erlang)– All consider functional programming a key competitiveadvantage∗ In part for hiring smarter people• Lots of research projects (e.g., Macah compiler at UW)Note: None of these examples use SML or Scheme, but that’s okay:think how much you’ve learned in the last 10 days.Dan Grossman CSE341 Winter 2008, Lecture 6 13'&$%SummaryThere is no such thing as a “best programming language”. (There aregood general design principles we will st udy.)A good language is a relevant, crisp, and clear interface for writingsoftware.Software leaders should know about programming languages.Learning languages has super-linear payoff.• But you have to learn the semantics and idioms, not a cutesyntactic trick for printing “Hello World”.Functional languages have been on the leading edge for decades, butideas get absorbed by the masses slowly.• Perhaps things are starting to change?• Even if not, it will make you a better Java/C programmerDan Grossman CSE341 Winter 2008, Lecture 6
View Full Document
Unlocking...