1
$\begingroup$

Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming.

What are the reasons leading to the choice of a syntax tree in genetic programming? Are there any particular assets in using this representation?

$\endgroup$
  • 1
    $\begingroup$ Do you mean syntax trees produced by a parser, or rather what is usually called Abstract Syntax Tree (AST)? $\endgroup$ – babou May 19 '15 at 10:11
  • $\begingroup$ I meant an AST. $\endgroup$ – Chirac May 19 '15 at 10:15
  • 2
    $\begingroup$ Do you mean programs that implement genetic algorithms, or genetic algorithms that work on populations of programs? I don't understand the former question, and the latter probably has the boring answer "because it works better". $\endgroup$ – Raphael May 19 '15 at 14:06
5
$\begingroup$

In short: AST representations of programs are more easily analyzed, manipulated, and transformed, while preserving and enforcing the existence of a formally defined program meaning through the transformations.

I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples.

The question is an issue about abstract objects (semantics) and their representations (syntax). We are usually interested in the semantics, applying transformations to entities to change or combine their meanings, their semantics, which can belong to all kinds of domains. But semantics is elusive, mathematical abstraction, and all we can actually manipulate to express our intent is syntax representations.

That is the basis of all programming, but is also to be found in logic, proofs, and finally all of mathematics. That is what makes the choice of representations and notations often so important. Good choice of representation will lead to easier, possibly more perspicuous or intuitive understanding of the problem and be better adapted at expressing answers, and proofs, for given questions.

The point is well known to programmers, as they are taught that it is essential to choose the right data structure in order to implement an algorithmic solution to a given problem. The choice of data structure is the choice of representation. And I just made a similar answer to a question on constructing (programming?) Turing Machines.

Note that there is a partially ambiguous use of the word syntax, which can be any concrete representation of an abstraction, or can be intended to mean only textual representation as strings (we are getting close to Turing machines), possibly structured by some logical system (a context-free (CF) grammar for example that specifies what are the legitimate strings, the well-formed-strings.

In fact, the existing parsing-unparsing technology, especially for CF grammars, makes it generally easy to switch between textual and an associated tree representation, to the point that they are often not distinguished much. Actually, mathematicians have been using tree representation (formally defined as Algebras), long before that technology existed, and this is what lead to using the representation of AST in manipulating programs.

So what was so convenient about these tree (or AST) representations?

The key points are:

  • it is very convenient for associating precisely semantic meaning to syntactic constructs, in a compositional way, by means of a simple mathematical concept: the homomorphism;

  • it provides and enforces a syntactic type system (statement, expression, ...) that preserve the existence of some meaning when the program representation is transformed in a way that preserves the syntactic typing constraints;

  • it is easily manipulated to actually perform analysis and transformations;

  • it is easy to decorate it with localized information to help or guide these analyses and transformations.

First, if you take a string representation of a program, without further structural information, there is no simple way to delimit substrings that have naturally a meaning of their own (I am saying naturally, because some people may always try to play at abstracting syntactic context or indulge in syntactic (text oriented) continuation games - ignore this if you do not get it).

The idea of a tree structure, with nodes labeled with operators, possibly restricted by syntactic types (statement, expression, variable, ...) is that they naturally decompose the syntactic structure into subparts (the subtrees) that can have fairly naturally, and perspicuously with respect to computational concepts, a semantic meaning of their own.

Then, if we associate a semantic function to each operator, we can get the meaning of a tree representation by applying the semantic function of the root operators to the semantic meaning of each of its subtrees. If we also provide some semantics to leafs operators (which may be defined as a mapping from syntactic representations to some semantic domains possibly by other means, for example associating the integer 23 to the string "23"), we know how to define simply the semantics of any well-formed tree, whether complete program or well-formed program fragment. This is the basis of what is known as denotational semantics.

In other word, the homomorphism thus defined gives a rather simple and tractable way to associate meaning to well-formed program fragments, by composing the meanings of its well-formed sub-fragments (this is known as semantic compositionality). Then, it becomes much easier to attempt defining semantically meaningful transformations. And semantics, what the program (fragment) does is what we really care about.

Furthemore, AST are fairly easy to manipulate by programs to express these transformations that somewhat respect the semantic structure (as they manipulate subtrees that are semantically meaningful), which initially justified their use in program editors, program manipulation systems, and programming environment.

Actually, the concept of AST in programming appeared with the language Lisp (and its ability to manipulate Lisp programs syntactically) in the very late fifties. But it developed mostly in the seventies (Emily, Cornell synthesizer, Mentor/Centaur), and further in the eighties, at the same time as denotational semantics (which is based on the above approach), and most likely under the influence of denotational semantics. The early work (LCF) on automated proofs about computation may also have been influencial.

From the point of view of genetic programming, the use of AST both facilitates and enforces the creation of syntactic structures that are more likely to have some meaning. Manipulating unstructured string representations would be likely to result in being swamped with string representations to which no meaning can be associated.

Another advantage of AST representations is that they are fairly easy to decorate with additional information: precomputed semantic properties, weights, or whatever is deemed useful for the intended program transformation or manipulation, including genetically programed transformations.

A detailed example

This section has been added later to answer some comments.

I will try to work out one example in some details to explain the relation between manipulations on the AST and their semantics conterpart.

We take a very simple example of crossover between two ASTs: T1=foo(exp1,exp2) and T2=bar(exp3, exp4). I keep it small for readability. Actually, exp1 to exp4 are meant to be subtrees of some AST, while you may also see what is around them as standing for the rest of some AST (or some AST subtree) that is the context in which they occur.

We suppose first that the language does not have typing (in the usual sense of programing languages), and accept any value in any context expecting a value, so that any expression can legitimately replace any other.

Then given T1 and T2, it is legitimate to apply a crossover that swaps exp1 and exp4, thus producing T1'=foo(exp4,exp2) and T2'=bar(exp3, exp1). Note that the algorithm could also consider only one of these two trees (I am incompetent regarding genetic splicing strategies).

Now, let us see what can be said about semantics, without getting too much into details.

Let $S$ be the semantic function, $V$ the domain of values, $M$ the domain of environments that map identifiers to values. The semantics $S$(exp) of an expression exp is a function $e: M\to V$ that takes an environment $m$ as argument (so that we have values for identifiers) and returns the value of the expression in that environment.

Now, if the operators foo and bar are supposed to compute respectively two functions $f$ and $b$ on their arguments, the semantics of T1, for example, will be defined as

$S$(foo(exp1,exp2))=$S$(foo)($S$(exp1),$S$(exp2))=$\lambda m.f(e_1(m),e_2(m))$

You notice that the semantic function is not necessarily easy to define in the complex case of a programming language, since for foo we have here $S$(foo)=$\lambda e, e', m\,.\, f(e(m), e'(m))$.

