COS 371: Programming Languages

Spring 2020

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

WeekMondayWednesdayFriday
Topic 1: Introduction
Week 11. 02/03 M

-

Introduction

[code]

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

[code]

Topic 2: Scheme
Week 24. 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

[code]

6. 02/14 F

Dybvig 3.2; Tail call

More list functions

[code]

hw2: Binary search trees

Week 37. 02/17 M

-

Tail recursion

[code]

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 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/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

[code]

Week 410. 02/24 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/26 W

-

Recursive substitution model

[code]

12. 02/28 F

-

(catch-up)

hw5: Sieve of Eratosthenes

Topic 3: C
Week 513. 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

[code]

hw6: C lab, part 1

15. 03/06 F

Memory: Stack v. Heap
fairy tale

Memory allocation

[code]

Week 616. 03/09 M

Pointers
Pointer Fun with Binky

Arrays and records

[code]

hw7: C lab, part 2

Project team preferences

17. 03/11 W

Strings

[note] The return value of strcmp is (incorrectly) reversed in this tutorial.

Strings and multidimensional arrays

[code]

18. 03/13 F

-

C wrap-up

hw8: Vector

Week 7: spring break(Spring break)(Spring break)(Spring break)
Week 8: extended spring break(Spring break)(Spring break)(Spring break)
Topic 4: Syntax
Week 919. 03/30 M

Scott 2–2.1.1

[note] Free on RedShelf after signing up with a Bethel student email address.

Regular expressions

[code]

20. 04/01 W

Scott 2.2.0

Tokenization

[code]

proj1: Linked list

21. 04/03 F

Scott 2.2.1–2.2.2

Tokenizer construction

Week 1022. 04/06 M

Scott 2.1.2

Context-free grammars

proj2: Talloc

23. 04/08 W

Scott 2.1.3

Derivations and parse trees

(Good Friday)
Week 11(Monday after Easter)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 1226. 04/20 M

Scott 2.3.1–3

Recursive descent parsing

27. 04/22 W

Dybvig 2.9, 4.5

Side effects

[code]

proj4: Parser

28. 04/24 F

SICP 3.2–3.2.1

[note] Linked above.

Environment model: eval, let

Week 1329. 04/27 M

-

Exam 2 (topics and tips)

30. 04/29 W

SICP 3.2.2

Environment model: apply, lambda

[code]

proj5: Eval

31. 05/01 F

SICP 3.1–3.1.1

Assignment forms: define, set!

[code]

Topic 6: Wrap up
Week 1432. 05/04 M

SICP 3.1.2–3

Binding forms: let*, letrec

[code]

33. 05/06 W

Scott 3.3–3.3.2, 3.3.6

Scope

[code]

proj6: Apply

34. 05/08 F

Scott 9.3–9.3.2

Parameter passing

[code]

Week 1535. 05/11 M

Scott 8.5.2–8.5.3a

Garbage collection: reference counting

[code]

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

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:

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%
Exam 118%
Exam 218%
Exam 318%
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+, 73% C, 70% C-, 65% 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 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. 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;
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. 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: