ISR 2024 – Track C
About Randomized Programming and Rewriting
Lecturer
Ugo Dal Lago University of Bologna
Course Description
Rewriting can be seen as an abstraction of the computational process in which the underlying configuration evolves through the process of substitution of expressions by expressions. As such, rewriting allows you to capture the fundamental concepts of program and algorithm. The latter, however, does not always enjoy a crucial property usually taken for granted, namely that of being deterministic. Indeed, many modern algorithms essentially rely on the availability of true randomness. How could one nicely express randomized algorithms? Would it be possible to capture this new computing paradigm in rewriting? What impact does all this have on the underlying theory? This course aims to provide an introduction to randomized computation, programming and rewriting, while answering the questions above.
Literature
-
Martin Avanzini, Ugo Dal Lago, Akihisa Yamada,
On Probabilistic Term Rewriting, Science of Computer Programming 185,
2020, doi: 10.1016/j.scico.2019.102338
PDF -
Ugo Dal Lago,
On Probabilistic λ-Calculi, In: Gilles Barthe,
Joost-Pieter Katoen, Alexandra Silva (eds.), Foundations of
Probabilistic Programming, Cambridge University Press
pp. 121 – 144, 2020, doi: 10.1017/9781108770750.005
PDF -
Ugo Dal Lago, Claudia Faggian, Simona Ronchi Della Rocca,
Intersection Types and (Positive) Almost-Sure Termination, Proc.
ACM on Programming Languages 5 (POPL), 32, pp. 1 – 32, 2021,
doi: 10.1145/343431
PDF -
Ugo Dal Lago, Charles Grellois,
Probabilistic Termination by Monadic Affine Sized Typing,
ACM Transactions on Programming Languages and Systems,
41(2), pp. 1 – 65, 2019, doi: 10.1145/3293605
PDF
Course Link
link