CS314: Principles of programming languages

Announcements

(5/1) Another extra-credit option on the last homework

In addition to Haskell, Prolog, Java, and CALL-BY-NEED, you can get extra credit on the 4/24 homework by solving n-queens in OCaml.

(4/26) Grades

If you wish, you can write all four extra-credit programs on the 4/24 homework. Each program is worth one problem (that is, 50% of a homework). See the “Software” section on this page for more information on Haskell and Prolog.

There will not be a final exam. Instead, the last 20% of your total grade will be your average homework grade or your average midterm grade, whichever is greater. (This calculation currently yields the same letter grades for everyone as simply computing the total grade out of 80%.)

(4/24) Some demo programs from class

To demonstrate how non-strict (in other words, call-by-need (in other words, lazy) or call-by-name) languages avoid an infinite loop, we used the following programs in class today.

• (proc (x) 3 letrec loop (x) = (loop x) in (loop 314))
• (proc (x) x letrec loop (x) = (loop x) in (loop 314))

To demonstrate how non-strict languages delay side effects such as mutable state, we used the following programs in class today.

• let i = 10 in (proc (x) i set i = 5)
• let i = 10 in
  (proc (x) let garbage = x in
            i
   set i = 5)
• let i = 10 in
  (proc (x) let garbage = x in
            let garbage = set i = 7 in
            let garbage = x in
            i
   set i = 5)

These programs will run in IMPLICIT-REFS, CALL-BY-REFERENCE, CALL-BY-NAME, and CALL-BY-NEED—try them out to see how the behavior changes!

To demonstrate non-strict data structures in Haskell, we used the following programs in class today.

• head [1, 2, (let loop x = loop x in loop 314), 4, 5]
• tail [1, 2, (let loop x = loop x in loop 314), 4, 5]
• take 2 [1, 2, (let loop x = loop x in loop 314), 4, 5]
• drop 3 [1, 2, (let loop x = loop x in loop 314), 4, 5]
• length [1, 2, (let loop x = loop x in loop 314), 4, 5]
• take 5 [1..]

Again, try them out to see how they work!

(4/24) Fixed link to inferred.scm

The link in the schedule to the INFERRED interpreter used to point at the CHECKED interpreter instead. Fixed! Thanks to Alanza Burke.

(4/17) Participation credit in recitations

Despite (or due to) the fact that attending recitation helps you learn, the recitation quizzes were intended to account for your help to others. People leaving right after the quiz indicated that this intention was not accomplished. Therefore, there is no more extra credit for quizzes. You will receive extra credit for your participation in recitations just as in the class newsgroup: thoughtfully and concretely initiate or continue a discussion about the readings, the lectures, the recitations, or the homework.

(4/12) Fix to bank.scm

Janet Weiss found a bug in bank.scm: in the second version of the code in the file, bank-s should call itself, not bank. Fixed. Thanks!

(4/5) What is a context?

The homework problem on observational equivalence only defines a context as “a program that is missing a part”. The missing part must be an expression according to the grammar, which you can find under the-grammar in the interpreter. For example, let x = □ in 0 is a context, but let □ = 3 in 0 is not. Because let □ = 3 in 0 is not a context, you can’t conclude that x and 1 are not observationally equivalent just because let x = 3 in 0 is a program but let 1 = 3 in 0 is not.

(4/5) ProfessorJ

Besides a Web server, DrScheme includes an interpreter for a Java-like language. Choose a language under “ProfessorJ” in Language | Choose Language.

(3/24) A tool to test whether your code is in tail form

There are three ways to test whether a program is in tail form. First, you can check if every call to a non-primitive function is a tail call. Second, you can try to translate the program into SLIM assembly language; in particular, translate each procedure call in Scheme into a jump in SLIM. Third, you can download and use an experimental tool I just wrote. This Scheme program defines a command tail-form, which you can wrap around another Scheme program. If the wrapped-around program is in tail form, the wrapper doesn’t do anything.

> (tail-form
    (define factorial
      (lambda (n)
        (compute n 1)))
    (define compute
      (lambda (n result)
        (if (zero? n)
          result
          (compute (- n 1) (* result n)))))
    (factorial 5))
120

