compiler extension



The nut language and its compiler is designed to be very compact. Some extension to the language will make programming easier.  This note discusses some possible extension.

Multiway branch

To do multiple way branches, nested-if is used.  This is very flexible but
  1. in special case, it is inefficient to do sequential testing on the conditions.
  2. the syntax for deep nested-if is quite cumbersome, especially the closing parenthesis.  The number of right parenthesis is equal to the depth of nested-if.  

(if (= op xADD) (doadd)
(if (= op xSUB) (dosub)
...
; else
(error "unknown op") ...))
 
To help syntax in general case, (cond....) in LISP is a good example.  In nut, we can do:

(switch
  (cond1) (action1)
  (cond2) (action2) ...
  true (default action))

This syntax will reduce the number of the closing right parenthesis to one.

To improve the efficiency, if the condition is equality of one variable with many constants, then we can do similar to "switch, case" in C or Pascal.  The implementation can use a jump-table indexed by the value of one variable.

(case op
  (label xADD (doadd))
  (label xSUB (dosub))
  ...
  (else (default action)))

The n-code for "case" will contain a jump-table of the association list of (label jump-to) which is implemented as an array of cells. To conform to the existing n-code only the head can be atom, therefore the head is a label instruction (a new instruction), the tail is a pointer to the action body.

in n-code, assume op is local, len is length of the jump-table, the last entry is an instruction to terminate the table.

(case.op
  ; jump table  
  (label.xADD L1)
  (label.xSUB L2)
  ...
  (else.0 Ln))
  ; actions
  <L1> (action 1)
  <L2> (action 2)
  ...
  <Ln> (default action)

If the lable is sorted according to the key (constants) then the jump table can be binary search. The length of jump-table must be known.

(case2.op lit.len
  ; jump table, label is sorted by its arg
  [xADD L1
   xSUB L2
  ...
   NIL Ln])
  ; actions
  <L1> (action 1)
  <L2> (action 2)
  ...
  <Ln> (default action)

Another way which is faster is to use label to index into the jump table directly.  The size of jump table is equal to the range of index.  The label instruction is not necessary.  The range of index must be known.  

(case3.op lit.lo lit.hi
  ; jump table, label is sorted by its arg
  [L1 L2 ... Ln])
  ; actions
  <L1> (action 1)
  <L2> (action 2)
  ...
  <Ln> (default action)

For the second kind and third kind of "case", the jump-table itself does not conform the format of n-code.  To implement it, it is not really a list, it is an array (which is a "data").  To have an array in the code segment, an additional representation must be designed.

Increment instruction

Incrementing a variable is oftenly used.

(set a (+ a 1))

A compact way to write it is to use a new instruction "inc".

(inc a)

"inc" can not be written as a function definition as it treats the second argument as un-evaluated (pass by reference).  It must be handle by the compiler.  If we concern only the "efficiency" of execution, a compiler optimisation can be done by replacing (set...) by (inc..).  The same method can be applied for decrementing a variable.

Macro

Macro is a textual replacement of the code.  It can help improving the efficiency of executing the program as it eliminates the function call overhead.  (see nut25 for implementation of macro).

26 June 2006