Hacker News Reader

Comment by bitminer | Hacker News Reader

I remember APL as part of learning how to program at my high school in the early 1970s.

I could touch type APL on the IBM 2741 text terminals (basically Selectric typewriters with serial interface.). And could compose simpler APL codes at that speed.

The principal weakness was APLs narrow view of data type. Text was a 3rd class citizen. There was no substring searching in the early IBM implementation. As a result one had to:

  Form a cross product of text with the substring, testing for equality of each character

  Rotate each row of the cross product by n steps where n is the row number

  (This aligns the tests along columns)

  Perform AND reduction along the columns to find the full matches.

None of this was intuitive and no I didn't invent that method.

View on HN

> None of this was intuitive

It's extremely intuitive!

    ⌊/(⍳≢b)⊖a∘.=b

Let me illustrate why with q:

    q)a:"this is some cake i like"
    q)b:"cake"

Form a cross product of text with the substring, testing for equality of each character

    q)a=/:b
    000000000000010000000000b
    000000000000001000000000b
    000000000000000100000010b
    000000000001000010000001b

Rotate each row of the cross product by n steps where n is the row number

    q)(til n:count b) rotate' a=/:b
    000000000000010000000000b
    000000000000010000000000b
    000000000000010000001000b
    000000001000010000001000b

Perform AND reduction along the columns to find the full matches.

    q)(&/) (til n:count b) rotate' a=/:b
    000000000000010000000000b

And there we have it. A naive string search in an array language.

Now some interesting advantages fall out of rediscovering this:

- It's obviously parallelisable: The "obvious" (iterative) solution in other languages isn't, and without some difficulty it isn't clear where the work can be split up.

- It uses "outer product" with compare = instead of multiplication × -- an experienced programmer might forget how deeply satisfying it is when first learning how to compose operators

- With some thought it gives a programmer ideas on how they can do string search even faster. Fast string search in an iterative language doesn't look anything like the naive solution.

b⍷a (b find-in a) is useful enough that an experienced programmer should expect a "modern" language to implement it (in q it's called "ss", other languages of course call it different things) but it is far from necessary, and we might cheat ourselves of something. After all, when we are experienced enough to see these things as obvious, other things become obvious as well.

When I was in high school in the 70s I got to attend a week of programming classes at U Waterloo. I had never programmed before. My first programming language was APL. We sat for hours in front of IBM typewriters with strange symbols, trying to write simple programs. The noise from a roomfull of typewriters still rang in my ears at night.

I didn't learn much, sadly, but it sure piqued my interest in programming.

APL is a great language, but it shouldn't be the first one you meet.

Reply on news.ycombinator.com