CS 251: Programming Languages

Spring 2018

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

Week	Monday	Wednesday	Friday
Week 1: Introduction	1. 03/26 M Introduction; Python revisited [code]	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 [code] hw1: Scheme lab
Week 2: Scheme	4. 04/02 M Dybvig 2.3–2.6; Scheme style guide Scheme lists [code]	5. 04/04 W Dybvig 3.2; Tail recursion Tail recursion [code] 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 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. 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 [code] hw4: First-class functions	8. 04/11 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. 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 [code] hw6: C lab, part 1 Project team preferences	11. 04/18 W Memory: Stack v. Heap fairy tale Memory allocation [code] hw7: C lab, part 2	12. 04/20 F Pointers Pointer Fun with Binky Records (structs) [code]
Week 5: Tokenization	13. 04/23 M Strings [note] The return value of strcmp is (incorrectly) reversed in this tutorial. Regular expressions [code] hw8: Vector	14. 04/25 W Lexical analysis Tokenization [code]	15. 04/27 F BNF Context-free grammar proj1: Linked list
Week 6: Parsing	(mid-term break)	16. 05/02 W Scott 2.3–2.3.1 [note] Linked on Moodle. Shift-reduce parsing [code] proj2: Talloc	17. 05/04 F Scott 2.3.2 Recursive descent parsing
Week 7: Evaluation	18. 05/07 M Compiler Interpreter Side effects [code] 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 [code]	22. 05/16 W Buddy memory allocation Dangling references Scope [code] proj5: Eval	23. 05/18 F Garbage collection Garbage collection [code] [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 [code] proj6: Apply	25. 05/23 W Lambda calculus [note] Up to but not including the Church–Rosser theorem. Lambda calculus basics [code]	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 [code]	28. 05/30 W Exam 3 (topics) proj8: Interpreter [note] Due at end of final exam period.	(reading day)