When is a functional program not a functional program?
John Longley

This talk is concerned with a rather surprising fact: there are ML programs whose behaviour is completely "functional" (in the sense that they give equal outputs for equal inputs), but the functions they compute cannot be written in the purely functional fragment of ML.

As a simple example, consider the function F : ((unit->unit)->unit)->bool specified by:

        F f = true      if f bot = ()
        F f = false     if f bot diverges  but f top = ()
        F f diverges    otherwise
where top, bot may be defined by
        fun top()=() and bot()=bot().

This function can be implemented using exceptions, or using references. In both cases, the observable behaviour of the implementation is completely functional: if f1,f2 are themselves functional and compute the same function, then (F f1) has the same effect as (F f2). However, there's no way of implementing this F in pure functional ML.

This observation came out of some theoretical work of mine on different notions of "sequentially computable functional". It turns out that there's a natural class of sequential functions, with several good mathematical characterizations, that includes the above example and "all things like it". Even better, there's a "universal" such function E, such that any other function of this kind can be written in the functional fragment of ML extended by E.

This suggests the possibility of a programming language that incorporates the power of E into its purely functional fragment - there are several plausible reasons why this might be useful. In fact, something like this can be achieved just by writing an implementation of E in SML (which I have recently done). This allows one to experiment with the kinds of programs that would be possible within this enhanced functional fragment.

In this talk I will explain these ideas in more detail, illustrating them with concrete bits of ML code. After giving some simple examples I'll try to explain what the universal functional E does. I'll then turn to applications, and suggest some of kinds of programming task for which my extended functional language might be suitable. Finally I'll make some tentative remarks on the possibility of incorporating these ideas either into an implementation of SML or into some future language design.

The talk will be an attempt to take some theoretical ideas and turn them into something practical. I'm hoping that some of you, whose interests and experience are more practical than mine, might be inspired to develop some of these ideas a bit further...


Talk to be given 29th Jan. 1998, Room 2511 JCMB


Return to t he ML-Club Home Page.