Syllabus for COMP 105, Programming Languages
(Information Every Student Must Know)

Fall 2020

Hard work is great but working smarter is even better. At times, you have to take a break, back off, and use your time efficiently.

— Bill Belichick

Introduction and Welcome

Welcome to COMP 105! Here you will learn to write code from scratch, in a language you have never seen before, in a way that sails through code review.

COMP 105 serves as the fourth course in our required programming sequence. In this sequence, it is the only 100-level course. It is the most technically deep, the most intellectually challenging, and the one in which you’ll develop the most diverse and highest-level thinking skills. You will think hard, stretch beyond the skills you have grown comfortable with, and emerge with a permanently higher level of skill.

COMP 105 introduces you—through extensive practice—to ideas and techniques that are found everywhere in today’s programming languages. These ideas and techniques infuse many languages you have not yet seen, and they will continue to infuse the programming languages of the future. Foremost among these ideas are functions, types, and objects. COMP 105 also introduces you to the mathematical foundations needed to talk precisely about languages and about programs: abstract syntax, formal semantics, type systems, and lambda calculus. Mathematics helps you recognize ideas and techniques that you have seen before, even when they are disguised.

To provide a sane and sensible context in which to learn, COMP 105 immerses you in case studies, conducted using tiny languages that are designed to help you learn. In any given case study, you may act as a practitioner (by writing code in a language), as an implementor (by working on an interpreter for the language), as a designer (by inventing semantics for a related language), or as a scholar (by proving mathematical properties of the language).

COMP 105 develops high-level, flexible programming skills that you can transfer. For example, you will find you can apply your skills to projects written in older languages such as Perl or Java, in currently popular languages such as JavaScript, Python, Ruby, Scala, and Swift, and in weird languages that might be important in the future, such as Haskell, Rust, Agda, Coq, and who knows what else. No matter what language you work in, when you finish 105, you’ll be writing more powerful programs using less code. In a profession where complexity is the enemy, your 105 skills will equip you to tackle the most demanding jobs—and succeed.

What will the experience be like?

COMP 105 is as difficult as any course in our program, and it’s a difficulty of a kind you are not used to encountering. I want every student to succeed, and you are more likely to succeed if you know what to expect.

Is 105 in-person or remote?

In Fall 2020, 105 can be taken fully remotely. For all students, lectures will be delivered online asynchronously.
Recitations will be held online in Virtual Halligan. Office hours will be held in Virtual Halligan with the help of the course help center.

What do we need to do if meeting in-person?

When meeting in person for this course (e.g. for a study group or by request), you’ll be responsible for wearing a mask that covers your mouth and nose, practicing physical distancing of 6 feet with other individuals, and keeping your desk and chair on the designated spots on the ground. You will also be responsible for wiping down your own desk, chair, and other frequently touched surfaces with alcohol wipes or other approved disinfectant upon arrival and departure from the classroom (or lab, studio, etc.). You are also responsible for following the one-way directional patterns indicated by the signs in the hallways in academic buildings. It is imperative that we work together as a community to uphold these standards to help mitigate the risk of spreading the virus. Failure to do so may result in a referral to the Dean of Student Affairs Office. For more information about expectations for the Fall, please review the Fall Guide.

What will the online lectures be like?

The online ``lectures" will be divided into a series of short videos, preceded and followed by questions that you’ll need to answer. The preceding questions ask you to reflect on a topic relevant for the lecture. These questions are open-ended and will be graded only to the extend that you respond to the prompt. The questions that follow each video are questions that can be graded immediately to give you feedback on whether you are understanding the key points in each video. These questions are designed to help you stay engaged with the material in each video. This structure of question, video, question takes the place of the question and answer dynamics of the normal 105 lecture style.

How does 105 compare with 40?

For most students, COMP 105 is as difficult as COMP 40. Some students find 105 a little easier, and some find 105 a little more difficult.

If you know 40, you know that your feeling of accomplishment comes primarily from building the projects. The 40 projects are easy to talk about: they look big, and many of them sound impressive, like “I built an image compressor.” Most important, the 40 projects require that you apply the same skills that you learned in 11 and 15, just to a greater degree. In brief, 40 yields to force.

COMP 105 also has a couple of projects that look big and sound impressive, like “I built a type inferencer.” But overall, 105 is much more about finding a small, elegant, precise solution to a small problem—usually a programming problem, but sometimes a math problem. As a result, compared with COMP 40,

But even though 105 is quite different from 40, there are lots of skills that transfer. If you have taken COMP 40, then

But you must also be aware that some of not all of your habits in COMP 40 will necessarily transfer to COMP 105:

Why do I feel lost?

To succeed in 105, you must understand that it is normal to feel lost. There is nothing wrong with you, and there is nothing wrong with the course—feeling lost is a consequence of the situation: where you’re coming from and where you’re going.

Where you’re coming from is most likely 11, 15, and possibly 40. All of these courses use a single programming paradigm, and they use almost the same language: imperative programming with unsafe pointers and explicit memory management, close to the machine. Even the syntax and the data are the same—compared to what you can see in the world, and to what you are introduced to in 105, differences between C and C++ barely matter. If you’ve completed 40, you’re going to feel like an expert. And rightly so! You are an expert. But you’re a narrow expert, and 105 introduces you to the demands of a wider world.

