CSC 430, Winter 2024🔗

1 Welcome!🔗

It’s Winter! Snowmen! Sleds! Something like that.

As always, our 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 we can help you write programs a bit more carefully and correctly. It’s up to you! (Well, I suppose it’s partly our fault if it doesn’t work out right, too.)

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. Second, Racket is a wonderful, beautiful language that is probably pretty dramatically different from other languages that you’ve used. (You can tell I’m totally not biased at all.) Finally, as one of the developers of Racket, running this course in Racket creates a positive feedback loop; your experiences can help to improve the language, especially since Racket is a language that can easily be extended and updated. If these reasons don’t make sense to you, then... perhaps you need to take the course!

3 Learning Outcomes🔗

3.1 Bonus Topics🔗

We usually get to one of these:

• parsing,

• macros, or

• somewhat more advanced type systems, or

• continuation-passing-style, specifically:

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

  • You have a limited ability to transform code written in a direct style into continuation-passing style.

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 Python. Actually, scratch the "such as"; in order to present examples in class, we are planning to use Python as the language that we assume that you already know. If you can’t read Python code, please let us know and we will try to accommodate your skillset by providing resources to get you up to speed in Python.

5 Names, Times, Locations🔗

5.1 Instructor🔗

• Brian Jones, btjones@calpoly.edu

• John Clements, clements@calpoly.edu

5.2 Lecture & Lab🔗

Section 03/04 (Jones):

• Lecture: 11:10–12:00, MWF, room 33-457

• Lab: 12:10–13:00, MWF, room 14-302

Section 05/06 (Clements):

• Lecture: 14:10–15:00, MWF, room 186-C301

• Lab: 15:10–16:00, MWF, room 14-302

Section 07/08 (Jones):

• Lecture: 15:10–16:00, MWF, room 20-129

• Lab: 16:10–17:00, MWF, room 14-257

5.3 Office Hours🔗

• Brian Jones: https://users.csc.calpoly.edu/~btjones/

• John Clements: https://brinckerhoff.org/index.html

5.4 Web Page🔗

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

6 Winter 2024 Team Submissions🔗

This quarter, we’re planning to be working in teams of two. We’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 another person in the course that you want to work with, you’ll have an opportunity to specify that in the team formation survey. We want to help you to work with the person that will help you learn.

There may be some of you that have no desire to work in a pair. That’s fine, and we’re happy to grade your work individually. However, we do want to know this in advance. If you want to work individually, specify that on the pair formation survey.

For the rest of you, that are interested in working in pairs, we’ll require you to submit your assignments as part of your pair, 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.

7 Lecture Classroom🔗

I think that an interactive and lively classroom is a better learning environment. In particular, I will almost certainly learn everyone’s name, and I’m likely to notice if you’re missing. My experience is that if you come to class reliably, you’re extremely likely to pass the class—there’s a reason that we conduct classes face-to-face; it keeps you engaged, and ensures that you’re connected to the other students in the class.

In addition, I’m likely to call on you, in places during the lecture where I want to see if you’re following what’s going on. If you don’t know, it’s totally fine to say "no, I have no idea." In particular, this is probably evidence that I’m going too fast or not explaining things well. However, I try to respect the wishes of students for whom this technique is disruptive. Please let me know if you don’t want me to call on you.

Finally, my experience standing in front of classes and more especially my experience of sitting behind classes has convinced me that laptops are useful for note-taking in approximately 1% of cases. Essentially, never.

Indeed, there’s now a mountain of evidence indicating that laptops are distracting to students and to those around them, and that even when these distractions are eliminated, taking notes on laptops fails to create learning in effective ways. I’ll just cite this one paper, because it’s got copious references to other sources.

• Mueller, Pam A., and Daniel M. Oppenheimer. "The pen is mightier than the keyboard: Advantages of longhand over laptop note taking." Psychological science 25.6 (2014): 1159-1168.

For this reason, I do not allow the use of laptops in class without special dispensation. If you need to use a laptop to take notes, please come and talk to me; otherwise, just put it away and take notes on paper.

8 Diversity🔗

Diversity has many components. Here are just a few of them.

• First and foremost, our classroom must respect ways of being that are different from our own. We all have biases, both implicit and explicit (dynamic scope! Grr, I hate it!) and our job is to try to be aware of our own biases and try to prevent those biases from preventing people in our course from learning and participating.

• Second, diversity is not just an obstacle, it’s an opportunity. As we will hopefully discover, programming languages are first and foremost about human interfaces: what are the best ways for us to express programs? In this context, diversity is crucial: when languages are all designed by a particular kind of person, the results are really useful ... but only for that particular kind of person.

9 Computing Environment🔗

You will be required to complete the assignments in this class using Racket, version 8.11.1 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.

10 Version Control🔗

Version control is important in this course and every course 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)

10.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:

• The Typed Racket Guide: This assumes familiarity with Racket, so perhaps you should start with a quick look at the

• Racket Guide. In addition, one excellent resource that you should be aware of is

• Rosetta Code, which allows you (like the Rosetta Stone) to compare things written in languages you do know to those in languages you don’t.

• An implementation of Dijkstra’s algorithm in Typed Racket

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. These describe problems that you’re almbost certain to run into, and if you see an error that doesn’t make sense to you, please check this list first.

Finally, here are some Helpful Tidbits.

10.2 Installing the Handin Server🔗

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

