Four Solutions to a Trivial Problem - Guy Steele Jr.

Guy Steele Jr. worked on a language called "Fortress." There are a few good talks that he gives: - (toy problem) ▶ this video - (parallelism) link - (languages) link

This type of interviewing style is bullshit. It means the interviewer knows a better solution that is "clever" and expects you to either have the same cleverness epiphany on the spot or to have studied this question. Neither is actually very useful as a hiring criterion. Guy Steele gave an incredibly interesting guest talk[1] at google about four different ways to solve this exact problem, and the fact that it's an interesting enough topic for an hour long google talk should probably be a clue that you shouldn't be expected to invent the best solution on the whiteboard in 40 minutes. [1] ▶ this video

I think APL has a lot to teach us about parallel (specifically GPU) programming. I've rewatched a few talks with Aaron Hsu and listened to his arraycast podcast[1]. In researching an upcoming blog post on monoids, I tried implementing the problem in Guy Steele's "Four Solutions to a Trivial Problem" talk[2] in APL (actually I tried GNU APL for this, because I didn't need anything fancy). This is what I came up with: +/((⌽⌈\⌽a)⌊⌈\a)-a That in turn should be fully parallelizable and run fast on the GPU, as it's based on a couple scan (generalized prefix sum) operations. There's a considerable amount of DNA from APL in modern compiler-based machine learning frameworks, mostly by way of numpy. Dr. Hsu makes a good case that APL has quite a bit of power which is considerably diluted in later spins such as numpy. I'm especially fond of the power (⍣) operator[3], which represents parallel iteration and I think can often be translated to a per-thread while or for loop in a compute shader. I don't believe numpy has anything quite like that (but feel free to correct me!). [1]: link [2]: ▶ this video [3]: link

Hi, the author here. One of the hidden messages of the introduction is: watch Guy Steele's talks [1][2][3] if you are interested in data parallelism! These talks are not Julia-specific and the idea is applicable and very useful in any languages. My libraries are heavily inspired by these talks. Of course, if you haven't used Julia yet, it'd be great if (data) parallelism gives you an excuse to try it out! It has a fantastic foundation for composable multi-threaded parallelism [4]. [1] How to Think about Parallel Programming: Not! link [2] Four Solutions to a Trivial Problem ▶ this video [3] Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful link [4] Announcing composable multi-threaded parallelism in Julia link

associativity is the key to parallelism Four Solutions to a Trivial Problem - Guy Steele Jr. ▶ this video (using a monoid-cached tree)

I enjoyed this talk along the same lines by Guy Steele, regarding not necessarily forcing a sequential solution to a non-sequential problem: Four Solutions to a Trivial Problem - Guy Steele Jr.: ▶ this video Look for steps that are commutative and/or associative in the problem to exploit parallelism.

Guy Steele [1] sometimes mentions it. He gave an interesting Google Tech Talk called Four Solutions to a Trivial Problem [2], and at 1:59 [3] he said: Also, algebraic properties are important. I've got a background in applied algebra, and I think that has informed my programming. And I think that making programmers aware of algebraic properties of their code, and communicating some of those properties to the compiler, may be worthwhile. The language Fortress [4], which he was one of the language designers of, allowed one to explicitly provide the compiler with such information - you could say that a certain operation was distributive or associative for instance, and the compiler could then do some refactorings and optimizations taking this knowledge into account. [1] link . [2] ▶ this video [3] ▶ this video [4] link