Crate synox

Program synthesis of string transformations from input-output examples.

This crate implements program synthesis of string transformations from input-output examples. Perhaps the most well-known use of string program synthesis in end-user programs is the Flash Fill feature in Excel. These string transformations are learned from input-output examples. In some cases, extra unpaired input examples can be used to improve results even when the outputs corresponding to those examples are not available.

String programs take a row of columns (strings) and produce a single string as an output. For example, a string program can capture the transformation demonstrated in the following table:

Name	Graduation Year	Output
Alyssa P. Hacker	1985	A. Hacker ’85
Ben Bitdiddle	2002	B. Bitdiddle ’02
Cy D. Fect	2017	?

The following example shows how to use the blinkfill module to learn a program that learns the above transformation and apply it to an example with unknown output (the last row in the table).

use synox::StringProgram;
use synox::blinkfill;

// no unpaired examples
let unpaired: &[Vec<&str>] = &[];
// two paired examples, demonstrating a diversity of inputs (one including a middle initial)
let examples = &[(vec!["Alyssa P. Hacker", "1985"], "A. Hacker '85"   ),
                 (vec!["Ben Bitdiddle",    "2002"], "B. Bitdiddle '02")];

// learn a program based on input-output examples
//
// blinkfill::learn returns an Option because it may fail to learn a program that matches all
// the examples
let prog = blinkfill::learn(unpaired, examples)?;

// StringProgram::run returns an Option because the program may fail on a particular input
let result = prog.run(&["Cy D. Fect", "2017"])?;
assert_eq!(result, "C. Fect '17");

To handle multiple output columns, you can infer separate string programs, one for each output column.

Modules

blinkfill

Implements the BlinkFill algorithm for learning syntactic string transformations.

Traits

StringProgram

A program that transforms a list of strings into a string.