TOPICS FOR THE COP 4020 EXAM
                                  on
		  Declarative Programming Techniques
                     $Date: 2010/11/05 18:50:39 $
				   
This exam covers topics from homework 3, including
declarative programming techniques.  It is related to all the course
objectives, but especially to [UseModels]. 

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.  We suggest that you memorize the Oz syntax
you'll need.) 

If you need more space, use the back of a page.  Note when you do that
on the front.

Before you begin, please take a moment to look over the entire test
so that you can budget your time.

Clarity is important; if your programs are sloppy and hard
to read, you may lose some points.  Correct syntax also makes a difference
for programming questions.

When you write Oz code on this test, you may use anything in the
declarative model (as in chapters 2-3 of our textbook), so you must
not use cells or the library functions IsDet and IsFree.  But please
use all linguistic abstractions and syntactic sugars that are helpful.

You are encouraged to define functions or procedures not specifically
asked for if they are useful to your programming; however, if they are
not in the Oz base environment, then you must write them into your
test.  You can use the built-in functions in the Oz base environment
like Append, Filter, Map, and FoldR.

HINTS

If you use functions like Filter, Map, and FoldR whenever possible,
you will have to write less code on the test, which will mean fewer
chances for making mistakes and will leave you more time to be
careful.

In the "follow the grammar" problems the examples may be very
extensive and take a long time to read if you read every detail.  But
the basic idea of the recursion is usually clear from the description,
simple examples, and the "follow the grammar" idea of recursing
everywhere possible.  So look to the examples to confirm your
understanding and don't spend time reading examples after you
understand the problem.

READINGS

Read chapter 3, sections 3.1-3.9 of van Roy and Haridi's "Concepts,
Techniques, and Models of Computer Programming" (MIT Press, 2004).
Also read the "Following the Grammar" handout and be sure to get the
comments from our grading of your homework.  You can also see our
solutions from webcourses.

