Peter Schachte

Lazy evaluation offers great flexibility by computing only what is necessary. However, analysing the cost of lazy programs is notoriously challenging, as computation occurs out of order and depends on future demands. Recent work has proposed alternative semantics for modelling lazy evaluation cost that avoid reasoning about program states. However, existing approaches either rely on nondeterminism or require complex bidirectional semantics. We present the Memorist Semantics , a novel semantics for analysing the cost of lazy programs by explicitly tracking the cost and dependencies of every subterm. Our semantics annotates components of a term with fine-grained cost and usage information, yielding a deterministic semantics that can be expressed through a simple monadic interface. We formalize the semantics in Rocq and verify its soundness with respect to the existing Clairvoyance Semantics. Similar to prior formalized semantics, our semantics is defined for a total, typed language with built-in structural recursion and without support for first-class functions. We outline ideas for possible extensions.

We propose a set of design principles to guide the design of a programming language intended for general, practical use. These principles center around supporting the development of robust programs, supporting independent development, the evolution of separate components of an application, and developing programs with adequate performance. We identify one key principle, interface integrity, as the most important characteristic of declarative programming languages. Following these principles has led to the development of the Wybe programming language, which provides a range of features common in functional, procedural, and logic programming languages. In particular, we argue that it provides much of the benefit of declarative programming languages, while providing much of the flexibility of imperative programming.

We propose a set of design principles to guide the design of a programming language intended for general, practical use. These principles centre around supporting development of robust programs, supporting independent development and evolution of separate components of an application, and developing programs with adequate performance. We identify one key principle, interface integrity, as the most important characteristic of declarative programming languages. Following these principles has led to the development of the Wybe programming language, which provides a range of features common in functional, procedural, and logic programming languages. In particular, we argue that it provides much of the benefit of declarative programming languages, while providing much of the flexibility of imperative programming.

Precondition inference is a non-trivial problem with important applications in program analysis and verification. We present a novel iterative method for automatically deriving preconditions for the safety and unsafety of programs. Each iteration maintains over-approximations of the set of safe and unsafe initial states, which are used to partition the program’s initial states into those known to be safe, known to be unsafe and unknown. We then construct revised programs with those unknown initial states and iterate the procedure until the approximations are disjoint or some termination criteria are met. An experimental evaluation of the method on a set of software verification benchmarks shows that it can infer precise preconditions (sometimes optimal) that are not possible using previous methods.

Zones and Octagons are popular abstract domains for static program analysis. They enable the automated discovery of simple numerical relations that hold between pairs of program variables. Both domains are well understood mathematically but the detailed implementation of static analyses based on these domains poses many interesting algorithmic challenges. In this article, we study the two abstract domains, their implementation and use. Utilizing improved data structures and algorithms for the manipulation of graphs that represent difference-bound constraints, we present fast implementations of both abstract domains, built around a common infrastructure. We compare the performance of these implementations against alternative approaches offering the same precision. We quantify the differences in performance by measuring their speed and precision on standard benchmarks. We also assess, in the context of software verification, the extent to which the improved precision translates to better verification outcomes. Experiments demonstrate that our new implementations improve the state of the art for both Zones and Octagons significantly.