Lecture notes for COMP 105 (Programming Languages)

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: 105 Tip Sheet

Handout: 105 Syllabus

Handout: Experiences of successful 105 students

Handout: Lessons in program design

Handout: Design checklists

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

What it involves:

Today:

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

Value structure: induction again

In-class exercise: inductive definition of natural number

Writing code with recursion and induction

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

Recursive-function problem

Exercise: all-fours?

Write a function that takes a natural number n and returns true (1) if and only if all the digits in n’s numeral are 4’s.

Key design step: form of number

Choose inductive structure for natural numbers:

Step 1: Forms of DECNUMERAL proof system (1st lesson in program design):

Example inputs

Step 2:

Function’s name and contract

Steps 3 and 4:

Function (all-fours? n) returns nonzero if and only if the decimal representation of n can be written using only the digit 4.

Example results

Step 5: write expected results as unit tests:

(check-assert      (all-fours?  4))
(check-assert (not (all-fours?  9)))
(check-assert      (all-fours? 44))
(check-assert (not (all-fours? 48)))
(check-assert (not (all-fours? 907)))

Algebraic laws

Step 6: Generalize example results to arbitrary forms of data

(all-fours? d) ==  (= d 4)

(all-fours? (+ (* 10 m) d)) ==
   (= d 4) && (all-fours? m)

Left-hand sides turn into case analysis

Step 7:

; (all-fours? d) == ...
; (all-fours? (+ (* 10 m) d)) ==  ...

(define all-fours? (n)
  (if (< n 10)
    ... case for n = d ...
    ... case for n = (+ (* 10 m) d),
        so m = (/ n 10) and
        d = (mod n 10) ...))

Each right-hand side becomes a result

Step 8:

; (all-fours? d) ==  (= d 4)
; (all-fours? (+ (* 10 m) d)) ==
;           (= d 4) && (all-fours? m)

(define all-fours? (n)
   (if (< n 10)
       (= n 4)
       (and (= 4 (mod n 10))
            (all-fours? (/ n 10)))))

Revisit tests:

Step 9:

(check-assert      (all-fours?  4))
(check-assert (not (all-fours?  9)))
(check-assert      (all-fours? 44))
(check-assert (not (all-fours? 907)))

(check-assert (not (all-fours? 48)))

Checklist:

Syntax in programming languages

Concrete Syntax

Programming-languages people are wild about compositionality.

Syntactic structure of Impcore

Watch for syntactic categories, syntactic composition

Our common framework

Goal: eliminate superficial differences

No new language ideas.

Imperative programming with an IMPerative CORE:

Idea of LISP syntax

Parenthesized prefix syntax:

Examples:

(+ 2 2)
(if (isbound? x rho) (lookup rho x) (error 99))

(For now, we use just the round brackets)

Impcore structure

Two syntactic categories: expressions, definitions

No statements!—expression-oriented

(if e1 e2 e3)
(while e1 e2)
(set x e)
(begin e1 ... en)
(f e1 ... en)

Evaluating e has value, may have side effects

Functions f named (e.g., + - * / = < > print)

The only type of data is “machine integer” (deliberate oversimplification)

Syntactic structure of Impcore

An Impcore program is a sequence of definitions

(define mod (m n) (- m (* n (/ m n))))

Compare

int mod (int m, int n) { 
  return m - n * (m / n); 
}

Impcore variable definition

Example

(val n 99)

Compare

int n = 99;

Slide 15 

Example function shows every form

(define even? (n) (= (mod n 2) 0))

(define 3n+1-sequence (n) ; from Collatz
  (begin
    (while (!= n 1)
       (begin
         (println n)
         (if (even? n)
             (set n (/ n 2))
             (set n (+ (* 3 n) 1)))))
    n))

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

(power x 0)       == 1
(power x (+ n 1)) == (* (power x n) x)

(power x 0)             == 1
(power x (+ (* 2 m) 0)) == (square (power x m))
(power x (+ (* 2 m) 1)) == (* x (square (power x m)))

(all-fours? d)              ==  (= d 4), [d is digit]
(all-fours? (+ (* 10 m) d)) ==  
      (and (= d 4) (all-fours? m)), where m != 0

