TOPICS FOR THE 541 TEST on Haskell, and Functional Programming and Related Language Design Topics $Date: 2005/10/06 06:08:41 $ This exam covers topics from homework 1, including functional programming 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 functional programming languages and Haskell, read Thompson's book, "Haskell: The Craft of Functional Programming (second edition)", chapters 1-17. 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 + 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, associated, approximations, commaSeparate, onSeparateLines, isFunction, define ++ using foldr, doubleAll, map using foldr] (Fall '03: associated, Spring '97: disjoint domains of relations) + use list comprehensions to define functions [delete_all, delete_second, matches, library database, doubleAll, brelCompose] (Fall '03: associated, Fall '02: matrixAdd :: Num a => Matrix a -> Matrix a -> Matrix a, Fall '98: setproduct::(Eq a, Eq b) => [a] -> [b] -> [(a,b)], Spring '97: bind for formal parameters or environments ) ++ 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] (Fall '04: concatenated list ADT, write toNormalList catlistMap :: (a -> b) -> CatList a -> CatList b, Fall '04: define an instance of the type class FreeVars for a datatype of terms in the Abadi-Cardelli sigma calculus Fall '03: mapN::([a] -> b) -> [[a]] -> [b], and subtyping test, i.e., (<:)::TypeExpr->TypeExpr->Bool, Fall '02: map2 :: (a -> b -> c) -> [a] -> [b] -> [c], and filterTree :: (a -> Bool) -> Tree a -> Maybe (Tree a), eval for little language of numeric expressions with variables, Fall '99: mapTree :: (a -> b) -> Tree a -> Tree b, type checking for Alexander's VHDL spec language, Fall '98: semantic interpreter for part of FP, Fall '97: Prolog term manipulations: varsIn and renameVars, Spring '97: symbols in Prolog terms, simple type checking for Prolog terms) + write functions using tail recursion + use of infinite (lazy) lists to help modularize code [approximations, within, squareRoot, relativeSquareRoot, diffApproxims, differentiate] (Fall '99: smooth :: Double -> [Double] -> [Double], Fall '97: reliable :: [Int]->[Int]) + use functions as data [compose, infinite sets, infinite geometric regions] (Fall '99: infinite geometric regions, Fall '97: fuzzy sets, membershipDegree, union) - 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] (Fall '03: can you write before::(a->())->(a->b)->(a->b)?, Fall '99: which are constants or constant functions?) + generalize functions [separatedBy, foldTree] (Fall '04: generalize functions on CatLists to write foldCat :: b -> ([a] -> b) -> (b -> b -> b) -> CatList a -> b Spring '97: generalize recursion over lambda calculus terms) + define instances of type classes [functor instance for Trees] (Fall '04: define an instance of the type class FreeVars for a datatype of terms in the Abadi-Cardelli sigma calculus) - 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) 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? + What is a syntactic sugar? Give examples from Haskell. (Fall '04: name a sugar in Haskell, give example and desugaring Spring '97: Why are syntactic sugars important?) + Haskell and functional langauge concepts: - recursion versus tail recursion + polymorphic vs. monomorphic types (Fall '03: say which expressions monomorphpic, ad hoc, or parameteric polymorphic) + 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 (Fall '99: how does laziness help implement DSLs?, Fall '98: how does laziness help programming?, Spring '97: why should a lazy language be applicative?) + avoiding capture + closures (also in Smalltalk blocks) (Spring '97: how is a closure like an object in OOP?) + curried functions + using curried functions as toolmakers to abstract from common patterns - combinators - monads - equational 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