# Photos from Lecture

There is a shared album with photos of lecture. Anybody can add photos.

# 16 January 2019: Introduction to Comp 105

There are PDF slides for 1/17/2019.

Handout: Experiences of successful 105 students

Handout: Lessons in program design

Handout: **Homework** (photograph, due Jan 22)

Handout: **Homework** (Impcore, due Jan 29)

There will be a shared album with photos of lecture. Anybody can add photos.

### Introduction

My pronouns are he, him, his.

Please call me “Norman,” “Professor Ramsey,” or “Mr Ramsey”

## Why we are here

- Write code from scratch
- In a language you’ve never seen
- That sails past code review

What it involves:

- Programming practice (emphasize widely used features: functions, types, modules, objects)
- Mathematical description (how things work, see patterns)

(Example: see patterns of recursion in homework)

Today:

- Start with technical work
- Then a little about experience and expectations

## What is a programming language?

What is a PL? Think. Then pair. Then share.

First three classes: new ways of thinking about stuff you already know

### Syntactic structure: induction

#### Numerals

Show some example numerals

Numerals:

```
2018
73
1852
```

Not numerals:

```
3l1t3
2+2
-12
```

**Q:** What does a numeral stand for?

That is, if a numeral appears in the syntax, what sort of value flies around at run time?

**Q:** Does every numeral stand for one of these things?

**Q:** How many of them are there?

**Q:** How many numerals are there?

##### In-class Exercise: Inductive definitions of numerals

Write an inductive definition of numerals

There is more than one! When you finish one, look for another

### Value structure: induction again

In-class exercise: inductive definition of natural number

- Again, there is more than one
- What makes it easy to know meaning of numerals?

## Writing code with recursion and induction

Data-driven design process. Connections to design ideas from 1970s, 1980s, 1990s, plus test-driven development (2000s).

## Syntax in programming languages

### Concrete Syntax

Programming-languages people are wild about **compositionality**.

Build sensible things from sensible pieces using just a few construction principles.

Example: expressions,

*e*_{1}+*e*_{2}

### Syntactic structure of Impcore

Watch for syntactic categories, syntactic composition

### Live coding in Impcore

Try `square`

function. E.g., `(square (+ 2 2))`

# 23 January 2019: Abstract syntax and operational semantics

There are PDF slides for 1/24/2019.

Handout: 105 Impcore Semantics, Part 1

## Live coding: Impcore

All fours, tests, big literals

`square`

, `negated`

, interactive `check-expect`

## Review: algebraic laws

## Approaching 105

100-level course

Responsibility for your own learning: lecture is the tip of the iceberg

Announcement: Syllabus scavenger hunt (participation grades)

Systematic programming process: we can’t observe process, but it will affect your time spent by a factor of 2, 3, or 4.

*Awareness* of your own learning: **Metacognition**

### Office hours

Students: go to office hours! An idle TA is an unhappy TA.

## Review

**Short discussion**: *One thing you learned in the first class*

Language: syntax, rules/organization/grammar

*Programming* language: you can run it (values)

## Preparing for a language you’ve never seen before

You need a vocabulary. It will involve math.

This week: abstract syntax and operational semantics (next homework)

### Concrete and abstract Syntax

Programming-languages people are wild about **compositionality**.

- Build sensible things from sensible pieces using just a few construction principles.

Example of compositionality: **concrete syntax** (grammar)

- How many different kinds of things can be composed:
*syntactic categories*

```
C/C++ Impcore
Compute w/ existing names
- value and behavior exp exp
- just behavior stm
Add new names to program
- initialized def def
- uninitialized decl
```

Example rules of composition:

C/C++: expressions, definitions, statements

Impcore

## Programming-language semantics

“Semantics” means “meaning.”

We want a *computational* notion of meaning.

**What problem are we trying to solve?**

Know

what’s supposed to happen when you run the code

Ways of knowing:

*People*learn from examples- You can build intuition from words

(Book is full of examples and words) - To know
*exactly*,*unambiguously*, you need more precision

(For homework, you’ll prove that our specification is unambiguous.)

### Why bother with precise semantics?

(Needed to build implementation, tests)

Same reason as other forms of math:

