Tasks

TIES542 Principles of Programming Languages, Spring 2017

Passing this course requires completing certain set tasks. Please take note of the deadlines policy and do practice academic honesty.

In all writing tasks, unless otherwise indicated, a page is not a precise concept and I will not be counting words or lines or measuring line spacing with a ruler. However, if you make your font or line spacing way too large, I will notice and I might consider your page not to actually be a page. My advice is that if you want to write as little as possible while being safe, stick to the standard manuscript page (liuska in Finnish): A4 or US letter page size, 12 point font with 1.5 or 2 line spacing and one inch (2.5 cm) margins. The font needs to be easily legible; a Times Roman variant is a good choice if you have no special reason to vary.

Mandatory, monitored tasks

TASK: Personal Study Plan

Mandatory, deadline: January 16, 2017; submit to Koppa in PDF format.

Write (in Finnish or English) a personal study plan for the principles of programming languages. It must be at least one page long. Discuss in this plan the following questions:

What is my background? In particular, what in my background led me to study the principles of programming languages?
What are my larger goals at this time, particularly in relation to my studies and career?
How can studying the principles of programming languages advance my larger goals?
What learning goals do I set for myself regarding the principles of programming languages that I hope to achieve during this course?

Approach this task as a thinking, not writing, task please. The teacher will not share your plan with anyone else. The pass criterion for this task is that the document is at least one page long and addressess all of these questions in some manner; it will not be assessed in any other way. Note that whether you achieve your personal learning goals or not will not affect your grade from this course.

Added in response to question in the margin: A page is not a precise concept and I will not be counting words or lines or measuring line spacing with a ruler. However, if you make your font or line spacing way too large, I will notice and I might consider your page not to actually be a page. My advice: if you want to write as little as possible while being safe, stick to the standard manuscript page (liuska in Finnish): A4 or US letter page size, 12 point font with 1.5 or 2 line spacing and one inch (2.5 cm) margins. The font needs to be easily legible; a Times Roman variant is a good choice if you have no special reason to vary.

Are there any restrictions pertaining to the font, font size and line spacing?

— 05 Jan 17

18 TASKS: Course meetings

Mandatory, deadline (for option 2) one week after the beginning of each course meeting

There are two meetings per week, one on Monday starting at 16:15 and one on Thursday at 10:15. Each meeting lasts approximately 90 minutes.

There are two ways to complete these tasks (you may choose freely which you use for each meeting separately).

Option 1: Attend the meeting. An attendance list will be circulated at the beginning and at the end of the meeting; your name must appear on both lists. Do not arrive late or leave early. If you have a very good excuse, the teacher may allow you to add your name to the first list late or to the second list early.

Option 2: A take-home task will be announced on or before the day after the meeting. The task will be designed to have you work on the same material and issues as we do in the meeting. The task is expected to take about 90 minutes, but time consumed is not a measure of completion unless explicitly so stated. You can find the tasks on the Meetings page

TASK: Participate in online discussion

Mandatory. Deadlines below.

Join the course's group in Yammer. If you have not used it before, follow the IT services guide for logging in and read their Yammer guide. You can find the group by searching for TIES542. The teacher will approve your join request as soon as possible.

Write at least two messages (in either Finnish or English) to the course's Yammer group. There are two requirements:

Both messages must discuss some aspect of the principles of programming languages. Off topic and course procedure (tasks etc) related messages do not count.
At least one message must be a response to someone else's message.

Deadlines:

post your first message on or before February 1, 2017
post your second message on or before March 14, 2017

You are encouraged to participate in the discussion throughout the course, but only two messages are mandatory. Points are available for further messages as specified in another task below.

Mandatory, unmonitored tasks

The following tasks are in principle mandatory but whether you complete them or not is not recorded, nor will any points be awarded for completing them.

0–18 TASKS: Preliminary reading for meetings

For some meetings, preliminary reading will be assigned. You are expected to have read it before coming to that meeting or before starting to work on the corresponding take-home task.

You should read the material well enough that you know what its main points are. You should try to form an opinion on whether the material makes a good argument or not and whether you believe in its conclusions. If the material contains technical content (such as formal definitions) that you are unable to grasp, make a note of this but do not use too much time trying to decipher it. You are not expected to learn the material thoroughly, just to be able to discuss it in the meeting or in your take-home task intelligently.

For Monday meetings, preliminary reading will be assigned no later than the previous Thursday.

For Thursday meetings, preliminary reading will be assigned no later than the previous Monday.

You may find the assigned reading on the Meetings page

Point-awarding tasks

The following tasks are not mandatory, but whether you complete them or not and how well you complete them will determine your grade (once you have completed all monitored mandatory tasks). Most tasks will award a variable number of points depending on how well you do them.

