Proposals on Middle-level APIs

[e-]

In this issue, I propose a middle-level API for the library. The API should connect the low-level implementation (i.e., computational trees) and high-level codes (i.e., the current interface with sessions and loops).

Examples

Accumulating an array

original:

for i in array:
    res += arr[i]

middle-level:

res = Accumulate(each(arr))

Accumulating two equal-length arrays

original:

for i in array:
    res += arr[i] * 2 + arr2[i]

middle-level:

res = Accumulate(each(arr) * 2 + each(arr2))

Ambiguity 1

middle-level:

res = Accumulate(each(arr) + each(arr2))

The code above can mean either of the following:

Case 1:

for i in array:
    res += arr[i] + arr2[i]

Case 2:

for i in array:
    res += arr[i]
    
for i in array2:
    res + arr2[i]

We will choose Case 1.

Advantage:

• The accumulate function is explicitly mapped to one loop. One Accumulate corresponds to one loop.
• It is more explicit that there is nothing between the two loops in the second case.

Disadvantage:

• The two arrays must have the same length (there is a workaround for this. see the next example).

Ambiguity 2

middle-level:

res = Accumulate(each(arr)) + Accumulate(each(arr2))

means

for i in array:
    res += arr[i]

for i in array2:
    res += arr2[i]

not

for i in array:
    res += arr[i] + arr2[i]

Benefit 1

for i in array:
    res1 += arr[i]
    res2 += res1

This example cannot be progressivified, but there is no way to detect this before compilation in the current high-level API.

With the middle-level API, we prevent the user from stating such a case because

res1 = Accumulate(each(arr))
res2 = Accumulate(res1)

means

for i in array:
    res1 += arr[i]

for i in array:
    res2 += res1

which can be progressivified.

Corner case 1

res = Accumulate(1)

The code above is not compilable as the length of the array is not specified.

Corner case 2

res = Accumulate(each(arr))
res += Accumulate(each(arr))

The code above is not compilable.
We do not support the in-place operations (e.g., __iadd__) between variables.

Average

for i in array:
    res += arr[i]

res /= len(array)

is equivalent to

res = Accumulate(each(arr)) / len(array)

Variance

mean = Accumulate(each(arr)) / len(array)
res = Accumulate((each(arr) - mean) ** 2) / len(array)

Covariance

mean1 = Accumulate(each(arr1)) / len(array)
mean2 = Accumulate(each(arr2)) / len(array)
res = Accumulate((each(arr1) - mean1) * (each(arr2) - mean2)) / len(array)

Linear regression

mean1 = Accumulate(each(arr1)) / len(array)
mean2 = Accumulate(each(arr2)) / len(array)
cov = Accumulate((each(arr1) - mean1) * (each(arr2) - mean2)) / len(array)
var = Accumulate((each(arr1) - mean1) ** 2) / len(array)
slope = cov / var
intercept = mean2 - slope * mean1

Note that usually, division between base quantities is not allowed, but in this case, slope and intercept are out of loops.

Uncompilable 1

for i in array:
    res += arr[i] / arr2[i] 
res /= len(array)

middle-level:

res = Accumulate(each(arr) / each(arr2)) / len(array)

However, this is not compilable because there is no base quantity that represents the ratio of two elements for now (will be included later).

Difference

However, below is possible:

for i in array:
    res += arr[i] - arr2[i]
res /= len(array)

middle-level:

res = Accumulate(each(arr) - each(arr2)) / len(array)

This is because subtraction can move between additions (i.e., Accumulate).

Observation

0-order expression: No Accumulate, e.g., 5
1-order expression: Accumulate in the argument, e.g., Accumulate(each(arr)) and Accumulate(each(arr) + each(arr2))
2-order expression: Accumulate in the argument of Accumulate, e.g., Accumulate(each(arr) - v) where v is a 1-order expression.

TODOs

• What program can be described with the middle-level API but not progressive?