The Term Graph Programming System HOPS

Wolfram Kahl

pp. 136-149 in Rudolf Berghammer, Yassine Lakhnech (eds.) Tool Support for System Specification, Development and Verification, Advances in Computing Science, Springer-Verlag Vienna, ISBN 3-211-83282-3, March 1999.

(.bib, .ps.gz, .pdf)

Introduction

Programmers of Haskell or ML know that once their programs are syntactically correct and get past the type checker, the probability that they are correct is usually already pretty high. But while the parser or the type checker still complain, it is not always easy to spot the real problem, which may be far from the trouble spot indicated by the often cryptic error message.

Syntax-directed editing can solve the problem with syntax errors. But, even if a syntax-directed editor would be extended with online typing, another problem would be how to present the typing information to the user; huge type expressions with unclear relation to the program expression may perhaps be of only very little help.

We present a system that deals with both problems by making the program structure and the program's typing structure explicit and interactively accessible in the shape of term graphs. The design of this system relies on recent advances in the theories of untyped and typed second-order term graphs.

The Higher Object Programming System HOPS, which has been developed by a group led by Gunther Schmidt since the mid-eighties, is a graphically interactive term graph programming system designed for transformational program development.

In HOPS, only syntactically correct and well-typed programs can be constructed. The choice of the language is only constrained by certain restrictions of the term graph formalism and of the typing system. An important ingredient of HOPS is the transformation support; this favours referentially transparent languages -- for this reason most of our examples use a language close to typed λ-calculi and Haskell. HOPS is intended as:

Research tool:

New languages can easily be constructed and experimented with via the transformation mechanism.

Programming tool:

HOPS may be used as a ``better Haskell editor'', integrating syntax directed editing with strong online typing. The editing safety more than weighs up the time required to get used to the term graph view.

Visualisation and debugging tool:

Automatic evaluation sequences help to illustrate the workings of, for example, purely functional programs with lazy evaluation -- in the absence of accessible Haskell debuggers or tracers this is especially useful.

Education tool:

A hands-on experience of term graphs, syntactic structure, typing, graph reduction, general second-order rule application and reduction strategies can be gained easily through the use of HOPS.

The current version (available via WWW) features several significant improvements over earlier prototypes:

• The theory behind the term graph transformations is now well-understood,
• typing has been integrated into the term graphs both theoretically and in the implementation,
• HOPS is now an essentially language-independent framework, and
• literate programming ideas are more adequately integrated.

Also refer to the HOPS home page.