CSC-430 Winter ‘22


Welcome to the Syllabus/Information page for CSC 430 Sections 09/10
Winter Quarter 2022, Cal Poly San Luis Obispo
Michael Van De Vanter PhD

Schedule/Homework

Lab number submission servlet

Hints on Using Typed Racket in CPE 430

Helpful Tidbits

Textbook

PLAI TR Translation

Common Assignment Errors

Basic Mastery Details

Contents

A special note about this quarter

This is my fourth year teaching CSC 430, which I do in close collaboration with Profs. Clements and Beard. It is also my fourth quarter teaching virtually (I live out of the area and no longer commute). I ask for your patience with the limitations of online learning, and I promise you the same, whatever your personal circumstances. A particular challenge, as I'm sure you experienced, is to create the kind of engagement online that we take for granted in the classroom. I'll do my best with this, and I ask for your commitment as well.

1. About the course

Programming languages determine what programs we can write. Although any computation (spoiler alert for your theory class) can be described by just about any programming language, those with nice abstractions allow us to write elegant, concise, and readable programs with less effort and much less debugging.

In this class we will build a programming language starting from scratch. We will study and add necessary pieces step by step. Along the way we will discover the power of simple abstractions, and how you can do more with less!

Completing this course will make you a better programmer. You will also learn that programming languages don't simply fall out of the sky, but rather are designed via many choices in a large design space. This will help you learn new languages and understand similarities and differences among them. Finally, you may develop some taste for what you personally like in a programming language.

This course will involve lots of programming in Typed Racket, a good choice for several reasons. First, functional programming languages make this kind of course feasible. Writing a series of interpreters in another language would probably require a whole lot more code. Second, the core Racket language is a simple language to learn, with no complex syntactic rules. Racket's (optional) type system is powerful and can be used incrementally (aside: Racket's type system was the model for the one used by TypeScript). Finally, the simplicity of Racket makes it an ideal blank slate for adding features. If these reasons make no sense to you, then... perhaps you need to take the course!

Acknowledgement : this section will follow closely the sections taught by Profs. John Clements and Stephen Beard, both in general organization and in course material. We in this syllabus refers to the three of us.

