exam02 topics

exam02 will be 2022-Dec-06 (Tue) 14:45, in-class, on-paper, closed-notes.

Topics

A practice-exam and solution is available on practice exam (D2L). (A solution for the practice-exam's solution will be released Sunday eve 18:00, to help encourage a practice-take before looking at the solution).

The following topics may be on the exam:

• Tail recursion:
  • be able to define;
  • recognize whether a function is or isn't tail recursive;
  • be able to convert a (Java-ish) while-loop into a tail-recursive function perhaps adding a helper-function which accepts the loop's “so-far”/accumulator variable as an argument;
  • be able to write a tail-recursive function from scratch;
  • Understand how a compiler can optimize tail-recursive functions to avoid building up unnecessary stack frames.
• Context-Free Grammars:
  • Given a grammar, be able to design structs to represent parse trees for it (you'll have a choice of racket or Java).
  • write a recursive-descent parser for that grammar (returning the parse tree).
  • Be able to write functions which process that parse-tree, including functions that selectively stop processing sub-trees based on some criterion.
  • From an English description of desired strings, be able to come up with a grammar that generates it e.g. for a (simplified) Java-field-declaration, or a Java-Boolean-Expression.
• Questions based on bits of code from the B0–B4 implementations, possibly modifying that code.
• Understanding static scope (let,let*), shadowing, and function-closures.
• prolog questions, including list-based processing.
• Anything else on hw06–hw10.
• questions very-similar to #1,#2 from the exam02-practice.
• Questions the same-or-similar-to any question on exam01 are certainly fair game.

The following will not be on the exam:

• The second half of the lecture objects using let-over-lambda (v4 and onward).
  (Your understanding of let's scope and closures should make the examples up through v3 sensible at least, except for the match-define shortcut. However, none of the v4 or higher examples will be on the exam (and certainly no define-syntax).
• Functions which return a function (as discussed in the last lecture on higher-order-functions).

Instructions:

• This exam is 2hrs, in-class, on-paper.
• Please use any suggested abbreviations, to save writing. In addition, I recommend using short (but mnemonic) field-names (3 letters or so). E.g., str+ for string-append, str=? for string=?, def/c for define/contract, def-str/c for define-struct/c, mk-… for make-…, and nat? for natural?.
• Unless otherwise specified, you may write any exam-code in Java, or in Racket.
  You may even switch languages between problems; just be sure to use the correct field/struct names.
  For each java method, specify which class that method belongs in.
• If using Java, you may assume we are using records (so you have a standard/boilerplate constructor, toString, equals, and hashCode).
For parsing, you can use either java.util.Scanner methods next(), hasNext(String), nextDouble(),hasNextDouble(), or a Racket scanner with functions peek and pop!.

// Java: boolean hasNext( String s ) /* Is the next token equal to `s` (or, matches `s` as a regex)? Consumes no input. */ boolean hasNextDouble() /* Is the next token a numeral? Consumes no input. */ String next() /* Return the next token from the input stream, consuming it. */ String next( String s ) /* Return the next token from the input stream, consuming it; throw exception if the token doesn't match the regular expression `s`. */ boolean nextDouble() /* Return the next token from the input stream as a double, consuming it. */ ;; Racket: peek : scanner → String ; return the next token from the input stream, not consuming it. pop! : scanner → String ; return the next token from the input stream, consuming it.

Assume that the scanner correctly accounts for how punctuation separates tokens (for the exam you can pretend java.util.Scanner does this; for the project, we needed the UtilIan methods to do so).
• For any question, you may use functions defined in previous questions and assume they are correct, even if you didn't complete the previous question.