- Distill down your understanding and express it
- Prove properties people care about (e.g., private information doesn’t leak; device driver can’t bring kernel down)
- Most important for you:
*things that look different are actually the same*

The programming languages you encounter after 105 will certainly look different from what we study this term. But most of them will actually be the same. Studying semantics helps you identify that.

The idea: **your new skills will apply**

### Behavior decomposes

What happens when we run

`(* y 3)`

?

We must know something about `*`

, `y`

, 3, and function application.

**Knowledge is expressed inductively**

Atomic forms: Describe behavior directly (e.g., constants, variables)

Compound forms: Behavior specified by composing behaviors of parts

### ASTs

Question: What do we assign behavior to?

Answer: The **Abstract Syntax Tree (AST)** of the program.

An AST is a

*data structure*that represents a program.A

*parser*converts program text into an AST.

Question: How can we represent all while loops?

`while (i < n && a[i] < x) { i++ }`

Answer:

- Tag code as a while loop
- Identify the condition, which can be any expression
- Identify the body, which can be any expression

As a data structure:

- WHILEX(exp1, exp2), where
- exp1 is the representation of (i < n && a[i] < x), and
- exp2 is the representation of i++

## Key question: names (review)

### From ASTs to behaviors

# 28 January 2019: Judgments and Rules

There are PDF slides for 1/29/2019.

**Students: Take a blank white card**

Handout: Redacted Impcore rules

Today:

How do we know what happens when we run the code?

- Judgment
- Rules
**Valid derivations**

What can we prove about it?

**Metatheory**

## Review: environments

## Rules and metatheory

Review: **What elements are needed to know run-time behavior?**

**OK, your turn:** what do you think is rule for evaluating literal, variable? (Base cases)

## Good and bad judgments

## Proofs: Putting rules together

Every terminating computation is described by a data structure—we’re going to turn computation into a data structure: a tree. Proofs about computations are hard (see: COMP 170), but proofs about trees are lots easier (see: COMP 61).

Code example

```
(define and (p q)
(if p q 0))
(define digit? (n)
(and (<= 0 n) (< n 10)))
```

Suppose we evaluate `(digit? 7)`

**Exercise**:

In the body of

`digit?`

, what expressions are evaluated in what order?As a function application, the body matches template

`(`

*f**e*_{1}*e*_{2}`)`

. In this example,- What is
*f*? - What is
*e*_{1}? - What is
*e*_{2}?

- What is

Let’s develop the ApplyUser rule for the special case of two arguments: ⟨*A**P**P**L**Y*(*f*, *e*_{1}, *e*_{2}), *ξ*, *ϕ*, *ρ*⟩ ⇓ ?

What is the result of `(digit? 7)`

?

How do we know it’s right?

## From rules to proofs

### Building a derivation

### Building derivations

# 30 January 2019: Derivations, metatheory, better semantics

There are PDF slides for 1/31/2019.

## Review: calls

## Review: Derivations

### Building a derivation

### Building derivations

## Proofs about derivations: metatheory

Cases to try:

- Literal
- GlobalVar
- SetGlobal
- IfTrue
- ApplyUser2

For your homework, “Theory Impcore” leaves out While and Begin rules.

# 4 February 2019: Scheme

There are PDF slides for 2/5/2019.

### Announcements

Note: course not graded on a curve

Scheme homework:

- ramp-up
- not frightfully hard concepts, but…
- new language (notable load)

## Where are we going?

Recursion and composition:

Recursive functions in depth

Two recursive data structures: the list and the S-expression

More powerful ways of putting functions together (compositionality again, and it leads to reuse)

Today: **programming with lists and S-expressions** (around laws)

## For a new language, five powerful questions

As a lens for understanding, you can ask these questions about any language:

**What is the abstract syntax?**What are the syntactic categories, and what are the forms in each category?**What are the values?**What do expressions/terms evaluate to?**What environments are there?**That is, what can names stand for?**How are terms evaluated?**What are the judgments? What are the evaluation rules?**What’s in the initial basis?**Primitives and otherwise, what is built in?

(Initial basis for *μ*Scheme on page 159)

## Introduction to Scheme

Two new kinds of data:

The function closure: the key to “first-class” functions

Pointer to automatically managed cons cell (mother of civilization)

