Edit page

This program induces a deterministic arithmetic function from input-output examples.

(define (random-arithmetic-fn)
  (if (flip 0.3)
      (random-combination (random-arithmetic-fn) 
                          (random-arithmetic-fn))
      (if (flip) 
          (lambda (x) x) 
          (random-constant-fn))))

(define (random-combination f g)
  (define op (uniform-draw (list + -)))
  (lambda (x) (op (f x) (g x))))

(define (random-constant-fn)
  (define i (sample-integer 10))
  (lambda (x) i))

(define (sample)
  (rejection-query
   (define my-proc (random-arithmetic-fn))
   (my-proc 2)
   (and (= (my-proc 0) 2)
        (= (my-proc 1) 3))))

(sample)

To induce stochastic functions, it can be useful to condition on the evidence – our input-output examples – having high marginal likelihood under the induced function:

(define (random-arithmetic-fn)
  (if (flip 0.3)
      (random-combination (random-arithmetic-fn) 
                          (random-arithmetic-fn))
      (if (flip) 
          (lambda (x) x) 
          (random-constant-fn))))

(define (random-combination f g)
  (if (flip 0.5)
    ((lambda (op) (lambda (x) (op (f x) (g x))))
      (uniform-draw (list + -)))
    (lambda (x) (sample-integer 10))))

(define (random-constant-fn)
  (define i (sample-integer 10))
  (lambda (x) i))

(define (find-prob x xs ps)
  (if (null? xs)
      0.0
      (if (equal? (first xs) x)
          (first ps)
          (find-prob x (rest xs) (rest ps)))))

(define (likelihood fn x)
  (let ([dist (enumeration-query (define _ 1) (fn) #t)])
    (find-prob x (first dist) (second dist))))

(define (sample)
  (rejection-query
   (define my-proc (random-arithmetic-fn))
   (define (my-proc-likelihood x y)
     (likelihood (lambda () (my-proc x)) y))
   (my-proc 2)
   (and (flip (my-proc-likelihood 0 2)) 
        (flip (my-proc-likelihood 1 3)))))

(hist (repeat 100 sample))

This is semantically equivalent to conditioning on input-output examples directly, but can improve convergence rates when MCMC is used in the outer query.

References: