CSE 341, Winter 2008, Lecture 5 SummaryStandard Disclaimer: These comments may prove useful, but certainly are not a complete summary ofall the important stuff we did in class. They may make little sense if you missed class, but hopefully will helpyou organize and process what you have learned.This lecture covers two topics:• It completes our investiation of pattern-matching by giving the full definition of pattern-matching,which allows for nested patterns (patterns inside patterns). It shows several examples where nestedpattern-matching is particularly elegant.• It motivates why one should study programming languages, particularly functional programming lan-guages. Most courses have this discussion in the first lecture, but it can make much more sense afterhaving seen some basic functional programming.So far, we have said all patterns look like C1 or C2(x1,...,xn) or {f1=x1,...,fn=xn} or (x1,...,xn)where C1 and C2 are constructors and the fi are field names. These are all patterns, and we have learnedwhen they match a value and what bindings they introduce when the match is successful. However, it turnsout that where we have b ee n putting variables in our patterns we can also put other patterns, which leadsto an elegant recursive definition of pattern-matching. Here are some parts of the recursive definition:• A variable pattern (x) matches any value v and introduces one binding (from x to v).• A wildcard pattern (_) matches any value v and introduces no bindings.• The pattern C matches the value C, if C is a constructor that carries no data.• The pattern C p where C is a constructor and p is a pattern matches a value of the form C v (noticethe constructors are the same) if p matches v (i.e., the nested pattern matches the carried value).• The pattern (p1,p2) matches a pair of values (v1,v2) if p1 matches v1 and p2 matches v2.• ...This recursive definition extends our previous understanding in two interesting ways. First, for a con-structor C that carries multiple arguments, we do not have to write patterns like C(x1,...,xn) though weoften do. We could also write C x; this would bind x to the tuple that the value C(v1,...,vn) carries. Whatis really going on is that all constructors take 0 or 1 arguments, but the 1 argument can itself be a tuple.So C(x1,...,xn) is really a nested pattern where the (x1,...,xn) part is just a pattern that matches alltuples with n parts.Second, and more importantly, we can use nested patterns instead of nested case expressions when wewant to match only values that have a certain “shape.” For example, the pattern x::(y::z) would matchall lists that have at least 2 elements, whereas the pattern x::[] would match all lists that have exactly oneelement. Both examples use one constructor pattern inside another one.The nested patterns can be for different types. For example, the pattern (_,(_,x),_)::tl would matcha non-empty list where each element was a triple where the second element was a pair. It would bind thelist’s head’s middle element’s second element to x and the list’s tail to tl.We considered several examples where nested patterns lead to elegant code, including “zipping” or “un-zipping” multiple lists, seeing if a list is sorted, and coding a table of outputs by matching against a tupleof inputs. This silly example of the last idiom computes the sign that would result from multiplying twonumbers (without actually doing the multiplication).datatype sign = P | N | Zfun multsign (x1,x2) =let fun sign x = if x=0 then Z else if x>0 then P else Nin1case (sign x1,sign x2) of(Z,_) => Z| (_,Z) => Z| (P,P) => P| (N,N) => P| _ => NendEnding a case-expression with the pattern _, which matches everything, is somewhat controversial style. Thetype-checker certainly won’t complain about an inexhaustive match, which can be bad if you actually didforget some possibly that you are accidentially covering with your “default case.” So more careful coding ofthe example above would replace the last case with two cases with patterns (P,N) and (N,P), but the codeas written above is also okay.Returning to how general pattern-matching is, it turns out that every val-binding and function argumentis really a pattern. So the syntax is actually val p = e and fun f p = e where p is a pattern. In fact, thetextbook and many ML programmers use a form of function-binding where you can have multiple cases byrepeating the function name and using a different pattern:fun f p1 = e1| f p2 = e2...| f pn = enThis is just syntactic sugar for:fun f x =case x ofp1 => e1| p2 => e2...| pn => enYour instructor happens not to be a big fan of the rep eated function-name style, but you are welcome to useit if you are.Turning our attention to course motivation, we can break the question of, “what is this course good for”into 3 parts:1. Why should we learn programming languages other than popular industry ones like Java, C, C++,Perl, etc.?2. Why should we learn fundamental concepts that appear in most programming languages, rather thanjust learning particular languages?3. Why should we focus on languages that encourage (mostly) functional programming (i.e., that discour-age mutation, encourage recursion, and encourage functions that take and return other functions)?A good analogy is with automobiles. There will never be a be st programming language much as therewill never be a best car. Different cars serve different purposes: some go fast, some can go off-road, some aresafer, some have room for a large family, etc. Yet there are remarkable similarities and while drivers or automechanics may have preferences and spe cialties, they learn enough fundamental principles to work with newkinds of cars easily. Still, it can be uncomfortable to switch cars, as anyone who has ever had trouble findingthe windshield wipers in a friend’s car can attest.You should also know that in a very precise sense all programming languages are equally powerful: If youneed to write a program that takes some input X and produces output Y , there is some way to do it Java orML or Perl or a ridiculous language where you only have 3 variables and 1 while loop. This equality is oftenreferred to as the “Turing tarpit” because Alan Turing first advanced the thesis that (roughly speaking)2all languages were equally powerful and “tarpit” because a tarpit is somewhere you get stuck (in this case,making arguments that some language is great because it can do e verything you
View Full Document
Unlocking...