### Scheme Values

Most values are *S-expressions*.

An *fully general S-expression* is one of

a

**symbol**`'Halligan`

`'tufts`

a

**literal integer**`0`

`77`

a

**literal Boolean**`#t`

`#f`

`(cons`

*v*_{1}*v*_{2}`)`

, where*v*_{1}and*v*_{2}are S-expressions

Many predefined functions work with a **list of S-expressions**

A list of S-expressions is either

the empty list

`'()`

`(cons`

*v**v**s*`)`

, where*v*is an S-expression and*v**s*is a list of S-expressionsWe say “an S-expression

*followed by*a list of S-expressions”

## Programming with lists and S-expressions

### Lists: A subset of S-Expressions.

Can be defined via a recursion equation or by inference rules:

**Constructors**: `'(),`

cons

**Observers**: `null?`

, `pair?`

, `car`

, `cdr`

(also known as “first” and “rest”, “head” and “tail”, and many other names)

**Any** list is therefore *constructed* with `'()`

or with `cons`

applied to an atom and a smaller list.

- How can you tell the difference between these types of lists?
- What, therefore, is the structure of a function that consumes a list?

### Why are lists useful?

Sequences a frequently used abstraction

Can easily approximate a set

Can implement finite maps with

**association lists**(aka dictionaries)You don’t have to manage memory

These “cheap and cheerful” representations are less efficient than balanced search trees, but are very easy to implement and work with—see the book.

The only thing new here is **automatic memory management**. Everything else you could do in C. (You can have automatic memory management in C as well.)

### Programming example: lists of numbers

Problem-solving: students pose problem on list of numbers

- Live coding: detect duplicate elements

*μ*Scheme’s new syntax

### Immutable data structures

Key idea of functional programming: **constructed data**. Instead of mutating, construct a new one. Supports composition, backtracking, parallelism, shared state.

### List-design shortcuts

Three forms of “followed by”

**Given:**Element .. list of values =`(cons x xs)`

**Define:**List of values .. list of values =`(append xs ys)`

**Ignore:**List of values .. element =`(snoc xs y)`

Or`(append xs (list1 y))`

Two lists? Four cases!

Using informal math notation with .. for “followed by” and e for the empty sequence, we have these laws:

```
xs .. e = xs
e .. ys = ys
(z .. zs) .. ys = z .. (zs .. ys)
xs .. (y .. ys) = (xs .. y) .. ys
```

The underlying operations are `append`

, `cons`

, and `snoc.`

Which ..’s are which?

But we have no

`snoc`

If we cross out the

`snoc`

law, we are left with three cases… but case analysis on the first argument is complete.So cross out the law

`xs .. e == xs`

.Which rules look useful for writing append?

You fill in these right-hand sides:

```
(append '() ys) ==
(append (cons z zs) ys) ==
```

Why does it terminate?

### Cost model

The major cost center is `cons`

because it corresponds to **allocation**.

How many cons cells are allocated?

Let’s rigorously explore the cost of append.

### Induction Principle for List(A)

Suppose I can prove two things:

IH (’())

Whenever a in A and also IH(as), then IH (cons a as)

then I can conclude

Forall as in List(A), IH(as)

*Claim*: Cost (append xs ys) = (length xs)

*Proof*: By induction on the structure of xs.

Base case: xs = ’()

I am not allowed to make any assumptions.

`(append '() ys) = { because xs is null } ys`

Nothing has been allocated, cost is zero

`(length xs)`

is also zero.Therefore, cost =

`(length xs)`

.

Inductive case: xs = (cons z zs)

I am allowed to assume the inductive hypothesis for

`zs`

.Therefore, I may assume the number of cons cells allocated by

`(append zs ys)`

equals`(length zs)`

Now, the code:

`(append (cons z zs) ys) = { because first argument is not null } = { because (car xs) = z } = { because (cdr xs) = zs } (cons z (append zs ys))`

The number of cons cells allocated is 1 + the number of cells allocated by

`(append zs ys)`

.`cost of (append xs ys) = { reading the code } 1 + cost of (append zs ys) = { induction hypothesis } 1 + (length zs) = { algebraic law for length } (length (cons z zs)) = { definition of xs } (length xs)`

