Participation in at least one master's seminar in the TCS group is mandatory for all master's theses.

Formal Verification of the Amortised Analysis of Lazy Skew Heaps

Lazy skew heaps are a purely functional priority queue data structure introduced by Chris Okasaki in The Fun of Programming [5]. In a persistent setting, the standard amortised analysis of ephemeral data structures no longer applies directly, since expensive operations may be shared across multiple versions of a data structure [8]. Okasaki addresses this challenge by exploiting lazy evaluation and presents an informal potential-based proof establishing logarithmic amortised complexity for the core heap operations of lazy skew heaps. While machine-checked amortised analyses exist for classical (non-lazy) skew heaps, notably in the work of Nipkow and Brinkop [6], the corresponding analysis for the lazy variant has not been formalised.

The proposed project aims to develop a machine-checked formalisation of Okasaki's amortised analysis of lazy skew heaps. The project can build upon existing approaches to the verification of amortised complexity for lazy functional programs [1–4]. In particular, recent work based on bidirectional demand semantics has successfully been applied to the verification of Okasaki's amortised queues using the reverse physicist's method. This project will investigate whether the same approach can be extended to a more sophisticated data structure such as lazy skew heaps and whether it provides a suitable foundation for formalising more intricate amortised analyses.

A second objective is to extend the formalisation to the refined amortised bounds established by Schoenmakers for top-down skew heaps and to determine whether these tighter bounds also apply to the lazy variant. Furthermore, the developed approach can be evaluated on other complex lazy data structures, providing insight into its applicability beyond the case of lazy skew heaps.

References

(1) Nils Anders Danielsson. "Lightweight semiformal time complexity analysis for purely functional data structures". In: ACM SIGPLAN Notices 43.1 (2008), pp. 133–144.

(2) Martin AT Handley, Niki Vazou, and Graham Hutton. "Liquidate your assets: reasoning about resource usage in liquid haskell". In: Proceedings of the ACM on Programming Languages 4.POPL (2019), pp. 1–27.

(3) Glen Mével, Jacques-Henri Jourdan, and François Pottier. "Time credits and time receipts in Iris". In: Programming Languages and Systems: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings 28. Springer, 2019, pp. 3–29.

(4) Xia, Li-yao, et al. Story of Your Lazy Function's Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy Programs. Proceedings of the ACM on Programming Languages 8.ICFP (2024): 30–63.

(5) Okasaki, C. (1995). Fun with Binary Heap Trees. In J. Gibbons & O. de Moor (Eds.), The Fun of Programming Languages. Section 1.7: "Analysis of Lazy Skew Heaps".

(6) Nipkow, T., & Brinkop, H. (2019). Amortized Complexity Verified. Journal of Automated Reasoning, 62, 367–391.

(7) Schoenmakers, L. (1997). A Tight Lower Bound for Top-Down Skew Heaps. Information Processing Letters, 61(5), 279–284.

(8) Okasaki, Chris. Purely functional data structures. Cambridge University Press, 1998.

Supervisor

Georg Moser, Armin Walch

Prerequisites

Interactive Theorem Proving (e.g. VU Logic and Learning B: Interactive Theorem Proving in Isabelle/HOL)

Probabilistic Term Rewriting

In recent years interest and techniques in resource analysis of probabilistic programs have significantly increased. In the project, we study a recent approach for the automated complexity analysis of probablisitic term rewrite systems (PTRS) due to Avanzini et al., with the goal of implementing the methods in TcT. A further goal is the (potential) improvement of the theory and methods.

  • On Probabilistic Term Rewriting
    Martin Avanzini, Ugo Dal Lago, Akihisa Yamada
    Proc. 14th International Symposium on Functional and Logic Programming, LNCS 10818, pp. 132–148, 2018
  • TcT: Tyrolean Complexity Tool
    Martin Avanzini, Georg Moser, Michael Schaper
    Proc. 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, LNCS 9636, pp. 407–423, 2016
Supervisor

Georg Moser

Prerequisites

term rewriting

Complexity Analysis of Lazy Programs

In contrast to the wealth of literature on the (automated) resource analysis of strict language, like OCaml, the resource analysis of non-strict languages, like Haskell, has received scarce attention. One notable exception is Okasaki, who adapted the banker's method of amortised cost analysis to the debit method, in order to correctly analyse the amortised costs of lazy data structures. In this master thesis project, we aim to study and formalse his approach. In particular we aim to adapt recent work on the fully automated amortised analysis of self-adjusting data structures such as splay trees, splay heaps, pairing heaps to lazy evaluation. The first goal is a rigorous formalisation of the Okasaki's debit method for the amortised analysis of non-strict functional programs, second the implementation of this formal methodology is envisioned as well as the application of this prototype implementation to popular lazy data structures, like lazy skew heaps. A possible further target could be lazy pairing heaps.

Supervisor

Georg Moser

Prerequisites

Program and Resource Analysis

Multivariate Amortised Resource Analysis

In recent work in resource analysis the amortised analysis has received substantial interest. In this master project, we'll investigate the various approaches and in particular implement recent results on multivariate amortised analysis of term rewrite systems. Among others this will involve the automatic synthesis of tree automata, which are employed to define the potential of values over arbitrary user-defined datatypes.

Supervisor

Georg Moser

Prerequisites

Program and Resource Analysis

No entries.

Automated Amortized Multi-Potential Analysis

ATLAS (Automated Amortised Complexity Analysis of Self-Adjusting Data Structures) provides a fully automated expected amortised cost analysis of self-adjusting data structures, that is, of randomised splay trees, randomised splay heaps, randomised meldable heaps and other sophisticated data structures (not necessarily randomised), which so far have only (semi-)manually been analysed in the literature. The current prototype is implemetned in Java and should be ported to Haskell. If possible, this re-implementation should also extend the class of resource functions considered.

Student

Armin Walch

Supervisor

Georg Moser

Prerequisites

Program and Resource Analysis

Real Root Counting and Derivational Complexity of Term Rewrite Systems

We can induce polynomial upper bounds on the derivational complexity of a term rewrite system if we find a compatible matrix interpretation whose maximum matrix has spectral radius at most one. Starting from root counting algorithms of the mathematical literature, we investigate the performance of several constraints which ensure this condition is met.

Student

Philipp Wirtenberger

Supervisor

Georg Moser

Nach oben scrollen