PartI Higher-OrderProbabilisticProgramming

Ugo Dal Lago

(Based on joint work with Flavien Breuvart, Raphaëlle Crubillé, Charles Grellois, Davide Sangiorgi,. . . )

POPL 2019, Lisbon, January 14th

Probabilistic Models

I The environment is supposed not to behave deterministically, but probabilistically.

q

q

q

q

14

34 1

12 12 13 23

I Abstractions:

I (Labelled) Markov Chains.

Probabilistic Models

I The environment is supposed not to behave deterministically, but probabilistically.

I Crucial when modeling uncertainty.

q

q

q

q

34 1

12 12 13 23

I Abstractions:

I (Labelled) Markov Chains.

Probabilistic Models

I The environment is supposed not to behave deterministically, but probabilistically.

I Crucial when modeling uncertainty.

I Useful to handle complex domains.

q

q

34 1

12 12 13 3

I Abstractions:

I (Labelled) Markov Chains.

Probabilistic Models

I The environment is supposed not to behave deterministically, but probabilistically.

I Crucial when modeling uncertainty.

I Useful to handle complex domains.

I Example:

q

q

q

q

14

34 1

12 12 13 23

probabilistically.

I Crucial when modeling uncertainty.

I Useful to handle complex domains.

I Example:

q

q

q

q

14

34 1

12 12 13 23

I Abstractions:

I (Labelled) Markov Chains.

R OBOTICS

AR TIFICIAL INTELLIGENCE

NA TURAL LANGUA GE PR OCESSING

Randomized Computation

I Algorithms and automata are assumed to have the ability to sample from a distribution [dLMSS1956,R1963].

I Abstractions:

I Randomized algorithms;

I Probabilistic Turing machines.

I Labelled Markov chains.

Randomized Computation

I Algorithms and automata are assumed to have the ability to sample from a distribution [dLMSS1956,R1963].

I This is a powerful tool when solving computational problems.

I Abstractions:

I Randomized algorithms;

I Probabilistic Turing machines.

I Labelled Markov chains.

Randomized Computation

I Algorithms and automata are assumed to have the ability to sample from a distribution [dLMSS1956,R1963].

I This is a powerful tool when solving computational problems.

I Example:

Randomized Computation

I Algorithms and automata are assumed to have the ability to sample from a distribution [dLMSS1956,R1963].

I This is a powerful tool when solving computational problems.

I Example:

distribution [dLMSS1956,R1963].

I This is a powerful tool when solving computational problems.

I Example:

I Abstractions:

I Randomized algorithms;

I Probabilistic Turing machines.

I Labelled Markov chains.

0

1 1 1 0

s

· · · δ(s, 0) ={(q, 1, ←)¹², (r, 0,→)²³} 0

1 1 1 0

r

· · · ·

1

1 1 1 0

q

· · · ·

1 2

1 2

0

1 1 1 0

s

· · · δ(s, 0) ={(q, 1, ←)¹², (r, 0,→)²³} 0

1 1 1 0

r

· · · ·

1

1 1 1 0

q

· · · ·

1 2

1 2

0

1 1 1 0

s

· · · δ(s, 0) ={(q, 1, ←)¹², (r, 0,→)²³} 0

1 1 1 0

r

· · · ·

1

1 1 1 0

q

· · · ·

2 3

1 3

ALGORITHMICS

CR YPTOGRAPHY

PR OGRAM VERIFICA TION

What Algorithms Compute

I Deterministic Computation

I For every inputx, there is at most one output y any algorithmA produces when fed withx.

I As a consequence:

A ; JAK : N * N.

A ; JAK : N → D (N).

I The distributionJAK(n) sums to anything between 0 and 1, thus accounting for the probability of divergence.

For every inputx, there is at most one output y any algorithmA produces when fed withx.

I As a consequence:

A ; JAK : N * N.

I Randomized Computation

I For every inputx, any algorithmA outputs y with a probability 0 ≤ p ≤ 1.

I As a consequence:

A ; JAK : N → D (N).

I The distributionJAK(n) sums to anything between 0 and 1, thus accounting for the probability of divergence.

Higher-Order Computation

I Mainly useful in programming.

I Modularity;

I Code reuse;

I Conciseness.

I Example:

I Models:

I λ-calculus

Higher-Order Computation

I Mainly useful in programming.

I Functions are first-class citizens:

I They can be passed as arguments;

I They can be obtained as results.

I Example:

I Models:

I λ-calculus

Higher-Order Computation

I Mainly useful in programming.

I Functions are first-class citizens:

I They can be passed as arguments;

I They can be obtained as results.

I Motivations:

I Modularity;

I Code reuse;

I Conciseness.

I Models:

I λ-calculus

Higher-Order Computation

I Mainly useful in programming.

I Functions are first-class citizens:

I They can be passed as arguments;

I They can be obtained as results.

I Motivations:

I Modularity;

I Code reuse;

I Conciseness.

I Example:

Higher-Order Computation

I Mainly useful in programming.

I Functions are first-class citizens:

I They can be passed as arguments;

I They can be obtained as results.

I Motivations:

I Modularity;

I Code reuse;

I Conciseness.

