Back to search

University of Waterloo

TreeGen: a monotonically impure functional language

Abstract

dc:description.abstract

We present TreeGen, an impure functional language designed to express, consume, and validate JSON-like documents, as well as generate text files. The language aims to provide a more reliable and flexible way to create customised Interface Definition Languages, since the current state of the art is implemented via monolithic, ad-hoc codebases, which cannot easily be modified. TreeGen's principal contribution, aside from being tailored to the domain of manipulating documents and generating text, is the concept of monotonic mutability: despite being an impure scripting language, its execution remains deterministic under arbitrary reordering of operations, making it robust to many common classes of programmer error possible in languages that allow unchecked mutability. We prove this by basing TreeGen's unordered constraint-based formal semantics on a partially-ordered model of TreeGen's heap, then showing that the execution of any TreeGen expression's constraint set is deterministic under chaotic iteration. We also give notes on our experience implementing the language. These notes include a model for execution tracing and error reporting, necessary data structures to practically implement the formal semantics, related performance issues, and comments on potential mitigations of those performance issues.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hackett, Alistair Finn
Advisor dc:contributor.advisor
  • Lhoták, Ondřej

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/16133

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hackett, Alistair Finn. TreeGen: a monotonically impure functional language. University of Waterloo, 2020. http://hdl.handle.net/10012/16133