Stuff in RED was not covered in 2013 and therefore not on the final.
Functions * Domain (input) * Range (output) * If x is in the domain of a function f, and y is in the range with y = f(x), then (f x) in Scheme code will ALWAYS return y. Special forms (not functions; rules for application may not follow the mathematical definition of functions) * define * if * cond * quote (means "take literally" or "do not evaluate") * lambda * let (a lambda that is immediately executed; nice for simplifying code) * * Example: ((lambda (x y) (+ x y)) 1 2) * * is the EXACT SAME THING as * * (let ((x 1) (y 2)) (+ x y)) Lambda (unnamed function) * Behaves EXACTLY like a defined function except that it has no name Substitution Model * Tell us that if we have parameters in a function (say, x and y), and if those parameters are bound to values (say 1 and 6), then everywhere you see an x you can replace it with a 1 and everywhere you see a y you can replace it with a 6. This makes it a lot easier to analyze a function and to show your work when analyzing a function. Abstractions (produce abstract data types (ADT)) * Constructors * Selectors (sometimes called accessors) * Predicates (selectors for asking questions) * Mutators (sometimes called modifiers; NOT used in this class) * Constants Word ADT * Constructors * * word * Selectors * * first * * butfirst/bf * * last * * butlast/bl * * item (starts at 1) * * count * Predicates * * empty? * * word? * Constants * * "" (the empty word) Sentence ADT * Constructors * * sentence/se * Selectors * * first * * butfirst/bf * * last * * butlast/bl * * item (starts at 1) * * count * Predicates * * empty? * * sentence? * Constants * * () or '() (the empty sentence) HOFs for words and sentences * every * keep * accumulate List ADT (standard Scheme) * Constructors * * cons * * list * * append * Selectors * * car * * cdr * * cxr (where x is replaced by up to four a/d letters; * * note that the letters are processed right to left: * * (cadddr l) does three cdrs and then a car * * list-ref (starts at 0) * * length * Predicates * * null? * * pair? * * list? * Constants * * () or '() (the empty list) HOFs for lists * map * filter * reduce HOFs for everything * repeated User Input * read * read-line Tree ADT * Constructors * * make-node * Selectors * * datum * * children * Predicates * * leaf? (defined in book; not given as part of simply.scm) * * empty-tree? (discussed in class) * Constants * * the-empty-tree not pre-defined, you have to do it yourself and make * * it consistent with the empty-tree? predicate (discussed in class) Binary search tree (BST) ADT * Constructors * * make-node * Selectors * * datum * * left * * right * Predicates * * leaf? * * empty-tree? * Constants * * the-empty-tree not pre-defined, you have to do it yourself and make * * it consistent with the empty-tree? predicate (discussed in class) Recursion * A recursive function is a function that calls itself * For a recursive function to work, it MUST include two things: * * At least one base case * * At least one recursive call * Recursive functions work by calling themselves with inputs that * get progressively smaller in size * Example: * * (define (factorial x) * * (cond ((= x 1) 1) * * (else (* x (factorial (- x 1)))))) * Usage: * * (factorial 3) becomes * * (* 3 (factorial 2)) becomes * * (* 3 (* 2 (factorial 1))) becomes * * (* 3 (* 2 1)) becomes * * (* 3 2) becomes * * 6 * Note how the inputs to factorial are 3 then 2 then 1... * They decrease as the function gets closer to the solution