Course:CPSC311/2013WT1/Lecture Notes

This goal of this page is to consolidate all of the learning goals and other sections of the lecture notes into a single document. All the material here comes directly from the files uploaded by the instructor in the notes sections of the webpage found here: http://www.ugrad.cs.ubc.ca/~cs311/current/_notes.php

Please warn the reader if any of the information being uploaded is significantly paraphrased/reformatted or not directly from the lecture notes. Also provide the source of the information as either a file name or hyperlink.

Lecture 1 - Intro

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture1.pdf

Learning Goals

• Desugaring
  • Define the PL term "desugaring"
  • Recognize desugaring in an example

• Semantics
  • Define the PL term "semantics"
  • Distinguish between syntactic and semantic issues in a programming-language
  • Illustrate how the semantics of syntactically similar constructs can differ

• Static and Dynamic
  • Define the PL terms "static" and "dynamic"
  • Distinguish between static and dynamic properties of a program given information about how information about those properties is determined (stored and/or computed)

• Dispatching
  • Define the PL term "dispatching" (with respect to function calls)

Lecture 2 - Concrete Syntax, Abstract Syntax, and Parsing

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture2.pdf

Question of the Day

You have a collection of associations: names and values. For example, the variables in a function. Given a name, you want to find and/or set its value. What are some fast ways to do it?

See notes for solution

Learning Goals

• Question of the Day
  • Define the term "environment": a program's mapping from identifiers (names) to values.
    • Later on we'll look at how different program analyses can make use of environments that map identifiers to other quantities.
  • Compare and contrast static and dynamic solutions to a program.
    • Statically and dynamically mapping identifiers to values.
  • Discriminate among concepts that impact the semantics of a program and those that do not.
    • The form we use to implement a program's environment does not necessairly have any semantic effect.
    • Use of hash tables, unordered association lists, and static replacement of identifiers with addresses (used appropriately) all produce programs with the same meaning.

• Syntax and Parsers
  • Define the terms "concrete syntax", "abstract syntax", "abstract syntax tree", and "parser".
  • Translate among:
    • 1. Concrete syntaxes that you've studied explicitly or reasonably natural new concrete syntaxes.
    • 2. A provided abstract syntax.
    • 3. Sketched tree representations.
  • Given a syntax, determine what purpose it might be best suited to, and justify your answer.
  • Design and understand simple parsers for given concrete/abstract syntaxes.

• EBNF
  • Roughly define the term EBNF.
    • Extended Backus Naur Form.
    • A standard language for describing syntaxes.
  • Given the EBNF for a language:
    • 1. Determine whether some small snippets of code are legal syntax.
    • 2. Write some small snippets of code.
  • Give a desired modification to a language and an EBNF, modify the EBNF to describe the new language.

Lecture 3 - Interpreters, Expressions/ASTs, and Values

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture3.pdf

Question of the Day

What language is your {Racket, Java, C} {compiler, interpreter} written in?

See notes for solution

Learning Goals

• Question of the Day
  • Steve likes to ask QotDs

• Interpreters and Values
  • Define the terms: value and evaluate.
  • Describe the job of an interpreter in terms of expressions, values, and evaluation
  • Explain with an example how a single concrete syntax can have multiple different semantics
  • Modify an existing interpreter to support a small change to one or more of the semantics, abstract syntax, and values that it operates on.

Lecture 4 - Catch-up

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture4.pdf

Question of the Day

Which of these is a function in Racket: / (division) or and (logical "and")?

See notes for solution

Learning Goals

There was no new material here except the QotD, Quiz, and Logistics.

• Question of the Day
  • More on the definition/application of the term semantics.
    • The semantics of function application in Racket includes the idea that argument expressions are evaluate to values before the function is called.
    • Therefore a "short-circuit and" cannot be written as a function, at least not with the type (boolean boolean -> boolean).

Lecture 5 - Scary Catch-up

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture5.pdf

