Tree matchings with Behavior Trees
Auroux, Lionel
Any python data structure could be seen as a big tree of related objects. Would it be useful for you to recognize in this big tree some specific form? Recognizing of subtrees is really a common aim in compilers implementation. But it's not an easy task. I recently found that I could easily use behavior trees to do such things. However this kind of techniques could be useful in other situation. This talk want to popularize this technique by explaining how behavior trees work in common way, how to adapt then for a bottom-up tree matching algorithm. For instance, some HTML parser provide CSS Selector function to match one node at the time optionally related to some ancestor. Here, with this kind of matching algorithm you could match many nodes in only one pass. I create on my github a "treematching" module that use this algorithm to provide an Embedded DSL to write patterns, match any python data structure and in some case, allow you to do tree rewriting.
 Okay, hi. I'm Lionel and I'm going to talk about tree matching with Bay of your trees. So the aim of this presentation is to explain how to organize sub-trees into complex and deep trees of data. It is related to Python but you could use these techniques in any language that supports reflexivity. So we are going to speak about Bay of your trees and to define it. And so after that I will try to explain why we need tree matching and in common use case for using tree matching. And during all the presentation I put some code to explain how to do all these stuff. So what is a Bay of your tree? A Bay of your tree in fact is basically a diagram or schema that represents a process that describes a different task. It's useful and very used in video games. For example to describe the artificial intelligence of a boat, or the behavior of the boat. For example here I could explain a boat in the game that crossed the door. So I begin to describe with our symbol a sequence of tasks to be executed. So I begin to say to my boat begin to work to the door. And this task could be used a pathfinder algorithm to find where the door is. For example after that do a complex sub-trees that is described by a question mark. A question mark is another abstraction provided by Bay of your tree. The arrow symbol means sequences. But the question mark in fact is called selector. A selector on Bay of your tree is a list of tasks. But we try each one and the first that's that's be okay is all the subtree is okay. So I will try to open the door but this task could be failed. This task could be failed because I need a key to open the door. So I will continue and go to another sequences that will try to unlock the door and finally open it. But could be in the task unlock the door. I will check that I have the correct key for the door. But could be I don't get the correct key. So all this stuff could be failed. So finally I could just smash the door and after all this possibility task I will work through the door. So from this diagram I describe a complex process with a lot of steps. The three main components that I use is the task. This is a simple abstraction to say okay do something. This is very easy to understand in programming language because it's just a method name. But behind this task you will check your context of the environment of your video game basically to know if the task is doable or any context you want to test. After that I have the sequence so the arrow symbol that it just do the next task if the previous task succeed. And the selector this is in fact like the or the boolean or because in fact it is do the next if the previous task fail. So in the selector I don't do the task. I don't do all the task because I just do only task that say okay or fail and I stop to do task if at the first succeeded task. Okay. This is I show you the representation of the BVR tree as a diagram. Now I will explain BVR tree as a piece of code. The main part of BVR tree we will describe task. So I create a class task and at each step of my process I will call a method that's named tick. A tick is related to time in the video game but in our application or problem here tree matching the tick will be something else. But the important things that this method tick do something and return the status of the task done. But the status is not just a boolean function fail or success is a special enum with failure, success and running. So the first part is a task could say okay I didn't finish so just say running. So you need to test me again in the next tick. So after define the classical blocks the task I will create nodes and also define the nodes and the roots of my tree. So I need to create a tree and each node and roots of tree is related to child. So when you recreate a tick method for a tree element or task I will be related to my parents and to my child because with this block I could be inside the tree and the task block is a leaf so I did not relate to anybody. With this I could define my famous symbol so the sequence. So the sequence the tick method in the sequence could take user data and return the status but in fact is related to child so for each child I just call tick on the child with the context and get this status and I will handle this status as a task. So if my status is running I'm also running so recursively from the leaf that say running all my better tick could say okay I didn't decide what I've done. If I fail I stop and all the sequences fail and if I could check all my child the sequence is a success. So in return success. After the sequence we have selectors so the selector is like or so in fact we try old child we check the status like sequence if the sub task is running I'm also say running but if sub task success I stop and say success and if all my child fail I'm fail too. With all that we have just three basic blocks but we could imagine another blocks so if I understand the concept of any part of my better tree could say fail success or running I could create for example a concurrent block a concurrent block that will propose to test each child concurrently so I could in the opposite new position of selector or selector just run a test and call tick and each child in order but here I will call tick in each in any child so I will enumerate my child store in the statu list all status of all my child when if all my child run as finished I did not also so the I don't have a task still running all my child could be fail or failure but never running I could check I need only one success to say I'm successful if I didn't have only one success I fail my concurrent test my concurrent block say fail and if I still a running task inside inside my child I'm still running so with this kind of abstraction I could in a synchronous way manage asynchronous processes not notably with the concurrent abstraction so this is the presentation for the concept of behavior trees and now how to use it in a precise use case that is tree matching tree matching in fact it comes at any moment where you need to do some data validation you have a complex data representation inside your application and you need to identify inside this big data tree some form and validate that is correct or incorrect you could use tree matching when you want to do some data transformation because you want to match some form and rewrite inside your tree is only this kind of data and more generally you always need tree matching when you want to do some data generation because you have a first data tree that you will traverse in notifying some some some things and cool some other method that creates another tip of data so you will have a depth first data tree that generates a second data tree and in fact all these use case are in fact inside a compiler when you want to identify some pattern in in your bigger data tree this is a semantic check because the semantic the meaning of what you write in your language represent into an ICT in fact is a good construction good tree construction all ICT transformation could be done with tree matching and at the end code generation is basically tree matching all this stuff in fact are already done in with functional language like a scale or another language that supports pattern matching pattern matching is a statement a powerful statement in this kind of language because you you could easily match a partially a subtree a tree and partially a subtree to basically do a tree tree only you begin to write a recursive function that traverse all your tree in top down way and use a pattern matching to identify not deconstruct it and do something with it and call some piece of code this could be useful for a major part of your of your stuff but when you want to do some tree reconstruction to to identify some part of code some part of the data and rewriting you are not in this in the good way you are you can't match in a top down way because you begin to to match roots before leaf so you can't rewrite leaf this is this is finished so you if you want to do some tree reconstruction you need to match it or identify your tree in a bottom up way and if you have more complex pattern matching that are deepest from only one level because you want to to match an ancestor and a child deep deep at a two or three level because you want to to check a special construction inside a statement for a language and other stuff like that basically pattern matching is not enough so for all this kind of stuff I think about behavior trees and I have an entretient to to to test that is okay behavior tree is a sub us certain way to do a finite state machine but in academic definition a behavior tree is called like it's like a year-old machine this is a kind of automata more adaptable and more versatile that the basic finite state machine you don't have explosion of states you will you have a good a lot of good properties so I try to use this this kind of new way to do to describe automata behavior trees to identify the and to do the tree matching the main idea is to have a work method that allows to traverse our data tree in the correct order so bottom up and to notify all our behavior tree and the other good parts it is that a behavior theory it's a good representation and mimic a pattern for example I will I will describe for my tree matching module I will describe the pattern of tree and this pattern is easily transformed into behavior tree using the concurrent abstraction so for example here this is like a generic representation of pattern matching with data structure in python I begin to match a value if this value is the correct types if these value types it's inside the attribute name if this is okay concurrently I could match other parts of those things that could be exist inside the data pattern data tree and with all this I could easily quite easily describe translate my my pattern into a behavior tree and it's also versatile because my needs is to do traversal in bottom up to allow reconstruction but in fact if you change some inverse some line of code you have again a top down a top down matter so it's completely versatile you could use it in both both way so let's create a generic python tree I create a class I just do a mapping of k words parameters inside my my attributes so with my class I could simulate any class with attributes I create also something related to a dictionary to simulate the things that you could also match a dictionary to match a key or the value part of a dictionary the same thing for list and this is this could be a data tree or a small part of a data tree that represents our our challenge so I could have an attribute I could have an attribute and a list inside the list I could have a dictionary a thing like that and to handle this kind of of that that tree I need to to to rely to the basic reflection mechanism of python with vars and get a tear to iterate through attributes and some some types of collections module like mapping and it terrible to know if my my object is like a dictionary or is like a list and use yield and yield from because my work my work my traversal function will be you will be used in as a generator and my my work traversal function is also recursive so I will send notification through a yield statement but my my function is recursive so my recursion you must be yield from if you understand the previous presentation you understand why you use yield from here okay this is a generate pattern of a universal working function that iterates for any tree in python I'll hide some data here the the big big step is to identify what kind of tree I I traverse so my tree is it related to mapping or any terrible and at the end I directly iterate through common attributes at each part I yield from recursively my work function into the child so this this piece of code the iterates any data tree and at each I then port in fact I do notification I do notification to yield okay now I have matching a value this is a value of the data I have I have much I have matching your type this is what type this is the name of the tree this is the name of the key this is the index of the list with all these information I could send it to a behavior tree that compose and do pattern matching and with this I could identify a value or any value type a component attribute a list or dictionary list attributes etc so with all this stuff I have one pattern one subtree identified but I need to to do some more smart stuff because you could have a tree inside trees thing like that so I need just to identify a signal tree but a forest so to identify forest in fact one pattern is correctly one behavior tree but in fact I do and concurrent pattern be and behavior trees with the concurrent abstraction when I I work and traverse my tree I I be I must be aware of the storing of status and positioning inside my tree so I can't store it inside the behavior tree because the behavior tree represents the pattern not the actually partially identified sequence so I need to create another store store to store this sub-element so my self that status but my privacy self that status that allow me to store the current status of a behavior tree are now stored in the user data user data it's another parameter provided to the behavior tree so you you have the behavior tree that you that identify that represent the structure of the pattern and all the data and current element is defined by another structure and you need also to clean because you begin to to to identify with your behavior trees and sometimes behavior trees fails so you need to clean up during the traversal of trees to to be aware when correct sequence are reached. Okay I took all this and I put in on the module to a cold tree matching on my heat up soon I will distribute it in a paper. Basically you could use a bunch of class that allow you to describe pattern in fact it was a number that they sell through the Python classes so you could have for example match any type with the class any type early list with at any index I want a tip a star with this value etc etc I could describe attribute and precisely this attribute I want a full of tip int for any value I don't care I put it I describe my pattern as as as a on computation of data of class instantiation I send it to my bare matching battery and after that I use a match method on my data tree and the stuff are done. You could manage all these things you could capture nodes and call back function after some cleaning and bugging I need to write some documentation after all that I could send the module on pipe. Okay I don't think we have a question see no one question one question any question no okay thank you.
 Okay, hi. I'm Lionel and I'm going to talk about tree matching with Bay of your trees.  So the aim of this presentation is to explain how to organize sub-trees into complex and  deep trees of data. It is related to Python but you could use these techniques in any  language that supports reflexivity. So we are going to speak about Bay of your trees  and to define it. And so after that I will try to explain why we need tree matching and  in common use case for using tree matching. And during all the presentation I put some  code to explain how to do all these stuff. So what is a Bay of your tree? A Bay of your  tree in fact is basically a diagram or schema that represents a process that describes a  different task. It's useful and very used in video games. For example to describe the  artificial intelligence of a boat, or the behavior of the boat. For example here I could  explain a boat in the game that crossed the door. So I begin to describe with our symbol  a sequence of tasks to be executed. So I begin to say to my boat begin to work to the door.  And this task could be used a pathfinder algorithm to find where the door is. For example after  that do a complex sub-trees that is described by a question mark. A question mark is another  abstraction provided by Bay of your tree. The arrow symbol means sequences. But the question  mark in fact is called selector. A selector on Bay of your tree is a list of tasks. But  we try each one and the first that's that's be okay is all the subtree is okay. So I will  try to open the door but this task could be failed. This task could be failed because I  need a key to open the door. So I will continue and go to another sequences that will try  to unlock the door and finally open it. But could be in the task unlock the door. I will  check that I have the correct key for the door. But could be I don't get the correct  key. So all this stuff could be failed. So finally I could just smash the door and after  all this possibility task I will work through the door. So from this diagram I describe  a complex process with a lot of steps. The three main components that I use is the task.  This is a simple abstraction to say okay do something. This is very easy to understand  in programming language because it's just a method name. But behind this task you will  check your context of the environment of your video game basically to know if the task is  doable or any context you want to test. After that I have the sequence so the arrow symbol  that it just do the next task if the previous task succeed. And the selector this is in  fact like the or the boolean or because in fact it is do the next if the previous task  fail. So in the selector I don't do the task. I don't do all the task because I just do  only task that say okay or fail and I stop to do task if at the first succeeded task.  Okay. This is I show you the representation of the BVR tree as a diagram. Now I will  explain BVR tree as a piece of code. The main part of BVR tree we will describe task.  So I create a class task and at each step of my process I will call a method that's  named tick. A tick is related to time in the video game but in our application or problem  here tree matching the tick will be something else. But the important things that this method  tick do something and return the status of the task done. But the status is not just  a boolean function fail or success is a special enum with failure, success and running. So  the first part is a task could say okay I didn't finish so just say running. So you need  to test me again in the next tick. So after define the classical blocks the task I will  create nodes and also define the nodes and the roots of my tree. So I need to create  a tree and each node and roots of tree is related to child. So when you recreate a tick  method for a tree element or task I will be related to my parents and to my child because  with this block I could be inside the tree and the task block is a leaf so I did not  relate to anybody. With this I could define my famous symbol so the sequence. So the  sequence the tick method in the sequence could take user data and return the status  but in fact is related to child so for each child I just call tick on the child with the  context and get this status and I will handle this status as a task. So if my status is  running I'm also running so recursively from the leaf that say running all my better  tick could say okay I didn't decide what I've done. If I fail I stop and all the sequences  fail and if I could check all my child the sequence is a success. So in return success.  After the sequence we have selectors so the selector is like or so in fact we try old  child we check the status like sequence if the sub task is running I'm also say running  but if sub task success I stop and say success and if all my child fail I'm fail too. With  all that we have just three basic blocks but we could imagine another blocks so if I understand  the concept of any part of my better tree could say fail success or running I could create  for example a concurrent block a concurrent block that will propose to test each child  concurrently so I could in the opposite new position of selector or selector just run  a test and call tick and each child in order but here I will call tick in each in any child  so I will enumerate my child store in the statu list all status of all my child when  if all my child run as finished I did not also so the I don't have a task still running  all my child could be fail or failure but never running I could check I need only one  success to say I'm successful if I didn't have only one success I fail my concurrent  test my concurrent block say fail and if I still a running task inside inside my child  I'm still running so with this kind of abstraction I could in a synchronous way manage asynchronous  processes not notably with the concurrent abstraction so this is the presentation for the concept  of behavior trees and now how to use it in a precise use case that is tree matching tree  matching in fact it comes at any moment where you need to do some data validation you have  a complex data representation inside your application and you need to identify inside  this big data tree some form and validate that is correct or incorrect you could use  tree matching when you want to do some data transformation because you want to match some  form and rewrite inside your tree is only this kind of data and more generally you always  need tree matching when you want to do some data generation because you have a first data  tree that you will traverse in notifying some some some things and cool some other method  that creates another tip of data so you will have a depth first data tree that generates  a second data tree and in fact all these use case are in fact inside a compiler when you  want to identify some pattern in in your bigger data tree this is a semantic check because  the semantic the meaning of what you write in your language represent into an ICT in fact  is a good construction good tree construction all ICT transformation could be done with  tree matching and at the end code generation is basically tree matching all this stuff  in fact are already done in with functional language like a scale or another language  that supports pattern matching pattern matching is a statement a powerful statement in this  kind of language because you you could easily match a partially a subtree a tree and partially  a subtree to basically do a tree tree only you begin to write a recursive function that  traverse all your tree in top down way and use a pattern matching to identify not deconstruct  it and do something with it and call some piece of code this could be useful for a major  part of your of your stuff but when you want to do some tree reconstruction to to identify  some part of code some part of the data and rewriting you are not in this in the good  way you are you can't match in a top down way because you begin to to match roots before  leaf so you can't rewrite leaf this is this is finished so you if you want to do some  tree reconstruction you need to match it or identify your tree in a bottom up way and  if you have more complex pattern matching that are deepest from only one level because  you want to to match an ancestor and a child deep deep at a two or three level because you  want to to check a special construction inside a statement for a language and other stuff  like that basically pattern matching is not enough so for all this kind of stuff I think  about behavior trees and I have an entretient to to to test that is okay behavior tree is  a sub us certain way to do a finite state machine but in academic definition a behavior  tree is called like it's like a year-old machine this is a kind of automata more adaptable  and more versatile that the basic finite state machine you don't have explosion of states  you will you have a good a lot of good properties so I try to use this this kind of new way  to do to describe automata behavior trees to identify the and to do the tree matching  the main idea is to have a work method that allows to traverse our data tree in the correct  order so bottom up and to notify all our behavior tree and the other good parts it is that a  behavior theory it's a good representation and mimic a pattern for example I will I will  describe for my tree matching module I will describe the pattern of tree and this pattern  is easily transformed into behavior tree using the concurrent abstraction so for example  here this is like a generic representation of pattern matching with data structure in  python I begin to match a value if this value is the correct types if these value types  it's inside the attribute name if this is okay concurrently I could match other parts  of those things that could be exist inside the data pattern data tree and with all this  I could easily quite easily describe translate my my pattern into a behavior tree and it's  also versatile because my needs is to do traversal in bottom up to allow reconstruction but in  fact if you change some inverse some line of code you have again a top down a top down  matter so it's completely versatile you could use it in both both way so let's create a  generic python tree I create a class I just do a mapping of k words parameters inside  my my attributes so with my class I could simulate any class with attributes I create  also something related to a dictionary to simulate the things that you could also match  a dictionary to match a key or the value part of a dictionary the same thing for list and  this is this could be a data tree or a small part of a data tree that represents our our  challenge so I could have an attribute I could have an attribute and a list inside the list  I could have a dictionary a thing like that and to handle this kind of of that that tree  I need to to to rely to the basic reflection mechanism of python with vars and get a tear  to iterate through attributes and some some types of collections module like mapping and  it terrible to know if my my object is like a dictionary or is like a list and use yield  and yield from because my work my work my traversal function will be you will be used  in as a generator and my my work traversal function is also recursive so I will send  notification through a yield statement but my my function is recursive so my recursion  you must be yield from if you understand the previous presentation you understand why you  use yield from here okay this is a generate pattern of a universal working function that  iterates for any tree in python I'll hide some data here the the big big step is to identify  what kind of tree I I traverse so my tree is it related to mapping or any terrible and  at the end I directly iterate through common attributes at each part I yield from recursively  my work function into the child so this this piece of code the iterates any data tree and  at each I then port in fact I do notification I do notification to yield okay now I have  matching a value this is a value of the data I have I have much I have matching your type  this is what type this is the name of the tree this is the name of the key this is the  index of the list with all these information I could send it to a behavior tree that compose  and do pattern matching and with this I could identify a value or any value type a component  attribute a list or dictionary list attributes etc so with all this stuff I have one pattern  one subtree identified but I need to to do some more smart stuff because you could have  a tree inside trees thing like that so I need just to identify a signal tree but a forest  so to identify forest in fact one pattern is correctly one behavior tree but in fact  I do and concurrent pattern be and behavior trees with the concurrent abstraction when  I I work and traverse my tree I I be I must be aware of the storing of status and positioning  inside my tree so I can't store it inside the behavior tree because the behavior tree  represents the pattern not the actually partially identified sequence so I need to create another  store store to store this sub-element so my self that status but my privacy self that  status that allow me to store the current status of a behavior tree are now stored in  the user data user data it's another parameter provided to the behavior tree so you you have  the behavior tree that you that identify that represent the structure of the pattern and  all the data and current element is defined by another structure and you need also to  clean because you begin to to to identify with your behavior trees and sometimes behavior  trees fails so you need to clean up during the traversal of trees to to be aware when  correct sequence are reached.  Okay I took all this and I put in on the module to a cold tree matching on my heat up soon  I will distribute it in a paper. Basically you could use a bunch of class that allow  you to describe pattern in fact it was a number that they sell through the Python classes  so you could have for example match any type with the class any type early list with at  any index I want a tip a star with this value etc etc I could describe attribute and precisely  this attribute I want a full of tip int for any value I don't care I put it I describe  my pattern as as as a on computation of data of class instantiation I send it to my bare  matching battery and after that I use a match method on my data tree and the stuff are done.  You could manage all these things you could capture nodes and call back function after  some cleaning and bugging I need to write some documentation after all that I could  send the module on pipe. Okay I don't think we have a question see no one question one  question any question no okay thank you.
Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_0_167.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_168_347.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_348_851.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_852_1487.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_1488_5411.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_5412_7571.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_7572_7691.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_7692_7871.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_7872_10811.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_10812_13115.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_13116_13187.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_13188_13559.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_13560_14999.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_15000_16475.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_16476_19187.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_19188_22799.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_22800_24587.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_24588_27107.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_27108_28091.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_28092_28571.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_28572_30167.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_30168_31463.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_31464_31727.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_31728_31775.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_31776_32315.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_32316_32615.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_32616_33143.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_33144_35879.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_35880_37727.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_37728_38471.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38472_38519.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38520_38615.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38616_38675.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38676_38723.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38724_38771.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38772_38819.png Tree_matchings_with_Behavior_Trees_How_to_recognize_a_complex_38820_38979.png
Okay, hi. I'm Lionel and I'm going to talk about tree matching with Bay of your trees. So the aim of this presentation is to explain how to organize sub-trees into complex and deep trees of data. It is related to Python but you could use these techniques in any language that supports reflexivity. So we are going to speak about Bay of your trees and to define it. And so after that I will try to explain why we need tree matching and in common use case for using tree matching. And during all the presentation I put some code to explain how to do all these stuff. So what is a Bay of your tree? A Bay of your tree in fact is basically a diagram or schema that represents a process that describes a different task. It's useful and very used in video games. For example to describe the artificial intelligence of a boat, or the behavior of the boat. For example here I could explain a boat in the game that crossed the door. So I begin to describe with our symbol a sequence of tasks to be executed. So I begin to say to my boat begin to work to the door. And this task could be used a pathfinder algorithm to find where the door is. For example after that do a complex sub-trees that is described by a question mark. A question mark is another abstraction provided by Bay of your tree. The arrow symbol means sequences. But the question mark in fact is called selector. A selector on Bay of your tree is a list of tasks. But we try each one and the first that's that's be okay is all the subtree is okay. So I will try to open the door but this task could be failed. This task could be failed because I need a key to open the door. So I will continue and go to another sequences that will try to unlock the door and finally open it. But could be in the task unlock the door. I will check that I have the correct key for the door. But could be I don't get the correct key. So all this stuff could be failed. So finally I could just smash the door and after all this possibility task I will work through the door. So from this diagram I describe a complex process with a lot of steps. The three main components that I use is the task. This is a simple abstraction to say okay do something. This is very easy to understand in programming language because it's just a method name. But behind this task you will check your context of the environment of your video game basically to know if the task is doable or any context you want to test. After that I have the sequence so the arrow symbol that it just do the next task if the previous task succeed. And the selector this is in fact like the or the boolean or because in fact it is do the next if the previous task fail. So in the selector I don't do the task. I don't do all the task because I just do only task that say okay or fail and I stop to do task if at the first succeeded task. Okay. This is I show you the representation of the BVR tree as a diagram. Now I will explain BVR tree as a piece of code. The main part of BVR tree we will describe task. So I create a class task and at each step of my process I will call a method that's named tick. A tick is related to time in the video game but in our application or problem here tree matching the tick will be something else. But the important things that this method tick do something and return the status of the task done. But the status is not just a boolean function fail or success is a special enum with failure, success and running. So the first part is a task could say okay I didn't finish so just say running. So you need to test me again in the next tick. So after define the classical blocks the task I will create nodes and also define the nodes and the roots of my tree. So I need to create a tree and each node and roots of tree is related to child. So when you recreate a tick method for a tree element or task I will be related to my parents and to my child because with this block I could be inside the tree and the task block is a leaf so I did not relate to anybody. With this I could define my famous symbol so the sequence. So the sequence the tick method in the sequence could take user data and return the status but in fact is related to child so for each child I just call tick on the child with the context and get this status and I will handle this status as a task. So if my status is running I'm also running so recursively from the leaf that say running all my better tick could say okay I didn't decide what I've done. If I fail I stop and all the sequences fail and if I could check all my child the sequence is a success. So in return success. After the sequence we have selectors so the selector is like or so in fact we try old child we check the status like sequence if the sub task is running I'm also say running but if sub task success I stop and say success and if all my child fail I'm fail too. With all that we have just three basic blocks but we could imagine another blocks so if I understand the concept of any part of my better tree could say fail success or running I could create for example a concurrent block a concurrent block that will propose to test each child concurrently so I could in the opposite new position of selector or selector just run a test and call tick and each child in order but here I will call tick in each in any child so I will enumerate my child store in the statu list all status of all my child when if all my child run as finished I did not also so the I don't have a task still running all my child could be fail or failure but never running I could check I need only one success to say I'm successful if I didn't have only one success I fail my concurrent test my concurrent block say fail and if I still a running task inside inside my child I'm still running so with this kind of abstraction I could in a synchronous way manage asynchronous processes not notably with the concurrent abstraction so this is the presentation for the concept of behavior trees and now how to use it in a precise use case that is tree matching tree matching in fact it comes at any moment where you need to do some data validation you have a complex data representation inside your application and you need to identify inside this big data tree some form and validate that is correct or incorrect you could use tree matching when you want to do some data transformation because you want to match some form and rewrite inside your tree is only this kind of data and more generally you always need tree matching when you want to do some data generation because you have a first data tree that you will traverse in notifying some some some things and cool some other method that creates another tip of data so you will have a depth first data tree that generates a second data tree and in fact all these use case are in fact inside a compiler when you want to identify some pattern in in your bigger data tree this is a semantic check because the semantic the meaning of what you write in your language represent into an ICT in fact is a good construction good tree construction all ICT transformation could be done with tree matching and at the end code generation is basically tree matching all this stuff in fact are already done in with functional language like a scale or another language that supports pattern matching pattern matching is a statement a powerful statement in this kind of language because you you could easily match a partially a subtree a tree and partially a subtree to basically do a tree tree only you begin to write a recursive function that traverse all your tree in top down way and use a pattern matching to identify not deconstruct it and do something with it and call some piece of code this could be useful for a major part of your of your stuff but when you want to do some tree reconstruction to to identify some part of code some part of the data and rewriting you are not in this in the good way you are you can't match in a top down way because you begin to to match roots before leaf so you can't rewrite leaf this is this is finished so you if you want to do some tree reconstruction you need to match it or identify your tree in a bottom up way and if you have more complex pattern matching that are deepest from only one level because you want to to match an ancestor and a child deep deep at a two or three level because you want to to check a special construction inside a statement for a language and other stuff like that basically pattern matching is not enough so for all this kind of stuff I think about behavior trees and I have an entretient to to to test that is okay behavior tree is a sub us certain way to do a finite state machine but in academic definition a behavior tree is called like it's like a year-old machine this is a kind of automata more adaptable and more versatile that the basic finite state machine you don't have explosion of states you will you have a good a lot of good properties so I try to use this this kind of new way to do to describe automata behavior trees to identify the and to do the tree matching the main idea is to have a work method that allows to traverse our data tree in the correct order so bottom up and to notify all our behavior tree and the other good parts it is that a behavior theory it's a good representation and mimic a pattern for example I will I will describe for my tree matching module I will describe the pattern of tree and this pattern is easily transformed into behavior tree using the concurrent abstraction so for example here this is like a generic representation of pattern matching with data structure in python I begin to match a value if this value is the correct types if these value types it's inside the attribute name if this is okay concurrently I could match other parts of those things that could be exist inside the data pattern data tree and with all this I could easily quite easily describe translate my my pattern into a behavior tree and it's also versatile because my needs is to do traversal in bottom up to allow reconstruction but in fact if you change some inverse some line of code you have again a top down a top down matter so it's completely versatile you could use it in both both way so let's create a generic python tree I create a class I just do a mapping of k words parameters inside my my attributes so with my class I could simulate any class with attributes I create also something related to a dictionary to simulate the things that you could also match a dictionary to match a key or the value part of a dictionary the same thing for list and this is this could be a data tree or a small part of a data tree that represents our our challenge so I could have an attribute I could have an attribute and a list inside the list I could have a dictionary a thing like that and to handle this kind of of that that tree I need to to to rely to the basic reflection mechanism of python with vars and get a tear to iterate through attributes and some some types of collections module like mapping and it terrible to know if my my object is like a dictionary or is like a list and use yield and yield from because my work my work my traversal function will be you will be used in as a generator and my my work traversal function is also recursive so I will send notification through a yield statement but my my function is recursive so my recursion you must be yield from if you understand the previous presentation you understand why you use yield from here okay this is a generate pattern of a universal working function that iterates for any tree in python I'll hide some data here the the big big step is to identify what kind of tree I I traverse so my tree is it related to mapping or any terrible and at the end I directly iterate through common attributes at each part I yield from recursively my work function into the child so this this piece of code the iterates any data tree and at each I then port in fact I do notification I do notification to yield okay now I have matching a value this is a value of the data I have I have much I have matching your type this is what type this is the name of the tree this is the name of the key this is the index of the list with all these information I could send it to a behavior tree that compose and do pattern matching and with this I could identify a value or any value type a component attribute a list or dictionary list attributes etc so with all this stuff I have one pattern one subtree identified but I need to to do some more smart stuff because you could have a tree inside trees thing like that so I need just to identify a signal tree but a forest so to identify forest in fact one pattern is correctly one behavior tree but in fact I do and concurrent pattern be and behavior trees with the concurrent abstraction when I I work and traverse my tree I I be I must be aware of the storing of status and positioning inside my tree so I can't store it inside the behavior tree because the behavior tree represents the pattern not the actually partially identified sequence so I need to create another store store to store this sub-element so my self that status but my privacy self that status that allow me to store the current status of a behavior tree are now stored in the user data user data it's another parameter provided to the behavior tree so you you have the behavior tree that you that identify that represent the structure of the pattern and all the data and current element is defined by another structure and you need also to clean because you begin to to to identify with your behavior trees and sometimes behavior trees fails so you need to clean up during the traversal of trees to to be aware when correct sequence are reached. Okay I took all this and I put in on the module to a cold tree matching on my heat up soon I will distribute it in a paper. Basically you could use a bunch of class that allow you to describe pattern in fact it was a number that they sell through the Python classes so you could have for example match any type with the class any type early list with at any index I want a tip a star with this value etc etc I could describe attribute and precisely this attribute I want a full of tip int for any value I don't care I put it I describe my pattern as as as a on computation of data of class instantiation I send it to my bare matching battery and after that I use a match method on my data tree and the stuff are done. You could manage all these things you could capture nodes and call back function after some cleaning and bugging I need to write some documentation after all that I could send the module on pipe. Okay I don't think we have a question see no one question one question any question no okay thank you.
and in common use case for using tree matching. algorithm to find where the door is. For example something. This is very easy to understand in else. But the important things that this method the task I will create nodes and also define the with this block I could be inside the tree and concept of behavior trees and now how to use it big data tree some form and validate that is you could easily match a partially a subtree a tree tree only you begin to write a recursive some piece of code this could be useful for a and rewriting you are not in this in the good way pattern matching that are deepest from only one level because you want to to match an ancestor I try to use this this kind of new way to do to matching module I will describe the pattern of I create also something related to a dictionary function that iterates for any tree in python piece of code the iterates any data tree and at could use a bunch of class that allow you to I put it I describe my pattern as as as a on