The most important way in which 11, 15, and 40 are narrow is that their programming model is a thin veneer over the machine model. These courses don’t rely heavily on functions or types, and they do not commit deeply to objects. (While C++ makes it possible to commit strongly to types and to objects, it imposes such staggering complexity that these techniques cannot be taught in introductory courses.) Your inexperience with functions, types, and objects makes you a beginner again. And beginners often feel lost.

The other factor that comes into play is that when you learn challenging new material, you feel bad. Here’s the neuroscience:1

Many labs have observed that these critical brain regions increase in activity when people perform difficult tasks, whether the effort is physical or mental… [The road is difficult], though, because these brain regions have another intriguing property: When they increase in activity, you tend to feel pretty bad—tired, stymied, frustrated. Think about the last time you grappled with a math problem or pushed yourself to your physical limits. Hard work makes you feel bad in the moment.

What should I do about it?

When a successful student suddenly feels lost and confused, it’s discouraging. To keep up your courage, I recommend two steps:

Both these steps will help you feel better.

You will also need to learn to proceed with your work despite feelings of confusion, uncertainty, or anxiety. To help with that, you need support.

What tactics do and don’t work?

In 105, the slow approach is the fastest one. Effective 105 students stop, think, pause frequently, and work in short sessions. These tactics can be hard to put into practice, especially if you have used other tactics to succeed in other courses. But the work tactics often preferred by beginners do not promote success in 105. I paraphrase Garth Flint:

[Talented students] are very resistant to [a systematic, thoughtful, slow] approach. They do not want to plan; they want to do trial and error at the keyboard. They have not learned an important axiom of programming: “three hours of trial-and-error coding will save fifteen minutes of planning.” (I wish I knew who came up with that. They deserve an award.) [Students] want to hammer keys [in Halligan for hours on end and] then complain [that the course is too much work].

If you approach 105 by hammering away at the keyboard, be aware how the approach is working for you. If the course starts taking too much time, you can adjust your tactics—but only if you are mindful of them.

If you have already learned systematic tactics for program design and implementation, you should be able to apply them to COMP 105. If you have not had to learn a systematic approach, which is common after early courses, you will easily master a nine-step design process described in Seven Lessons in Program Design.

How does the class support my success?

To help you navigate the learning process successfully, we have built a variety of support structures into COMP 105.

How can I use office hours effectively?

COMP 105 office hours are organized around the help center, a website allows you to put your name in a queue to meet with a TA in zoom. We strongly encourage you to hangout in the Comp105 space in Virtual Halligan while you are waiting to talk to the TA.

What is Virtual Halligan?

Virtual Halligan is an instance of the Sococo networked application that uses a map-based metaphor to encourage informal interactions. While in Virtual Halligan, you can chat with other students who are working on the homework, much as students in the past might have met up in the Halligan kitchen. If a group of you all have the same question, you can meet with a TA in a group, which sometimes means your question may get answered more quickly. You can also attend recitations and office hours.

You can enter Virtual Halligan via the url https://tuftscs.sococo.com and login using your Tufts SSO credentials. The application works in Chrome or in native applications on Windows or on Macs.

Information about how to use Sococo is available via the onboarding guide written by Tufts students.

What can I expect from teaching assistants?

In COMP 105, the TAs have been instructed to use a model that may be a little different from what you are accustomed to. The TAs are not there to help you debug your homework. They are there to help you learn. And the TAs who provide the best help and who help students learn the most are the ones who guide students with questions.

The questions that TAs ask are meant to be timeless and to apply to many problems. Eventually, you will be able to use the questions yourself, to help your own progress. Questions range from the technical (“what algebraic laws apply to this function”?) to the conceptual (“in your own words, what is meant by Γ ⊢ e : τ?”) to the procedural (“how much of your 105 time is spent working alone?”). Expect questions about your work, your understanding, and your study practices.

Here are some other things you can and cannot expect from TAs:

What if I need special support?

Tufts University values the diversity of our students, staff, and faculty; Tufts recognizes the important contribution each student makes to our unique community. Tufts is committed to providing equal access and support to all qualified students through the provision of reasonable accommodations so that each student may fully participate in the Tufts experience. If you have a disability that requires reasonable accommodations, please contact the Student Accessibility Services office at Accessibility@tufts.edu or call 617-627-4539 to make an appointment with a representative who will help determine appropriate accommodations.

Accommodations cannot be enacted retroactively; if you need an accommodation, you must ask for it in advance.

How must I support my own success?

Everyone on the course staff is committed to your success. But as we do our part, you must do your part. Take advantage of the resources we offer. Read the syllabus. Most important, do not allow yourself to become socially, emotionally, or intellectually isolated. To prevent isolation, I recommend that you join a study group, and that when you can, you work in the 105 space reserved in Virtual Halligan (aka the department’s Sococo space), The informal support network in physical Halligan has been strong; participating in this culture is one of the unique advantages of getting your computer-science education at Tufts. This semester, that culture is moving online to Virtual Halligan. Don’t miss out.

As you will see throughout this syllabus, there is more you can and should do:

105 is a 100-level course. What does that mean?

Unlike 11, 15, and 40, COMP 105 is numbered above 100. Formally, this means only that unlike 11, 15, and 40, 105 counts for graduate credit. But informally, a 100-level course carries additional expectations:

