On this page:
Principles of Programming Languages

Principles of Programming Languages

Programming Languages

I expect students to visit this page once per 24 hours starting with the first day of the semester.

Tuesday, February 18th, 2020 5:24:33pm

Here is a table of the fundamental ideas we have covered so far in this course:













a region of program text





assignable variables

mutation effects




represent order of effects





about a program’s behavior

type checking




check compatibility of type claims



with program syntax



without running the program



type soundness


are types true?


are the claims correct predictions?

The left column are ideas you find in a languages’ syntax and tools from the language’s ecosystem (type checker, IDE). The second column tells you what these visible things mean in the interpreter model of a programming language.

The last row is about the relationship between visible ideas and meaning.

It is important to identify these ideas, to keep them separate, and to know where they belong.


Tuesday, February 11th, 2020 9:28:32am

Some of yuo still seem to have trouble understanding how the lessons of Fundamentals I, II, and III (OOD) apply to the big picture organization of programs in the world of PL. So here is a tabular view.






read JSON: Simplicity and Complexity from file into internal JSexpr



parse JSexpr into Abstract Syntax Tree



map Abstract Syntax Tree to Typed Abstract Syntax Tree or Value



unparse Typed Abstract Syntax Tree or Value to JSexpr



write JSexpr to file as JSON: Simplicity and Complexity

The word map means type-check or interpret here.

JSON: Simplicity and Complexity is an externally defined information format.

JSexpr is the internal data representation of JSON. Your JSON library will define this representation; it is never JSON and you must make an effort to understand it.

Abstract Syntax Tree is a tree-shaped data representation of grammatically valid inputs.

Typed Abstract Syntax Tree is a tree-shaped data representation of Abstract Syntax Trees that satisfies the typing rules.

Value is the result of interpreting an [optionally Typed] Abstract Syntax Tree.


Saturday, February 8th, 2020 11:00:31am

We have the results from the code inspection for homework 4. Let me once again reiterate some basic hints:
  • Many of you fail to figure out data representations and a statement of purpose (or data interpretation). When you work In a language with types–say Java—a well-named type definition with good function names gets you most of the way there; you still need to understand what the data represents. In a language without types—such as Python 3.7—it is critically important to write down your data representation. Otherwise you cannot produce even halfway viable code.

    Here is an illustration of this point with the ISL+ version (Fundamentals I) of the data definition for interpreter values
    (define-struct closure [parameters code environment])
    (define-struct prim-op [n f])
    ;  type Values = Integer ||
    ;                (closure [Listof Var] VExpr Env) ||
    ;                (primop N (-> Val_1 ...  Val_n Val))
    ; Values are what the interpretation of every expression returns and what
    ; the interpreter associates with variables in the environment.
    Figure 1 sketches the Fundamentals II variant (and a bit more).

  • You really want purpose statements for methods, too.

    The interpreter_helper produces the values of expressions; it also has the effect of throwing an exception for an error situation.

    The interpreter function/method produces the final answer, i.e., what the external observer (you and the test fest framework) will see and compare.

  • The test harness should really do nothing but read JSON, evaluate the given program to an answer, and print the result as JSON. Period.

