Hacker News Reader

Comment by pavlov | Hacker News Reader

"J might overly encourage programmers to use arrays when another data structure would be a better fit."

I feel this is actually a distinct advantage of the APL/J model: it eliminates boring data structure bikeshedding.

If I were Supreme Dictator of Tech, I'd mandate APL as the language for all whiteboard interviews. Everyone would have learn it, but at least it would be far more interesting to study than the "Leetcode / Cracking the Code Interview" type material that's currently being prescribed.

View on HN

I deal with sparse graph data structures a lot, as molecular graphs, with a maximum degree of about 5. While graphs can be represented as an adjacency matrix, many of the algorithms become suboptimal in that representation, eg, finding the list of 1-away neighbors becomes an O(n) operation rather than O(1), in the number of nodes.

Now, I'm not saying that these graphs or algorithms can't be represented in APL. But, as an example, consider the problem of how to find strongly connected components in a graph, which is something that is not an unreasonable interview topic for an intermediate developer in my field.

An implementation for Dyalog APL is at https://dfns.dyalog.com/c_scc.htm with commentary at https://dfns.dyalog.com/n_scc.htm . It requires about 30 lines of code, starting:

  scc←{⎕ML←1                                  ⍝ Strongly connected components.
                                              ⍝ (Tarjan)
    loop←{                                  ⍝ for each vertex in graph G
        vert←{⍺ conn⍣(0=X ⍺⊃⍵)⊢⍵}           ⍝ connection of unvisited vertex ⍺
        ⊃vert/(⌽⍳⍴G),⊂⍵                     ⍝   for each vertex in G
    }                                       ⍝ :: T ← ∇ T

    conn←{v←⍺                               ⍝ connection of vertex v
        T0←v trace ⍵                        ⍝ optional tracing
        T1←x1 v push v Lx v Xx T0           ⍝ successor state for x S L and X
        T2←↑{w←⍺                            ⍝ edge v → w
            min_L←{(⍺ w⊃⍵)⌊@(⊂L v)⊢⍵}       ⍝ L[v] ⌊← ⍺[w]
            0=X w⊃⍵:L min_L w conn ⍵        ⍝ w not connected: depth-first trav
            X min_L⍣(w∊S⊃⍵)⊢⍵               ⍝ low-link if w on stack
        }/(⌽v⊃G),⊂T1                        ⍝ for each edge from vertex v
        root←(L v⊃T2)=X v⊃T2                ⍝ is a root vertex?
        v comp⍣root⊢T2                      ⍝ new component if root
    }                                       ⍝ :: T ← v ∇ T
     ...

The pseuocode on the Tarjan's strongly connected components algorithm Wikipedia page (not counting "end if", "end for", etc. lines) is shorter.

One Python implementation is at https://codereview.stackexchange.com/questions/46832/strongl... where you can see it's slightly shorter than the APL version and - I argue - easier to understand.

Now, the APL commentary page points out:

> Nick Nikolov provides this alternative one-liner, which uses the transitive closure of the adjacency matrix (see →Graphs←).

    scc←{(∪⍳⊢)↓∧∘⍉⍨∨.∧⍨⍣≡i∘.∊⍵,¨i←⍳≢⍵}
    ⍝    ·     ·   ·     ·   ·  i←⍳≢⍵   vertex indices
    ⍝    ·     ·   ·     ·   ⍵,¨i   ·   consider each vertex a SCC by itself
    ⍝    ·     ·   ·     i∘.∊   ·   ·   neighbour lists to adjacency matrix
    ⍝    ·     ·   ∨.∧⍨⍣≡   ·   ·   ·   transitive closure: g[x;y] ←→ path x → y
    ⍝    ·     ∧∘⍉⍨ ·   ·   ·   ·   ·   ... and from y to x
    ⍝    (∪⍳⊢)↓ ·   ·   ·   ·   ·   ·   renumbering of component numbers

> The version is very good for small graphs but its space and time requirements grow rapidly as the size increases.

Which, I believe (not knowing more than a trivial amount of APL) is a consequence of using an array data structure rather than something which is a better fit.

Can't you use sparse arrays?

I don't understand your question.

I think you're asking if APL and/or J supports a sparse matrix representation, such that the one-liner scales as expected for the Tarjan algorithm.

As I wrote, I don't know more than a trivial amount of APL, and cannot answer that question.

However, I infer that if that were the case then the links I pointed to would use a sparse array implementation and simple one-liner, instead of the 30 or so lines of APL.

Perhaps pavlov, as the next Supreme Dictator of Tech, could show us an appropriate whiteboard interview solution for this problem in APL?

I can't speak for APL, but J does have a standardized sparse-array format, and a verb for converting normal arrays to sparse and back. Most operations work on both kinds of arrays transparently, although (in my limited experience) many ops are quite a bit slower on sparse arrays. Perhaps the performance difference is less significant for huge arrays, but for me it was measurably slower when working with a 1000x1000 table.

Having said that, the sparse format gives you direct access to its internal index (coordinate) array, as well as the value array. So algorithms that can take advantage of these data structures might benefit significantly.

(I also deal with sparse graph data in my dayjob.)

A 1-step traversal is the same complexity for both a linear algebra and vertex- or edge-centered representation. However, you do absolutely need a sparse linear algebra representation and operations (cfr. GraphBLAS mathematical foundations paper).

With the standardization of linear algebra for large graphs in the form of GraphBLAS, it would be interesting to see a sparse extension to APL or J for dealing with large graph analytics. It's already there for Matlab, Python and Julia.

One of the problems I was constantly trying to avoid when using APL (professionally, for real-world applications, not academics) was the explosion of arrays.

You have to understand what the interpreter is doing. Just because you can write a cool one-liner that gets you an answer with one turn of the crank it doesn't mean this is the best solution.

When I started using APL I was using seriously resource-constrained machines of the time (think ~1 MB of RAM rather than 64GB). This makes you far more aware of what's going on behind the curtains.

In many ways this is one of my pet peeves with today's programmers, I think I can say the majority have not been exposed to what might actually be happening at the processor/memory level. This leads to such things as OOP being their default level of abstraction and the explosion of classes and layers. Very soon a simple addition of two numbers takes a thousand clock cycles rather than one.

Anyhow, love APL, I really do, but I have no clue why it shows up so much on HN. These days I would not use it (or much less J) if my life depended on it. Learn it, yes. Definitely. Write some non-trivial stuff with it. Seriously consider using it in a business? No way.

I'd say the same thing about Forth, BTW. Love both languages. No longer good choices for anything other than learning about different ideas.

Taking the tangent further, you write "one of my pet peeves with today's programmers".

As someone who started programming in the 1980s, I've observed both sides of the issue. When I started, the earlier generation complained that 'today's programmers' didn't know anything about the hardware, like being able to re-write the computer to add new hardware capabilities, or to debug the machine by attaching probes to the bus. And they were right ... and mostly irrelevant, as the hardware complexity and reliability increased. Eg, it's much harder to hand solder surface mount than discrete components.

On the other hand, I've had to re-learn programming for modern hardware. I remember when I implemented a string upper-case function like:

    while (*s) {
        *s = toupper(*s);
        s++;
    }

only to find that

    while (*s) {
        if (islower(*s)) {
            *s = toupper(*s);
        }
        s++;
    }

was faster for my use case. Someone had to explain to me the difference between read and write performance - on the machines I learned on, they were both one cycle.

Similarly, I've had to learn (poorly, in an ad hoc fashion) about instruction pipelining and prefetching.

I've therefore concluded that talking about problems with "today's programmers" is more like voicing the age-old complain about "kids these days" then expressing something more fundamental.

Regarding APL, I like the comment at https://prog21.dadgum.com/122.html - "I encourage learning J, if only to make every other language seem easy."

Regarding Forth, see http://yosefk.com/blog/my-history-with-forth-stack-machines.... and commentary at https://news.ycombinator.com/item?id=1680149 .

The exception I'll take with regards to my "today's programmers" comment is that, again, in my opinion, things are not getting better.

The simplest example of this I have is iOS. I wrote an app years ago that required me to implement a genetic solver. Simple enough. Well, not so. Objective-C is so thick and heavy that this thing was a complete dog. This was back in the iPhone 3 days. I needed this solver to produce results in real time, defined as "as quickly as a user could touch a button". This thing was at least an order of magnitude slower than what the app required.

So, I re-coded the thing in plain procedural C++, not OO. Clean, simple fast code. With that change the code ran faster than real time, to the point that I could then add features.

Anyone trained in languages like Objective-C, Python, etc. sees the world through a single OO lens and "programs" by threading together libraries and really chunky slow code. They lack the benefit of understanding the same or more can be achieved by leaving that baggage behind. This is how we end-up with machines operating at GHz that actually slow down despite having massive amounts of memory and resources.

I am not anti-OO, but OO seems to be an inextricable part of bloated code these days.

While I don't believe it's getting worse.

Objective-C dates from the 1980s, and I'm surprised you needed anything from C++ which wasn't available in the C that Objective C supports.

Python doesn't encourage a single OO lens. I've been working with Python since the 1990s, and don't use OO that much. When I teach Python to computational chemists, I deliberately don't touch on "class" or other OO aspects because it doesn't seem that useful for what most people need to do.

I double-checked using the text of "Automate the Boring Stuff" at https://automatetheboringstuff.com/ , which is also for beginners. I found no description of making classes. So I do not accept the idea that Python programmers "[see] the world through a single OO lens".

Certainly there are people with bad habits. I wrote about one of these in a scientific methods paper published just a couple of weeks ago, at https://jcheminf.biomedcentral.com/articles/10.1186/s13321-0... :

> Many search implementations interpret Eq. 1 literally, and represent fingerprints using a set data type and compute the Tanimoto using set operations. This approach often uses a large number of temporary set instances. By comparison, an implementation which represents a fingerprint as a byte string or sequence of machine words uses less memory, has less memory management overhead, and can implement Eq. 2 with a handful of fast bit and arithmetic operations.

But it's not specific to this generation, because I read essentially the same complaints - scratching off "OO" - back around 1991 or so (either in CACM or Dr. Dobbs').

Looking now, I found https://www.drdobbs.com/are-the-emperors-new-clothes-object-... complaining about the slowness of OO software back in 1989.

And "threading together libraries" is, you certainly know, the goal of software re-use. Consider Jon Bentley's classic 1986 paper where Donald Knuth and Doug McIlroy write short program, at https://dl.acm.org/citation.cfm?id=315654 .

> Read a file of text, determine the n most frequently used words, and print out a sorted list of those words along with their frequencies.

As McIlroy comments, "A wise engineering solution would produce—or better, exploit—reusable parts. ... The simple pipeline given above will suffice to get answers right now, not next week or next month. It could well be enough to finish the job. But even for a production project, say for the Library of Congress, it would make a handsome down payment, useful for testing the value of the answers and for smoking out follow-on questions."

Note that converting a boolean matrix m to an adjacency list is easy. In k:

  adj: ,/(!#m),''&:'m

In fact for something like SCC, &:'m is good enough since you are going to iterate over all the rows any way.

Reply on news.ycombinator.com