Constant Folding in the TeSSLa compiler

The TeSSLa compiler is capable of highly advanced constant folding/constant evaluation features. In general all constant expressions that appear in a TeSSLa specification, i.e. are not relying on stream values, are already evaluated during compilation.

A simple example

The most simple form of this constant evaluation can be seen in the following specification:

in x: Events[Int]

def y = 3
def z = y + 8
def o = x + z

out o

In this specification there is an input stream x. Further there are variables y and z (of type Int) defined as 3 and the sum of y and 8, respectively. An output stream o (of type Events[Int]) is finally defined as the sum of x and z.

What the TeSSLa compiler does with this specification can be seen if we instruct the compiler to deliver us the TeSSLa Core code, i.e. the compiler-internal code which is used by the TeSSLa backends. This can be done by running the command tessla compile-core spec.tessla:

in x: Events[Int]

out o$461

def z$462: Int = 11
def o$461: Events[Int] = extern("slift")[Int, Int](x, $463)
def $463: (lazy Int) => Int = (x0: lazy Int) => {
  extern("add")(x0, z$462)

What can be realized in this code is, that variable y is fully removed from the TeSSLa code and the result of y + 8 = 11 was already computed by the compiler and is not evaluated at runtime.

More complex constant folding

The capabilities of the compiler's constant folding however go far beyond the evaluation of simple integer additions. Since TeSSLa specifications can only consume inputs via input streams, the compiler is always able to evaluate every non-stream expression (which does not rely on unknown external, backend specific definitions). Consider for example the following specification:

# Constant part
def fac(x: Int): Int = if (x == 1) then 1 else x * fac(x-1)
def m: Map[Int, String] = Map.add(Map.add(Map.add(Map.empty, 1, "a"), 24, "b"), 27, "d")
def v: String = Map.get(m, fac(4))

#Stream-related part
in x: Events[Int]
def o: Events[String] = const(v, x)

out o

In the static part the factorial of 4 is recursively computed, and a corresponding letter is looked up in a map data structure and stored in variable v (the value of v is "b"). This variable is then used in a const stream expression in the lower part of the specification.

The TeSSLa compiler evaluates the complete constant part of the specification already during compilation time. Calling tessla compile-core spec.tessla yields:

in x: Events[Int]

out o$460

def o$460: Events[String] = extern("slift")[Int, String](x, const$461)
def const$461: (lazy Int) => String = (_$462: lazy Int) => {

Dynamic stream structures with constant folding and macro expansion

The capabilities of the TeSSLa constant folder can be used to dynamically create complex stream structures. Therefore one can use macros which return streams but can be unrolled at compilation time. The classical example for this would be the macro prevN which takes the n-th previous value of a stream:

def prevN[A](s: Events[A], n: Int) : Events[A] = {
	static if n == 0 then s else last(prevN(s, n-1), s)

in x: Events[Int]

def n = 2 + 1
def o = prevN(x, n)

out o

Here the TeSSLa compiler unrolls (expands) the macro already during compilation and yields:

in x: Events[Int]

out prevN$461

def prevN$463: Events[Int] = extern("last")[Int, Int](x, x)
def prevN$462: Events[Int] = extern("last")[Int, Int](prevN$463, x)
def prevN$461: Events[Int] = extern("last")[Int, Int](prevN$462, x)

Likewise streams can be stored in dynamic data structures (like maps) and then be resolved during compilation. E.g. in the following example.

in a: Events[Int]
in b: Events[Int]
in c: Events[Int]

def m: Map[Int, Events[Int]] = Map.add(Map.add(Map.add(Map.empty, 0, a), 1, b), 2, c)

def addPrev(map: Map[Int, Events[Int]]): Map[Int, Events[Int]] = {
	Map.fold(map, Map.empty, (newMap, id, stream) => Map.add(newMap, id, prev(stream)))

def twoTimesPrev = addPrev(addPrev(m))

def ppb = Map.get(twoTimesPrev, 1)
out ppb

def ppb2 = prev(prev(b))
out ppb2

There a map m is defined which maps an id (Int from 0 to 2) to an input stream. The function addPrev then takes this map, iterates it and produces a new map, where every stream of the previous map is wrapped into a previous operator prev. Thus, addPrev(addPrev(m)) delivers a map of the input streams with two prev operators wrapped around them and Map.get(twoTimesPrev, 1) is thus equal to the stream expression prev(prev(b)) I.e. the output streams ppb and ppb2 are equal.

The generated TeSSLa Core code looks as follows:

in a: Events[Int]
in b: Events[Int]
in c: Events[Int]

out addPrev$465
out addPrev$465

def addPrev$465: Events[Int] = extern("last")[Int, Int]($468, $468)
def $468: Events[Int] = extern("last")[Int, Int](b, b)

As in the other examples all constant expressions (map structures etc.) have been folded away by the compiler and only the two prev stream operations (expressed by last operators) remain. Note that the compiler has even detected the equivalence of ppb and ppb2 and only contains the corresponding stream once.

Advantages of constant folding

The extensive constant evaluation of the TeSSLa compiler at compilation time brings the following advantages:

Building DSL-like structures with help of constant-folding features

A pattern when developing TeSSLa specifications and libraries is to describe a high-level structure which shall be monitored (like a logic or automaton) in a constant expression which uses macros or complex data structures. This strucutre is then internally transformed to a interconnection of intermediate streams (often over simple data structures) that can then be used for monitoring.

An example is e.g. the TeSSLa Petri net library. There a Petri net can be described in a DSL-like combination of addPlace and addTransition function calls and streams for observing the number of tokens at a specific place can then be retrieved:

include lib "petri_net:1.0.0"

import PetriNetMonitoring
import PetriNetStructure

in t0: Events[Int]
in t1: Events[Int]
in t2: Events[Int]
in t3: Events[Int]

def petriNet =
  addPlace("s0", 2, Some(10), true,
  addPlace("s1", 0, None, false,
  addPlace("s2", 0, None, true,
  addTransition("t0", Set.empty, Set.singleton(("s1", 1)), t0,
  addTransition("t1", Set.empty, Set.singleton(("s0", 1)), t1,
  addTransition("t2", Set.add(Set.singleton(("s0", 1)), ("s1", 2)), Set.add(Set.singleton(("s2", 1)), ("s1", 2)), t2,
  addTransition("t3", Set.singleton(("s1", 1)), Set.empty, t3,
def tokenCntMonitor = toTokenCntMonitor(petriNet)

out tokenCntMonitor.tokenCnt("s1") as tokens
out tokenCntMonitor.overflow("s1") as overflow

During compilation the complex net structure is completely folded away and only Int streams for tracking the tokens of a specific place remain.