2. Learning Outcomes

  • 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 (optionally 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.

2.1 Bonus Topics

We sometimes get to one of these:

  • parsing,
  • macros, 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.

3. Prerequisites

In order to take this course you must be able to design and implement small programs (~ 1 KLOC) efficiently. You must 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.

4. Names, Times, Locations

4.1 Instructor

Michael L. Van De Vanter, PhD (aka mlvdv ), email: mvandeva at calpoly.edu

4.2 Lectures & Labs

4.3 Office Hours

4.4 Web Page

This is the course web page; its link is http://vandevanter.net/mlvdv/CSC-430.html . It is part of my personal web site http://vandevanter.net/mlvdv/ , but is not linked from any of those pages.

5. Lecture Environment

An interactive and lively classroom (in-person or virtual) is a more productive learning environment, for which reason (based on our experience and good research) we usually request that in-person students engage fully with the classroom and not with their laptops. This is, after all Cal Poly's "brand". Achieving this environment online is a real challenge, but we've evolved some rules and practices that seem to help, and feedback or suggestions are always welcome.

My first request is that your camera be on during lecture. This is very important to my efforts to get to know you (there's that Cal Poly brand again). It is also important that you to get to know one another. You are by definition part of an interactive learning community for the duration of every course. On the other hand, I understand that there can real privacy issues online.

Some privacy issues can be addressed with a Zoom background, and I will do that for myself. I teach from the bedroom of a son who is away for a bit, and, well, he's not the most inspiring interior decorator. I have an actual green screen to minimize the weird video artifacts that sometimes appear, and I will understand if those sorts of artifacts plague your image. I'd rather see you in any case, no matter how it looks. Please use some discretion around your choice of Zoom background, though. I appreciate distinctive backgrounds but not ones that are distracting and especially not ones that are animated in any way. You can also criticize my backgrounds or suggest improvements.

If you are occasionally unable to have your camera on (things happen), please just let me know via email or private chat at the beginning of that lecture. If you have an ongoing issue with the camera please get in touch with me to discuss privately. Thanks.

I would also like to call on you occasionally during the lecture to see if you are following. If you can't answer a particular question it is totally fine to say no, I have no idea . I will take that to mean that I am not explaining things effectively. However, I try to respect the wishes of students for whom this technique is disruptive. Please let me know if you do not want me to call on you.

6. Teams

We’re going to be working in teams of three or four. I’ll form the groups using input from a survey, combined with a 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.

Some of you may prefer not 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. I’ll put you in a special "anti-team" team of people working individually.

Those of you working in teams will 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.

7. Computing Environment

7.1 Racket IDE

You will be required to complete the assignments using the Racket IDE version 8.3 or later. It is freely available for all major platforms, including Mac OS, Windows, and UNIX. This IDE has been known as Dr. Racket or sometimes PLT Racket but is most often referred to most often as just Racket , which is the name of the language the IDE supports.

7.2 Version Control

Version control is important in every class in which you write programs of more than 50 lines. Good choices include private git repos on github and bitbucket. Remember, it’s not whether you lose data, but when. For Heaven’s sake, though, make sure the repos are private! See the section on Honesty below.

7.3 Typed Racket

We will use the Typed Racket language for this course.

Racket (just plain Racket) is a functional programming language based on Scheme. It started out being the largest Scheme implementation, in which professor Clements was and continues to be a major player. They eventually decided it would make more sense just to rebrand it as a new language. Clojure did it, right? So the MzScheme project became the Racket project, and VOILA it is 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, and 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:

In order to help you learn to use Typed Racket, Professor Clements has written up some extremely helpful Hints on Using Typed Racket in CSC 430 . I encourage you to re-read them every time you start a new programming assignment, as some hints will only become relevant (or even intelligible) later in the course.

Here are some test-yourself examples of converting quoted s-expressions to conses , something you will need to do for every programming assignment, as well as every quiz and exam.

Here are some examples of useful patterns that you can use with the match operation, an extremely powerful mechanism that is essential for the assignments but sometimes very confusing to learn.

Prof. Clements' short essay on debugging in CSC 430 could save you a lot of time.

Finally, here are some Helpful Tidbits you will eventually need, even though they might make little sense until you do. Re-reading some of these from time to time during the quarter would be a good learning strategy.

7.4 Installing Handin Server

In order to hand in your work you must install a DrRacket 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#2222-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. You will know that installation has completed when the Close Output button becomes enabled.

    If any errors occur (it will 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 . Do not click it, yet. First you need to create an account.

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

  • Fill in your data. Use your Cal Poly login name 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 have finished.

Now, you should be ready to hand in.

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

The first two weeks may also include readings from How To Design Programs (also known as HtDP ), available free online.

8.1 plai-typed and typed/racket

Assignments will be written in the frighteningly awesome typed/racket language. Unfortunately, code in the textbook is written using the slightly different Racket variant known as plai-typed . In order to make your lives slightly less difficult, Prof. Clements has translated code from the first few chapters of plai-typed into typed/racket to make them more applicable to your code.

PLAI-TR-translation.rkt

9. Communication

This class will use a single ed group for communication among the three sections taught this quarter by Profs. Clements, Beard, and myself. This will be the principal means that I will use to notify you of deadlines, organizational updates, and changes to assignments. If you do not keep up with the group you will miss important information.

It is also the best (and sometimes fastest) way for you to direct questions to me and/or the class (all three sections). Helping other students in this forum is a good way to improve your performance as well. Feel free to e-mail me with personal questions, but use the ed group as your main means of communication. It is possible to post anonymously, if you like.

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

Important: Do not post any assignment code or test cases (test cases are part of your assignment). Anything else, including lab code, 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 and e-mails. One easy rule of thumb: just read over what you have written before clicking post or send, and imagine others in the class reading it.

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

A big exception is for programming assignments: you may not copy another team's code, not even test cases . You are also responsible that no other students see your team's 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 program 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 option to assign a failing grade in the class when appropriate.

The other exception, of course, would be exams (quizzes, midterm, final); these must be entirely your own work.

11. Labs

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

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.

I will check these off during the lab; you are responsible for demo-ing your lab solutions for me. Your marks on these labs will be simple credit/no-credit. When time permits I may give feedback on some aspects of your code.

The labs will be due at the end of your lab period on the day specified, usually on Thursday. 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.

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

11.1 Virtual 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 (encourage?) you to spend more time with your classmates.

Labs this quarter will generally be held in breakout rooms, in one of two configurations; either you will be in a breakout room with only your team, or you will be in a larger room of about three teams, a sort of miniclass .

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

12. Assignments

Programming assignments will be due at 10:00 PM on the day listed in the class schedule. 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 during lecture. Try to ensure that the code you submit is something you would be proud to show to the others in the class.

Late Policy: Other than exceptional circumstances (and then only if communicated in a timely way), late assignments will be given 0 points.

13. 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 must 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 ahd contracts/types
  • 3 points : a serious misunderstanding, you did not 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, does not compile, or has widespread major problems
  • 1 point : you did not 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 ;;> so you can search for these in the e-mail that you get with your final assignment grade.

13.1 Code Organization

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

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

You must 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 is done and what is still left to implement.

As a rule, I like to read code top-down . This means that the definition of the top-level, important functions should come first, and that supporting functions should come later. I want 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 after it is working is to collect the test cases in a sensible place that does not interrupt the flow of reading the code. It is best, after you finish writing the code, to collect the test cases at the bottom of the file. This will also help you avoid certain order of definition errors from DrRacket that can arise from test code.

Most languages have a style guide. Here is the one for Racket . You are not required to follow the 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.

13.2 But it Works!

I reserve the right to assign bad scores to programs that work correctly; if I do not believe you are doing a good job of programming, then you will not receive a good score. It works is no defense for bad code.

13.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. Do not be surprised to see comments like ran out of grading time here.

Naturally, all grades contain an element of subjectivity.

13.4 Grading code in 430

For most of the assignments in this class, I will 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,
  • test cases.

Per the style guide, please do not follow the one closing brace per line style that is 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.

13.5 Common Errors

Also, see Prof. Clements' discussion of issues we frequently find: Commmon CSC 430 Eyeball Problems . This will save you time.

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

  • Do not 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 have defined the things you are 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 use hidden test cases . 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 have neglected to test some important functionality. This is rare but always possible.
  • When you fail a test case, you will get an error dialog that contains the first 80 or so characters of the test code. For many tests, that is the full text of the test. For longer ones, however, it may not be. That is 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 is before the deadline)
  • The handin server stores the last five submissions on your account. So, if you are 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 is nothing 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.

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

mvandeva+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 .

15. Quizzes and Exams

There will be frequent quizzes, since evidence suggests these help ensure you are understanding what I am present, and that I am presenting things you understand. Assume that they will be weekly, 15-20 minutes long, and usually during Thursday lab.

There will be one midterm during week 6 of the course and a final exam. The midterm will be during the lecture. All exams are open book and open DrRacket . In fact we encourage you to have DrRacket close at hand during examinations to help develop answers to coding questions, even if only to be sure that parentheses match (we try to grade some of them automatically).

16. Grades

Grades will be determined by performance on programming projects, 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 : 40%
  • Quizzes : 15%
  • Midterm : 15%
  • Final : 20%
  • Labs : 5%
  • Wiggle Room : 5%

16.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 assignments 2, 4, and 5, your first four labs, and to re-take the midterm exam. If your iteratively perfected first assignments are all passing all test cases and up to the standard an employer might require, 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.

Also note that while it’s a very good 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.

17. 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 is not a clickable link, because you must edit it to add your login. So, for instance, if your name is Annette Czernikoff and your login is aczernik@calpoly.edu , you would put aczernik in the login spot.