What will we learn?

COMP 105 is built around two sets of skills:

The programming skills contribute to your professional practice, getting you ready to code from scratch in a language you’ve never seen before. The math contributes to several outcomes:

Here are some of the detailed skills you will develop:

What topics will we study?

You will develop the skills above by studying these topics:

  1. Functions

    • Recursion revisited: design by algebraic laws
    • Abstract syntax & (big-step) operational semantics
    • First-class, higher-order functions
    • Functions as continuations

  2. Types

    • Core ML
    • Typing rules (monomorphic and polymorphic)
    • Type checking
    • Type inference

  3. Theory

    • Lambda calculus & small-step operational semantics
    • Recursion and fixed-point operators

  4. Data abstraction

    • Abstract data types, modules, and interfaces
    • Objects, classes, and protocols
    • Inheritance and the design of class hierarchies

How heavy is the workload?

The workload in 105 is heavy; it counts for 5 semester hours of credit. Expect a demanding homework assignment almost every week, plus a final examinations. Most students say 105 demands as much time and effort as 40.

What does the workload consist of?

The work is mostly programming assignments. These assignments are significantly more challenging than the assignments in COMP 15 and COMP 40, but most of them are also much smaller: many solutions take 10 to 40 lines of code. Many of the assignments use software that comes with the text by Ramsey.

The homework also has a significant theory component. You will prove theorems using existing theory, and you will also develop new theory of your own, which will describe how a language feature might work. Early assignments are either “mostly programming” or “mostly theory;” later assignments mix programming and theory; and some assignments ask you to apply theory to write code.

The course also has one exam: a final.

How does my work affect my grades?

Your course grade is based on my judgment of the quality of your work and the degree of mastery you demonstrate. My judgment is influenced by your written work, by your class participation, and by your examination scores, but I give heavy consideration to written work, as indicated by this approximate system of weights:

Reflection questions interwoven with lecture videos 5%
Check-understanding questions interwoven with videos 7%
Recitations 10%
Office-hour visit to the course instructor 5%
Participation in other class activities 5%
Homework including comprehension questions 58%
Final exam 10%

The weights may be adjusted at my discretion.

How am I graded on reflection questions?

Reflection questions are interwoven with lecture videos. They ask you to think about a topic that will be covering in the associated video so that when you watch the video, you’ll be more ready to learn the material covered in the video. You are not expected to know the answers to reflection questions, just to write thoughtful responses, typically comprising a few sentences. Your response to each reflection question will be scored as either satisfactory or not satsifactory. All reflection questions for a given module will be aggregated into a single grade using the same categories we use for homework grades, which are explained below.

How am I graded on retrospective questions?

This form of question is interwoven with lecture videos. It asks you to look back on what you have learned in a series of videos and think about what you have learned and where you still have questions. Like reflection questions, retrospective questions are graded as satisfactory or not satisfactory and simply judge whether you thoughtfully engaged with the prompt. Retropsective questions will be grouped with reflection questions in your homework scores.

How am I graded on coding interlude questions?

This form of question is interwoven with lecture videos. It asks you run and then make modifications to code that you have just seen written in lecture videos. Such questions will occasionally ask you to comment on the code or the process you used to write the code. Like reflection and retrospective questions, coding interlude questions are graded as satisfactory or not satisfactory and simply judge whether you thoughtfully engaged with the prompt. Coding interlude questions will be grouped with reflection questions in your homework scores.

How am I graded on check-understanding questions?

Check-understanding questions are interwoven with lecture videos. Each such question asks about material you have just seen covered in an associated video. These questions are structured so they can be graded automatically as soon as you enter an answer so you can get immediate feedback. They are designed to help you stay engaged with the video content and make sure you understand the key material in each video. All check-your-understanding questions for a given module will be aggregated into a single grade using the same categories we use for homework grades, which are explained below.

How am I graded on reading-comprehension questions?

Reading-comprehension questions are found on each homework. Each such question guides you to a specific part of the reading and lets you know which homework problems you are ready to tackle. Each comprehension question is graded as completely correct, mostly correct, or incorrect. When all questions are mostly correct, a homework earns Very Good grades for reading comprehension. Excellent grades may sometimes be earned for completely correct answers, and a majority of mostly correct answers earn Good grades. Reasonable attempts earn Fair grades, and substantially incomplete work earns Poor grades.

How am I graded in recitation?

COMP 105 requires you to learn many new ideas and techniques. Before you can make progress on the homework, you need to understand the ideas and techniques. Recitation helps; each week it gives you practice working relevant exercises. Each recitation is graded on a three-point scale:

We drop the three lowest recitation grades, so if you have some bad days, it won’t affect your final course grades. This policy also enables you to miss up to three recitations without penalty.

Although we drop the three lowest recitation grades, we still expect you to attend every recitation. There is no such thing as an “excused absence” from recitation. If you need to miss a recitation, it is kind to let your recitation leader know, but please do not ask them to officially excuse you. If you need to miss more than three recitations, explain the situation to your academic dean, and have your dean make contact with me.

How am I graded on my office hour visit?

