8 ms·
Thinking in an array language
- ogogmad 5y agoArray languages might make good maths notation. It's terse and easy to write, and there's a logical naming scheme (for instance, matrix multiplication is just (+/*)\: ). I suppose the trick is to think of (+/*)\: as one unit.
- pxeger1 5y agoAPL, an array language, literally started out as a computer adaptation of traditional mathematical notation. https://aplwiki.com/wiki/Iverson_notation https://aplwiki.com/wiki/Iverson_notation https://aplwiki.com/wiki/Comparison_with_traditional_mathematics https://aplwiki.com/wiki/Comparison_with_traditional_mathema...
- hoosieree 5y agoMath notation is highly context dependent (is + addition or boolean or?) and yet authors rarely feel the need to provide context. If they wrote in an array language instead of LaTeX, not only would it make writing papers easier (+/ is shorter than either \Sigma or \sum), but it would be trivially reproducible, due to being an executable notation.
- grayclhn 5y agoYeah… for actual papers “easier to read” is 1000x more important than “easier to write.”
- kmstout 5y agoSomewhere on YouTube is a talk where Gerald Sussman described mathematics (or at least mathematical presentation) as "impressionistic."
- Mathnerd314 5y agoI think he says that in every talk he gives. https://youtu.be/HB5TrK7A4pI?t=1090 https://youtu.be/HB5TrK7A4pI?t=1090, https://youtu.be/arMH5GjBwUQ?t=377 https://youtu.be/arMH5GjBwUQ?t=377, https://youtu.be/EbzQg7R2pYU?t=3201 https://youtu.be/EbzQg7R2pYU?t=3201, etc. There's a 2002 paper where he uses the term: https://dspace.mit.edu/bitstream/handle/1721.1/6707/AIM-2002-018.pdf?sequence=2 https://dspace.mit.edu/bitstream/handle/1721.1/6707/AIM-2002...
- snidane 5y agoArray notation is great, but only for single array operations and for dense array operations. The moment you need to run complex group bys and store non-contiguous data efficiently, it gets awkward pretty quick. On the other hand, operations on dense data is pretty cumbersome in SQL. You can only do so much with limited support of proper scan algorithms, merge joins or bolted on window functions. Please somebody combine APL with SQL and you win the programming language wars.
- mlochbaum 5y agoI would say APL-family languages today have largely addressed these concerns with operators such as Key[0][1] and nested arrays. J also has built-in support for sparse arrays. Some more complicated things like storing a list of lists in a compact representation (perhaps lengths and data) aren't supported natively, but I'd consider that a niche concern as a list of lists will have similar performance, just with more memory use. There's a lot of database software built on array languages, with kdb and Jd being the most prominent as far as I know. [0] https://aplwiki.com/wiki/Key https://aplwiki.com/wiki/Key [1] https://code.jsoftware.com/wiki/Vocabulary/slashdot#dyadic https://code.jsoftware.com/wiki/Vocabulary/slashdot#dyadic
- hoosieree 5y ago> Please somebody combine APL with SQL and you win the programming language wars. kdb+ and q fit this description. Docs here: https://code.kx.com/q/basics/qsql/ https://code.kx.com/q/basics/qsql/ Here's an example. In SQL: SELECT stock, SUM(amount) AS total FROM trade GROUP BY stock In q: q)select total:sum amt by stock from trade
- eismcc 5y agoWas gonna say the same plus kdb+ is a columnar store so you can get vectorizarion in your sql execution as well.
- nerdponx 5y agoR? Julia? Python with Pandas even.
- geophile 5y agoSort of related: thinking in relational algebra, or SQL. It appears to be "natural" to think about computing one atomic value at a time, in loops, or slightly less intuitively, recursive functions. (That latter choice may follow from whether your first language was pure Lisp.) I was fortunate to have a teacher whose database course drilled relational algebra into us. This was in the 70s, shortly after Codd's paper, and well before SQL was invented, much less established. Now I think about much computation algebraically (and often functionally). But I do see that this is "unnatural" for many, including students, having taught databases for several years. SQL reflects this. I often see students writing nested subqueries, because that is more procedural, where joins would be a cleaner choice. A colleague of mine wrote a paper many years ago, pointing out that thinking procedurally is more "natural" for many: https://dl.acm.org/doi/10.1145/319628.319656 https://dl.acm.org/doi/10.1145/319628.319656. But thinking set-at-a-time instead of one-at-a-time is a valuable skill, not that far off from thinking functionally.
- TFortunato 5y agoHaving taught it, do you have any recommendations for folks who are looking to improve their thinking in relations/sets/SQL skills?
- co_dh 5y agohttps://arxiv.org/abs/1803.05316 https://arxiv.org/abs/1803.05316
- geophile 5y agoI teach, in order, more or less (there is some interleaving): - Data modeling - Relational algebra - SQL - DBMS architecture (buffering, btrees, query processing, index selection, ...) - Query optimization - Transactions A few assignments have students write an in-memory relational algebra implementation, and then use it to write queries. A typical query is a deeply nested set of function calls (as a "one-liner"). And only then to we get to SQL. The hope is that RA is so ingrained, that the connections to SQL are easier to see. And this background is also really useful in understanding query optimization. All of this material, including assignments, is available online (this is my own webserver): http://geophile.com/115 http://geophile.com/115.
- IshKebab 5y ago"What if we could make entire programs as unreadable as regexes?" -K
- icsa 5y agoAnd yet regular expressions are a part of most programming languages as a library or built-in syntax. Why is that?
- bear8642 5y agoProbably due to they're a great notation for the problem area which for regex is concisely describing text patterns. For example 'a*b' is any number of 'a's followed by 'b'. How else would you concisely state that?
- LAC-Tech 5y agoHow else would you concisely state that? Presumably people who hate array languages think all 3 character regexes should instead be big nested loops, so they are "readable".
- samatman 5y agoRegexes in the Unix tradition are a user interface as much as a programming language. Not that there's a sharp distinction, but it's almost a trite observation that regexes per se shine for ad hoc string searching but show their weakness when they start becoming parts of programs. When writing a program, I prefer to use a PEG, giving the less compact notation `'a'* 'b'` but also letting me say `'a'* b` and define b as its own rule, including recursion for the useful cases. It helps that it's more powerful, being little more than a formalization of the post-regular strategies used in Perl-style 'regular' expressions while embracing recursion. For '/' in vim, grep, wherever? Yeah regex is fine, that's what it was designed for.
- IshKebab 5y agoI can't remember the names but I've seen at least two alternative syntaxes recently that are a lot more readable. At least one of them fixed the issue of regex mixing up control in-band with data. So your example would be something like "a"* "b" Much more readable and less error-prone.
- unnouinceput 5y agoAny performance benchmarks between a simple C implementation of matrix multiplication like explained in the article and K one? Story time: 2 years ago, right before 1st lockdown, I landed a client. A data scientist who had already implemented an algorithm which dealt with matrices, implemented by a previous programmer he hired. Said implementation was in Python, no more than 10 line altogether, which performed well when matrix size where small, like 10x10. But the problem was, his real work need it to have matrices of size 10^6 x 10^6. Not only the Python implementation had to be ran on a beast of server with 4TB of memory, it also took 3 days to finish. And while the algorithm was small in size in Python, its explaining paper was 4 pages in total, which took me 1 week to understand. And then an entire month to implement in C. But in the end, when all was said and done, the run time when used with real data was only 20 minutes and consumed only 8 GB of memory, though it did required at least 16 virtual processors. Hence my question, in the end performance is what it matters, not number of lines.
- mlochbaum 5y agoK timing, squaring a 100x100 matrix in ngn/k: a:100 0N#?10000 / 100x100 double matrix \t:1000 a(+/*)\:a / Total of 1k runs in ms 1514 Following C program outputs 272 when compiled and run with -O3 -march=native. #include <stdio.h> #include <time.h> size_t monoclock(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); return 1000000000*ts.tv_sec + ts.tv_nsec; } int main() { const size_t n = 100; double a[n][n], r[n][n]; size_t t = monoclock(); for (size_t iter=0; iter<1000; iter++) { for (size_t i=0; i<n; i++) { for (size_t j=0; j<n; j++) { double sum = 0; for (size_t k=0; k<n; k++) sum += a[i][k]*a[k][j]; r[i][j] = sum; } } } printf("%lld\n", (monoclock() - t)/1000000); } So K is slower, by a factor of 5 rather than the 200 you saw with Python. K appears to scale to larger matrices better than C: 8664 in K vs 2588 in C for 200x200, but I can't be bothered to sort out heap allocation for the C code to do larger sizes. I would certainly not say that your story supports the idea that performance is what matters. In the month you took to implement the C version, the Python solution could have run ten times over, and there are many computations that only ever need to be performed once. Besides, I bet you were glad to have working Python code to use as a reference!
- carapace 5y agoI was just playing with Nils M Holm's Klong this morning: https://t3x.org/klong/index.html https://t3x.org/klong/index.html (Klong rather than the others mostly because the C implementation looks like C so I have a ghost of a chance of actually grokking it.) These folks are really onto something, but I think they get sidetracked in the (admittedly very very fun) minutia of the languages and lose sight of the crucial insight in re: mathematical notation, to wit: it's a means of human communication. For APL or K to get out of their niches would require, I am convinced, something like a tome of documentation of a ratio of about 1.5 paragraphs per line of code. That would give us mere mortals a fighting chance at grokking these tools. A similar problem plagues the higher-order stuff they're pursuing over in Haskell land. I know e.g. "Functional programming with bananas, lenses, envelopes and barbed wire" and "Compiling to Categories" are really important and useful, but I can't actually use them unless some brave Prometheus scales Olympus and returns with the fire. Stuff dribbles out eventually. Type inference and checking have finally made it into the mainstream after how many decades?
- jodrellblank 5y ago> "would require, I am convinced, something like a tome of documentation of a ratio of about 1.5 paragraphs per line of code. That would give us mere mortals a fighting chance at grokking these tools." You can download a free PDF copy of Mastering Dyalog APL by Bernard Legrand which is 700+ pages, from here: https://www.dyalog.com/mastering-dyalog-apl.htm https://www.dyalog.com/mastering-dyalog-apl.htm
- carapace 5y agoThat's an amazing reference, but it's about the language, I was thinking more of walk-throughs of code in the language. E.g., for some BQN code: https://news.ycombinator.com/item?id=30913872 https://news.ycombinator.com/item?id=30913872 There was a better example a couple of weeks ago here in a thread, someone had done a bit of APL or K for Advent of Code or something and posted a line, and someone else broke it down and explained how it worked. I spent an hour just now with Algolia trying to find it but I failed. :( Holm's Klong docs have a good example in https://t3x.org/klong/klong-intro.txt.html https://t3x.org/klong/klong-intro.txt.html where he explains how a table formatter function works. Mathematical equations are usually embedded in papers that explain them. (I mean, I've read papers that were basically equations one-after-another with just scraps of interstitial prose, but they were heavy going.)
- btheshoe 5y agoThis all seems very similar to writing vectorized code in numpy
- eismcc 5y agoThat’s because numpy is based on J which is based on APL
- MontyCarloHall 5y agoYet another Iverson Ghost! https://dev.to/bakerjd99/numpy-another-iverson-ghost-9mc https://dev.to/bakerjd99/numpy-another-iverson-ghost-9mc
- da39a3ee 5y agoWhat? matmul: (+/*)\: