Course meetings

TIES542 Principles of Programming Languages, Spring 2017

Please read about the following tasks related to the meetings elsewhere:

Some of the readings are only accessible through the university network. Use VPN if necessary.

Note that meetings are held in Finnish only.

Meeting 18 on Thursday, 9 March 2017 at 10:15

This is the final meeting of this course.

Preliminary task.

Read the following essay:

  • Andreas Stefik and Stefan Hanenberg: The Programming Language Wars: Questions and Responsibilities for the Programming Language Community. Onward! 2014 Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, 283–299, 2014. doi:10.1145/2661136.2661156

Also consider the following questions in advance:

  • What challenges do you see the in programming language field for the next decade or so?
  • What did you learn from this course?
  • How do you feel this course format has worked?

Take-home task for those who missed the meeting:

Write at least one page on the questions above, and submit in PDF to Koppa on or before Thursday, 16 March 2017.

Meeting 17 on Monday, 6 March 2017 at 16:15

We will discuss programming language research generally.

Preliminary task.

Read the following essay:

  • Stefan Hanenberg: Faith, Hope, and Love: An essay on software science's neglect of human factors. OOPSLA '10 Proceedings of the ACM international conference on Object oriented programming systems languages and applications, 933–946, 2010. doi:10.1145/1932682.1869536

Pay attention particularly to Hanenberg's classification of research methods. You do not need to (but, of course, may) agree with him about the importance of human factors research.

As you are reading, think back to all the research papers we have studied on this course. What kinds of research methods have they used and what kinds of questions do they (attempt to) answer?

Can you think of any questions that you would like to see answered by research into programming languages? (You do not need to know whether it has already been researched or not.) How would such a question be researched?

Take-home task for those who missed the meeting:
Submit a writeup (at least one page) discussing the above questions in PDF format to Koppa on or before Monday, 13 March 2017.

Meeting 16 on Thursday, 2 March 2017 at 10:15

Preliminary assignment.

Think about everything you have learned on this course (and otherwise know) about the issue of choosing a statically or dynamically typed language, or the issue of designing a language to be either statically or dynamically typed. Try to come up with at least three arguments for static typing and at least three arguments for dynamic typing, and try to figure out how one (who disagrees with the conclusion) could respond to such arguments. Also, try to form an opinion of your own on this topic.

Additional reading for those who are interested:

  • Sebastian Okon and Stefan Hanenberg: Can We Enforce a Benefit for Dynamically Typed Languages in Comparison to Statically Typed Ones? A Controlled Experiment. Proceedings of the 2016 IEEE 24th International Conference on Program Comprehension (ICPC), 2016. doi:10.1109/ICPC.2016.7503719

Take-home task for those who missed the meeting:

Come up with arguments both for and against static typing (as opposed to dynamic typing). Try to find a good counterargument for each. Then evaluate each argument:

  • Is the argument strong or weak? Why?
  • Is it possible to disagree reasonably about the argument's strength?
  • What factors might cause different people to reasonably take different stances on that argument?

Finally, state and defend your own position on the matter.

Submit a writeup (at least one page) in PDF format to Koppa on or before Thursday, 9 March 2017.

Meeting 15 on Monday, 27 February 2017 at 16:15

We will study and discuss issues related to late binding and inheritance in object-oriented languages

Preliminary reading.

Read the following works before the meeting or working on the take-home task.

  • Antero Taivalsaari: On the Notion of Inheritance. ACM Computing Surveys 28 (3), 438–479, 1996. doi:10.1145/243439.243441
    Read only sections 1–2 (pages 438–457).
  • Roland Ducournau: Implementing Statically Typed Object-Oriented Programming Languages. ACM Computing Surveys 43 (3), a18, 2011. doi:10.1145/1922649.1922655
    Skip Section 6.

Additional reading for those who are interested.

Take-home task for those who missed the meeting:

Discuss the following questions based on the preliminary reading and what you otherwise know about the topic:

  • What is inheritance?
  • What is late binding?
  • What should inheritance and late binding look like in a programming language?
  • Should a good programming language support inheritance and late binding?
  • What do you find confusing or unclear about this topic?

Submit your writeup (at least one page) in PDF format to Koppa on or before Monday, 6 March 2017.

Meeting 14 on Thursday, 23 February 2017 at 10:15

We discuss the issues in typing the subclass relation of mainstream object-oriented languages.

Preliminary reading.