Conclusion: Cost of append is linear in length of first argument.

## Costs of list reversal

Algebraic laws for list reversal:

```
reverse '() = '()
reverse (x .. xs) = reverse xs .. reverse '(x) = reverse xs .. '(x)
```

And the code?

The `list1`

function maps an atom `x`

to the singleton list containing `x`

.

How many cons cells are allocated? Let’s let `n = |xs|`

.

- Q: How many calls to
`reverse`

? A:`n`

- Q: How many calls to
`append`

? A:`n`

- Q: How long a list is passed to
`reverse`

? A:`n-1`

,`n-2`

, … ,`0`

- Q: How long a list is passed as first argument to
`append`

? A:`n-1`

,`n-2`

, … ,`0`

- Q: How many
`cons`

cells are allocated by call to`list1`

? A: one per call to`reverse`

. - Conclusion:
*O*(*n*^{2}) cons cells allocated. (**We could prove it by induction**.)

## The method of accumulating parameters

Write laws for

`(revapp xs ys) = (append (reverse xs) ys)`

**Who could write the code?**

The cost of this version is linear in the length of the list being reversed.

Parameter `ys`

is the **accumulating parameter**.

(A powerful, general technique.)

## Association lists represent finite maps (code not to be covered in class)

Implementation: list of key-value pairs

`'((k1 v1) (k2 v2) ... (kn vn))`

Picture with spine of cons cells, `car`

, `cdar`

, `caar`

, `cadar`

.

Notes:

- attribute can be a list or any other value
- ‘nil’ stands for ‘not found’

### Algebraic laws of association lists

# 6 Feb 2019: First-class and higher-order functions

There are PDF slides for 2/7/2019.

## Skills refresh

## Where we’ve been and where we’re going: Functional programming

Last time: new data forms (lists, S-expressions)

Today: New syntax, its rules and values

Context: Techniques and features we’re learning fit under **functional programming**.

- Idea: reuse more code because of “better glue”

Already doing it: immutable data (`append`

)

- Always safe to share data (I can’t mess up things for you)
- Perfect for parallel/distributed (think Erlang)
- Perfect for web (JSON, XML)

Next up: better ways of gluing functions together

*μ*Scheme’s semantics

It’s not precisely true that rho never changes.

New variables are added when they come into scope.

Old variables are deleted when they go out of scope.

But the location associated with a variable never changes.

### New syntax exploits semantics

Evaluate `e1`

through `en`

, bind answers to `x1`

, … `xn`

- Name intermediate results (simpler code, less error prone)
Creates new environment for local use only:

`rho {x1 |-> v1, ..., xn |-> vn}`

Also `let*`

(one at a time) and `letrec`

(local recursive functions)

Note that **we would love to have definititions** and it might be easier to read if McCarthy had actually used definition syntax, which you’ll see in ML, Haskell, and other functional languages:

So let’s see that semantics!

Key idea: **don’t worry about memory**

## From Impcore to uScheme: Lambda

### Anonymous, first-class functions

From Church’s lambda-calculus:

`(lambda (x) (+ x x))`

“The function that maps x to x plus x”

At top level, like `define`

. (Or more accurately, `define`

is a synonym for `lambda`

that also gives the `lambda`

a name.)

In general, `\x.E`

or `(lambda (x) E)`

`x`

is**bound**in`E`

- other variables are
**free**in`E`

The ability to “capture” free variables is what makes it interesting.

Functions become just like any other value.

### First-class, *nested* functions

`(lambda (x) (+ x y)) ; means what??`

What matters is that `y`

can be a parameter or a let-bound variable of an *enclosing* function.

- Can tell at compile time what is captured.
- To understand why anyone cares, you’ll need examples

**First example**: Finding roots. Given n and k, find an x such that x^n = k.

*Step 1*: Write a function that computes x^n - k.

*Step 2*: Write a function that finds a zero between `lo`

and `hi`

bounds.

Picture of zero-finding function. Algorithm uses binary search over integer interval between `lo`

and `hi`

. Finds point in that interval in which function is closest to zero.

Code that computes *the function* `x^n - k`

given `n`

and `k`

:

The function `to-the-n-minus-k`

is a *higher-order function* because it **returns another (escaping) function as a result**.

General purpose zero-finder that works for any function `f`

:

`findzero-between`

is also a higher-order function because it takes another function as an argument. But nothing escapes; you can do this in C.

Example uses:

### Your turn!!

## How `lambda`

works

### Rule for `lambda`

Key idea: ``every name I can see—remember where it is stored.’’

### Rule for function Application

Questions about ApplyClosure:

What if we used

*σ*instead of*σ*_{0}in evaluation of*e*_{1}?What if we used

*σ*instead of*σ*_{0}in evaluation of arguments?What if we used

*ρ*_{c}instead of*ρ*in evaluation of arguments?What if we did not require ℓ

_{1}, ℓ_{2}∉ dom(*σ*)?What is the relationship between

*ρ*and*σ*?

# 11 Feb 2019: Vocabulary building: List HOFs, the function factory

There are PDF slides for 2/12/2019.

Today: Using lambda to enlarge your vocabulary

- List computations
- Cheap functions from other functions

Similar: Haskell, ML, Python, JavaScript

Bonus: proving facts about functions

## Higher-Order Functions on lists

Today: both functions and lists

**Live coding interlude**

### List search: `exists?`

Algorithm encapsulated: linear search

Example: Is there an even element in the list?

Algebraic laws:

```
(exists? p? '()) == ???
(exixts? p? '(cons a as)) == ???
(exists? p? '()) == #f
(exixts? p? '(cons a as)) == p? x or exists? p? xs
```

### List selection: filter

### “Lifting” functions to lists: `map`

Algorithm encapsulated: Transform every element

Example: **Square every element of a list.**

Algebraic laws:

```
(map f '()) == ???
(map f (cons n ns)) == ???
```

### The universal list function: `fold`

`foldr`

takes two arguments:

`zero`

: What to do with the empty list.`plus`

: How to combine next element with running results.

Example: `foldr plus zero '(a b)`

```
cons a (cons b '())
| | |
v v v
plus a (plus b zero)
```

### In-class exercise

### Language design — why?

## One-argument functions: Curry and compose

Build one-argument functions from two-argument functions

*Currying* converts a binary function `f(x,y)`

to a function `f'`

that takes `x`

and returns a function `f''`

that takes `y`

and returns the value `f(x,y)`

.

What is the benefit? Functions like `exists?`

, `all?`

, `map`

, and `filter`

all expect a function of **one** argument. To get there, we use **Currying** and **partial application**.

Curried functions take their arguments “one-at-a-time.”

### Currying and list HOFs

### One-argument functions compose

Preview: in math, what is the following equal to?

`(f o g)(x) == ???`

Another algebraic law, another function:

```
(f o g) (x) = f(g(x))
(f o g) = \x. (f (g (x)))
```

Another example: `(o not null?)`

# 13 Feb 2019: Tail calls and continuations

There are PDF slides for 2/14/2019.

Announcement: late homework

- 2, 3, 4 hours late ==
**unfair**

Announcement: recitations next week

- Thursday is Monday schedule, will have lecture
- Opportunity for make-up recitation Wednesday, Saturday

Where have we been, where are we going: **functions**

Today: proofs, costs, control flow

## Proofs about functions

## Tail calls

Intuition: In a function, a call is in *tail position* if it is the last thing the function does.

A tail call is a *call in tail position*.

Important for optimizations: Can change complexity class.

Anything in tail position is the **last thing executed**!

Key idea is **tail-call optimization**!

Example: `reverse '(1 2)`

Question: How much stack space is used by the call?

Call stack:

```
reverse '()
append
reverse '(2)
append
reverse '(1 2)
```

Answer: Linear in the length of the list

## Tail calls and the method of accumulating parameters

Trick: put answer in parameter

Write laws for

`(revapp xs ys) = (append (reverse xs) ys)`

**Who could write the code?**

The cost of this version is linear in the length of the list being reversed.

Parameter `ys`

is the **accumulating parameter**.

(A powerful, general technique.)

Example: `revapp '(1 2) '()`

Question: How much stack space is used by the call?

Call stack: (each line *replaces* previous one)

revapp ‘(1 2)’() –> revapp ‘(2)’(1) –> revapp ‘()’(2 1)