In contrast, if the wrapped-around program is not in tail form—in other words, if the wrapped-around program makes a non-tail call to a non-primitive function—then the wrapper triggers a syntax error.

> (tail-form
    (define factorial
      (lambda (n)
        (if (zero? n)
          1
          (* n (factorial (- n 1))))))
    (factorial 5))
non-tail-call: bad syntax in: (non-tail-call (factorial (- n 1)))

The error message (on the last line) identifies the offending call. This tool is experimental—please let me know whether it is helpful and whether you encounter any surprises.

(3/21) Reading, printing, and searching a linked list in C

For those of you familiar with the C programming language, I translated print.slim to C. Studying this code can help you understand how to allocate and arrange memory for linked lists. I also translated find.slim to C with the GNU C Compiler’s computed-goto extension. Studying this code can help you understand how to allocate and arrange memory for procedures.

(3/19) Homework correction and clarification

In handout exercise 3 (both the Scheme part and the SLIM part), please assume that the list is not empty and the target does not occur at the beginning of the list. In this exercise, you should not allocate any new memory. More specifically, the Scheme code you write should not use cons, and the new SLIM code you write should not refer to the free register.

SLIM registers correspond to Scheme variables. SLIM labels correspond to Scheme procedures. To jump to a SLIM label and change the concents of SLIM registers corresponds to a procedure call in Scheme. The only SLIM action that corresponds to set!, set-car!, or set-cdr! in Scheme is changing the contents of memory locations. Thus, except for handout exercise 3, do not use set!, set-car!, or set-cdr! in Scheme.

(3/6) Reminders and hints for the 2/27 homework

Recall that EOPL exercise 3.14 says that the program

let x = 30
in let x = -(x,1)
       y = -(x,2)
   in -(x,y)

should evaluate to 1. Be sure to check that your solution to exercise 3.18 makes the corresponding program

let x = 30
in (proc (x,y) -(x,y)
    -(x,1)
    -(x,2))

also evaluate to 1.

EOPL exercise 3.18 is independent of the two (other) exercises described on the 2/27 handout. In other words, you don’t have to implement an interpreter for a programming language with both procedures that take an arbitrary number of arguments and a primitive procedure sub. In particular, the primitive procedure sub you put in the initial environment in the two handout exercises should take one argument at a time: the program ((sub 4) 3) should yield 1, whereas the program (sub 4 3) doesn’t have to yield any result.

Feel free to use arbno and separated-list in the-grammar, as documented in the 2/13 reading. Feel free also not to use these features—you don’t need them, and some students find it easier to figure out the abstract syntax returned by the generated parser if they don’t use these features.

Another hint on handout exercise 2: of the two variants you need to add to (define-datatype proc ...), one constructor takes no arguments and the other constructor takes one argument. Each argument you provide to the constructor of a data structure that represents a defunctionalized procedure corresponds to a free variable in that procedure. A free variable in an expression is a variable that is used, but not bound, in that expression.

(3/5) How to make your grammar LL(1)

If you get the following error message from SLLGEN as you work on EOPL exercise 3.14 or 3.18:

parser-generation: grammar not LL(1): shift conflict detected for class identifier in nonterminal

be sure that your abstract syntax tree for repetition is heavy on the right (that is, right-associative) rather than heavy on the left (that is, left-associative). This is a quirk of SLLGEN shared by all so-called look-ahead parser generators: they require the context-free grammar to be in a certain restricted form.

(2/23) Typos in EOPL Sections 3.2–5

In the inference rules at the top of page 63 and in the middle of page 70, two occurrences of v should be val. Near the bottom of page 76 and the top of page 77, the procedure procedure is described as taking a “vble” as its first argument, but it is not explained that “vble” means variable name (i.e., a symbol).

We haven’t covered LETREC (recursive procedures) in class, but there is an important typo in EOPL Section 3.5: in the numbered list on page 80, the variable x is bound twice! Professor Wand has issued a fix. (This problem is of the same kind as the mistake Aaron Borden caught me making in lecture today.)

(2/22) Interpreters updated

I changed the files with the code for the interpreters to better match what we did in lecture. The LET interpreter (which adds variables and “let”) is in let.scm; the PROC interpreter (which adds procedures but not recursive procedures) is in proc.scm. The essence of these interpreters has not changed. Compare these two interpreters to see exactly what it takes to add procedures to a language! In your feb15 homework, please feel free to start from any version of let.scm posted so far.

(2/20) EOPL exercise 2.27

It’s unclear which concrete syntax on page 49 you should use for unparse-lc-exp. Take your pick: the expression

(unparse-lc-exp (lambda-exp 'hi (var-exp 'there)))

should return either the string “proc hi => there” or the string “(lambda (hi) there)”. But do you see why the first grammar has an ambiguity problem?

(2/12) How to see data built using define-datatype

It is useful to see the data you are working on. Unfortunately, DrScheme by default hides data you define with define-datatype. For example, a diff-exp from class on 2/8 is printed as

#<struct:diff-exp>

no matter what its subexpressions are. To make your data visible, say

(require (only mzscheme print-struct))
(print-struct #t)

Now you can see inside a diff-exp without writing a function to convert it to a string:

#(struct:diff-exp #(struct:const-exp 4) #(struct:const-exp 3))

(2/1) Homework clarifications

In TLL ex 5.4, (occurN markers lat) should be the number of elements of lat that occur in markers, so duplicates in markers don’t matter but duplicates in lat do matter. For example, if lat1 is (basil) and lat2 is (basil basil), then (occurN lat1 lat2) is 2 and (occurN lat2 lat1) is 1.

In TLL ex 4.7, it is the job of whoever invokes dot-product, not you who implements dot-product, to make sure that vec1 and vec2 have the same length. The dot-product of two empty lists (that is, two zero-dimensional vectors) is zero, which should be convenient for your coding.

(1/17) How to submit homework

Please submit each homework assignment assigned before 2/15 as a single plain-text file containing a sequence of S-expressions. The file should be named after the start date of the assignment, like jan18.scm or feb01.scm. Don’t bother with zip, tar, gz, pdf, ps, doc, or the like. Use comments (which start with a semicolon and extend to the end of the line) to label your responses and for exercises that ask for not just code (such as CA exercise 1.7). A skeleton file illustrates the format.

Communication

You are responsible for checking this Web page for announcements.

You are also responsible for participating in the class newsgroup. Point your newsreader (such as KNode, Pan, Thunderbird, or tin) at the newsgroup ru.nb.dcs.class.314.ccshan on the server news-lcsr.rutgers.edu. When the news server asks you to authenticate yourself, you may need to put “@remus”, “@paul”, or “@aramis” at the end of your username. The news server expires posts every night, and can be unresponsive for about 10 minutes around 10–11pm—please plan accordingly.

When sending email to course staff or posting to the newsgroup, use a descriptive subject. Put “314” in the subject of emails to course staff, so that the message stands out and is easy to categorize. See “The do’s and don’ts of posting on Google Groups” for more information on newsgroup etiquette.

Grading

Participation (10%)

Attend classes; ask questions; offer answers. By midnight before each (non-exam) class, finish the reading assigned at the previous class and post a message to the class newsgroup. Your post should thoughtfully and concretely initiate or continue a discussion about the readings, the lectures, the recitations, or the homework.

• You will receive credit for your effort: At midnight before each (non-exam) class, the participation part of your grade increases by 2% (of 10% of your final grade) if you have posted a message in the last week. However, each post counts only once. For example, if you post a message at noon on Wednesday March 1, it will increase your final grade by 0.2% at midnight before class on Monday March 6 or Wednesday March 8, but not both. To take another example, if you post two messages every week, you will receive full credit in this part.
• You will also receive credit for the quality of your contributions to the discussion, for example when you ask a question in the class newsgroup that I choose to elaborate on in lecture. I will let you know by email when you have made a good, helpful post.

Homework (50%)

There will be a couple of homework assignments every week, containing short-response questions and programming problems. (If you are not a CS student, you can get a departmental account to do the programming assignments.) Each homework is due in one week by midnight unless otherwise indicated. Each day late discounts the grade by 10%. Please submit your work online.

Exams (40%)

There will be two midterms (10% each) and a final (20%).

You are encouraged to discuss homework with others, but everything you finally submit must be your own work, and you must acknowledge your collaborators in your submission. When in doubt, ask. Please refer to the department’s academic integrity policy. Cheating cheapens everyone’s degree.

You can see your grades and our comments online at the FAS Gradebook. Check out the grading criterion on the Web. On the course newsgroup, you can see the answer key and test programs we used for grading, but note:

• These materials are protected by copyright law. Do not redistribute them to anyone else or anywhere else.
• Many problems have multiple solutions, some radically different from others.

Readings

• Daniel P. Friedman and Matthias Felleisen, The Little Schemer, 4th edition. Cambridge, MA: MIT Press, 1995. “The goal of this book is to teach the reader to think recursively.” (Available at the campus bookstore.)
• Max Hailperin, Barbara Kaiser, and Karl Knight, Concrete Abstractions: An Introduction to Computer Science Using Scheme. Pacific Grove, CA: Brooks/Cole, 1999. “At first glance, the title of this book is an oxymoron.” (Available online.)
• Daniel P. Friedman and Mitchell Wand, Essentials of Programming Languages, 3rd edition. Draft of December 19, 2005. “The most interesting question about a program as object is, ‘What does it do?’ The study of interpreters tells us this.” (Available in three ways:
  1. You can get a physical copy on reserve at the SERC reading room.
  2. Once you have a remus account, you can print yourself a copy at a public computer lab over the Web. This method lets you print a single chapter at a time if you like.
  3. Once you have a remus account, you can also print yourself a copy at a public computer lab by sending a blank email message to ccshan at remus dot rutgers dot edu with a subject line of the precise format “EOPL netid printer” without quotation marks, where netid is your NetID and printer names the printer you want.
  However, printing to the LSM printers doesn’t seem to work.)

• Daniel P. Friedman and Matthias Felleisen, The Seasoned Schemer. Cambridge, MA: MIT Press, 1995. (Available at the campus bookstore.) “The goal of this book is to teach the reader to think about the nature of computation.”
• Harold Abelson and Gerald Jay Sussman with Julie Sussman, Structure and Interpretation of Computer Programs, 2nd edition. Cambridge, MA: MIT Press, 1996. (Available online.) “A computer language is not just a way of getting a computer to perform operations but rather . . . a novel formal medium for expressing ideas about methodology.”
• Peter Van Roy and Seif Haridi, Concepts, Techniques, and Models of Computer Programming. Cambridge, MA: MIT Press, 2004. (Available on reserve at the SERC reading room.)

If you need a reference for Scheme, try “Revised⁵ report on the algorithmic language Scheme” (aka R5RS, the de-facto standard), R. Kent Dybvig’s The Scheme Programming Language, or Dorai Sitaram’s “Teach yourself Scheme in fixnum days”.

Software

Scheme

Download and play with DrScheme. We use version 301 in class, but any recent version should work.

There are two ways to run DrScheme in the campus computer labs. You can download and install DrScheme in a location where you have write permission (such as the Z drive) every time you sit down at a computer. Or you can run DrScheme remotely from your remus account: start an X server such as Exceed, then use ssh to connect with port forwarding to spanky.rutgers.edu and run /ug/users/ccshan/local/spanky/bin/drscheme .

For graphics and quilting as described in Concrete Abstractions, install fungraph.ss as a DrScheme teachpack (Language | Add Teachpack) and load quilting.scm (File | Open). We’ll be using Concrete Abstractions with DrScheme in class, but the book can also be used with other Scheme implementations.

To work with code and exercises from EOPL, choose “Essentials of Programming Languages (2nd ed.)” under “Teaching Languages” in Language | Choose Language in DrScheme. See the EOPL 2nd ed. Web site for support code for other Scheme implementations.

Haskell

The learning page on the Haskell Web site links to numerous Haskell tutorials and four implementations, all of which are compatible with Queens.hs. For what it’s worth, I use GHC for class demonstrations.

Prolog

SWI-Prolog is a nice and free Prolog implementation. It is what I use in class demonstrations.

Schedule

It’s tentative! As noted above, readings (and your twice-a-week post to the class newsgroup) are due by midnight before the next class unless otherwise noted, and homework assignments are due by midnight in one week unless otherwise noted. Readings enclosed in parentheses are optional.