official website | free online textbook
Contents
- Intro
- Mapping from Lectures to Assignments
- Mapping from Questions to Lectures and Assignments
- Projects
| Questions(the contents start with * are extensions from lectures) | Answers | Relevant lectures | Relevant assignments | Relevant projects |
|---|---|---|---|---|
| what is expression? | An expression describes a computation and evaluates to a value in the context of an environment. | Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Types of Expressions | 1. Primitive expressions: number; name(symbol), string. 2. Call expressions: combination of operators and operands. |
Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Evaluation procedure for call expressions | 1. evaluate operators and then operands subexpressions 2. apply the function that is the value of evaluated operator to the arguments that are the values of evaluated operands. |
Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| *Wha is statement? | A statement is executed by the interpreter to perform an action. 1. simple statements: A simple statement is comprised within a single logical line. Several simple statements may occur on a single line separated by semicolons. Examples: assignment statements, import statements, return statements. 2. compound statements: Compound statements contain (groups of) other statements; they affect or control the execution of those other statements in some way. In general, compound statements span multiple lines. Examples: while statement, conditional statement, try statement.(Reference: The Python Language Reference |
Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Execution rule for assignment statements | 1. Evaluate all expressions to the right of = from left to right. 2. Bind all names to the left of = to those resulting values in the current frame. |
Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Means of abstraction | 1. assignment is simple means of abstraction, binding names to values 2. function definition is a more powerful means of abstraction, binding names to expressions |
Functions, Interpreter, Control | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| what is data abstraction? | A methodology by which functions enforce an abstraction barrier between representation and use. Data abstraction uses selectors and constructors to define behavior, leting us manipulate compound values as units. Data abstraction is one method for oragnizaing programs, while another method is bundling together information and related behavior by objects. |
Functions, Data abstraction, Objects | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Procedure for calling/applying user-defined functions | 1. Add a local frame, forming a new environment 2. Bind the function's formal parameters to its arguments in that frame 3. Execute the body of the function in that new environment |
Functions, Interpreter | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| *what is function signature? | A function signature (or type signature, or method signature) defines input and output of functions or methods. A ignature can include: parameters and their types. a return value and type. A function’s signature has all the information needed to create a local frame (Reference: Signature |
Functions, Interpreter | lab01(Functions, control), hw01((Functions, control) | Scheme interpreter project |
| Pure functions and non-pure functions | Pure functions only return values. A pure function's behavior is the relationship it creates between input and output. While non-pure functions also have side effects, which are not values, but consequences of calling functions. |
Control | Hog | |
| what is a function's domain and range? | A functions' domain is the set of all inputs it might possibly take as arguments. A function's range is the set of output values it might possibly return. | Higher-order functions | Hog | |
| What is higher-order function? | Higher-order function is a function that takes a function as an argument value or returns a function as a return value. Remember, functions are values in Python. | Higher-order functions | lab02, hw02, lab03 | Hog |
| Lexcial scope and dynamic scope | Python is a language using lexical scope(also called static scope), which means the parent of a frame is the environment in which a procedure was defined. Lisp is language using dynamic scope, which means the parent of a frame is the environment in which a procedure was called. | Environments, Tail calls | lab02, hw02, lab03 | Scheme Interpreter |
| What is lambda expression? | Lambda expressions (sometimes called lambda forms) are used to create anonymous functions. Note that functions created with lambda expressions cannot contain statements or annotations. (Reference: The Python Language Reference | Environments | lab02, hw02, lab03 | Hog |
| What is return statement? | A return statement completes the evaluation of a call expression and provides its value, switching backing to the previous environment. In a generator function, the return statement indicates that the generator is done and will cause StopIteration to be raised. A function that does not explicitly return a value will return None, which is not displayed by the interpreter as the value of an expression. |
Functional abstraction | lab03 | Hog |
| How are logical operators evaluated? | To evaluate the expression and : 1. Evaluate the subexpression 2. If the result is a false value v, then the expression evaluates to v. To evaluate the expression or : 1. Evaluate the subexpression . 2. If the result is a true value v, then the expression evaluates to v. 3. Otherwise, the expression evaluates to the value of the subexpression . 3. Otherwise, the expression evaluates to the value of the subexpression |
Functional abstraction | lab03 | Hog |
| what is decorator? | A decorator is a design pattern in Python that allows a user to add new functionality to an existing object without modifying its structure. The return of decorator is a new version of function we want. (Reference: What is Decorator?) | Function examples | ||
| what is recursive function? | A function is called recursive if the body of that function calls itself(self reference), either directly or indirectly. The function is consist of base cases which are evaluated without recursive calls, and recursive cases which are evaluated with recursive calls. | Recursion, Tail calls | lab04, hw03 | Cat |
| For statements | 1. Evaluate the header , which must yield an iterable value (a sequence) 2. For each element in that sequence, in order: A. Bind to that element in the current frame B. Execute the |
Sequences | lab04, lab05, hw04 | Cat |
| what is list comprehension? | A list comprehension consists of brackets containing an expression followed by a for clause, then zero or more for or if clauses. The result will be a new list resulting from evaluating the expression in the context of the for and if clauses which follow it. (Reference: list comprehension | Sequences | lab04, lab05, hw04 | Cat |
| The Closure Property of Data Types | A method for combining data values satisfies the closure property if the result of combination can itself be combined using the same method. Closure is powerful because it permits us to create hierarchical structures. In Python, list satisfies the closure property. | Containers | lab04, lab05, hw04 | |
| what is dictionary comprehension？ | Dict comprehensions are just like list comprehensions, except that you group the expression using curly braces instead of square braces. Also, the left part before the for keyword expresses both a key and a value, separated by a colon. | Containers | lab04, lab05, hw04 | |
| what is object? | Objects represent information,** consisting of data and behavior** which are bundled together to create abstractions. Objects can represent things, but also properties, interactions, & processes. In Python, every value is an object. All objects have attributes, and a lot of data manipulation happens through object methods. Every object has three fundamental components: its id, its data type, and its value. A useful metaphor here is to view an object as a box: the object’s id and type are like labels printed on the box, and the value is some piece of data that’s stored inside the box. In the past when we’ve talked about “values” in a Python program, we’ve really been talking about “objects that contain values”. And when we’ve talked about the data type of a particular value, we’re really been talking about the data type of the object that contains the value. (Reference: objects and object mutation |
Mutability, Objects | lab06 | |
| *what is the id of an object? | The id of an object is a unique int representation of the memory address of the object. we can access the id of an object using the built-in id function. (Reference: objects and object mutation) | Mutability, Objects | lab06 | |
| what is object-oriented programming? | Object-oriented programming (OOP) is a method of structuring a program by bundling related properties and behaviors into individual objects. Python is an OOP language. |
Mutability, Objects | lab06 | |
| Function VS Object | Functions do one thing; objects do many related things. | Mutability, Objects | lab06 | |
| what is class in Python? | Class is a type of object, and first-class value in Python(function is also first-class value in Python) | Mutability, Objects | lab06 | |
| Object mutation | In Python, object mutation (often shortened to just mutation) is an operation that changes the value of an existing object. The id and type of object cannot be changed after the object is created, but the thing contained in the box --its values-- can. (Reference: variable reassignment and object mutation | Mutability, Objects | lab06 | |
| * Difference between variable reassignment and object mutation | For example, we have my_list = [1, 2, 3], my_list = my_list + [4] is variable reassginment, while my_list.append(4) is object mutation. The object mutation version was “faster” because it didn’t need to create a copy of the new list. (Reference: variable reassignment and object mutation |
Mutability, Objects | lab06 | |
| Which data types are mutable or immutable? | 1. Data types int, float, bool, str, and collection data type tuple are all immutable. * For example, if we have an int object with value 3, that object’s value will always be 3. But remember, a variable that refers to this object might be reassigned to a different object later. This is why is is important that we differentiate between variables and objects. * Immutable values are protected from mutation. * An immutable sequence may still change if it contains a mutable value as an element. 2. The collection data types set, list, and dict are mutable. 3. Data classes are mutable by default. (Reference: mutable data types) |
Mutability, Objects | lab06 | |
| Why some data types are immutable? | By choosing to make some data types immutable, the Python programming language designers are then able to simplify the code for handling those data types in the Python interpreter, and in doing so make the remaining non-mutating operations less error-prone and more efficient. (Reference: mutable data types) | Mutability, Objects | lab06 | |
| Disadvantages of mutation | 1. Introducing mutation makes our code harder to reason about, as we need to track all changes to variable values line by line. 2. Mutable Default Arguments are Dangerous(Because a default argument value is part of a function value, not generated by a call) | Mutability, Objects | lab06 | |
| How to mutate list? | 1. list.append, list.insert, and list.extend; list.pop, list.remove; 2. list index assignment; 3. list augmented assignment; | Mutability, Objects | lab06 | |
| *How to mutate set? | set.add, set.discard,set.pop.set.remove | Mutability, Objects | lab06 | |
| *Tuple VS Set | 1. Tuple is Immutable, e.g. x = (1,2,3); 2. Set is mutable, e.g. y = {1,2,3}. |
Mutability, Objects | lab06 | |
| what is mutable function? | A Function with Behavior That Varies Over Time. | Mutability, Objects | lab06 | |
| what is an iterator? | A container can provide an iterator that provides access to its elements in order. * iter(iterable): Return an iterator over the elements of an iterable value* next(iterator): Return the next element in an iteratorAn iterator is returned from iter and can be passed to next. All iterators are mutable. It's useful for ensuring that each element of a sequence is processed only once. You can processes an iterator (via next) or iterable (via for or iter). |
Iterators, Containers | lab06 | |
| Iterable values | An iterable value is any value that can be passed to iter to produce an iterator. Data collection data types list, set, tuple, dictionary(its keys, values and items) are all iterable. | Iterators | lab06 | |
| built-in Python sequence operations that return iterators | map, filter, zip, reversed | Iterators | lab06 | |
| what is generator? | A generator is an iterator created automatically by calling a generator function. A generator function is a function that yields values instead of returning them. When a generator function is called, it returns a generator that iterates over its yields. Generators can yield from iterators or iterables. |
Generators | hw05 | |
How to evaluate a dot expression<expression>.<name> of objects? |
1. Evaluate the to the left of the dot, which yields the object of the dot expression 2. is matched against the instance attributes of that object; if an attribute with that name exists, its value is returned 3. If not, is looked up in the class, which yields a class attribute value 4. That value is returned unless it is a function, in which case a bound method is returned instead |
Objects | lab07, hw06 | |
| String representations for objects | In Python, all objects produce two string representations: 1. repr* The repr is legible to the Python interpreter* The result of calling repr on a value is what Python prints in an interactive session.2. str* The str is legible to humans * The result of calling repr on a value is what Python prints in an interactive session. |
Representation | ||
__repr__ and __str__ methods of objects |
__repr__ and __str__ are built-in for all objects in python, but the default representation possibly doesn't meet our needs. repr invokes a zero-argument method __repr__ on its argument, str invokes a zero-argument method __str__ on its argument. |
Representation | ||
| what is polymorphic function? | A function that applies to many (poly) different forms (morph) of data | Representation | ||
| What kinds of frames are active? | 1. Environments(frames) for any function calls currently being evaluated 2. Parent environments of functions named in active environments |
Efficiency | lab09 | |
| Scheme expressions | Scheme programs consist of expressions, which can be: 1. Primitive expressions 2. Combinations(A combination that is not a call expression is a special form) | Scheme, Functions, Interpreters | hw07, lab10, hw08 | |
| Machine language VS High-level language | Machine languages: statements are interpreted by the hardware itself • A fixed set of instructions invoke operations implemented by the circuitry of the central processing unit (CPU) • Operations refer to specific hardware memory addresses; no abstraction mechanisms High-level languages: statements & expressions are interpreted by another program or compiled (translated) into another language • Provide means of abstraction such as naming, function definition, and objects • Abstract away system details to be independent of hardware and operating system |
Calculator, Interpreters | lab11 | Scheme |
| How to create a new programming language? | A programming language has: * Syntax: The legal statements and expressions in the language * Semantics: The execution/evaluation rule for those statements and expressions To create a new programming language, you either need a: * Specification: A document describe the precise syntax and semantics of the language * Canonical Implementation: An interpreter or compiler for the language |
Calculator, Interpreters | lab11 | Scheme |
| What is parsing? | The task of parsing a language involves coercing a string representation of an expression to the expression itself(which means a Parser takes text and returns an expression). The parsing process consists of lexical analysis and syntactiv analysis. Lexical analysis: * Iterative process * Checks for malformed tokens * Determines types of tokens * Processes one line at a time Syntactic analysis: * Tree-recursive process * Balances parentheses * Returns tree structure * Processes multiple lines |
Calculator, Interpreters | lab11 | Scheme |
| Read-Eval-Print Loop of interpreter | The user interface for many programming languages is an interactive interpreter 1. Print a prompt 2. Read text input from the user 3. Parse the text input into an expression 4. Evaluate the expression 5. If any errors occur, report those errors, otherwise 6. Print the value of the expression and repeat |
Calculator, Interpreters | lab11 | Scheme |
| How to implement the "Eval" step? | Base cases: • Primitive values (numbers) • Look up values bound to symbols Recursive calls: • Eval(operator, operands) of call expressions • Apply(procedure, arguments) • Eval(sub-expressions) of special forms |
Interpreter | Scheme | |
| How to implement the "Apply" step during "Eval"? | Base cases: • Built-in primitive procedures Recursive calls: • Eval(body) of user-defined procedures |
Interpreter | Scheme | |
| What are functional programming? | 1. All functions are pure functions 2. No re-assignment and no mutable data types 3. Name-value bindings are permanent |
|||
| The advantage of tail call? | A call expression is not a tail call if more computation is still required in the calling procedure. The return value of the tail call is the return value of the current procedure call. Therefore, tail calls shouldn't increase the environment size. |
Tail calls | ||
| what are macros? | A macro is an operation performed on the source code of a program before evaluation. Macros exist in many languages, but are easiest to define correctly in a language like Lisp. | Macros | lab12, hw09 | |
| Evaluation procedure of a macro call expression | • Evaluate the operator sub-expression, which evaluates to a macro • Call the macro procedure on the operand expressions without evaluating them first • Evaluate the expression returned from the macro procedure |
Macros | lab12, hw09 |