Condition controlled loops

How do you write APL code for “do-while” type problems? Well, modern APL does actually have :While-:EndWhile and :Repeat-:Until constructs. But we have other options: like the ⍣ operator, and recursion, which isn’t bad in APL, as you can use the optimised tail-recursion.

Power ⍣

About ⍣, it is important to note that it always applies its left operand at least once. Let’s take a very simple (pun intended) example. Let’s say we have an array like ⊂⊂⊂⊂2 2⍴'ok'. We want to disclose it until it is simple. If we do ⊃⍣≡ we’ll end up with ‘o’.

Another common pitfall is to use ⍵ in the right operand (the one that answers “are we done?”) instead of ⍺.

⊃⍣{1≥|≡⍺} ⊂⊂⊂⊂2 2⍴'ok'

ok
ok

The problem is that our input might have 0 levels of nesting; then we fail:

⊃⍣{1≥|≡⍺} 2 2⍴'ok'

o

This is because ⊃ is being applied once before we even ask if we’re done. If instead we move the test inside the left operand we get:

{1≥|≡⍵:⍵ ⋄ ⊃⍵}⍣≡ 2 2⍴'ok'

ok
ok

The left operand will become a no-op when we’re done. In fact, we can even use the power operator instead of the guard!

{⊃⍣(1<|≡⍵)⊢⍵}⍣≡⊂⊂⊂⊂2 2⍴'ok'
{⊃⍣(1<|≡⍵)⊢⍵}⍣≡ 2 2⍴'ok'

ok
ok

ok
ok

Of course, you don’t have to write everything inline. You could use a separate function for the main processing. In your left operand, you can of course place your done-condition at the top or at the bottom, or anywhere else. But let’s say instead that we don’t want the condition to be based on the data processed. Rather, we want to periodically read an outside value to decide whether to continue or not.

You can try this in your local APL:

done←0 ⋄ {⎕←⍵⊣⎕dl 5}⍣{done}&'work'

It will run in the background, printing “work” every 5 seconds. Of course, it didn’t need to be a single value in {done}. It could be an entire function that figures out if we’re done based on a bunch of stuff.

Recursion ∇

Recursion can be done simply by calling the function name. Dfns can also call themselves using ∇. The benefit of ∇ is that you can rename the function or leave it anonymous. We should also mention ∇∇. If you are writing your operators, you might want the operator’s code to “use” itself. You do that with ∇∇. Inside such a dop, you can also use ∇ as a shortcut for ⍺⍺∇∇ or ⍺⍺∇∇⍵⍵ depending on operator valence.

Other than this, it is actually much the same as with ⍣: Establish the stop condition with a guard (or a control structure in a tradfn), and do the work otherwise.

The important thing is that APL detects when the final result will be used unmodified as the result of the previous iteration. Let’s say we wanted the beginning number of the 7-long sequence: {16=+/'2'=⍕⍵:⍵⋄⊃∇1+⍵}⍳7. Now APL has to keep track of where came from so we can apply that final ⊃. Can we detect a tail call? Yes. You can try this:

{⎕←≢⎕SI ⋄ 16=+/'2'=⍕⍵:⍵ ⋄ ∇ 1+⍵}2000+⍳7

It starts searching at 2000 to prevent output flooding. ⎕SI is the State Indicator, or stack. Every time around the loop, we count the frames on the stack and print that. It’ll print 1 every time, because the stack “forgets” about the previous call every time.

However, if you try it with the ⊃, then:

{⎕←≢⎕SI ⋄ 16=+/'2'=⍕⍵:⍵ ⋄ ⊃ ∇ 1+⍵}2000+⍳7 

you should be able to observe the stack frames increasing.

Let’s try implementing Fib n (which returns the n first Fibonacci numbers) using ⍣ and recursion. We can factor out the fundamental Fibonacci operation, which sums the last two elements of a vector, and tacks on the result:

∆←{⍵,+/¯2↑⍵}  ⍝ Fundamental Fibonacci function 

Using this, we can write a neatly tail-recursive Fibonacci function – note that all processing is to the right of the ∇:

{⍺≤≢⍵:⍺↑⍵ ⋄ ⍺∇∆⍵}∘1⊢ 10 ⍝ Tail-recursive

1 1 2 3 5 8 13 21 34 55

And here’s a clever application of the power operator:

{⍵↑∆⍣⍵⊢1 1} 10 ⍝ append 1 1, n times

1 1 2 3 5 8 13 21 34 55