'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2008Lecture 6— Nested pattern-matching; course motivationDan Grossman CSE341 Spring 2008, Lecture 6 1'&$%PatternsWhat we know:• case-expresssions 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 general — patterns are much richer than wehave let on.Dan Grossman CSE341 Spring 2008, Lecture 6 2'&$%Deep patternsThe full definition of pattern-matching is recursive, processing thematched-on value and the pattern together.A pattern can be:• A variable (matches everything, introduces a binding)• _ (matches everything, no binding)• A constructor C (matches value C, if C carries no data)• 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 Spring 2008, Lecture 6 3'&$%Can you handle the truth?It’s really:• case e of p1 => e1 | ... | pn => en• val p = e• fun f p1 = e1 | f p2 = e2 ... | f pn = enInexhaustive matches may raise exceptions and are bad style.Example: could write pattern Add pr or Add (e1,e2)Again: The definition of pattern-matching is recursive ove r thevalue-being-matched and the pattern._ and binding a variable are just base cases.Dan Grossman CSE341 Spring 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)• (We discussed this on Wednesday too.)See lec6.sml for a few examples where nested patterns are quite nice.Dan Grossman CSE341 Spring 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 Spring 2008, Lecture 6 6'&$%A couple questions...What’s the best car?What are the best kind of shoes?Dan Grossman CSE341 Spring 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, recursive 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 Spring 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 semantics.And there is a place in universities for learning deep truths andbeautiful insights as an end in itself. (Like watching Hamlet.)Dan Grossman CSE341 Spring 2008, Lecture 6 9'&$%Aren’t languages somebody else’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 Spring 2008, Lecture 6 10'&$%Functional programmingOkay, so why ML and Scheme where:• 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 Spring 2008, Lecture 6 11'&$%Ahead of their time• Garbage collection (Java didn’t exist in 1995, SML & Scheme did)• Generics (List<T> in Java, C#), much more like SML than C++• XML for universal data representation (like Scheme / 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. “assim ilation”Dan Grossman CSE341 Spring 2008, Lecture 6 12'&$%Recent Surge• F#• C# 3.0• Multicore computing (no mutation = easier to parallelize)• MapReduce / Hadoop (first published in 2004)• Small companies (Jane Street, Galois, many others)– And not so small (Ericsson’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 Spring 2008, Lecture 6 13'&$%SummaryThere is no such thing as a “best programming language”. (There aregood general design principles we will study.)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 Spring 2008, Lecture 6
View Full Document
Unlocking...