I was thinking about how to implement a “Puppy is following me” behavior for a while now.
If I break down my puppy’s imagined behavior as shown in the State Diagram above, I can just about envision a complete system to implement it in my Robot and Java program, which will allow on-the-fly specification of that behavior with no recompilation required for either program.
Update 5/11/17:
Back to Updates List...
I completed implementation of the Assembler and RVM back in March.
They are both written in C++ and run in the Robot.
Update 5/11/17
Update 6/5/17
Update 9/1/17
Update 9/24/17
Update 9/29/17
Update 10/5/17
Update 10/28/17
Puppy Algorithm Description
I am now 65% finished with implementing the Compiler in my Robot's
Java Program. Below is a current Compiler screenshot.
The panes that the Compiler displays are:
End Update.
Update 6/5/17:
Back to Updates List...
Below is my current test program being compiled, with colors added
to identify each category of Token parsed by the Tokenization
process. Somewhat elaborate expressions are used to more thoroughly
exercise the Compiler, which marks detected compiler errors
in bright Red (not shown here):
On the left side below is the Grammar Tree. This is
parsed from the standard C-language BNF Grammar Rules.
On the right side below is a portion of the Syntax Tree created
by connecting together the Tokens above.
The generated Tokens are connected to according to
the grammar rules specified in the Grammar Tree,
giving the syntax tree shown on the right.
When/if the syntax tree construction reaches the root node
of the C-language grammar rule tree, the user's program can
then be declared to be "syntactically correct".
Following that, Assembly language statements can be generated from syntax
tree and sent to the Robot to be executed.
Multiple user programs run in parallel in the Robot that respond
to sensor input changes from the external environment.
The programs compete and blend their commands, to give layered
and prioritized control signals to the Robot, so it can
gracefully respond to a variety of competing goals, as shown in the
example State Diagram at the top of this page.
End Update.
Update 9/1/17: Back to Updates List...
I am now 85% finished with implementing the Compiler in my Robot's Java
Program.
When the Java program first starts up, it reads the usual Backus-Naur
Form (BNF) Grammar for the C language from a file, of which the first
few lines are:
<translation-unit> ::= {<external-declaration>}*
<external-declaration> ::= <function-definition> | <declaration>
<function-definition> ::=
{<declaration-specifier>}* <declarator>
{<declaration>}* <compound-statement>
The program checks for the existence of a second file which contains
a human-readable serialized version of this Grammar info, and creates
it if not found.
This serialization adds a "_"-prefix to each Grammar node, where "x"'s
can be entered to indicate that a particular node (and all its
dependencies, both up and down the graph), are to be stripped out.
A portion of a Grammar rule can also be stripped out
while leaving its sibling sub-rules intact.
Here are some examples of full and partial
stripping-out of Grammar rules in the serialization file:
x <type-qualifier> ::=
"const"
|
"volatile"
x <pointer> ::=
"asterisk"
"*"{
<type-qualifier>
}
"?"{
<pointer>
}
x <storage-class-specifier> ::=
"auto"
|
"register"
|
"static"
|
"extern"
|
"typedef"
_ <cast-expression> ::=
<unary-expression>
x|
"("
<type-name>
")"
<cast-expression>
_ <constant> ::=
integer-constant
|
hex-constant
|
binary-constant
x|
character-constant
x|
floating-constant
x|
enumeration-constant
_ <conditional-expression> ::=
<logical-or-expression>
x|
<logical-or-expression>
"?"
<expression>
":"
<conditional-expression>
My design intent here was to strip out all datatype-related language
constructs, as I support only one datatype, a signed 2-byte integer.
The processing and propagating of these "Strip Marks" consists of these
steps, which only happen once at the beginning of program execution:
Phase #A: Propagating per-orDef pruneMarks within BNFNodes...
Phase #B: Propagating whole-node pruneMarks within each BNFNode...
Phase #C1 & C2: Propagating pruneMarks downwards+upwards between BNFNodes...
Phase #C1 & C2, Pass# 1...
Phase #C1 & C2, Pass# 2...
Phase #D: Locating partially-pruned AndDefs...
Phase #E: Gathering of unpruned leafNodes...
Phase #F: Connecting leafNodes to grammarTree...
Similar to Eclipse, compilation is triggered each time the cursor moves to a new line. Currently the compilation steps are:
Phase #1: Tokenizing user program...
Phase #2: Coloring GrammarTree LeafNodes...
Phase #3: Connecting Tokens to their grammarRule OrDefs...
Phase #4: Grouping PARENS and enclosing their contents...
Phase #5: Building Syntax Tree on Unary Operators and their children...
Phase #6: Building syntaxTree on Binary Operators and their children...
Phase #7: Stack <expression> on all BNFNode Tokens...
Phase #8: Building syntaxTree on <jump-statement>'s...
Phase #9: Grouping BRACES and enclosing their contents...
Phase #10: Building Flow Control Statements and enclosing their contents...
Phase #11: Re-stack variable initializations outside functions...
Phase #12: Re-stack function invocations outside functions...
Phase #14: Wrap up function definitions...
Phase #15: Re-stack variable initializations outside functions...
Phase #16: Wrap up everything left over in <translation-unit>...
Phase #17: Populate Symbol Table...
Phase #18: Check Symbol Table( Used before Set)...
Phase #19: Check Symbol Table( # Function Args)...
Phase #20: Slot Global Variables...
Phase #21: Slot Function Call Args And Local Var Accesses...
Phase #22: Generate Global Vars Init Instructions...
Phase #23: Transmit Global Vars Init Instructions...
Phase #24: Generate Function Def Instructions...
Phase #25: Transmit Function Def Instructions...
Phase #26: Generate Function Invoke Instructions...
Phase #27: Transmit Function Invoke Instructions...
I also added the following instructions to the Robot's Assembler and Virtual Machine:
INSTR = >28++MATH<
INSTR = >29--MATH<
INSTR = >30MATH++<
INSTR = >31MATH--<
Thus the Robot Virtual Machine's Instruction Set now consists of:
INSTR = >14UNARY!<
INSTR = >15UNARY~<
INSTR = >16WHILE<
INSTR = >17IF<
INSTR = >18FOR<
INSTR = >19CALL<
INSTR = >20XSNV<
INSTR = >21VSXV<
INSTR = >22VGX<
INSTR = >23XGN<
INSTR = >24BREAK<
INSTR = >25RETURN<
INSTR = >26UNARY+<
INSTR = >27UNARY-<
INSTR = >28++MATH<
INSTR = >29--MATH<
INSTR = >30MATH++<
INSTR = >31MATH--<
INSTR = >32MATH+<
INSTR = >33MATH-<
INSTR = >34MATH*<
INSTR = >35MATH/<
INSTR = >36MATH%<
INSTR = >37MATH&<
INSTR = >38MATH|<
INSTR = >39MATH^<
INSTR = >40CMPR<<
INSTR = >41CMPR><
INSTR = >42CMPR==<
INSTR = >43CMPR!=<
INSTR = >44CMPR<=<
INSTR = >45CMPR>=<
INSTR = >46CMPR&&<
INSTR = >47CMPR||<
The Java program fetches this list of Instructions and the associated Addressing Mode info from the Robot and serializes them for use when the Robot is unavailable.
End Update.
Update 9/24/17:
Back to Updates List...
The Compiler in my Robot's Java Program is now compiling and assembling
Functions, and saving them for later execution by the Robot's Task Scheduler.
End Update.
Update 9/29/17:
Back to Updates List...
The Compiler in my Robot's Java Program is now compiling 22 functions,
one for each of the Instructions supported by the Robot's Virtual
Machine (RVM).
UNARY+:15
This shows which Instruction each function executed, its return value,
and that they all ran without problems.
End Update.
Update 10/5/17:
Back to Updates List...
The Compiler in my Robot's Java Program, and the Robot's Assembler and
Virtual Machine (RVM), are now compiling, assembling, and executing
function calls from within functions.
End Update.
Update 10/28/17:
Back to Updates List...
The Compiler in my Robot's Java Program,
and the Robot's Assembler and Virtual Machine (RVM),
are now compiling, assembling, and executing function
invocations as arguments to function invocations :-).
For clarity, the global variable initialization instructions are
omitted below.
0 >a< - >4<
fUminus():
RVM execution output:
// fUminus( bark, canary, 0, 0);
$CR19,0#2#4,0,0;
RVM execution output:
// bird( goose);
$CR19,1#7,0,0,0;
RVM execution output:
// cat( woof, xd);
$CR19,2#11#15,0,0;
RVM execution output:
// ostrich( d, honk);
$CR19,3#5#8,0,0;
RVM execution output:
// moose()
$CR19,4,0,0,0,0;
RVM execution output:
// chirp( xe, c, meow, xa);
$CR19,5#16#3#9#12;
The global variables' ending values are:
0 >a< - >4<
End Update.
Here is some pseudo-code of what I'd type into a
"compiler" window in my Robot program, which would be stored as
"bytecodes"/"opcodes" in the Robot and executed there:
// 6 inches is the minimum detection
threshold. PingSonarThresholdsInInches = {54,36,18};
PingSonar.registerThresholds(
PingSonarThresholdsInInches);
PingSonar.registerCrossingThresholdApproachingListener( PuppyR0toR1, 0);
PingSonar.registerCrossingThresholdApproachingListener( PuppyR1toR2, 1);
PingSonar.registerCrossingThresholdApproachingListener( PuppyR2toR3, 2);
PingSonar.registerCrossingThresholdRecedingListener(
PuppyR3toR2, 2);
PingSonar.registerCrossingThresholdRecedingListener( PuppyR2toR1, 1);
PingSonar.registerCrossingThresholdRecedingListener( PuppyR1toR0, 0); // Start off by just hangin’ out in
State0. // // We noticed someone < 54” away, so
now we’re in State1. // PuppyR0toR1() { Puppy.State = State1;
// “Hmm, interesting…” } int[5][4] wheelSpeeds = int[5][4];
// Initialize this some way … // Someone’s now inside
our “warm & fuzzy”-zone, so request from // the Java program an array of 5 or 6
possible wheelSpeeds to use to // follow them if they start walking away.
// PuppyR1toR2() {
// This first if( == State3) below is for processing the transition from //
State3->State2, i.e., when our friend turns back to us after // we chase
them. // // The
“first” part of R1->R2 handling (for State1->State2) comes
after the // if( == State3) below. // // Our new friend may
have turned towards us once we started chasing them. // In that case,
disconnect our chase mechanism, and go back to being //
“_really_ ready to follow” them. // // Go ahead and
fall through to do the wheelSpeeds fetching code again, // in case
our friend is approaching from a different direction now. //
if (Puppy.State == State3) {
PingSonar.unregisterDistanceChangedListener(
PuppyDistanceChangedInR1); } // Now we’re
back to processing the transition from State1->State2. // Puppy.State == State2;
// “I’m _really_ ready to follow you!”
// Read the direction
we want to go from the Sonar Servo,
// to be defined later. int
headingInDegreesToGo = 58;
// Pick some direction for now. // At this
point, I’m guessing that I’ll typically get ~5 possible speeds
// back from the
Java program for any particular direction I request. // The [4] is
because each there is a speed returned for each of the // 4 wheels,
so we can go sideways or do whatever Mecanum maneuver // we want.
//
wheelSpeeds =
fetchWheelSpeedsArrayFromJavaProgram(
headingInDegreesToGo); } // Oh-boy, oh-boy, oh-boy,
they’re walking away! // Let’s follow them, at a speed
proportional to how far into Range1 // they are. // Note: For the first little bit into
Range1 our speed is zero, so we // don’t move back and forth
“quivering”. // PuppyR2toR1() { Puppy.State = State3;
// “Chase! Chase! Chase!” // This tells the
Ping’s code to map its value that’s somewhere
// between Threshold1 and Threshold0, into an integer between // 0 to 5.
// We’ll use
this 0->5 value to pick one of our WheelSpeeds that we // received from
the Java program up above in PuppyR1toR2(). //
PingSonar.registerDistanceChangedListener(
PuppyDistanceChangedInR1,
Threshold1, Threshold0, 0, 5); } // Note: Unlike the other listeners above,
this one is being called for // _every_ (noise-filtered)
change in the Ping’s distance measurement, // not just when the Ping’s
distance crosses one of our registered // Thresholds. // PuppyDistanceChangeInR1( int
mappedDistanceFromThreshold1toThreshold0) { // The argument
passed in is an integer between 0->5, as we requested // up above.
//
setWheelSpeedsForward(
wheelSpeeds[
mappedDistanceFromThreshold1toThreshold0]); } // We can’t keep up! // Just go back to hangin’
out-mode. // PuppyR1toR0() {
// If we get to here,
we’re always coming from State3,
// so we have to disconnect our moment-to-moment // “give
chase”-Listener. //
PingSonar.unregisterDistanceChangedListener(
PuppyDistanceChangedInR1); Puppy.State = State0;
// “I’m lonely.” } // The evil stranger got too close!
// Run away! Run away! // PuppyR2toR3() { Puppy.State = State4;
// “Evil Stranger! Run awaay!” // This tells the
Ping’s code to map its value that’s somewhere // between
Threshold3 and 6 inches, into an integer between 0 to 5. // // We’ll use
this 0->5 value to pick one of our WheelSpeeds that we // received from
the Java program up above in PuppyR1toR2(), except // in reverse this
time, to run away from the evil stranger who got too // close! //
PingSonar.registerDistanceChangedListener(
PuppyDistanceChangedInR3,
Threshold3, 6, 0, 5); } // Note: Unlike the other listeners above,
this one is being called for _every_
// (noise-filtered) change in the Ping’s
distance measurement, not just when // the Ping’s distance crosses one
of our registered Thresholds. // // Let’s run away from the evil
stranger, at a speed proportional to how far // they are into Range3 (meaning how
close they are to the 6-inch minimum // measurement of the Ping sonar sensor.
// // Note: As above, for the first little bit
into Range3, our speed is zero, so // we don’t move back and forth
“quivering”. // PuppyDistanceChangedInR3( int
mappedDistanceFromThreshold3toSixInches) { // The argument
passed in is an integer between 0->5, as we requested // up above.
//
setWheelSpeedsReverse(
wheelSpeeds[mappedDistanceFromThreshold3toSixInches]); } // Whew! // The evil stranger backed off a
bit, so now we’re back
// in our “Ready to Follow”-state. // PuppyR3toR2() { // If we get to here,
we’re always coming from State4, // so we
disconnect our moment-to-moment “run away!”-Listener. //
PingSonar.unregisterDistanceChangedListener(
PuppyDistanceChangedInR3);
Puppy.State = State2; }
Here are some global variables and two testing functions,
that exercise the unary"+" and unary"-"
Assembly Language Instructions (which happen to be new
since the previous update):
Here are the corresponding Assembly Language Instructions
emitted by the Compiler and sent to the Robot to be stored
for recurring execution by its Task Scheduler:
Next up: Emitting instructions for function invocations
inside functions, and even function invocations as arguments
inside function invocations(!), followed finally by all those
pesky flow-control statements.
Lastly, here's the overall GUI after executing storedFunction[2], which invokes
storedFunction[0] and storedFunction[1]:
The Assembler in the Robot Assembles the functions, and the RVM successfully
stores them for later use, as shown here, where the RVM sends back to the
Java program, "^^^ 22 functions ready. ^^^":
At the end of its work, the Compiler generates an anonymous
"start()" function that calls all the other functions.
In this case, the Compiler processed function[0] thru function[21]
in the input source code, so the "start()" is function[22].
Thus the last line in the green "To Bot:" window is,
"$CR19,22,0,0,0". This is a CALL Instruction I typed in,
that calls "start()" (function[22]) with 4 dummy "0" arguments.
"start()" in turn calls function[0] thru function[21] with the
variables specified in the source code as function invocation args.
At the bottom of the gray "From Bot:" window the RVM sends back to the
Java program:
MATH-:-6
UNARY-:-4
MATH-:19
++MATH:5
--MATH:6
MATH++:5
MATH--:7
MATH+:12
MATH-:-10
MATH*:49
MATH/:2
MATH%:1
MATH&:7
MATH|:7
MATH^:0
CMPR<:0
CMPR>:1
CMPR==:1
CMPR!=:1
CMPR<=:0
CMPR>=:1
CMPR&&:0
CMPR||:1
The source code and assembly language files that I want to list here
for completeness get a bit long, so I'll just show them as links.
They open in a new window/tab in your browser.
Source code for the 22 functions compiled by the Java program...
Assembly Language statements from compiling the source code,
with [comments]...
The same Assembly Language statements, with comments stripped, +assembler
responses...
Once I begin accumulating functions to run in parallel all the time
in the Robot, I'll migrate their fully-assembled binary versions
from SRAM to Flash to save memory.
Next up: Emitting instructions for function invocations
inside functions, and even function invocations as arguments
inside function invocations(!), followed finally by all those
pesky flow-control statements.
I.e., for this test program:
the Compiler now produces these "human-readable" Assembly Language
Instructions:
After stripping out the "[]"-enclosed comments,
it sends to the Robot:
The first line defines the implementation of fUminus(), the second line
defines chirp(), and the third calls chirp( b, e);.
Thus to call "chirp( b, e)", I type in "$CR19,1#1#6,0,0", to which
the Robot replies:
This confirms that it successfully executed each of the Instructions in
chirp()
and in
fUminus().
Each of the functions below compiles into the assembly language
statements that follow their source code.
To execute a function, I type
"$CR19,funcNdx, ...", where
19
is the opCode for the
CALL Assembly Language Instruction,
and "$CR" is the Robot's command for
"Stored Command Run".
After each function's
assembly language statements is the Robot Virtual Machine (RVM)'s
output from running it, including its return value.
Of special note is the chirp()
function at the end.
Its second line contains pretty much everything I could throw at the
compiler, which successfully emits the corresponding rather elaborate
assembly language statements.
The global variables' symbolTable #'s and initial values are:
1 >b< - >4<
2 >bark< - >15<
3 >c< - >4<
4 >canary< - >7<
5 >d< - >4<
6 >e< - >11<
7 >goose< - >7<
8 >honk< - >16<
9 >meow< - >16<
10 >quack< - >15<
11 >woof< - >9<
12 >xa< - >7<
13 >xb< - >7<
14 >xc< - >7<
15 >xd< - >7<
16 >xe< - >7<
newDollarCmd = >$CR19,0#2#4,0,0;<
processDollarCommand.result = >3<
================================================
bird():
newDollarCmd = >$CR19,1#7,0,0,0;<
processDollarCommand.result = >105<
================================================
cat():
newDollarCmd = >$CR19,2#11#15,0,0;<
processDollarCommand.result = >225<
================================================
ostrich():
newDollarCmd = >$CR19,3#5#8,0,0;<
processDollarCommand.result = >9<
================================================
moose():
newDollarCmd = >$CR19,4,0,0,0,0;<
processDollarCommand.result = >15<
================================================
chirp():
newDollarCmd = >$CR19,5#16#3#9#12;<
processDollarCommand.result = >13<
================================================
1 >b< - >10<
2 >bark< - >15<
3 >c< - >143<
4 >canary< - >7<
5 >d< - >5<
6 >e< - >11<
7 >goose< - >7<
8 >honk< - >16<
9 >meow< - >9<
10 >quack< - >15<
11 >woof< - >9<
12 >xa< - >7<
13 >xb< - >7<
14 >xc< - >165<
15 >xd< - >15<
16 >xe< - >7<
Next up:
continue,
break,
return,
if,
while, and
for statements will be added next.
Below are the Assembler's responses as it
assembles the functions into byte-code and
stores them away for later execution.
Lastly I ran each function as described above:
Puppy Algorithm Description:
Back to Updates List...