:::warning Announcements - A6 due tonight - Quiz 2 grades back by Monday - Help hours today 3:45-5:15pm, L037 - CS Prof Tea @ 6pm ::: :::success Agenda for today - Course reflection - Gameplan for the final 1/3 of the course - More on interpreters - Reminder: functional vs. imperative - Interpreters for imperative languages ::: --- # Course reflection - Most people are happy with our mix of lecture/live coding/exercises. - Course difficulty: "just right" slightly beat out "too much". Trying to strike a balance across different experience levels, but give lots of practical programming practice. - The good: in-class exercises, the assignments - Some of my takeaways for improvement: - Pacing of the lectures/writing material - Some more example cases for assignments - Continuing to emphasize motivation/context - Organization of early material - first time teaching, really trying to focus on the most useful material - Tutor/TA - will have in the future, now that you all have taken 251 :D - Mostly, the group exercises are going well. But remember that we have a wide range of experiences in this course. Be good citizens of your group! Be supportive and make sure everyone is on board as you work on the problems. # Gameplan for the final 1/3 of the course Reminder of the goals of the course: :::success In this class, you will: - Gain a more accurate view on what programs actually mean. - Learn powerful programming language features—such as structural recursion, higher-order functions, and pattern matching—that will make you a stronger programmer across languages even beyond the two functional languages (Racket and OCaml) we will use. - Develop skills and strategies that will help you learn programming languages more quickly and effectively in the future. - Gain an appreciation for the expressive power of different programming language constructs. - Approach problem-solving through the lens of language design and program analysis. - Develop and apply skills for independent learning, critical thinking, and problem-solving as a self-reliant computer scientist. ::: At this point, we've accomplished one substantial goal: you've become proficient functional programmers! You've become much stronger at using recursion and decomposing problems into functional steps. You know how to think more deeply about the meaning of programming constructs. We've covered all of the key ingredients to functional programming, in two different styles: LISP-y with Racket, and ML-y with OCaml. We've also built an appreciation for the "principals" of programming languages, as the name of the course promises: syntax vs semantics, scope, type systems and their tradeoffs. In the remaining 1/3 of the course, we'll expand our focus out from the fundamentals of functional programming. Today, we'll think about interpreting languages that make different design decisions than Racket or OCaml--for example, imperative rather than functional languages. Assignment 7 will be another interpreter assignment (in OCaml). Next week, we'll focus on parallelism and concurrency, and think about how they expand our understanding of the meaning of a program beyond a sequential series of steps. This is also practical: most "real world" programs have to contend with parallelism to some extent. After that, we'll examine the principals of object-oriented programming (a la Java). We'll see how objects and subtyping bring up different interesting challenges in implementing type systems. You may think you know Java--you'll find that you may understand inheritance less than you expected! The final week of class, we'll discuss memory safety and memory management. I asked one of my friends, who's a senior software engineer at Apple, what he wished every new-grad engineer knew about programming languages. Understanding the stack vs the heap was one part of his answer, understanding memory management and the push toward memory safety was the other! This material is even newer/more experimental than other parts of this course, so we may have to change the game plan a bit as we go. --- # ASTs and interpreters for imperative languages We've now seen how to interpret (and type check) code using environments--dynamic in the case of interpretation, and static/type in the case of type checker. However, in both cases, we were considering functional languages. In a functional language, programs are bindings of _expressions_ to values. However, consider a Python program: ```python def find_x(ls, x, start, end): if start > end: print("oh no! bad start and end") return i = start while (i < end): if ls[i] == x: print(f"Found {x} in the list!") break # Exit the loop i += 1 ``` :::success How would we model this as an AST? In Racket or OCaml, functions are nested expressions. What would the outer-most expression be here? ::: Imperative language tend to make a distinction between _statements_ and _expressions_. - _expressions_, as before, evaluate to a value. Expressions can be recursively nested. - _statements_ are instructions that perform an action, rather than producing a value. For example, in imperative languages, the following are typically statements: - assignment to a variable - `if` statements - `return` statements - `while`/`for` statements - `break`/`continue` statements Statements and expressions can then both be recursively defined, with some statements containing expressions. For example, `(1 + (2 * 3))` is a recursively define expressions. `x = (1 + (2 * 3))` is a statement (assignment to variable `x`). Note that in OCaml, we would write this as something like `let x = (1 + (2 * 3)) in BODY` if it was a local binding. This is an expression, not a statement. In the top-level, `let x = (1 + (2 * 3))` in OCaml is a closer analogy to imperative languages, but the execution model is still a series of bindings, rather than statements done for their side effects. If we were defining this as part of an AST definition in OCaml, we could write: ```ocaml type expr = | ... type stmt = | Asgn of string * expr ``` In more full-fledged language definitions, this would actually be something like: ```ocaml= type stmt = | Asgn of lvar * expr ``` Where an `LVar` is a left-hand side destination used in an assignment. --- :::success Take a minute and write down examples of `lvar`s in Python that are *not* just a variable name. ::: - Assigning to a field `student.id = 5` - Assigning a value to dictionary at a key `dict[k] = v` - Assigning to an array `l[0] = 5` For the next assignment, we'll just assign to variables for simplicity. --- `return` is also a statement: ```ocaml= type stmt = | Ret of expr ``` Or, if we don't want to say `return` is syntactic sugar for `return None`, we can represent this as: ```ocaml= type stmt = | Ret of expr option ``` # Group exercise :::success Design an OCaml AST for the remaining forms required by this Python snippet. Think about which places should be `expr` and which should be `stmt`. There is more than 1 reasonable answer. Your answer should include `type expr = ...` and `type stmt = ...`, and can also include additional type definitions if you find them useful. ::: ```python def find_x(ls, x, start, end): if start > end: print("oh no! bad start and end") return i = start while (i < end): if ls[i] == x: print(f"Found {x} in the list!") break # Exit the loop i += 1 ``` ## One possible solution ```ocaml= (* One possible solution *) type binop = | Add | Sub | Lt | Gt | Eq type expr = | Int of int | Bool of bool | Var of string | BinOp of binop * expr * expr | Call of string * expr list type stmt = | Assign of string * expr | AssignIndex of expr * expr * expr (* ls[i] = x *) | If of expr * stmt list * stmt list | While of expr * stmt list | Expr of expr | Break | Return of expr option | Def of string * string list * stmt list | Pass ``` In the prior solution, we used `stmt list` anywhere we had multiple statements. We could also separate this out as a `Block` or `Seq` statement (this is closer to the OCaml way of thinking about `;`). ```ocaml type stmt = | Assign of string * expr | AssignIndex of expr * expr * expr (* ls[i] = x *) | If of expr * stmt * stmt (* Instead of stmt list, we use Block *) | While of expr * stmt | Expr of expr | Break | Return of expr option | Def of string * string list * stmt | Pass | Block of stmt list (* Explicit block of statements *) ``` In this second solution, the interpreter can define how to evaluate a sequence of statements once, then share it elsewhere. The interpreter could also accomplish this via a helper function in each location. `Block` wraps a `stmt list`. Other, more function representations might use a `Seq of stmt * stmt` to represent `;`, where `Seq` essentially forms a linked-list across a chain of `;` uses. ## Control flow Imperative programming constructs can be more difficult to reason about (even without mutation!) due to more complex *control flow*. *control flow* refers to what statement we execute next in a program. :::success Recall: If I have a loop like this, what statement executes after `break`? ```python A while (x) B break C D ``` ::: Answer: `D` :::success If I have a loop like this, what statement executes after `continue`? ```python A while (x) B continue C D ``` ::: Answer: `B` (or `D`! depends on the while loop condition `x`). The statements `break` and `continue` modify the flow of control in loops. The `continue` skips the remainder of the current loop iteration and proceeds with the next iteration, while the `break` command terminates the loop and proceeds with the next command after the loop. A `break` or `continue` outside of the body of a loop is a dynamic error. ## Implementing control flow There are several options for implementing imperative loops structures with break and continue inside an interpreter. ### Less pretty: exceptions One option is to use the host language support for non-local control flow (exceptions!) if the language has it. This is a bit uglier, since it's using exceptions for non-erroneous program conditions. The alternative is much nicer! # Continuations Another option is to use an idea called _continuations_. A continuation describes "the rest of the computation" at a particular point in the program. _Continuations_ have close connections to practical programming constructs, such as callbacks in web-based programming. `break` and `continue` indicate that a program should _choose a different continuation_. An interpreter can implement `break` and `continue` using continuations by having `interp` carry along more information as it recurs. (A simple recursive descent interpreter/type checker that passes along just an environment, as we used for A3 and A5, cannot support `break` and `continue`!). For example, in A7, you'll work on an interpreter for a simple, dynamically-typed imperative language where `interp_stmt` takes the following arguments: ``` (e : env) (* The dynamic environment *) (curr : stmt) (* The current statement to be executed *) (next : stmt) (* The continuation under normal control flow *) (conts: (stmt * stmt) list) (* A list of continuations for break/continue, respectively *) ``` The continuations for `break` and `continue` are stored in a list to support nested `while` loops. More on this in A7!