Someone raised the problem of negative exponents. I fixed the homework statement (in purple!). Yet many of you failed. Please read Piazza and please read the homework carefully.

  // IValue = IntVal | Closure | PrimOP

  // reprsents values that interpreter returns or stores in Env

  interface IValue {

    IValue apply_as_function(IValue arguments[]);

    boolean arityCheck(int n_of_arguments);



  // since the arity field and arity checking occurs in two classes,

  // you should apply the abstraction design recipe from F II


  class IntVal implements IValue {

    private int x; // okay big ints


    public IValue apply_as_function(IValue arguments[]) {

      throw new RuntimeException("closure or primop expected");





  // a programmer-created function

  class Closure implements IValue {




  // a baked-in primitive operatioon such expt

  class PrimOp implements IValue {

    private IBin op;

    private int arity;

    PrimOp(int arity, IBin op) {

      this.op = op;

      this.arity = arity;




  // IBin represents binary function

  interface IBin {

    int call(int x, int y);



  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  // in Main you can then write something like this to "play"


   IValue expt = new PrimOp(2,

                            (int x, int y) ->

                                (int)Math.pow(x,(y > 0)?y:y));

   // you could also raise an error after checking y

   IValue arg[] = new IntVal[] { new IntVal(2), new IntVal(3) };


Figure 1: A Java data representation for values (hw 4)


Thursday, February 6th, 2020 3:05:06pm

Your homework grades are higher than your code deserves.

Here is how the test fest works and how you must react to the results:

  • You get points if your solution passes my tests.

    For now I have written simple tests that every basic solution should pass, and as it turns out, many of yours do—with the emphasis on basic.

  • You get points if your tests pass my solution.

  • You get points if your tests pass my oracle and expose a failure in someone else’s solution.

    You do not lose points if your solution fails on the tests of others.

So a solution may get a relatively high test-fest score even if it fails a massive number of tests.

The goals are (1) to show you that your solution is flawed, (2) to get you to fix your solution in a timely fashion, and (3) without having a discouraging effect.

The time will come when I collect all submitted tests and run them as my tests on your solutions because you will have had plenty of weeks to get things right by then.


Tuesday, February 4th, 2020 1:58:34pm

Yes, software is bad.

If you didn’t see this headline, that’s to be expected. The NYT knows who you are and picks which headline to display for every article visible in your browser so that you click around and stay on its page as long as possible.


Friday, January 31st, 2020 2:08:16pm

I have update In-Class Reviews. Please take a look, especially if you haven’t presented yet.


Wednesday, January 29th, 2020 10:51:54am

Last Tuesday’s code walk displayed two major programming mistakes that did not get discussed properly in class. Since 4 — Interpreting Functions and the following homework assignments demand that you hue to the blue prints and design recipe more strictly—unless you really wish to spend 40 hours per week on just PL—I am providing the following hints.

General The lectures present blueprints for your homework solutions. A blueprint is not an actual implementation but a sketch of what we eventually want. The real “thing” comes with variations, warts, and all. By implementing a blueprint, you get your hands dirty with the concepts and hopefully you develop an understanding in the process.

Mutation The code walk presented a mutable implementation of the environment. Since Java comes with a mutable Stack library and since the environment for VExpr was called a "stack" in class, the presenters used Stack and somehow got it to behave properly, mostly, kind of. In case your F II instructor did not mention “frame tests,” they are tests that ensure the absence of accidental side-effects of your method. (For example, note the absence of “effect” statements—purpose statements when you design a method with assignments—and frame tests.)

I refer to this programming style as 1970s (typically taught in AP CS in high schools and still practiced to a some extent in industry). Let me one more time remind you that the design recipes of Fundamentals II are not some random thought that occurred to me in a bad dream; they are partly based on the Design Patterns book and even more so on Josh Bloch’s Essential Java, which comes with slogans such as

Favor Immutability.

Now you may say “who’s Josh Bloch” because you may not know that he designed the Java API and then wrote this book to apologize for overdoing mutation.

Alternatively, consider the first design guideline for Smalltalk, arguably the first proper object-oriented programming language (Salt Lake City, early 1970s):

Abolish Assignment Statements.

meaning reduce their use as much as possible.

So in this spirit, here’s an alternative that would have cost imperative Stack programmers about 20 lines of code and would have saved them about two hours of debugging:

  interface IEnv {

    // extend this e with a binding of x to v

    IEnv extend(IEnv e, Var x, IValue v);


    // retrieve the value of x in this e

    IValue lookup(IEnv e, Var x);



  class EmptyEnv implements IEnv { ... }

  class ExtEnv implements IEnv { ... }

Apologies for providing this language-specific hint but this is how I design in Python, too, and you really can apply design recipes in all OOPLs.

Data Definitions One of the key ideas is that the design of functions/methods matches the design of data definitions (the informal or code-based description of how you represent information as data). Here are critical hints, again in contrast to the code presentation from Tuesday:
  • If your data definition does not refer to any other data definition, your function/method uses only language primitives.

  • If your data definition refers to other data definitions, your function/method typically calls functions/methods on the pieces of data from those data definitions.

  • If your data definition refers to itself, your function/method typically calls itself (via an interface in Java).

  • If you are dealing with several data definition at once, design the same number of function/methods in parallel.

    If these data definitions refer to each other, like Decl and FVExpr, your functions/methods call each other.

Note how the last two hints are really just refinements of the first two.


Tuesday, January 28th, 2020 2:49:34pm

1. I have pushed a clarification concerning FDecls in 4 — Interpreting Functions.

2. Someone expressed the desire to change the chosen implementation language. This is a perfectly reasonable desire, given how some languages are less helpful than others.

(2a) For a change from say TypeScript to JavaScript or from Racket to Typed Racket (and vice versa), there is no need to inform us. The two languages run on top of the same run-time system. Indeed, one may consider each language pair as a single language with support for writing typed and an untyped code.

(2b) For a change from say Python to Rust, you will need to write a brief memo addressed to Leif and myself consisting of about two paragraphs. The first one must describe the major shortcoming of the current language; the second one should express your hopes on how the next language will improve your lives.


Monday, January 27th, 2020 6:30:03pm

Dustin J. has to move his office hours for now; he may be able to move it back later in the semester. See Email, Office Hours, Etc..


Tuesday, January 21st, 2020 3:06:07pm

To accommodate the large number of students who misinterpreted the homework, 2 — Static Distance, Simple Interpretation is now due on Wednesday, 22 January at 6pm.


Thursday, January 16th, 2020 8:55:05am

This short clip is a love letter to all those of you who think that Node.js is new, fast, amazing, and whatever. (Not that threads are the solution either.) As I said in class yesterday, science is not a consensus business, a majority-rules area, or worst of all a fashion industry—even though it’s practitioners have acted like this for millenia. Keep this general idea in mind.


Wednesday, January 15th, 2020 9:35:27am

Thanks to Nathaniel R. for pointing to a Python Wat repository. I am replicating it here for "eternity".


Tuesday, January 14th, 2020 4:31:41pm

Let me remind everyone that the web page for the course is easily reachable from my CCIS page:

my CCIS page

A backup page is provided at my personal web page. It really is just a backup page in case CCIS’s web cache gets in your way. (Ask in class.) The primary page is provide thru the College’s server.


Tuesday, January 14th, 2020 12:16:10pm

2 — Static Distance, Simple Interpretation has an exceptional due time. I have pushed back the due time so that you can benefit from the help session that Suzanne and Julia will run in the morning.


Tuesday, January 7th, 2020 12:41:25pm

Every year Stackoverflow publishes a the results of surveying software developers. The 2019 results came out a couple of weeks back. Now that you have seen the first lecture, you understand that this is just one of many perspectives on programming languages and perhaps not even the most relevant one. It is still interesting to peruse the tables and figures for simple facts, such as Clojure programmers are the most highly paid programmers or only 7% of developers work less than 30 hours a week.

[As someone said after class, I followed the design recipe for programming in Algorithms and needed one or two hours; my friends didn’t and they needed two days.]


Sunday, December 8th, 2019 4:43:12pm

Please watch the original Wat Video. Some two years ago, Katie McLaughlin gave a really neat JavaScript is awe-ful presentation at Linux.Conf.Au, and I would like you to watch her talk after you are through with "Wat".

Then start thinking about which programming language you would like to use for solving the homework problems in this course. You may wish to use a language you know well or you may wish to learn more about a language that you know a little. (I recommend against learning a brand-new language.)

To make sure that we can automatically test your solutions, you will need to make sure that your language (1) runs on the College’s Linux boxes (see Delivery), (2) permits reading from standard input (STDIN) and writing to standard output (STDOUT), and (3) comes with a decent library for mapping JSON/XML/S-expression information to a data representation (reading) and back (writing).