We find that meeting 1-1 with the course instructor early in the semester positively impacts the dynamics of the class as it reinforces that we are a team working together to help you master the material in the course. To encourage that connection, I count up to five minutes of office-hour visits as part of your course grade. Each minute you spend in conversation with me during my office hours will earn one percent of your overall course grade, up to a possible total of five percent. To earn full credit, you must come to my office hours by the end of October.
I will likely schedule extra office hours over one or more weekends to make it easier to find time to talk. While you may find it helpful to talk about homework, class, engineering, or Tufts overall, any mutually agreeable topic of conversation is acceptable.

Office-hour visits after the end of October may still count toward your course grade, but not for the full five percent.

How is my participation graded?

A portion of your grade is based on your participation in the class. This phrase encompasses a variety of activities that demonstrate you are engaged actively in managing your own learning, developing new skills, and understanding new ways of programming and problem-solving. To earn high grades for class participation, you must show that you are so engaged. You can show this engagement in a variety of ways:

Nobody has to do all of these things; you can earn top grades for class participation by doing just a few things well. What questions are appropriate? Any question about programming languages. However, it may not be appropriate to insist that every question be tracked to its lair and answered. If a question becomes inappropriate, I or another member of the teaching staff will let you know.

How is my homework graded?

Your homework grades are based on the course staff’s judgement of the quality of your work and your mastery of the material. Grades are assigned a coarse five-point scale:2

In a typical class, a consistent record of Very Good homework, together with commensurate examination grades, will lead to a course grade in the A range. If some work goes “above and beyond” and is rated Excellent, a grade of A+ is possible. Work rated Good corresponds to a wide range of passing grades centered roughly around B. Work rated Fair will lead to low but satisfactory course grades; if a significant fraction of your work is Poor, you can expect an unsatisfactory grade (D or F).

No Credit is a disaster. If 10% to 15% of your work is awarded No Credit, it is likely to cost you something like one full letter grade. Any grade, even Poor, is dramatically better then No Credit. Why? Because the worst thing you can do is to skip problems. Every problem you attempt will teach you something; when you skip a problem, you learn nothing.

With each homework assignment and exam, we will let you know our estimate of the nearest equivalent letter grade. Homework grades tend to run lower than recitation grades and participation grades, and on average, a student’s final letter grade is about one-third of a letter grade higher than their homework average. But there is a lot of variance.

What is a “minor deduction”?

Sometimes there is a fault in your code that needs to be corrected, but that does not warrant dragging a grade down from Very Good to Good or from Good to Fair. That sort of fault typically receives a “minor deduction.” Here’s the prototypical example:

It is never correct to write if P then true else false. Clean code always says just P.

A minor deduction is the rough equivalent of a “point off” out of 100 points.

What if my homework is graded incorrectly?

If we make a mistake in grading your homework assignment, you have seven days after the return of the assignment to call the mistake to our attention. File a request using the form at https://www.cs.tufts.edu/comp/105/regrade. We reserve the right to reassess your entire assignment and assign a new grade. The new grade may be higher or lower than the original grade.

What will the midterm be like?

There will not be a midterm this semester.

What will the final be like?

The final exam will be given as a set of online quizzes, each quiz corresponding roughly to what would be one question on an in-person exam. The points for the quizzes, summed up, will be your final exam score. I will post a list of the quiz titles, their point values, and the time per quiz in advance of the exam. You may take the quizzes in any order, and you will have several days over which to take the quizzes. The time for each quiz will be roughly proportional to the time that question would take on an in-person exam, plus some extra time to account for the cognitive overhead each time you start a quiz. Because of the extra time, the total time for the quizzes will add up to more than the normal two hour final exam. But, if you choose to take all the quizzes one after the other, you will be able to do them in the standard exam time as you can stay exam the whole time.

I’ll make a practice quiz available before the real exam. Although I won’t grade the practice exam, please do take it so are familiar with the mechanics and the instructions before the actual exam.

The quizzes will be made available starting on Tuesday, December 15, no later than 3:30pm ET, which corresponds to the final block for the scheduled time of the course.

What does a grade of D mean in the course?

The Tufts Bulletin states that a grade of D may be awarded in cases where a student submits work that is “unsatisfactory but allowable for credit.” In COMP 105, work that is allowable for credit earns satisfactory grades (Fair or above); work that is not satisfactory earns a failing grade (Poor). For this reason, D grades are not awarded: a record that is unsatisfactory overall earns an F.

Extraordinary circumstances may justify raising an F grade to a D. Such circumstances are very rare—roughly once every five years—and they apply at the sole discretion of the course instructor, whose decision is final.

How should I interact with people?

Engineering is not a solitary profession. To maximize your chances of success in 105 and beyond, I have designed some interactive experiences into the class.

How much interaction is too much?

Interactions and discussions with classmates must take place in human language, at a high level. You must not discuss code, algebraic laws, or contracts for functions you design yourself. You must not exchange human language, algebraic laws, pseudocode, or other information that is expressed at the level of code. If you start communicating in code or at the level of code, including algebraic laws, you’re breaking the rules.

Suspected violations will be reported to the University’s Director of Community Standards, who will investigate, decide if a violation has taken place, and if so, recommend an appropriate penalty. Be careful! As described in the university’s academic-integrity policy, the penalties for violation can be severe. A single bad decision made in a moment of weakness could lead to a permanent blot on your academic record.

The same standards apply to all homework assignments; work you submit under your name must be entirely your own work. Always acknowledge those with whom you discuss problems!

So can I post my code on github?

Code in a github repository is visible to other students. So no, you may not post your code to a github repository—unless you are very careful to make the repository private. It is certainly convenient to use github for backup and to share your work with potential employers. But it must be private. It is against course policy for you to put your homework in a public github repository—and because a public github repository can facilitate misbehavior by others, it is considered a violation of academic integrity.

How do pair-programming interactions work?

In pair programming, you work with a partner under the following constraints:

While we strongly encourage both discussion and pair programming, we are also charged with guarding Tufts’s standards of academic integrity. The following policies help ensure that these standards are upheld:

What if pair programming doesn’t work for me?

In COMP 105, you are never required to pair program. About 20% of students routinely opt not to pair program.

If you try pair programming and find it is not working, or if your programming partner disappears mid-project, proceed as follows:

How does the course staff monitor pair programming?

To try to ensure a good pair-programming experience for everyone, the course staff will choose a random sample of students to ask these questions:

The course staff will use this information to try to improve students’ pair-programming experience and to try to prevent disappointing experiences from getting worse.

Do I have a right to pair program?

Pair programming is a privilege, not a right. If you foul up and don’t fix it, I may revoke your pair-programming privileges. Fouling up consists in any of the following unacceptable behavior:

If I revoke your pair-programming privileges and you believe I have done so unfairly, you may appeal to the department TA ombudsperson, who is currently Mark Sheldon.

What is expected of my homework?

In this class, you will learn most of the material as you complete the homework assignments. The importance of homework is reflected in the weight it is assigned. Most homework for this course involves short programming assignments. Many of them are based on the text by Ramsey. There are also some larger programming assignments. And there is some theory homework, involving more proving and less programming.

As in most classes, it helps to start the homework early. But in 105, starting early seems to produce unusually good benefits. Many students report that if they start early, even if they don’t appear to make much progress, a solution will “come to them” while they are doing something else.

Another reason to start early is that if you get stuck, early help is a lot better than late help. 105 is a big course, and your difficulties could be overlooked until they get out of control. Keep an eye on yourself, and remember that a short conversation during office hours or recitation can save hours of aimless frustration.

If you complete and understand all the homework assignments, you are almost certain to do well in the course and earn a high grade. If you miss assignments or don’t really understand the homework, it will be difficult for you to earn a satisfactory grade.

The homework is relentlessly cumulative, so failure to grasp important points in early assignments will compound in later assignments. This is not a course where you can make up for early misunderstandings by cramming on later ones. This is a course where a slow-and-steady approach will win the race.

How should my homework be submitted?

Homework for each assignment is submitted using a course-specific submit script, with a name like submit105-impcore. The submit script checks to be sure you have files with the right names, and so on.5 On most assignments, there are some additional checks:

And the submit script may ask for other information:

Before running a submit script, cd to the directory in which you have placed your solutions. If the submission script complains, fix the problems and resubmit. You may submit and resubmit the same assignment as many times as you like. I encourage you to submit work early and often, even if it is incomplete, so that you have an independent check that what you plan to submit is what the submit script is expecting.

How do I get access to the submit scripts?

We provide a submission script for each assignment. To get access to those scripts, you need to execute

     use comp105

to ensure that these scripts are on your execution path. This use command should also give you access to interpreters for impcore, uscheme, and so on.

It is very convenient to put the use line in your .cshrc or .profile file, but to work around a misfeature in use you will need the line

     use -q comp105

Without the -q option you may have difficulties with scp, ssh, git, VNC, or rsync.

A submission script is named submit105-name, so for example the submission script for the first assignment is called submit105-impcore.

How should my homework be formatted?

Whether it is digital or analog, your written work must bear your name, and it must be neat and well organized. Clear English expression is required; grammar and spelling count. The same requirements apply to exams.

Every assignment should include a README file that describes the work. This description must

How should my code be written?

Your code should conform to our coding-style guidelines. Pay special attention to the offside rule. These guidelines will help your solution be understood and modified by others. Your code is graded on its conformance to these guidelines, on your explanation of what you are doing, and on your code’s functional correctness.

You will notice that the code from the book does not conform to all of the guidelines in the handout—especially the guidelines on layout. That’s because the book code is written as a literate program. If you wish to submit your own code as a literate program, you may. And you may choose whether you wish to work with the bare or the commented versions of the code in the book.

How will the structure of my code be evaluated?

The structure and organization of your code is evaluated according to our general coding rubric.

How will the correctness of my code be evaluated?

Submitted code is typically evaluated by automated testing. Our test scripts aim to explain why you got the grade you did, and if you made a mistake, what it was. On most assignments, you can expected grades to be assigned according to the following criteria:

In summary, Very Good code is expected to be faultless. Faulty code normally earns a Fair grade, but if the faults are very minor, it might earn a Good grade, and if the faults are grave, it might earn a Poor grade.

Code that writes to standard output or standard error, unless such output is called for in the problem specification, is at risk of earning No Credit. Use print and println at your peril!

Should I use LaTeX to write theory homework?

No. LaTeX and the mathpartir package do make it possible to typeset clear, legible inference rules, derivations, and proofs. That makes it easy for the course staff to read your work. But unless you already have experience using LaTeX to typeset mathematics, I recommend against using it. LaTeX is a power tool, but it’s hard to learn, and it provides terrible error messages. In COMP 105, you will be learning plenty of other power tools; learn LaTeX some other time.

If, however, you already know LaTeX, you may benefit by emulating our LaTeX source code for a simple proof system or Sam Guyer’s LaTex source code for typesetting operational semantics.

Then how should theory homework be written?

Use pencil and paper. (Microsoft Word, Open Office, and that ilk are even worse choices than LaTeX—they aren’t set up to handle even simple math, let alone inference rules.) Of course, you need to submit PDF. Here are two ways to get it:

Any PDFs you submit will be emailed back to you automatically. Use the automated email to confirm that the PDF was correctly transferred to the homework server, that it opens, and that it displays your work as you expect.

How may I use the library?

You may look in the library (including the Internet, etc.) for ideas on how to solve homework problems, just as you may discuss problems with your classmates. But using the library is never required; everything you need to know can be found in lecture, in recitation, on the course web site, or in one of the books.

Some students rely heavily on the library. Although this behavior is permissible, I discourage it. I assign homework problems not because I want to know the answers, but because doing homework is the best way for you to learn. While library skills are important in our profession, the homework in this course is designed to develop other skills that are even more important. Remember, you will not have the library with you when you write your exams or go on job interviews!

If you do use the library, the Internet, or other outside sources, your homework must acknowledge the use of these sources, even if you find little or nothing useful.

How may I use code I find on the Internet?

Any code that is posted to the official Tufts COMP 105 web site is permissible for you to use. You must not download any other code from the Internet. You certainly may not submit it as part of a homework assignment.

May I use code from the book?

Absolutely! Any code from either of the books is fair game for you to use. Most of this code is provided in machine-readable form in /comp/105/build-prove-compare. Help yourself!

Several of the later homework assignments—especially around type systems—are feasible only with the support of code from the book.

How should I use Wikipedia?

Don’t. Wikipedia is a terrible source of information on programming languages. Many of the entries are just plain wrong, and Wikipedia’s rules make it nearly impossible for experts to correct bad articles. You don’t yet have enough experience to identify bad information, so don’t use Wikipedia for 105.

What does an extra-credit problem mean?

Most homework assignments will offer opportunities to earn extra credit. I use extra credit to adjust final letter grades. For example, if your grade average falls in the borderline between A- and B+, I will assign you the higher grade at my discretion if you have done significant extra-credit work. I will also mention extra credit if I write you a letter of recommendation. Extra credit is just that: extra. You can earn an A or A+ without doing any extra credit.

What if I can’t get my homework in on time?

Homework is typically due at 11:59 PM on a Monday, Tuesday, or Wednesday. We will grant an automatic extension of fifteen minutes at no cost to you. If you plan on submitting your work at midnight, you will have fourteen minutes for last-minute changes.

We expect your homework to be submitted on time. But we recognize that the exigencies of college life occasionally interfere. If you have difficulty, you have several options:

After the 24-hour extension deadline has passed, model solutions will be available on the Web or distributed as hard copy, making further extensions extremely unlikely.

What if my partner is out of extension tokens?

If you are pair programming with another student, and you need to submit work a day late, both partners are charged an extension token. If your partner is out of extension tokens, your only choices are to submit on time or to get a “no-fault divorce” and submit separately. After the divorce, both students have equal rights to all common work, but only the student who still has tokens can submit late. At submission time, both submissions must be identified as individual work (list nobody as the programming partner). Submitting as a partnership is likely to harm one or both grades. The true situation should be explained in the README file.

What if I can’t finish all the problems?

If you can’t finish every problem, act tactically to maximize your grade:

105 is very cumulative, so if you can’t finish every problem, you’ll also want to act strategically to maximize the chances that you can do better on the next assignment. Your best strategic choice depends on the details of the assignment, so ask the course staff.

What is expected in lecture?

In-person lectures will be replaced by a series of videos interleaved with reflection and check-your-understanding questions. The videos for the each week will be released the preceding Friday. You should plan to watch the videos and answer the corresponding questions no later than your recitation session, which will be sometime between Wednesday late afternoon and Friday morning. The recitation material assumes you have already watched and actively engaged with the video content.

When watching the videos, I expect you to maximize your learning by actively engaging with the short videos and associated questions and by eliminating distractions that might interfere with your learning.

Should I take notes? How?

To maximize your learning, I recommend that you take notes, sketches, and diagrams by hand. Paper is good, with a pen or pencil. If you have a large touch screen and can take notes with a stylus, that works, too. I recommend against using a keyboard with a standard laptop or word-processing software:

You never need to copy the instructor’s notes or slides; they are available online. Use your own notes to make connections and to highlight points that you find difficult or that you want to remember.

What is expected in recitation?

Recitation helps deepen your knowledge of the course material, and it helps you learn to work in a way that promotes insight and defends you against overwork and exhaustion. Recitation is structured around practice on problems related to current homework assignments.

Recitation is mandatory, and your participation is graded.

Which recitation do I attend?

Attend the recitation you signed up for on SIS when you registered for COMP 105. In order to create a small-group learning environment, we cap the enrollment of each recitation section. This cap is strictly enforced.

If your recitation section has been cancelled, or if there is another reason you need to change recitations, please make a private post on Piazza with the following information:

What logistics and policies affect my homework?

Here is a summary of relevant information that is distributed throughout this syllabus:

I’m not required to take 105. Should I take it anyway?

COMP 105 is required for Computer Science majors. If you’re not a Computer Science major, find the paragraph that applies to you below.

If you’re getting a Computer Science minor, or if you’re just interested in computing, you should take 105 if you want an intense experience that will broaden and deepen your programming skills. (Unless you have a professional or recreational interest in mathematics or logic, some of the theory parts of the course may be less interesting to you.)

If you’re a postbac student or a master’s student, you also should take 105 if you want an intense experience that will broaden and deepen your programming skills. Many of our postbac students, in particular, report that 105 was a highlight of their certificate program. Postbac students and master’s students do need to be aware that as part of Tufts’s commitment to residential learning, the course is designed to serve undergraduate students who are on campus during the day.

If you’re a doctoral student or MS/PhD student, the value of 105 depends on what you are trying to accomplish.

What skills must I have already?

COMP 105 is the final course in our required programming sequence, and it calls on a broad and deep array of skills you are expected to have developed in earlier courses.

What basic skills do I need?

You must grasp basic algorithms, data structures, and good programming practice.

What Unix skills do I need?

You must understand the basics of files, directories, creating and editing files, printing, compiling and loading programs, and using make. You will be much, much happier if you also can write a simple shell script (sh) and use Awk and grep effectively. You can learn about such things from Kernighan and Pike.

What file-transfer skills do I need?

If, as we recommend, you do your theory homework on paper, you need to know how to convert it to PDF and to get the PDF onto a departmental Linux machine.

What theory skills do I need?

You must be comfortable with basic discrete mathematics. You must be able to prove theorems, especially by induction.

You must have taken Discrete Math (Math 61 or COMP 61). If you have not, you must produce some other evidence that you can reason precisely about computational objects.

You must be able to write an informal mathematical proof. For example, you should be able to prove that a sort function returns the same set of elements that it was passed.

You must be comfortable using basic mathematical formulas with “forall” (∀) and “exists” (∃) quantifiers, i.e., the propositional and predicate calculi.

You must know basic set theory, e.g., the mathematical definition of functions as sets of ordered pairs.

You must be comfortable reading and writing formal mathematical notation, or at least be able to look at it without running screaming from the room.

What programming skills do I need?

You must have substantial programming experience. If you don’t, you will have difficulty keeping up with the homework.

A few homework assignments require some proficiency in C. If you have a strong background in C++, some details will be different, but your background should be sufficient.

Your programming experience should include work with dynamically allocated data structures and with recursive functions. You must be comfortable writing recursive functions in the language of your choice, as well as proving that such functions terminate.

You must have implemented some of the basic data structures and algorithms used in computer science, like stacks, queues, lists, tables, search trees, standard sorts (quick, insertion, merge, heap), topological sort, and graph algorithms. These topics are well covered in COMP 15 at Tufts. Prior exposure to exhaustive search (backtracking) will also be helpful.

What other programming skills might help?

It really helps to have some facility with systematic software design. Our recommended nine-step design process is a solid starting point, but if you have practice with additional design methods, you will prosper. Many of the most effective design methods are grounded in formal reasoning about programs, including the following intellectual tools:

You can brush up on this material by looking at the article by Bentley on the reading list. Chapter 4 of Liskov and Guttag has a nice tutorial on reasoning about data, which you will find helpful in several assignments.

What is the most important skill of all?

The most valuable skill you can have for COMP 105 is the skill of managing yourself. To do well in 105 or in any other course that involves programming, develop these habits:

If you have these habits, the other prerequisites are almost irrelevant. If you don’t, you can expect difficulty no matter what other background you have.

What books do I need?

You absolutely, positively have to have the book Programming Languages: Build, Prove, and Compare by Norman Ramsey. And you have to have the August 2020 edition—older editions will not do. You can buy the book in the Computer Science office in Halligan. We will post information about times to purchase and pick up the book on Piazza. When you buy the book, nobody profits: the intellectual property is donated; the copies are printed by the University printing office; and the department sells the book for a sum just sufficient to cover the cost of printing. If you are not able to pick up the book in the CS department office, we will mail a copy of it to you. For the price of the printed copy, you will also be able to download a pdf copy of the textbook.

The short booklet Seven Lessons in Program Design is available online.

The book Elements of ML Programming by Jeff Ullman is very useful, but just for a few assignments. If need be, you can get by without it; we have assembled an extensive ML learning guide that uses entirely free resources. We recommend Ullman’s book anyway, because we think that spending the extra money will save you enough time to be a good tradeoff. If you do buy the book, be sure you get the ML’97 edition. It is available in the University bookstore, but you can probably get it more cheaply elsewhere.

What computers can I use?

The class is set up to run on Red Hat Enterprise 64-bit Linux, as installed on the departmental homework server. For remote access use homework.cs.tufts.edu. The software from the book will be installed on these machines, but you can also grab the software and compile it on your own computer; try git clone homework.cs.tufts.edu:/comp/105/build-prove-compare.

