Suggestivity and Idioms in APL

https://www.sacrideo.us/suggestivity-and-idioms-in-apl/

by mr_tyzic • 3 years ago

74 15 3 years ago

I walked in, realized just how advanced this was and then proceeded to read through the same way I pan through the Abstract Art section of the museum.

I freaking love APL and would love to learn it, but it is so incredibly jarring not knowing anything about the syntax.

jph00• 3 years ago

I have a video series that covers every glyph in Dyalog APL, if you're interested in learning APL syntax:

https://www.youtube.com/playlist?list=PLfYUBJiXbdtSgU6S_3l6p...

There's also a concise guide covering every glyph, which if read in order only ever uses glyphs in examples that have been covered previously:

https://fastai.github.io/apl-study/

Finally, we have a discussion forum for learners:

https://forums.fast.ai/t/apl-array-programming/97188

boerseth• 3 years ago

I share your sentiments and it is incredible. To an outsider this might as well be a parody of programming blog posts. Such impenetrable syntax taken in stride:

    We can improve this approach by recognizing that we can handle the edge cases by using a catenation:
        ⍸0 1⍷0,⍵
        ⍸1 0⍷⍵,0
    Notice immediately how much better this feels.

Ah yes, how immediate is the feeling, much better, indeed. APL is so ridiculous, you have to love it.

abrudz3• 3 years ago

The syntax is actually quite simple, but you may be confused by the unfamiliar symbols and lack of syntax. 0 1 is simply [0,1] in JSON and ⍵ is the argument name. The other symbols cirrespond to prefix and infix operators. Compare the following JS expression which is syntactically (but not semantically) equivalent to the APL expression below it:

    - [0,1] * 0 ** w
    ⍸  0 1  ⍷ 0 , ⍵

abrudz3• 3 years ago

As for the semantics, here are the equivalent JS functions:

    I =    y  => [...y.keys()].filter((e,i) => y[i])            // ⍸y Indices of trues in y
    E = (x,y) => y.map((e,i) => x.every((e,j) => e == y[i+j]))  // x⍷y mask indicating indices where x Exists as a sub-array in y
    C = (x,y) => [x,y].flat()                                   // x,y Catenate x and y into a single array
    
    w = [1,1,1,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1]
    I(E([0,1],C(0,w)))  // [0,5,9,11,16]

Now, if I, E, and C were prefix/infix JS operators, with x being the left argument (if any) and y being the right argument, we'd write:

    I([0,1] E (0 C w))

All APL operators have long right scope, so we don't need to parenthesise right arguments:

    I [0,1] E 0 C w  // same syntax as APL's ⍸ 0 1 ⍷ 0 , ⍵

Alternatively, you can see the infix operators as being methods of all types:

   I([0,1].E(0.C(w)))

Now we remove all the .() noise:

   I [0,1] E 0 C w  // same syntax as APL's ⍸ 0 1 ⍷ 0 , ⍵

Wasn't that hard, was it?

skruger• 3 years ago

If you are interested in learning APL, take a look at https://xpqz.github.io/learnapl/intro.html

Disclaimer: author

abrudz3• 3 years ago

I'd be happy to teach you; just let me know.

The syntax is in fact quite simple, and the semantics of the core language is mnemonic and limited, so I believe that a reasonably intelligent person can learn the entire core lanuage in 24 hours of dedicated studies. Subtract a few if the student has a knack for mathematics, but add a few if they have a CS degree.

jcrites3• 3 years ago

Not knowing APL, I unfortunately find the beginning code completely unreadable:

  ⍸(⊃⍵)@0⊣¯1⌽0 1⍷⍵

[Edit: My thought process here is: "This syntax is so difficult that I can't even begin to reason about it even using web search. Can GPT understand it? Yep, it seems to."

"Could this algorithm be more clearly expressed in another language? Yes, it looks like it."]

----

I asked ChatGPT (4) to explain this expression (Prompt: "Explain what this APL code does: ___"). In case others find it helpful, the response is below.

First, let's break down each symbol:

1. ⍵ represents the right argument of a function.

2. ⊃ is the disclose or first function, which picks the first item of its argument.

3. ⍷ is the "where" function, which returns a boolean mask of where its left argument appears in its right argument.

4. ⌽ is the reverse function. With the argument ¯1, it rotates its argument one place to the right.

5. @ is the "at" function, which modifies certain elements of an array. (⊃⍵)@0⊣ replaces zeros in its right argument with the first element of ⍵.

6. ⊣ is the left function, which returns the left argument, ignoring the right one.

7. ⍸ is the "where" function, which returns the indices where its argument is true (or in the case of numeric data, non-zero).

Now, let's combine these to understand the whole expression:

0 1⍷⍵ returns a boolean mask of where the sequence 0 1 appears in ⍵.

¯1⌽ then rotates this mask one place to the right.

(⊃⍵)@0⊣ replaces zeros in the rotated mask with the first element of ⍵.

Finally, ⍸ returns the indices of non-zero elements in the result.

So, this code is finding the indices in the array ⍵ where a 0 is immediately followed by a 1, and replaces these 0s with the first element of ⍵. It then returns the indices of the non-zero elements in the result.

[Edit: I'm not entirely sure but this explanation might contain an off-by-one error. I don't quite follow APL enough to tell. The translated alternative does for sure though.]

----

