COS 371: Programming Languages
Spring 2020
Basic Information
- Instructor: Jed Yang, CC221, 651-638-6405,
- Office hours: by appointment (instructions)
- Lectures: Mod B (MWF 09:00–09:50) in RC229
- Course website: https://www.mathcs.bethel.edu/yang/cos371.20s/
Resources
- 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 (starting hw2)
- 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 and exam dates are tentative and subject to change.
Date | Read before class | Topics | Due 10pm after class |
---|---|---|---|
Topic 1: Introduction | |||
Week 1 | |||
1. 02/03 M | - | Introduction | |
2. 02/05 W | Programming paradigms
What is Python? Python vs. others | Programming languages | hw0: Logistics |
3. 02/07 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 | |
Topic 2: Scheme | |||
Week 2 | |||
4. 02/10 M | Dybvig 2.3–2.6; Scheme style guide | Scheme lists | hw1: Scheme lab |
5. 02/12 W | Dybvig 2.7–2.8; Scheme grading guide | List functions | |
6. 02/14 F | Dybvig 3.2; Tail call | More list functions | hw2: Binary search trees |
Week 3 | |||
7. 02/17 M | - | Tail recursion | |
8. 02/19 W | 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 |
9. 02/21 F | 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 | |
Week 4 | |||
10. 02/24 M | Dybvig 6.1–6.4
[note]
Do not worry too much about quasiquote.
Do not use | Lambda shielding | hw4: First-class functions |
11. 02/26 W | - | Recursive substitution model | |
12. 02/28 F | - | (catch-up) | hw5: Sieve of Eratosthenes |
Topic 3: C | |||
Week 5 | |||
13. 03/02 M | - | Exam 1 (topics and tips) | |
14. 03/04 W |
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 |
15. 03/06 F |
Memory: Stack v. Heap
fairy tale | Memory allocation | |
Week 6 | |||
16. 03/09 M |
Pointers
Pointer Fun with Binky | Arrays and records | hw7: C lab, part 2 |
17. 03/11 W |
Strings
[note]
The return value of
strcmp is (incorrectly) reversed in this tutorial. | Strings and multidimensional arrays | |
18. 03/13 F | - | C wrap-up | hw8: Vector |
Week 7: spring break | |||
Week 8: extended spring break | |||
Topic 4: Syntax | |||
Week 9 | |||
19. 03/30 M |
Scott 2–2.1.1
[note]
Free on RedShelf after signing up with a Bethel student email address.
| Regular expressions | |
20. 04/01 W | Scott 2.2.0 | Tokenization | proj1: Linked list |
21. 04/03 F | Scott 2.2.1–2.2.2 | Tokenizer construction | |
Week 10 | |||
22. 04/06 M | Scott 2.1.2 | Context-free grammars | proj2: Talloc |
23. 04/08 W | Scott 2.1.3 | Derivations and parse trees | |
Week 11 | |||
24. 04/15 W | Scott 2.3.0, 2.4 | Parsing | |
25. 04/17 F | Scott 2.3.4 | Shift-reduce parsing | proj3: Tokenizer |
Topic 5: Evaluation | |||
Week 12 | |||
26. 04/20 M | Scott 2.3.1–3 | Recursive descent parsing | |
27. 04/22 W | Dybvig 2.9, 4.5 | Side effects | proj4: Parser |
28. 04/24 F | SICP 3.2–3.2.1
[note]
Linked above.
| Environment model: eval, let | |
Week 13 | |||
29. 04/27 M | - | Exam 2 (topics and tips) | |
30. 04/29 W | SICP 3.2.2 | Environment model: apply, lambda | proj5: Eval |
31. 05/01 F | SICP 3.1–3.1.1 | Assignment forms: define, set! | |
Topic 6: Wrap up | |||
Week 14 | |||
32. 05/04 M | SICP 3.1.2–3 | Binding forms: let*, letrec | |
33. 05/06 W | Scott 3.3–3.3.2, 3.3.6 | Scope | proj6: Apply |
34. 05/08 F | Scott 9.3–9.3.2 | Parameter passing | |
Week 15 | |||
35. 05/11 M | Scott 8.5.2–8.5.3a | Garbage collection: reference counting | proj7: Primitives |
36. 05/13 W | Scott 8.5.3b | Garbage collection: tracing | |
37. 05/15 F | - | Exam 3 (topics and tips) |
proj8: Interpreter
[note]
Due at final exam time.
|
Course Information
- Official course title: Organization of Programming Languages
- Official course description: Formal programming language specification using various grammars and the Backus-Naur Form. Data types and structures, control structures, and data flow of several programming languages, including interpreters and compilers. Introduction to parsing and lexical analysis.
- Prerequisites: COS 216: Data Structures and Algorithms
- Textbooks:
Here are two optional books.
- R. Kent Dybvig, The Scheme programming language. This will be central to the course; I would have required it were it not freely available electronically (see resource section above).
- Michael Scott, Programming language pragmatics. This is an advanced textbook for a year-long course and, as such, it contains a wealth of information, mostly beyond the scope of this course.
Topics
Programming Languages is a course designed to delve deeper into understanding the design and implementation of programming languages. Our primary thrust is to implement a Scheme interpreter in C from scratch. Throughout, we will also spend time on various aspects of programming language design and structure. The list of topics is flexible. We will discuss topics as they arise naturally or when there is a lull in the project that gives us a chance for a diversion. Some topics may include:- Regular expressions and tokenization
- Context-free grammars and parsing
- Tail recursion, memory management, variable scope, parameter passing
- Lambda calculus
Objectives
I will guide you to:- Learn Scheme, a functional programming language.
- Think tail recursively.
- Implement a Scheme interpreter in C from scratch.
- Understand key features and tradeoffs that undergird programming languages you've seen.
- Commit to working, struggling, learning, laughing, and succeeding together as a team.
Grading
Your grade will be determined by a weighted arithmetic mean of various components with weights listed in the table on the right.component | weight |
---|---|
Term project | 21% |
Contribution | 10% |
Homework | 15% |
Exam 1 | 18% |
Exam 2 | 18% |
Exam 3 | 18% |
Note that there is no preset curve of how many of each letter grade will be given. If you all do A-level work, you will each get an A. As such, you are encouraged to help each other in the pursuit of perfection.
In many courses I intentionally make one exam harder than others, which gives me information (in a mathematical sense) in separating an A performance from an A- performance. Typically, I will let you know and adjust that exam scores upward. What this means is that you should NOT care about how hard an exam is. If you do A-level work, you will get an A, regardless of the raw numerical score prior to adjustment.
Besides possibly adjusting scores upward for difficult exams, I also reserve the right to lower the grade cutoffs. Both of these help you. I will not hurt you by adjusting your exam scores downward or increasing the grade cutoffs.
Contribution. This component is based on your contribution to the learning of your classmates in general (classroom participation, Moodle involvement, etc.) and to the success of your partners. Peer Evaluations: Because you will be working in teams, I will ask you to give honest and thorough feedback about the contributions of you and your teammates. Providing an honest appraisal of your peers is difficult, but it's also important. Your contribution to your team, as measured both by peer evaluations and by my observations, will be part of your contribution grade.
Requirements
Whatever you do, work at it with all your heart, as working for the Lord, not for human masters, since you know that you will receive an inheritance from the Lord as a reward. It is the Lord Christ you are serving.I will be trying to make these verses true for me as I work with you throughout this course, and I hope that you will, too.- Colossians 3:23–24 NIV
Attendance and participation. I expect you to attend class. You may not notice me taking attendance during class meetings, but I will notice if you are not in class. Occasional absences will not impact your grade because what I look for is not mere attendance, but engagement and participation.
Indeed, coming to class is not just about showing up; it is also about being fully engaged in the learning experience. If you have a question, others in the class may also be wondering the same thing. So, please speak up and ask questions anytime you need to. Not only will you be helping yourself, but also you will be helping your peers. Attending office hours is another great opportunity to ask questions.
Be mindful of others. Refrain from using mobile phones or laptops for activities unrelated to the learning process. If you prefer to use laptops to take notes, please kindly sit in the back, as the screen may distract others. There is research that suggests taking notes by hand is better for long-term retention (P. A. Mueller and D. M. Oppenheimer, The pen is mightier than the keyboard, Psychological Science 25 (2014), 1159–1168).
Silence and put away mobile phones and do not use laptops for anything other than class-related activities.
Homework and Projects. There will be stand-alone assignments, particularly at the beginning of the term. There will be mileposts for the term project due regularly throughout the term. Typically, assignments are due at 22:00.
You are allowed up to three (3) late days throughout the term for homework and two (2) late days for project mileposts (but not the last project submission). (A day is 24 hours, regardless of weekends and holidays.) This allotment is to cover for legitimate reasons for tardiness that may arise. No explanation for the tardiness is necessary or desired, but please do inform me that you are submitting an assignment late. After the freebies, work handed in late will receive zero credit. If you wish to use more than one late day for a single assignment, please discuss with me first. To be fair to everyone in the class, I will generally not grant additional extensions without the intervention of a doctor or dean. But if a genuine emergency situation arises, please talk to me.
Exams. There are three (3) in-class midterm exams (see calendar for a tentative schedule), weighted equally. The exams are cumulative, but will focus on material not yet tested. (There is no final exam, but I reserve the right to replace the third midterm with a final exam.)
There are no make-up exams except in circumstances recognized by the instructor as beyond the control of the student. To receive this consideration, the instructor must be notified of the problem before the exam unless this is impossible, in which case as soon as possible.
Time outside of class. I expect a typical student to spend about two to three hours outside of class for each hour in class. Some students need to spend a bit more than that (which is okay). If you are spending more than 10 hours per week on this course outside of class time, please come talk to me so we can find ways to help you learn the material without spending so much time.
Illness. You should make every effort to attend class when you are healthy. If you become ill, for your well-being and the well-being of the rest of the class, you should not come to class. (Nor should you show up to my office with your germs!) Yes, this sounds like common sense, but it is tempting to try and power through as normal so as not to fall behind. If you become ill, or know that you will need to miss class for some reason, please contact me as soon as you are able, and we will work together to plan how you will keep up and/or make up any missed work.
Policies
Learning integrity.
Search me, O God, and know my heart;Collaborative work is an integral part of many successful ventures. As such, I expect that you should collaborate with your classmates a lot during your time in this course. However, it is important to understand that there is a big difference between thinking about and solving a problem as part of a group (which is good, both educationally and morally) and copying an answer or letting someone else copy your answer (which is bad, educationally and morally, and has punitive consequences).
Try me, and know my anxieties;
And see if there is any wicked way in me,
And lead me in the way everlasting.- Psalm 139:23–24 NKJV
In short, I trust you to maintain the utmost level of academic integrity in this course. Please do not break this trust; if you do, there will be repercussions. The formal policy below lays this out explicitly, and supplements Bethel's academic honesty policy.
Collaboration policy.
- You may collaborate on the homework assignments to the extent of formulating ideas as a group, but you may not collaborate in the actual writing of solutions/code (unless explicitly allowed in the instructions).
- In particular, you may not work from notes taken during collaborative sessions.
- You may not consult any materials from any previous offerings of this course or from any other similar course offered elsewhere unless explicitly permitted.
- You may not show your homework assignment code to other students, or to copy code from other students or other resources, including Internet sources. Do not email each other code, and do not copy code over each other's shoulders. Any code you hand in for an assignment must represent your own work.
- You are required to completely understand any solution/code that you submit and, in case of any doubt, you must be prepared to orally explain your solution/code to me. If you have submitted a solution/code that you cannot verbally explain to me, then you have violated this policy.
Accommodation policy. Disability-related accommodations are determined by the Office of Accessibility Resources and Services (OARS). Students are responsible to contact the Office of Accessibility Resources and Services. Once OARS determines that accommodations are to be made, they will notify the student and the instructor via e-mail. Students choosing to use the disability-related accommodations must contact the instructor no later than five business days before accommodations are needed. The instructor will provide accommodations, but the student is required to initiate the process for the accommodations.
Concerns and appeals. If you have any concerns regarding the course, your grades, or the instructor, see the instructor first. If needed, see Bethel's academic appeals policy.
Getting Help
If you need help there are multitude of resources you can use:- Yourself. If you're stuck on a problem or struggling with a concept from class, take a break and think about something else (e.g., your Hebrew assignment, the economics of Star Trek) for a few hours and then try a fresh start.
- Your classmates. You are each other's best resource: talking through
the course material with someone else who is also trying to master it is a
great way for you both to learn. (And don't discount the learning that you
will do while trying to explain to a classmate an idea covered during class
that you think you understand; I can't count the number of times that I've
discovered that I didn't really understand something until I tried to teach it
to someone.) The homework assignments are meant to challenge you, and figuring
some of them out together is a great approach.
- The instructor. Come to my office hours or email to make an appointment. To make an appointment, please email me several times you are available and try to give me at least 24 hours of lead time. Each afternoon, I will look at your availabilities and try to schedule as many people as I can fit for the next day. I will consistently reserve Thursdays for research, and I do not schedule office hours or make appointments for that day. I have this scheduled "research day" so that I can work on my research projects in an uninterrupted block of time. Without reserving a large block, I won't have time for any research. Tuesdays tend to be good days for appointments.
- The Moodle forum. Personal questions (e.g., regarding grades) should be elsewhere, but all other questions (e.g., course content, homework, logistics) should go here rather than sending me email. I will periodically respond on the forum, but also please help answer each other's questions! While I try to answer queries about homework within 24–48 hours, I cannot always make this timeline, and you should not rely on faster responses than this. Among other things, this means that you would be well advised to ask any questions of clarification earlier than the day before an assignment is due.