Tasks will be announced throughout the course and listed here. The intent is that there will be enough tasks published before the end of the course to award at least 16 points (not counting any points marked optional).

Points thresholds for grades are as follows:

Minimum points	Grade
0	1
3	2
6	3
9	4
12	5

TASK: Continue to participate in online discussion (1–2 points)

Deadline: only messages posted on or before March 14, 2017, count toward this task. Points must be collected by sending email to the teacher on or before March 15, 2017.

Once you have posted the mandatory two messages as required above, additional messages to the Yammer group produce points as follows:

at least 10 messages gives you 1 point
if you fulfill the 1 point criterion and at least 8 of your messages are responses to other people's messages, you get an additional 1 point

Multiple messages by you responding to the same message count as one single message. Responses to yourself do not count at all.

Only messages discussing the principles of programming languages count here. Off topic messages do not count, nor do messages dealing with the course procedures (tasks, meeting schedules etc.)

Procedure for collecting points. Keep track of your own messages and once you have reached enough messages, send an email to the teacher saying what points (1 or 2) you are claiming.

TASK: Reimplement the calculator using other technologies (1–2 points)

Deadline February 7, 2017. Submit under the source code submission rules.

Write an interpreter for the calculator language specified in this document using some other technology. For example, use Haskell instead of Java.

Your interpreter must be compilable and runnable either using freely available tools under Ubuntu 16.10 or in Agora computer classrooms using only software already installed there.

Include in your submission a README file giving compilation and usage instructions, including what compilers and libraries must be installed.

Added to clarify on 2017-01-17: The task is to reimplement the whole interpreter, capable of reading the calculator language as a character input and outputting the result (or diagnosing a static semantics violation). Thus, you will likely need a lexer, a parser, an AST, a static checker, and an evaluator (corresponding to the Interpreter class of the example interpreter).

Assessment:

1 point if the interpreter looks correct (even if seriously buggy) and mostly does not include any code borrowed directly from me or others
2 points if the 1 point criterion is fulfilled and the interpreter implements exactly the same language as defined in this document with no significant bugs

TASK: Write an interpreter for the untyped or the dynamically typed lambda calculus extended with nonnegative integers (1–3 points + 1 optional point)

Deadline February 14, 2017. Submit under the source code submission rules – or if your submission contains no source code, you may choose to submit in PDF format to Koppa.

Write an interpreter for the untyped or the dynamically typed lambda calculus extended with nonnegative integers, as it is specified in the following documents:

Lambda calculus part 1 [PDF, LaTeX]
Meeting 5 notes [PDF, LaTeX]
Lambda calculus part 2 [PDF, LaTeX]
Lambda calculus part 3 [PDF, LaTeX]

Subtasks:

Define precisely a concrete syntax for the language (both lexical and phrase-structure syntax) using some formal or informal means other than source code or executable code. (1 point)
Write a lexer, parser, and an AST module for the language, and a main program that reads a term as a character string from the input and outputs a human-readable description of its abstract syntax tree. (1 point)
Write an interpreter module based on \(\beta\) reduction using normal-order evaluation together with reduction rules for arithmetic. Have the main program print out all steps of the reduction, or just the final result, as the user requests. In the latter case, if the term has no \(\beta\) normal form, you program may (but is not required to) hang. (1 point)
Optional (difficult): Write a (different) interpreter module closely following the denotational semantics. Do not base this interpreter on reduction rules. Have the main program print out a human-readable representation of the result, if it is a number. If the result is \(\bot\), your program may (but is not required to) hang. If the result is not a number, an informative error message is acceptable. (1 point)

Additional instructions:

You may choose freely which subtasks you complete.

Your program should not crash in any situation.

The user should be able to specify which subtask's output to show.

Your program must be compilable and runnable either using freely available software under Ubuntu 16.10 or in Agora computer classrooms using only software already installed there.

Include in your submission a README file giving compilation and usage instructions, including what compilers and libraries must be installed. Also describe any bugs you are aware of. Also indicate in the README file which subtasks you have completed in your own view and whether the language you implement is untyped or dynamically typed.

Include your lexical and syntactic grammar (first subtask) in plaintext, LaTeX source or PDF format within the source code package (git or zip). If you do only the first subtask (and do not submit any source code), you may submit in PDF format to Koppa.

Assessment:

For all subtasks, the assessment criterion is whether the program parts required appear correctly written and perform in tests adequately. There should be no critical bugs, but complete bug freeness is not expected.

If you both specified the concrete syntax and wrote the lexer and the parser, you can get both points only if it is reasonably easy to see that they describe the same language (disregarding minor bugs). If the languages differ significantly or it is difficult to establish whether they do so or not, you get only one point from these two together.