Read the following papers and be prepared to discuss the arguments made in these papers. Do not spend too much time trying to make sense of the formal definitions.

  • William R. Cook, Walter L. Hill, and Peter S. Canning: Inheritance is not Subtyping. In POPL '90 Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 125–135, 1990. doi:10.1145/96709.96721
  • Sukyoung Ryu: ThisType for Object-Oriented Languages: From Theory to Practice. ACM Transactions on Programming Languages and Systems 38 (3), a8, 2016. doi:10.1145/2888392
    Skip the appendix.

Meeting notes: Lecture notes

Take-home task for those who missed the meeting:
Summarize, in your own words, the issue discussed in the two papers and in the meeting notes. Try to figure out what its relevance is to major object-oriented languages like Java. Submit a PDF (at least one page) to Koppa on or before Thursday, 2 March 2017.

Meeting 13 on Monday, 20 February 2017 at 16:15

We will study the polymorphic Hindley–Milner type discipline.

Preliminary reading.

Read the following and attempt all its exercises (except Exercise 15) before the meeting or before working on the take-home task:

  • Introduction to lambda calculus, part 5 (Example 17 and onward) [PDF, LaTeX]
  • Introduction to lambda calculus, part 6 [PDF, LaTeX]

Take-home task for those who missed the meeting:

  • Explain in your own words the informal meaning of principal type.
  • Try to solve Exercises 14 and 16.
    • Note that in Exercise 16, you need to use both the procedure described in the middle of page 5 of part 6 (above Example 20) and the type equation solution algorithm described in Section 2.5.2
  • What did you find unclear or difficult, or particularly interesting?

Submit your answers in PDF format to Koppa on or before Monday, 27 February 2017.

Meeting 12 on Thursday, 16 February 2017 at 10:15

Note the unusual location of this meeting.

We will practice critical reading of experiment reports.

Preliminary reading.
Read first the following document:

