By the same authors

The Space Usage Problem: An Evaluation Kit for Graph-Reduction Semantics

Research output: Contribution to conferencePaper



Publication details

DatePublished - 2000
Original languageUndefined/Unknown


We describe a software tool for specifying operational semantics as a term-graph reduction system. The semantics are guaranteed to model the asymptotic space and time usage of an implementation accurately yet are abstract enough to support reasoning at the program level. Term graphs make all the aspects of reduction relating to space usage explicit as they naturally encode size and address information. The semantics are constrained to be small-step, deterministic rules and each rewrite step uses bounded resources. The result is a system suitable for describing and analysing the space behaviour of functional programming languages.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations