CS 68 S11 Syllabus

• Monday, March 28
  • Programming languages - History and Overview (M 1)
  • Skim Programming Languages - the First 25 Years linked to Blackboard

• Tuesday, March 29 (optional x-hour)
  • Haskell (for those who have not taken CS 8).
    I will assume that you understand the material in the first 3 lectures and the short assignments SA-0, SA-1, and SA-2 in CS 8. See the CS 8 course page. Eventually you should look at lectures 4 through 7 (except the graphics and drawing) and do SA-4.

• Wednesday, March 30
  • Computability (M 2)
  • Begin LISP (M 3)
  • Examples: examples.lisp hof.lisp
  • To download Dr. Scheme (now DrRacket): Download Racket

• Friday, April 1
  • LISP ( Recursive Functions of Symbolic Expressions and their Computation by Machine).
  • Examples: hof.lisp, inter.lisp, examples.env
  • Compilers, interpreters, and Virtual Machines (M 4.1)

• Monday, April 4
  • Lambda Calculus (M 4.2)
  • Lambda calculus cheat sheet

• Tuesday, April 5 (optional x-hour)
  • More Haskell (for those who have not taken CS 8).
    We will discuss material in the List Processing, Data (representing shapes), and Polymorphism lectures. Eventually you should look at the lectures on List Functions and Trees and do SA-6.

• Wednesday, April 6
  • Lambda Calculus, cont.
  • Lambda calculus cheat sheet (cont)
  • Example: The "fix" function in Haskell
  • Functional and imperative languages (M 4.4)
  • Read: "Can Programming Languages be Liberated from the Von Neuman Style?" (Backus) linked to Blackboard.

• Friday, April 8
  • The Algol family, ML, and Haskell (M 5)
  • Read "Report on the Algorithmic Language Algol 60" linked to Blackboard.
  • Read "Go to Statement Considered Harmful" (Dijkstra) linked to Blackboard.

• Monday, April 11
  • Data Types (M 6.1, 6.2, and 6.5)

• Tuesday, April 12 (optional x-hour)
  • More Haskell (for those who have not taken CS 8).
    Parsing (lectures Intro to parsing, Parsing sentences, parsing expressions). Do SA 9.

• Wednesday, April 13
  • Type checking and Inference (M 6.3-6.4)

• Friday, April 15
  • Lexing and Parsing
  • Examples: LexArithP.hs, LexArith.hs, ParseArithP.hs, ParseArith.hs, Parser68.hs, PcfLexer.hs, ParserPCF.hs, PCFcode.zip
  • Handouts: parserGuide.txt

• Monday, April 18
  • Semantics (M 4.3) - operational.
  • Examples: ArithSemantics.hs, PCFSubstInterpreter.hs, PCFEnvInterpreter.hs

• Tuesday, April 19 (optional x-hour)
  • More Haskell (for those who have not taken CS 8).
    Monads. Lectures "Intro to monads," "List, IO, and state monads." Do SA 12.
  • Handout: HaskellCheatSheet.pdf

• Wednesday, April 20
  • Semantics continued - axiomatic
  • Type checking
  • Examples: TypeCheck.hs, ParseTypedPCF.hs, PcfTypedLexer.hs, TypedPCFcode.zip
  • Readings: Assigning Meaning to Programs (Floyd),
    An Axiomatic Basis for Computer Programming (Hoare),
    Proof of a Program: Find (Hoare)
    Proving Type Safety (Bruce)
    on Blackboard

• Friday, April 22
  • Run-time Storage Management (M 7.1-7.2)

• Monday, April 25
  • Functions, Procedures, and Tail Recursion (M 7.3)
  • Supporting Higher-Order Functions (M 7.4-7.5)
  • Managing the Heap

• Wednesday, April 27
  • Haskell and Monads (Tackling the Awkward Squad, pp. 1-16)
  • Examples: controlIO.hs, Stack.hs, stacks.hs, State.hs, randomNumGen.hs
  • You may want to review the Monad lectures linked to the CS 8 web page.

• Friday, April 29
  • Finish State monad, StateT monad, Parser using StateT monad, IORef
  • Examples: randomNumGenMonad.hs, turtleS.hs, StateT.hs, ParserST.hs, IORefExample.hs

• Monday, May 2
  • Control and Exceptions (M 8.1-8.2)

• Wednesday, May 4
  • Continuations and Evaluation Order (M 8.3-8.5)
  • Example: factCont.hs

• Friday, May 6
  • Data Abstraction (M 9.1-9.2)
  • Modules (M 9.3-9.5)
  • ML Modules

• Monday, May 9
  • Subtyping ("Understanding Subtypes," Chap. 5 from Bruce's book. On blackboard.)
  • Examples: TreeNode.java, SearchTreeNode.java, BinarySearchTree.java,
  • Midterm 7 pm, 006 Kemeney

• Wednesday, May 11
  • OOLs (M 10)

• Friday, May 13
  • OOLs: Simula and Smalltalk (M 11)

• Monday, May 16
  • C++ and Implementation (M 12)

• Wednesday, May 18
  • Java and Typing Issues (M 13.1-13.4)

• Friday, May 20
  • Java 5 Generics and Wild Cards (M 13.5)

• Monday, May 23
  • Concurrency (M 14)

• Wednesday, May 25
  • Java and Haskell Concurrency
  • Examples: BoundedBuffer.java, BoundedBufferTest.java, Producer.java, Consumer.java, concur.hs
  • Readings: Tackling the Awkward Squad (Chap. 4)

• Friday, May 27
  • Concurrency - Channels, Software Transactional Memory
  • Readings: Beautiful Concurrency
  • Examples: stm.hs, phil.hs
  • Optional Reading: Communicating Sequenctial Processes (Hoare), linked to blackboard

• Monday, May 30 - No class - Memorial Day

• Wednesday, June 1
  • Programming Language Design - Principles, Discuss Python
  • Readings: On the Design of Programming Languages (Wirth), linked to blackboard