Then, in light of the guidance of that document and using all of your existing critical reading skills, read and prepare to evaluate the following two research reports:

  • M.E. Sime, T.R.G. Green, D.J. Guest: Scope marking in computer conditionals—a psychological evaluation. International Journal of Man-Machine Studies 9 (1), 107–118, 1977. 10.1016/S0020-7373(77)80045-X
  • Phillip Merlin Uesbeck, Andreas Stefik, Stefan Hanenberg, Jan Pedersen, and Patrick Daleiden: An empirical study on the impact of C++ lambdas and programmer experience. In Proceedings of the 38th International Conference on Software Engineering (ICSE '16), 760-771, 2016. 10.1145/2884781.2884849

Take-home task for those who missed the meeting:

Discuss the two reserach reports above critically using the first document's questions as a guide. At the end, state your personal, subjective conclusion as to whether the paper is reliable and what you learned from it. Also discuss what you found difficult or unclear about assessing experiment reports.

Submit your writeup (1–2 pages) in PDF format to Koppa on or before Thursday, 23 February 2017.

Meeting 11 on Monday, 13 February 2017 at 16:15

We will study a model of ML and Haskell, and develop our understanding of formal type systems.

Preliminary reading.
Read the following and attempt all its exercises before the meeting or before working on the take-home task:

  • Introduction to lambda calculus, part 5 [PDF, LaTeX]

Meeting notes:

  • disorganized notes
  • We did not reach example 17 or the exercises after it. We will get back to them next Monday.

Take-home task for those who missed the meeting:
Discuss the following questions:

  • What algebraic types are, in your understanding?
  • Are there any points you do not understand regarding the abstract syntax or reduction rules of the ML/Haskell model.
  • Explain in your own words what happens in Example 16.
  • Write in the ML/Haskell model language a function that removes the first element of a nonempty list. You may assume that the list is not empty. Then compute using the reduction rules the value of that function applied to Cons 1 (Cons 2 Nil).

Submit in PDF format to Koppa on or before Monday, 20 February 2017.

Meeting 10 on Thursday, 9 February 2017 at 10:15

Note the unusual location of this meeting

We will consider the idea of type systems, and study the simple type theory.

Preliminary reading.
Read the following works before the meeting or working on the take-home task:

  • Luca Cardelli and Peter Wegner: On Understanding Types, Data Abstraction, and Polymorphism. ACM Computing Surveys 17 (4), 471–523, 1985.
    doi:10.1145/6041.6042
    Read only Section 1 (pages 471–485)
  • Stephen Kell: In Search of Types. In the Proceedings of the Onward! 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, 227–241, 2014. doi:10.1145/2661136.2661154
  • Introduction to lambda calculus, part 4 [PDF, LaTeX]

Also attempt all the exercises in the last work.

Meeting notes: here

Take-home task for those who missed the meeting:

  • What different views on the concept of type are discussed in the preliminary reading, and what is common to all views? What is your own view of the concept?
  • What do the type rules (1)–(5) of the last work say, speaking informally?
  • Attempt to use the type system given in the last work to determine whether \(\lambda x : \mathbf{Num} \cdot x + 4\) has the type \(\mathbf{Num}\).
  • What was unclear or difficult for you?

Submit a PDF to Koppa on or before Thursday, 16 February 2017.

Meeting 9 on Monday, 6 February 2017 at 16:15

We will examine the concept of paradigm in the context of programming and programming languages. Where it came from and is it useful?

Preliminary reading.
Read the following works before the meeting:

  • Peter Godfrey-Smith: Theory and Reality. An Introduction to the Philosophy of Science. University of Chicago Press, 2003. Accessible online in the university network.
    Read only Chapter 5 (pages 75–86).
  • Robert W. Floyd. Paradigms of Programming. Communications of the ACM 22 (8), 455–460, 1979. doi:10.1145/359138.359140
  • Allen L. Ambler, Margaret M. Burnett, and Betsy A. Zimmerman: Operational Versus Definitional: A Perspective on Programming Paradigms. Computer 25 (9), 28–43, 1992. doi:10.1109/2.156380
  • Shriram Krishnamurthi: Teaching Programming Languages in a Post-Linnaean age. ACM SIGPLAN Notices 43 (11), 81–83, 2008. doi:10.1145/1480828.1480846

If you want a summary, read additionally Section 2.2.3 of my dissertation (linked to earlier).

Take-home task for those who missed the meeting:
Discuss the following questions based on the preliminary reading:

  • What does the term paradigm mean
    • according to Kuhn (as summarized by Godfrey-Smith)
    • according to Floyd
    • according to Ambler et al
    • according to Krishnamurthi
    • in your own opinion?
  • In your own view, is the paradigm concept useful in discussing programming languages?

Submit in PDF form (at least one page) on Koppa on or before Monday, 13 February 2017.

Meeting 8 on Thursday, 2 February 2017 at 10:15

We will study the environment problem, and how common programming constructs can be modeled in a Lisp-like language with no new primitive constructs.

Preliminary reading.
Read the following works:

  • Joel Moses: The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem. ACM SIGSAM Bulletin no 15, 13–27, 1970. doi:10.1145/1093410.1093411
  • Guy Lewis Steele, Jr., and Gerald Jay Sussman: LAMBDA: The Ultimate Imperative. AIM-353, 1976. Link
    Skip (do not read) Section 4 (Parameter passing mechanisms).

When reading the first paper, keep in mind that the same problem exists in modern languages. Any language that supports lambdas (that includes recent versions of C++, Java, and C#) has to deal with it. Any language that allows defining a function or method inside another function or method has the same problem (so it exists even in older Java, where it occurred in the context of anonymous inner classes). C deals with it by forbidding free variables (apart from globals) in functions. Try to see how the issues discussed are relevant to your favourite modern languages.

The environment problem is also related to the variable capture issue of lambda calculus. How?

When reading the second paper, try to see how the usual programming constructs can be reduced into just lambda calculus. The examples are in Scheme, but try to see how they also apply to your favourite modern programming language. Further, try real hard to understand what continuation passing style is.

Also have a brief look at Simple Lisp, particularly eval.c. Note that it is known to be buggy at this time.

Meeting notes.

Take-home task for those who missed the meeting:
Write a summary of the first paper (Moses), at least one page, using your own words. Try to grasp how the problem discussed appears in modern languages like Java or C#. Also point out what you find confusing, unclear, or particularly interesting, and discuss why. You may use the summary of the lecture linked above as a further source of ideas. Submit in PDF format to Koppa on or before Thursday, 9 February 2017.

Meeting 7 on Monday, 30 January 2017 at 16:15

We will study dynamically typed lambda calculi, including a model of Lisp.

Preliminary reading.
Read the following works and also attempt all the exercises given in the last one.

  • Introduction to lambda calculus, part 2 (only section 1.7) [PDF, LaTeX]
  • Introduction to lambda calculus, part 3 [PDF, LaTeX]

Take-home task for those who missed the meeting:
Attempt to answer or solve all of these in writing (at least one page):

  • What is wrong?
  • How does \(\mu x \cdot t\) work, speaking informally?
  • What happens in Example 12?
  • What happens in Example 14?
  • Solve Exercise 6, using at least two different reduction orders.

If you have trouble with any of it, discuss what the trouble appears to be. Submit on or before Monday, 6 February 2017, in PDF format to Koppa.

Meeting 6 on Thursday, 26 January 2017 at 10:15

We will continue studying the untyped lambda calculus. Key concepts to be discussed include

  • \(\alpha\) conversion and equivalence
  • \(\beta\) reduction
  • variable binding and free variables
  • variable substitution
  • variable capture (and the related concepts lexical, static, and dynamic scope)
  • normal forms
  • the Church–Rosser property
  • normal order and applicative order reduction
  • weak applicative order reduction
  • weak head normal form
  • graph reduction

Preliminary reading.
Read the following document and attempt all the exercises in it before the meeting.
Introduction to lambda calculus, part 2 [PDF, LaTeX]

Meeting notes The last section (1.7) was postponed to Monday.

Take-home task for those who missed the meeting:
Submit a document in PDF format to Koppa on or before Thursday, 2 February 2017 containing the following:

  • Discuss three issues with the preliminary reading. Issues may be things you found confusing or unclear, or things you found especially interesting. Why did you choose it? If it is a problem, how can it be fixed?
  • Attempted solutions for all the exercises except Excercise 5.

Meeting 5 on Monday, 23 January 2017 at 16:15

We will study the basics of lambda calculus and continue studying denotational semantics.

Preliminary reading. Read the following work and try to solve the exercise given in it, before coming to the meeting:

  • Introduction to Lambda Calculus, Part 1: PDF, LaTeX

Meeting notes: PDF, LaTeX

Take-home task for those who missed the meeting:
Read through the meeting notes linked above. Then consider the following questions:

  • Why do we need both abstract and concrete syntax? Why could we not live with only one of them?
  • How does one read the equations (1)–(6) in the meeting notes? What do they say, in plain English?
  • Do you think you will be able to compute \((\lambda xy\cdot x \mathbin* 2 + y)\,3\,4\) using the definitions in the preliminary reading and in the meeting notes?
  • Is there anything confusing or unclear about the preliminary reading or the meeting notes?

Submit a writeup of your answers (at least one page) in PDF to Koppa on or before Monday, 30 January 2017.

Meeting 4 on Thursday, 19 January 2017 at 10:15

We will talk about Strachey's fundamental ideas and particularly one of its progeny: the idea of formal, denotational semantics for simple programming languages.

Preliminary reading. Read the following works before the meeting:

  • Peter D. Mosses: A Foreword to ‘Fundamental Concepts in Programming Languages’. Higher-Order and Symbolic Computation, 13 (1), 7–9, 2000. doi:10.1023/A:1010048229036
  • Christopher Strachey: Fundamental Concepts in Programming Languges. Higher-Order and Symbolic Computation, 13 (1), 11–49, 2000. doi:10.1023/A:1010000313106
    Only up to the end of section 3.3, so only pages 11–25.
  • R. D. Tennent: The Denotational Semantics of Programming Languages. Communications of the ACM 19 (8), 437–453, 1976. doi:10.1145/360303.360308
    Only up to the end of section 3, so only pages 437–442.
  • Denotational semantics for the calculator language [PDF, LaTeX]

Meeting notes:

  • See here
  • sample computation using the calculator language denotational semantics [PDF, LaTeX]

Take-home task for those who missed the meeting:
Consider the following concepts that occur in the Strachey paper:

  • lvalue, rvalue
  • idealized/abstract store
  • expression, command
  • referential transparency
  • environment
  • bound/free variable
  • applicative structure
  • evaluate vs apply
  • "device originated by Schönfinkel" (p. 21)
  • "commands can be considered as functions wchich transform \(\sigma\)" (p. 24)

Please write a short summary of each; if you do not understand a concept, try to formulate what you find confusing or unclear about it.

Then try to compute let x = 5 in 2 * x using the the denotational semantics for the calculator language (linked above). If you are not able to do it, try to comment on why; what is unclear or confusing?

Submit your writeup in PDF format to Koppa on or before Thursday, 26 January 2017.

Meeting 3 on Monday, 16 January 2017 at 16:15

Preliminary plan is to discuss the anatomy of programming languages, how PLs are described, and the concept of a definitional interpreter.

Bring a laptop computer if possible.

Preliminary reading. Read the following before the meeting:

  • The anatomy of a programming language
  • Section 2.3 (pages 29–31) of Antti-Juhani Kaijanaho: Evidence-based programming language design: a philosophical and methodological exploration. Dissertation, University of Jyväskylä, Jyväskylä Studies in Computing 222, 2015; Available in JYX.

Take-home task for those who missed the meeting: Make a list of the three biggest issues you have with the preliminary reading. They can be unclear concepts or ideas, or claims that you find dubious. If you have no problems with the text, choose as your issues things you find the most interesting. Try to find external sources discussing your issues (do not take a long time, 30 minutes max for all three together). Then write about your issues in light of what you found: why is it an issue and whether it can be resolved somehow. Submit your writeup (at least one page) in PDF format to Koppa on or before Monday, 23 January 2017.

Notes made during meeting: see here

Supplemental reading for those who are interested:

Meeting 2 on Thursday, 12 January 2017 at 10:15

We will discuss and ponder various forms of argument in the field of programming languages as well as the various ways that a programming language may develop.

Preliminary reading. Read the following before the meeting:

  • Argument assessment
  • Stefan Hanenberg: Doubts about the Positive Impact of Static Type Systems on Programming Tasks in Single Developer Projects: An Empirical Study. In Theo d'Hondt (ed): ECOOP 2010 – Object-Oriented Programming, 24th European Conference, Maribor, Slovenia, June 21-25, 2010, Proceedings. Berlin: Springer, Lecture Notes in Computer Science 6183, 300–303, 2010. doi:10.1007/978-3-642-14107-2_14
  • Guy L. Steele: Growing a Language. Higher-Order and Symbolic Computation 12 (3), 221–236, 1999 . doi:10.1023/A:1010085415024

Take-home task for those who missed the meeting: Consider the following questions regarding both papers listed above in preliminary reading:

  • What is the main conclusion of the paper?
  • What are the most important premises of the paper's argument?
  • Are you convinced by the paper's argument? If you are, why? If you are not, try to formulate a counter-argument.

Write your answers in a PDF document and submit to Koppa on or before Thursday, 19 January 2017.

Supplemental reading for those who are interested:

  • Stefan Hanenberg: An experiment about static and dynamic type systems: doubts about the positive impact of static type systems on development time. In the OOPSLA'10 Proceedings of the ACM international conference on Object oriented programming systems languages and applications, 2010. Also published in ACM SIGPLAN Notices 45 (10), 22–35, 2010. doi:10.1145/1869459.1869462
  • Brad A. Myers, Andreas Stefik, Stefan Hanenberg, Antti-Juhani Kaijanaho, Margaret Burnett, Franklyn Turbak, Philip Wadler: Usability of Programming Languages Special Interest Group (SIG) meeting at CHI 2016. CHI EA '16 Proceedings of the 2016 CHI Conference Extended Abstracts on Human Factors in Computing Systems, 1104–1107, 2016. doi:10.1145/2851581.2886434
  • Usability of Programming Languages website

Meeting 1 on Monday, 9 January 2017 at 16:15

The plan is to discuss the course goals and teaching approach, and finally ponder the concept of a programming language: how can it be defined – or can it?

Preliminary reading: Read the following documents before the meeting:

Take-home task for those who missed the meeting: Give examples of things that clearly are programming languages, things that clearly are not programming languages, and things for which the question is debatable (there are reasonable arguments both for and against them being programming languages). Using these examples as test cases, can you come up with a definition (giving both necessary and sufficient conditions) of the concept of a programming language that correctly handles your examples? Correct handling means that those that clearly are PLs or clearly are not PLs are correctly classified, and for those for which arguments can be made either way, the definition gives a definite answer one way or the other.

You are not expected to come up with a coherent answer, just consider the various issues in writing. Submit your resulting document, which must be at least one page long, in PDF format to Koppa on or before Monday, 16 January 2017.

Supplemental reading for those who are interested: Antti-Juhani Kaijanaho: Evidence-based programming language design: a philosophical and methodological exploration. Dissertation, University of Jyväskylä, Jyväskylä Studies in Computing 222, 2015; Available in JYX

  • On the definition of programming languages, see Chapter 2.1.
  • On conceptual analysis, see Chapter 3.

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.