Programming Language Design — CSCE 604: Class Projects

Presentation Schedule:

Project Assignments

General rules

The expectations of the project are roughly:

  1. Study a current interesting recent problem in the area of programming languages and the solutions offered by recent research on it. I have given a few starting points—they are just that, starting points. You should do literature search to find out more relevant sources.
  2. Summarize your findings in a written report, that demonstrates your understanding of the topic, and that offers the reader well-organized introduction to the topic, and knowledge of what is the state of the art regarding the problem. You should write on relevant related work as well. Reports will be due a few days before grades must be turned in, exact date will be announced later.
  3. Prepare a presentation for the class, where you educate others of your findings. Presentations will be during the last two weeks of class.

In the ideal case, you may find ways to contribute further to the work you have studied. In the short time frame we have, I don't expect that many get very far with that—the above three itemized requirements are surely sufficient. Nevertheless, keep your eyes open.

Projects can be completed in pairs or individually. If any of the suggestions below interest you, please send me email or contact by other means. I will update this page to reflect which project is assigned to whom. In case of conflicts, first to claim a project topic has the right of way.

Starting points for projects

Variant parametric types, wildcards, …

Java wildcards, and related language mechanisms, deal with how to mix subtyping and generics, not considering them as orthogonal features. This leads to rather interesting type systems, and there has been active work on this area during the past few years. Some starting points:

Atsushi Igarashi and Mirko Viroli. ACM Transactions on Programming Languages and Systems, 28(5):795-847, September 2006. see: http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/papers/variance.html

Adding wildcards to the Java programming language, http://portal.acm.org/citation.cfm?id=968162

http://www.jot.fm/issues/issue_2004_12/article5/

Gradual Typing

Should a language be statically typed or dynamically typed? Can it be both, allowing the programmer to choose when to use static typing and when to forgo with typing at compile-time and rely on run-time checks for type safety. Siek et al. have recently done more work on this idea, and provide a nice formalism that allows a smooth transition between dynamic and static typing.

Starting point: ECOOP 2007 – Object-Oriented Programming (2007), pp. 2-27. by Jeremy Siek, Walid Taha http://www.springerlink.com/content/a052j27um6829356/

Other related work: Erik Meijer and Peter Drayton. Static Typing Where Possible, Dynamic Typing When Needed: The End of the Cold War Between Programming Languages. Proc. OOPSLA'04 Workshop on Revival of Dynamic Languages. http://research.microsoft.com/~emeijer/Papers/RDL04Meijer.pdf

Type classes vs. object oriented programming

A recent paper:

Software extension and integration with type classes, Lämmel and Ostermann, http://portal.acm.org/citation.cfm?id=1173706.1173732

studies how ad-hoc polymorphism (overloading) is quite expressive, and solves with ease many issues known problematic in OO languages. The abstract of the paper says:

The abilities to extend a software module and to integrate a software module into an existing software system without changing existing source code are fundamental challenges in software engineering and programming-language design. We reconsider these challenges at the level of language expressiveness, by using the language concept of type classes, as it is available in the functional programming language Haskell. A detailed comparison with related work shows that type classes provide a powerful framework in which solutions to known software extension and integration problems can be provided. We also pinpoint several limitations of type classes in this context.

Generalized Algebraic Data Types

GADTs are the a hot topic in the functional programming community. They can be realized in the context of OO as well:

A. Kennedy and C.V. Russo. Generalized Algebraic Data Types and Object-Oriented Programming. OOPSLA 2005. http://research.microsoft.com/~akenn/generics/gadtoop.pdf

What are GADTs? How they relate to OO? Can they be expressed in, say, C++ or Java as well? Why or why not?

LINQ

Erik Meijer, Confessions Of A Used Programming Language Salesman (Getting The Masses Hooked On Haskell), OOPSLA 2007 Essays. http://research.microsoft.com/~emeijer/Papers/es012-meijer.pdf

Find answers to questions, such as, what is LINQ, by what kind of mechanisms the program gets access to parts of the same program's structure, and what kind of expressiveness is thus achieved. In particular, find out about the connection between monads and LINQ. This blog post might be helpful in getting started with the connections with monads: http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx

Dependent types

Dependent type systems offer very expressive typings, but on the other hand complicate type checking—type checking becomes theorem proving. Dependent types have recently received much attention. What are dependent types? What is the state of the art in exploiting dependent types in practical programming. One particularly interesting language to study Agda http://wiki.portal.chalmers.se/agda/pmwiki.php, another is Epigram: http://www.e-pig.org/

Another useful source http://okmij.org/ftp/Computation/lightweight-dependent-typing.html

And a recent gathering over dependent types: http://sneezy.cs.nott.ac.uk/darcs/DTP08/

Type-checking Modular Multiple Dispatch with Parametric Polymorphism and Multiple Inheritance.

By Eric Allen, Justin Hilburn, Scott Kilpatrick, Sukyoung Ryu, David Chase, Victor Luchangco, and Guy L. Steele Jr. Submitted for publication, December 2010. http://www.mpi-sws.org/~skilpat/papers/multipoly-ecoop.pdf

Multiple dynamic dispatch poses many problems for a statically typed language with nominal subtyping and multiple inheritance. In particular, there is a tension between modularity and extensibility when trying to ensure at compile time that each function call dispatches to a unique most specific definition at run time. We have previously shown how requiring that each set of overloaded definitions forms a meet semi-lattice allows one to statically ensure the absence of ambiguous calls while maintaining modularity and extensibility.

In this paper, we extend the rules for ensuring safe overloaded functions to a type system with parametric polymorphism. We show that such an extension can be reduced to the problem of determining subtyping relationships between universal and existential types. We also ensure that syntactically distinct types inhabited by the same sets of values are equivalent under subtyping. Our system has been implemented as part of the open source Fortress compiler.

Multiple dispatch in practice

Why are mainstream object oriented languages "single-dispatch" only? Alternatives have been studied a lot (Cecil, MultiJava, CLOS, …) but none of those have really caught on. Here's an interesting study that might shed some light on the issue:

http://portal.acm.org/citation.cfm?id=1449808&dl=ACM

Can run of the mill programs be proven correct?

Find out about a tool, such as Spec#, preform some practical experiments with it, and report the results.

Invertible Syntax Descriptions: Unifying Parsing and Pretty Printing

Rendel Tillmann and Klaus Ostermann http://www.informatik.uni-marburg.de/~rendel/unparse/rendel10invertible.pdf

Parsers and pretty-printers for a language are often quite similar, yet both are typically implemented separately, leading to redundancy and potential inconsistency. We propose a new interface of syntactic descriptions, with which both parser and pretty-printer can be described as a single program. Whether a syntactic description is used as a parser or as a pretty-printer is determined by the implementation of the interface. Syntactic descriptions enable programmers to describe the connection between concrete and abstract syntax once and for all, and use these descriptions for parsing or pretty-printing as needed. We also discuss the generalization of our programming technique towards an algebra of partial isomorphisms.

Suggest a paper from recent OOPSLA, ECOOP, POPL, PLDI

Author: Jaakko Jarvi <jarvi@cse.tamu.edu>

Date: 2011-04-05 22:59:24 CDT

HTML generated by org-mode 6.33x in emacs 23