robpike
ivy: control flow
Our discussion about looping in Ivy made me also think about control flow generally. I wrote this code recently:
op (x i ai bi) firstmod (a b l r) =
(a==0) or (b==0): 0
x i = x i + (0 max ceil (l - x) / a)*(a ai)
x i = x i + (0 max ceil (x - r) / b)*(-b) bi
(l <= x) and (x <= r): i
b >= a: x i ai (bi+ai*n) firstmod a (b-a*n=floor b/a) l r
x i (ai+bi*n) bi firstmod (a-b*n=floor a/b) b l r
op firstmod (a b l r) =
l > r: 0
(0 0 1 0) firstmod (a b l r)
firstmod 13 256 1 5
(firstmod 13 256 1 5 is the first (smallest) value i such that 1 <= i*13 mod 256 <= 5, but the exact meaning of the code doesn't matter.)
This illustrates a typical (for me at least) Ivy loop and conditional. The unary firstmod calls the binary firstmod with the looping variables as the left operand. Also, at the end of the binary firstmod, there is a conditional that wants to decide how to update the variables for the next iteration, and instead it has to make two separate tail-calls.
It looks like Dyalog has :if, :else, :while, :end, which would let me write:
op firstmod (a b l r) =
l > r: 0
:while (a != 0) and (b != 0)
x i = x i + (0 max ceil (l - x) / a)*(a ai)
x i = x i + (0 max ceil (x - r) / b)*(-b) bi
(l <= x) and (x <= r): i
:if a >= b
a ai = a ai + (floor a/b)*((-b) bi)
:else
b bi = b bi + (floor b/a)*((-a) ai)
:end
:end
0
It does seem like that would be nicer. I don't know if this is a direction you want Ivy to go.
The first one (tail recursion) is the Scheme programmer's approach; the second one (a loop) is the Algol programmer's approach. I believe the APL programmer's approach to iteration (if the vector operations aren't sufficient) would be the power operator (⍣):
(step⍣done) initialState
Although the explicit if and while syntax might be nice, it'd be great to see a couple of flavours of factor. It definitely feels more APL'ish.
The other thing I've wondered along these lines is if we can get simple tail call optimisation? I couldn't find any reference to it in the code, but a lot of times on the AoC tasks (sadly that's when I use ivy most), I want to reach for simple recursion on the larger datasets and worry that it'll blow out the stack.
Not ready for prime time, and I'm not sure I like it, but I have this working now in unchecked-in code:
)op sign
op sign i = if: i >= 0; "positive"; else: "negative"; end:
sign@ -3 4
negative positive
)op fac
op fac n =
f = n
while: n=n-1
f = f * n
end:
fac 1e4
2.84625968092e+35659
)cpu
26.166ms (34.585ms user, 10.617ms sys)
)op rfac
op rfac n =
n <= 0: 1
rfac 1e4
2.84625968092e+35659
)cpu
59.164ms (69.903ms user, 11.344ms sys)
The if: and while: constructs are expressions, not (exactly) control flow. Also there is the dangling else problem, which will require elif: or some such.
This works now.
op firstmod (a b l r) =
l > r: 0
x i ai bi = 0 0 1 0
:while (a != 0) and (b != 0)
x i = x i + (0 max ceil (l - x) / a)*(a ai)
x i = x i + (0 max ceil (x - r) / b)*(-b) bi
(l <= x) and (x <= r): i
:if a >= b
a ai = a ai + (floor a/b)*((-b) bi)
:else
b bi = b bi + (floor b/a)*((-a) ai)
:end
:end
i
firstmod 13 256 1 5
20
Needs some polishing but I think it's good.
One nuance: The colon operator returns from the block, not the whole function. I think that's correct but will entertain counterarguments. Either way is easy. Other than adding the missing variables (second line of the loop), the only change was changing the last line to i from 0. In fact you don't even need that, because i becomes the value of the loop itself, and everything in ivy is an expression:
op fac n =
f = n
:while n=n-1
f = f * n
:end
fac 6
24
Very nice, thanks. I like the colon prefixes, or at least the fact that they don't look like the other colon expressions. I am not sure about the colon not returning entirely, though. The 0 at the end of my original block-structured version was catching the "impossible" case, for when the while loop can't find an answer (for example 'firstmod 14 256 1 1' should return 0). So there were two returns - one inside the while when it finds an answer, and one after the while if it couldn't find an answer. I am not sure how best to do that with the colon-as-break version. It seems like maybe x:y should stay as a return and we could always have a separate :break.
The countercounterargument is that none of these constructs is restricted to user-defined operators any more, meaning it forms a kind of switch expression. That seems powerful So making colon a return would break that symmetry unless it could be made to stop overall execution, which isn't how it's structured in the code. It's almost moving towards having closures, as the code has now acquired the somewhat hidden concept of a block, and the colon operator gives a value to the block. These new constructs are just blocks that execute and then return a value.
It's six of one, half a dozen of the other.
I could add an explicit :return. Maybe that's the way. It's certainly easy to do.
I still have a lot of testing and docs to write, but I'm pretty happy with how it's worked out. This one lingering question is just which way an internal if goes.