Supervisor

Suitable for

Abstract

PicoML

PicoML is a polymorphically-typed lazy functional language with I/O actions (cf the I/O Monad in Haskell). It has a very flexible concrete syntax, and a very straightforward polymorphic type system. Its only implementation - a prototype - is written in OCaml as direct, closure-based, abstract-syntax tree interpreter. PicoML GitHub Repository

We would like to see a more efficient implementation, as well as one that would make it straightforward to incorporate new features for engaging with external entities (graphics, etc)

The present project would reimplement the language in one or both of the following ways, each of which would first require a reimplementation of parser and type checker – possibly, but not necessarily, in Scala.

1. as a closure-based, abstract-syntax tree interpreter using continuations.
2. as a (Scala) compiler translating to code for an abstract machine - possibly the G-Machine of Lennart Augustsson and Thomas Johnsson - thence to executable code for conventional architecture.

The outcome of the project should be both useable and scrutable: students should be able to read the code of a realistic language implementation.

Mini Haskell

What?

We think that the PicoML language implementation described above would be a very good basis for a new implementation of a simplified variant of Haskell, suitable for introducing that language in such a way that the need for type classes emerges organically from programming practice.

The project would aim to deliver an implementation suitable for use by Haskell novices that would place emphasis on good error diagnostics: both type errors and runtime errors. Availability of such an implementation could make the teaching of functional programming is the secondary school CS curriculum and for home study a practical proposition: thereby liberating at least some pupils from the conceptual straightjackets of Python, C++, etc.

Why?

An important difficulty students have with Haskell and its type system is the (important) notion of type classes: whilst very useful to more advanced Haskell users, they can pose a barrier to learning because what might (in their absence) be a type-error that is straightforward to report and to diagnose, gets reported in terms of instances and classes. For example:

   ghci> max xs
 
   <interactive>:2:1: error:
       • No instance for (Show ([Integer] -> [Integer]))
           arising from a use of ‘print’
           (maybe you haven't applied a function to enough arguments?)
       • In a stmt of an interactive GHCi command: print it

   ghci> max

   <interactive>:1:1: error:
       • No instance for (Show (() -> () -> ()))
        arising from a use of ‘print’
        (maybe you haven't applied a function to enough arguments?)
       • In a stmt of an interactive GHCi command: print it

Of course wise neophytes take their tutors’ advice, and explore the type of the function they thought they were using correctly:

        ghci> :t max
        max :: Ord a => a -> a -> a

and may then realize that what they were after is

        ghci> :t maximum
        maximum :: (Foldable t, Ord a) => t a -> a

But what’s a Foldable? The neophyte has to understand that it’s a constructor class! And the most succinct explanation of that that can be found is

“A constructor class is declared with a type parameter of kind

                * -> *, * -> * -> *

In other words: a constructor class describes behaviour of type constructors, not of ground types.”

Thus in order to understand an inscrutable diagnosis of simple mistake made in writing in a simple language, our neophyte must take on board explanations of advanced ideas (type class, kind, etc) that can only be understood once the simpler language has been mastered.