Answer: Constant

Answer: a **goto**!!

Think of “tail call” as “goto with arguments”

But `goto`

is limited to labels named in the code.

Remember tail calls? Suppose you call a **parameter**!

A **continuation** is code that represents “the rest of the computation.”

- Not a normal function call because continuations never return
- Think “goto with arguments”

## Continuations

### Different coding styles

**Direct style**: Last action of a function is to return a value. (This style is what you are used to.)

**Continuation-passing style (CPS)**: Last action of a function is to “throw” value to a *continuation.* For us, tail call to a parameter.

### Uses of continuations

Compiler representation: Compilers for functional languages often convert direct-style user code to CPS because CPS matches control-flow of assembly.

Some languages provide a construct for

*capturing*the*current continuation*and giving it a name`k`

. Control can be resumed at captured continuation by*throwing*to`k`

.A style of coding that can mimic

*exceptions*Callbacks in GUI frameworks

Event loops in game programming and other concurrent settings

Even web services!

### Implementation

We’re going to simulate continuations with function calls in tail position.

First-class continuations require compiler support: primitive function that materializes “current continuation” into a variable. (Missing chapter number 3.)

## Motivating Example: From existence to witness

Ideas?

Bad choices:

- nil
- special symbol
`'fail`

- run-time error

Good choice:

- exception (not in uScheme)

Question: How much stack space is used by the call?

Answer: Constant

# 20 Feb 2019: Continuations for backtracking

There are PDF slides for 2/21/2019.

### Continuations for Search

### Solving a Literal

`start`

carries a partial truth assignment to variables `current`

Box describes how to extend `current`

to make a variable, say `x`

, true.

Case 1: `current(x) = #t`

Call `success`

continuation with `current`

Pass `fail`

as `resume`

continuation (argument to `success`

)

Case 2: `current(x) = #f`

Call `fail`

continuation

Case 3: `x`

not in `current`

Call `success`

continuation with `current{x -> #t}`

Pass `fail`

as `resume`

continuation

**Board**: pictures of two solvers:

- Make
*either*A or B equal to`b`

(last time) [“or true”, “and false”] - Make
*both*A and B equal to`b`

[“and true”, “or false”]

### Solving a Negated Literal (Your turn)

`start`

carries a partial truth assignment to variables `current`

Box describes how to extend `current`

to make a negated variable, say `not x`

, true.

Case 1: `current(x) = #f`

Call `success`

continuation with `current`

Pass `fail`

as `resume`

continuation (argument to `success`

)

Case 2: `current(x) = #t`

Call `fail`

continuation

Case 3: `x`

not in `current`

Call `success`

cotinuation with `current{x -> #f}`

Pass `fail`

as `resume`

continuation

### Solving A and B

Solver enters A

If A is solved, newly allocated success continuation starts B

If B succeeds, we’re done! Use

`success`

continuation from context.If B fails, use

`resume`

continuation A passed to B as`fail`

.If A fails, the whole thing fails. Use

`fail`

continuation from context.

### Solving A or B

Solver enters A

If A is solved, we’re good! But what if context doesn’t like solution? It can resume A using the resume continuation passed out as

`fail`

.If A can’t be solved, don’t give up! Try a

**newly allocated failure continuation**to start B.If ever B is started, we’ve given up on A entirely. So B’s success and failure continuations are exactly the ones in the context.

If B succeeds, but the context doesn’t like the answer, the context can resume B.

If B fails, abject failure all around; call the original

`fail`

continuation.

## Lisp and Scheme Retrospective

### Common Lisp, Scheme

Advantages:

- High-level data structures
- Cheap, easy recursion
- Automatic memory management (garbage collection!)
- Programs as data!
- Hygenic macros for extending the language
- Big environments, tiny interpreters, everything between
- Sophisticated Interactive Development Environments
- Used in AI applications; ITA; Paul Graham’s company Viaweb

Down sides:

- Hard to talk about data
- Hard to detect errors at compile time

Bottom line: it’s all about `lambda`

- Major win
- Real implementation cost (heap allocation)

## Bonus content: Scheme as it really is

- Macros!
- Cond expressions (solve nesting problem)
- Mutation
- …