PERFECT v0.1

PERFECT is a formal artificial intelligence which can let you tweak the output of a program, and modify either the program of its input data. This is the core project, meaning it cannot be used as such. One need to provide a programmation language and an interpreter. A bit more work is needed to use PERFECT, but once you're done, it will be perfectly working.

The core project will be available both for the JVM and for Javascript through Scala-JS.

Potential Applications

Examples of utilisation would include.

• Create a page in PHP, add creation logics, modify directly the output HTML and PERFECT will manage the PHP to reflect these changes.
• Create React templates in JSX or javascript, modify them on your browser and PERFECT will update the javascript.
• Create a Powerpoint, do some advanced stuff in the code that creates the powerpoint, go back to powerpoint mode in a breeze.

Meaning

Perfect stands for something like "Programming by Example, Repair oF Existing Coded Templates"

Features

PERFECT can currently reverse-engineer the following programming fragments:

• Anonymous functions (lambda) and function applications.
• Immutable variables
• String concatenation
• Conditional expressions
• List operations: concatenation, map, filter, flatmap, mkString
• Recursive operations (fixpoint operator)
• Immutable objects (Algebraic Data Types, or ADT).

As for use in an editor, instead of providing a raw output, PERFECT supports also composable editing operations on the output data.

• String insertion/modification/deletion
• List insertion/modification/deletion
• Tree wrapping/unwrapping/modification
• Tree/String matching/replacing (e.g. Clone-and-Paste)

Tutorial in 150 Lines of Code

In this tutorial, we are going to create a small language consisting of strings, assignments and concatenation, and we are going to demonstrate the potential of PERFECT.

First, checkout PERFECT and compile it locally, then use sbt publish-local to have it available from sbt.

In an empty folder "tutorial", create a build.sbt file with the following:

scalaVersion := "2.11.8"

libraryDependencies += "ch.epfl.lara.synthesis" %% "perfect-core" % "0.1"

Create the file src/main/scala/Main.scala with the [following content](src/main/scala/example). It describes a simple programming language with variable naming and string concatenation. We will now review the file. You can write the content as we describe it.

First write the package and import the core and predefined lenses:

package example

import perfect.core._
import predef._

Now we describe a set of expressions. Note that we need to define And, Equal and BooleanLiteral because they are required to reason about formulas later.

object Expressions {
  abstract class Expr
  case class StringLit(value: String) extends Expr
  case class Variable(name: String) extends Expr
  case class Concat(a: Expr, b: Expr) extends Expr
  case class Let(name: Variable, expr: Expr, body: Expr) extends Expr

  case class BAnd(left: Expr, right: Expr) extends Expr
  case class BEqual(left: Expr, right: Expr) extends Expr
  case class BooleanLiteral(b: Boolean) extends Expr
}

We start by a scala App, and mix-in the three main traits ProgramUpdater with ContExps with Lenses. The first trait defines all common utilities, the second one augmented contextual expressions, and the third one the lenses concept, which serve to repair program based on output. We mix-in also traits for dealing with String, StringConcat, Let and Variable.

