Program Synthesis

Tikhon Jelvis (tikhon@jelv.is)

Press key to advance.
Zoom in/out: Ctrl or Command + +/-

1 Program Synthesis

  • Generate program to specification
  • Search through programs:
    • randomized search (MCMC)
    • constraint solving (SMT)

2 GreenArrays

  • Very low-power
  • stack-based: colorForth
    • 32 instructions
    • 18-bit words
    • very difficult

3 Superoptimization

  • spec: valid program
  • generate faster program

4 Existing

  • emulator for single core
  • MCMC synthesizer
  • two solvers: z3 and SKETCH