Elements of Programming Languages University Homepage School Homepage School Contacts School Search Elements of Programming Languages - Fall term 2017 The web page for last year's edition of this course is available here. Summary Elements of Programming Languages is an Honours course in Informatics on the foundations and practicalities of programming language design. It is normally to be taken in year 3 but as a level 10 course it can also be taken by year 4 or MSc students. Few computer scientists will ever design a new, general-purpose language, but most will need to learn several languages over the course of a career, and many will design new domain-specific languages for restricted problem domains. Programming language design involves many subtle choices and tradeoffs among performance, convenience, and elegance. Although some of the earliest programming languages (such as FORTRAN) are still going strong, new language designs and features are still being proposed, and it seems that we are still far from fully understanding the space of possible language designs. Elements of Programming Languages covers the essential programming structures for managing data and controlling computation, as well as abstractions that facilitate decomposing large systems into modules. The course also covers pragmatics of programming languages, including abstract syntax, interpretation and domain-specific language implementation. Elements of Programming Languages is not about learning or programming in one specific language, rather, it covers the basic elements needed to understand the next 700 programming languages, or design a new one. Course Staff Lecturer: James Cheney TA: Simon Fowler Course Structure There will be 20 lectures, starting Monday, September 18th, 2017. The lectures include the course introduction, three guest lectures, 16 lectures of examinable course content, and a course review lecture. Lectures are 1510-1600 on Monday and Thursday in 7 Bristo Square, Lecture Theatre 2. In case of any discrepancy between this web page and the University timetable, the latter takes precedence. There is a laboratory session on Wednesday, September 28th from 1210-1400 in Forrest Hill labs 3.D01 and 3.D02, with a not-for-credit coursework exercise due one week later. This exercise does not count toward your final grade, but will be returned with formative feedback. Tutorials are held in weeks 3-10. Participation in tutorials (including working on tutorial problems in advance) is expected and the tutorials cover examinable material that is part of the course. There will be three coursework exercises. The first two are evaluated and returned for formative feedback. The third is worth 25% of the final grade. Most students will take the exam in the April exam diet. Visiting undergraduate students who are here for semester 1 only will take the exam in the December diet. (There are a few UG3 courses whose exam is in December for all students this year, but EPL is not one of them.) Please see the University's exam schedule page to check on the date / time of your exam, and please discuss with the ITO or your Personal Tutor if you are uncertain which exam you should attend. Course timetable The exact schedule of lectures is subject to change, depending on availability of guest lecturers. Week Begins Tue Lec Tutorials/Lab Fri Lec Assignments 1 18 Sep Intro Lec 1 2 25 Sep Lec 2 Assignment 1 (Lab) available Lec 3 3 2 Oct Lec 4 Tut 1 Lec 5 Assignment 1 due, Assignment 2 available 4 9 Oct Lec 6 Tut 2 Lec 7 5 16 Oct Lec 8 Tut 3 Lec 9 6 23 Oct Lec 10 Tut 4 Guest Lec 1 Assignment 2 due ; Assignment 3 available 7 30 Oct Lec 11 Tut 5 Guest Lec 2 8 6 Nov Lec 12 Tut 6 Lec 13 9 13 Nov Lec 14 Tut 7 Lec 15 10 20 Nov Guest Lec 3 Tut 8 Lec 16 Assignment 3 due 11 27 Nov Review No tutorial Mock exam discussion Mock exam available Key: Introductory/review lecture (non-examinable) Guest lecture (non-examinable) Examinable lecture Office hours James Cheney (IF 5.29): Tuesdays 11:30-12:30 TAs: By appointment The course lecturer and teaching assistants are available (during Semester 1) for discussion of course material at the above hours. Meetings outside these hours are also possible by appointment. If you are enrolled in this course, you are on the course mailing list. This list can be used for general questions. There is also a Piazza page for EPL where you may ask questions that other students or course staff can answer. Course staff will try to respond within 1 working day. This means that if you ask a question at 5:01pm on Friday, you should not be surprised if it is not answered until Monday afternoon or Tuesday morning. We will of course try to be more responsive before deadlines. Topics Abstract syntax and name-binding; Lexical vs. dynamic scope Modelling programming language features using inference rules Interpreters as a way of defining and exploring language features Domain specific languages, translators, and pragmatics of language processing Some of the following topics: data structures: pairs/record types; variant/union types; recursion abstracting data: overloading; generics; ad hoc vs. parametric polymorphism control structures: goto, loops, case/switch, exceptions abstracting control: procedure call/return; function types; continuations design dimensions: eager vs. lazy evaluation; purity vs. side-effects; state object-oriented features: objects, classes, interfaces, subtyping, (multiple) inheritance Advanced topics/guest lectures on concurrent, parallel, distributed programming, security, or verification Course Text and Supplementary Material There is no required course text. The following resources are recommended reading to supplement the course materials. Specific reading suggestions are listed along with the lectures below. Practical Foundations for Programming Languages (PFPL2), second edition, by Robert Harper (Cambridge University Press 2016). Both editions of the book are available electronically through the library, and there are print copies of the first and second editions in the library. A draft of the second edition is also available on the author's webpage; some chapter references may differ between the two editions. Concepts in Programming Languages (CPL), by John Mitchell (Cambridge University Press). Also available at no cost through the University Library's ebook access. Martin Odersky and Tiark Rompf, Unifying functional and object-oriented programming with Scala, Communications of the ACM, Vol. 57 No. 4, Pages 76-86 Other useful books on programming languages include: Types and Programming Languages, by Benjamin Pierce (MIT Press). In the University Library. Essentials of Programming Languages, by Friedman and Wand (MIT Press) presents programming languages via a series of interpreters (in Scheme). In the University library (including electronic access). The book Functional Programming in Scala by Chisuano and Bjarnason and is a well-written introduction to functional programming in Scala (targeted at mainstream programmers, not academics), similar to the way we will mostly be using it in this course. A library copy has been requested but it is reasonably priced. The following are some historically-influential papers on programming languages, and may be of interest to students interested in pursuing further study of programming languages. Peter J. Landin. The next 700 programming languages. Communications of the ACM, 9(3):157-166, March 1966. John C. Reynolds. Definitional interpreters for higher-order programming languages. Higher-Order and Symbolic Computation, 11(4):363-397, 1998. Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, August 1978. Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science, 1:125-159, 1975. John C. Reynolds. Towards a theory of type structure. In Colloque sur la Programmation, Paris, France, volume 19 of Lecture Notes in Computer Science, pages 408-425. Springer-Verlag, 1974. C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576-580 and 583, October 1969. John Hughes. Why functional programming matters. From "Research Topics in Functional Programming" ed. D. Turner, Addison-Wesley, 1990, pp 17-42. Scala The programming language used for lab, tutorial and coursework exercises is Scala. Any DICE machine (i.e. any Linux machine in an Informatics computer lab) should have Scala 2.11 installed; type scala at a command prompt to start the Scala interpreter. Scala has many features in common with functional languages (such as Haskell) and object-oriented languages (such as Java). Prior familiarity with Scala is not needed for EPL, and we will investigate many of these features as part of the course. We will not cover all of Scala's more advanced or experimental features. We will follow a "functional-first" style of Scala programming for most of the course, while most resources on Scala are oriented towards object-oriented programmers familiar with Java, Python or Ruby. Although the lectures, tutorials and lab/assignment handouts should provide all of the information about Scala you need for this course, you might be interested the following resources which cover Scala's features in more depth or from a different perspective. Scala for Java Programmers explains how to map some familiar concepts from Java to Scala. A Tour of Scala covers most of the major features of Scala in bite-size pieces. The Scala Style Guide is also a good source of advice on good Scala coding practice. Finally, if you are especially interested, there is a Coursera MOOC on Functional Programming Principles in Scala that looks like fun. Lab The lab session is scheduled for 12:10-14:00 on Wednesday, September 27 in AT 6.06. The lab handout is here: assignment1.pdf The associated Scala file is here: Assn1.scala Submission instructions: To submit, run the following command on DICE: $ submit epl cw1 Assn1.scala Here is a sample solution: Assn1Solution.scala There will be a 2-hour lab session during Week 2 to ensure that students have an opportunity to learn the basics of Scala needed for later coursework exercises. Students unfamiliar with Scala (i.e., most students) are strongly encouraged to attend and complete the lab assignment. The first hour will consist of an interactive demo of basic Scala programming concepts, following a lab handout (which will also be available in advance). During the second half of the lab session, you will be free to work on the lab exercises on your own or with others, and the course lecturer and lab demonstrator will be available to answer any questions. If you already know Scala: we will (at least initially) be using only a very small "pure" subset of the language, as described in the lab handout. Even if you are already an accomplished Scala programmer, please try to run through the lab and other exercises and do them using only this subset. The lab exercises may be handed in for formative feedback. That is, they will be marked and returned with feedback, but the results do not count toward your final grade. The due date for completed lab assignments is October 6. Tutorials Tutorials start Week 3 (October 2-6). The tutorial group times and membership will be posted early in the semester. See tutorial groups with times and (tentative) membership. Tutorial notes and solutions will also appear here as they become available. Tutorial for week 3. (Sample solution) Tutorial for week 4. (Sample solution) Tutorial for week 5. (Sample solution) Tutorial for week 6. (Sample solution) Tutorial for week 7. (Sample solution) Tutorial for week 8. (Sample solution) Tutorial for week 9. (Sample solution) Tutorial for week 10. (Sample solution) Guest Lectures There is a lot of research on programming languages in the School of Informatics. EPL will feature guest lectures covering more advanced topics that apply or extend ideas covered in the course. Further information will be posted here when the lectures are confirmed. The guest lectures are as follows: October 26: GULCII: Graphical Untyped Lambda Calculus Interactive Interpreter, Claude Heiland-Allen (10am AT 5.04 or 4pm IF G.07) GULCII is an untyped lambda calculus interpreter supporting interactive modification of a running program, with graphical display of graph reduction and sonification of node statistics. This talk covers aspects of using GULCII for live performance, including encodings of data within lambda calculus. November 2: Layering Abstractions: Heterogeneous Programming and Performance Portability. Alastair Murray, Principal Software Engineer, Compilers, Codeplay Software Ltd. Widely used heterogeneous programming models such as OpenCL and CUDA provide programmers a means of exploiting heterogeneous hardware to achieve higher performance. A modern heterogeneous programming model, however, should also aid programmer productivity and allow for portable performance. This talk will give an overview of how this is being achieved by layering abstractions, by providing high-level domain specific approaches for programmers to model problems, and allowing the flexibility for even lower level layers to gain more precise control over hardware. November 20: Rust: using linear and region types to make the Internet more secure. Dr. Keith Wansbrough, Software Engineer, Metaswitch Networks Ltd. Rust is a relatively new programming language which is rapidly gaining traction in industry. It aims to replace C++, using linear types and region types to enforce safe use of pointers while retaining the efficiency required for systems programming. Buffer overflows and incorrect memory management are responsible for a large fraction of recent security vulnerabilities; Rust simply makes these impossible to compile. It's a great example of how the concepts of this course are making a practical difference to modern software engineering. While these lectures don't cover examinable material, we encourage students to attend, as they provide additional context and motivation for the material covered in EPL, and may also be interesting starting points for students interested in doing a Honours project or MSc project on a topic related to EPL. Lecture Slides Lecture slides will be posted here as the course proceeds. The suggested readings cover related material in "Practical Foundations for Programming Languages (second edition)" (PFPL2), "Concepts in Programming Languages" (CPL), and other sources, however, we will cover some topics in a different order or differently than in these textbooks. Course Introduction and Admin (pdf) Related reading: CPL 1 Lecture 1: Abstract Syntax (pdf). Related reading: PFPL2 1.1; CPL 4.1, 5.4.1 Lecture 2: Evaluation (pdf, LArith.pdf). Related reading: PFPL2 2.1-3, 2.6, 7.1, CPL 5.4.2 Lecture 3: Booleans, conditionals, and types (pdf, LIf.pdf). Related reading: PFPL2 4.1-4.2, CPL 5.4.2, 6.1, 6.2 Lecture 4: Variables, scope, and binding (pdf, LLet.pdf). Related reading: PFPL2 1.2, 3.1-3.2, CPL 4.2, 7.1 Lecture 5: Functions and Recursion (pdf, LRec.pdf). Related reading: PFPL2 8, 19.1-2; CPL 4.2, 5.4.3 Lecture 6: Data structures (pdf, LData.pdf). Related reading: PFPL2 10.1, 11.1, CPL 5.4.4 Lecture 7: Records, subtyping, and pattern matching (pdf). Related reading: CPL 6.5; PFPL2 10.2, 11.2-3, 24.1-3 Lecture 8: Polymorphism and type inference (pdf, LPoly.pdf). Related reading: PFPL2 16.1; CPL 6.3-4 Lecture 9: Programs, modules, and interfaces (pdf). Related reading: CPL 9, PFPL2 42.1-2, 44.1 Lecture 10: Objects and classes (pdf). Related reading: CPL 10, 12.5, 13.1-2 Lecture 11: Object-oriented functional programming (pdf). Related reading: Odersky and Rompf Guest Lecture 2 (pdf) Lecture 12: Imperative programming (pdf, LWhile.pdf). Related reading: CPL 4.4, 5.1-2, 8.1 Lecture 13: Small-step semantics and type safety (pdf). Related reading: CPL 6.1-2, PFPL2 5.1-2,2.4,7.2, 6.1-2 Lecture 14: References, arrays and resources (pdf). Related reading: PFPL2 35.1-3, CPL 5.4.5, 13.3 Lecture 15: Evaluation strategies and laziness (pdf). Related reading: PFPL2 36.1, CPL 7.3, 8.4 Guest Lecture 3 (pdf) Lecture 16: Exceptions and Continuations (pdf). Related reading: CPL 8.2-3, PFPL2 29.1-3, PFPL2 30.1-2 Course review lecture (pdf) Assignments There will be three coursework exercises. The first and second are worth 0% of the final grade and the third is worth 25%. Once marked, the coursework will be returned to students with feedback. Assignment 1 Available: September 27 Due: October 6, 4pm Files: Lab handout: assignment1.pdf Initial Scala file: Assn1.scala To submit, run the following command on DICE: $ submit epl cw1 Assn1.scala Here is a sample solution: Assn1Solution.scala Assignment 2 Available: October 6 Due: October 24, 4pm Files: assignment2.pdf (v1.0, updated October 7) Assn2.scala Tests.scala Assn2Solution.jar example1.gir example2.gir example3.gir example4.gir example5.gir example6.gir To submit, run the following command on DICE: $ submit epl cw2 Assn2.scala Sample solution: Assn2Solution.scala Assignment 3 Available: October 25 Due: November 21, 4pm Files: assignment3.pdf (v1.2, updated November 15) Assn3.zip To submit, run the following command on DICE: $ submit epl cw3 Assn3.zip Sample solution: Core.scala Source.scala Desugar.scala Late assignment submission and academic conduct policies Important: Please note that, as with all Informatics courses, unexcused late submissions of coursework will be penalized in accordance with the School policy. Extensions to the deadline to submit are subject to approval by the appropriate Year Organiser (UG3). This course is subject to the School's academic conduct policy regarding plagiarism and acknowledgement of sources. For full details please consult the School's policies: Late coursework and extension policy Good Scholarly Practice: Please remember the University requirement as regards all assessed work for credit. Details and advice about this can be found at: http://web.inf.ed.ac.uk/infweb/admin/policies/academic-misconduct and links from there. Note that, in particular, you are required to take reasonable measures to protect your assessed work from unauthorised access. For example, if you put any such work on a public repository then you must set access permissions appropriately (generally permitting access only to yourself, or your group in the case of group practicals). Feedback Formative feedback provides students with feedback on performance and understanding in time to assist with the assessed aspects of the course (coursework and exam). Elements of Programming Languages offers the following formative feedback: Interaction with tutors in tutorials provides general feedback on understanding. The laboratory assignment will be collected, evaluated, and returned with formative feedback. The first coursework assignment will be collected, evaluated, and returned with formative feedback. The course lecturer has office hours (see above) in which they are available to discuss any aspect of the course. Students are welcome to drop in either individually or in small groups (up to 3 students at a time). In addition, the summatively assessed coursework exercise will be marked, commented and made available for students to collect 2 weeks after submission. Previous Exams This course was introduced in 2015, so there are few previous exams. Past courses "Language Semantics and Implementation", and "Functional Programming and Specification" offered in previous years may cover similar material, but EPL is a different course and its exam will be different. A mock exam is available here: Mock exam Mock exam solution Exam review session slides Past exams for previous Elements of Programming Languages courses are available here. Home : Teaching : Courses Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh
