CS 251: Programming Languages

Fall 2017

Basic Information

Instructor: Jed Yang, Center for Math & Computing 324,
Office hours: Monday 16:20–17:20 (in CMC 306), Thursday 14:35–15:35, Friday 13:00–14:00; or by appointment
Lectures: 5a (MW 13:50–15:00, F 14:20–15:20) in Center for Math & Computing 301
Course website: http://cs.carleton.edu/faculty/jyang/cs251.17f/

Course Information

What makes a programming language like "Python" or like "Java"? This course will look past superficial properties (like indentation) and into the soul of programming languages. We will explore a variety of topics in programming language construction and design: syntax and semantics, mechanisms for parameter passing, typing, scoping, and control structures. Students will expand their programming experience to include other programming paradigms, including functional languages like Scheme and ML.

Textbook: None. Readings will be assigned from a variety of electronic sources.

Resources

Syllabus [PDF]
Scheme (we will mostly be using R5RS in this course) resources:
- Dybvig's The Scheme Programming Language: 3rd edition (R5RS) | 4th edition (R6RS)
- Guidelines: style | grading
- Language standards: R5RS | R6RS
- Introductory programming textbooks based on Scheme: SICP | HtDP
- Racket (a descendant of Scheme): guide | reference
C resources:
- Guidelines: style | grading
- Tutorials: Gribble | Allain
- Books: K&R (not free) | The C Book
- Lecture Notes: Summit | Marshall
- Tools: Valgrind | Makefile | Git

Calendar

Daily/weekly schedule to be updated throughout the term; topics, readings, and exam dates are tentative and subject to change.

Date Read before class Topics Due 10pm after class

Week 1: Introduction

1. 09/11 M Introduction; Python revisited
[code]

2. 09/13 W Programming paradigms
What is Python?
Python vs. others Programming languages hw0: Logistics
3. 09/15 F Dybvig 1; 2.1–2.2
[note] Dybvig 3rd and 4th editions (both linked above) are based on R5RS and R6RS, respectively, which are slightly different standards for Scheme. We are using R5RS in DrRacket, and the interpreter project will be based on R5RS. As such, I recommend reading 3rd ed. However, if you prefer to learn newer features, feel free to read 4th ed., as long as you keep in mind that some code will not work.
Scheme basics
[code]
hw1: Scheme lab
Week 2: Scheme

4. 09/18 M Dybvig 2.3–2.6;
Scheme style guide Scheme lists
[code]

5. 09/20 W Dybvig 3.2; Tail recursion Tail recursion
[code]
hw2: Binary search trees
6. 09/22 F Dybvig 4
[note] When encountering unfamiliar concepts that we skipped (e.g., define-syntax from Dybvig 3.1), feel free to look it up or ignore.
Do not use set! in your code (yet). We will talk about this later.
Do not use the shorthand forms for binding variables to procedures: (define (f x) body). Instead, write out the lambda expression: (define f (lambda (x) body)).
Binding forms
[code]
hw3: Lazy lists
Week 3: Scheme

7. 09/25 M Dybvig 5.1–5.4, 5.8*
[note] Do not use iteration syntax do and for-each. Instead, use recursion.
* Adjust section numbers if reading 4th ed.: skip sections on continuations, delayed evaluation, and multiple values.
Higher-order functions
[code]
hw4: First-class functions
8. 09/27 W Dybvig 6.1–6.4
[note] Do not worry too much about quasiquote.
Do not use set-car! or set-cdr! (or any other procedure that ends with !).
Recursive substitution model
[code]
hw5: Sieve of Eratosthenes
9. 09/29 F Exam 1 (topics)
Week 4: C

10. 10/02 M C tutorial
[note] The tutorial is long. There's lots of great info in there! Rather than read it word for word, my recommendation is to skim it so that you are aware of what is in it and where. Your goal is to have your eyes land on all the text in there, but not to absorb all of it. Focus in particular on something you notice that looks different from Java. A lot of it is very similar to Java, but there are some pockets with some very major differences.
Specific sections are assigned for the next few days.
C basics, assignment models
[code]
hw6: C lab, part 1
Project team preferences
11. 10/04 W Memory: Stack v. Heap
optional fairy tale Memory allocation
[code]
hw7: C lab, part 2
12. 10/06 F Pointers
Pointer Fun with Binky Records (structs)
[code]

Week 5: Tokenization

13. 10/09 M Strings
[note] The return value of strcmp is (incorrectly) reversed in this tutorial.

BNF Specifying syntax
[code]
hw8: Vector
14. 10/11 W Lexical analysis Tokenization
[code]

15. 10/13 F Scott 2.3–2.3.1
[note] Linked on Moodle.
Shift-reduce parsing
[code]
proj1: Linked list
Week 6: Parsing

16. 10/18 W Scott 2.3.2 Recursive descent parsing
- grammars: [ Python | Java | C ]
proj2: Talloc
17. 10/20 F Exam 2 (topics)
Week 7: Evaluation

18. 10/23 M Compiler
Interpreter Side effects
[code]
proj3: Tokenizer
19. 10/25 W SICP 3.2–3.2.1
[note] Linked above.
Environment model
[code]

20. 10/27 F SICP 3.1–3.1.1 Environment model
[code]
proj4: Parser
Week 8: Topics

21. 10/30 M C macros Scope
[code]

22. 11/01 W Buddy memory allocation
Dangling references Heap management
[code]

- disliked programming languages

- a small malloc implementation
proj5: Eval
23. 11/03 F Garbage collection Garbage collection
[code]

Week 9: Topics

24. 11/06 M Evaluation strategy
[note] Skip "Nondeterministic strategies" at the end.
Parameter passing
[code]
proj6: Apply
25. 11/08 W Lambda calculus
[note] Up to but not including the Church–Rosser theorem.
Lambda calculus basics
[code]

- lambda calculus game

26. 11/10 F Lambda calculus
[note] Skim: some of this will be review, and we will cover some of the rest in class.
Programming with lambda calculus
- alligator eggs
proj7: Primitives
Week 10: Topics

27. 11/13 M Dybvig 3.3–3.4 Continuations; wrap up
[code]

28. 11/15 W Exam 3 (topics) proj8: Interpreter
[note] Due at end of final exam period.

Date	Read before class	Topics	Due 10pm after class
Week 1: Introduction
1. 09/11 M		Introduction; Python revisited [code]
2. 09/13 W	Programming paradigms What is Python? Python vs. others	Programming languages	`hw0`: Logistics
3. 09/15 F	Dybvig 1; 2.1–2.2 [note] Dybvig 3rd and 4th editions (both linked above) are based on R5RS and R6RS, respectively, which are slightly different standards for Scheme. We are using R5RS in DrRacket, and the interpreter project will be based on R5RS. As such, I recommend reading 3rd ed. However, if you prefer to learn newer features, feel free to read 4th ed., as long as you keep in mind that some code will not work.	Scheme basics [code]	`hw1`: Scheme lab
Week 2: Scheme
4. 09/18 M	Dybvig 2.3–2.6; Scheme style guide	Scheme lists [code]
5. 09/20 W	Dybvig 3.2; Tail recursion	Tail recursion [code]	`hw2`: Binary search trees
6. 09/22 F	Dybvig 4 [note] When encountering unfamiliar concepts that we skipped (e.g., `define-syntax` from Dybvig 3.1), feel free to look it up or ignore. Do not use `set!` in your code (yet). We will talk about this later. Do not use the shorthand forms for binding variables to procedures: `(define (f x) body)`. Instead, write out the `lambda` expression: `(define f (lambda (x) body))`.	Binding forms [code]	`hw3`: Lazy lists
Week 3: Scheme
7. 09/25 M	Dybvig 5.1–5.4, 5.8* [note] Do not use iteration syntax `do` and `for-each`. Instead, use recursion. * Adjust section numbers if reading 4th ed.: skip sections on continuations, delayed evaluation, and multiple values.	Higher-order functions [code]	`hw4`: First-class functions
8. 09/27 W	Dybvig 6.1–6.4 [note] Do not worry too much about quasiquote. Do not use `set-car!` or `set-cdr!` (or any other procedure that ends with `!`).	Recursive substitution model [code]	`hw5`: Sieve of Eratosthenes
9. 09/29 F		Exam 1 (topics)
Week 4: C
10. 10/02 M	C tutorial [note] The tutorial is long. There's lots of great info in there! Rather than read it word for word, my recommendation is to skim it so that you are aware of what is in it and where. Your goal is to have your eyes land on all the text in there, but not to absorb all of it. Focus in particular on something you notice that looks different from Java. A lot of it is very similar to Java, but there are some pockets with some very major differences. Specific sections are assigned for the next few days.	C basics, assignment models [code]	`hw6`: C lab, part 1 Project team preferences
11. 10/04 W	Memory: Stack v. Heap optional fairy tale	Memory allocation [code]	`hw7`: C lab, part 2
12. 10/06 F	Pointers Pointer Fun with Binky	Records (structs) [code]
Week 5: Tokenization
13. 10/09 M	Strings [note] The return value of `strcmp` is (incorrectly) reversed in this tutorial. BNF	Specifying syntax [code]	`hw8`: Vector
14. 10/11 W	Lexical analysis	Tokenization [code]
15. 10/13 F	Scott 2.3–2.3.1 [note] Linked on Moodle.	Shift-reduce parsing [code]	`proj1`: Linked list
Week 6: Parsing
16. 10/18 W	Scott 2.3.2	Recursive descent parsing - grammars: [ Python \| Java \| C ]	`proj2`: Talloc
17. 10/20 F		Exam 2 (topics)
Week 7: Evaluation
18. 10/23 M	Compiler Interpreter	Side effects [code]	`proj3`: Tokenizer
19. 10/25 W	SICP 3.2–3.2.1 [note] Linked above.	Environment model [code]
20. 10/27 F	SICP 3.1–3.1.1	Environment model [code]	`proj4`: Parser
Week 8: Topics
21. 10/30 M	C macros	Scope [code]
22. 11/01 W	Buddy memory allocation Dangling references	Heap management [code] - disliked programming languages - a small `malloc` implementation	`proj5`: Eval
23. 11/03 F	Garbage collection	Garbage collection [code]
Week 9: Topics
24. 11/06 M	Evaluation strategy [note] Skip "Nondeterministic strategies" at the end.	Parameter passing [code]	`proj6`: Apply
25. 11/08 W	Lambda calculus [note] Up to but not including the Church–Rosser theorem.	Lambda calculus basics [code] - lambda calculus game
26. 11/10 F	Lambda calculus [note] Skim: some of this will be review, and we will cover some of the rest in class.	Programming with lambda calculus - alligator eggs	`proj7`: Primitives
Week 10: Topics
27. 11/13 M	Dybvig 3.3–3.4	Continuations; wrap up [code]
28. 11/15 W		Exam 3 (topics)	`proj8`: Interpreter [note] Due at end of final exam period.