A deep dive into APL
curtisautery.appspot.com
curtisautery.appspot.com
As much as I love it I have to say one of the issues with APL is that it was way ahead of it's time. Because of that it struggled to run on computers of that era.
I was introduced to the language in 1982~ish. Like I said, I used it extensively, attended and presented at APL conferences and even have a picture of my younger and dorkier self with Ken Iverson (creator of APL).
This struggle to run on hardware that could not handle the huge expansions and contractions of memory utilization inherent in the way APL works multidimensional data sets like putty meant it could not compete where other languages had no issues at all. On PC's you were limited to 640K of RAM. It would be years before you could have enough memory to almost not care about utilization.
As the language didn't really catch the attention of the CS masses it failed to evolve as it could have over the years. And this is the reason I would suggest today it is not much more than a curiosity.
I'm sure there are some out there using it professionally. If I were to guess i'd say it must be mostly companies with a significant installed based of APL software they don't dare try to rewrite.
I firmly believe that the future of computing has to be in an APL-like language. By this I mean that we need to evolve to a notation for computing, rather than text for computing. Iverson himself wrote an excellent paper titled "Notation as a Tool for Thought".
The issue is that in order to evolve APL one has to have a deep understanding of APL. And, frankly, there are but a few of us around who have that understanding. Not sure how many of this group would embark on the mission to create a true next-generation APL worthy of it's lineage.
I read and I smile every time I see the language come up on HN. I taught my kids some APL and they are always blown away by it. Not sure where to go from here.
Here's a paper by Ken Iverson about the power of APL notation:
http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...
Why does J exist?
Back in the mid 80's (I don't remember exactly) dealing with APL on IBM PC's was not easy. You really had to want to run APL.
For example, we had to hack the equivalent of today's graphics card to replace the character ROM with one programmed to display APL characters. The more advanced modification allowed you to throw a mechanical switch and go between APL and non-APL characters.
Printing APL characters required using very specific printers and changing the print wheel or ball (IBM printers) with versions having APL characters.
Again, you really had to want to run APL to endure this. And, that, of course, affected adoption. You couldn't run APL on any random IBM PC or clone on a desk.
So, Iverson, despite identifying notation as one of the more powerful features of APL, ends-up "going commercial" by transliterating APL symbols into combinations of ASCII characters. Now you could run something that behaved like APL on any computer. And, of course, it was a complete abomination. Terrible thing.
I think I can say the APL community rejected J almost universally. Doing this was a terrible idea. And a short-sighted one at that. It wasn't long til all computers had the ability to display expanded character sets and eventually full graphical canvases where anything was possible.
J was a commercial reaction to a hardware problem that evaporated very quickly. J was not a commercial success for reasons obvious to those of us who used APL professionally every day for years: It was a hot mess and almost diametrically opposed to what made APL so incredible to use in solving problems through computing.
I would stay far away from J. As brilliant as Iverson had to be to create APL when he did, J, as far as I am concerned, was an almost unforgivable mistake.
I appreciate that Dyalog is free for non-commercial use, but I think that part of what makes a programming language successful is if people can start using it in small ways to make their work better. For instance, at my previous job we started using Go for small things and it eventually took on a larger role once we saw how well it worked out in practice. Had we needed to pay to use Go for those small things, we never would have even tried it in the first place. I realize that the Dyalog company needs to actually make money somehow, but I wonder if they are aware of this problem. I did email Dyalog to see if using Dyalog for my work at a non-profit constituted commercial use, but they said that it did. :(
Edit: The reason why I haven't used GNU APL is because it seems like getting it to work under Windows will be difficult, and my work is unfortunately a Windows environment. Maybe I should give it a shot anyway.
And I agree, I would pay, even if it's not that much. The commercial license comes with a too steep price tag. I'd rather opensource my code or contribute where I can.
For the past few years I've been telling people about the APL family of languages. The clincher for me was seeing the video of an APL version of Conway's Life mentioned in the submission. The impressive part wasn't its brevity, it was how they approached the problem.
In APL you have a 'rotate' operator that shifts data in a particular direction. If you have a vector and you rotate it once, every element moves to the next position and the last element then becomes the first.
The nice thing about APL is that most operations work on data regardless of its dimensionality. So, to do Conway's Life, you take your 2D matrix of cells and produce rotations of it in eight directions (N,NE,E,SE,S,SW,W,NW). You then take those rotated versions of the matrix along with the original and conceptually stack them. Then, for each grid point, you sum downward, producing a new matrix that contains the neighborhood count of the original matrix. From that you can create the next Life generation.
This sort of problem doesn't come up everyday, but the thing that I think is profound is that the existence of these operations allows us to think about problems in different, possibly simpler ways. They are untapped potential and they could be as well known as map and fold.
APL and its derived languages are hard to approach but there isn't much that keeps us from importing the data structures and operations in more approachable languages.
Do you believe that refactoring a large APL codebase would be inherently easier than something like, a large legacy C++ codebase?
What is the relative complexity of comparing, say 1000 lines of APL to 10K lines of C++?
I remember reading an interview between Arthur Whitney and Bryan Cantrill where they mentioned something about recognizing idioms in the dense code much more easily in K than in something like C because it took so many less characters. Do you see any sort of refactoring advantage to that?
I've also recently seen work on the Co-dfns compiler in APL where the author mentioned that APL allowed him to easily refactor compared to traditional codebase, and looking at the github library, there is something like 3 million edited lines over the span of several years in a codebase this is a few thousand lines of code. I find this fascinating because my hope is to eventually start a small software business and I think reducing complexity in the number one priority in order to make it sustainable in the small (the goal isn't to have a team of 50 developers).
Thoughts?
I think array languages, or at least their operation set and idioms, will move into the mainstream in the same way that functional is, but it will take time. Sustainability for your business would be more an issue of hiring and retaining talent.
Reach out if you want to talk about this more: @mfeathers
APL makes you see and envision computational problem solving differently than, say C. Use it enough and your brain starts thinking in patterns, shapes, vectors and matrices being "zippered" together or apart, contorted and distorted.
Take a matrix of values and hit it with another matrix of 1's and 0's to select elements and then flip it, slice it, convert it to a vector and combine it with another vector to form a new matrix, then scale every element and apply a polyphase FIR filter across the rows using another matrix for the coefficients to then arrive at a vector containing your answer. This is made-up, of course, but that's how you start thinking, you start seeing parallel computing in your head and you can reach for it instantly with a notation that allows your hands to describe what you just imagined with a few well-selected symbols. No other language sends you on these flights.
It is truly seeing and approaching computational problems from a very different perspective. And the notation makes it comparable to composing music rather than going through the ugly mechanics of text-based programming languages.
I find it hard to explain to those who have never experienced this revelation of sorts. Watching a few videos and playing around with APL isn't enough. If I had to guess I'd say someone would have to work with it on a daily basis for about a year to achieve that mental shift.
Again, no different from musical notation. It is impossible to explain or experience how you see music once your brain can look at a page full of funny symbols and your mind starts to hear the music. The relationship with the piano, guitar or other instrument changes once that mental connection requires no thought at all.
Getting there with APL takes time. For example, you need to be able to sight read idioms like thee following much as a musician learns to read a two hand chord and instantly place their fingers exactly as required on the piano, without though.
http://docs.dyalog.com/14.0/Dyalog%20APL%20Idioms.pdf
or a large enough subset of these:
http://aplwiki.com/FinnAplIdiomLibrary
Back then, a lot of us used to walk around with a small pocket-sized FinnAPL idiom book in our pocket and had the FinnAPL idiom library book on our desk.
For people interested in Byzantine music, the notation can seem imposing at first -- especially to people who already know western notation. Much effort has gone into translating Byzantine music into western notation, but some problems arise. First, some Byzantine scales use very different pitches compared to a western equal tempered scale. Second, the rhythms in Byzantine music can involve syncopation or other rhythms that can be difficult to notate using western rhythmic symbols. Finally, Byzantine notation is optimized for depicting melody, while western notation is focused on harmony. There is simply more unnecessary visual noise in writing Byzantine music in western notation.
That last point resonates with your talk of idioms. While Byzantine music may seem to have many neumes for a given musical phrase, there are many idiomatic combinations of pitch-changing and rhythmic neumes together. As such, what would be read in Western notation with many individual notes and rhythmic markings, becomes in Byzantine notation a single "word".
If you're interested in seeing how these systems of notation compare, look at the following hymn: http://www.cappellaromana.org/wp-content/uploads/2014/04/Che... The neumes are in red at the top, with a simple western interpretation on the first western music staff and an ornamented interpretation on the bottom staff. Comparing the neumes to ornamented western interpretation (which represents the full Byzantine ethos, or style), we can see that significantly more information is contained in the sparser Byzantine neumes.
Anyway, you've convinced me to learn APL because I now see how similar the arguments for this notation are to my own arguments for using Byzantine notation. Thank you for your insight.
Also, the <- instead of = in R comes from APL, although that's relatively minor. :)
[1] https://scottlocklin.wordpress.com/2013/07/28/ruins-of-forgo...
This was an amazing combination of languages to have in my toolbox simultaneously. The mental calisthenics alone were truly enjoyable to me.
Here's the cache: https://webcache.googleusercontent.com/search?q=cache:K-e7Jh...
Later they say: "Under this implicit lifting, the iteration space is the argument frame rather than a sequence of loop indices." So if I understand correctly, we have iteration, but no loop. But that doesn't seem like a really important distinction...what am I missing?
Abstract iteration is useful because it results in programs with fewer "moving parts"- no loop induction variables to misplace or mutate in the middle of a loop body. Programs are necessarily expressed in a more rigid manner and some irregular algorithms can be difficult to express.
Summing a vector with an explicit loop in K (very non-idiomatic!):
r:0;i:0; do[#v;r+:v@i;i+:1]; r
+/v
The real reason we like +/v besides less typing; it can be handled with special code which runs close to the theoretical machine speed. Lots of small places and languages this fact can be exploited in. R and Matlab basically have a subset of operations you can do +/v type things with. APL is the main class of languages where this sort of thing is built into the semantics of the language. If you're dealing with numerics in an interpreted language, it should be built into the semantics of your language, and that's how you should do things. Really it should be in compiled languages too, and that's how people should reason about code, but it's probably asking too much since APL has only been around since the 70s...
This is just another way of saying "we don't have a compiler, so don't process data at the element level if you want speed".
It is not an advantage of the language, but a disadvantage.
If you have a compiler, then it's only valid for aggressive, machine-specific optimizations. This is articulated by statements like "the library function is marginally faster than an open coded loop, because it uses some inline assembly that takes advantage of vectorized instructions on CPU X".
If I write an FFT routine in C myself, it will not lose that badly to some BLAS/LAPACK routine.
I encourage you to try writing an FFT routine in C yourself and compare it to FFTW, where they basically wrote a compiler for doing FFTs. It's also worth doing in an interpreted language in an array-wise fashion versus with a for-loop. You should get something like a factor of 100,000 speed up.
What is the alternative, if there is no canned procedure for it?
The procedure has to be written somewhere, somehow, in some language.
If compilers are silly, assembly, I guess?
This is basically common to all languages with a strong emphasis on functional programming. Instead of looping, you perform operations directly on the arrays/matrices, and in fact APL and J are focused on matrix manipulation.
Also modern Fortran falls into this category. (I mention it because it's far from a functional language.)
Compare to an vectorizing/parallelizing an explicit loop, about which there have been tens if not hundreds of PhD dissertations, and it is still not a solved problem.
This is why "for x in ..." in Python/C#, and even the "map" variants, are still inferior to APL/J/K: the facts that iteration order is predefined, and that the iteration itself my terminate prematurely, make it extremely hard for the compiler to optimize, whereas in most cases, neither consideration matters.
My only experience with APL-like languages was playing with K for a few months. It's amazing, no other language can do so much in a few characters. Here's a list of hundreds of snippets: http://code.kx.com/wiki/Qidioms
To give a taste of K style, I'll try to explain one of those snippets here. The problem statement is to merge three arrays x, y, z under control of another array g. Don't worry, it will make sense in a moment. These are the definitions of x, y, z and g, followed by one line of code solving the problem, and the result:
x:"abcd"
y:"123456789"
z:"zz"
g:"101121211010101"
(x,y,z)[<<g]
"1a23z4z56b7c8d9"
But the really clever bit is <<g. A single invocation of < returns the sorting permutation of an array, i.e. an array of indices x such that g[x] is sorted. After two invocations of < you get the sorting permutation of the sorting permutation. In other words, the inverse of the sorting permutation. In other words, the permutation that turns sorted g into regular g. In other words, exactly the permutation that you need to mesh x, y and z together!
By any reasonable programmer's standard, that's way too much cleverness. But if you want a lot of functionality in a few characters, that's the price to pay, and K programmers seem happy to pay it. It's also really fast, because you're combining optimized bulk operations, and dropping down to individual elements only in special cases.
Clarity in function names is one of the main reasons I prefer Lisp and Scheme over languages like APL, K, and Haskell, which seem to favor the use of something like a mathematical notation, which I've always found obfuscating. This obfuscation is made worse by the aversion to comments that I've seen in some of these languages, while in Lisp and Scheme, the verbose and explicit function names are in a way self-documenting.
For someone who prefers a clear and explicit programming style, the terseness of some programming languages is a real turnoff.
ordinal: <<:
(x,y,z)[ordinal g]
"1a23z4z56b7c8d9"
(x,y,z)ordinal g
"1a23z4z56b7c8d9"
$ txr
This is the TXR Lisp interactive listener of TXR 173.
Use the :quit command or type Ctrl-D on empty line to exit.
1> (let ((l '#"abcd 123456789 zz")
(i '(1 0 1 1 2 1 2 1 1 0 1 0 1 0 1)))
(gun (pop [l (pop i)])))
(#\1 #\a #\2 #\3 #\z #\4 #\z #\5 #\6 #\b #\7 #\c #\8 #\d #\9)
2> (let ((l '#"abcd 123456789 zz")
(i '(1 0 1 1 2 1 2 1 1 0 1 0 1 0 1)))
(cat-str (gun (pop [l (pop i)]))))
"1a23z4z56b7c8d9"
The expression uses side effects. The pop macro is straight of ANSI CL. Except, in TXR Lisp, list processing stuff like `pop` works on other sequences such as character strings: we can pop the letter a out of a place which holds "abcd", leaving "bcd" in that place. This approach just "popped into my head" immediately.
We also have a syntactic [...] which gives us indexing (and other things).
We also have #"..." which is a "word list literal". Simply, #"foo bar baz" means ("foo" "bar" "baz"). Note there is no quote there to prevent the evaluation of this as a form; so we still have to use one.
I won't bother implementing the apparent requirement that the indices be digit characters from a string; I consider it a serious blemish on the language, if it's doing it implicitly. We can map a string of ASCII digits to the corresponding values like this:
3> [mapcar chr-digit "01234"]
(0 1 2 3 4)
There's no such requirement, < (and by extension <<) returns the same result for 0 1 0 2, "0102" or "abac".
Obviously, there is here a language-level requirement in K that 0, "0" or "a" all denote an index zero, at least in the exemplified situation.
Though that may help get points on http://codegolf.stackexchange.com, it comes across as rather arbitrary.
We could easily acheive the same thing without pushing it into the language, at the cost of making a function call, which could have a one-letter name.
12> (defun $ (x)
(cond
((numberp x) x)
((chr-digit x))
((chr-isalpha x) (- (chr-tolower x) #\a))))
13> ($ #\b)
1
14> [mapcar $ "cdba"]
(2 3 1 0)
15> [mapcar $ #(1 3 9 5)]
#(1 3 9 5)
16> [mapcar $ "012a3"]
(0 1 2 0 3)
no, 0 just sorts before 1, "0" before "1" and "a" before "b"
"Auto-indexifying" a sequence in this way does seem like a useful little operation to have.
[1] http://www.mirrorservice.org/sites/www.bitsavers.org/pdf/ibm...
[1]: https://en.wikipedia.org/wiki/Kdb%2B
http://www.timestored.com/kdb-guides/kdb-database-intro
If you want to dive in and try it, I've also made a video tutorial here:
http://www.timestored.com/kdb-guides/getting-started-kdb
Even if you don't use it, it's an interesting language to study as it's significantly different to the common java/python etc. The one drawback is that for commercial use it's very expensive. Other "modern" APL like languages that are available free include J and kona (open source K).
APL has a small number of very flexible operations, and the key to using APL efficiently lies in understanding these primitives to achieve your goal. Once you learn them, it's more comfortable to use than learning all the intricacies of the R language.
I wouldn't recommend anyone writing a full application in it though. But then again, I don't think anyone uses R for that purpose either.
As an example (which I believe I mentioned last time APL came up on HN) is that one of my solutions to last year's Google Code Jam was a single short line of APL, but then there was about 20 lines of supporting code just to load the dataset and format the output so that is exactly matched the correct format for the submission.
Is my suspicion correct?
BTW: A mere 20 lines for format conversion is very good. Although by APL standards, it might be terrible.
And more to the point, I wouldn't assume that kOS would be closer to Unix/Windows than Forth/SmallTalk/Mesa etc.
I think the issue is that there's no name for that kind of software which are just programs that run on bare metal. So everyone just call it an "OS" - including embedded system software vendors even though what is being sold is really just a library.
But often you have no kernel, no drivers, no resource management, no filesystem, no processes... All features one would expect from an operating system.
Furthermore, operating systems in the generally accepted definition are not supposed to include an interpreter or a compiler. They are not supposed to be interpreters or compilers.
So that's not hair-splitting at all. Those systems are really distinct from operating systems.
#(*<<#$**$[x;]&^^;
It's available on MELPA as gnu-apl-mode, or you can get it here: https://github.com/lokedhs/gnu-apl-mode
As poor as this video is (and the last time I posted it I believe I said I was going to make a new one), it does illustrate some of the features: https://www.youtube.com/watch?v=yP4A5CKITnM
nnoremap <buffer> <C-P> :write !cat - <(echo ")OFF") \| apl --script<CR>
* You shoot yourself in the foot and then spend all day figuring out how to do it in fewer characters.
* You hear a gunshot and there's a hole in your foot, but you don't remember enough linear algebra to understand what happened.
[0] http://www.toodarkpark.org/computers/humor/shoot-self-in-foo...
http://www.vetta.org/2008/05/scipy-the-embarrassing-way-to-c...