# Progress notes of 21st July 2021 * Author: Jérémy Turi * Date: 21/07/2021 ## Introduction The Refinement Acting Engine is an acting engine first described in _Planning and Acting_ from Ghallab & Co. A first version has been developped by Sunandita in python. This version integrates a first prototype of RAE working in simulation. The select method to refine a task was using RAEPlan, UPOM or UPOM with learning capabilities. The goal of my thesis is to work from operationnal models to generates plans using planning technics, and then executes the plan. In our scenario, planning is continuously working online in parallel of the execution. Previous works exist combining both approches to maximise long-term utility and prevent deadlock \(Propice-Plan, FAPE, others?\) The first step has been to look at the state-of-the-art in term of executing engine and their languages. From this preliminary search, the choice has been made to base the RAE Description Language \(RAEDL\) on Scheme. Once the language has been defined, we used it to build RAEDL on top of it. RAEDL is used to describe domains and the environment \(as special functions and initial facts that can be asserted\). ## Todos * Describe the scheme interpreter briefly * Basic structures : LValue, LError * Core operators * How library systems works * How macros work * How to run it from the project * RAE Architecture * Main algorithm * How threads communicates \(diagram\) * TaskHandler * Async/Await system * Action Status update and check * RAEDL * Elements of description: facts, actions, tasks, methods * Functions to define the environment * Using RAE: * How to launch it, monitor * trigger a task * link with godot * What is still to be done: * check proper tail recursion \(some stack overflow to be checked, maybe caused by the construction of recursive environments\) * Implement agenda for methods * Implement error handling when a method fails and retry * Implement enumeration of applicable methods * Future work for RAE V2. * Generation of chronicles/ppdl problems/hddl problems from operationnal models to call a planner online \(aries/fape\) * STN network for actions. ## Outline * A Scheme Interpreter in Rust * Implementation and adaptation of the RAE Algorithms * RAE Description Language * Overview of the global progress ## A Scheme Interpreter in Rust Scheme is derived from the functionnal language Lisp.Peter Norvig made a tutorial to implement a basic version in Python. The Rust implementation is based on Lis.py and Lispy.py \(the second version integrates advanced features\). The main idea developping our own Scheme Interpreter is first, to better understand how an interpreter works and how Scheme works. Another good point developping our custom interpreter is that we can add special features that we want to implemented. ### A first glance at the Scheme Interpreter. A scheme interpreter is a REPL \(Read-Eval-Print-Loop\). It takes from the standard input a string, parse it to transform it into an SExpr \(or LValue in our case\) and then evaluates it in an environment. An environment contains bindings between symbols and LValues. Interpreting an expression in lisp can either returns a LValue or an LError #### LValue The _LValue_ is the basic object used in our intrepreter to represent any kind of object. In rust it is an enumeration with the following kinds: * **Number**: any kind of number. We distinquish three kinds of numbers: _Integer_, _Float_ and _Usize_. Usize is a particular type that can only be built by internal functions. * **Symbol**: A string containing a unique word * **String**: Mainly use for debugging and pass messages. * **Character**: A simple character. * **Nil**: Represent both boolean value false and the empty list * **List**: A list LValues * **Map**: A HashMap of LValues. This type is not originally in the basic structures of scheme. However it is of great interest for us to be implemented in the core functions, we added it the basic types. * **Fn**: Pointer to functions with low level computation \(i.e. here rust\). * **MutFn**: Same as Fn but it can modify objects. * **Lambda**: Lambda function that can be called using other kinds of LValues. #### LError Some errors can occurs evaluating LValues: * WrongType: Error that his raised when the wrong kind of LValue is received. ```text >> (* 3 t) LI>> error: In LValue::mul, t: Got Symbol, expected Number ``` * NotInListOfExpectedTypes: Same as wrong type, but several types could have been ok. ```text >> (length 10) LI>> error: In length, 10: Got int, expected [List, Map] ``` * WrongNumberOfArgument: The number of arguments is not in the expected range ```text >> (- 10 25 3) LI>> error: In -, "(10 25 3)": Got 3 element(s), expected 2 ``` * UndefinedSymbol: The symbol as no binding in the environment. ```text >> (set! x 10) LI>> error: In set!: x is undefined ``` * SpecialError: Special error with formatting string in function of the context. Mainly used for internal errors. Special Errors should not occur and raise a bigger programming problem that needs to be adressed. * ConversionError: Conversion Error when transforming a LValue to its inner type \(Internal Error\). Should not occur if functions are safe and type verifications are done. #### Functions Scheme has two kinds of functions. Core operators that are optimized and can mutate the environment, and pointer to functions. **Core operators** Core operators are the very basic functions present directly in the **eval** function: * **Define** : binds a symbol to a LValue ```text (define x 10); the symbol will be bound to the value x ``` * **Set**: modify the value of a symbol already defined in the environment. ```text (set! x 12); x previously bound the value 10 will now have the value 12 ``` * **If** : Basic conditional structure. Evaluates an expression that returns a boolean, executes two differents branches in function of the result. ```text >> (if (> 3 10) (+ 3 3) (* 10 5)) LI>> 50 ``` * **Begin**: Evaluates a list of expressions and return the result of the last. ```text >> (begin (define x 10) (define y 20) (+ x y)) LI>> 30 ``` * **Eval**: Explicitely evaluates an expression. ```text '(* 3 3) LI>> (* 3 3) (eval '(* 3 3)) => 9 ``` * **DefLamda**: creates a lambda expression. ```text >> (define square (lambda (x) (* x x))) ; defines a new lambda in the environment binded to symbol 'square' >> (square 5) LI >> 25 ``` There is two ways to define the arguments of a lambda. `(lambda args body)` will consider _args_ as a list of arbitrary length when `(lambda (x y) body)` will wait for two arguments that will be bound to _x_ and _y_. * **DefMacro**: defines a lambda that format lisp code ```text (defmacro cadr (lambda (x) `(car (cdr ,x)))) (cadr '(3 4)); <=> (car (cdr '(3 3))) LI >> 4 ``` * **Async** & **await**: Evaluates asynchronously an expression. Returns a pid \(usize\) of the task. The pid can be used with **await** to get the result of the evaluation. ```text >>(await (async (*3 3))) LI>> 9 ;we can split await and async to launch several async blocks and await on the results later >> (let ((x (async (* 3 3))); x is the pid of the async block (y (async (* 4 5)))); y is the pid of the async block (+ (await x) (await y))) LI>> 29 ``` * **Quote**: Prevent evaluation of the expression ```text >>(quote (*3 3)) LI>> (* 3 3) ``` * **QuasiQuote** & **UnQuote**: Creates a block in which everything is quotted except unquotted expressions: ```text >> (quasiquote (3 (+ 6 7) (unquote (- 2 1))))) LI>> (3 (+ 6 7) 1); the unquotted expression has been evaluated ``` #### Environment In Scheme, an expression is evaluated in an environment in which symbols have meaning. For example a symbol can have a value or be a function. Unless the expression is quotted, the first element of a list should be a function \(lambda, _lfn_, _lmutfn_ or _core-operator_\). * Root Environment: provides basic functions * **env**: returns the list of all elements defined in the environment * **get**: function to get an element from a list of a map \(for map objects, prefer get-map\) * **map**: constructs a map. * **list**: constructs a list. * **car**: returns the first element of a list, nil if the list is empty. ```text >>(car '(3 4 5)) LI>> 3 ``` * **cdr**: returns list without the first element, nil if the list has one element. ```text >>(cdr '(3 4 5)) LI>>(4 5) ``` * **last**: returns the last element of a list. ```text >>(cdr '(3 4 5)) LI>>5 ``` * **cons**: creates a cons of two elements ```text >> (cons 3 nil) LI>> (3) >> (cons nil 3) LI>> (nil 3) >> (cons 4 '(3)) LI>> (4 3) >> (cons '(4) '(3)) LI>> ((4) 3) ``` * **get-map**: get the value inside a map ```text >> (define m1 (map '((test . 10)))) >> (get m1) LI>> test: 10 >> (get-map m1 test) LI>> 10 ``` * **set-map**: returns a map with the new value inserted. ```text >> (define m1 (set-map m1 '(twenty . 20))) >> (get m1) LI>> twenty: 20 test: 10 ``` * basic math functions: * add \(+\) * sub \(-\) * div \(/\) * mul \(\*\) * eq \(=\) * gt \(>\) * ge \(>=\) * lt \(<\) * le \(<=\) * type verification * **lambda?** : returns true if the LValue is a lambda. * **integer?**: returns true if the LValue is an integer. * **float?**: returns true if the LValue is a float. * **nil?**: returns true if the LValue is nil. * **bool?**: returns true if the LValue is a boolean. * **symbol?**: returns true if the LValue is a symbol. * **fn?**: returns true if the LValue is a function. * **mut-fn?**: returns true if the LValue is a mutable function. * **quote?**: returns true if the LValue is a quote. * **map?**: returns true if the LValue is a map. * **list?**: returns true if the LValue is a list. * **pair?**: returns true if the LValue is a list with at least one element. All aboves functions are defined in the _root_ environment. Some macros and lambdas are also defined for syntactical sugar. * Macros: * **caar** => \(car \(car ..\)\) * **cadr** => \(car \(cdr ..\)\) * **cdar**, **cddr**, **cadar**, **caddr**, and lot others added in function of the use. * **and**, **or** and **!=** * **let** and **let\***: Used to evaluate a code with locally binded variables. The difference lies in the possibility to bind variables in function of previous bindinds with **let\*** ```text >>(let ((x 3) (y 4)) (+ x y)) LI>> 7 >>(let* ((x 3) (y (x +1))) (+ x y)) LI>> 7 ``` * **cond**: equivalent to successive _if_ _else if_ ... _else_ ```text >> (define weather (lambda (x) (cond ((< x 10) '(It is cold!)) ((< x 20) '(It is cool!)) ((< x 30) '(It is warm!)) (else '(It is hot!))))) >> (weather 10) LI>> (It is cool!) >> (weather 9) LI>> (It is cold!) >> (weather 25) LI>> (It is warm!) >> (weather 36) LI>> (It is hot!) ``` * **await-async** => `(await (async ..))` * **apply** : applies a function to a list of args ```text >> (apply + (10 6)) LI>> 16 ``` * Lambdas: * **zip**: zip elements of two lists in pairs ```text >> (zip '(1 2 3 4) '(5 6 7 8)) LI>> ((1 5) (2 6) (3 7) (4 8)) ``` * **unzip**: undo a zipped list. ```text >> (define zipped (zip '(1 2 3 4) '(5 6 7 8))) >> zipped LI>> ((1 5) (2 6) (3 7) (4 8)) >> (unzip zipped) LI>> ((1 2 3 4) (5 6 7 8)) ``` * **mapf**: maps a function to a list of argument ```text >> (mapf weather '(9 15 25 36)) LI>> ((It is cold!) (It is cool!) (It is warm!) (It is hot!)) ``` * Modules: In addition to the basic functions, we can add modules linked to a specific context that can handle special objects. * DOC: provides a unique function **help** that prints the whole help if called withour arg. Prints verbose help of symbol if called with a symbol. * IO: * **print**: print a LValue ```text >> (print test) test ``` * **read**: reads an expression from a file. ```text >>(read ) ``` * **write**: write a LValue to a file. ```text >>(write ) ``` * Math: provides advanced math functions as **sin**, **cos**, **rand-int-in-range** and **rand-float-in-range** that generate respectively a random integer and a random float from a range of number: ```text >> (rand-int-in-range 0 10) LI>> 6 >> (rand-float-in-range 0 10) LI>> 1.875527591323538 ``` * Utils: provides a bunch of utility functions: * **rand-element**: pick a random element from a list ```text >> (rand-element '(10 2 6)) LI>> 2 ``` * **enumerate**: enumerates all possible sets of combination from several lists. ```text >> (enumerate '(1 2) '(3 4) '(5 6)) LI>> ((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6)) ``` You now have a brief overview of the Scheme Interpreter. **How to run the Interpreter.** From the project you can run an executable without rae libraries loaded: ```bash cargo run --bin lisp_interpreter # to enter debug mode cargo run --bin lisp_interpreter -- -d ``` **RAE** The _Refinement Acting Engine \(RAE\)_ is based on the Algorithm first described in Ghallab, co 2016 \(Book **Acting and Planning**\). Several articles expanded the algorithm: * Refinement Planning and Acting, 2017 * Acting and Planning Using Operational Models, 2019 * Decentralized Refinement Planning and Acting, 2021 * Deliberative acting, planning and learning with hierarchical operational models, 2021 * _**TODO**_: Complete lists of State of the Art concerning RAE, APE, etc. **RAE Architecture** The executable of RAE is decomposed in several processus and asyncrhonous tasks. The following diagram gives an overview of the Architecture and how tasks are communicating, what object is shared between tasks and threads etc. * The _main_ process is the process that is launched with the command `cargo run`, i.e. _unnamed\_superviser_. At initialisation it launches a repl that communicates via a channel with the Scheme Interpreter task. This task _await_ on a channel to receive raw \(str\) Scheme expression, that will be parsed, expanded and evaluated. The result is then sent back to the REPL to be printed on stdout. Other processes can call the Scheme Interpreter to Evaluate Expressions. However the return of the value is only available for the REPL Task \(To be implemented later if future case need this feature...\) * The task RAE is launched via the REPL with the command `(rae-launch)`. It will successively launch _rae\_main_ and the platform. In our case _godot3_ via command line loaded with an hardcoded scenario and options. The platform godot then opens a tcp connection to receive state updates and action status updates. * The objects RAEState and Status are shared between the different tasks \(using _Arc_\). ![REA executable architecture](../.gitbook/assets/architecture.png) **Main algorithm** The main algorithm of rae receives job via a channel. A job is lisp code that will be evaluated in RAE environment. Here is a simple view of how RAE works. It has been extremly simplified in its main algorithms as most of the reasoning part is done during evaluation and in **RAEExec** context. ```text rae_main(context: RAEEnv) loop: new_job <- job_receiver spawn(progress(new_job, RAEEnv.env)) end progress(job: Job, env: LEnv) eval(job, env) ``` **TaskHandler** The TaskHandler is a simple way that I found to stop all tokio tasks spawned that are looping during the whole process lifetime. In the REPL, when it receives a _CTRL-C_ entry, it calls `task_handler::end_all()`. Every task can get the end signal by calling `task_handler::subscribe_new_task`. It returns a broadcast receiver. Here is one example of how to use it. We recommand to use `tokio::select!` has it awaits concurently several futures and executes the code of the first received future. In this example it loops and awaits on two futures given by `receiver.recv()` that awaits on messages to send to godot, and `end_receiver.recv()` that awaits on a message from the task\_handler. If the task\_handler broadcast the end message, the task breaks it main loop and end the task process by ending the function. ```rust let mut end_receiver = task_handler::subscribe_new_task(); loop { tokio::select! { command = receiver.recv() => { let command = match command { None => break, Some(s) => s }; //println!("new command to send: {}", command); let size = u32_to_u8_array(command.len() as u32); let msg: &[u8] = &[&size[0..4], &command.as_bytes()].concat(); match stream.write_all(msg).await { Ok(_) => {} Err(_) => panic!("error sending via socket"), } } _ = end_receiver.recv() => { println!("godot sender task ended"); break; } } } ``` **Executing commands in RAE** In RAE, the goal of the engine is to find methods to refine a task. Once the methods has been found, it will be executed. The body of a method is an operationnal model that contains richer control structures than descriptive models. To execute a command in RAE. There is two functions: * `(rae-exec-platform