Decision-tree based Finite Domain Constraint Solver, used for building layouts for The Grid.
FlowerFlip is an API that allows the creation of promise-based decision trees. FlowerFlip allows the creation of complexe decision trees by giving the possibility to compose the decision tree of subtrees and managing how the result of these subtrees are handled in the parent decision tree.
The decision tree in FlowerFlip are composed of promises that are chain together to form the decision tree. Decision taken in the decision tree are represented using a
The initial use of FlowerFlip is for Design Systems. Design system are used in TheGrid as solver for web page design as well as HTML and styling rendering of the resulting web page.
The primary API for building decision trees is promise-based.
f = require 'flowerflip't = fRootthen 'foo'# Do somethingelse 'bar'# Handle error
To see more information on a running Flowerflip setup, there are two log settings available:
errors: see details about failed preconditions, aborted trees, and other errors
asserts: see details about failed preconditions
values: see the return values of the promises in the tree
tree: see details about tree execution, including which node is currently being executed
collection: see details about collection fulfillment
branch: see branching
abort: see aborts
To use these, run Flowerflip with the
DEBUG environment variable set, for example:
$ DEBUG=errors grunt test
You can combine them comma-separated, like
Work in progress
This doc is far from being complete and may lack accuracy in certain sections as some discussions are taking place in the issues and questions still need to be answered. But this should still give you a good starting point.
Promises are used to build decision trees. FlowerFlip provides its own implementation of promise with the
What are promises?
Here's a very good introduction to promises: http://www.html5rocks.com/en/tutorials/es6/promises/
Positive & Negative Promise results
When a promise returns a positive result (truthy value) the next promise to be executed in the chain will be one of the following:
If the promise returns a negative results (throw an error, falsy values, abortion of the choice object) the next promise to be called in the chain will be of type:
The Thenable object supports the following methods:
contest(name, tasks, score, resolve)
race methods behave in accordance with the promise specification so they are not covered here.
some promise will be fulfilled if at least one of the promises passed in the
tasks input parameter is fulfilled.
If one or more of
p3 promises are fulfilled, the
.then method will be called and will receive an array, for the
data parameter, where items represent the data being returned from the promises that were fulfilled.
For example if
p3 were fulfilled but
p2 was rejected, the
then method would be called with an array of two items where
data are the data returned by the
If none of the tasks were fulfilled, the next
.always following the
.some method will be called with the last task error as the data parameter.
maybe promise is very similar to
some. The only difference is that if all promises are rejected, the
.always method will be called with the value that was delivered to the maybe promise instead of the last promise error.
Maybe some of these tasks will be fulfilled, if not, continue with the original data.
contest(name, tasks, score, resolve)
contest promise will execute each promise and select one of the tasks that is fulfilled as the winner of the contest.
score callback is passed in, this function will be called with the array of the fulfilled promises and an array of the return values from the fulfilled promise. If no score is passed, the first promise that was fulfilled will win the contest.
The data of the winning promise (task) is then passed to the next positive promise in the chain following the contest. If all promises are rejected the error of the last promise will be passed to the next negative promise in the chain. The winning subtree or branch will be added to the
resolve the contest
resolve callback is used to determine whether the contest was "enough". If not, the contest node is cloned to under the current contest and run again. This allows looping contests until all items have been eaten, for instance. The first time the contest is executed,
choosenSolutions will be empty.
resolve returns false, a new contest node is added to the decision tree. This new contest will be resolved using the same tasks and the
score callback will be called with the current contest
results. Each time a contest and its inner contests choose a solution, the solution is added to the chosenSolutions array. This object is passed in the
score callback for inner contest so we can score based on current but also previous results.
Let's take this example:
contest sectionsn results chosenSolutions -> # scoring#return results0before = chosenSolutions -> cchoicefor r in resultssong = beforeconcat rchoicerscore = scoregrade songrtotal = rscore -> a+bresultssort compareresults0n chosen -> # untilreturn false if nlengthtrue
In this example,
sections are the subtrees representing the decision tree of each selected sections by the user spectrum.
The choice path of the chosen solutions is concatenated with the results of each tasks in the inner contests. If its the parent contest,
chosenSolutions is empty. Fletcher is then called with the
score.grade will give a score for each rules in the Fletcher harmony. The score array is then map reduce in order to calculate the total score for the concatenated choice path.
The winning path according to the Fletcher harmony will then be added to the chosenSolutions and this will go on until there's no more availableItems to be eaten by sections.
Let's say we have section A, B and C. The first contest will try each section A, B and C. If branching is used, they will each eat items independently. At the end of the first contest, Fletcher will evaluate the winning section. Then, if some available items are remaining in each branch, a second contest will be created. Section A, B and C will then be contested again, and they will each eat new items.
The name of this one is self-explanatory, regardless of whether the previous promise in the chain generates a positive or negative result this promise will be called. Note that the data it receives will vary.
else promise will only be called if the previous promise in the chain generated an error or aborted its choice.
finally is like
always except it will mark the current promise as final. Promises added after
finally will never be called and doing so will actually throw an exception.
contest promises are called composite promise since they are composed of sub-promises and will evaluate as one single result in the decision tree execution.
Thenable input & output
Non-composite thenables will receive
Choice is covered in a later section.
Thenable will pass the return value of a promise to the next one in the chain.
pthen 'thenName'data * 2finally 'end'consolelog data
then is delivered a value of
finally will output
A decision tree is a chain of promises. FlowerFlip allows the creation of complex decision trees by providing support for subtrees and branches.
Defining a chain of promises such as the following doesn't actually execute it.
FlowerFlip provides the
BehaviorTree module to manage the complexity of decision trees and support their execution. More on
BehaviorTree in the next section.
Root promise of the tree
FlowerFlip provide the
Root module to initialize the root promise of the decision tree. The root module does the following:
- defines on the
Choiceinstance will be used in the decision tree
- creates an instance of
BehaviorTreeand passes in the
- creates an instance of
Rootas the promise root
Execution of the decision tree
In order to execute a decision tree or subtree, some data must be delivered to it using the
t = Roottdeliver someData
someData will be passed to the first promise in the tree. This promise will return a value that will then be passed to the next one and so on. The
data parameter of promises is the only mutable object in decision trees.
BehaviorTree module supports the execution of the promise decision tree.
deliver on the root promise, the behavior tree attached to the promise will be executed calling
BehaviorTree.execute(...). A behavior tree is composed of nodes. When creating a
BehaviorTree instance a root node is created.
More than one promise can lead to a node in the tree and a node can have multiple destinations. Consider this example:
rootthen 'then0'datathen 'then1'dataelse 'else0'datathen 'then2'dataelse 'else1'data
else0 as two sources (
then1) and two destinations (
BehaviorTree will walk the promise chain to create all required sources and destinations.
When chaining a promise, a new node will be registered to the tree. The registration will get the node representing the source promise in the tree and add the current node to the
Destinations array of the source node. The source node will also be added to the
Sources collection of the current node. Doing this creates an edge between these two nodes in the tree.
If the sources promise has branches, the branches will be added as source of the current node and the current node will be added as destination. This is the reason why, if using branches outside of
contest multiple executions can occur of the promise following the branches.
What leads to a node is a choice made in the decision tree. The
Choice module is used to represent the transition from one promise to another in the
BehaviorTree. More on
Choice in the next section.
When delivering data to a tree, the data being delivered to the tree will be used to feed the
Choice.attributes object if the data is an object other than an array.
As explained in more detail in the Choice section, the behavior tree will keep track of all the decision made within the decision tree. Each node has a name and when a Choice is made, the name of that node is added to the solution path.
Let's assume all
then promises will be fulfilled in the following example:
rootthen 'then0'datathen 'then1'dataelse 'else0'datathen 'then2'dataelse 'else1'data
The execution of this tree would give the following path:
['then0', 'then1', 'then2']
If the first
then promise is rejected, and the
else is fulfilled this would give the following path:
['then0', 'else0', 'then2']
BehaviorTree module allows the creation of
Subtrees for scenarios where out of a single promise, several decisions must be taken before continuing in the main tree. Subtrees should be used in composite promise scenarios:
Subtrees are used to create decision components like the following:
=tree = choicecontinue 'layout'treedeliver datathen 'user'delse 'derived'dthend
Once the execution of the subtree is done, depending on which composite promise is used, the result of the fulfilled leaf of the subtree will be passed to the next promise in the parent tree.
This module can then be added into a decision tree easily and will take part in the execution of the root tree.
Subtrees have two modes,
tree, and are created using
Choice.continue subtrees will add the solution path of the subtree to its parent solution path.
Choice.tree subtrees will add the name of the subleaf that is fulfilled in the subtree to the parent solution path and add a child path to the solution path of the subtree.
finally with subtrees
.finally should not be called on a subtree since the subtree is part of the parent decision tree. Calling
.finally on the subtree would prevent further promise to be called.
Promises that returns promises
If a promise returns a promise, a subtree will be created using that promise as the root of the subtree.
Visualizing the tree
BehaviorTree provides the
toDOT method that will output graphviz data that can then be used in a tool like the following to generate an image of the tree: http://www.webgraphviz.com
Choice represents the decision edges between nodes for which a decision was made to transition from the source node to the destination node.
If a promise has a name, that name will be added to the
path when it is resolved. On the tree node, the path is used to identify the choice object that led to this node in the tree.
Data can be added to a choice by calling its
set method using a key-value pair. Decisions to fulfill or reject a promise can then be made in later promises using attribute values via the
get method. These properties can be used for any useful purpose.
get will look in the current choice attributes if a key exists in the
attributes object, if not, it will look at the parent source choice and so on until a matching key is found or the root choice is reached.
If the data passed to the root promise of the tree contains a property named
items, the value of the items will be added to
Choice.attributes of the root choice.
These item can be obtained using
getItem and can be eaten using
eatItem. Items can be, for example, posts from users of The Grid for their websites. For a concrete example, see the Design System section.
Once an item is eaten, it is no longer available for the current choice and its child choices. Items are immutable, meaning they will always remain in the
Choice.attributes.items object but will be filtered from the
getItem function can be passed a callback function. If no callback is received, the first item in the
availableItems collection will be returned. Otherwise, the callback function will be called for each available items. If the callback function returns a
truthy value for a given item, that item will then be returned from the
getItem function otherwise the loop will continue until there's no more available items.
Items can have blocks, which is the item content. For example, an HTML item would be composed of blocks representing the innerHTML of the item tag.
Blocks can be obtained and eaten in the same fashion as items using the
A choice can be aborted. This should only be done in subtrees used in composites. The remaining promises of the subtree will not be called. Depending on which composite promise was used, if you abort all the subtrees then the negative destination of the composite will be called.
The path of a
Choice including child paths from subtrees or branches can be obtained by calling the
toSong method. This is used by Fletcher.
Branches are used to create independent execution of a portion of the tree.
When creating a branch, the choice from which the branch is created is aborted. The branch is then registered as a destination for the source node of the aborted choice. The destination nodes of the branches are then copied from the aborted node.
A branch is created using the
The branch uses a new root
Choice that copies the attributes from the aborted node. By copying the attributes, the branch will have its own copy of available items meaning that, contrary to subtrees, two sibling branches can eat the same item.
The branch is then resolved, resulting in the execution of that branch's promises and if fulfilled, will then chain to one of its destinations.
In most cases, branches will be used within contest, since contest is the only composite that delivers only one result. If using branches in other composites, an independent execution of the entire decision tree will occur for each branch that is fulfilled.
If you do a branch within a
choice.continue subtree, the complete path of the branch decision tree will be added to the path of the parent tree.
If you do a branch within a choice.tree subtree, if the branch resolve, the name of the leaf choice of the branch will be added to the path of the parent tree and a child-path will be added to the solution to define the decision path of the branch:
path: 'parent_decision1''parent_decision2''branch_decision2''parent_decision3'child: 'branch_decision1''branch_decision2'
Since layout filters usually utilize multiple components, which in turn may utilize components of their own, it is possible for a component to receive data it didn't expect. These should be treated as programmer errors instead of failed preconditions, and handled via
thenunless itemchoiceerror'Item expected'
Design systems are used in The Grid as solvers for web page designs as well as HTML and styling rendering of the resulting web page.
FlowerFlip is the API that allows the creation of design systems. A central part of a design system is the decision tree used to make all the design decisions needed to create a web page.
A decision tree is composed of all the possible choices that can be made and it also defines how these choices relate to each other. Choices can be grouped, contests can be made, etc.
Design systems must make decisions at two main levels: page wide decision trees and section decision trees.
Design systems are used to solve the design of a page of a web site. Web pages built with The Grid are, at least at this point, composed of sections. Simple sections are rectangles that take 100% of the page's width. Sections can contain what we call Posts, Reposts and/or Components. A Post is a group of Components. Reposts represent social media posts a user "re-posts" to their website. Components represent HTML elements.
Design systems built with FlowerFlip will therefore contain a set of decisions for page wide configuration and a set of decisions for the sections. The section decisions are decomposed as Post, Repost, and Component decision trees.
Page wide decisions
Page wide decisions include but are not limited to:
- which Typography to use
- which color scheme to use (example: light colors, dark, muted + saturated, etc.)
- what kind of spectrum the user chose or the best one that fits the available content (example: informal voice, entertaining colors, use image filter, etc.)
A section is a portion of a web page. The section is composed of one or more posts. A post is some content the user sent to The Grid (image, text, video, social media post, etc.).
A post (aka: item) is composed of blocks. A block is a piece of content within the post (example: header
h1 tag, image
img tag, paragraph
p tag, etc.).
Section decisions deal with how well the available posts fit into a given section. Some examples of decisions that need to be made in a section:
- does the post contain the required block for the section?
- does the image block in the post have the characteristics needed for the given section?
- does the length of the component text fit in the section?
Integration of FlowerFlip in The Grid
Poly is using design systems as the solver for web page design. Poly is responsible for choosing the design system(s) that will be used. It's also Poly that is responsible to provide to the design system the user configuration and the available items in GOM representation.
Item = user post sent using grid-chrome or iOS app.
The design system will return the solution tree and the HTML rendered page. Poly will persist the solution tree for later analysis and comparison with later updates of the page.
Design system input
At this stage, the promise tree is built but not executed. In order to execute the tree, some data must be delivered to the root promise. The data passed in is the user's configuration and GOM representation of the user's posts (aka. items).
Here's an example of site configuration (WIP for config section):
[ config: spectrums: voice: type: -0.4 personality: colour: palette: -0.4 tone: -0.2 intensity: .3 application: .2 imageFilter: active: 1 application: .4 intensity: .4 items: [ id: '029384-234' content: [ type: 'h1' text: 'My H1' html: '<h1>My H1</h1>' , id: 'foo' type:'video', html:'<video></video>', cover: src: 'cover.jpg' orientation: 'landscape' width: 1000 height: 1000 ] ] ]
Item data in GOM
Before being processed by FlowerFlip, when a user sends a post to The Grid, this post is analyzed and some metadata is generated for it. Examples of generated metadata:
- text length
- image color palette
- saliency region in an image
FlowerFlip will receive a GOM representation of the post so the GOM object can be used to make precise and accurate design decisions.