CSC 430, Fall 2020
1 Fall 2020 Special Note
2 About the Course
3 Learning Outcomes
3.1 Bonus Topics
4 Prerequisites
5 Names, Times, Locations
5.1 Instructor
5.2 Lecture & Lab
5.3 Google Calendar
5.4 Web Page
6 Lecture Classroom, Fall 2020
7 Fall 2020 Team Submissions
8 Computing Environment
9 Version Control
9.1 Typed Racket
9.2 Installing the Handin Server
10 Readings
10.1 plai-typed and typed/  racket
11 Communication
12 Honesty
13 Labs
13.1 Fall 2020 Labs
14 Assignments
15 Grading Code
15.1 Code Organization
15.2 "But it Works!"
15.3 Grading Time Limit
15.4 Grading code in 430
15.5 Common Errors
16 Interacting with the Handin Server
16.1 Fall 2020 Team Handin
17 Quizzes and Exams
18 Grades
18.1 Basic Mastery
19 Checking your Grade
7.8.0.11

CSC 430, Fall 2020

1 Fall 2020 Special Note

Whoa, it’s Fall now, and everything’s back to normal.

^L

SURPRISE! No, it’s not.

Here we go with this crazy crazy thing again.

As always, my highest-level goal is to make the world a better place, and to make you happier, healthier, and better able to make the world a better place yourselves.

So, what exactly does that have to do with programming languages? Well, the tools and ideas of programming languages *can* be deep ones that affect the way you work and think for the rest of your life. Or, at a much lower level, maybe I can help you write programs a bit more carefully and correctly. It’s up to you! (Well, I suppose it’s partly my fault if it doesn’t work out right, too.)

One of the biggest challenges—as in the Spring—is going to be providing an engaging (heard that word much recently?) experience, and to try to provide a space for you to connect with your fellow students, as well as your instructional team (basically, me & Professor Van De Vanter).

We’re going to try to be flexible, while still pushing you to expand your horizons and discover some new ideas. This course is always an experiment-in-process, but these last two quarters have been more experimental than most. Fingers crossed, let’s see what happens!

2 About the Course

Programming languages determine what programs we can write. Languages with nice abstractions allow us to write elegant, concise, and readable programs.

In this class, we’ll start from scratch, and build a programming language by adding only what’s necessary. What we’ll discover is that this simplistic approach leads to some really powerful abstractions. You can do more with less!

At the end of the course, you should be a better programmer. You should also have a clearer picture of a given language as a choice in a larger design space, and be better able to understand new programming languages and the similarities between them. Finally, you may develop some taste for what you like in a programming language.

This course will involve lots of programming in Racket. I choose Racket for several reasons. First, “functional” programming languages make this kind of course feasible. Writing a series of interpreters in another language would probably involve a whole lot more code. Secondly, Racket is a simple language for you to learn, without complex syntactic rules or a confusing type system. Thirdly, the simplicity of Racket makes it an ideal “blank slate” for adding features. If these reasons don’t make sense to you, then... perhaps you need to take the course!

3 Learning Outcomes

Here are the course outcomes that I’m striving for:
  • You can write programs in a largely functional language (i.e. ML, Racket).

  • You can identify expressions and other syntactic elements of a language that you know or are learning.

  • You can perform simple parsing by hand, transforming textual strings into abstract syntax trees.

  • You can apply standard reduction rules for the following language forms to compute the results of programs, including these forms:
    • arithmetic & other primitive function applications

    • function calls / variable references

    • mutation forms

  • You can write programs to produce these same results (a.k.a. interpreters), up to families of similar reduction rules.

  • You understand the relationship between substitution and environments, and can model a computation’s progress using either model.

  • You understand the notion of scope induced by these rules, and can identify and reason about the bindings and bound variables in arbitrary programs.

  • You have a limited ability to read and understand programs written in store-passing style.

  • You have a limited ability to transform code using mutation into purely functional code, using store-passing style

  • You can apply the rules of a type-checker (given as Gentzen-style natural deduction rules) to determine whether a program satisfies a type system.

  • You can explain why these systems work the way they do, and have a limited ability to consider variations of these systems and how such variant systems would behave.

3.1 Bonus Topics

We usually get to one of these:

4 Prerequisites

In order to take this course you must be able to design and implement small programs (~ 1 KLOC) efficiently. You must have a basic understanding of mathematics and data structures. You should be able to reduce arithmetic expressions by hand, in a small-step style (that is, one step at a time). You should be able to identify statements and expressions in a programming language such as Java, Python, or C.

5 Names, Times, Locations

5.1 Instructor

5.2 Lecture & Lab

Section 01/02:

Section 03/04:

5.3 Google Calendar

