TOPICS FOR THE 541 TEST on Object-Oriented Programming, Scala, Lambda Calculus, and Related Language Design Topics $Date: 2005/11/15 04:13:55 $ This exam covers topics from homeworks 2-4, including lambda calculus, type checking, object-oriented, (and functional) programming in Scala, and a bit of advanced topics in Haskell. REMINDERS The exam will be open book, open notes. (Warning: don't expect to learn the material during the exam, you won't have time! A good idea for studying is to condense your notes to a few pages of ready reference materials.) If you need more space, use the back of a page. Note when you do that on the front. This exam is timed. We will not grade your exam if you try to take more than the time allowed. Therefore, before you begin, please take a moment to look over the entire exam so that you can budget your time. Clarity is important; if your diagrams or programs are sloppy and hard to read, you will lose points. Correct syntax also makes a difference for programming questions. READINGS For lambda calculus see the excerpts from Gunter's book, "Semantics of Programming Languages: Structures and Techniques" that were handed out. For object-oriented programming and Scala, read the Scala documents from the http://scala.epfl.ch/ web site, including the following: Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stephane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. An Overview of the Scala Programming Language. Ecole Polytechnique Fedrale de Lausanne, 1015 Lausanne, Switzerland. Technical Report IC/2004/64, 2004. Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stephane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. The Scala Language Specification Version 1.0. Martin Odersky. Scala by Example. Draft of October 15, 2005. For Haskell, read Thompson's book, "Haskell: The Craft of Functional Programming (second edition)", especially the chapter on Monads (chapter 18). If you have time, see the course web site and also the course syllabus for other readings. (If you read more articles about scala, you can do extra credit problem 16 on homework 4 to summarize it.) TOPICS In the following, I use + to denote relatively more important topics, and - to denote relatively less important topics. Topics marked with ++ are almost certain to be on the exam. All of these are fair game, but if you have limited time, concentrate on the ones that are more important first (and in those, the ones you are most uncertain about). SKILLS - Haskell programming; be able to: - write monadic-style code - give the value of Haskell code that uses syntactic sugars for monads - explain how a purely functional language like Haskell connects to the real world and still preserves referential transparency (using the IO type) + write type inference code for a simple language [HW2: type checker for lambda-calculus.] + Lambda Calculus; be able to: + use the parsing and precedence rules for the lambda calculus + give the type of a term in the simply-typed lambda calculus [HW2: derive and prove types of terms] + formally prove a term has a type in the simply-typed lambda calculus [HW2: derive and prove types of terms] (Fall '04: \c:o.(\a:o.\b:o.a)c ) + formally reduce a term to normal form [HW2: prove K M N =>* M; find normal forms for (S K K) x, B x y z, and (S (B B S) (K K)) x y z.] (Fall '03: (\f.\x.f(f x))(\t.t), Fall '04: (\c.(\a.\b.a)c)b((\f.\x.f x)(\f.f f)(\g. g g)) ) + Scala programming; be able to: + give output of Scala code, especially for code that uses operator sugars (infix, etc.), pattern matching, exceptions, anonymous functions, inheritance, mixins, method overriding, method calls, and "super" [HW4: interpreter problem] + write code that uses functional programming idioms in Scala + use library functions such as map, foldr, and filter [HW4: delete_all_b, approximations] + use for-comprehensions to define functions [HW4: delete_all, library database] + write recursive functions on lists, numbers [HW4: delete_all_c] + write curried functions [HW4: library database] + use streams to help modularize code [HW4: approximations, within, squareRoot] + give output of code that uses XML literals and XPath operators ++ write methods that process XML data [HW4: ListDir, ListImages, Web2RSS] + write that uses and subclasses existing Scala (and Java) code [HW4: tests for numeric code, ListDir, ListImages, Web2RSS] ++ write recursions over algebraic data types (grammars) [HW4: FSEntity problem, interpreter problem] (for grammars, expect to see something like a small interpreter or type checker) - write code that uses dispatch instead of explicit tests + write code to implement classes, including case classes [HW4: FSEntity problem, interpreter problem] TERMS AND CONCEPTS You should be able to explain and use (in problems or essays) the following concepts (with appropriate comparisons to related concepts). You should be able to give examples of these concepts. + Haskell and functional langauge concepts: - using curried functions as toolmakers to abstract from common patterns - combinators - monads + Lambda Calculus langauge concepts: + lambda calculus notation, parsing, and precedence rules + relation between standard lambda calculus notation, and the notation in Haskell + type system of the simply-typed lambda calculus + typing rules and axioms, type environments + substitution, avoiding capture, free and bound variables + equational rules, conversion rules, reduction + normal form, normal order reduction strategy vs. applicative order reduction strategy - Church's thesis - Church-Rosser theorem, confluence, weakly normalizing - strongly normalizing, terminating + Scala and OO language concepts: - Web services + component, component-based programming + packages, imports + value versus reference data in Scala + scala.Predef + class, subclass, object - class object, metaclass + message passing, method + abstract method + trait vs. abstract class + abstract vs. concrete classes + concrete classes versus objects + case classes and abstract syntax trees + XML and how to work with it in Scala, XPath operators (\ and \\) + instance variables, class variables - immutable versus mutable objects - components (composition) vs. inheritance (and when to use each) + inheritance, multiple inheritance (advantages and disadvantages) + semantics of mixins and overriding ++ this, super, and their use in methods (method inheritance) + factoring methods to allow for better method inheritance + equality in Scala, eq vs. == vs. equals [HW3: how does == differ between Scala and Java?] + syntactic sugars and user-defined extensibility in Scala [HW3: what methods are special like apply?] + declaration vs. definition [HW3: Difference between a declaration and a definition?] + val vs. def definitions [HW3: differences between val and def definitions] + Comparisons to other languages: [HW3: How is a trait different from a Java (or C#) interface?] [HW3: pattern matching facility vs. Haskell.] [HW3: advantages vs. Java] [HW4: compare to Haskell] [HW4: compare code reuse versus Haskell] + Benefits of Scala [HW4: what features of Scala in the next programming language?] - OO type system concepts (mostly on the next exam) - type and type errors - protocol, behavioral protocol + type, subtype, behavioral subtype + subtype polymorphism + structural verses nominal (by name) typing + type systems as static approximations + types system soundness, completeness - type systems and security + subclass versus subtype + casting + generics, generic polymorphism + variance annotations + covariance, contravariance + bounded polymorphism, parameter bounds + type members (problems and solutions) + type checking for mixin composition + self types