Exercise 1 (Warm-up):

Write a probabilistic program representing the probability
distribution given by the following generalized density:

Λr. ∫dx(1/2·[0≤x]·[x≤1]+1/2·1/(√(2π)·e^(x^2)))·(1/2·δ(x)[r]+1/2·δ(x²)[r])


Exercise 2 (Properties):

In the lecture, you have seen the following definitions:

return : T → D[T]
return(x) = Λt. δ(x)[t]

map : (A → B) → (D[A] → D[B])
map(f)(d) = Λb. ∫da d[a]·δ(f(a))[b]

(;) : (A → D[B]) → (B → D[C]) → (A → D[C])
(f;g) = λa.Λc. ∫db f(a)[b]·g(b)[c]


Show the following identities (we quantify universally over free variables):

- map(λx. f(g(x)))(d) = map(f)(map(g)(d)).

- return(f(x)) = map(f)(return(x)).

- f;return = f
- return;f = f

- (f;g);h = f;(g;h).


Hint: The following identities may be useful:
- (λx. f(x))(v) = f(v)
- (Λx. f[x])[y] = f[y]
- ∫dx δ(v)[x]·f(x) = f(v). (Basic Dirac delta elimination).
- ∫dx f[x]·δ(x)[y] = f[y]. (Reverse Dirac delta elimination).
- ∫dx∫dy f[x,y] = ∫dy∫dx f[x,y]. (Fubini's theorem).
- λt.Λr. f(t)[r] = f


Exercise 3 (Dirac delta inversion):

Manually compute the distribution of the result of the following PSI
programs as a simplified symbolic expression representing a generalized
probability density (there should be no integral signs left in your solution):

def main(){
    x := uniform(0,1);
    y := uniform(0,1);
    return x+y;
}

def main(){
    x := uniform(0,1);
    y := uniform(0,1);
    return x*y;
}

def main(){
    x := if flip(1/2)
         then uniform(0,1)
         else 1/2;
    return x*(1-x);
}

def main(){
    x := uniform(0,1);
    y := (2+x)/(3+x);
    return y;
}


Exercise 4 (Conditioning):

Manually compute the distribution of the result of the following PSI
program as a symbolic expression representing a generalized
probability density (there should be no integral signs left in your solution):

def main(){
    p := uniform(0,1);
    x₁ := flip(p);
    x₂ := flip(p);
    observe(x₁ && !x₂);
    return p
}

Hints:
- ⟦observe(x)⟧ = λσ.Λσ'.[⟦x⟧(σ)≠0]·δ(σ)[σ']
- Remember to renormalize the final result.


Exercise 5 (Continuous conditioning):

Manually compute the expected result of the following PSI programs:

def main(){
    x := uniform(0,1);
    y := uniform(0,1);
    cobserve(x-y,0);
    assert(x == y);
    return x;
}

def main(){
    x := uniform(0,1);
    y := uniform(0,1);
    cobserve(x/y,1);
    assert(x == y);
    return x;
}

Intuitively, why is the result not the same for both programs? Add a
parameter ε>0 and rewrite the programs using a standard "observe"
statement (but without the assertions), such that you recover the
above programs in the limit ε→0.