Assignment 8: Topics

Instructions:

  • Due date: Wednesday, Dec. 11
  • Upload your solutions to gradescope as assignment-8.rkt.
  • Ask questions on Piazza or during office hours.
  • Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code and solve your own exercises.
  • Starter code: here

Problem 1: Programming in a Probabilistic Programming Language [40 Points]

Consider the simple probabilistic programming language with observations that we saw in class, available here. In this exercise we will solve some probability problems by writing programs in this tiny programming language.

Problem 1a: Noisy Sensors

Suppose you live on Mars and you have three emergency sensors that each record the temperature of your home. The sensors have the following properties:

  • If it is too hot in your home, they output “Warning” with probability 90% and “OK” with probability 10%
  • If it is a normal temperature in your home, they output “OK” with probability 99% and “Warning” with probability 1%.

On any given day, there is a 0.01% chance that it is too hot; otherwise, it is normal temperature.

However, each sensor has a 0.001% chance of being broken! If it is broken, then it always outputs “Warning”.

Suppose you observe two of the three sensors outputting “Warning”. What is the probability that your home is too hot? Put your answer in problem1a in the solution file. You can feel free to use the provided parser, but your answer should be a probabilistic expression.

Problem 1b: Graph Reachability

A directed graph

The directed graph above gives an abstract view of a computer network. The goal in a network like this is to deliver a packet – piece of data – from one router to another by passing it through intermediate routers in the graph. Each node is a router, and each directed edge is a link from one router to another. Packets always begin at $A$.

In the real world there is often some uncertainty in the behavior of such a network. Assume that each link has a failure probability given by its annotation; for instance, the probability that a packet traversing the link $A \rightarrow C$ fails to be delivered is 0.2. Furthermore, assume that, when given multiple options, a router will choose uniformly at random which router to forward to; for instance, if the packet is at node $A$, then at the next step it will have a 50% chance of being at node $C$ and a 50% chance of being at node $B$. Use your probabilistic programming language implementation to answer the following questions about this network’s behavior:

  1. What is the probability that a packet successfully reaches $H$? Put your answer in problem1b-1.
  2. If packet reached $H$, what is the probability that the packet reached $C$? Put your answer in problem1b-2.

Fill in each of your programs into the definitions in the starter code. We will test your definitions by checking that, using your implementation, they run to the correct probabilities.

Problem 2: Making a Monad [50 Points]

In this exercise you’ll implement a monad for logging information as a function executes. A writer is a struct that has the following signature:

(struct writer (value log) #:transparent)

Value is any value and log is a list. Now, using monadic style, we can write a program that constructs a writer struct:

> (bind
  (tell "hi")
  (λ _           ; the _ denotes ignoring an argument
    (bind
     (tell "bye")
     (λ _ (pure 7))))))
(writer 7 '("hi" "bye"))

This program makes use of the following helper functions that you will define:

  • The pure function lifts a Racket value into the writer monad.
  • The bind function sequences two writer monad computations.
  • The tell function logs information to the writer monad.

This output has two pieces: first, the return value of the program – in this case, the value 7 – and second, log that is a list that contains the value that each tell is called with in the order that they are called.

Here is another example for a Fibonacci function that logs the value computed by each recursive call:

(define (fib n)
  (cond
    [(= n 0) (pure 0)]
    [(= n 1) (pure 1)]
    [else
     (bind
      (fib (- n 1))
      (λ (f1)
        (bind
         (tell f1)
         (λ _
           (bind
            (fib (- n 2))
            (λ (f2) (bind (tell f2) (λ _ (pure (+ f1 f2))))))))))]))

When we run the above program, we get the following output:

> (fib 6)
(writer 8 '(1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3))

Your job is to fill in the implementations of pure, bind, and tell to match the above behavior. Your solution should not use mutation.

Problem 3: Array Programming [10 Points]

In class we saw how Remora is used to lift computations over arrays. In this exercise, you will evaluate some Remora programs by hand. Be sure to look at the lecture notes for examples of how Remora works.

For example, the function add1 lifts adding 1 as follows:

> (define (add1 (n 0))
    (+ n 1))
> (add1 2)
3
> (add1 [1 2 3])
[2 3 4]
> (add1 [[1 2 3] [4 5 6]]))
[[2 3 4] [5 6 7]]

Definitions of the functions we used:

;;; Compute average value of the input vector
(define (mean (a 1))
  (define sum (reduce + 0 a))
  (define n (length a))
  (/ sum n))

;;; Compute the sum of the entire input array
(define (sum (a all))
  ;; flatten array a into a vector with all the elements
  (define elements (ravel a))
  (reduce + 0 elements))

;;; Add 1 to a given number
(define (add1 (n 0))
  (+ n 1))

;;; Subtract 1 from a given number
(define (sub1 (n 0))
  (- n 1))

Evaluate the following programs:

  1. (mean [1 2 3])
  2. (mean [[1 2 3 4] [5 6 7 8]])
  3. (sum [1 2 3])
  4. (sum [[1 2 3 4] [5 6 7 8]])
  5. ([add1 sub1] 5)
  6. (add1 [[[1 2 3] [4 5 6]] [[15 16 17] [24 26 28]]])

Enter your answers as strings in the solution.