CS 251: Programming Languages
Spring 2018
[ Current Week ]
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: 3a (MW 11:10–12:20, F 12:00–13:00) in Center for Math & Computing 301
- Course website: http://cs.carleton.edu/faculty/jyang/cs251.18s/
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:
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. 03/26 M | Introduction; Python revisited | ||
2. 03/28 W | Programming paradigms
What is Python? Python vs. others | Programming languages | hw0: Logistics |
3. 03/30 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 | hw1: Scheme lab |
Week 2: Scheme | |||
4. 04/02 M | Dybvig 2.3–2.6; Scheme style guide | Scheme lists | |
5. 04/04 W | Dybvig 3.2; Tail recursion | Tail recursion | hw2: Binary search trees |
6. 04/06 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 Do not use the shorthand forms for binding variables to procedures: | Binding forms | hw3: Lazy lists |
Week 3: Scheme | |||
7. 04/09 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 | hw4: First-class functions |
8. 04/11 W | Dybvig 6.1–6.4
[note]
Do not worry too much about quasiquote.
Do not use | Recursive substitution model | hw5: Sieve of Eratosthenes |
9. 04/13 F | Exam 1 (topics) | ||
Week 4: C | |||
10. 04/16 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 | hw6: C lab, part 1 |
11. 04/18 W |
Memory: Stack v. Heap
fairy tale | Memory allocation | hw7: C lab, part 2 |
12. 04/20 F |
Pointers
Pointer Fun with Binky | Records (structs) | |
Week 5: Tokenization | |||
13. 04/23 M |
Strings
[note]
The return value of
strcmp is (incorrectly) reversed in this tutorial. | Regular expressions | hw8: Vector |
14. 04/25 W | Lexical analysis | Tokenization | |
15. 04/27 F | BNF | Context-free grammar | proj1: Linked list |
Week 6: Parsing | |||
16. 05/02 W | Scott 2.3–2.3.1
[note]
Linked on Moodle.
| Shift-reduce parsing | proj2: Talloc |
17. 05/04 F | Scott 2.3.2 | Recursive descent parsing | |
Week 7: Evaluation | |||
18. 05/07 M |
Compiler
Interpreter | Side effects | proj3: Tokenizer |
19. 05/09 W | Exam 2 (topics) | ||
20. 05/11 F | SICP 3.2–3.2.1
[note]
Linked above.
| Environment model | proj4: Parser |
Week 8: Topics | |||
21. 05/14 M | SICP 3.1–3.1.1
C macros | Assignment and binding forms | |
22. 05/16 W |
Buddy memory allocation Dangling references | Scope | proj5: Eval |
23. 05/18 F | Garbage collection | Garbage collection |
[note]
Department webserver is down for maintenance 5:30pm to 6:30pm on Friday 5/18.
|
Week 9: Topics | |||
24. 05/21 M |
Evaluation strategy
[note]
Skip "Nondeterministic strategies" at the end.
| Parameter passing | proj6: Apply |
25. 05/23 W |
Lambda calculus
[note]
Up to but not including the Church–Rosser theorem.
| Lambda calculus basics | |
26. 05/25 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 | proj7: Primitives |
Week 10: Topics | |||
27. 05/28 M | Dybvig 3.3–3.4 | Continuations; wrap up | |
28. 05/30 W | Exam 3 (topics) |
proj8: Interpreter
[note]
Due at end of final exam period.
|