On that note, I'll remark that I find APL's syntax to have distinct disadvantages. I know a number of programming languages well, having written production code in them for decades. I've come across basically every mainstream programming language and find them generally readable, even though I don't have much domain knowledge, because they share so many concepts that are typically reflected with similar syntax (for loops, assignments, functions, etc.) Even relatively more "out there" languages like Haskell and Perl are somewhat readable without a ton of domain knowledge.

I find it very difficult to get on board with languages that value terseness of this sort over readability (like in K and APL – especially with APL's special symbols). Code is read so much more than it's written, in general, that transparency is valuable and important – as well as the ability to search for code fragments to understand their meaning.

I asked ChatGPT4 to translate this code into Rust, for example, to see what it would come up with. Here was its literal translation, that relies on mutating the input (analogous to the APL code). This is similar to what you'd get transliterating the code into C/C++/Java:

  fn find_zero_one_and_replace(input: &mut Vec<i32>) -> Vec<usize> {
      let first_element = *input.first().unwrap_or(&0);
      let mut indices = vec![];
      let mut prev_zero_index = None;
  
      for (i, &item) in input.iter().enumerate() {
          if item == 0 {
              prev_zero_index = Some(i);
          } else if item == 1 {
              if let Some(index) = prev_zero_index {
                  input[index] = first_element;
                  indices.push(index);
                  prev_zero_index = None;
              }
          }
      }
      
      indices
  }

[Edit: I haven't checked whether this is correct]

After some back-and-forth, asking it to write a function that doesn't mutate the input, and uses iterators, it comes up with some code that I think is probably readable even if you don't know the language well (barring some particulars of the syntax):

  fn find_zero_one_indices<'a>(input: &'a [i32]) -> impl 
  Iterator<Item = usize> + 'a {
      input.windows(2)
          .enumerate()
          .filter_map(move |(i, window)| {
              if window == &[0, 1] {
                  Some(i+1)
              } else {
                  None
              }
          })
  }

[Edit: This code fails to detect the leading group of `1s` in the input and return a response beginning with `0`. Corrected code might be:]

  fn find_zero_one_indices<'a>(input: &'a [i32]) -> impl Iterator<Item = usize> + 'a {
      let mut previous = 0;
      input.iter().enumerate().filter_map(move |(i, &x)| {
          let result = if previous == 0 && x == 1 { Some(i) } else { None };
          previous = x;
          result
      })
  }

[Edit: The corrected form is arguably less readable than the original due to the need to detect a leading window that doesn't start with `0`. This version somewhat weakens my argument about the clarity of the alternative, but this is still readable. Perhaps someone else with more Rust experience can suggest a simplification.]

I find this readable since "windows" here is a direct reference to the concept of windowing, which is collecting sequences of items from a stream into groups. "Enumerate" iterates over a pair of sequence elements and their indexes: `(i, window)`. These concepts exist in a number of languages.

But if you didn't know what these code elements meant, you could search for them: "rust windows", "rust enumerate", "rust filter_map" and get useful results. The stdlib documentation will be the first or second link. For example, if you don't know what "filter_map" does: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho... (And the same would be true for Java, Python, etc.)

Each of these elements (windows, enumerate, filter) is syntactically joined into a conceptual pipeline, providing a framework for reasoning about how they work, in a paradigm used by many languages.

Finally we have the detection logic: `if window == &[0, 1]`. Hopefully that's readable, and I expect makes this solution easier to understand than any of the other variants.

I may have somewhat missed the point of the article: it goes on to describe how the solution can be generalized in various ways. But this is also likely true of the canonical solutions in many languages: iterators (in particular), anonymous functions, etc. enable code snippets to compose and generalize in many ways as well.

rak15072• 3 years ago

Why has this thing of posting unchecked GPT4 output become popular? It's infuriating. The explanation is wrong, but who cares right?

Oh great I see now they've added yet another APL-on-HN trope: the 'equivalent' (note: it's wrong too!) code in some trendy language (and saying APL/K are unreadable). It's like someone crafted the perfect message to piss me off.

jcrites3• 3 years ago

I checked it insofar as I understand APL and what the algorithm was attempting to do: that the algorithm was attempting to detect and return the index of the first element of every consecutive "[0 1]" pair.

[Edit: OK, I see the mistake is that it should return the index of the `1`, not the `0`. Yes, that's the kind of mistake I'd catch during unit testing, or after more carefully reviewing the code.]

In what way is its explanation wrong? Its summary of the algorithm is:

So, this code is finding the indices in the array ⍵ where a 0 is immediately followed by a 1, and replaces these 0s with the first element of ⍵. It then returns the indices of the non-zero elements in the result.

That summary seemed to correctly describe the algorithm, and seemed consistent with the article, so I assumed that its breakdown was correct. I don't understand the individual symbols or operators of APL and can't quickly fact-check the answer, but given that the summary was consistent with the article, it seemed to indicate that GPT had deduced (with no context from the article) what the algorithm was doing in human terms – in other words, whether it was able to "read" the APL code.

Whether it's actually mutating the input or not, I don't know. Its description of the transformation seemed to check out, though.

Regardless of whether its breakdown is right or wrong, my true intended commentary is about the opacity of the syntax and the difficulty in reading it (which I elaborated on via an edit, after your comment was posted but before seeing it).

mk12• 3 years ago

For anyone looking to get into array programming, I'd recommend https://mlochbaum.github.io/BQN/. I'm no expert but I had a lot of fun using it for Advent of Code last year. I found it to be a lot more sensible and modern feeling than J (the only other one I've tried).

Suggestivity and Idioms in APL

Related Stories