Programming Languages (CS162)

Contacting Us

Office Hours



  1. First-order logic
  2. Lambda Calculus
  3. Simply-Typed Lambda Calculus
  4. Simply-Typed Functional Language (SimpleFUN)
  5. Polymorphically-Typed Functional Language (PolyFUN)
  6. Small-Step Operational Semantics
  7. Small-Step Operational Semantics for Simply-Typed FUN (SimpleFUN)
  8. Small-Step Operational Semantics for mini-prolog


  1. Introduction to Scala, Due Friday, January 20
  2. Functional Images Implementation, Due Wednesday, February 1
  3. Simply-Typed FUN (SimpleFUN) Typechecker, Due Tuesday, February 14
  4. Polymorphically-Typed FUN (PolyFUN) Typechecker, Due Wednesday, February 22
  5. Simply-Typed FUN (SimpleFUN) Interpreter with Small-Step Operational Semantics, Due Wednesday, March 8
  6. Introduction to Prolog, Due Wednesday, March 15
  7. Interpreter for Subset of Prolog (mini-prolog) with Small-Step Operational Semantics, Due Friday, March 24


Example Code

Some Relevant Links

Books (With Links)

General Advice

In general, if you want to know what sort of methods are available, along with their signatures, Googling for scala class-of-interest will give you a lot of information. For example, if you want to know how to use Scala's Seq class (representing Sequences), then Googling for scala Seq should turn up the scaladoc (Scala's equivalent of javadoc) for Seq. This will give you the methods and method signatures on Seq, along with its position in the inheritance hierarchy.

In general, unless we explicitly say otherwise, you may not use mutable state in your assignments. This includes both mutable variables (i.e., those introduced with var), along with mutable data structures (e.g., arrays, most everything in scala.collection.mutable). When in doubt, ask us if something is ok to use. Using mutable data in an unauthorized way will hurt your grade significantly. The reason for this restriction is to intentionally force the usage of functional programming, which strongly discourages mutable state. Without this restriction, you are basically writing Java in Scala, and not really learning Scala or functional programming.


Some Relevant Links


It is not necessary to look at any of these books to understand the course material. These links are here only for those who are interested in learning more about Prolog. I own all the books listed, and I would be happy to let you take a look at them.

General Advice

Prolog, and logic programming overall, behaves very differently from other programming languages. It is expected to be challenging to pick it up, because in many respects you'll be learning programming all over again. The trace clause is your friend here, which will give you a whole lot of debugging information. For example, if you do trace, foo(X)., this will show all the steps taken while calling foo with the parameter X, which is extremely valuable. This includes information regarding values passed back and forth, which is more than what one usually gets with a stack trace.

To keep things simple, I advise against the use of metaprogramming and extra-logical features, including, but not limited to:

You may use the above features without penalty, but there is no assignment which requires you to do so. The reason why I advise against these features is that they do not mix well with the rest of Prolog, and are really hacks which have been done to the language in order to make it more flexible. Proper use of these can lead to very clean code, but they are semantically complicated and they are all special cases in the language. To this date, I have not seen a student use any of these features correctly, and broken code was the result.

Additionally, as with the Scala assignments, you may not use mutable state in your assignments. This includes features which dynamically modify the clause database (e.g., assert and retract), as well as global mutable variables in SWI-PL (accessed through nb_setval, nb_getval, etc.). There are no cases in which the usage of these is permitted, so using them will hurt your grade significantly. As with Scala, we want you to learn Prolog, not to learn how to force C or Java into Prolog. Additionally, these features are extremely error-prone, even moreso than the extra-logical features discussed previously. Case in point, I have found bugs in SWI-PL libraries involving improper use of nb_setval, and I have seen students use these in ways which were subtly incorrect.