COS 371: Programming Languages

Spring 2022

[ Current Week | Syllabus ]

Basic Information

Resources

Calendar

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

DateRead before classTopicsDue 10pm after class
Unit 0: Introduction
Week 1
1. 01/31 M -
introduction
[code]
2. 02/02 W Programming paradigms
What is Python?
Python vs. others
programming languages
[code]
hw0: Logistics
3. 02/04 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]
Unit 1: Scheme
Week 2
4. 02/07 M Dybvig 2.3–2.6;
Scheme style guide
Scheme lists
[code]
hw1: Scheme lab
5. 02/09 W Dybvig 2.7–2.8;
Scheme grading guide
list functions
[code]
6. 02/11 F Dybvig 3.2
more list functions
[code]
hw2: Binary search trees
Week 3
7. 02/14 M Tail call optimization
sections 1 and 3
tail recursion
[code]
8. 02/16 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 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
9. 02/18 F Dybvig 5.1–5.4*
[note] Do not use iteration syntax do and for-each. Instead, use recursion.

* Also 5.5 if reading 4th ed.

higher-order functions
[code]
Week 4
10. 02/21 M 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 !).

lambda shielding
[code]
hw4: First-class functions
11. 02/23 W -
recursive substitution model
[code]
12. 02/25 F -
(catch-up)
[code]
hw5: Sieve of Eratosthenes
Unit 2: C
Week 5
13. 02/28 M -
exam1 (topics and logistics)
14. 03/02 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
[code]
hw6: C lab, part 1
15. 03/04 F Memory: Stack v. Heap
fairy tale
memory allocation
[code]
Week 6
16. 03/07 M Pointers
Pointer Fun with Binky
arrays and records
[code]
hw7: C lab, part 2
17. 03/09 W Strings
[note] The return value of strcmp is (incorrectly) reversed in this tutorial.
strings and multidimensional arrays
[code]
18. 03/11 F -
C wrap-up
[code]
hw8: Vector
Unit 3: Syntax
Week 7
Week 8
19. 03/21 M Scott 2–2.1.1
[note] Linked below.
regular expressions
[code]
20. 03/23 W Scott 2.2.0
tokenization
[code]
proj1: Linked list
21. 03/25 F Scott 2.2.1–2.2.2
tokenizer construction
Week 9
22. 03/28 M Scott 2.1.2
context-free grammars
23. 03/30 W Scott 2.1.3
derivations and parse trees proj2: Talloc
24. 04/01 F Scott 2.3.0, 2.4
parsing
Week 10
25. 04/04 M Scott 2.3.3
shift-reduce parsing
26. 04/06 W Scott 2.3.1–2
recursive descent parsing proj3: Tokenizer
27. 04/08 F Dybvig 2.9, 4.5
side effects
[code]
Unit 4: Evaluation
Week 11
28. 04/11 M SICP 3.2–3.2.1
[note] Linked above.
environment model: eval, let proj4: Parser
29. 04/13 W -
exam2 (topics and logistics)
Week 12
30. 04/20 W SICP 3.2.2
environment model: apply, lambda
[code]
proj5: Eval
31. 04/22 F SICP 3.1–3.1.1
assignment forms: define, set!
[code]
Unit 5: Topics
Week 13
32. 04/25 M SICP 3.1.2–3
binding forms: let*, letrec
[code]
33. 04/27 W Scott 3.3–3.3.2, 3.3.6
scope
[code]
proj6: Apply
34. 04/29 F Scott 8.3–8.3.2
parameter passing
[code]
Week 14
35. 05/02 M Scott 7.7.2–7.7.3a
garbage collection: reference counting
[code]
36. 05/04 W Scott 7.7.3b
garbage collection: tracing proj7: Primitives
37. 05/06 F (catch-up)
Week 15
38. 05/09 M exam3 (topics and logistics)
39. 05/11 W (catch-up)
40. 05/13 F (wrap-up) proj8: Interpreter
[note] Due at final exam time.

Course Information

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:

Objectives

I will guide you to:

Structure and Adjustments

This is a remote, synchronous course: Due to the uncertain and ever-changing conditions the world is in, additional adjustments may need to be made. Thus: We will get through this semester together.

Grading

Your grade will be determined by a weighted arithmetic mean of various components with weights listed in the table on the right.
componentweight
Term project21%
Contribution10%
Homework15%
Exams54%
The total score will be converted to a letter grade whose lower bounds are: 93% A, 90% A-, 87% B+, 83% B, 80% B-, 77% C+, 72% C, 69% C-, 66% D+, 60% D, 0% F.

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's 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.
- Colossians 3:23–24 NIV
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.

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. 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).

In general, you are expected to keep your video on most of the time to make your engagement more clear. Let me know if there are legitimate reasons why you need to be off-camera frequently.

It is my sincere hope that every one of you get all the points for attendance and participation.

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 several in-class midterm exams (see calendar for a tentative schedule). Subsequent exams will mainly focus on the material covered since the previous exam, but can include previous material too. (There is no final exam, but I reserve the right to replace the last 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, you should not come to class. 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;
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
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).

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.

Handing in plagiarized code will result in a minimum penalty of no credit on the assignment and may result in harsher penalties depending on the severity of the honesty policy violation. Plagiarizing code will also result in being less prepared for the exams since you will not have developed the skills to produce appropriate solutions on your own without assistance. If you have doubts about the honesty of an action, ask the professor. Ignorance is not an excuse.

Accommodation policy. Bethel University is committed to accessibility for students with disabilities and the Office of Accessibility Resources and Services (OARS) is a resource to ensure students experience access. The instructor will provide accommodations after the student initiates the process.

OARS recommends the student and faculty discuss how accommodations may apply in the specific course. Accommodations cannot modify essential requirements or fundamentally alter the nature of the course. Consultation with OARS may be necessary to clarify reasonable accommodations based on the course. If there are any questions or concerns, connect with OARS at accessibility-services@bethel.edu or 651.638.6833.

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: