PLDG Talks

  • Polytypic Programming (Nov. 2, 2001)

    Routine infrastructure functions (e.g., pretty printers, parsers, equality and comparison, mapping and folding) are often times obvious and tedious to write for new, user-defined datatypes. Polytypic programming aims to relieve the programmer of this tedium by allowing her to write such a function once, while its specialization to different instances of datatypes happens without further effort from the user. In this talk, I'll motivate polytypic programming with some examples and introduce one approach for writing and specializing polytypic functions. My aim is to keep this mostly practical, with an eye on using these features; we'll leave the deeper type-theoretic investigation for another time.

  • Local CPS Conversion (Feb. 22, 2002)

    One important task faced by compilers for functional languages is efficiently translating nested and higher-order functions into machine code. Of particular importance is the translation of nested loop structures: in order to be competitive with imperative languages, loops expressed with functions and recursion must compile to machine code that is similar to the output of an equivalent loop structure expressed using "for" and "while" loops. This week, I'll present Local CPS Conversion, a transformation (and supporting analysis) that increases the number of tail calls to known functions in a direct-style compiler. These tail calls to known functions can be compiled to explict "gotos", thereby achieving an efficient machine code implementation.

    I'll be drawing from the following two papers: 1) Local CPS conversion in a direct-style compiler, and 2) Optimizing Nested Loops Using Local CPS Conversion, both available from the Moby homepage: http://moby.cs.uchicago.edu

  • Cycle Therapy: A Prescription for Fold and Unfold on Regular Trees (June 7, 2002)

    Creating and manipulating cyclic data structures can be tricky in declarative languages. One natural subset of cyclic data structures are those representing regular trees -- trees which may be infinite, but have only a finite number of distinct subtrees. I'll talk about ways of implementing an unfold (anamorphism) operator in both lazy and strict languages, where the result is a cyclic (rather than infinite-lazy) data structure. The usual fold (catamorphism) operator can also be implemented, but is undefined on an infinite tree when used with a strict combining function. Instead, I'll define and show how to implement a cycfold operator with slightly different, but more useful, semantics on cyclic data structures. Finally, we'll look at cycamores, an abstract data type, to simplify the use of cyclic structures representing regular trees.

    The paper, which appeared in PPDP'01, is available at: http://types.bu.edu/reports/Tur+Wel%3APPDP-2001.html

  • Template Meta-programming for Haskell (October 18, 2002)

    I'll discuss a proposed extension to the purely functional programming language Haskell that supports compile-time meta-programming. With the system, a programmer can construct programs (and program fragments) at compile-time, which further allows a programmer to implement such features as polytypic programs, macro-like expansion, user directed optimizations, and the generation of supporting data structures and functions. We'll see how a gensym-like operator can be incorporated into a purely functional language, how a staged type-checking algorithm supports powerful code generation without the need for dependent types, and how reification of programmer-written components can be used to analyze the structure of previously written/compiled code.

    The paper, which appeared in the '02 Haskell Workshop, is available at: http://research.microsoft.com/Users/simonpj/Papers/meta-haskell/index.htm

  • Flattening Combinators: Surviving Without Parentheses (February 6, 2003)

    Due to some scheduling shuffling, a quickie forthcoming Journal of Functional Programming: Theoretical Pearl by Chris Okasaki.

    A combinator expression is _flat_ if it can be written without parentheses, that is, if all applications nest to the left, never to the right. We will explore a simple method for flattening combinator expressions involving arbitrary combinators.

    http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#jfp03

  • Library Design (September 5, 2003)

    This week, we'll put the "discussion" back into the "Programming Languages Discussion Group" with an open forum on library design. This won't be a presentation, per se; rather, it will be a chance to share experiences, anecdotes, and thoughts on how the design of libraries can/should be integrated into language design. Below, Nate and I have cobbled together a list of issues/questions that should provide a good starting point for discussion.

    If anyone out there has particular experience with the STL and would be willing to share them, it would be greatly appreciated; that is one obvious candidate in the design space that I know virtually nothing about.

    One essential for the success of a general-purpose language is an accompanying standard library that is rich enough and efficient enough to support the basic, day-to-day tasks common to all programming. Libraries provide the vocabulary with which a language can be used to say something about something. Without a broad common vocabulary, a language community cannot prosper as it might.

    -- John Reppy & Emden Gasner, The Standard ML Basis Library (Preface)

    A collection of leading questions:

    • What is a "library"?
    • What belongs in a "standard" library?
    • What belongs in an add-on library?
      • I/O
      • Data structures
      • Regexps
    • What makes a library successful?
    • What makes a library well-designed?
    • Are successful libraries necessarily well-designed?
    • What language features help library design? library implementation?
    • What language features hinder library design? library implementation?
      • polymorphism
      • parameterized types
      • subclassing
      • type classing
      • operator overloading
      • exceptions
      • module systems
    • What is the role of documentation in the success of a library?
    • What is the role of design philosophy?
    • Can design be codified? Can it be imposed on other libraries?
    • How should libraries be standardized?
    • How should libraries evolve?
    • What are examples of good library design? bad library design?

    Example libraries:

    • The Standard ML Basis Library

      These web pages contain the interface specifications for the modules of the SML Basis Library, which is a standard library for the 1997 Revision of SML[CITE]. The SML Basis Library provides interfaces and operations for basic types, such as integers and strings, support for input and output (I/O), interfaces to basic operating system interfaces, and support for standard datatypes, such as options and lists. The Library does not attempt to define higher-level APIs, such as collection types or graphical user-interface components. These APIs are left for other libraries.

      The design philosophy of the SML Basis Library is to use the SML module system as an organizing tool. All type, exception, and value identifiers are bound in some module. A small number of these, which are called pervasive identifiers, are also bound at top-level (i.e., without qualification). In addition, the top-level environment defines overloading of some identifiers.

    • The Objective Caml Library
    • The Caml Light/OCaml Hump
    • Haskell 98 Language and Libraries
    • JavaTM 2 Platform, Standard Edition, v 1.4.2: API Specification
    • Standard Template Library Programmer's Guide
    • Edison

      Edison is a library of functional data structures implemented in Haskell. It supports three main families of abstractions: sequences, collections (e.g., sets and priority queues), and associative collections (e.g., finite maps). This paper summarizes the design of Edison, with particular attention to how that design is influenced by details of Haskell.

    • BLAS
    • GNU C Library

  • A Safe Runtime System in Cyclone (December 5, 2003)

    By popular demand (alright, it was really just Nate and Michael chatting in my office), I will present some recent joint work with Greg and Dan Wang on implementing a safe runtime system in Cyclone. I will outline the implementation of a simple Scheme interpreter and a copying garbage collector that manages the memory allocated by the interpreter. The entire system including the garbage collector is implemented in Cyclone, a safe dialect of C, which supports safe and explicit memory management. I will describe the high-level design of the system, report preliminary benchmarks, and compare this approach to other Scheme systems. Preliminary benchmarks demonstrate that one can build a system with reasonable performance when compared to other approaches that guarantee safety. More importantly one can significantly reduce the amount of unsafe code needed to implement the system.