Programming Languages 201516 (F28PL)

Course overview

Welcome to the Programming Languages 201516 webpage. In a nutshell, this course says:

“How should we program? Well, it matters what programs we have in mind. Let’s think this through …”

For historical reference.
See this year’s course.

Class times

- Wednesday at 12:15 in EM1.82.
- Thursday at 10:15 in EM1.83.
- Thursday at 13:15 in EM2.50 (lab/tutorial).
- Thursday at 15:15 in JN302.

The rules:

  1. Attend lectures.
  2. Keep up with the course. Understand lecture materials while the course is going on. Independently research stuff on the in-ter-net. A student who thinks “I’ll sort it out during the holidays” is a student in denial (look at 1m03s).
  3. Rules 1-2 apply most especially to the student who thinks that rules 1-2 do not apply to them.

How to answer a programming question:

Somewhat to my surprise, many students don’t know how to answer a programming question (such as the ones here). So here are Jamie’s Simple Steps to Answering a Programming Languages Question:

  1. Use an obscure file format: WordPerfect is good, a .tiff file embedded in a spreadsheet is better, or best of all convert your answer to a .gpx course file. At all costs avoid simple, portable solutions such as .txt or .odt.
  2. Never cut-and-paste the question number and the text of the question itself. Your marker can infer what the question was, probably by viewing the question sheet on a second computer which he or she will purchase specially to commemorate the honour of marking your work.
  3. Do not include your name, student ID, e-mail, or any other identifying marks in your answer. Call your file “questions.gpx”, or better still just “q”. Send from an anonymous e-mail account, or at least, from a non-university account with a suggestive identification such as “mangaLover” or, for that classic touch, “n00b”.
  4. Do questions in random order.
  5. Don’t check your answers for syntax errors, e.g. by trying to compile them yourself. If your compiler cannot parse your code then it is unworthy.
  6. If a question asks you to write a function called foo, rename it to one or me or kermit or perhaps something in Thai script; you know better.
  7. Never comment on or explain your answer. Your genius speaks for itself.
  8. Test cases are for wimps, but if you must do test cases (for instance if the cowardly question insists on this) then neglect corner cases such as 0, a, z, fn x => x, or the empty list []. Users who run your program on corner cases deserve what they get (whatever that may be).
  9. Never comment, indent, or annotate your code. Code should be written all on one long line without linebreaks and with minimal spaces, preferably in Comic Sans 8pt.
  10. Constants, variables and functions should have unsuggestive — or better still, misleading — names. For instance, a program to calculate the total of a list should be called average (true story). ASCII codes should always be given as unelaborated raw numbers, in binary if possible or, if you’re feeling cheerful, in octal.
  11. File suffixes (the kind that help a browser to implement one-click preview) are also for wimps. If your lecturer can’t be bothered to download your file, open it with a binary editor, figure out what file format you were using, rename the file accordingly, open it locally with a compatible editor, mark it, reupload it … and then repeat this cycle for the next student and the student after that … then he doesn’t deserve to read your work.

I felt moved to write a poem on this subject:



The Literate Programmer’s Manifesto (in amphibrachtic verse)

What is a program supposed to do?
A program is data, which if put through
the execution on a machine,
has certain behaviour that will be seen.

But readability too is required:
the maintainer’s mind must be inspired
with what that behaviour that should be seen
was thought in the programmer’s brain to have been!

You see, your code’s not written by you,
for your machine to just instantly do.
Your code will travel through space and time
from your computer console … to mine.

Coding’s not just a solitary chore.
Code is read, checked, modified, debugged, and more.
So to you, to all humans; right now and years hence
poor code is sinful; good code just makes sense.


- Jamie ‘literate code’ Gabbay, November 2015

Lecture slides

I am updating these from last year. Up-to-date slides are:

- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5 – Python

The pdfs below are from last year (l11 below corresponds to lecture-1 above):

l11.pdf l12.pdf l13.pdf l14.pdf l15.pdf l16.pdf l17.pdf l18.pdf l19.pdf l20.pdf

Lectures

Videos of lectures are here; see also the lecture slides.

