Kawa parser for SRFI 105 curly infix and operator precedence optimization

[Damien Mattei <damien.mattei@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3516 bytes --]

hello,

i have written a SRFI 105 optimizer for curly infix with operator
precedence.
It allows optimization of infix mathematics expression that are translated
in the fastest prefix scheme expressions.

For example:
{M_i_o[j {i + 1}]  <-  M_i_o[j {i + 1}] - (- η) * z_input[i] *
მzⳆმz̃(z_output[j] z̃_output[j]) * ᐁ_i_o[j]}

is normally translated in SRFI 105 curly infix in:
($nfx$
  (bracket-apply M_i_o j (+ i 1))
  <-
  (bracket-apply M_i_o j (+ i 1))
  -
  (- η)
  *
  (bracket-apply z_input i)
  *
  (მzⳆმz̃ (bracket-apply z_output j) (bracket-apply z̃_output j))
  *
  (bracket-apply ᐁ_i_o j))

but the $nfx$ which should be an infix operator precedence evaluator is a
long recursive algorithm that slows down scheme infix evaluation.

The parser curly-infix2prefix4kawa.scm precompute symbolically any infix
mathematics expression and replace them by prefix scheme expressions before
being compiled or interpreted by your favorite scheme implementation.

Then the SRFI 105 could be used with any scheme implementation Kawa or
other and more than curly infix, infix expression with operator precedence
could be used.

the expression above:

{M_i_o[j {i + 1}]  <-  M_i_o[j {i + 1}] - (- η) * z_input[i] *
მzⳆმz̃(z_output[j] z̃_output[j]) * ᐁ_i_o[j]}

is then translated in:

(<- sum
         (+ sum
          (*
           (მzⳆმz̃
            (bracket-applynext (bracket-applynext z (list (+ i 1))) (list
k))
            (bracket-applynext (bracket-applynext z̃ (list (+ i 1)))
             (list k)))
           (*
            (bracket-applynext (bracket-applynext M (list i)) (list k (+ j
1)))
            (bracket-applynext (bracket-applynext ᐁ (list (+ i 1)))
             (list k)))))

you will notice there is then no more $nfx$ (from SRFI 105) call and
expression is then normal scheme (bracket-applynext is only for [ ]
specialisation) . It is more than 4 times faster than without optimization.

The optimiser works also for specialisation of [ ] that allow the Python
sliced array notation but it is implemented outside the parser then, only
optimization is done in the parser:

example where the slice notation with : in Python is replaced by $ in
scheme (note that Kawa as also its own 'ranges' features for containers
see: https://www.gnu.org/software/kawa/Ranges.html ):

echo "{#(1 2 3 4 5 6 7)[2 * 5 - 8 $ 3 * 5 - 10 $ 2 * 4 - 6]}" >
sliced-array+.scm

cat sliced-array+.scm
{#(1 2 3 4 5 6 7)[2 * 5 - 8 $ 3 * 5 - 10 $ 2 * 4 - 6]}

parsing of the file :

kawa curly-infix2prefix4kawa.scm --infix-optimize --infix-optimize-slice
sliced-array+.scm
curly-infix2prefix4kawa.scm:421:5: warning - unreachable code
(bracket-applynext #(1 2 3 4 5 6 7)
 (list (- (* 2 5) 8) $ (- (* 3 5) 10) $ (- (* 2 4) 6)))

testing of the expression :

kawa -Dkawa.import.path=".:/Users/mattei/Scheme-PLUS-for-Kawa:./kawa"
#|kawa:1|# (require Scheme+)
#|kawa:3|# bracket-applynext
#<procedure bracket-applynext>
#|kawa:4|# (bracket-applynext #(1 2 3 4 5 6 7)
#|.....5|#  (list (- (* 2 5) 8) $ (- (* 3 5) 10) $ (- (* 2 4) 6)))
#(3 5)

the result is #(3 5) because the slicing of  {#(1 2 3 4 5 6 7)[2 * 5 - 8 $
3 * 5 - 10 $ 2 * 4 - 6]} is equal to the slicing of {#(1 2 3 4 5 6 7)[2 $ 5
$ 2]}

the parser is available (with its includes files in the same directory)
here:

https://github.com/damien-mattei/Scheme-PLUS-for-Kawa/blob/main/curly-infix2prefix4kawa.scm

Damien