|
APL and its descendants form an obscure but powerful family of programming languages. They permit writing extremely concise programs, often expressing in a few characters what more conventional languages would take dozens of lines to say. They eschew explicit loops, conditional statements and recursion- typically the bread and butter of programming- in favor of high level built-in operators and functional abstractions. The resulting style of programming is naturally highly parallel and can be easy to optimize. At the same time, the cryptic symbiology, excessively dynamic type systems, heavy operator overloading and relative lack of accessible information can make these languages very hard to approach. Let's learn about Array languages and share our experiences. The three most prominent languages in this family are, in order of creation, APL, J and K: APL APL was designed by Kenneth Iverson in the late 60s. Originally it was meant to be a concise handwritten notation for describing algorithms which unified the notations for vector and matrix arithmetic, logic and set theory, laid out in a book titled A Programming Language. APL introduced a set of special symbols as part of its notation which initially posed some challenges for typesetting and distribution. Notably, the symbols used by APL for "floor" and "ceiling" are now commonplace in mathematics. After teaching with this notation for a number of years, an effort began to implement an interpreter for a simplified form of the notation. In the decades since, APL interpreters have absorbed ideas from functional programming (first-class functions, particularly) and object-oriented programming. Find prime numbers between 1 and R: quote:(~R∊R∘.×R)/R←1↓ιR Compute rows of Pascal's Triangle: quote:Pascal←{0~¨⍨a⌽⊃⌽∊¨0,¨¨a∘!¨a←⌽⍳⍵} The Game of Life in APL: https://www.youtube.com/watch?v=a9xAKttWgP4 A Sudoku solver: https://www.youtube.com/watch?v=DmT80OseAGs J J was a later effort by Iverson which dispensed with a special character set in favor of ASCII digraphs. It features an extremely rich set of mathematical datatypes (arbitrary-precision, rationals, imaginary numbers, etc) and operators. It also includes some features which are largely unique, such as "forks" for expressing complex tacit expressions (expressions which contain no named variables). Calculate the arithmetic mean of a list of numbers: code:code:K K was developed by Arthur Whitney while working at Morgan Stanley, and is now sold commercially by Kx Systems, inc. It feels like a hybrid of APL and Scheme, radically simplified and with a well-earned reputation for being surprisingly fast. K1 was an internal project, K2 was the first independent commercial release, the K3 dialect is targeted by the open-source re-implementation Kona, K4 is the current commercial release, bundled inside kdb+, a high-performance in-memory database. Today, K is used extensively in high-frequency trading applications but is virtually unheard of outside finance and code-golf. Calculate the arithmetic mean of a list of numbers: code:code:code: code:Feel free to discuss APL, J, K and other related languages. If you've never tried programming in this style before, why not give it a spin with one of these browser-based interpreters?
Internet Janitor fucked around with this message at 17:00 on Dec 13, 2015 |
#
?
Dec 1, 2015 21:17
|
|
|
|
| # ? Apr 23, 2024 22:07 |
|
|
I approve of this thread and may yet add something of actual value to it. Though I am not sure at this moment what, though some K3/K4 code may be in the cards if I manage to go through my messy archives.
|
|
#
?
Dec 1, 2015 21:50
|
|
|
Which one should I learn?
|
|
#
?
Dec 1, 2015 23:17
|
|
|
Personally, K is my favorite of the three and the one I found easiest to learn. Fluency in APL requires relearning how to type (or using a special editor), J's use of unbalanced brackets and lots of digraphs makes it tricky to learn to read. K syntax is very simple, regular and familiar in comparison. Unfortanately K also has the fewest high-quality introductory materials available, in no small part due to its proprietary history. You must be mindful of the dialect you're working with, as some operators behave quite differently between, say, K2 and K4. Here are a few materials worth reading if you're up for it:
|
|
#
?
Dec 1, 2015 23:59
|
|
|
Oh, cool! I've been trying to get into K, but put it on hold for a bit in part due to the lack of accessible information and tutorials on the language. I've seen some reference documentation before, but it's not like you can scan it and go "ok I can code K now". These resources look quite neat though so I'll give it another go.
|
|
#
?
Dec 2, 2015 00:30
|
|
|
K4 is confusingly most commonly consumed in the form of KDB+, which includes a slim wrapper on top of K to make it a bit more SQL-like and friendly, (nick)named Q. However, the semantics are all really the same, and the step to learning K4 from learning Q is actually really small (though for a lot of tasks it is not a really necessary step other than for fun). This however means that you can leap into the more available Q reference materials as a first step, launching into K off of that. Then one can recommand the rather nice Q for mortals: http://code.kx.com/wiki/JB:QforMortals2/contents For availability of the propriety version of Q/K, go to kx.com and download the free 32-bit version, when started it will land you at a Q prompt, a single backslash followed by enter drops you down into K4.
|
|
#
?
Dec 2, 2015 08:51
|
|
|
I've been fascinated by APL and its dialects for the past few years. My background is in classic functional programming, and I'm now a researcher in the field of optimising compilers for data-parallel functional programming, and the APL community contains the most experience with writing expressive data-parallel programs. I'm still more of an APL fanboy than a real APL programmer, but I like this function for removing the inner wovels of words:code:For learning K, can anyone recommend a good open source implementation? I've seen Kona before, and even played a little with it, but I was not aware that it implemented an older version of the language. I still need to learn J also. I don't care much about the ASCII-fied syntax, but I've heard that it has made some things cleaner (like working with multidimensional arrays). Some of its features, like trains, have made it into Dyalog APL, though. Finally, a shout out to GNU APL. It's a very good free software implementation of APL, which nobody seems to know about.
|
|
#
?
Dec 2, 2015 13:21
|
|
|
Cybernetic Vermin posted:K4 is confusingly most commonly consumed in the form of KDB+, which includes a slim wrapper on top of K to make it a bit more SQL-like and friendly, (nick)named Q. However, the semantics are all really the same, and the step to learning K4 from learning Q is actually really small (though for a lot of tasks it is not a really necessary step other than for fun). This however means that you can leap into the more available Q reference materials as a first step, launching into K off of that. Then one can recommand the rather nice Q for mortals: http://code.kx.com/wiki/JB:QforMortals2/contents Thanks. I guess I was going at it rear end-backwards, as I wanted to learn K with the end goal of applying it with KDB+ 
|
|
#
?
Dec 2, 2015 16:42
|
|
|
Athas: fyi, APL symbols don't seem to work in code blocks. They work in quote blocks, though. As far as open-source K implementations go, I think Kona and oK are the only ones in existence. There are a handful of "K-like" languages out there, though. For example, Klong.
|
|
#
?
Dec 2, 2015 17:55
|
|
|
To give the thread a touch of content, lets do a small tutorial post on roughly what K4 looks like in not too uncommon use. Let us say we have a variable t containing a list of market data tuples (backtick followed by a string is a symbol, an internalized string,): code:We use unary '+' to flip the list, basically the transpose, i.e. +t is (`IBM`MSFT`IBM`IBM`MSFT`AMZN`MSFT`MSFT;10 101 11 12 90 99 92 90). We take the first element, the symbols themselves, using unary '*', *+t is `IBM`MSFT`IBM`IBM`MSFT`AMZN`MSFT`MSFT. Then we use unary '=', group, to create the occurrence dictionary of the symbols, that is, a dictionary containing the symbols as keys, mapping to the list of indices at which they occur in the original list: code:Then we index the original list with the dictionary, which may make little sense, but the rule of thumb is that in any situation where one would expect an array and supply a dictionary the value part of the dictionary is used as the array, so we get the values from t replacing the indices on the value side: code:code:code:code:code:Now, the above is a bit over-elaborate for the sake of illustration, both in that it would of course be better not to index in all those symbols only to remove them, but more than that if one is actually in KDB+ one would instead turn t into a table and do this as a database operation. The database operation does, however, do pretty much exactly the above; tables are first-class objects in K4, but they are really just an abstracted dictionary of symbols (column names) mapping to arrays of equal length (the actual columns). The way it works is in fact to take the flip of such a dictionary, so if we construct +`sym`val!+t we get +`sym`val!(`IBM`MSFT`IBM`IBM`MSFT`AMZN`MSFT`MSFT;10 101 11 12 90 99 92 90), where the leading plus now signifies that we have sealed it as a table, and can now do: code:So, K4 appears sort of opaque at first glance, but it is actually fantastically transparent in that one can usually see straight through how stuff is done. A good example is the indices on offer on tables, you can have a hash index, partitioned tables, or have tables sorted on a column, which are used to speed up queries. This is however a trivial generalization of flags on arrays, e.g. an array that is sorted manually, or when one requests it, can get the sorted flag, and on such an array a number of operations (comparisons, find) are sped up using binary search. The query processing then just uses the same verbs one would if one were to interact with the table columns like the arrays they are. Any mutation to the array is validated to not violate sorting, and if it does the attribute is silently dropped. This leads to very easy optimizations, but also some responsibility, since e.g. appending a row to a large table in a production database in a way that causes it to lose sorting may just get you fired within minutes  I did a lot of work sort of abusing the transparency of KDB to do stuff like primitive distribution, caching and query optimizations which were only possible thanks to the model being very simple in its building blocks. So, in short, K4 is the coolest thing you'll never use.
|
|
#
?
Dec 2, 2015 19:02
|
|
|
Great writeup, Cybernetic Vermin! I haven't worked with kdb+ myself, but it seems very expressive. How often do you find yourself writing entire programs against it, and how often do you simply use it as a way to interactively explore datasets? It seems to me that treating the language as a user interface is a strong argument in favor of the syntactic brevity of k/q/ksql. I just found an excellent talk about J which could serve as a decent introduction to the language and the style of programming with APL-family languages: https://www.youtube.com/watch?v=IKfJRyoiBlY Karl Hoijarvi, Array Algorithms and J
|
|
#
?
Dec 2, 2015 21:36
|
|
|
Is there a good writeup of why K as a language is fast? I understand how a column-oriented in-memory database can be fast, but what about the language itself? As far as I understand, it's just an interpreter. Does it even use parallelism? My own theory is that most K code uses language features directly, without any pointless abstraction layers, which means that only a relatively small number of interpreter actions are actually performed (and those are of course hand-optimised), but I have never seen a large K program. Are there any benchmarks comparing K to C? I often see it mentioned that it's just so much faster, but nobody mentions exactly why (except of course for the K code being much shorter, thus making it easier to optimise).
|
|
#
?
Dec 2, 2015 22:22
|
|
|
Low expectations, that's how.
|
|
#
?
Dec 2, 2015 22:48
|
|
|
Internet Janitor posted:I haven't worked with kdb+ myself, but it seems very expressive. How often do you find yourself writing entire programs against it, and how often do you simply use it as a way to interactively explore datasets? It seems to me that treating the language as a user interface is a strong argument in favor of the syntactic brevity of k/q/ksql. On my end it tended to be almost all long-running actual systems, but it is a quant favorite as well, and they no doubt mostly interactively poke at data in it. Almost all K programs end up using KDB stuff though once you have it, since it makes for a very clean way to talk about the input/output of functions and one-liners (which with the brevity of the language is pretty important) to almost always do it in terms of tables. Plus that the facilities for input/output of tables in various formats (as well as reasonably seamlessly being able to switch to compute off of disk) makes it sort of helpful. Athas posted:Is there a good writeup of why K as a language is fast? I understand how a column-oriented in-memory database can be fast, but what about the language itself? As far as I understand, it's just an interpreter. Does it even use parallelism? My own theory is that most K code uses language features directly, without any pointless abstraction layers, which means that only a relatively small number of interpreter actions are actually performed (and those are of course hand-optimised), but I have never seen a large K program. For the basics it is mostly a matter of tightly written loops assuming long arrays as the default, so it wrings a lot out of a modern processor by default. Then it one of those languages where the design sort of drives you towards short solutions, and all the constructs in the language are such that the short solutions tend to be the fast solutions. That is, there are a lot of operators doing fairly complex-looking operations, like the unary grouping operator '=', but which are actually linear-time and very fast when very properly tuned. As such you end up reaching for some powerful-looking tools that nonetheless actually perform very well. Optimization-wise it is mostly a matter of some special-casing of some known combinations, so for example *|x, reverse an array and picks the first element, which amounts to picking the last element, is internally fused into just picking the last element. Memory layout in K is also all about these large arrays of dense values. If you have a collection of WidgetThingys in C++ and loop over them to check something, you are likely accessing a tiny subset of the member variables in the WidgetThingys in the loop, but you are effectively loading the entire objects, including all the pointless book-keeping fields into valuable cache memory on the processor, where in K4 you would have table of WidgetThingys, but the table is represented column by column, and if you look at a subset of the columns in a query you will never waste memory bandwidth bringing the other columns into memory. The dictionaries are actually also dense, the keys are one array, the values are one array (so if you do the equivalent of fetching the keys or values from a K array it is basically free, you just get a peek at an array that exists), in fact when doing a lookup md`GOOG what K4 does is that it fetches the key array, and uses the "find" verb, '?' on it. Find works like this: 1 7 999 0 7 2 11?7 2 0 evaluates to 1 5 3, i.e. it returns the first index at which each element in the right argument occurs in the left, so a lookup like md`IBM`AMAZN runs (. md)[(!md)?`IBM`AMAZN] where '.' is the verb getting the values of a dictionary and '!' it the verb getting the keys. The way the lookups are made quick is by K4 noting when a dictionary gets large enough that it gets meaningful, and then building a hash index on the kley array, which the find operator can use (as opposed to e.g. Java where you'll have HashMaps with 50 elements where it'd be far quicker to just linearly scan but you still touch a bunch of memory to do the whole hashing song and dance). You can in fact make a medium-speed small dictionary in K4 yourself by sorting the key array before building the map, because the find verb looking up the values will then note the sorting flag and use binary search to do the lookup. K is fairly inefficient if you have a lot of single values, or a bunch of "general" arrays containing mixes of types, but K also makes that very inconvenient code to write, so you get naturally prodded into good code. The garbage collector is a simple reference counter, but since you almost always handle large arrays of values that is actually very efficient. Another aspect that improves the garbage collection, and performance, is that there is very limited aliasing in K. Every piece of memory is only reachable in one way (with some caveats, but there are no arbitrary references). That seems weird for most languages, but this too ends up feeling rather natural in K, to the point where a large fraction of K programmers are unaware of the fact. If you want to refer to various data you will usually end up naturally representing it as index arrays into whatever place the "actual" data lives in. So where in Java you would have a WidgetThingy class and a bunch of objects may create and keep WidgetThingys you would usually in K4 have a WidgetThingy table, and anything that "has" a WidgetThingy would have an index or a foreign key into that table (effectively a typed integer index). As we know, few data dependencies make modern processors go fast! That's a lot of word to not say a lot, since obviously you can do all this in C, since K4 is indeed an interpreter in competently written but not necessarily genius-level C. With light effort you'll write fast K far more easily than fast C, but if you invest a lot of time and effort C will run circles around K every time for fairly natural reasons (so, depending on your views the answer may be that, no, K will never win a benchmark war). Cybernetic Vermin fucked around with this message at 23:53 on Dec 2, 2015 |
|
#
?
Dec 2, 2015 23:01
|
|
|
Athas posted:Is there a good writeup of why K as a language is fast? K4 is impressively terrible at working with CSV files. Also column database as ideal format for time series is not always true, the competing product MemSql is a good platform to test this albeit limited language support.
|
|
#
?
Dec 3, 2015 01:13
|
|
|
Somehow I didn't notice (until recently) that Internet Janitor had already mentioned this over a month before I posted this... I are dumb, sorry. minidracula fucked around with this message at 04:09 on May 13, 2016 |
|
#
?
Jan 13, 2016 18:12
|
|
|
Lately I've been making many additions to iKe, including vector drawing and audio output. Click on any of these GIFs to run the program for yourself. The X box in the top right lets you see the source and try tweaking it. Panning around a hyperbolic projection of a grid:  A Lindenmayer-System visualizer:  A simple musical keyboard:  A chiptune music player:  Another interesting find is this OCaml implementation of K2. It's a bit unclear how much is implemented currently, but neat to see an interpreter in something radically different from C!
|
|
#
?
Jan 13, 2016 18:42
|
|
|
I've been trying to go through Project Euler using K as it seemed like a good way to practice this language. However, I'm on problem 2 and have already run into a wall. I'm trying to separate the evens so that I can add them up, as the problem states, but I'm not quite sure how to go about the conditionals for K despite reading the reference manual. Here's what I've got so far: code:
|
|
#
?
Jan 23, 2016 00:15
|
|
|
I think the operator you're looking for is &- "where".code:In unrelated news, I published a paper about iKe in Vector.
|
|
#
?
Jan 23, 2016 03:17
|
|
|
I've been playing with InternetJanitor's fun little K VM (iKe) to make short music loops. Variation #3 Dark Racing
|
|
|
#
?
Jan 23, 2016 06:51
|
|
|
Internet Janitor posted:I think the operator you're looking for is &- "where". Ah I had forgotten about where, but I read through your documentation again and saw the overload for # was what I was going for. Unfortunately I'm testing this using kona, so the version of K is a bit older. As a result this is what I have now: code:Because while the above works, it feels very ugly to do. Also, one of the first things I did when looking at this language was go through your sample codes and tried to figure out how they worked. Although I wasn't sure how draw looped until I read the paper you wrote, so thanks for that!
|
|
#
?
Jan 23, 2016 17:39
|
|
|
One way is to store an intermediate value in a variable:code:code:code:code:code:
|
|
#
?
Jan 23, 2016 17:50
|
|
|
At your suggestion, I've got another question. Today I tried to define this function:code:When I put it in oK, it will take the assignment, but calling the function will give "n is undefined". Running the above with ints in the cli works just fine, so I think it's something to do with how variable definitions are handled when declaring a function? This error wasn't one I could find in the reference book, nor on the google groups suggested on the kona github. mekkanare fucked around with this message at 17:55 on Jan 24, 2016 |
|
#
?
Jan 24, 2016 17:45
|
|
|
Oh, that's a common gotcha that tripped me up several times- In older versions of K, underscores were allowed as part of identifiers. By convention, built-in functions were often prefixed with an underscore. However, the underscore is also a primitive function (drop/cut/floor) so this leads to ambiguity. In Kona, adding a space after the underscore will probably do what you want: code:Internet Janitor fucked around with this message at 18:04 on Jan 24, 2016 |
|
#
?
Jan 24, 2016 18:00
|
|
|
Found a fun paper: Language as an Intellectual Tool: From Hieroglyphics to APL. It discusses the origins of mathematical notation and in so doing provides some rationale for why APL was designed the way it was.
|
|
#
?
Mar 9, 2016 05:01
|
|
|
I discovered K recently while doing some research at work, it's changed the way I think about programming. It's pretty awesome. I'm advocating for it now since it kicks the crap out of our current stuff (and in much less code), but it's a pretty tough sell to people who don't already know about it. Proprietary, closed-source, expensive software made by one small company makes for a hard comparison against the usual big data crap. K deserves much more attention than it gets, IMO, but they don't make it easy. P.S. Anybody going to KxCon this year?
|
|
#
?
Apr 28, 2016 03:40
|
|
|
I recently obtained a copy of k6, the successor to k5, and I've begun studying it. I'm recording my findings in preparation for moving my interpreter toward supporting this new dialect. Man, I'd really love to attend KxCon, but it's rather far away and I don't think I could afford it. 
|
|
#
?
Apr 28, 2016 05:29
|
|
|
I can't help feeling that the language has been in regression since K4 (really since K3, but the Q integration in K4 made some of the losses worth it) 
|
|
#
?
Apr 28, 2016 10:01
|
|
|
So I actually program use APL at work. Once you get past the syntax and the special characters, its quite nice. Prototyping is a breeze Also, as you could imagine, the user community is quite idiosyncratic.
|
|
#
?
Apr 29, 2016 01:52
|
|
|
BigBobio posted:So I actually program use APL at work. Once you get past the syntax and the special characters, its quite nice. Prototyping is a breeze Where do you work? Everyone I know who programs APL is either in finance or... idiosyncratic.
|
|
#
?
Apr 29, 2016 09:00
|
|
|
I've been thinking about trying to get a job doing K stuff. Any advice from people who've worked in that community before, i.e. is there anything/any companies I should watch out for?Internet Janitor posted:I recently obtained a copy of k6, the successor to k5, and I've begun studying it. I'm recording my findings in preparation for moving my interpreter toward supporting this new dialect. Using a single numeric type (doubles only I guess?) is an interesting choice, not sure how I feel about that.
|
|
#
?
Apr 30, 2016 04:22
|
|
|
Rhusitaurion posted:Using a single numeric type (doubles only I guess?) is an interesting choice, not sure how I feel about that. Currently k6 does distinguish between ints and floats if you inspect the typecodes with @, so the implications of this choice seem to be more that ints and floats will coerce to one another in more situations and if the interpreter does something special under the hood as an optimization the programmer need not concern themselves with it. The major change here is the banshment of various subtypes, like "boolean ints" that are restricted to 0 or 1, shorts, etc. as distinct numeric types. In oK using doubles for everything hasn't produced any particularly weird problems, but then again I'm mostly applying it to toy problems.
|
|
#
?
Apr 30, 2016 05:15
|
|
|
Internet Janitor posted:Currently k6 does distinguish between ints and floats if you inspect the typecodes with @, so the implications of this choice seem to be more that ints and floats will coerce to one another in more situations and if the interpreter does something special under the hood as an optimization the programmer need not concern themselves with it. The major change here is the banshment of various subtypes, like "boolean ints" that are restricted to 0 or 1, shorts, etc. as distinct numeric types. In oK using doubles for everything hasn't produced any particularly weird problems, but then again I'm mostly applying it to toy problems. Ah, that makes a bit more sense. I've had cause to use shorts before, but I suppose storage and memory is cheap. Found any other cool stuff in K6? I saw Dave Thomas from FD at a meetup a few weeks ago, and he was saying something about having type annotations and a built-in JIT (I'm forgetting the details now).
|
|
#
?
May 1, 2016 18:43
|
|
|
Anyone happen to be playing with Dyalog APL? I'm tinkering with it on Windows, and I'm hoping someone else has already done the work for me and made a easy-to-use 2D canvas object I can mess with. In some quick searching and scouting around on Dyalog's community forums, while there's some pack in GUI objects in the environment, they seem to mostly be for forms, grids/cells, traditional application widgets, graphs & charts, etc. I'm looking for something more like isigraph/gl2 from J. In one of the Dyalog community forum posts I found, there's mention that the preferred method would be to use a .NET widget (and use Dyalog APL/W's .NET integration to take advantage of it); does anyone have a suggestion, ideally that they've used? I mostly want to play with programmatically generating 2D graphics as a display of states, etc. (my initial motivation was to reimplement some CAs and ALife simulations in APL).
|
|
#
?
May 13, 2016 04:18
|
|
|
Fun little iKe demo: Noyemi K observed that my manhattan-distance voronoi diagrams resemble subway schematic diagrams, and was interested in trying to apply this technique to generating content for a game. I developed a simple alternative algorithm which also produces appropriate shapes: do a series of drunkard's walks radiating from a centerpoint and making turns in 45 degree increments. I think the results are reasonably convincing. It's great fun to tinker with the parameters of the simulation to see what you can come up with. code:
|
|
#
?
May 13, 2016 07:21
|
|
|
Fun with Poisson Disk Sampling: code:Still a fair bit of room to simplify this one, I think.
|
|
#
?
May 25, 2016 03:59
|
|
|
Just watched a great introductory talk about Q and array programming in general: https://www.youtube.com/watch?v=ZGIPmC6wi7E Tim Thornton - Data Analysis with Vector Functional Programming
|
|
#
?
Jun 12, 2016 21:46
|
|
|
Fun side note: my goofy K projects gained enough recognition to land me an interview with a large consulting firm whose backend systems are written in K. The interview experience itself was, to put it mildly, surreal in the best way. I'm now in the process of relocating to NYC to start a new job there. So, uh, I guess the lesson here is occasionally weird side projects can result in unexpected new career paths? 
|
|
#
?
Jun 13, 2016 06:55
|
|
|
are you also going to be doing their internal newsletter, drawing the eldrich horror that is K itself?
|
|
#
?
Jun 13, 2016 07:33
|
|
|
|
| # ? Apr 23, 2024 22:07 |
|
|
Suspicious Dish posted:are you also going to be doing their internal newsletter, drawing the eldrich horror that is K itself? Will neither confirm nor deny.
|
|
#
?
Jun 13, 2016 17:09
|
|