If you have time, study the relevant examples form the Code examples
Web page.  Also if you have time, and try the old exams (but note that
some problems that are relevant to this exam were on Exam 3 in other
semesters).  Also 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 [UseModels] [Concepts] [MapToLanguages]

 + Oz programming; be able to:
  ++ Write iterative functions on integers and lists
     [HW3: LastIndex using tail recursion, iterative SumList]
     (Fall07: MinElement, SumSquares;
     Spring08: SumValues of a list using tail recursion;
     Fall08: Find element of a list using tail recursion;
     Spring09: Count elements in a list equal to argument using tail recursion;
     Fall09: Write MyLength iteratively
     Spring10: Write DecimalValue iteratively)

   + Know when to use (or not use) tail recursion to write iterative functions.
   - Convert a fully recursive function into one that uses tail recursion.

  ++ Write functions that work on (finite) lists (following the grammar)
     [HW3: ExpandEnglish, InAList, ReplaceNth, Bag Operations, BRelConverse]
     (Fall07: TeamSpirit, EvenNumbers;
      Spring08: VoteFor, Positive;
      Fall08: Find, RoboCall, StateTemps, and ApplyList;
      Spring09: Down, Map2; Fall09: SquareAll, SelectAndMap, Project
      Spring10: PrefixAll, Partition)

   + Write functions that implement the operations of some declarative ADT.
     [HW3: BagOps, Possibly Infinite Bags (PIBag)]

  ++ Write functions that work on a given grammar, following the
     grammar, even if the grammar is previously unknown to you and for
     which you have never seen examples.
     [HW3: ChangeChannel on the WindowLayout grammar]
     [HW3: NegateIfs on the Statement and Expression grammar]
     [HW3: HighestNote and Transpose on Music grammar]
     [HW3: TypeOf on an expression grammar]
     (Fall07: TeamSpirit, EvenNumbers on list grammar, 
     ChangeChannel on WindowLayout grammar, 
     EvalExp on a new expression grammar,
     ChangeAddress on SalesData grammar, 
     FreeVarIds on the one-argument lambda calculus grammar;
     Spring08: VoteFor and Positive on list grammar,
     NegateIfs on the statement and expression grammar,
     Transpose on a new grammar for "music";
     Fall08: Find, RoboCall, StateTemps, and ApplyList on list grammar,
     OptimizeIfs on the statement and expression grammar;
     Spring09: Write MaxAmmounts using sales data grammar,
     write ApplyRules using Rule grammar;
     Fall09: write Subst for the BExp grammar, AllPass for a testcase grammar
     Spring10: write Iconify over the WindowLayout grammar, 
               write Retrograde over the Music grammar)

 + Oz programming; be able to:
   + Write functions using for loops (with collect:).
     [HW3: Capitalize]
     (Fall08: RoboCall that maps a list and StateTemps that filters a list)

  ++ Write functions using Oz library functions such as Map, Filter,
     FoldR, All.
     [HW3: Capitalize]
     [HW3: MyAppend, DoubleAll, and MyMap using FoldR]
     (Fall 07: MinElement, SumSquares using FoldR;
     Spring08: Positive elements in a list of numbers using FoldR,
     FilterThenMap that filters a list and maps over it also;
     Fall08: RoboCall that maps a list and StateTemps that filters a list,
     write ApplyList that applies all the functions in a list using FoldR;
     Spring09: write NoDuplicates test using FoldR)

   + Know when to use Oz library functions (especially Map, Filter, and FoldR)
     and for loops.
     [HW3: AppendMap using FoldR]
     (Spring08: Positive elements in a list of numbers using FoldR;
      LazyLanguages filter on a database using for loops;
      Fall08: RoboCall that maps a list and StateTemps that filters a list;
      Spring09: write NoDuplicates test using FoldR
      Spring10: PrefixAll (use Map!), CurriedPartition (use Filter!), 
                AppendAll using FoldR)

   + Curry a given function (make a curried version of it).
     (Spring08: Curry2 for currying a 2 argument function;
     Fall09: Curry Project function)
   - Uncurry a given function.

  ++ Write curried, higher-order functions that satisfy some specification.
     [HW3: Curry]
     [HW3: Possibly Infinite bags (PIBag)]
     (Spring08: Curry2 for currying a 2 argument function;
     Fall08: StateTemps that filters a list;
     Spring09: Map2 for mapping a 2 argument function over two lists
     SPring10: CurriedPartition)

   + Write higher-order abstractions of other functions, and 
     use the abstraction to define the original other functions
     [HW3: SearchForMaker as abstraction of SearchForZero and SearchForFixedPoint]
     [HW3: FoldMusic as abstraction of HighestNote and Transpose]

   + Use functions embedded in data to implement a specification.
     [HW3: Possibly Infinite sets (PISet)]
     (Fall08: ApplyList that applies all the functions in a list of functions)


TERMS AND CONCEPTS [Concepts] [MapToLanguages] [EvaluateModels]

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.

 + following the grammar

    + Read a BNF grammar for a data structure.
    + Decide whether code (in Oz) follows a given grammar.
      [Self test on webcourses: following grammar for lists]

 + declarative model semantics

    + When is declarative programming useful?
      [HW3: Why is declarative programming useful?]
      [HW3: Can you write declarative programs in C, C++, or Java?]
    + How is declarative programming defined?
      [HW3: In the declarative programming model, how can a function
      make a change to a data structure?]
      [HW3: Name a language capability that is not supported by the
      declarative programming model, and that is useful in interfacing
      with the physical world.]
    - Time and space of the declarative model
      [HW3: How does the book recommend calculating time and space
      needs of a program? Would that work in Java?]

    + What is a difference list? 
    + What are difference lists useful for? What are their limitations?

 + declarative model and higher-order functional programming
    + What is a closure?
    + What is a higher-order function?
      [HW3: Briefly describe what the Some function does.]
    + What is a curried function?
   
 + Abstract Data types
    + How is an ADT different from a data type specification?
    + What is an invariant property of data?
    + What problems related to the security of ADTs do we need to prevent?
    + Why prevent them?  How could we prevent them?
      [HW3: What kind of data member is used to hide data in Java or C+?]
    - Why are read-only views needed in the declarative model?

 + Modules
    + What is a module? What is it like in C, C++, and Java?
      [HW3: In what way is a module in Oz like a class in C++ or Java?]
    + What is a functor? What is it like in C, C++, and Java?
    - How are modules linked in Oz?