This complexity results from the choice of the Abstract Syntax, that considers here foo and bar as AST operator nodes. Instead, the AST could have a call operator that has several daughters, for example as in call(foo, exp1, exp2). Then the complexity of dealing with the environment $m$ would be factorized in the semantics of call, while the semantics of foo would simply be the function $f$.

Sorry for this complexity.

The whole point is that we can define the semantics of an AST subtree such as exp1 independently of any context, but as a function $e_1$. Whatever information it needs from the context to be evaluated is summarized in the arguments (here the environment $m$) that are passed to its semantics. And this information is in turn passed to the semantic functions associated to subexpressions.

So now we know that a subtree of AST can have a well defined semantics, independently of its context.

But what about the context? Does it have a well defined semantics when a subtree is missing. The nice point is that it does.

If you consider the context foo(??,exp2), what can its semantics be. The natural answer is that it is whatever semantics it would have if you provided the missing part. In other words, it is a functional semantics that takes as argument the semantics of the missing part. This is very similar to the semantics of the complete expression $S$(foo(exp1,exp2)) that we defined above, except that the missing exp1 must be accounted for with an argument $e$ standing for the semantics of whatever expression could replace exp1.

We had $S$(foo(exp1,exp2))=$\lambda m.f(e_1(m),e_2(m))$

So, without going into further details, you have

$S$(foo(??,exp2))=$\lambda e.\lambda m.f(e(m),e_2(m))$

Then, given that $S$(exp1)=$e_1: M\to V$, we have
$S$(foo(exp1,exp2))= $S$(foo(??,exp2))($S$(exp1))

which is precisely what we would like: syntactic abstraction directly translate into semantic abstraction.

Then we also have, of course:

$S$(foo(exp4,exp2))= $S$(foo(??,exp2))($S$(exp4))

In other words, both AST subtrees and AST contexts (of subtree) have well defined semantics, that do not change, and they compose to give the semantics of the whole AST tree when a subtree is placed in a permitted context.

But of course: $S$(foo(exp1,exp2)) $\neq$ $S$(foo(exp4,exp2))

I hope this explains how things work. Using well-formed AST will ensure that you are actually manipulating semantic fragments that compose meaningfully.

Actually, things may be a bit more complicated, because you want to include in the process what is usually called static semantics, i.e. constraints on the AST that are usually checked at compile time. The best known examples are type constraints for statically typed languages, or declaration of identifiers when that is required. Thus you may want to decorate ASTs with this statically computable information, and use splicing techniques that will incrementally preserve the information and check the required constraints on the AST, so that you produce only programs that at least compile.