See my home page for my calendar. You can add it to your calendar, if that makes your life easier.

Office hours also appear on this calendar; you may find them easier to see if you click on the "week" tab of the calendar.

5.4 Web Page

This is the course web page, its link is https://www.brinckerhoff.org/clements/2208-csc430/.

6 Lecture Classroom, Fall 2020

Hmm... I think the "no laptops" rule isn’t going to work well, this quarter.

I do think that engagement is going to be a huge challenge; you’re almost certainly going to be engaging with the classroom through a small rectangular picture and a pair of headphones, which is a totally different experience from actually being there in a classroom.

Despite this, there are some things that we can do to try to bring us all into the same mental space; first among these is this: when you are in class or lab, I expect you to have a camera turned on.

I’m aware that this is not a small request, and I don’t make it lightly. I realize that having a camera pointed at your face is exhausting, and that in a virtual space, you have far less sense of the space around you. However, without a camera, your classmates have a much harder time getting to know you, and I have a much harder time getting to know you.

Why is it so important for your classmates (and me) to get to know you? In essence, that’s the main difference between Cal Poly and Khan Academy; at Cal Poly, we’re working together to help you learn. That can mean slowing down and finding new ways to explain and understand, it can mean teaching and learning from your classmates, and it can mean going off on interesting tangents that you’re interested in. Courses at Cal Poly should genuinely be interactive, with the course material responding to you, as well as vice versa.

Please talk to me if there are specific circumstances that prevent you from having a camera on; now that we live in a world where phones have cameras, there are fewer obstacles, but I’m happy to discuss things with you one-on-one.

7 Fall 2020 Team Submissions

This quarter, we’re going to be working in teams of three, or four. I’ll be forming the groups with the input of surveys that you complete, and a large dose of random-number-generator.

If you already know other people in the course that you want to work with, you’ll have an opportunity to specify that in the team formation survey. I want to help you to work with the group that will help you learn.

There may be some of you that have no desire to work on a team. That’s fine with me, and I’m happy to grade your work individually. However, I do want to know this in advance. If you want to work individually, specify that on the team formation survey, and I’ll put you in a special "anti-team" team, that consists of people that want to work individually.

For the rest of you, that are interested in working in teams, I’ll require you to submit your assignments as part of your team, as specified in the handin instructions below. Note that some coordination on your part is probably a good idea; if Pat and Alex are on the same team but not in contact with each other, it might be that Alex submits after Pat, but Pat doesn’t know it, and is surprised later to discover that the graded assignment isn’t the one that they expected.

8 Computing Environment

You will be required to complete the assignments in this class using Racket, version 7.8 or later. It is freely available for all major platforms, including Mac OS, Windows, and UNIX.

Most of you will probably want to use the IDE, DrRacket, which is a part of this package.

9 Version Control

Version control is important in this class and every class in which you write programs of more than 50 lines. I personally use private git repos on both github and bitbucket. Remember, it’s not whether you lose data, but when. For Heaven’s sake, though, make sure they’re private repos. (See the Honesty section, below)

9.1 Typed Racket

We’re going to be using the Typed Racket language for this course.

Racket (just plain Racket) is a functional programming language based on Scheme. Okay, I’ll be honest; we used to be the largest Scheme implementation, and we decided it would make more sense just to rebrand ourselves as a new language. Clojure did it, right? So the MzScheme project became the Racket project, and VOILA we’re a brand new language.

Functional programming gives you new ways to think about programs, and pushes you toward solutions that are more high-level, more portable, and more likely to be correct.

Depending on your background, writing programs functionally may be a challenge for you; as we’ll discuss, functional programming challenges you to step away from the notion of "time" as a part of computation, and that can be a big step, if your notions of computation are tightly tied to the notion of time.

When it comes to the tasks that we’re tackling in this particular course—that is, implementing languages—functional programming languages are kind of perfect. You could write all of this stuff in Java or C++, but it would be a lot of extra work.

Although, having said that, nearly all languages are now developing a fairly complete suite of functional tools, so using (say) Java for these tasks is more feasible now that it has been before.

But wait... what about the "Typed" part?

Typed Racket has a ground-breaking type system that uses "occurrence typing" to allow union types in a statically typed language in a computationally tractable way. See this paper for details, if you’re interested. This type system originated in Racket, but is now used in a variety of gradually typed languages, such as TypeScript.

Also, there are a variety of introductions to Racket and/or Typed Racket that may be useful to you:

Also, in order to simplify the task of writing in Typed Racket, I’ve written up some Hints on Using Typed Racket in CSC 430.

Finally, here are some Helpful Tidbits.

9.2 Installing the Handin Server

In order to hand in your work, you’ll need a plugin.

