[ The Types Forum (announcements only),
http://lists.seas.upenn.edu/mailman/listinfo/types-announce ]
Dear colleagues,
The next talk of the Semantic and Formal Approaches to Complexity (SCOT)
webinar will be given by Martin Avanzini. Abstract and practical informations
are given below. You are welcome to attend it on Zoom. To obtain the connexion
informations and/or be informed of future talks, please subscribe to the
mailing list (for that send an email with subject "subscribe scot_webinar" and
empty body to [email protected]).
Tuesday November 9th 2021, 3pm-4pm (CET). Martin Avanzini (Inria
Sophia-Antipolis).
Title: On Continuation-Passing Transformations and Expected Cost Analysis
- the room will open at 2:45pm (CET). You can come with your coffee for a chat!
- the talk will start at 3:00 pm.
Abstract:
In this talk I will present recent joint work with Ugo Dal Lago and Gilles
Barthe, which is concerned with a novel methodology for the cost analysis of
randomized higher-order programs, i.e., programs which can sample values from
chosen distributions during execution, and at the same time are capable of
treating functions as first-class citizens. The evaluation of such a program
results in a distribution of values, and has an expected cost, namely the
average cost the program experiences along its execution.
The way we tackle such an expected cost analysis is reminiscent of the seminal
work of Rosendahl (1989), and lies in turning the program at hand into a second
one, which is structurally quite similar but computes the cost of execution in
addition. This turns an intensional property, namely the cost of execution,
into an extensional one. A crucial aspect of this program transformation is
that probabilistic effects are eliminated along the way, thereby enabling
classical reasoning tools for non-probabilistic programs in our context. As one
such tool we propose a slight variation of a standard higher-order logic,
dubbed EHOL, which we also use to study some classical examples from
probability theory.
For the seminar:
Isabel Oitavem, Patrick Baillot, Ugo Dal Lago
------------------------
Seminar web page:
https://urldefense.com/v3/__http://www.cs.unibo.it/*dallago/SCOSEM/__;fg!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePztdSF0wyQ$
The list's homepage:
https://urldefense.com/v3/__https://groupes.renater.fr/sympa/info/scot_webinar__;!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePzuEyIZDzQ$
General information about mailing lists:
https://urldefense.com/v3/__https://groupes.renater.fr/sympa/help/introduction__;!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePzuhkLhmtA$
To unsubscribe from this list: send an email with subject "unsubscribe
scot_webinar" and empty body to [email protected]
If you wish to subscribe: same procedure with subject "subscribe scot_webinar"
