Seminar: Features of Programming Languages

This seminar will be in english / Dieses Seminar findet auf Englisch statt.

The history of programming languages is rife with the cross pollination and adoption of features from esoteric languages into so called "main stream" languages. Examples of such features include generics, multiple inheritance, objects and curried functions. This seminar offers a platform for students to become familiar with this history, and closely analyze and evaluate common features in programming languages. Student's will accomplish this through the reading, examination, and discussion of selected papers and texts. Students are to select a topic, familiarize themselves with the topic, prepare a written report and hold a scientific lecture on their topic, as well as participate in the discussion of other lectures.

• Multiple inheritance
• Information hiding
• Lazy Evaluation
• Objects
• Operator overloading (also called ad-hoc polymorphism)
• Generics (also called parametric polymorphism)
• Reflection and Meta-programming
• Type Inference
• Modules
• Substructural Type Systems and Memory Safety (linear types, affine types)
• Session Types (π calculus) and Concurrent Programming
• Lambdas and Closures in OOP languages

Multiple Inheritance

• Cardelli, Wegner: Understanding Types, Data Abstractions, and Polymorphism
• Liskov: A Behavorial Notion of Subtyping
• Cook, Hill, and Canning: Inheritance is Not Subtyping

Information Hiding

• Parnas: Criteria to be Used in Decomposing Systems
• Ostermann, Giarrusso, Kästner, Rendel: Revisiting Information Hiding
• Findler and Flatt: Modular OOP With Units and Mixins

Lazy Evaluation

• Ariola, Felleisen: The Call-By-Need Lambda Calculus
• Wadsworth: Semantics and Pragmatics of Lambda-Calculus
• Peyton Jones: Implementation of Functional Programming Languages
• Peyton Jones: Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine

Objects

• Cook: On Understanding Data Abstraction, Revisited
• Cardelli, Wegner: Understanding Types, Data Abstractions, and Polymorphism
• Liskov and Zilles: Programming with Abstract Data Types
• Nygaard and Dahl: The Development of the Simula Languages

Operator Overloading

• Cardelli, Wegner: Understanding Types, Data Abstractions, and Polymorphism
• Oliveira and Cook: Extensibility for the Masses
• Krishnamurthi, Felleisen, Friedman: Synthesizing Object-Oriented and Functional Design to Promote Re-use
• Clifton et al: MultiJava: modular open classes and symmetric multiple dispatch for Java

Generics

• Oliveira and Cook: Extensibility for the Masses
• Krishnamurthi, Felleisen, Friedman: Synthesizing Object-Oriented and Functional Design to Promote Re-use
• Wadler, Odersky, Stoutamire, Bracha: Adding Genericity to the Java Programming Language

Reflection and Meta-Programming

• Cantwell: Procedural Reflection in Programming Languages
• Demers and Malenfant: Reflection in Logic, Functional and Object Oriented Programming: A Short Comparative Study
• Mcllroy: Macro Instruction Extensions of Compiler Languages
• The term Homoiconicity comes from: Mooers and Deutsch: Programming Languanges for Non-Numeric Processing: TRAC, a Text Handling Language
• McCarthy: Recursive Functions of Symbolic Expressions and Their Computations by Machine, Part 1
• Maes: Concepts and Experiments in Computational Reflection
• Chiba: Load-Time Structural Reflection in Java

Type Inference

• Damas and Milner: Principle type-schemes for functional programs
• Milner: A thoery of type polymorphism in programming
• Palsberg, Shwartzbach: Object-oriented type inference
• Pottier: A Framework for Type inference with Subtyping
• Type inference in Languages with subtyping (like most OOP) is problematic, see:
  • Pierce: Bounded quantification is undecidable
  • Curien, Ghelli: Coherence of subsumption

Modules

• Findler and Flatt: Modular OOP with units and Mixins
• Parnas: criteria to be used in decomposing systems
• (Book), Peirce: Advanced Topics in Programming Languages (See Chapter 8)
• Ostermann, Giarrusso, Kastner, Rendel: Revisiting information hiding
• Strnisa et al: The java module system: core design and semantic definition

Substructural Type Systems and Memory Safety (linear types, affine types)

• Garbage Collection
  • Invented in LISP: McCarthy: Recursive Functions of Symbolic Expressions and Their Computations by Machine, Part 1
  • Wilson: Uniprocessor garbage collection techniques
  • See also: Stefanovic et al: Older-first garbage collection in practice
  • and: Detlefs et al: Garbage-first garbage collection
• Linear and Affine Types
  • Wadler: Linear types can change the world!
  • Tov, Pucella: Practical affine types

Session Types (π calculus) and Concurrent programming

• Dezani-ciancaglini and De'Liguro: Sessions and Session Types: An Overview
• Gay et al: Modular session types for distributed OOP
• Milner: The Polyadic pi-Calculus: A Tutorial
• Dijkstra: Solution of a problem in concurrent programming control
• Hewitt et al: A universal modular ACTOR formalism for artificial intelligence

Lambdas and closures in OOP languages

• Fundamentals:
  • Anonymous functions: McCarthy: Recursive Functions of Symbolic Expressions and Their Computations by Machine, Part 1
  • Closures: Landin: The mechanical evaluation of expressions
• Lambdas have been around since 1958 (LISP), Java got lambdas in 2014, Other papers of interest:
  • (Article) Bracha et al: Closures for the Java Programming Language
  • Cross the Gap from Imperative to Functional Programming through Refactoring
  • Khatchadourian: An Empirical Study on the Use and Misuse of Java 8 Streams
  • Khatchadourian: Safe automated refactoring for intelligent parallelization of Java 8 Streams
  • Mazinanian, Ketkar, Tsantalis, Dig: Understanding the use of lambda expressions in Java