I Example:

I Functions are first-class citizens:

I They can be passed as arguments;

I They can be obtained as results.

I Motivations:

I Modularity;

I Code reuse;

I Conciseness.

I Example:

I Models:

I λ-calculus

FUNCTIONAL PR

OGRAMMING

FUNCTIONAL D A T A STR UCTURES

λ -CALCULUS

Higher-Order Probabilistic Computation?

Does it Make Sense?

Interesting Research Problems?

Higher-Order Probabilistic Computation?

Does it Make Sense?

What Kind of Metatheory

Does it Have?

Does it Make Sense?

What Kind of Metatheory Does it Have?

Interesting Research Problems?

This Tutorial

1. Motivating Examples.

2. A λ-Calculus Foundation.

3. Operational and Denotational Semantics.

4. Termination and Resource Analysis.

2. A λ-Calculus Foundation.

3. Operational and Denotational Semantics.

4. Termination and Resource Analysis.

A webpage: http://www.cs.unibo.it/~dallago/HOPP/

merge sort

merge sort

merge sort

quick sort

quick sort

quick sort

0 1 2 · · · n

p 1 − p

The Coupon Collector

I A brand distributes a large quantity of coupons, each labelled with i∈ {1, . . . , n}.

I Example: if n = 5, you could get the following coupons: 3, 1, 5, 2, 3, 1, 5, 2, 3, 1, 5, 2, . . .

I Are you guaranteed to win the prize with probability1? After how many days, on the average?

The Coupon Collector

I A brand distributes a large quantity of coupons, each labelled with i∈ {1, . . . , n}.

I Every day, you collect one coupon at a local store. Any label i has probability

1

n to occur.

3, 1, 5, 2, 3, 1, 5, 2, 3, 1, 5, 2, . . .

I Are you guaranteed to win the prize with probability1? After how many days, on the average?

The Coupon Collector

I A brand distributes a large quantity of coupons, each labelled with i∈ {1, . . . , n}.

I Every day, you collect one coupon at a local store. Any label i has probability

1

n to occur.

I You win a prize when you collect a set of n coupons, each with a distinct label.

I Are you guaranteed to win the prize with probability1? After how many days, on the average?

The Coupon Collector

I A brand distributes a large quantity of coupons, each labelled with i∈ {1, . . . , n}.

I Every day, you collect one coupon at a local store. Any label i has probability

1

n to occur.

I You win a prize when you collect a set of n coupons, each with a distinct label.

I Example: if n = 5, you could get the following coupons:

3, 1, 5, 2, 3, 1, 5, 2, 3, 1, 5, 2, . . .

i∈ {1, . . . , n}.

I Every day, you collect one coupon at a local store. Any label i has probability

1

n to occur.

I You win a prize when you collect a set of n coupons, each with a distinct label.

I Example: if n = 5, you could get the following coupons:

3, 1, 5, 2, 3, 1, 5, 2, 3, 1, 5, 2, . . .

I Are you guaranteed to win the prize with probability1? After how many days, on the average?

Beyond Randomized Algorithms: The Grass Problem

I You get up in the morning, and notice that the grass in your garden is wet.

I If it rains, there is90% probability that the grass is wet the following morning.

I If the sprinkler is activated, there is80% probability that the grass is wet the following morning.

I In any other case, there is anyway a10% probability that the grass is wet.

I In other words, you are in a situation like the following: rain

sprinkler

grass is wet

I Now: how likely it is that it rained?

Beyond Randomized Algorithms: The Grass Problem

I You get up in the morning, and notice that the grass in your garden is wet.

I You know that there is30% probability that it rains during the night.

80% probability that the grass is wet the following morning.

I In any other case, there is anyway a10% probability that the grass is wet.

I In other words, you are in a situation like the following: rain

sprinkler

grass is wet

I Now: how likely it is that it rained?

Beyond Randomized Algorithms: The Grass Problem

I You get up in the morning, and notice that the grass in your garden is wet.

I You know that there is30% probability that it rains during the night.

I The sprinkler is activated once every two days.

I In any other case, there is anyway a10% probability that the grass is wet.

I In other words, you are in a situation like the following: rain

sprinkler

grass is wet

I Now: how likely it is that it rained?

Beyond Randomized Algorithms: The Grass Problem

I You get up in the morning, and notice that the grass in your garden is wet.

I You know that there is30% probability that it rains during the night.

I The sprinkler is activated once every two days.

I You further know that:

I If it rains, there is90% probability that the grass is wet the following morning.

I If the sprinkler is activated, there is80% probability that the grass is wet the following morning.

I In any other case, there is anyway a10% probability that the grass is wet.

I In other words, you are in a situation like the following:

rain sprinkler

grass is wet

I You know that there is30% probability that it rains during the night.

I The sprinkler is activated once every two days.

I You further know that:

I If it rains, there is90% probability that the grass is wet the following morning.

I If the sprinkler is activated, there is80% probability that the grass is wet the following morning.

I In any other case, there is anyway a10% probability that the grass is wet.

I In other words, you are in a situation like the following:

rain sprinkler

grass is wet

I Now: how likely it is that it rained?

Questions?