Aleksandar Nanevski

Functional Programming with Names and Necessity Degree Type: Ph.D. in Computer Science
Advisor(s): Frank Pfenning
Graduated: August 2004

Abstract:

All programs interact with their environments in one way or another: they read and write to memory, query users for input, print out results, send data to remote servers, etc. Because increasingly complex environments result in increasingly difficult and error-prone programming, programming languages should facilitate compile-time detection of erroneous interactions with environments. In this dissertation, I propose variants of modal logic with names, and their related lambda-calculi, as a type theoretic foundation for such languages.

In the first part of the dissertation, I review the judgmental formulation of propositional constructive modal logic, and the definitions of necessity and possibility as universal and existential quantification over possible worlds. In the application to functional programming, possible worlds in modal logic will correspond to execution environments.

The second part investigates the notions of partial judgments; that is, judgments satisfied under some abstract condition. Partial necessity and partial possibility correspond to bounded universal and bounded existential quantification over possible worlds. While the partiality condition may be specified in several different ways, in this dissertation the focus is on the definition of partiality in terms of names. Names are labels for propositions, and a set of names represents the partiality condition obtained as a conjunction of the respective propositions.

In the third part, I discuss applications of modal logic to staged computation and metaprogramming. In these applications, it is frequently necessary to consider a primitive operation of capture-incurring substitution of program expressions into a context, which is naturally expressed in a modal type system.

The last part of the dissertation develops modal type systems for effects. The effects associated with partial possibility are those that permanently change the execution environments, and therefore must be executed in a specific linear order. Writing into a memory location is a typical example. The effects associated with partial necessity are those that may depend on the execution environment, but do not change it -- they are benign, and do not need to be specifically serialized. Examples include memory reads and control flow effects.

Thesis Committee:
Frank Pfenning (Chair)
Dana Scott
Robert Harper
Peter Lee
Andrew Pitts (University of Cambridge)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Functional programming, modal type systems, modal logic, lambda calculus, effect systems, monads, staged computation, metaprogramming