TOPICS FOR THE 541 TEST on Haskell, Functional Programming, Smalltalk, OO Programming and Related Language Design Topics $Date: 2003/10/13 21:27:14 $ This exam covers topics from homeworks 1-3, including expressive power, functional programming in Haskell, lambda calculus, and object-oriented programming in Smalltalk. It does not cover object-oriented type systems. 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 issues of expressive power read Matthias Felleisen's paper "On the Expressive Power of Programming Languages", in Science of Computer Programming 17(1-3):35-75, Dec. 1991. For functional programming languages and Haskell, read Thompson's book, "Haskell: The Craft of Functional Programming (second edition)", chapters 1-17. 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 primarily, you should read chapters 1-14 of Adele Goldberg and David Robson's book, Smalltalk-80: The Language (Addison Wesley, 1989). If you have time, see the course web site and also the course syllabus for other readings. 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 Expressive power; be able to: + Apply the concept of expressive power to Haskell and Smalltalk - Desugar Haskell function definitions + Haskell programming; be able to: + give the output of a Haskell expression, possibly involving higher-order functions, or library functions of general utility, such as map, foldr, filter, or list comprehensions + use library functions such as map, foldr, and filter [delete_all, delete_second, matches, approximations, commaSeparate, onSeparateLines, isFunction, define ++ using foldr, doubleAll, map using foldr] + use list comprehensions to define functions [delete_all, delete_second, matches, library database, doubleAll, brelCompose] ++ write recursive functions on lists, numbers, and algebraic data types (grammars) (for grammars, expect to see something like a small interpreter or type checker) [delete_all, delete_second, merge, onSeparateLines, sumTree, preorderTree, typeOf for Exps, lambda calculus type checker] + write functions using tail recursion + use of infinite (lazy) lists to help modularize code [approximations, within, squareRoot, relativeSquareRoot, diffApproxims, differentiate] + use functions as data [compose, infinite sets, infinite geometric regions] - infer the types of expressions or functions - describe properties of a value in Haskell depending on its type [extra credit: whether functions are constant from types] - generalize functions [separatedBy, foldTree] - define instances of type classes [functor instance for Trees] - desugar expressions in Haskell - write monadic-style code - explain how a purely functional language like Haskell connects to the real world and still preserves referential transparency (using the IO type) + Lambda Calculus langauge; be able to: + use the parsing and precedence rules for the lambda calculus ++ gives the type of a term in the simply-typed lambda calculus + formally reduce a term to normal form + Smalltalk programming; be able to: + give output of Smalltalk code, especially for code that uses inheritance, method overriding, and "super" + write client code that uses existing classes in Smalltalk [like NGon's drawNested: method] ++ design and write code for classes in Smalltalk + based on specifications [HW1: HanoiDisk] + using inheritance: + as a subclass of a given class [HW1: NGon] ++ as a subclass of Collection [HanoiTower, BinaryRelation, ReflexiveRelation] + as a subclass of Stream [HanoiMoveStream] - using indexed instance variables + write code that uses dispatch instead of explicit tests, like the Booleans or the List example from class - Be able to extract the problem from a paper you have read, explain its main points, and discuss its contribution vs. related work. [HW3: problem 10] 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. + General points about programming languages: - What is a programming language? - What is a paradigm? What kinds of paradigms are there? How do languages fit within the different paradigms? + Expressive Power Concepts: + What is a syntactic sugar? Give examples from Haskell. + What is in a eliminable feature of language? Give examples from Haskell. - What are the essential features of Haskell that are not eliminable? + Haskell and functional langauge concepts: - recursion versus tail recursion + polymorphic vs. monomorphic types + algebraic types and their relation to grammars + abstract data types vs. free types + type checking in Haskell and type inference + ad hoc polymorphism and Haskell's type classes and instances + higher-order type classes (like Functor) + lazy evaluation and normal order evaluation vs. eager evaluation + avoiding capture + closures (also in Smalltalk blocks) + curried functions + using curried functions as toolmakers to abstract from common patterns - combinators + monads + equation reasoning for functional programming + structural induction for proving properties, e.g. of list functions - proving properties about partial or infinite lists + module systems and Haskell's module system + relationship between modules and records + export control: hiding definitions + import conflict resolution - higher-order modules + Lambda Calculus langauge concepts: + lambda calculus notation, parsing, and precedence rules + relation between standard lambda calculus notation, and the notation in Haskell and Smalltalk + type system of the simply-typed lambda calculus + typing rules and axioms, type environments + substitution, avoiding capture, free and bound variables - Church's thesis + equational rules, conversion rules, reduction + normal form, normal order reduction strategy vs. applicative order reduction strategy - Church-Rosser theorem, confluence, weakly normalizing - strongly normalizing, terminating + Smalltalk and OO language concepts: + class, subclass, object - class object, metaclass + message passing, method + abstract method + abstract vs. concrete classes + instance variables, class variables ++ protocol, behavioral protocol ++ type, subtype, behavioral subtype + polymorphism + mutable vs. immutable objects + components (composition) vs. inheritance (and when to use each) + inheritance, multiple inheritance (advantages and disadvantages) ++ self, super, and their use in methods (method inheritance) - factoring methods to allow for better method inheritance + equality in Smalltalk, = vs. == [HW3: problem 9] - hashCode vs. identityHashCode, and Set vs. IdentitySet + aliasing, exposing the rep (and how to avoid it) [HW13 BinaryRelation, ReflexiveRelation] - frameworks