object MySimpleLanguage extends App
    with ProgramUpdater with ContExps with Lenses
    with StringLenses
    with StringConcatLenses with LetIndependentLenses
    with VariableLenses
{

Let us import Expressions

    
import example.Expressions._

ProgramUpdater requires that we provide expressions and variables. The symbol type is used only for type language, let's ignore it for the moment. The cache helps to reduce computation time.

type Exp = Expr
type Var = Variable
type Symbols = Unit
implicit def symbols: Symbols = ()
implicit val cache = new Cache

A value should be a literal, or a lambda without free variables. We have to provide a test for a variable.

def isValue(e: Exp): Boolean = e.isInstanceOf[StringLit] ||
  e.isInstanceOf[BooleanLiteral]
def isVar(e: Exp): Boolean = e.isInstanceOf[Variable]

We provide PERFECT ways to build formulas using boolean expressions in our language.

/** Builds an equality constraint */
def Equal(e1: Exp, e2: Exp): Exp = BEqual(e1, e2)
/** Builds a conjunction of constraints */
def And(e1: Exp, e2: Exp): Exp = BAnd(e1, e2)

/** Value of a true expression */
def ExpTrue: Exp = BooleanLiteral(true)
def ExpFalse: Exp = BooleanLiteral(false)

Later, when we will be able to insert variables, PERFECT needs to introduce let-statements.

/** Assigns a given variable to e inside a body */
def Assign(v: Var, e: Exp, body: Exp): Exp = Let(v, e, body)

In order to traverse trees and modify them, PERFECT requires an extractor for each expression. An extractor returns a list of sub-expressions and a way to rebuild them. It does not extract variables.

/** Extractor for all expression */
def extractors(e: Exp): (Seq[Exp], Seq[Exp] => Exp) = e match {
  case Let(name, expr, body) => (Seq(expr, body), eb => Let(name, eb.head, eb.tail.head))
  case Concat(left, right) => (Seq(left, right), lr => Concat(lr.head, lr.tail.head))
  case BAnd(left, right) => (Seq(left, right), lr => BAnd(lr.head, lr.tail.head))
  case BEqual(left, right) => (Seq(left, right), lr => BEqual(lr.head, lr.tail.head))
  case e => (Seq(), _ => e)
}

We need to tell which variables an expression is binding inside it. It will be useful to compute free variables.

/* Which variables these expressions bind. */
def bindings(e: Exp): Set[Var] = e match {
  case Let(v, expr, body) => Set(v)
  case _ => Set.empty[Var]
}

We need to provide a way to create fresh variables. Our variable system is very simple here.

/** Fresh variable creation */
def freshVar(exp: Exp, name: Option[String], showUniqueId: Boolean, others: Var*)(implicit symbols: Symbols): Var = {
  val n = name.getOrElse(exp match {
    case Variable(nn) => nn
    case _ => Utils.makeVariableName(exp.toString)
  })
  val nWithoutConflicts = Utils.uniqueName(n, others.map(_.name).toSet)
  Variable(nWithoutConflicts + "1")
}

Later, when we will have constraints which are harder to solver (e.g. changes at different places), these two methods will be useful.

// Unused for the moment.
def solveGeneralConstraints(constraint: Exp,freeVariables: Seq[Var]): Stream[Map[Var,Exp]] = Stream.empty
def weakCondition(v: Var,c: OriginalValue): Exp = v === c.e

Our little language needs an interpreter. The interpreter returns a Left expression containing the value of the result or a Right expression with the message of the exception.

/** Evaluates a given closed expression */
def eval(expr: ContExp)(implicit symbols: Symbols): Either[ContExp, String] = {
  try Left(ContExp(e(expr))) catch { case e: Exception => Right(e.getMessage) }
}

// Helper
def e(expr: ContExp)(implicit symbols: Symbols): Exp = {
  implicit def toContExp(e: Exp): ContExp = expr.subExpr(e)
  expr.exp match {
    case Concat(left, right) => (e(left), e(right)) match {
      case (StringLit(v), StringLit(w)) => StringLit(v+w)
    }
    case v: Variable => expr.context.known(v).getValue.get
    case Let(v, value, body) => e(ContExp(body, expr.context.withOverride(v, e(value)))
    case BEqual(left, right) => (e(left), e(right)) match {
      case (a, b) => BooleanLiteral(a == b)
    }
    case BAnd(left, right) => (e(left), e(right)) match {
      case (BooleanLiteral(a), BooleanLiteral(b)) => BooleanLiteral(a && b)
    }
    case _ => expr.exp
  }
}

The lenses that we mixed in now require us to implement methods to extract various composants so that it can understand what they are doing.

/** Extraction link */
def extractStringliteral(e: Expr): Option[String] = e match {
  case StringLit(v) => Some(v)
  case _ => None
}

def buildStringLiteral(e: String): Expr = StringLit(e)

def extractStringConcat(e: Expr): Option[(Expr, Expr)] = e match {
  case Concat(left, right) => Some((left, right))
  case _ => None
}

def buildStringConcat(left: Expr, right: Expr): Expr = Concat(left, right)

def extractLet(e: Expr): Option[(Variable, Expr, Expr)] = e match {
  case Let(v, value, b) => Some((v, value, b))
  case _ => None
}

def buildLet(v: Variable, assigned: Expr, body: Expr): Expr = Let(v, assigned, body)

That's it ! Now we can use these lenses and combine them into one lens. Here is a possible order. Most lenses are preemptive, which mean that when one succeeds, the subsequent are not invoked. The first two lenses are usual, and the order of the remaining lenses usually does not matter. Later when we will have goals, the order will matter.

/** The main reversion lens */
def lens: SemanticLens =combine(
  NoChangeLens,
  ConstantReplaceLens,
  StringConcatLens.named("StringConcat"),
  LetLens,
  VariableLens
)

Now we are set up with everything, we can invoke the repair function as expected. This little program returns the string I think that you are perfect because you love math.. The user then edits the first "you" and replaces it by "we". After repair, the execution of the program replaces also the second "you" by "we" because it updated the variable's value.

  val a = Variable("a")
  val prog = Let(a, StringLit("you"),
    Concat(Concat(Concat(StringLit("I think that "), a), StringLit(" are perfect because ")),
      Concat(a, StringLit(" love math."))))

  assert(eval(prog) == Left(StringLit("I think that you are perfect because you love math.")))

  Utils.Log.activate = true
  val prog2 = repair(prog, StringLit("I think that we are perfect because you love math.")).head
  assert(eval(prog2) == Left(StringLit("I think that we are perfect because we love math.")))
}

Run your file using

sbt run

There should not be any error and the programs are repaired correctly.