Topics for Test on EOPL Chapter 3

* Reminders

For this test, you can use one (1) page (8.5 by 11 inches, one (1)
side, no less than 9pt font) of notes.  Handwriting is okay.
No photo-reduction is permitted. Don't use anything with printing on the
other side, please.  These notes are to be handed in at the end of the
test.  Have your name in the top right corner. Use of other notes or
failure to follow these instructions will be considered cheating.

WARNING: you won't have time to learn the material on during the test.
Just write down what would be too tedious to remember otherwise.

Topics marked `+' below are more important than topics marked `-'
below.  In general, things that are more like the homework (4 and the
first part of 5) will be more important.  I have cited [in square
brackets] problems from homeworks 4 and 5 that are illustrate the
relevant ideas for this test.  Note that I may ask some questions that
integrate ideas, such as whether define-record-type should be
considered to be syntactic sugar (and for what?), or programming
free-vars and bound-vars over some abstract syntax using variant-case.

* Chapter 3

** syntactic abstraction (3.1-3.3)

	+ The advantages and reasons for using syntactic abstraction (sugaring)
		(Why is it a good thing?)
		[advantages of syntactic abstraction,
		 define-record and variant-case as syntactic abstractions]

	- Which is the sugared form, and which is the desugared form?

	+ Know how to desugar expressions in Scheme
		for the sugars: let, and, or, cond, case
          and how to use the sugars to abbreviate the desugared forms.
	  [desugar-let, desugar-cond]

	(you should also know that letrec is a syntactic sugar, but I won't
	test you on the details or how to desugar a letrec.)

	++ what are the consequences of the syntactic sugarings
           for scope rules?
		e.g., What are the free or bound variables/varrefs in a let?
		[free-vars, bound-vars, record-free?, record-bound-vars]

	++ what the free and bound variables are in a letrec, and how they
          differ from let

	+ Be able to use let, letrec, and, or, cond, case in Scheme programs.
	  [cond vs. case]

	+ Be able to determine the values of expressions using them.
	  [value of let expressions on hw4]

	- Be able to use letrec to write a tail-recursive procedure
	  [vector-index]

	+ be prepared to give an example of a syntactic sugar
		(and the corresponding desugared forms) in some other
		language, such as C++, C, Pascal, etc.
		[examples of syntactic abstraction]
	
** records (3.4)

	- What is a variant record?  Give examples.  What would this look
	  like in other languages?
	  
	+ what does define-record do?  How are the procedures it produces used?
	  [leaf-sum]

	++ Be able to use variant-case in Scheme programming,
		especially over some abstract syntax.
		[eval-arith-expr, strength-reduce]

	+ What is the abstract syntax for some concrete syntax?
		e.g., given a concrete syntax in the form of a BNF,
			give the corresponding record declarations.
			[abstract syntax for a grammar]

	- what does parse do?  what does unparse do?

	++ You should be able to write recursions over abstract syntax,
		using variant-case [eval-arith-expr, strength-reduce,
		record-free?, record-bound-vars]

** data abstraction (3.5)

	+ What is the importance of data abstraction?
		Can you give examples?  (Both positive and negative ones)

	+ What is the importance of representation independence?
		Can you give examples?  (Both positive and negative ones)
		[transparent reps]

	+ how does the type of an ADT's operations relate to the types
		of the implementation's operations?
		[vector rep of records, list rep of records]

	+ Be able to answer questions about the behavior of the ff ADT.
		(e.g., given an example, what is the output?)
		[finite function ADT]

* Transformation of Procedural to Record Representations (3.6)

        + Be able to implement an ADT using a procedural
        representation [infinite-set-ADT]

	++ Be prepared to transform a procedural representation of some data
		to a record representation, or vice versa
		[infinite-set-ADT-record]

* Hints
	You might look at the suggested practice problems in the homework,
        and at the old tests on-line.