JOHN: Jumble of Heuristic Notions

Abstract

We introduce an educational programming language with a syntax similar to a natural language. It is built around a theoretical programming model where the default mode of computation is declarative and non-deterministic, as opposed to imperative and highly optimized. Users can then specify declarative optimizations and heuristics that may essentially make the program imperative, without sacrificing compactness or clarity. We have written several applications in the language including a chess program and a register allocation component for an industry-level compiler. While these programs tend to be inefficient compared to highly optimized implementations, they are much more compact, easily understandable, and extensible. We believe this programming environment is suited for education of programming, and represents a model that may eventually become practical as multi-core hardware becomes mainstream.

2008