Then as a last comment, I would like to remarks that linear genetic programming seems to be doing pretty much the same, but restricts splicing to sequences of statements, so that there is always some executable semantics preserved. But I am not specialist of that.

$\endgroup$
  • $\begingroup$ From what you just said, are ASTs in genetic programming (or sub trees) supposed to be meaningly equivalent? Semantic is described by syntax to a certain point, but no homomorphism operation could be performed if ASTs differ by their level of semantics (or abstraction) during crossovers for example. For example, the operation 3 + 3 + 3 is globally equivalent to 3 * 3 but can we truly say that the '+' operator is semantically equivalent to the '*' operator because it gives us the same result? $\endgroup$ – Chirac May 19 '15 at 14:24
  • 1
    $\begingroup$ @Chirac In simple crossover, the semantics of the subparts that are being swapped stays unchanged. But the semantics of the individual trees affected by the crossover is usually changed. What is always preserved, however, is the existence of some well defined semantics for each. The role of homomorphism is to define the semantics of whatever AST tree or subtree you are considering. It does not participate in the genetic AST transformations. However, it can also be used to associate an unchanging meaning to the 2 tree contexts where the cross-over takes place. $\endgroup$ – babou May 19 '15 at 17:32
  • 1
    $\begingroup$ @Chirac For example, if you have the AST for foo(exp1,exp2) and bar(exp3, exp4). You swap exp1 and exp4 in a crossover. The semantics of exp1, exp2, exp3, and exp4 are preserved, and so is the semantic of foo(??,exp2) and bar(exp3,??) which is actually a functional semantics. But the semantics of the two complete trees has changed. Am I answering your question? $\endgroup$ – babou May 19 '15 at 17:34
  • 1
    $\begingroup$ @Chirac What we can say, for example is that x+x+x is equivalent to 3*x and to x*3. Actually, it should be said with x as a syntactic metavariable that could be any AST expression (up to type - I have to skip details). Such equivalences were used at some point to perform semantics preserving program transformations. Applicability of such tranformations was driven by matching techniques, on trees, on terms of equational algebras, or on lambda terms. I guess the same techniques could be used for more complex mutations or crossovers in genetic programming, no longer semantics preserving. $\endgroup$ – babou May 19 '15 at 17:36
  • $\begingroup$ From your second comment, why would the semantics of the two complete trees change if their functional semantic is preserved? $\endgroup$ – Chirac May 20 '15 at 7:31
3
$\begingroup$

Syntax trees provide an abstract representation of a program with a certain kind of type information at each vertex. This allows, when attempting to evolve a program, the swapping/changing of subtrees as long as the root vertex of the subtrees have the same type. As long as the program was valid, (and the subtrees are also valid), the result will still be a valid program.

As a somewhat trivial example if your programming language has a rule for addition expressions along the lines of $\langle plus \rangle ::= \langle expression_{1}\rangle + \langle expression_{2} \rangle$, then anything that is an $expression$ (i.e. that satisfies the typing rules for $expression$) can be put in place for $\langle expression_{1}\rangle$ or $\langle expression_{2} \rangle$. So if you're trying to implement a crossover operator for example, you know the places where you can swap subtrees and still get something that makes at least a basic level of sense.

This is also why syntax trees are a very important tool in compilation - they have the same utility as representations of the flat text of the program.

Note that tree representations aren't the only way, see for example linear genetic programming.

$\endgroup$
  • $\begingroup$ Thank you for this. I've always seen syntax trees as hierarchical tools to order data and links between data. For example the number 3 and 5 being dependent on the + operator. With your answer, if I understand correctly, it also provides a structure, an entity for my data to be changed dynamically with crossovers etc.. Okay! Thanks again! $\endgroup$ – Chirac May 19 '15 at 8:54
  • $\begingroup$ I am wondering whether linear genetic programming (LGP) should not be seen as a degenerate form of AST based genetic programming. Since the main advantage of AST is to enforce existence of meaning through syntactic types. The point is that LGP, as I understand, is only editing statement sequences, hence preserving a trivial form of syntactic typing. $\endgroup$ – babou May 19 '15 at 12:53
  • 1
    $\begingroup$ To emphasise this: normal "genetic" operations on strings will produce invalid texts (in the sense that the resulting program is not syntactically and semantically valid) with high probability, thus the algorithm will be very, very inefficient. (Decorated) ASTs can be used to define more meaningful operations that maintain validity (with high probability). $\endgroup$ – Raphael May 19 '15 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.