TASK: Learn a Lisp (1–3 points)

Deadline: Tuesday, 21 February 2017. Submit under the source code submission rules. If your submission contains no source code, you may also submit in PDF format to Koppa.

Overview of task.

Learn a (real-world) Lisp. I recommend Common Lisp, Scheme, Racket, or Clojure. If you are feeling curious and a bit brave, Emacs Lisp is also a possibility. Talk to me before choosing some other Lisp dialect.

Subtasks and points.

Figure out what features of your Lisp dialect correspond to the features of the Lisp model discussed in the course materials, and how do they differ. How would the factorial function be written in your Lisp dialect? Describe your findings in writing (at least one page). (1 point)
Write in your Lisp dialect, using facilities that are as close as possible to those described in the course materials, the following functions. In your submission, indicate which implementation (including version and OS) you used to test them, and include a transcript of a testing session. (1 point)
- a function counting the elements in a list
- a function computing the average of a list of numbers
- a function reversing a list
Write in your Lisp dialect a small but complete program that does something at least marginally useful. (Hello World and greeting the user are not sufficiently useful programs.) Include in your submission instructions for how I can test your code (on Ubuntu 16.10, if possible). (1 point)

TASK: Write an essay on the concept of paradigm (1–3 points)

Deadlines:
Submit the complete draft on or before Tuesday, 28 February 2017.
You will be given a deadline for submitting your revised essay separately.

General instructions.
Write an essay, at least three pages, asserting and defending a claim regarding the meaning and usefulness of the term paradigm in the field of programming languages.

You may write your essay in Finnish or English. Your essay must cite sources, at least those listed as preliminary reading for Meeting 9. Your essay does not need to accept the view of any of the sources as correct, but it should at least discuss them.

What is an essay?
An essay is essentially one continuous argument written in prose form.

An essay should, near the beginning, stake a clear claim: a proposition or thesis which could in principle be true or false.
Then, an essay should discuss this claim from multiple points of view: it should offer an argument that supports the thesis, and state and reject (by giving clear arguments) the most important counterarguments that a reader might offer.
Finally, an essay should bring the argument to a close and conclude (at least rationally, but ideally convincingly) that the claim made in the beginning is true.

An essay is a form of prose writing. It should use clear and correct language. A good essay offers a plausible argument and is not difficult to read. An excellent essay is both convincing as an argument and a pleasure to read.

Phase one.
Submit a complete draft in PDF format to Koppa on or before Tuesday, 28 February 2017.

Phase two.
The teacher will give you feedback as soon as possible. The feedback will be given to you in written form, usually by email. The teacher may also give you oral guidance, but that will not be counted as feedback for the purposes of this task.

Based on the feedback, revise your essay. The feedback will specify a deadline for submitting your revision (typically one week after the feedback is sent to you).

Include, as an appendix to your essay, a discussion of all the changes you made and how your revision deals with the feedback.

Your revision must take into account all of the feedback. If you think some point made by the teacher's feedback is wrong or otherwise does not merit a change to the essay, you must nevertheless discuss that point in the appendix and defend your choice of not making a change.

Submit your revised essay, together with the appendix, in PDF format to Koppa within the deadline specified for you.

Points:

You will be awarded one point upon submitting your complete draft.
You will be awarded another point upon submitting your revised essay.
If the teacher considers your revised essay well written and well argued (even if he does not ultimately agree with the claim), he will award you a third point.

The first two points require that the submission fulfills the following minimum requirements:

The complete draft and the revised essay are on topic.
The complete draft and the revised essay comply with the requirements of academic honesty.
The complete draft and the revised essay cite all the required literature.
The complete draft is at least three pages long.
The revised essay, together with the appendix, address all points made in the feedback.

The third point is a matter of the teacher's judgment, but it cannot be awarded if you have not earned both of the other points.

TASK: Write a Hindley–Milner type checker (1–3 points + 2 optional points)

Deadline March 7, 2017. Submit under the source code submission rules – or if your submission contains no source code, you may choose to submit in PDF format to Koppa.

Modify the lambda calculus interpreter you wrote for a previous task so that it performs polymorphic Hindley–Milner typechecking (with or without generalization). For specifications, see

Lambda calculus part 5 [PDF, LaTeX]
Lambda calculus part 6 [PDF, LaTeX]

If you have not yet submitted your lambda calculus interpreter, you may submit it (and claim points from it) as part of your submission here, notwithstanding the earlier task's deadline.

Subtasks:

Specify precisely a concerete syntax for defining algebraic data types and global variables (that is, toplevel function definitions). (1 point)
Modify your lexer, parser, and AST modules to support algebraic data types and global variables (toplevel function definitions). (1 point)
Write a Hindley–Milner type checker without generalization (as described in part 6). (1 point)
Optional: Extend your type checker to perform top-level generalization (as described in part 6). (1 point)
Optional: Extend one of your interpreter modules to handle algebraic data types and global variables. (1 point)

Additional instructions:

You may choose freely which subtasks you complete (though there are obvious dependencies between them).

Your program should not crash in any situation.

It should be possible for the user to give algebraic data type definitions, global variable definitions (toplevel definitions), and a lambda term as input. The output should always include the term's principal type or a type error, even if the evaluation of the term never terminates.

A global variable definition (also known as a toplevel function definition) means equations of the form f = ... that the user may write outside any term. The intent is that such global definitions introduce variables to the initial type environment at type checking and to the initial environment at denotational semantics. For reduction semantics, the simplest idea is to support so called \(\delta\)-reduction: a free variable of the term is a \(\delta\)-redex if it has a global definition, and \(\delta\)-reduction means simply replacing the variable occurrence with the definition of the variable (taking care to avoid variable capture).

You do not need to support recursive global (toplevel) definitions.

Your program must be compilable and runnable either using freely available software under Ubuntu 16.10 or in Agora computer classrooms using only software already installed there.

Include in your submission a README file giving compilation and usage instructions, including what compilers and libraries must be installed. Also describe any bugs you are aware of. Also indicate in the README file which subtasks you have completed in your own view, including whether you claim any additional points from the earlier lambda calculus task.

Assessment:

Note that your goal should be clarity and correctness. Runtime speed is a secondary issue.

TASK: Perform calculations in the lambda calculus formalisms (1–3 points)

Deadline Tuesday, 14 March 2017, for initial submission. A separate deadline will be given for corrections based on teacher feedback.

Subtasks

Each subtask is worth one point. You may choose which subtasks you attempt.

Solve Exercise 5 as it is given in Introduction to Lambda Calculus, Part 2 [PDF, LaTeX].
Solve either Exercise 12 or Exercise 13 (but not both) as it is given in Introduction to Lambda Calculus, Part 5 [PDF, LaTeX].
Determine the principal type of the term \[ \mathbf{let}~x=\lambda y\cdot \textit{Cons}~y~x~\mathbf{in}~x \] or, if it has no type, explain why. You may assume the algebraic type \(\textit{List}~\alpha\) with the constructors \(\textit{Cons} : \alpha \to \textit{List}~\alpha \to \textit{List}~\alpha\) and \(\textit{Nil} : \textit{List}~\alpha\). Use the Hindley–Milner formalism described in Introduction to Lambda Calculus, Part 6 [PDF, LaTeX].

Assessment criteria

Earning a point requires that the answer is clear and substantially correct. Your answer must include all the steps needed to reach the result (do not skip over steps or combine multiple steps into one).

For each genuinely attempted but incorrect answer, the teacher will give you feedback. You will have the opportunity to correct your mistakes based on that feedback.

Submission instructions

Submit your answers in PDF format to Koppa. You may (but are not required to) submit multiple PDFs.

TASK: Write an essay on static versus dynamic typing (1–3 points)

Write an essay that asserts and defends a claim regarding the choice between static or dynamic typing in the field of programming languages.

You must cite at least two relevant research articles as sources, but you may choose which ones.

Deadline for the complete draft is Tuesday, 21 March 2017.

In all other respects, the instructions in the previous essay task apply.

TASK:Feedback to the teacher (1 optional point or candy)

Deadline. Tuesday, 14 March 2017

Write at least one page of free-form text in Finnish or English addressing the following questions:

What did you expect to learn in this course?
What did you actually learn in this course?
The stated learning outcomes for this course are "After this course, you the student will be able (1) to argue intelligently for or against propositions regarding programming languages, taking into account the state of the art and of the science, and (2) to evaluate such arguments critically". Did you achieve this partially or wholly? Why, or why not?
How do you feel, subjectively, about the course format?
Is there any other feedback you would like to give the teacher about this course?

Also, please explicitly answer the following three questions:

If I write about this course in an academic publication, may I use your answers here as source material?
Do you have any objection to me writing about this course in an academic publication? (If you do, what is your objection?)
Which form of compensation for your answers would you like?
- 1 point (taken into account when computing your course grade)
- one retail package of candy, chocolate, or other similar edible item of your choice (which is commonly sold in Jyväskylä grocery shops at a price of at most 5 euros per package)

Submit in PDF format to Koppa.

Note that this submission is not anonymous. For anonymous feedback, use the regular course feedback form.

If I use your answers as source material, I will take care not to reveal your identity.