Current issues in programming language implementation

Adrian Johnstone

Programming language research underpins almost every aspect of computing, since all applications of computing rely on the specification of behaviour in some more-or-less convenient notation. Until now, mainstream language design has emphasised the use of notations that can be efficiently translated into efficient machine representations and behaviours. This focus is shifting.

Gordon Moore noted that ever since commercial machines first appeared in the 1950's, processor performance has been doubling roughly every 18 months. Todd Proebstring has suggested that improvements to programming language translators yield a doubling of performance only every 18 years. If this is true, then the current emphasis in compiler research on ever more esoteric code improvement algorithms is a wasted effort. Proebstring's view is that programming languages will evolve towards highly expressive notations with little emphasis on implementation constraints.

In this talk I shall describe some of our work which is aimed at delivering enabling technologies for these kinds of future language designs. I shall describe the tangled history of generalised context free parsing theory and outline two of our approaches, including what we believe is the fastest currently known general context free parsing algorithm. I shall also describe approaches to brute force exact dataflow analysis, and its application to the reverse compilation of machine level programs for a Digital Signal Processor with rather eccentric features. Finally, I shall give an outline of a future compiler/hardware synthesizer in which the processor instruction set is a fluid interface between the 'soft' and 'hard' parts of the system, specified on an application-by-application basis by the compiler.