COMPSCI 61A Midterm Review: Higher-Order Functions, Recursion, Objects and Interpreters

Terms in this set (33)

1. What is abstraction in programming?Hiding the details of how something works behind a name or interface, so you can use it based only on what it does. Functions, data types and classes are all abstraction tools.
2. What is a higher-order function?A function that takes another function as an argument, returns a function, or both. Examples: map, filter, and a function that builds and returns an adder.
3. What does this return? def make_adder(n): return lambda x: x + n ... make_adder(3)(4)7. make_adder(3) returns a function that adds 3 to its argument, and calling it with 4 gives 7.
4. What is an environment frame?A record of name-to-value bindings. Evaluating a name looks it up in the current frame, then each parent frame, ending at the global frame.
5. Which frame is the parent of a new frame created by calling a function?The frame in which the function was defined (lexical scoping), not the frame from which it was called.
6. What is a closure?A function together with the environment it was defined in, so it can still access names from that enclosing frame after the outer function has returned.
7. What does the nonlocal statement do?It lets an inner function reassign a name bound in an enclosing (non-global) function's frame instead of creating a new local binding.
8. Two essential parts of a recursive functionA base case that returns without recursing, and a recursive case that calls the function on a smaller problem moving toward the base case.
9. Write factorial recursively in one line of logicdef fact(n): return 1 if n == 0 else n * fact(n - 1). fact(4) = 4*3*2*1 = 24.
10. What is tree recursion?Recursion where a call makes more than one recursive call, like fib(n) = fib(n-1) + fib(n-2) or counting partitions. Its call structure forms a tree.
11. Counting partitions idea: count_partitions(n, m)Number of ways to write n as a sum of parts up to size m = ways using at least one m (count_partitions(n-m, m)) + ways using no m (count_partitions(n, m-1)).
12. Pitfall: why can naive recursive Fibonacci be slow?It recomputes the same subproblems many times, giving exponential time. Memoization (caching results) makes it linear.
13. Python list comprehension syntax[expression for x in iterable if condition]. Example: [x * x for x in range(5) if x % 2 == 0] gives [0, 4, 16].
14. Iterable vs iteratorAn iterable can produce an iterator through iter(). An iterator returns successive values through next() and raises StopIteration when it runs out; it can be used only once.
15. What is a generator function?A function containing yield. Calling it returns a generator (a lazy iterator) that runs until each yield, pausing and resuming its state between next() calls.
16. What does yield from do?It yields every value from another iterable or generator in turn, which is handy for recursive generators.
17. What is a data abstraction barrier?A separation between code that uses a data type through its constructors and selectors and code that implements its representation. Violating it means relying on internal details.
18. Mutable vs immutable values in PythonLists and dictionaries are mutable (can change in place). Integers, strings and tuples are immutable. Two names bound to the same list both see changes made through either name.
19. is vs == in Python== tests whether two values are equal. is tests identity, that is, whether both names refer to the very same object.
20. Class attribute vs instance attributeA class attribute is shared by all instances and stored on the class. An instance attribute is stored on one object, often set in __init__ through self.
21. What is inheritance?A subclass reuses the attributes and methods of its base class and can override them. Attribute lookup checks the instance, then its class, then base classes.
22. Bound method: what happens with obj.method(arg)?Python looks up method on the class and passes obj automatically as the first parameter, self, so it is the same as Class.method(obj, arg).
23. __str__ vs __repr____str__ gives a readable string used by print and str(). __repr__ gives an unambiguous string, ideally valid code, shown by the interactive interpreter and repr().
24. What is a linked list?A recursive sequence where each node holds a first value and a rest, which is another linked list or empty. Access to the k-th element takes time proportional to k.
25. What is a tree in 61A-style data abstraction?A value with a label and a list of branches, where each branch is itself a tree. A leaf has no branches.
26. Order of growth: what is Theta(log n)?Time grows with the logarithm of input size, typical when each step halves the problem, as in binary search or repeated halving of n.
27. Order of growth of a nested loop over n items for each of n itemsTheta(n^2), quadratic: doubling n roughly quadruples the work.
28. Functional vs object-oriented vs declarative paradigmsFunctional: compose pure functions and avoid mutation. Object-oriented: bundle state and behavior in objects. Declarative: state what result you want (as in SQL) rather than how to compute it.
29. In Scheme, what does (define (square x) (* x x)) do?It binds the name square to a procedure that multiplies its argument by itself. Scheme uses prefix notation with the operator first inside parentheses.
30. What are the two core steps of an interpreter's eval loop?Eval evaluates an expression: for a call it evaluates the operator and operands. Apply then calls the procedure on those argument values, often by evaluating its body in a new frame.
31. Special form vs call expression in SchemeA call expression evaluates all operands first. Special forms such as if, define, lambda and and do not evaluate all subexpressions in the usual way.
32. What is a macro?A procedure that operates on unevaluated code and returns new code, which is then evaluated in the caller's environment. It lets you add new special forms to a language.
33. What is tail recursion and why does it matter in Scheme?A call is in tail position when nothing remains to do after it returns. Scheme implementations must optimize tail calls, so tail-recursive procedures use constant space.