In :
Read("../gap/optim.g"); Read("../gap/bench.g");


# GAP Level Reflection¶

This newly added feature of GAP allows GAP programs to examine and modify the code of executable GAP function objects within the workspace. This will provide a platform for optimisation, automatic parallelisation and Cython-like partial static typing.

## A Small Optimisation¶

It is natural in GAP to write Int(x/y) for integer division, but this is actually quite inefficient. If x is not divisible by y then a rational number object will be made on the heap and reduced to lowest terms before being rounded to the nearest integer below. The QuoInt function exists to avoid this, but is unnatural and underused.

We demonstrate the difference with a simple benchmark:

In :
foo := function(n) local i,x; for i in [1..n] do
x := Int(i/3);
od; end;;
bar :=  function(n) local i,x; for i in [1..n] do
x := QuoInt(i,3);
od; end;;
ns2string(timer(foo)); ns2string(timer(bar));

Out:
"137ns"
Out:
"23ns"

We show how SyntaxTree could be used to automatically fix this in the workspace.

f below is a test function. The second comment is a pragma -- a comment which is retained in the function object, which could be used to direct optimisation.

Note that the pragma appears in the syntax tree, unlike the regular comment

In :
f := function(x)
# normal comment
#% optimise here
return Int((x+1)/3) + Int((x^2)/11);
end;;
Display(SyntaxTree(f));

EXPR_FUNC(name := f, nams := [ "x" ], variadic := false, narg := 1, nloc := 0,\
stats := STAT_SEQ_STAT2(
statements := [
STAT_PRAGMA(value := % optimise here ), STAT_RETURN_OBJ(
obj := EXPR_SUM(
right := EXPR_FUNCCALL_1ARGS(
args := [
EXPR_QUO(
right := EXPR_INT(value := 11), left := EXPR_POW(
right := EXPR_INT(
value := 2), left := EXPR_REF_LVAR(lvar := 1)))
], funcref := EXPR_REF_GVAR(gvar := Int)
), left := EXPR_FUNCCALL_1ARGS(
args := [
EXPR_QUO(
right := EXPR_INT(value := 3), left := EXPR_SUM(
right := EXPR_INT(
value := 1), left := EXPR_REF_LVAR(
lvar := 1)))
], funcref := EXPR_REF_GVAR(gvar := Int))))]))


Now to produce an improved version of f, we define a pattern including placeholders "$1" and "$2" and a replacement.

Both are essentially just fragments of syntax tree. Nicer pattern editing tools and in development.

In [ ]:
pattern := rec(type := "EXPR_FUNCCALL_1ARGS",
funcref := rec(type := "EXPR_REF_GVAR", gvar := "Int"),
args := [rec(type := "EXPR_QUO", left := "$1", right := rec(type := "EXPR_INT", value := "$2"))]);
replace := rec(type := "EXPR_FUNCCALL_2ARGS",
funcref := rec(type := "EXPR_REF_GVAR", gvar := "QuoInt"),
args := ["$1",rec(type := "EXPR_INT", value := "$2") ]);

Out[ ]:
rec( args := [ rec( left := "$1", right := rec( type := "EXPR_INT", value := "$2" ), type := "EXPR_QUO" ) ], funcref := rec( gvar := "Int", type := "EXPR_REF_GVAR" ), type := "EXPR_FUNCCALL_1ARGS" )
Out[ ]:
rec( args := [ "$1", rec( type := "EXPR_INT", value := "$2" ) ], funcref := rec( gvar := "QuoInt", type := "EXPR_REF_GVAR" ), type := "EXPR_FUNCCALL_2ARGS" )

We can use these to rewrite f

In :
g := RewriteFunc(f, pattern, replace);;
Display(g);

function ( x )
#% optimise here
return QuoInt( x + 1, 3 ) + QuoInt( x ^ 2, 11 );
end


We compare the performance.

In :
ns2string(timer( function(n) local i; for  i in [1..n] do f(i); od; end));
ns2string(timer( function(n) local i; for  i in [1..n] do g(i); od; end));

Out:
"340ns"
Out:
"95ns"