(has-digit? d d)   == 1
(has-digit? d d')  == 0, where d differs from d'
(has-digit? (+ (* 10 m) d) d') ==
      (or (= d d') (has-digit? m d')), where m != 0

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)

Bloom’s taxonomy (Metacognition 10)

Cognitive actions:

  1. Remember
  2. Understand
  3. Apply
  4. Analyze
  5. Evaluate
  6. Create

Operational semantics

Cognitive actions:

  1. Remember
  2. Understand
  3. Apply
  4. Analyze
  5. Evaluate
  6. Create

Concrete and abstract Syntax

Programming-languages people are wild about compositionality.

Example of compositionality: concrete syntax (grammar)

                                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:

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:

(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:

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

Concrete syntax for Impcore

Definitions and expressions:

How to define behaviors inductively

Expressions only

Base cases (plural): numerals, names

Inductive steps: compound forms

First, simplify the task of specification

What’s different? What’s the same?

 x = 3;               (set x 3)

 while (i * i < n)    (while (< (* i i) n)
   i = i + 1;            (set i (+ i 1)))

Abstract away gratuitous differences

(See the bones beneath the flesh)

Abstract syntax

Same inductive structure as BNF grammar
(related to proof system)

More uniform notation

Good representation in computer

Concrete syntax: sequence of symbols

Abstract syntax: ???

The abstraction is a tree

The abstract-syntax tree (AST):

Exp = LITERAL (Value)
    | VAR     (Name)
    | SET     (Name name, Exp exp)
    | IFX     (Exp cond, Exp true, Exp false)
    | WHILEX  (Exp cond, Exp exp)
    | BEGIN   (Explist)
    | APPLY   (Name name, Explist actuals)

One kind of “application” for both user-defined and primitive functions.

ASTs

Question: What do we assign behavior to?

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

Question: How can we represent all while loops?

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

Answer:

As a data structure:

In C, trees are fiddly

typedef struct Exp *Exp;
typedef enum {
  LITERAL, VAR, SET, IFX, WHILEX, BEGIN, APPLY
} Expalt;        /* which alternative is it? */

struct Exp {  // only two fields: 'alt' and 'u'!
    Expalt alt;
    union {
        Value literal;
        Name var;
        struct { Name name; Exp exp; } set;
        struct { Exp cond; Exp true; Exp false; } ifx;
        struct { Exp cond; Exp exp; } whilex;
        Explist begin;
        struct { Name name; Explist actuals; } apply;
    } u;
};

Let’s picture some trees

An expression:

  (f x (* y 3))

(Representation uses Explist)

A definition:

  (define abs (n)
    (if (< n 0) (- 0 n) n))

Key question: names (review)

From ASTs to behaviors

Behaviors of ASTs, part I: Atomic forms

Numeral: stands for a value

Name: stands for what?

Slide 12 

Slide 13 

``Environment’’ is pointy-headed theory

You may also hear:

Influence of environment is “scope rules”

Find behavior using environment

Recall

  (* y 3)   ;; what does it mean?

Your thoughts?

Impcore uses three environments

Global variables ξ

Functions ϕ

Formal parameters ρ

There are no local variables

Function environment ϕ not shared with variables—just like Perl

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:

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

    • Judgment
    • Rules
    • Valid derivations
  2. What can we prove about it?

    • Metatheory

Review: environments

Slide 1 

Find behavior using environment

Recall

  (* y 3)   ;; what does it mean?

Impcore uses three environments

Global variables ξ (“ksee”)

Functions ϕ (“fee”)

Formal parameters ρ (“roe”)

There are no local variables

Function environment ϕ not shared with variables—just like Perl

Rules and metatheory

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

Slide 4 

Slide 5 

Slide 6 

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

Slide 7 

Slide 8 

Slide 9 

Slide 10 

Slide 11 

Slide 12 

Slide 13 

Slide 14 

Slide 15 

Slide 16 

Good and bad judgments

Your turn: good and bad judgments

Which correctly describes what happens at run time?

  1. (+ 2 2), ξ, ϕ, ρ⟩ ⇓ ⟨4, ξ, ϕ, ρ

  2. (+ 2 2), ξ, ϕ, ρ⟩ ⇓ ⟨99, ξ, ϕ, ρ

  3. (+ 2 2), ξ, ϕ, ρ⟩ ⇓ ⟨0, ξ, ϕ, ρ

  4. (while 1 0), ξ, ϕ, ρ⟩ ⇓ ⟨77, ξ, ϕ, ρ

  5. (begin (set n (+ n 1)) 17)ξ, ϕ, ρ
     ⇓ ⟨17, ξ, ϕ, ρ

To know for sure, we need a proof

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:

  1. In the body of digit?, what expressions are evaluated in what order?

  2. As a function application, the body matches template (f e1 e2). In this example,

    • What is f?
    • What is e1?
    • What is e2?

Let’s develop the ApplyUser rule for the special case of two arguments: APPLY(f, e1, e2), ξ, ϕ, ρ⟩ ⇓ ?

What is the result of (digit? 7)?

How do we know it’s right?

From rules to proofs

Judgment speaks truth when ``derivable’’

Special kind of proof: derivation

A form of “syntactic proof”

Recursive evaluator travels inductive proof

Root of derivation at the bottom (surprise!)

Build

The ``Tony Hawk’’ algorithm

First let’s see a movie

Building a derivation

Slide 20 

Slide 21 

Slide 22 

Slide 23 

Slide 24 

Slide 25 

Slide 26 

Slide 27 

Slide 28 

Slide 29 

Slide 30 

Slide 31 

Slide 32 

Slide 33 

Building derivations

Slide 34 

30 January 2019: Derivations, metatheory, better semantics

There are PDF slides for 1/31/2019.

Review: calls

Slide 1 

Slide 2 

Slide 3 

Review: Derivations

Judgment speaks truth when ``derivable’’

Special kind of proof: derivation

A form of “syntactic proof”

Valid derivation

Initial state partially or fully known

Final state determined by initial state (homework)

Every node in tree is an instance of some rule

No primes!

Recursive evaluator travels inductive proof

Root of derivation at the bottom (surprise!)

Build

The ``Tony Hawk’’ algorithm

First let’s see a movie

Building a derivation

Slide 7 

Slide 8 

Slide 9 

Slide 10 

Slide 11 

Slide 12 

Slide 13 

Slide 14 

Slide 15 

Slide 16 

Slide 17 

Slide 18 

Slide 19 

Slide 20 

Building derivations

Slide 21 

Proofs about derivations: metatheory

Syntactic proofs empower meta reasoning

Proof 𝒟 is a data structure

Got a fact about all proofs?

Prove facts by structural induction over derivations

Example: evaluating an expression doesn’t create or destroy any global variables (the set of defined global variables is invariant)

Metatheorems often help implementors

More example metatheorems:

Slide 24 

Metatheorems are proved by induction

Induction over structure (or height) of derivation trees 𝒟

These are “math-class proofs” (not derivations)

Proof

Let’s try it!

Cases to try:

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

Slide 26 

Slide 27 

Slide 28 

Slide 29 

Slide 30 

4 February 2019: Scheme

There are PDF slides for 2/5/2019.

Announcements

Note: course not graded on a curve

Scheme homework:

Where are we going?

Recursion and composition:

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:

  1. What is the abstract syntax? What are the syntactic categories, and what are the forms in each category?

  2. What are the values? What do expressions/terms evaluate to?

  3. What environments are there? That is, what can names stand for?

  4. How are terms evaluated? What are the judgments? What are the evaluation rules?

  5. 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:

Scheme Values

Most values are S-expressions.

An fully general S-expression is one of

Many predefined functions work with a list of S-expressions

A list of S-expressions is either

Programming with lists and S-expressions

Lists: A subset of S-Expressions.

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

Slide 1 

Slide 2 

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.

Why are lists useful?

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

Lists generalized: S-expressions

An ordinary S-expression is one of:

Can write literally in source, with quote

μScheme’s new syntax

Slide 4 

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”

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?

You fill in these right-hand sides:

(append '()         ys) == 

(append (cons z zs) ys) == 

Equations and function for append

(append '()         ys) == ys

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


(define append (xs ys)

  (if (null? xs)

      ys

      (cons (car xs) (append (cdr xs) 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:

  1. IH (’())

  2. 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 = ’()

Inductive case: xs = (cons z zs)

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?

Naive list reversal

(define reverse (xs)
   (if (null? xs)
       '()
       (append (reverse (cdr xs))
               (list1 (car xs)))))

The list1 function maps an atom x to the singleton list containing x.

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

The method of accumulating parameters

Write laws for

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

Who could write the code?

Reversal by accumulating parameters

(define revapp (xs ys)
   ; return (append (reverse xs) ys)
   (if (null? xs)
       ys
       (revapp (cdr xs) 
               (cons (car xs) ys))))

(define reverse (xs) (revapp xs '()))

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.

A-list example

    -> (find 'Building 
             '((Course 105) (Building Barnum) 
               (Instructor Ramsey)))
    Barnum
    -> (val nr (bind 'Office 'Halligan-222
               (bind 'Courses '(105 150TW)
               (bind 'Email 'comp105-grades '()))))
    ((Email comp105-grades) 
     (Courses (105 150TW)) 
     (Office Halligan-222))
    -> (find 'Office nr) 
    Halligan-222
    -> (find 'Favorite-food nr)
    ()

Notes:

Algebraic laws of association lists

Laws of association lists

(find k (bind k  v a-l)) = v
(find k (bind k' v a-l)) = (find k a-l), provided k != k'
(find k '()) =  '() --- bogus!

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

There are PDF slides for 2/7/2019.

Skills refresh

Refresh: Complete these laws

(append '()         zs) == ...
(append (cons y ys) zs) == ...

(reverse '())         == ...
(reverse (cons y ys)) == ...

Refresh: Complete these laws

Waiting…

Refresh: Complete these laws

(append '()         zs) == zs
(append (cons y ys) zs) == (cons y (append ys zs))

(reverse '())         == '()
(reverse (cons y ys)) == (append (reverse ys) 
                                 (list1 y))

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.

Already doing it: immutable data (append)

Next up: better ways of gluing functions together

μScheme’s semantics

Impcore: Things that should offend you

Look up function vs look up variable:

To get variable, check multiple environments

Create a function? Must give it a name

Slide 5 

Slide 6 

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

Slide 7 

Slide 8 

Evaluate e1 through en, bind answers to x1, … xn

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:

Slide 9 

So let’s see that semantics!

Key idea: don’t worry about memory

Slide 10 

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)

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.

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:

Function escapes!

-> (define to-the-n-minus-k (n k)
      (let
        ([x-to-the-n-minus-k (lambda (x) 
                                (- (exp x n) k))])
        x-to-the-n-minus-k))
-> (val x-cubed-minus-27 (to-the-n-minus-k 3 27))
-> (x-cubed-minus-27 2)
-19

The function to-the-n-minus-k is a higher-order function because it returns another (escaping) function as a result.

No need to name the escaping function

-> (define to-the-n-minus-k (n k)
      (lambda (x) (- (exp x n) k)))

-> (val x-cubed-minus-27 (to-the-n-minus-k 3 27))
-> (x-cubed-minus-27 2)
-19

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

The zero-finder

(define findzero-between (f lo hi)
   ; binary search
   (if (>= (+ lo 1) hi)
       hi
       (let ([mid (/ (+ lo hi) 2)])
          (if (< (f mid) 0)
              (findzero-between f mid hi)
              (findzero-between f lo mid)))))
(define findzero (f) (findzero-between f 0 100))

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:

Cube root of 27 and square root of 16

-> (findzero (to-the-n-minus-k 3 27))                                    
3
-> (findzero (to-the-n-minus-k 2 16))
4

Your turn!!

Lambda questions

(define combine (p? q?)
   (lambda (x) (if (p? x) (q? x) #f)))

(define divvy (p? q?)
   (lambda (x) (if (p? x) #t (q? x))))

(val c-p-e (combine prime? even?))
(val d-p-o (divvy   prime? odd?))

(c-p-e 9) == ?            (d-p-o 9) == ?
(c-p-e 8) == ?            (d-p-o 8) == ?
(c-p-e 7) == ?            (d-p-o 7) == ?

Lambda answers

(define combine (p? q?)
   (lambda (x) (if (p? x) (q? x) #f)))

(define divvy (p? q?)
   (lambda (x) (if (p? x) #t (q? x))))

(val c-p-e (combine prime? even?))
(val d-p-o (divvy   prime? odd?))

(c-p-e 9) == #f           (d-p-o 9) == #t
(c-p-e 8) == #f           (d-p-o 8) == #f
(c-p-e 7) == #f           (d-p-o 7) == #t

Slide 17 

How lambda works

Rule for lambda

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

Slide 18 

Rule for function Application

Slide 19 

Questions about ApplyClosure:

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

Similar: Haskell, ML, Python, JavaScript

Bonus: proving facts about functions

Higher-Order Functions on lists

Today: both functions and lists

Slide 1 

Your turn: Common list algorithms

Algorithms on linked lists (or arrays in sequence):

Predefined list algorithms

Some classics:

Fold also called reduce, accum, a “catamorphism”

Live coding interlude

List search: exists?

Slide 4 

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

Defining exists?

; (exists? p? '())         = #f
; (exists? p? (cons y ys)) = #t,          if (p? y)
; (exists? p? (cons y ys)) = (exists? p? ys),
                                          otherwise
-> (define exists? (p? xs)
      (if (null? xs)
          #f
          (if (p? (car xs)) 
              #t
              (exists? p? (cdr xs)))))
-> (exists? symbol? '(1 2 zoo))
#t
-> (exists? symbol? '(1 2 (zoo)))
#f

List selection: filter

Defining filter

; (filter p? '()) == '()
; (filter p? (cons y ys)) ==
;         (cons y (filter p? ys)), when (p? y)
; (filter p? (cons y ys)) ==
;         (filter p? ys), when (not (p? y))

-> (define filter (p? xs)
     (if (null? xs)
       '()
       (if (p? (car xs))
         (cons (car xs) (filter p? (cdr xs)))
         (filter p? (cdr xs)))))

Running filter

-> (filter (lambda (n) (>  n 0)) '(1 2 -3 -4 5 6))
(1 2 5 6)
-> (filter (lambda (n) (<= n 0)) '(1 2 -3 -4 5 6))
(-3 -4)
-> (filter ((curry <)  0) '(1 2 -3 -4 5 6))
(1 2 5 6)
-> (filter ((curry >=) 0) '(1 2 -3 -4 5 6))
(-3 -4)

“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)) ==  ???

Your turn:

-> (map     add3 '(1 2 3 4 5))
(4 5 6 7 8)

;; (map f '())         =
;; (map f (cons y ys)) =

Answers:

-> (map     add3 '(1 2 3 4 5))
(4 5 6 7 8)

; (map f '())         ==  '()
; (map f (cons y ys)) ==  (cons (f y) (map f ys))

Defining and running map

; (map f '())         == '()
; (map f (cons y ys)) == (cons (f y) (map f ys))
-> (define map (f xs)
     (if (null? xs)
       '()
       (cons (f (car xs)) (map f (cdr xs)))))
-> (map number? '(3 a b (5 6)))
(#t #f #f #f)
-> (map *100 '(5 6 7))
(500 600 700)

Slide 11 

The universal list function: fold

Slide 12 

foldr takes two arguments:

Example: foldr plus zero '(a b)

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

Slide 13 

Slide 14 

In-class exercise

Slide 15 

Slide 16 

Slide 17 

Language design — why?

Slide 18 

One-argument functions: Curry and compose

Build one-argument functions from two-argument functions

Slide 19 

The idea of currying

-> (map     ((curry +) 3) '(1 2 3 4 5))
; add 3 to each element

-> (exists? ((curry =) 3) '(1 2 3 4 5))
; is there an element equal to 3?

-> (filter  ((curry >) 3) '(1 2 3 4 5))
; keep elements that 3 is greater then

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.

To get one-argument functions: Curry

-> (val positive? (lambda (y) (< 0 y)))
-> (positive? 3)
#t
-> (val <-c (lambda (x) (lambda (y) (< x y))))
-> (val positive? (<-c 0)) ; "partial application"
-> (positive? 0)
#f

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

Slide 22 

Slide 23 

Currying and list HOFs

Your turn!

-> (map     ((curry +) 3) '(1 2 3 4 5))
???
-> (exists? ((curry =) 3) '(1 2 3 4 5))
???
-> (filter  ((curry >) 3) '(1 2 3 4 5))
???                        ; tricky

Answers

-> (map     ((curry +) 3) '(1 2 3 4 5))
(4 5 6 7 8)
-> (exists? ((curry =) 3) '(1 2 3 4 5))
#t
-> (filter  ((curry >) 3) '(1 2 3 4 5)) 
(1 2)

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)))

One-argument functions compose

-> (define o (f g) (lambda (x) (f (g x))))
-> (define even? (n) (= 0 (mod n 2)))
-> (val odd? (o not even?))
-> (odd? 3)
#t
-> (odd? 4)
#f

Another example: (o not null?)

Slide 27 

13 Feb 2019: Tail calls and continuations

There are PDF slides for 2/14/2019.

Announcement: late homework

Announcement: recitations next week

Where have we been, where are we going: functions

Today: proofs, costs, control flow

Proofs about functions

Proofs about functions

Function consuming A is related to proof about A

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.

What is tail position?

Tail position is defined inductively:

Idea: The last thing that happens

Anything in tail position is the last thing executed!

Key idea is tail-call optimization!

Slide 3 

Slide 4 

Slide 5 

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)

Reversal by accumulating parameters

Moves recursive call to tail position

Contract:

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

Laws:

  (revapp '()         ys) == ys
  (revapp (cons z zs) ys) ==
             (revapp zs (cons z ys))

Who could write the code?

Reversal by accumulating parameters

; laws: (revapp '()         ys) = ys
;       (revapp (cons z zs) ys) =
;                     (revapp zs (cons z ys))

(define revapp (xs ys)
   ; return (append (reverse xs) ys)
   (if (null? xs)
       ys
       (revapp (cdr xs) 
               (cons (car xs) ys))))

(define reverse (xs) (revapp xs '()))

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.)

Slide 8 

Slide 9 

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

Are tail calls familiar?

In your past, what did you call a construct that

  1. Transfers control to a point in the code?

  2. Uses no stack space?

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.”

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

Implementation

Motivating Example: From existence to witness

Slide 11 

Ideas?

Bad choices:

Good choice:

Slide 12 

Slide 13 

Slide 14 

Slide 15 

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

Answer: Constant

Example Use: Instructor Lookup

-> (val 2016f '((Fisher 105)(Hescott 170)(Chow 116)))
-> (instructor-info 'Fisher 2016f)
(Fisher teaches 105)
-> (instructor-info 'Chow 2016f)
(Chow teaches 116)
-> (instructor-info 'Souvaine 2016f)
(Souvaine is-not-on-the-list)

Slide 17 

Slide 18 

Slide 19 

Slide 20 

20 Feb 2019: Continuations for backtracking

There are PDF slides for 2/21/2019.

Slide 1 

Homework: Solving Boolean formulas

A formula is one of these:

In context of:

Your turn: Find satisfying assignment!

(val f1 (make-and (list4 'x 'y 'z (make-not 'x))))
   ; x /\ y /\ z /\ !x

(val f2 (make-not (make-or (list2 'x 'y)))) 
   ; !(x \/ y)

(val f3 (make-not (make-and (list3 'x 'y 'z))))
   ; !(x /\ y /\ z)

Slide 4 

Satisfying assignments

(val f1 (make-and (list4 'x 'y 'z (make-not 'x))))
   ; x /\ y /\ z /\ !x  ;; NONE

(val f2 (make-not (make-or (list2 'x 'y)))) 
   ; !(x \/ y)          ;; { x |-> #f, y |-> #f }

(val f3 (make-not (make-and (list3 'x 'y 'z))))
   ; !(x /\ y /\ z)     ;; { x |-> #f, ... }

Slide 6 

Slide 7 

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

Solving a literal

; (satisfy-literal-true x current succ fail) =
;   (succ current fail), when x is bound to #t in cur
;   (fail),              when x is bound to #f in cur
;   (succ (bind x #t current) fail), x unbound in cur

(define satisfy-literal-true (x current succ fail)
  (if (bound? x current)
      (if (find x current)
          (succ current fail)
          (fail))
      (succ (bind x #t current) fail)))

Board: pictures of two solvers:

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

  1. Solver enters A

  2. If A is solved, newly allocated success continuation starts B

  3. If B succeeds, we’re done! Use success continuation from context.

  4. If B fails, use resume continuation A passed to B as fail.

  5. If A fails, the whole thing fails. Use fail continuation from context.

Solving A or B

  1. Solver enters A

  2. 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.

  3. If A can’t be solved, don’t give up! Try a newly allocated failure continuation to start B.

  4. 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.

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

  6. If B fails, abject failure all around; call the original fail continuation.

Lisp and Scheme Retrospective

Slide 9 

Five powerful questions

  1. What is the abstract syntax?
    Syntactic categories? Terms in each category?

  2. What are the values?
    What do expressions/terms evaluate to?

  3. What environments are there?
    What can names stand for?

  4. How are terms evaluated?
    Judgments? Evaluation rules?

  5. What’s in the initial basis?
    Primitives and predefined, what is built in?

Slide 11 

Common Lisp, Scheme

Advantages:

Down sides:

Bottom line: it’s all about lambda

Bonus content: Scheme as it really is

  1. Macros!
  2. Cond expressions (solve nesting problem)
  3. Mutation

Macros!

Full Scheme: Macros

A Scheme program is just another S-expression

(See book sections 2.16, 2.17.4)

Conditional expressions

Full Scheme: Conditionals

(cond [c1 e1]    ; if c1 then e1
      [c2 e2]    ; else if c2 then e2
       ...            ...
      [cn en])   ; else if cn then en

; Syntactic sugar---'if' is a macro:
(if e1 e2 e3) == (cond [e1 e2]
                       [#t e3])

Mutation

Full Scheme: Mutation

Not only variables can be mutated.

Mutate heap-allocated cons cell:

(set-car! '(a b c) 'd)  => (d b c)

Circular lists, sharing, avoids allocation