If you need an account for CS machines, please send email to staff@cs.tufts.edu. I recommend that you ask for bash or fish as your login shell.

What software can smooth my path?

I recommend a wonderful program called ledit, which is extremely handy for interacting with our interpreters. Try typing, e.g., ledit impcore, and you will be able to get an interactive editing loop with the impcore interpreter. The ledit program is already installed on the departmental servers, and it can also be downloaded from INRIA and installed on your own machine.

I also recommend using a “programmer’s editor” such as vim or emacs. A most valuable feature of such editors is the ability to jump directly to the source location of an error. For vim you will need to learn the :make command, and you will probably need to set makeprg. For emacs you will need to learn the M-x compile command.

How about Emacs tricks?

If you do use emacs, you will find your code much easier to manage if you enable paren-mode, which you can do by placing these lines in your .emacs file:

  (require 'paren)
  (show-paren-mode)
  (setq show-paren-style 'expression)

I also recommend using the M-x customize-face command with face show-paren-match to set the screen to bright yellow on parenthesis match.

You can use the Emacs TRAMP facility to edit files directly on the remote server, by using file names like /nr@homework.cs.tufts.edu:/comp/105/www/syllabus.md. This allows you to edit on your own local machine, but every time you save the file, it is automatically sent to the homework server, where you can compile or run it.

What if campus closes unexpectedly?

We will continue fully online. In-person recitations will move online, as will in-person office hours. Everything else will continue as planned.

What may I do with solutions?

I provide solutions to all homework and exam questions. Being able to examine master solutions helps you learn. But I provide solutions for your private use only. Please do not share them with other students, and please make sure they do not find their way into public places, archives, and so on.

Copying solutions, whether from me or from another student, is a serious violation of academic integrity. Providing solutions to be copied is equally serious.

What if I am repeating the course?

If you are repeating the course, we expect you to abide by the following policies.

What else do I need to know about academic integrity?

The course operates under the university’s academic-integrity policy, which you must know. In addition, you must know that in COMP 105, seeing another student’s code is an integrity violation, and so is allowing another student to see your code. I am mandated to report even the suspicion of an integrity violation.

Where else might I go to get help?

The StAAR Center (formerly the Academic Resource Center and Student Accessibility Services) offers a variety of resources to all students (both undergraduate and graduate) in the Schools of Arts and Sciences, and Engineering, the SMFA, and The Fletcher School; services are free to all enrolled students. Students may make an appointment to work on any writing-related project or assignment, attend subject tutoring in a variety of disciplines, or meet with an academic coach to hone fundamental academic skills like time management or overcoming procrastination. Students can make an appointment for any of these services by visiting go.tufts.edu/TutorFinder, or by visiting go.tufts.edu/StAARCenter.

What if I have a problem with a TA?

If you have concerns about anyone on the teaching staff, please raise the issue with a member of the senior teaching staff or the course instructor. If you don’t feel comfortable approaching anyone associated with the course, please reach out to the department TA ombudsperson, who is currently Mark Sheldon.

The TA ombudsperson (AKA TA liaison) is here to help mediate conflicts that arise involving TAs. Specifically, the TA ombudsperson/liaison will help with the following situations:

If you are involved in or aware of such an issue, please contact the TA ombudsperson, Mark Sheldon, at ta-ombudsperson@cs.tufts.edu or ta-liaison@cs.tufts.edu. If you are one of Mark’s students or TAs and are not comfortable discussing the issue with him, please contact the back-up TA ombudsperson, Prof. Megan Monroe, at mmonroe@cs.tufts.edu.

I’m different. Am I really welcome here?

Yes! We strive to create a learning environment that welcomes students of all backgrounds. If you feel unwelcome for any reason, please let us know so we can work to make things better. Talk to anyone on the teaching staff, or if that feels uncomfortable, try your academic advisor, the department TA ombudsperson (who can be reached by emailing ta-ombudsperson@cs.tufts.edu), our department chair, or your dean.

COMP 105 can be especially difficult for first-generation college students and for members of groups that are underrepresented in computing, who may not have the family or social support that helps them develop their skills in “how to be a college student.” If you are a first-generation college student or a member of group that is underrepresented in computer science, I encourage you to have your “five minutes with the professor” visit early in the term, and we can talk about your support system.

Acknowledgments

Norman Ramsey wrote the great majority of this syllabus. Kathleen Fisher wrote the portions related to online instruction. Jared Chandler, Alex Chandler, and Jeff Foster also contributed. Norman would like to thank Annie Soisson for help with syllabi in general.

  1. Lisa Feldman Barrett, “How to Become a ‘Superager’”, New York Times, Dec. 31, 2016↩

  2. It is the same scale used by the National Science Foundation and by Consumer Reports.↩

  3. By definition, it is not possible for the entire class to excel. The normal top grade is Very Good, and students who consistently produce Very Good work earn A’s. Grades of Excellent are awarded only in cases of true distinction. This means, for example, that if everyone in the class turns in a perfect solution, all those perfect solutions are judged Very Good.↩

  4. Change made on account of COVID-19↩

  5. We hope one day to get provide to take care of these checks for us, but we’re not there yet. Please don’t submit homework using provide.↩

  6. When writing recursive functions, try to develop your understanding of the deep connections between recursion and loops; the ideas of invariants and termination conditions apply to both.↩