-
Notifications
You must be signed in to change notification settings - Fork 37
Tutorial
- What is the Fast Tree Language (FTL)
- Classes and Interfaces
- Attributes and attribute types
- Actions
- Actions in Loops: Collective Definitions
- Traits
- Rendering
- Invoking the Compiler
- Invoking a synthesized HTML5 layout engine
- Debugging HTML5 Layout
- Why do I not see anything?
The Fast Tree Language (FTL) is a declarative attribute grammar language. Given a language specification, it emits a evaluator that can solve the attributes on a tree (document) in a bounded number of parallel traversals. For convenience, FTL supports a class system, loops, and a rendering API. Documents for input are specified in XML. FTL's C++ implementation supports using CSS templates for bulk definition of input node attributes but the JS version does not at this point.
A grammar can define its own types, defines the document schema in terms of classes, interfaces, and attributes, and defines the values of attributes in terms of actions. It can share code using traits. A typical grammar has the following structure:
type Shape = Circle | Square | Line
/* more types */
interface I1 {
var a : int;
var siblingId : int;
var p : int;
}
/* more interfaces */
trait ChildCount {
attributes {
var numC : int;
}
actions {
loop moreChilds {
numC := fold 0 .. $-.numC + 1;
}
}
}
class C1(ChildCount) : I1 {
children {
myChild : I1;
moreChilds : [ I1 ]
}
attributes {
var b : bool;
input c : Shape;
input d : ?int;
input e : int = 2;
var numSiblings : int;
}
actions {
a := 2;
self.b := myChild.a == 3 ? true : false;
loop moreChilds {
moreChilds.p := 1 + moreChilds$i.a;
moreChilds.siblingId := fold 0 .. moreChilds$-.siblingId + 1;
numSiblings := moreChilds$$.siblingId;
}
}
}
/* more classes */
A typical document (C++ backend):
<style>
box, mbox { display: C1; d: 20 }
box { refname: myChild; c: Circle }
mbox { refname: moreChilds; c : Square }
</style>
<box>
<mbox/>
<box/>
<mbox>
<box/>
</mbox/>
<mbox/>
</box>
A typical document (weaker HTML5 backend without CSS selectors):
<C1 refname="myChild" d="20" c="Circle">
<C1 refname="moreChilds" d="20" c="Square"/>
<C1 refname="myChild" d="20" c="Circle"/>
<C1 refname="moreChilds" d="20" c="Square">
<C1 refname="myChild" d="20" c="Circle"/>
</C1>
<C1 refname="moreChilds" d="20" c="Square"/>
</C1>
Topics covered: class interface
The class and interface system defines the set of syntactically valid input documents. In the example, "class C1 : I1" means class "C1" implements interface "I1". There may be other classes that also implement "I1". In an input document, a "C1" node is indicated using attribute 'display="C1"'. The JS version currently instead uses the tag name ("<C1/>").
Classes must specify their child node types in the "children" section. In the example, "myChild : I1" indicates C1 has a child aliased "myChild" of interface "I1". In the input document, this relationship is indicated by using attribute 'refname="myChild"' on the child node. Multiple children may be referenced collectively. For example, "moreChilds : [ I1 ]" indicates that there may be 0 or more children with 'refname="moreChilds"' and they can instantiate different classes that implement "I1".
Topics covered: type <userType> = <name> (| < name >)* (var | input) <attr> : [?] (bool | float | int | px | color | <userType>) [ = <const>]
Each node has attributes associated with its interface and class. We will revisit this, but interface-level attributes are referenceable by parent nodes, but class-level attributes are only referenceable by the node.
Attributes are either of system-implemented types or of user-defined types. System types are "bool", "int", "float", "px" (pixel), and "color". These are fully supported in the C++ version; the HTML5 backend has weaker support for "px" and "color". User-defined types are specified as enumerations, as in "type Shape = Circle | Square | Line". After this definition, "Circle" and "Square" can be used as values.
Attributes have modifiers "var" or "input". Modifier "var a : int" means the document does not supply the value of "a"; the grammar is responsible for finding its value based on the values of other attributes. Modifier "input c : Shape" means the document provides input attribute 'c="Circle"'. Note that both system and user-defined types may be used for input types.
Input attributes may be optional. This comes in two forms. First, as in "input e : int = 2", if the input attribute is not defined by the document, the value "2" will be used. Second, as in "input d : ?int", the grammar may dynamically inspect attribute "d" using functions "isEmptyInt(d)" and "valueInt(d)". Function "isEmptyInt" returns true iff no input integer is available, and if it is available, "valueInt" returns the integer value.
If an input attribute was not flagged as optional and is missing from the document, its use should throw an error.
Topics covered: <node><attr> := <expr>
Classes provide actions that constrain attribute values of the node and its children in terms of other attributes of the node and its children. The order of actions in a class does not matter. The FTL compiler will check that every attribute is defined and infer the order of evaluation.
Each attribute is named by the node and attribute name. For example, in "self.b := myChild.a == 3 ? true : false;", attribute "a" of child "myChild" is inspected to determine the value of attribute "b" of the node instantiating class "C1". Node identifier "self" is optional, as seen in "a := 2". Note that typical arithmetic and ternary conditional expressions can be on the right-hand side of an action.
Attributes abide by the class system. First, any class or interface attribute may be accessed for a "self" node, but only interface attributes may be accessed on a child node. Second, interfaces have an implicit contract on whether the implementing class provides the action to solve an attribute or if the class of the parent node must solve it. Our analyzer automatically infers and checks this relationship.
Topics covered: loop <child> { <action>* } <node>($- | $i | $$)
Actions may occur in loops. For example, "loop moreChilds { ... }" contains actions that either read or define attributes of the "moreChilds" children of C1. Multiple loops may be used, and as with normal actions, which loop an action is placed in does not matter to the compiler. Currently, loops cannot be nested.
Collective assignment a child's attribute may reference other attributes of the child by using name suffices. For example, in "moreChilds.p := 1 + moreChilds$i.a;", the "p" attribute of the ith child is 1 plus its "a" attribute value.
It is convenient to reference the previous node's attributes, such as for counting: "moreChilds.siblingId := fold 0 .. moreChilds$-.siblingId + 1;". Suffix "$-" defines the ith node in terms of the "i - 1"th node. For the first node, there is no previous node, which is why we use the special "fold" form of "fold <expr> .. <expr>", where the first expression provides an initial value. Unlike accumulators in traditional fold operator, the previous attribute can be referenced from a different attribute also defined by a fold expression. (You can use "$-" of attributes besides the one you are currently defining).
It is also useful to reference the last value of a collective definition. For example, "numSiblings := moreChilds$$.siblingId" will be 0 if there are no children (due to the initial fold value) and 3 if there are 3 children (due to the full fold expression).
Code sharing is currently performed through a simple trait construct. For example, if counting the number of children is a common enough behavior, we could encapsulate the code as a trait:
trait ChildCount {
attributes {
var numC : int;
}
actions {
loop moreChilds {
numC := fold 0 .. $-.numC + 1;
}
}
}
The attributes { ... } and actions { ... } blocks are analogous to what is seen for classes. In this case, the _numC_attribute is introduced and it is the sum from looping over children moreChilds. Children could also be introduced in a trait using a children { ... } block.
The trait is mixed into a class, adding whatever children, attribute, and actions it has to that class. For example, class C1 mixes in trait ChildCount. Once mixed in, the class definition implicitly expands into:
class C1(ChildCount) : I1 {
children {
myChild : I1;
moreChilds : [ I1 ]
}
attributes {
var b : bool;
input c : Shape;
input d : ?int;
input e : int = 2;
var numSiblings : int;
var numC : int; //new
}
actions {
a := 2;
self.b := myChild.a == 3 ? true : false;
loop moreChilds {
moreChilds.p := 1 + moreChilds$i.a;
moreChilds.siblingId := fold 0 .. moreChilds$-.siblingId + 1;
numSiblings := moreChilds$$.siblingId;
}
loop moreChilds {
numC := fold 0 .. $-.numC + 1; //new
}
}
}
Traits are entirely syntactic. Future versions of traits will likely enable more flexible binding mechanisms.
Multiple traits may be mixed in (C1(ChildCount1, ChildCount2, ...)). The order of traits do not matter. If traits conflict, the synthesizer will report an error, and if they are fine, the synthesizer will find a sound order of evaluation.
FTL provides a rendering API. An initial form of FTL associated a visual shape with each node, but we found this to be too restrictive. Now, we expose an "immediate-mode" rendering API. The FTL compiler will automaatically schedule calls based on dependencies. For example, to paint a 1x1 at (x=0,y=0,z=2) square and then a 100x100 one at (x=0,y=0,z=2), assign "render := paintRect(0, 0, 1, 1, "#000", 2) + paintRect(0, 0, 100, 100, "#000", 2)". To then paint another 3x3 rectangle on top, assign "fld2 := render + paintRec(0,0,3,3,"#000",2). FTL will track the dependencies to paint in the right order.
Currently, the GPU-accelerated C++ implementation may have visual glitches for overlapping shapes, irrespective of their order.
Paint calls:
- int paintRect (int x, int y, int w, int h, int col, int z)
- int paintRectZ (int x, int y, int w, int h, int col, int z, int ignore)
- int paintQuad( int x1, int y1, int z1, int x2, int y2, int z2, int x3, int y3, int z3, int x4, int y4, int z4, int col, int ignore)
- int paintLine (int x1, int y1, int x2, int y2, int col, int ignore)
- int paintOval (int x, int y, int w, int h, int col, int ignore)
FTL can be invoked through our Ant build script. It has two backends, HTML5 and C++, and options to control the search for schedules.
To generate HTML5 code on input "foo/bar.ftl" as "baz/bar.js", from the "projects" folder run:
ant -DaleGrammar=foo/bar.ftl run-alegen-html5 -Doutput.dir=baz
To generate the C++ code:
ant -DaleGrammar=foo/bar.ftl run-alegen-ftl -Doutput.dir=baz
There are additional options for controlling the search. E.g., to limit search to "greedy prefix" schedules, to a schedule length, all parallel, or enumerate multiple. See the "build.xml" file for these options.
For layout language "mylanguage.ftl", which compiles into layout engine "mylanguage.js", include the following in your HTML document:
<html>
<head>
<title>Demo</title>
<script src="mylanguage.js"></script>
<script src="render.js"></script>
<script src="jquery-1.6.1.js"></script>
<script>
window.addEventListener("load", function () { displayDoc(0); }, false);
</script>
</head>
<body>
<canvas id="canvas"/>
<contents id="contents">
<C1 refname="myChild" d="20" c="Circle">
<C1 refname="moreChilds" d="20" c="Square"/>
<C1 refname="myChild" d="20" c="Circle"/>
<C1 refname="moreChilds" d="20" c="Square">
<C1 refname="myChild" d="20" c="Circle"/>
</C1>
<C1 refname="moreChilds" d="20" c="Square"/>
</C1>
</contents>
</body>
</html>
All debug output is sent to the global logger object. The document may redefine this object, such as with the following code:
if (true) logger = {log: function () {}, group: function (){}, groupEnd: function(){}, error: function() {} }; else logger = console;
By default (true), logging is disabled. Changing the condition to false will output logs to Firebug's _console_API.
In general, try opening a JavaScript console / debugger (e.g., Firebug) for a more specific error message. A common error is having logging enabled (see above) but no console supported by the browser (e.g., Firebug is disabled).