Algorithms as a Tool of Thought // Conor Hoekstra // APL Seeds '21
Vložit
- čas přidán 9. 06. 2024
- Kenneth Iverson won the Turing Award in 1979 for his work on APL. His 1979 Turing Award Lecture "Notation as a Tool of Thought" could just as easily been called "Algorithms as a Tool of Thought." In this talk, Conor explains why he believes this by showing how APL teaches you to think differently about solving problems.
Slides and code from this talk is available from:
github.com/codereport/Talks/t...
www.dyalog.com/apl-seeds-user...
#APL #Dyalog #Algorithms #ProgrammingLanguages #APLProgramming #SoftwareDevelopment #CodingTips #TechTalks #ComputerScience #DataStructures #CodingCommunity #TechConference - Věda a technologie
I love Conor's passion! I wish I could work with developers that have this much passion for code!
Thank you for the nice animations from the dfn/'lambda' syntax (supported by GNU APL) to the 'point-free' (fork) syntax during this presentation. It really helps one understand the equivalence of the two in translating between the more prevalent Dyalog examples online and APL2/GNU APL.
These algorithms remind me of everything I hated about APL. In order to get execution speed, you had to use native operators instead of loops. But the native operators generally did way more than necessary to solve the problem. In most languages, the programmer would loop, and would exit the loop the instant a different value was found. Most of these “elegant” algorithms traverse the entire vector multiple times. Most are opaque. You have to unravel the programmers thinking to find out what the algorithm does.
This is an interesting comment and made me think about abstraction and encapsulation. I'm a Java/C# developer by trade, so as OO as it gets, but to me these symbols are like interfaces. When Java 8 came out, many developers at my company struggled with the streams (LINQ for Java) and it was exactly what you pointed out. It was too much of an abstraction over loops. It's interesting because by having abstraction, you get reuse, but you lose visibility through encapsulation. It seems like a tension that we have to face as developers and APL looks like it dials up abstraction and encapsulation. It's not good or bad, but brings problem solving to a higher level. This also reminds me of introducing interfaces to Pascal developers. They thought that interfaces were way too abstract because the implementation wasn't visible. Looking at APL makes me empathize with those Pascal developers as I now know how they felt.
It's not that complicated. APL functions have certain semantics, which mesh well with the objective of the language, which is to operate on multidimensional arrays and nested arrays. It's those semantics that you need to focus on. Moreover, when you work with APL you start to recognise typical patterns (combinations of phrases) after a while. It's no different than in other languages, really.
@@chewbaccarampage In APL you trade time efficiency with space efficiency, as usual. In order to operate on whole arrays reasonably fast, you "lift" them in higher dimensions, essentially, and then you reduce/project over some axes of those higher-dimensional arrays. That's the gist of it.
So here's a story from my physics years.
I was lucky enough to read physics at a uni in Greece where most of our profs had taken their PhDs from the US.
So one of them met once P. A. M. Dirac at a conference (google the guy).
He gathered all the strength he could and went to talk to him. So, my prof allegedly asked him one question only: prof. Dirac, in all your career what do you think was your most important contribution in physics? Dirac thought for a moment and said: the bra-ket notation (google this too if you're a linear algebra freak).
So yeah. Notation as a tool of thought. Prof. Iverson couldn't have been closer to the truth.
That being said, thank you for your videos. I think you're teaching us how to fall in love with APL, and judging from myself, you're doing a great job. Please do keep it up!
Very appreciative for this talk. I am liking APL.
Hello Code report, from your CZcams videos like solving Leet code problems with different programming languages, i found that APL language, it was very new to me. currently, I'm started to APL programming languages.
fantastic to hear you are starting with APL. Let us know if we can help!
I think it's not correct to use the term function and algorithm interchangeably. Take the Grade Up function for instance (represented by the symbol ⍋). It uses a sorting algorithm but it could be quick sort or merge sort or some other algorithm. So a function is typically an abstraction over an algorithm.
great talk. thank you!
The FinnAPL was completely new thing to me as a finn, thanks for that. These cult like encapsulated knowledge vaults just don't come up unless someone from the "inside" hints at it.
Looked up the pdf and it's interesting how old-timey the linguistic expressions are, it has some benefit from mathematics being so old that it has established vocabulary, but particularly computer science has always had difficulties where you think everything sounds odd in finnish and has a wrong translation when you learn the english original words. Like until very recently it was still common to refer to a function as "subprogram" in finnish which is not wrong but feels weird. And the object-oriented programming is a word that nobody understands when they are taught it in finnish, it is like "creature based programming" and nobody even learns classes until way into it so they have no concept (the finnish words for the creature based programming term are just somewhat uncommon in common spoken language, and their combination doesn't even connect with the meaning of the words because of the pronunciation).
That being said, the pdf was really well written, I wish all programming languages had that kind of introductory booklet where you're introduced to the style, "vocabulary" of the language and just very practical examples. It's funny how they use some well known tongue twisters as example inputs.
You talked about J's feature to convert non-tacit to tacit. This reminded me of another incredible feature of J: if you have a tacit function you can apply the "invert" operator and have the inverse function.
Beautiful.
It alkso exists, in APL, if you apply the power operator with -1 as the right argument, to some function on the left, it will invert it, if possible.
@@gtgunar I think this only works with Dyalog APL?
Excellent talk !
I think it will be easier who understand if you called n-wise solution as "windowed-solution"
Looking for the podcast on which Conor previously gave a top 5 favorite languages list.. Anyone have an episode link?
I've seen people with larger icons on their Dyalog IDE but try as I might I can't configure this. I can increase the font which is great but on a hi-res 13" screen the icons are literally 3mm tall. The actual glyph is maybe 2mm tall? I hope I don't have to read an 87 page manual on editing registry keys to make this small change.
Fun talk, I use mostly Julia so here's a fun solution to all_equal for a vector of integers in Julia.
A = [1,1,1,1]
A[1].==(A) which will return a bitvector [1,1,1,1]. Nice succinct code for checking this, also given two vectors A and B, can do A.==(B).
The fourth solution is mathematically elegant. It basically encodes an L_inf measure.
This is the second time I've watched this talk! :-)
So I write an absolute ton of JavaScript, and JS provides an in-built reduce on lists. You can do some pretty APL-like things in JS.
APL (talks like this one and others) are what got me interested in learning about reduce. Diving into APL is on my list of things to accomplish.
Here is an example of one solution to the all_equal function in JS, using just native JS.
[1,1,1,1,1].reduce((a,v,i,arr)=>a && arr[0] === v, true)
Definitely not as pretty as APL.... lol. I really want to learn it, but there just isn't but one of me. We'll get to it eventually. Thanks for sharing your video. It was bad-to-the-bone.
Maybe an even more literal translation of Conor's ∧/{(⊃⍵)=⍵} and ∧/(⊃=⊢) into JS would be arr=>arr.map(v=>arr[0]===v).reduce((a,b)=>a&&b) or arr=>arr.every(v=>arr[0]===v)
Note also that Conor's {1=≢∪⍵} and (1=≢)∪ could be translated to arr=>(new Set(arr)).size==1
@@DyalogUserMeeting I love that. That's good stuff.
@@DyalogUserMeeting Growing in code, dude.
Very entertaining
Factor has all-equal? which takes a sequence
Looking for the Dave Thomas “shape thinkers” talk - does anyone have a link?
Here it is: czcams.com/video/ng-QNLdgQeY/video.html
@@code_report very interesting talk, thank you for linking it. After seeing the title I understand why my Google searching failed.
Most exciting takeaway for me was recognizing how similar SQL, R, and APL are. This is motivation to learn those first 2 and really lean into framing them as tools of thought.
@@arisweedler4703 the link above is broken now. Any idea what I should be searching for to find the talk? Thanks!
Very interesting talk, thanks 🙂 ( just one thing, I’m not ABSOLUTELY sure but I think what other people call functions, you like to call algorithms? At least I think that what the first seven minutes of the talk was about 😂)
Yes, but only in context of APL
@@froloket - did you or I have the sense of humour failure there?
😂😂😂
APL is the absolute pinnacle of data manipulation.
Please do keep sharing about APL and vector programming... super fascinating!
Here's a solution in Prolog:
```prolog
all_equal([X|Xs]) :-
maplist(==(X), Xs).
```
Haskell can be coded very similar to APL. allEqual = ap (all . (==) . head) id
ap should have been named "S" instead.
in raku
you can use the [==] or [eq] operators == for numeric eq for strings
which is the equivalent of
reduce &infix: or reduce &infix:
you can create a list in variable or apply it to a list directly
reduce &infix: , 1,3,3,4
> False
reduce &infix: , (1,3,3,4)
> False
my @list = (1,3,3,4) ; reduce &infix: , @list
> False
Yes, and in fact, you don't even need to write reduce &infix:, as you can spell this just [==] but, while it works, it is confusingly inconsistent with other reductions, as it is NOT in fact a reduction, but rather inserts the comparison between the elements and then relies on Raku's chained comparisons. How would you actually perform a comparison reduction, for example with inequality, to find the parity of a Boolean list? In APL, this is just ≠/
@@DyalogUserMeeting
i am not sure what ≠/ does exactly
but yes [!=] in raku seem to do mathematical chaining
so for example
[!=] 1 , 2 , 3 , 2
True
but
[!=] 1 , 3 , 3, 2
False
because raku i think transform to
1 != 3 && 3!=3 && 3!=2
so if in your list any 2 sequential numbers are equal it will be false
17:40, I believe you meant lte (0 or 1) and not gte (1 or more) for this. With gte, if you have more than 1 unique element, it is not allEqual.
If he used lte, at 16:50 it would evaluate true.
I guess the empty list is being considered allequal.
17:10 APL scans right to left so parens not needed
I found two character solution:
=/
So it reduces array if every element is equal to each other
It's pretty strange it wasn't mentioned in the video or by any other commenters
=/2 2 2
Will say 2=2=2 and then 1=2 and then 0.
I like the idea!! But I do not think it will work.
@@arisweedler4703 Thanks, it doesn't really work, I checked it on array of ones, so I should have made another test. Thanks for the comment
I really don't like this kind of one-dimensional judgements.
So, I'd really like to see a parser for, say Python, implemented in APL ...
All equal. ^/=\
Doesn't work, =\4 4 4 4 4 is 4 1 0 0 0
@@rorykemp5218 You right is wrong.
{0=⍴⍵~1↑⍵}
or
0=(⍴⊢~⊃)
Works
APL makes no sense to me.
Instead of making things easier, you have to learn a vocabulary of symbols (at least me, myself I think in words and not in images when programming).
And does it scale for programming in the large?
It would not be idiomatic to name your own functions/algorithms with anything but yet another symbol, right? Comments are extra characters and that is not the APL way as well. So if you end up with a program which has 5000 functions, people working on the code have to memorize an extra 5000 little images and their meaning. Even chinese kanji are built of radicals, so if a chinese person encounters an unknown kanji, they can sometimes deduce the kanjis meaning from the radicals it is composed of. APL is like chinese without the mental bridge of radicals.
Even if you get the first 50 symbols handed to you for free (knowing them already from your math classes), the rest is just learning names of images.
There is a video on youtube titled "Creating the worst possible programming language" and they use UTF-256 encodings for their characters. Build a large enough system in APL, and you will need that BS feature :)
The human mind is clearly able to understand both "symbols" and characters, so what is "easier" is probably just whatever you've been exposed to. For example, take a look at many east asian languages with a huge amount of symbols.
This is the old saying about the hammer and nails, it does get old and annoying but that's it.
You benefit of understanding and knowing how to use the best tool for the job. I used to think that AWK was a waste of time until I decided to give it a try and understanding the power of using AWK when AWK is needed.
My language of choice nowadays is Elixir, of course I could do every parsing and processing I'm using AWK for in Elixir.
Why would I, if AWK is more appropriated for the job?
On the other hand I wouldn't use AWK to write an HTTP server or to create a 3D game even though those two things have been done in AWK before. I just don't think AWK is the best tool for the job. I don't write games, and for HTTP Servers I have Elixir and Phoenix that's way more efficient and easy.
Equally, if you understand APL as a DSL that is the most appropriate tool for the specific job it was created for (arrays, matrices, linear equations and so on), you'll understand that you could use your language of choice to solve these kind of problems, but that doesn't mean that your language of choice really is the appropriate tool for the job.
I used to think like OP, those symbols are BS, so after seeing some cool solutions in APL, I decided that I would learn APL because I started to see that it would give me the power and the right tool to solve specific problems just like AWK did, but I would learn an ASCII APL, like J or K, so I could get rid of the fancy characters getting in my way.
I've downloaded J and Ivy. Cool. For some reason putting two non-sensical ASCII characters together doesn't necessary makes things easier, and writing functions by name or abbreviations also doesn't.
So I decided to download Dyalog and give it a try. After discovering that ` is a shortcut to write the special characters, and that hovering the mouse over the symbols gives you the key you need to press after `, you start writing things quickly because you only really need to learn 5 or so of the most used glyphs to start writing very efficient solutions for specific problems.
It took me about 30 minutes to understand the basics and get used to writing the symbols, and after about 2 hours experimenting and solving some Set Theory problems, I finally understood the Notation as a Tool of Thought.
After mere 2 hours of experimentation I was having zero problems typing the glyphs myself or looking for them in the top bar, and I was already thinking on symbols as steps and solutions. I was already transforming the array and matrices in my head by the mere thought of the glyph.
Now I'll look for Mr. Iverson paper to read because even though I didn't read it yet, I did understood the power of the notation "as a tool of thought".
I've studied Chemistry, I'm not a computer scientist, so I did had the experience of notation as a tool of thought before, but I would like to share the little story to you because like you I was resistant to even try, but because I decided to give it a try with an open mind I could see for myself what those guys are trying to say by this motto.
It's just like Lisp, most people don't want to even try it, too much parens right? Ugly and non-sensical.
The ones that give it a try with an open mind usually come back different. APL have the same level of enlightenment to me that Lisp and SICP did, but maybe it's correct to say that it even can be an order of magnitude greater of an enlightenment.
@@JacksonBenete I guess, the main point of my previous post was, that the "symbol driven" approach does not scale. Now, you have brought up LISP, I feel urged to share, that I think - in terms of scalability - LISP is just the opposite end of the scale. I think I have to elaborate:
The majority of programming languages capture certain aspects or mechanisms with syntax and dedicated keywords. Doing that, leaves the user of the language with a predefined, fixed set of tools. They can use the tools, but they cannot invent new tools, which add to the language in the same idiomatic way.
APL defines a set of symbols and yet, if you write code yourself in APL, you fall back to using words once again to name your own stuff (functions etc.), instead of inventing a new 8 by 8 or whatever bitmap to name your function. So the scalability of the approach is literally non-existing.
In Lisp, however - being on the opposite side, you can create not only functions and use, what you get. You can create new idioms, new syntax and mold the language itself to fit your use case. This is both a blessing and a curse, given that new users might get confused by all those "special forms" people create to fit their needs (or not). But at the same time it is the pinnacle of expressive power and no other language (family) comes even close.
So yes, APL is more like regular expressions (most have love hate relationship towards those, too). And Lisp is more like a compiler which also can get changed and used to write code in. And that - at least in my books is a real enabler of the power of thought.
@@ruffianeo3418 I think I understand your point better now. And I thank you for taking your time to read my reply.
I hope you don't mind if I share a bit more of my experience with APL, and about what you have just shared.
I'm by no means experienced with APL, I know only a couple of glyphs and I'm progressing baby-steps on learning everything.
There is a quote on SICP, it's more or less like this "Pascal is for building pyramids-(...) Lisp is for building organisms (...) It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures."
This is what makes Lisp so flexible and powerful, right? Or at least IMO? You have one data structure, the list (or lists and atoms), and we can build everything on top of that.
As far as I know, APL also have only one data structure, the vector or the array (or arrays and atoms/elements).
Take the reduce operator, which is `/`.
As a beginner at first I thought it would work only with other glyphs such as +/, ÷/ and so on...
You can define your function and `myfun/⍳3`, APL supports high-order functions.
APL supports lambdas.
APL supports functional programming. Even lazy evaluation if you want.
Maybe you're talking about the power that Lisp gives you by creating domain-specific languages?
You can create domain-specific languages in APL as well. I don't know how easy or good APL is to create macros, but as far as I know you can also do that.
Q was made on top of K, there are others DSL and you can even find books on writing Domain-Specific Languages in APL, like Menace (romilly.github.io/o-x-o/index.html).
You can write compilers in APL, there are papers and I think a book about that.
I don't think that APL is less powerful than Lisp but I do think that APL powers can be more hidden and difficult to discover or figure out. Also maybe not as practical.
Maybe I still misunderstood your point, sorry about that if that's the case, but maybe you do have everything you're thinking right on APL but you just don't know that.
I think that Lisp is more approachable and easier to learn, and have more materials about.
But as of yet I fail to think that APL is less powerful, even though I wouldn't use it myself for a lot of things, as I prefer to use what I think is the most appropriate tools for the job. Again, I'll not use Lisp or Elixir where I could pick AWK or APL easily and faster in my belt, but I would use Lisp for a lot of other things.
Now I understand that in Lisp you basically program direct in the abstract syntax tree. That's why metaprogramming is so easy. I don't know how APL works on this regard.
If you think that APL is not as powerful as Lisp I think that's fair enough, maybe it isn't really, you could still use and benefit from APL in specific appropriated cases. You can treat APL as a DSL and use it only when it's convenient.
I really think that people can do a lot of things fast with APL, and I really think it helps you reasoning about problems and finding solutions. You need to learn how to think on APL just like it takes time to learn how to think FP, like doing Lisp for the first time after many years of imperative programming.
But I agree that if you don't think it's useful to you, you wouldn't benefit from any of that.
Long but interesting and maybe useful talks:
czcams.com/video/bQlH49krwbk/video.html
czcams.com/video/9xCJ3BCIudI/video.html
The political flags in the background really take a lot away from this talk. Why can't we come together over shared passion for programming without injecting politics and faux virtue?
⊣≡≢⍴⊃ work fine with simple list but does not work on singleton I do not know why...Any suggestions?
Rho of a scalar is not 1. Ravel the argument first to ensure it’s a vector, possibly a vector of length 1.