Now, you should be ready to hand in.

10 Readings

The majority of the readings in this course will be from Programming Languages: Application and Interpretation, second edition, by Shriram Krishnamurthi.

We may also be reading smaller essays by language designers, as supplemental material.

10.1 plai-typed and typed/racket

As mentioned above, we will be writing our code in this class in the frighteningly awesome typed/racket language. The textbook is written using the plai-typed language. There are differences. In order to make your lives slightly less difficult, I’ve translated the code from the first few chapters from plai-typed to typed/racket to make them more applicable to your code.

./CodeFromClass/PLAI-TR-translation.rkt

11 Communication

This class will use Piazza. This will be the principal means that I’ll use to notify you of deadlines, organizational updates, and changes to assignments. If you’re not keeping up with the group, you’re going to be missing important information.

It’s also the best way for you to direct questions to me and/or the class. Feel free to e-mail me with personal questions, but use the Piazza group as your main means of communication. It’s possible to post anonymously, if you like.

You should already have received an invitation to the Piazza group; let me know if you need an invite.

Don’t post your code or test cases to the group; anything else is fair game.

Also, please keep in mind that I (and everyone else) judge you based in part on your written communication. Spelling, complete sentences, and evidence of forethought are important in all of your posts & e-mails. One easy rule of thumb: just read over what you’ve written before clicking post or send, and imagine others in the class reading it.

12 Honesty

We strongly encourage collaboration among students in almost every aspect of the course. See, for example, the following section on "Labs", which are designed for collaboration.

The exception is for programming assignments: you may not copy another student’s code, not even test cases. You are also responsible that no other students see your code, either during this course or afterwards, either deliberately or through negligence (e.g. via a non-private repo).

A very effective automated tool will review submissions for evidence of copying. Students believed to be cheating, i.e. both parties involved in a transfer of code, will in the first instance typically receive a 0 score for the assignment. We reserve the right to assign a failing grade in the class when appropriate.

13 Labs

Labs in this course take the form of simple exercises to be completed in a week during lab periods, designed to help you understand the lecture material and to lead you toward solutions for the larger assignments.

I’ll be checking these off during the lab; you’re responsible for demo-ing your lab solutions for me. Your marks on these labs will be simple credit/no-credit.

The labs will be due at the end of your lab period on the day specified, typically Friday. If we run out of time to check them, I will generally elect to accept them during the following lab session, but you cannot rely on this occurrence; the labs are due on the day specified on the schedule.

In labs, you are heartily encouraged to collaborate like crazy. Look at everyone else’s code, copy and paste, type on your neighbor’s keyboard, whatever. Labs need not be entirely your own work.

When you successfully demonstrate a lab, I will give you a number. You may enter these numbers at http://johnlewis.brinckerhoff.org:8026/servlets/standalone.rkt (also linked from the top of this page).

13.1 Fall 2020 Labs

In an online setting, it may be less obvious what the role of labs is. The principal goal, as usual, is to build your understanding in an environment where you can collaborate freely. The second goal, though, is to allow (force?) you to spend more time with your classmates.

In this quarter, labs will generally be held in breakout rooms, in one of two configurations; either you will be in a breakout room just with your team, or you will be in a larger room of about three teams, that I call a "miniclass" because hey why not.

The advantage of a miniclass over the standard full-class section is that it should be easier for you to ask questions and discuss things with others. The advantage of a miniclass over the more granular one-room-per-team setup is that I can actually feasibly spend a reasonable amount of time in each room; when we have ten team breakout rooms, I’m hopping like a sparrow between breakout rooms and it’s easy to get the impression that maybe I’ve abandoned the whole class. (This is not generally the case.)

14 Assignments

Programming assignments will be due at 10:00 PM. You must submit homework assignments using the Handin button in DrRacket. Late assignments will not be accepted.

From time to time, we may examine student code in lecture. Try to ensure that the code you submit is something you’d be proud to show to the others in the class.

Late Policy: Except for exceptional circumstances, late assignments will be given 0 points.

15 Grading Code

I will be grading your code repeatedly in this class. On most assignments, your score will consist of a part (usually 20 points) based on your performance on a set of test cases automatically administered by the handin server, and a part (usually 6 points) based on my opinion of your code’s clarity, organization, and adherence to rules about purpose statements and contracts/types (in short: you’ve got to have them). As a rule, my "eyeball" score rubric runs something like this:

Finally, please note that I will place comments in some of your submissions indicating errors or stylistic requests. These will all begin with the string ;;> (in Racket) or ##> (in Python), so you can search for these in the e-mail that you get with your final assignment grade.

15.1 Code Organization

