Pawns (logo)

What is Pawns?

Pawns is a functional programming language. It supports algebraic data types, polymorphism, higher order programming and pure declarative code. It is also an imperative programming language. It supports pointers, destructive update and a form of global variables. It combines these two programming paradigms in a tricky way and ensures code that looks like a pure function definition really behaves as a pure function, even if it calls imperative code with "effects" for efficiency.

Why bother?

Pure functional programming allows concise high level code that you can reason about very easily, so its a great way to program. But there are some things for which imperative code is simpler and much more efficient (a factor of at least twenty, even with state of the art functional programming language implementations). For some applications such a speed difference rules out functional programming being used, which is a shame. Besides, it just shouldn't be that way! With Pawns you can write most of your code in the pure functional style, but some parts for which efficiency is critical can be coded in an imperative style and the imperative code can be encapsulated in a declarative interface. Some other functional languages support this general idea but do not encapsulate imperative code to the same extent - if a data structure is built using imperative features it is forever "tainted" and cannot be viewed in a purely functional way.

What are the key ideas?

A key challenge is to ensure code that uses imperative features behaves in a purely functional way. Pawns stands for "Pointer assignment without nasty surprises". In a language like C we can have code such as *ptr1 = val; which changes what ptr1 points to and may also change what other variables point to. One of the design principles of Pawns is that if code can affect the value of a variable (or depends on the variable), this should be obvious. For example, a Pawns statement can have the annotation !ptr2 to indicate it may affect variable ptr2. Even imperative Pawns code avoids the problem of subtle undocumented interactions which can occur in other languages.

Programming with pointers requires the programmer to understand pointer aliasing and sharing of data structures. In Pawns, sharing information is declared, providing documentation and allowing the compiler to understand the sharing and check the declarations are correct. As well as declaring side-effects, the programmer declares what sharing may occur between arguments when a function is called and what sharing may occur when it returns. By tracking possible sharing we can determine if arguments of a function can be updated during its execution. If update is restricted to variables that are local to the function execution, purely functional behaviour is guaranteed. For example, a data structure can be built locally using an imperative style, then returned. Thus imperative code can be encapsulated inside a declarative interface.

Pure functional programming is the default in Pawns. Arbitrary sharing of function arguments and results is possible and update of such data structures is not allowed. However, if enough extra declarations and annotations are supplied, there are no restrictions on what can be updated anywhere.

How can I find out more?

Related languages

The Mars programming language has "assignment without nasty surprises" but no explicit pointers. Nasty surprises are avoided by copying data structures where necessary, as determined by sharing analysis (similar to that done in Pawns). Destructive update of shared data structures is not possible. Programs look imperative but the semantics is more like a pure functional language.

The Discus programming language supports similar low level imperative features to Pawns but uses "region" information rather than sharing information to limit interaction and effects. Disciple does more inference of region and side effect information than is done in Pawns, so there is more potential for "nasty surprises" and doesn't encapsulate effects to the same extent.

ML supports destructive update using data types containing ref and Haskell's STRef monad is similar. The type system limits interaction and effects. This has similar consequences to the Disciple approach with respect to nasty surprises and encapsulation and can also lead to multiple versions of a data type and extra indirection in the representation.

The scripting language Pawn has a similar name to Pawns but they are not at all closely related in other respects. Both are influenced by C. Pawn started life as a cut-down version of C and has no types or pointers (except it supports call by reference). Pawns combines C-style pointers with a nice type system and other benefits of pure functional programming.



Lee