Lecture of Wednesday 16 September at 12.15.
An introductory lecture. I warn that second year is harder than first year, so if you did OK without turning up to lectures or trying too hard in first year, then don’t necessarily assume you can do the same this year.
Lecture of Thursday 17 September at 10:15. (video)
I fire up SML.
Lecture of Thursday 17 September at 15:15. (video)
We write some nontrivial programs. I discover a one-page SML crib sheet and like it; you could do far worse than work through it yourself.
Lecture of Thursday 24 September at 10:15. (video)
I prepare you for the lab at 13:15. We don’t quite manage to cover lists.
Tutorial of Thursday 24 September at 13:15.
We do tutorial 6. I take a lot of good questions about function types.
Lecture of Thursday 24 September at 15:15. (video)
The fun continues.
Lecture of Wednesday 30 September at 12.15. (video).
Lecture of Thursday 1 October at 10:15. (video).
Lab of Thursday 1 October at 13:15.
We look more at the tutorials.
Lecture of Thursday 1 October at 15:15. (video).
Lecture of Wednesday 7 October at 12.15. (video).
We discuss polymorphism. We also discussed Wednesday smiling in the Addams Family Values. Enjoy. By the way, if anybody is wondering what having a small baby crawling around your house is like; well, it’s exactly like this.
Lecture of Thursday 8 October at 10:15. (video).
Lab of Thursday 7 October at 13:15.
Labs begin. Questions are here.
Lecture of Thursday 8 October at 15:15. (video).
Lecture of Wednesday 14 October at 12.15. (video).
I switch to PolyML (rlwrap poly). We implement factorial “up to a threshold” and note the use of accumulator variables and partial application. We consider user-defined polymorphic inductive datatypes and ask what the essence of a binary tree is.
Lecture of Thursday 15 October at 10:15. (video).
Lab of Thursday 15 October at 13:15.
Questions are here.
Lecture of Thursday 15 October at 15:15. (video).
We make a start on Python.
Lecture of Wednesday 21 October at 12.15. (video).
Half-a-dozen programs to calculate factorial. Recursion (and its limits in Python). Memoisation. Iterators. Lazy vs eager evaluation (cf. iterators and ML functional abstraction over unit type).
Lecture of Thursday 22 October at 10:15. (video).
Lab of Thursday 22 October at 13:15.
Questions are here.
Lecture of Thursday 22 October at 15:15. (video).
We finish Python! Notes are here.
Lecture of Wednesday 11 November at 12.15. (video).
We start Prolog and consider resolution, backtracking, and (the danger of) looping.
Lecture of Thursday 12 November at 10:15. (video).
Lab of Thursday 12 November at 13:15.
Questions are here; note in particular the Python questions.
Lecture of Thursday 12 November at 15:15. (video).
We continue with Prolog and consider arithmetic.
Lecture of Wednesday 18 November at 12.15. (video).
Prolog lists.
Lecture of Thursday 19 November at 10:15. (video).
We consider assert(happy) and retract(happy) and retractall(happy), and more.
Lab of Thursday 19 November at 13:15.
Questions are here.
Lecture of Thursday 19 November at 19:15. (video).
More on Prolog.
Lecture of Wednesday 2 December at 12.15. (video).
Revision lecture.

See also
- lectures from last year,
- the list of tutorials below.

rlwrap

rlwrap gives BASH-style history and completion at the command line. If you don’t know what that means then trust me—-you want this.

Run SML, PolyML, Python 3, and SWI Prolog by respectively typing

rlwrap sml
rlwrap poly
rlwrap python3
rlwrap swipl

Tutorials

- tut06.pdf - tut07.pdf - tut08.pdf - tut09.pdf - tut10.pdf

See also:

- Study class 1.

Labs

Labs are here.

Labs from last year are here:

- lab07.pdf - lab08.pdf - lab09.pdf - lab10.pdf - lab11.pdf

The exam

A mock paper is available in two flavours:
- Without solutions.
- With solutions.
Attempt the one without solutions first.

Also:

In addition:
- These 50 Chuck Norris facts will be examinable.
- So will all 93 of these rules of cycling (my personal favourites: rules 9, 12, and 14).

Interesting webpages

So far I have mentioned the following webpages during lectures:
- A Wired article about functional programming (Erlang and Haskell) being used by WhatsApp and Facebook. A worthwhile read.
- A rather beautiful article by Paul Graham about functional programming (Lisp) used in a startup. Also a very worthwhile read.
- If you liked Paul Graham’s essays, you could also look at The hundred-year language and Revenge of the nerds.
- A one-page SML crib sheet. Very helpful.

Course resources

Rosetta code is worth at least one visit, and not just because you’re doing F28PL.

Local stuff

- Lecture videos.
- Lecture slides.
- Tutorials.
- Labs.

ML

- Study class 1.
- Example SML programs (from last year, but still useful), and also
- The standard SML basis library. A useful read to explore built-in functions.
- A one-page SML crib sheet. Very helpful.
- These ML lecture notes from the University of Washington are succinct and very clear.

Python

There’s some really really good stuff online, including:
- Learn python the hard way.
- Learning Python.
- This online Python course, in particular the page on recursion.

Prolog

- Example Prolog programs.
- Bill Wilson’s Prolog dictionary.
- The Prolog tutorial by Paul Brna and Tamsin Treasure-Jones dates back to 1996 and is still great.
- Lydia Sinapova’s Prolog Class Notes.

Required reading

You are required to read the following short essays, which discuss imperative programming (represented by C, Pascal, and Java), functional programming (represented in the essays by Lisp and in this course by ML), and logic programming (represented by Prolog).
I may base a discussion question in the exam on material from these essays.

  1. Beating the averages,
  2. The hundred-year language, and
  3. Revenge of the nerds.

A bit about me

I am a researcher in theoretical computer science. My research is mostly in formal logic.
Everybody calls me Jamie but my name is actually Murdoch. You can contact me by e-mail on “gabbay at macs hw ac don’ttypethis uk”. My office is G.50 Earl Mountbatten Building.

The students

Ah, well. I’m glad you asked. You should be second year undergraduate students. Let me know if this is not the case; I’d be interested to know!

A propos nothing in particular

- Revised log levels proposal: “FYI” “WTF” and “OMG” (John Barnette)