Skip to content

Draft: Recursive array comprehension

Michel van Wijk requested to merge jmvanwijk/sac2c:Recursive-array-comprehension into develop

This adds support using @-notation for recursive array comprehensions (RACs) in (set) with-loops implemented as two phases. ARAC (annotate) marks a let with an isRecursive flag and the corresponding spids to indicate the presence of recursion. TRAC (transform) rewrites the marked lets into iterative code that resolves the recursive definition.

For example, fibonacci can then be defined as a = {[i] -> i == 0 ? 0 : i == 1 ? 1 : @a[i-1] + @a[i-2] | [i] < [n]; [i] -> 0 | [i] < [n]};

or as a regular with-loop: a = with{ ([0] <= [i] < [n]): (i == 0 ? 0 : i == 1 ? 1 : @a[i-1] + @a[i-2]); }: genarray([n], 0);

For more extensive descriptions, see the top comments in src/libsac2c/scanparse/annotate_recursive_array_comprehensions.c and src/libsac2c/scanparse/transform_recursive_array_comprehensions.c.

Merge request reports