Maybe Semantics

In stochastic content generation, sometimes it is convenient to have constructs to express the idea of something may or may not exist. We call this a maybe-semantics. In GIGL, this idea is applied when generating children of a rule and supported naturally by C++ pointer semantics.

• • When a pointer is a null pointer, it represents nothing, otherwise it represent actual content (assuming it points to a memory corresponding to an appropriate variable type).

  • The special syntax provided by GIGL on maybe semantics is a variant of node generator calls. If a probability value is specified in < and > after the generate keyword, this means there is only some probability this returns what was originally intended to be generate without this maybe semantics, and in the remaining probability it returns a null pointer, we call this a maybe generator call, or maybe node generator call. An example of this can be found at the Tree demo, where the

  • generate<branch_prob> TreePart(...)

  • returns what would be returned by

  • generate TreePart(...)

  • with branch_prob probability, and a null pointer with 1 - branch_prob probability. This is used to represent that a branch may or may not exist, which is beneficial to break symmetry as opposed to always generating the branch. The syntax definition for maybe generator calls can be found at [Here].

  • When using maybe generator calls, nothing needs to be changed on the rule signature (i.e. how rule children are declared), however just keep in mind that children assigned with maybe generator may get null pointer value. Therefore, the user is expected to guard against null pointers in the part of GIGL code explicitly user written (for the part that is implicit in GIGL framework, such as the implicit destructor, the guard against null pointers was already there).

  • Strictly speaking, maybe semantics does not increase the expressive power from the formal language point of view. Because every maybe semantics can be replaced with an additional nonterminal type with two expansion rules. The maybe-semantics in the Tree demo can be simulated by rewrite the item grammar to be:

  • TreePart := ntTree(TreePart, MaybeBranch, MaybeBranch, TreePart)

  • | termTree(TreeSegment),

  • MaybeBranch:= justBranch(TreePart)

  • | noBranch(),

  • and then the maybe generator calls are no longer needed. However, do we actually need the maybe semantics? Yes, because in certain cases it make the expression of design idea more direct and convenient. Do we always prefer using maybe-semantics over working on the item grammar? No, because in some other cases it is more natural to use item grammar to encode it.

    • When what the possible "nothing" means is close to literally nothing, then using maybe-semantics is preferred, and it can save much trouble on specifying implementations on implementation of attributes, which doe not have any concrete meaning anyway. For example, for the alternative item grammar above, the "justBranch" rule would just be passing attributes right through untouched, and the "noBranch" rule has no attribute implementation that actually gets used. In this case, using the maybe-semantics would be very appropriate, and the only slight addition there is guarding against null pointers when rendering.

    • When the possible "nothing" actually means something, then working on the item grammar is preferred, because the use of maybe-semantics would just try to cram one rule with what should be in two or more rules, which would introduce excessive switch or if-else statements which are designed to be expressed with grammars at the first place. For example, for the quiz demo, it is inappropriate to consider the "termTree" is considered a possible "nothing" in a maybe semantics, because it encodes the concrete syntax of a unit segment. With maybe-semantics, the "TreeSegment" child could no longer be in the rule signature and it would have to be created in the implementation and in some switch statement, and similarly for its rendering, all of which would be a mess. A simple rule of thumb here is that if you find yourself needing to write switch statements or if statement with both then and else branches, then it is likely time to consider adjusting the item grammar rather than using maybe-semantics etc..

  • This feature is still in early experimentation, we may consider adding more maybe-semantics syntax such as maybe constructor etc. In addition, how maybe-semantics can work with implicit generator calls may also be considered.