cs380 Exams

exam02 will be 2025-May-06 (Tue) 10:15, 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 at Sunday noon, to help encourage a practice-take before looking at the solution).

The following topics may be on the exam:

Standard vocabulary (e.g. parameter vs. argument vs. local variable; expression vs. statement; statically typed vs. dynamic typing vs. untyped; compiled vs. interpreted)
programming language paradigms — low-level, procedural, O.O., scripting, functional, declarative. Be able to give the primary features of each family/paradigm, and give a notable language associated with that paradigm.
Trade-offs of mutable vs. immutable data
Scope and shadowing: a binding occurrence vs. a bound occurrence; racket's let and let*.
Higher-order functions.
- You should be able to read and understand code that passes a function as an argument (either a named function, or an anonymous lambda/λ expression), as well as code which receives a function as an argument.
- How to write a function which returns a (newly-created) function (e.g. and/f from hw07/hw07-soln.
- You should be able to write the signature for such functions. Remember, you don't just say the input is "a function"; you provide the signature of that function — recall the shapes-in-a-row function from hw07/hw07-soln.
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 H0–H5 implementations, possibly modifying that code.
Understanding static scope (let,let*), shadowing, and function-closures. Regarding closures, you will want to know the concept/definition, be able to recognize an example of a closure that captures variables ¹ and roughly how they can be implemented in H6, but you won't be responsible for any specific code for implementing that.
prolog questions, including list-based processing.
Anything else on hw06–hw11.
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).

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 (sub)problems; just be sure to use the same field/struct names.
For any 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 hasNextDouble()      /* Is the next token a numeral?  Consumes no input. */
double  nextDouble()         /* Return the next token from the input stream as a double, consuming it. */
boolean hasNext( String s )  /* Is the next token equal to `s` (or, matches `s` as a regex)?  Consumes no input. */
String  next()               /* Return the next token from the input stream, consuming it. */


;; Racket:
peek : (-> scanner? (or/c string? number?)) ; return the next token from the input stream, not consuming it.
pop! : (-> scanner? (or/c string? number?)) ; 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.