• Choose File|Package Manager... , and enter this string (just copy it from this web page, WITHOUT ANY WHITESPACE, ESPECIALLY NOT A NEWLINE):

  git://github.com/jbclements/racket-handin-client#2242-csc430

  (If, after pasting this string in the box, it looks like it’s blank, it’s probably because you pasted something that ended with a newline. Don’t just paste again; hit the backspace key.)

  This should chug away a bit, and then you should be able to close the window. Note that the only completion signal is that the "Close Output" button becomes enabled.

  If any errors occur (it’ll say so at the end), be sure to copy the text so I can see it.

• Quit and restart DrRacket.

• You should now see a little "Poly" button labeled "handin". Don’t click it, yet. First you need to create an account.

• Choose File|Manage CSC 430 Handin account...

• Fill in your data. Use your cal poly login as your Username/ID (no @calpoly, just the login). Use "0" (zero) as the student ID#. Choose a password that you will remember. Click the "Add User" button when you’ve got that done.

Now, you should be ready to hand in.

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

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

12 Communication🔗

This class will use EdStem. 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 EdStem 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 EdStem 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.

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

One exception is for quizzes and tests, which must be entirely your own work.

The other exception is for programming assignments: you may not copy another team’s code, not even test cases. You are also responsible that no other teams 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, and an additional unspecified penalty on the quizzes and tests that follow, often about 10%. We reserve the right to assign a failing grade in the class when appropriate.

13.1 If it is late and you are desperate🔗

Please submit what you have. You will get partial credit, even if the handin server says "handin failed". It is way better to submit something terrible that is your own work than to submit someone else’s code. It’s okay. Let’s talk about it. Keep in mind that I want you to succeed.

13.2 Special note on Generative AI🔗

It’s so cool! I think we’re all excited about what Large-Language-Model based Generative AI tools are going to be able to produce, and how they’re going to change the act of programming.

In this course, you are definitely encouraged to use ChatGPT, GitHub Copilot, and other Generative AI tools *ON THE LABS ONLY*. I would love to see what you can come up with, please do share your prompts and tips with me.

On the assignments, however, I do require you to write the code on your own, without copying code from AI tools. There are a few reasons for this, besides the obvious reason that I want you to understand the code. First, the code produced tends to be not just low-quality but in some cases actually misleading. Second, "it was generated by AI" turns out to be a really large blanket to throw over copied code. So... it’s not allowed.

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

We’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, we 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 https://handin-1.brinckerhoff.org/servlets/standalone.rkt (also linked from the top of this page).

15 Assignments🔗

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

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.

16 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:

• 6 points – Your code displays unusual clarity or elegance, with no problems of consequence.

• 5 points – some inelegant parts, or one or two purpose statements or contracts/types missing

• 4 points – an actual misunderstanding, or a widespread lack of purpose statements and contracts/types

• 3 points – a serious misunderstanding–you didn’t understand some major part of the assignment, or I had to work to try to get your code to compile or run without looping

• 2 points – your program is seriously incomplete, doesn’t compile, or has widespread major problems

• 1 point – you didn’t make any apparent progress on the program at all.

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.

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

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

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

16.4 Grading code in 430🔗

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.

16.5 Common Errors🔗

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

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

• Don’t put your name in your submission. Whenever possible, we try to make sure that we’re grading assignments anonymously.

• Typically, the handin server will be configured to run tests on your code as it is submitted. Code that does not pass the tests will generally not be accepted. These tests will generally check whether you’ve defined the things you’re supposed to define. These tests will also generally check coverage. That is, you will not be able to submit code unless it includes test cases that completely cover your code.

• I do not currently have hidden test cases. Specifically, if you pass all of the tests associated with the handin server, you can generally expect to get full credit on the "correctness" portion of the assignment. The exception to this, naturally, is when I discover after the fact that I’ve neglected to test some important functionality. This has not happened in the last three years, but it’s always possible.

• When you fail a test case, you will get an error dialog that will contain the first 80 or so characters of the test case. For many tests, that’s the full text of the test case. For longer ones, however, it may not be. That’s by design; I do not want to supply you with the full text of every test case.

• I disregard earlier submissions when later ones are improvements. So, for instance, if you get a dialog that offers you a chance to save with a penalty, you need not worry that this penalty will affect you if you resubmit later (as long as it’s before the deadline)

• The handin server stores the last ten submissions on your account. So, if you’re unsure as to whether the deadline has passed, go ahead and submit; if I decide to disregard the final one, I can take the prior one instead.

• Code coverage is very important. The handin server will not run any of its tests unless your code has complete coverage. The best way to deal with this is to write your tests before you write the code. There are few things worse than a desperate last-minute comment-out test-insert frenzy, trying to get your code in shape before the deadline. Write the tests first, and get the code correct in advance.

• The handin server retains the last 10 "successful" submissions, and also the last "unsuccessful" submission. This means that even if the handin server says "handin failed", you do have a reasonable chance of getting some partial credit.

17.1 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".

18 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 a lecture period in the sixth week of class. The quizzes will be open-note. On exams, you will be allowed a single double-sided page or two single-sided pages of notes.

Quizzes will be given during lab, unless otherwise specified. The midterm is typically in place of a lecture.

19 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:

• Assignments : 25%

• Quizzes : 20%

• Midterm : 20%

• Final : 25%

• Labs : 5%

• Wiggle Room: 5%

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

21 Canvas🔗

I’m not a huge fan of Canvas. It’s a proprietary system, and it doesn’t fit well with the forms of automation that I like. Its API is kind of a mess.

With that said, there are certain affordances that Canvas provides. The most important of these is handin deadlines. I will make a concerted effort to make sure that Canvas deadlines match those on the actual course schedule, in order to allow you to coordinate your life in a reasonable way.