Topics for Exam 1 in Com S 342 This test covers topics from homeworks 0 and 1. REMINDERS This test is closed book and notes. (Although later tests will allow you to use a page of notes, but we want you to have the basics of Scheme memorized.) If you need more space, use the back of a page. Note when you do that on the front. This test is timed. We will not grade your test if you try to take more than the time allowed. Therefore, before you begin, please take a moment to look over the entire test so that you can budget your time. For programs, indentation is important to us for ``clarity'' points; if your code is sloppy or hard to read, you will lose points. Correct syntax also matters. Check your code over for syntax errors. You will lose points if your code has syntax errors. READINGS For homework 0: Class language design discussion Related to this discussion you should read chapter 1, especially section 1.1 (pages 1-30) of the recommended textbook Structure and Interpretation of Computer Programs, by Abelson and Sussman, which is on reserve and also on-line at http://mitpress.mit.edu/sicp/. For a reference on Scheme, see the Revised^5 Report on Scheme, which is available in several formats from the course resources web page and in DrScheme's help. For homework 1: Structure And Interpretation Of Computer Programs (Sections 1.1.1-1.1.6, 2.2.1-2.2.2, and 2.3.1) The Little Schemer (p. xiii, chapters 1-4) Revised^5 Report On The Algorithmic Language Scheme (Sections 1 [Overview], and 6.1-6.3 [Standard Procedures]) Scala Rationale TOPICS Topics marked + below are more important than topics marked - below. Topics marked ++ are pretty much certain to be on the exam. In general, things that are more like the homework will be more important. Homework problems are marked in [square-brackets]. Problems from old exams are marked in (parentheses). * Language design, goals + Means of computation, combination, and abstraction. + You should be able to give examples of these in Scheme, C++, and Java. [HW0: means of combination, means of abstraction] (Spring'06: classify features of Scala as means of computation, means of combination, and means of abstraction; Spring'05: classify features of SNOBOL; Spring'04: example of means of computation in Scheme, example of means of combination in Scheme, example of means of abstraction in Scheme; Spring'01: which are means of computation?, which are means of combination?, which are means of abstraction?) + Design goals of Scheme vs. Java (and C++) vs. Scala [HW0: design goals] + What are the design goals of Scheme? + Why are various data types included in Scheme or excluded? - What are the design goals of Java? - What are the design goals of Scala? + How did they influence the design and syntax of Java? (Spring'06: what design goals of Scala influenced XML literals and in Scheme quotation? Spring'05: what design goals of Java influenced detailed specification of numeric operations and formats? Spring'04: which design goals of Java influenced garbage collection as a feature?) + Differences between Java and Scheme syntax (if, begin, calls) [HW0: means of combination in Java (or C++)] - Static vs. dynamic type checking - advantages and disadvantages of each - how each matches design goals of Simple/Scheme vs. Java/C++ (Spring'01: why does dynamic type checking match goals better?) + expressiveness of data types - Special forms - if expressions - regularity of a language * Scheme ** data types - how to describe abstract data types: abstract values, external form, literals, operations, special forms + built-in types in Scheme, especially booleans, lists, numbers, and symbols - (other types, e.g., strings, vectors are less important) - (you don't need to know all the details of operations we haven't used in homework) - dot-notation - read dot-notation - translate back and forth between dot and list notation ** Expressions + translate algebraic notation into Scheme notation [HW1: translate into Scheme notation] ++ write Scheme code to: + give definitions [HW1: define pi and e] + compute conditionals (using if or cond) [HW1: find min and max of pi and e] ++ make symbols [HW1: experiment with quote (')] ++ construct and lists and pairs (improper lists) using either cons, or list, and numbers and quoted symbols [HW1: construct lists] (Spring'06: create ((problems) (worthy of attack)) using cons; Spring'05: create (cool (that is good)) using cons; Spring'04: create nested list of states using cons) + draw box and pointer diagrams [HW1: draw box and pointer diagrams] (Spring'05: draw diagram for (cool (that is good)); Spring'04: draw box and pointer diagram for nested list of states; Spring'01: draw diagram for ((oysters) (half shell))) ++ extract parts of lists (and improper lists) [HW1: extract parts of lists] (Spring'06: extract lists and symbols from a grook; Spring'05: extract you and (is good) from dictionary; Spring'04: extract iowa from usa-states; Spring'01: extract bacteria from the-kingdoms) + evaluate expressions using define, cons, car, cdr, list, eq?, equal?, etc. + Know when to use eq? vs. equals? [HW1: eq? and sharing transcript] + explain the difference between strings and symbols in Scheme [HW1: what can you do with string that can't be done with a symbol?] - explain the difference between vectors and lists in Scheme - procedure terminology: procedure (Scheme), function (math), application, combination operator, operand, subexpressions, arguments, actual parameters, actuals, parameters - read-eval-print loop ** procedures - what lambda does * programming in Scheme ++ Write Scheme procedures that: ++ extract and rearrange parts of a list [yodaize example in class] (Spring'06: name-event from a list of 4 symbols; Spring'05: delete-third from list of 4 symbols; Spring'04: make-question from list of 3 symbols; Spring'01: twist a list of 3 symbols) ++ recursively test the elements of a list for some property [HW1: all-numbers, list-of-number, occurs-twice] (Spring'06: all-divisible-by? list-of-lists?; Spring'05: symbols-first? all-length-n?; Spring'04: all-pork-dishes? all-bigger-than-first?; Spring'01: all-upper-case? equal-all?)