Here’s the most important thing to know about code in this class: I do actually read it. That means that—like most code you’ll write in industry—it neads to be readable and clear. If your code isn’t predictable and understandable, it will be ripped out and replaced, probably by someone who’s grumpy.

This means that getting your code to work is not the end of the process; after you get your code to work, you have to clean it up, put nice headers on the various parts, collect the test cases, document strange things that you did, and clarify the code.

You should begin with a single-paragraph comment that describes how far you got: did you finish, or did you get stuck on something? If you got stuck, describe what’s done and what’s still left to implement.

As a rule, I like to read code in a "top-down" way. This means that the definition of the top-level, important functions should come first, and the supporting functions should come later. I want to have a good understanding of the big picture before getting into the details. My experience is that if interp makes sense, then add-to-env will probably not present any difficulty.

Another part of cleaning up the code is collecting the test cases in a place that’s sensible and doesn’t interrupt the flow of reading the code. It’s probably best–after you’re done writing the code–to collect the test cases at the bottom of the file (or put them in another file altogether, if appropriate).

Whatever language you use, it’s likely to have a style guide. Here’s the one for Racket. You’re not required to follow any style guide, but anything that makes your code hard to read could hurt your score.

Finally: dead code is misleading and makes code hard to read. Delete it.

15.2 "But it Works!"

I reserve the right to assign bad scores to programs that work correctly; if I don’t think you’re doing a good job of programming, then you won’t receive a good score. "It works" isn’t a defense for bad code.

15.3 Grading Time Limit

Good code is easy to read. I reserve the right to allocate a fixed period of time to grading a program submission. Don’t be surprised to see comments like "ran out of grading time here."

Naturally, all grades contain an element of subjectivity.

15.4 Grading code in 430

For most of the assignments in this class, I’ll expect to see these things at the top, in this order:
  • Types and Data Structures,

  • the definition of top-interp,

  • the definition of interp, and

  • the rest of the program.

Per the style guide, please don’t follow the "one closing brace per line" style that’s common in Java and C; your Racket code will be reasonably deeply nested, and this convention causes such programs to consume huge amounts of vertical space.

15.5 Common Errors

Also, see my discussion of specific common errors in this class.

16 Interacting with the Handin Server

You will be handing in your work in this class using a plugin for DrRacket that communicates with a handin server running remotely. From past experience, there are several things that may not be obvious about your interactions with this server.

16.1 Fall 2020 Team Handin

In order to submit as a team using the CSC430 handin plugin, you need to specify all of the user ids in the "username" box, separated by pluses. So, for instance, if I were submitting with Ichabod Crane and Florence Nightingale, I might put

  clements+icrane+fnighti

... in the username box. The ordering of the names doesn’t matter; putting the names in a different order puts the submission in the same "box".

17 Quizzes and Exams

My experience suggests that frequent quizzes are a good way to ensure that you’re understanding what I’m teaching, and that I’m teaching things that you understand.

This class will have quizzes on Wednesdays, probably during the first six or seven weeks of the class. These quizzes will probably be fifteen minutes long, and will probably take place during lab.

There will be a midterm and a final exam in the course. The midterm will be during the lecture period in the sixth week of class. The quizzes and exams will be closed-note. No electronic devices, including calculators, phones, or mp3 players, will be permitted during the quizzes or exams.

18 Grades

Grades will be determined by performance on programming projects, the exams, and class interaction. A small fraction of the grade is determined by the labs, and by the instructor’s whim. The breakdown of the grade is as follows:

18.1 Basic Mastery

In addition to the standard grading scheme given above, there is also a different "Basic Mastery" way to earn a passing grade in this course. Specifically, in the final four weeks of the course, you will have an option to re-submit your first four assignments, your first four labs, and to re-take the first midterm exam. If your iteratively perfected first assignments are all (eventually) passing all test cases and well-styled, and your labs are complete, and you pass the first midterm with a score of 80% or higher, you are guaranteed a C in the course.

Please note that while it’s not a bad idea to discuss your plans with me, you absolutely do not have to make a choice between the standard path and the basic mastery path. Also, the basic mastery path is guaranteed not to hurt your grade; if you complete the basic mastery but your computed grade is higher than a C, you will receive the higher grade. If, on the other hand, your computed grade is lower, then you will receive a C.

19 Checking your Grade

I like to share your current grade in the class with you. It usually takes me a few weeks to get this set up, but you should eventually be able to check your student grade at

https://users.csc.calpoly.edu/~clements/student-grades/<your-login>/current-grade.txt

That’s not a clickable link, because you’ll have to edit it to add your login. So, for instance, if your name is Annette Czernikoff and your login is aczernik@calpoly.edu, you’d put aczernik in the login spot.