Question of the Day

From Erik: Why does (s-exp-list? "hello) evaluate to true?

No solution

Learning Goals

• Question of the Day
  • More reinforcing of what syntactic sugar and desugaring are.
  • What desugaring means to the programmer and programming language designer.

Lecture 6 - Desugaring

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture6.pdf

Learning Goals

• distinction between 'static' and 'dynamic'
• explain the relationship of a desugarer to the parser and interpreter
• justify the use of desugaring on various grounds
  • its impact on the programmer's interfaces
  • the languages implementation's complexity
  • the tractability (doableness) of useful reasoning over the language
  • and the software engineering advantages of isolating components of the interpreter system
• extend a surface language over an existing core language using a desugarer

Why Desugar?

• allows us to build different surface languages atop a single core
• may make either the program or the interpreter faster
• better grasp of semantics in 'leaner' core language
• separation of concerns: don't worry simultaneously about user interface needs and language design needs
• customize the language to the domain at hand
• simpler maintenance for core language
• keep the same surface syntax but improve the underlying language (backwards compatibility)

More...

• present the programmer with a 'friendlier' interface
• reduce a complex language to a simpler one to make our language implementation job easier
• reduce a complex language to a simple core to make it easier to reason about the core
  • security
  • correctness
  • resource use
• add desired features to the language without complicating its implementation

Lecture 7 - Functions Intro

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture7.pdf

Learning Goals

• Explain in context four of the key features of a function
  • delaying evaluation of the function body
  • allowing evaluation of the function body from (possibly distant) locations in the program
  • blocking out bindings from the function's dynamic context
  • "allowing in" a dynamic value via the parameters

• Formal parameters vs. actual parameters
  • distinguish between formal and actual parameters
    • formal parameters are the names give to argument values within the function
    • actual parameters are the argument expressions whose values (under eager evaluation) are bound to the formal parameters
  • identify formal and actual parameters in context

• Function calls vs function definitions
  • distinguish between a function call (aka function 'application') and a function 'definition'
    • a function call is application of a previously defined function to actual parameters, which causes the function body to be evaluated.
    • a function definition creates a function (prepares it to be used) with formal parameters and a body but does not evaluate the body yet
  • identify function calls and definitions in context

• Bound vs unbound identifiers
  • define bound and unbound identifier, including illustrating their meanings with examples
  • identify bound and unbound identifiers in context
  • define scope with respect to identifier
    • the scope of an identifier's binding is the protion of the program in which that binding is visible. In Racket, bindings use lexical (aka static) scope. However, Racket does have a facility for something like dynamic scope.

• Eager evaluation vs lazy evaluation
  • Explain the basic different between lazy and eager evaluation.
    • in lazy evaluation, actual parameters are not evaluated before proceeding with a function call. Formal parameters are bound to the actual parameter expressions, not their values.
    • in eager evaluation, actual parameters are evaluated prior to proceeding with a function call, and the function's formal parameters are bound to the resulting values.
  • be able to distinguish between lazy and eager evaluation regimes by evaluating (and possibly providing a test case that behaves differently under the two regimes
  • alter existing substitution and interpreter code to switch back and forth between lazy and eager evaluation regimes

Function Test Cases

What happens...

• in 'normal' cases where we call a natural*seeming function and it does its thing
• when a function calls another function
• when a function calls itself (requires conditionals)
• when a function does not use its parameters
• when a function uses its parameter twice (how can we tell?)
  • look for multiple references to the identifier. it will always have one binding site where it's defined, but it may be referenced multiple times
• when a function's 'actual parameter' is an identifier
• when we try to use an identifier that is not bound anywhere
• when we try to use an identifier that's bound in the function that calls the current function
  • if this is allowed, it means our language has dynamic scope for identifiers. in other words, an identifier binding made in a particular part of the program may be used in a totally unrelated part of the program just because this part of the program calls a function in that part (or calls a function that calls a function that....
• how could we tell the different between lazy and eager evaluation semantics? can we teset for the appropriate semantics? what do we need to be able to do such a test?

Lecture 8 - Functions Intro Continued

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture8.pdf

Question of the Day

Imagine a world without functions (or other control flow structures allowing repetition, like loops or "jumps"). If every programming in the world worked on a single program for a year, how long would it take to run on my laptop?

No solution

Learning Goals

• Question of the Day
  • Control flow matters!

Lecture 9 - Environments

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture9.pdf

Question of the Day

Haskell is probably the most prominent programming language that uses lazy evaluation. And it's used lots of places, right? Seriously, does anything actually use lazy evaluation? (Hint: Try running man yes from a UNIX prompt)

See notes for solution

Learning Goals

• Question of the Day
  • A bit of what lazy evaluation can be good for:
    • Chaining together processes (including infinite ones!) in a demand-driven way.

Lecture 10 - Functions and Environments Continued

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture10.pdf

Question of the Day

Why should I care about Programming languages? The spam botnet administrator edition: http://www.youtube.com/watch?v=ILOtIMShi9s

No solution

Learning Goals

• Question of the Day
  • Why functional programming is so great. Although it's not as good as a language based on General Abstract Nonsense.

Lecture 11 - Functions and Environments Continued

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture11.pdf

Question of the Day

Which song should Steve sing?

• The one that gives away what's not_so_hidden by a famous CSist Steve doesn't know personally?
• The one about ML (a functional programming language) by grad school friends of Steve's?

No solution

Learning Goals

• Question of the Day
  • Why faculty keep their day jobs.

Lecture 20 - Mutable State: Three Flows and Boxes

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture20.pdf

Question of the Day

What does the abstract syntax tree for this program look like?

(let-rec ((f (lambda (n) (if (= n 0) 1 (f (sub1 n )))))) (f 2))

See notes for solution

Learning Goals

• Question of the Day
  • Draw the abstract syntax tree for a program
  • Draw the function call tree for a program
  • Identify how values and the store flow through the function call tree
  • Explain why it's difficult to show how values/store flow through the AST
  • Explain how the environment can be understood both in terms of:
    • The AST and its "shape" (the identifiers bound at a given point)
    • The function call tree in its values

Practice Exercises

• Imagine we wanted to introduce something sort of halfway between let and set!. We'll call it sleet. In a language that other has static scoping, (sleet id value-expr body-expr) introduces a new dynamic binding for id. If a static binding for id alread exists in the current scope, that produces an error. If a dynamic binding already exists, this sleet shadows it. (We'll assume we cannot use set! on sleet-bound variables.) An id reference will always be to a static binding if one exists; otherwise, it will find dynamic (sleet) bindings.
  • Use a core language with sleet to desugar (deffun name funbody body), and discuss why it's easier than with let.
  • Imagine implementing sleet by passing two environments into interp, static-env and dynamic-env. Implement the appC, funcC, and idC cases for the interpreter, being sure to manage the two separate environments correctly. (Do closures need one environment or two??)
  • Describe any concerns you have about sleet' from a software engineering perspective.
• Implement a new syntactic form incr! that takes a variable and adds one to its value.
• Implement a new syntactic form time-maximum that evaluates to the largest values a variable has ever contained. Discuss whether we could incorporate this into a mainstream language. (Could we do it with desugaring rather than changing the underlying language?)
• Implement a new syntactic form count-bindings. It takes a single argument (a symbol) and evaluates to the number of bindings that symbol presently has in the environment. (More than 1 if there's both a binding and at least one shadowed binding)
• Create multiple-argument functions and applications in a surface language by desugaring them to one-argument functions and applications in the core.
• Assume you have a language with multiple-argument function definitions and applications as well as lists (cons, first, rest, and empty?) in the core. Implement a new core form apply that takes a function expression and an argument list expression, checks that they evaluate to the appropriate types (function value and list), and then applies the function to the list of arguments. apply should give an arity (ie number of arguments) error if the length of the list of arguments does not match the length of the list of parameters for the function.
  • Now, desugar as much of this as you can to a core that has only single-argument function definition and application. Discuss why the arity check, in particular, is very hard to manage in the desugaring. (Hint: when you apply a "two-argument function" to just one argument in this desugaring, the natural result is to get a function back waiting for the second arguments. Is such a value illegal or unreasonable as a "normal value" in a language with first-class functions?)

Lecture 23 - Mutable State: Variables and Pass-by-Reference

http://www.ugrad.cs.ubc.ca/~cs311/current/slides/2013W1-lecture23.pdf

Question of the Day

Continuing our big sequences of questions about state!

No solution

Learning Goals

• Pass-by-reference
  • Explain what pass-by-reference semantics means in a language.
  • Implement pass-by-reference semantics in a language (by desugaring or direct implementation)
  • Explain what restrictions there are on the actual parameter expressions when an actual parameter is passed by reference
  • Compare and contrast pass-by-value and pass-by-reference, including specifically identifying the one major different between them.
    • In pass-by-reference, directly mutating the formal parameter has an impact on the actual paramter.
    • "Indirect" mutation (mutations on a store location referred to in the value of the formal parameter) behaves the same for both

Practice Exercises

• Implement pass-by-reference semantics directly in the interpreter instead of in the desugarer
• Create a new ref-let construct that creates a "reference variable". The "binding expression" for the ref-let must be a syntactic identifier, and the ref-let aliases the new reference variables with this other variable (It does not create a new store location but reuses the one used by the other variable)
  • In C++, pass-by-reference semantics are actually accomplished through a type modifier that creates reference types. Reference types are initialized as with ref-let. Yet, it hardly seems worth bothering the have ref-let, since it just lets us refer to the same variable by more than one name.
    • Much more than just variables can appear on the left-hand-side of an assignment operator. Expressions like *x, array[3], or object.field can appear on the left of an assignment. Justify the existence of reference variables (ie. ref-let) given this fact.
    • Second, C++ even allows a function call to appear on the left side of an assignment operator as in call() = 5;. What do you think the type of the return value of call must be to make this work?

Lecture 27 - Continuations

Learning Goals

• Continuations
  • Justify the utility of grabbing everything that has to happen after the current evaluation finishes in a program?
    • For a callback: as in web programming.
  • Express the continuation of a particular program point as a function (to the extent that that's possible), an English description, and a portion of the runtime call tree.

• ˆ Continuation-Passing Style
  • Define tail call/tail position
    • A tail call is a function call (e.g., a call to interp) that represents all work remaining to be done in evaluating the current expression.
    • Evaluation of an expression in tail position within a syntactic form is always a tail call. (Note: sometimes a syntactic form has multiple of these, as in if expressions! Sometimes an expression will have no tail position, as in display.)
  • Define continuation-passing style
    • A program with the invariant that every (non-trivial, for some appropriate definition of non-trivial) computation is in tail position and where each non-trivial computation consumes a continuation: a function which, given the value of the cur-rent computation, performs all computations after the current computation.
  • Convert a simple program into continuation-passing style.

ˆ

• Converting an interpreter to CPS
  • Given an implementation of a case in an interpreter, convert it to continuation-passing style.
  • Explain the advantage of having an interpreter implemented in continuation-passing style.
  • Implement a simple control-flow construct using an interpreter in CPS (possibly by desugaring to let/cc and equivalent operations).

Last Lecture

Learning Goals

• Demonstrate by completing an example how continuations can be used to store and restart computations to accomplish interesting computational goals.
• Understand the syntax of the Racket let/cc primitive that lets us bind a continuation to a name.
• Explain the funcionality of let/cc in terms of our CPS interpreter implementation.