We will use a PCFG and conditional reasoning to infer a program given examples of its input-output behavior. In our generative model, we use a PCFG to sample the source code of candidate programs. The probability of sampling a program gives a measure of its complexity – roughly speaking, more likely programs are less complex. We then use factor to weight programs according to how well they explain a training set of input-output pairs. We will end up preferring programs that have the best balance of complexity and explanatory power.

var myEval = function(str) {
  return window.eval("(function(s, k, a, x) {  k(s, " + str + ") })");
}

var w = function(string) {
  return string.split(/ +/);
}

var grammar = {
  "S":   map(w, ["x OP S", "S OP x", "N"]),
  "OP":  map(w, ["+","-","*"]),
  "N":   map(w,["1","2","3","4","5","6","7"])
};

var terminals = w("x + - * 1 2 3 4 5 6 7");

var isTerminal = function(x) {
  return _.contains(terminals, x);
}

var unfold = function(symbol) {
  if (isTerminal(symbol)) {
    return symbol
  }
  
  var rules = grammar[symbol];
  var sampledRule = rules[ randomInteger(rules.length) ];
  
  // convert sampled rule to a string
  var str = map(unfold, sampledRule).join(" ");
  
  // parenthesize the sampled rule if it's more than a single symbol
  return sampledRule.length > 1 ? "(" + str + ")" : str
}

var need = function(bool) { 
  factor(bool ? 0 : -Infinity)
}

print(Enumerate(function() {
  var str = unfold("S");
  
  var f = myEval(str);
  
  need( f(1) == 3 );
  
  // prevent f from being a constant
  // need( f(2) != f(1) );
  
  // eliminate increasing functions 
  // need( f(2) < f(1) )
  
  // require that f is kinda complicated
  // need( str.length > 10 )
  
  return str
  
}, 300));

Observe (marvel at?) how we can condition on abstract properties of the programs. While we can certainly impose concrete requirements (e.g., f(1) = 3), there is also much to be gained by imposing relational requirements (e.g., f(2) < f(1)).