Howto:Add a new binary operator to Nasal


Problem

The Nasal engine in FlightGear/SimGear is currently not actively maintained, so we need to document how to extend and improve the engine on our own.

Objective

Demonstrate how to add a new binary operator to Nasal. The point of this tutorial is not that we really need a spaceship operator in Nasal, rather the whole point is to demonstrate how we can extend the engine, even though it is currently not actively maintained. So the spaceship operator is really just intended to be an example.

Note  For a more recent, and a more practical, example you can also see SimGear commit 9aa5c3b2ae9442a9f777088cae982aef9034183c which illustrates how support for standard bitwise operators was added to Nasal in FlightGear 3.2+.

Example: Perl's spaceship operator: <=>

<=> For details, see: http://en.wikipedia.org/wiki/Spaceship_operator

Semantics

The spaceship operator will return 1, 0, or −1 depending on the value of the left argument relative to the right argument. If the left argument is greater than the right argument, the operator returns 1. If the left argument is less than the right argument, the operator returns −1. If the two arguments are equal, the operator returns 0. If the two arguments cannot be compared (e.g. one of them is NaN), the operator returns undef.

Adding a new token

// Static table of recognized lexemes in the language
static const struct Lexeme {
    char* str;
    int   tok;
} LEXEMES[] = {
    {"and", TOK_AND},
    {"or",  TOK_OR},
    {"!",   TOK_NOT},
    {"(", TOK_LPAR},
    {")", TOK_RPAR},
    {"[", TOK_LBRA},
    {"]", TOK_RBRA},
    {"{", TOK_LCURL},
    {"}", TOK_RCURL},
    {"*", TOK_MUL},
    {"+", TOK_PLUS},
    {"-", TOK_MINUS},
    {"/", TOK_DIV},
    {"~", TOK_CAT},
    {":", TOK_COLON},
    {".", TOK_DOT},
    {",", TOK_COMMA},
    {";", TOK_SEMI},
    {"=", TOK_ASSIGN},
    {"<",  TOK_LT},
    {"<=", TOK_LTE},
    {"==", TOK_EQ},
    {"!=", TOK_NEQ},
    {">",  TOK_GT},
    {">=", TOK_GTE},
    {"nil", TOK_NIL},
    {"if",    TOK_IF},
    {"elsif", TOK_ELSIF},
    {"else",  TOK_ELSE},
    {"for",     TOK_FOR},
    {"foreach", TOK_FOREACH},
    {"while",   TOK_WHILE},
    {"return",   TOK_RETURN},
    {"break",    TOK_BREAK},
    {"continue", TOK_CONTINUE},
    {"func", TOK_FUNC},
    {"...", TOK_ELLIPSIS},
    {"?", TOK_QUESTION},
    {"var", TOK_VAR},
    {"+=", TOK_PLUSEQ},
    {"-=", TOK_MINUSEQ},
    {"*=", TOK_MULEQ},
    {"/=", TOK_DIVEQ},
    {"~=", TOK_CATEQ},
    {"<=>", TOK_SPCSHIP},
    {"forindex", TOK_FORINDEX},
};
enum tok {
    TOK_TOP=1, TOK_AND, TOK_OR, TOK_NOT, TOK_LPAR, TOK_RPAR, TOK_LBRA,
    TOK_RBRA, TOK_LCURL, TOK_RCURL, TOK_MUL, TOK_PLUS, TOK_MINUS, TOK_NEG,
    TOK_DIV, TOK_CAT, TOK_COLON, TOK_DOT, TOK_COMMA, TOK_SEMI,
    TOK_ASSIGN, TOK_LT, TOK_LTE, TOK_EQ, TOK_NEQ, TOK_GT, TOK_GTE, TOK_SPCSHIP,
    TOK_IF, TOK_ELSIF, TOK_ELSE, TOK_FOR, TOK_FOREACH, TOK_WHILE,
    TOK_RETURN, TOK_BREAK, TOK_CONTINUE, TOK_FUNC, TOK_SYMBOL,
    TOK_LITERAL, TOK_EMPTY, TOK_NIL, TOK_ELLIPSIS, TOK_QUESTION, TOK_VAR,
    TOK_PLUSEQ, TOK_MINUSEQ, TOK_MULEQ, TOK_DIVEQ, TOK_CATEQ,
    TOK_FORINDEX
};

Operator Precedence

To affect operator precedence, see $SG_SRC/simgear/nasal/parse.c#l6 and edit it accordingly:

// Static precedence table, from low (loose binding, do first) to high
// (tight binding, do last).
#define MAX_PREC_TOKS 6
static const struct precedence {
    int toks[MAX_PREC_TOKS];
    int rule;
} PRECEDENCE[] = {
    { { TOK_SEMI, TOK_COMMA },                 PREC_REVERSE },
    { { TOK_ELLIPSIS },                        PREC_SUFFIX  },
    { { TOK_RETURN, TOK_BREAK, TOK_CONTINUE }, PREC_PREFIX  },
    { { TOK_ASSIGN, TOK_PLUSEQ, TOK_MINUSEQ,
        TOK_MULEQ, TOK_DIVEQ, TOK_CATEQ     }, PREC_REVERSE },
    { { TOK_COLON, TOK_QUESTION },             PREC_REVERSE },
    { { TOK_VAR },                             PREC_PREFIX  },
    { { TOK_OR },                              PREC_BINARY  },
    { { TOK_AND },                             PREC_BINARY  },
    { { TOK_EQ, TOK_NEQ },                     PREC_BINARY  },
    { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE },    PREC_BINARY  },
    { { TOK_PLUS, TOK_MINUS, TOK_CAT },        PREC_BINARY  },
    { { TOK_SPCSHIP },                    PREC_BINARY  },
    { { TOK_MUL, TOK_DIV },                    PREC_BINARY  },
    { { TOK_MINUS, TOK_NEG, TOK_NOT },         PREC_PREFIX  },
    { { TOK_LPAR, TOK_LBRA },                  PREC_SUFFIX  },
    { { TOK_DOT },                             PREC_BINARY  },
};

Extending the code generator

// ...
    case TOK_MUL:   genBinOp(OP_MUL,    p, t); break;
    case TOK_PLUS:  genBinOp(OP_PLUS,   p, t); break;
    case TOK_DIV:   genBinOp(OP_DIV,    p, t); break;
    case TOK_CAT:   genBinOp(OP_CAT,    p, t); break;
    case TOK_LT:    genBinOp(OP_LT,     p, t); break;
    case TOK_LTE:   genBinOp(OP_LTE,    p, t); break;
    case TOK_EQ:    genBinOp(OP_EQ,     p, t); break;
    case TOK_NEQ:   genBinOp(OP_NEQ,    p, t); break;
    case TOK_GT:    genBinOp(OP_GT,     p, t); break;
    case TOK_GTE:   genBinOp(OP_GTE,    p, t); break;
    case TOK_SPCSHIP:genBinOp(OP_SPACESHIP, p, t); break;
    case TOK_PLUSEQ:  genEqOp(OP_PLUS, p, t);  break;
    case TOK_MINUSEQ: genEqOp(OP_MINUS, p, t); break;
    case TOK_MULEQ:   genEqOp(OP_MUL, p, t);   break;
    case TOK_DIVEQ:   genEqOp(OP_DIV, p, t);   break;
    case TOK_CATEQ:   genEqOp(OP_CAT, p, t);   break;
//...
enum {
    OP_NOT, OP_MUL, OP_PLUS, OP_MINUS, OP_DIV, OP_NEG, OP_CAT, OP_LT, OP_LTE,
    OP_GT, OP_GTE, OP_EQ, OP_NEQ, OP_EACH, OP_JMP, OP_JMPLOOP, OP_JIFNOTPOP,
    OP_JIFEND, OP_FCALL, OP_MCALL, OP_RETURN, OP_PUSHCONST, OP_PUSHONE,
    OP_PUSHZERO, OP_PUSHNIL, OP_POP, OP_DUP, OP_XCHG, OP_INSERT, OP_EXTRACT,
    OP_MEMBER, OP_SETMEMBER, OP_LOCAL, OP_SETLOCAL, OP_NEWVEC, OP_VAPPEND,
    OP_NEWHASH, OP_HAPPEND, OP_MARK, OP_UNMARK, OP_BREAK, OP_SETSYM, OP_DUP2,
    OP_INDEX, OP_BREAK2, OP_PUSHEND, OP_JIFTRUE, OP_JIFNOT, OP_FCALLH,
    OP_MCALLH, OP_XCHG2, OP_UNPACK, OP_SLICE, OP_SLICE2, OP_SPACESHIP
};

Extending the VM

#define BINOP(expr) do { \
    double l = IS_NUM(STK(2)) ? STK(2).num : numify(ctx, STK(2)); \
    double r = IS_NUM(STK(1)) ? STK(1).num : numify(ctx, STK(1)); \
    SETNUM(STK(2), expr);                                         \
    ctx->opTop--; } while(0)

        case OP_PLUS:  BINOP(l + r);         break;
        case OP_MINUS: BINOP(l - r);         break;
        case OP_MUL:   BINOP(l * r);         break;
        case OP_DIV:   BINOP(l / r);         break;
        case OP_LT:    BINOP(l <  r ? 1 : 0); break;
        case OP_LTE:   BINOP(l <= r ? 1 : 0); break;
        case OP_GT:    BINOP(l >  r ? 1 : 0); break;
        case OP_GTE:   BINOP(l > r ? 1 : 0); break;
	case OP_SPACESHIP: BINOP( l > r ? 1: l<r ?-1:0  ); break;
#undef BINOP

Testing the new operator

 print ( 1 <=> 1 );
 print (10 <=> 0 );
 print ( -3 <=> 4 );

The whole patch

diff --git a/simgear/nasal/code.c b/simgear/nasal/code.c
index 08d710f..8dc4c4c 100644
--- a/simgear/nasal/code.c
+++ b/simgear/nasal/code.c
@@ -584,6 +584,7 @@ static naRef run(naContext ctx)
         case OP_LTE:   BINOP(l <= r ? 1 : 0); break;
         case OP_GT:    BINOP(l >  r ? 1 : 0); break;
         case OP_GTE:   BINOP(l >= r ? 1 : 0); break;
+	case OP_SPACESHIP: BINOP(l > r ? 1: l<r ?-1:0 ); break;
 #undef BINOP
 
         case OP_EQ: case OP_NEQ:
diff --git a/simgear/nasal/code.h b/simgear/nasal/code.h
index 3db6107..1596f47 100644
--- a/simgear/nasal/code.h
+++ b/simgear/nasal/code.h
@@ -26,7 +26,7 @@ enum {
     OP_MEMBER, OP_SETMEMBER, OP_LOCAL, OP_SETLOCAL, OP_NEWVEC, OP_VAPPEND,
     OP_NEWHASH, OP_HAPPEND, OP_MARK, OP_UNMARK, OP_BREAK, OP_SETSYM, OP_DUP2,
     OP_INDEX, OP_BREAK2, OP_PUSHEND, OP_JIFTRUE, OP_JIFNOT, OP_FCALLH,
-    OP_MCALLH, OP_XCHG2, OP_UNPACK, OP_SLICE, OP_SLICE2
+    OP_MCALLH, OP_XCHG2, OP_UNPACK, OP_SLICE, OP_SLICE2, OP_SPACESHIP
 };
 
 struct Frame {
diff --git a/simgear/nasal/codegen.c b/simgear/nasal/codegen.c
index 059c114..37a4538 100644
--- a/simgear/nasal/codegen.c
+++ b/simgear/nasal/codegen.c
@@ -679,6 +679,7 @@ static void genExpr(struct Parser* p, struct Token* t)
     case TOK_NEQ:   genBinOp(OP_NEQ,    p, t); break;
     case TOK_GT:    genBinOp(OP_GT,     p, t); break;
     case TOK_GTE:   genBinOp(OP_GTE,    p, t); break;
+    case TOK_SPCSHIP:genBinOp(OP_SPACESHIP, p, t); break;
     case TOK_PLUSEQ:  genEqOp(OP_PLUS, p, t);  break;
     case TOK_MINUSEQ: genEqOp(OP_MINUS, p, t); break;
     case TOK_MULEQ:   genEqOp(OP_MUL, p, t);   break;
diff --git a/simgear/nasal/lex.c b/simgear/nasal/lex.c
index 89c3c40..5bd1d2f 100644
--- a/simgear/nasal/lex.c
+++ b/simgear/nasal/lex.c
@@ -49,6 +49,7 @@ static const struct Lexeme {
     {"*=", TOK_MULEQ},
     {"/=", TOK_DIVEQ},
     {"~=", TOK_CATEQ},
+    {"<=>", TOK_SPCSHIP},
     {"forindex", TOK_FORINDEX},
 };
 
diff --git a/simgear/nasal/parse.c b/simgear/nasal/parse.c
index 2e66d8f..7f89140 100644
--- a/simgear/nasal/parse.c
+++ b/simgear/nasal/parse.c
@@ -22,6 +22,7 @@ static const struct precedence {
     { { TOK_EQ, TOK_NEQ },                     PREC_BINARY  },
     { { TOK_LT, TOK_LTE, TOK_GT, TOK_GTE },    PREC_BINARY  },
     { { TOK_PLUS, TOK_MINUS, TOK_CAT },        PREC_BINARY  },
+    { { TOK_SPCSHIP }, 			       PREC_BINARY  },
     { { TOK_MUL, TOK_DIV },                    PREC_BINARY  },
     { { TOK_MINUS, TOK_NEG, TOK_NOT },         PREC_PREFIX  },
     { { TOK_LPAR, TOK_LBRA },                  PREC_SUFFIX  },
diff --git a/simgear/nasal/parse.h b/simgear/nasal/parse.h
index 1574ea3..52baa26 100644
--- a/simgear/nasal/parse.h
+++ b/simgear/nasal/parse.h
@@ -11,7 +11,7 @@ enum tok {
     TOK_TOP=1, TOK_AND, TOK_OR, TOK_NOT, TOK_LPAR, TOK_RPAR, TOK_LBRA,
     TOK_RBRA, TOK_LCURL, TOK_RCURL, TOK_MUL, TOK_PLUS, TOK_MINUS, TOK_NEG,
     TOK_DIV, TOK_CAT, TOK_COLON, TOK_DOT, TOK_COMMA, TOK_SEMI,
-    TOK_ASSIGN, TOK_LT, TOK_LTE, TOK_EQ, TOK_NEQ, TOK_GT, TOK_GTE,
+    TOK_ASSIGN, TOK_LT, TOK_LTE, TOK_EQ, TOK_NEQ, TOK_GT, TOK_GTE, TOK_SPCSHIP,
     TOK_IF, TOK_ELSIF, TOK_ELSE, TOK_FOR, TOK_FOREACH, TOK_WHILE,
     TOK_RETURN, TOK_BREAK, TOK_CONTINUE, TOK_FUNC, TOK_SYMBOL,
     TOK_LITERAL, TOK_EMPTY, TOK_NIL, TOK_ELLIPSIS, TOK_QUESTION, TOK_VAR,