ngn-k-tutorial/12-thinking-in-k.md at main · razetime/ngn-k-tutorial · GitHub
//blob/show" data-turbo-transient="true" />
Skip to content
Search or jump to...
Search code, repositories, users, issues, pull requests...
-->
Search
Clear
Search syntax tips
Provide feedback
--><br>We read every piece of feedback, and take your input very seriously.
Include my email address so I can be contacted
Cancel
Submit feedback
Saved searches
Use saved searches to filter your results more quickly
-->
Name
Query
To see all available qualifiers, see our documentation.
Cancel
Create saved search
Sign in
//blob/show;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up
Appearance settings
Resetting focus
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
razetime
ngn-k-tutorial
Public
Notifications<br>You must be signed in to change notification settings
Fork<br>23
Star<br>210
FilesExpand file tree
main
/12-thinking-in-k.md
Copy path
Blame<br>More file actions
Blame<br>More file actions
Latest commit
History<br>History<br>History
150 lines (121 loc) · 5.33 KB
main
/12-thinking-in-k.md
Top
File metadata and controls<br>Preview
Code
Blame
150 lines (121 loc) · 5.33 KB
Raw<br>Copy raw file<br>Download raw file
Edit and raw actions
Thinking in an array language
You can view the full source code for this chapter at GitHub.
Since you are now properly acquainted with K, let's do some programming.<br>Most K programming happens through the REPL, because it is very useful to iterate upon previous code. ngn/k with rlfe has history with the up/down arrow keys, and that should be more than enough to begin developing bigger programs in K. Functions are tested in the REPL, and then moved to actual code. Note that ngn/k's prettyprinting always returns valid k data, and you can precompute some things beforehand to speed up your program.
A K script is always executed like it was typed in the repl, that is: Each line is executed, and its return value is printed unless it ends with a semicolon. A script also allows multiline definitions, which are convenient for readability. Oftentimes, you may save your work in a script, and want to use it in a repl. In order to use your stored data and functions, just do \l file.k in the repl, and your file will be executed, and its data will be loaded. You can load a file into the REPL more than once, overwriting older data. The repl help accessed with \ lists more useful commands as well.
K programming (and array programming in general), is a continuous process of simplifying your patterns. A big, unwieldy pattern has one or more ways to condense to a smaller, more declarative, easy to read pattern. This is discussed in a lot of detail in Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17, if you'd like to understand it better.
A common problem most people have in K is the need to translate a common, well known algorithm to K, usually taken from a programming website like geeksforgeeks, or a Wikipedia article. Let us take an example: Matrix Multiplication.
From this wikipedia article, the iterative algorithm for matrix multiplication is as follows:
Input: matrices A and B<br>Let C be a new matrix of the appropriate size<br>For i from 1 to n:<br>For j from 1 to p:<br>Let sum = 0<br>For k from 1 to m:<br>Set sum ← sum + Aik × Bkj<br>Set Cij ← sum<br>Return C
If you want, you can try translating this to K. A direct translation would be:
matmul: {<br>A::x<br>B::y<br>n::#A<br>m::#*A<br>p::#*B<br>C::(n;p)#0<br>i::0<br>j::0<br>k::0<br>sum::0<br>i::x<br>j::x<br>sum::0<br>k::x<br>sum::sum+A[i;k]*B[k;j]<br>}'!m<br>C[i;j]::sum<br>}'!p<br>}'!n<br>C}
This is the worst K code I've ever written, because we are trying to write K like an imperative language, and K doesn't work well with that design. The main problems are:
Many, many globals are assigned
multiple nested loops
lots of modification
Luckily, there are a lot of things we can simplify here, and we can address these problems one by one.
Let us begin at the innermost loop:
sum::0<br>k::x<br>sum::sum+A[i;k]*B[k;j]<br>}'!m<br>C[i;j]::sum
The first and simplest fix we can make is summing using a fold (/).
C[i;j]::+/{<br>k::x<br>A[i;k]*B[k;j]<br>}'!m
One global down, 9 more to go.
The next global we can remove is C. Since ' (each) returns an array, C doesn't need to be modified. We can simply return the value of the nested loop.
i::x<br>j::x<br>+/{<br>k::x<br>A[i;k]*B[k;j] }'!m }'!p }'!n}
Now, we have three loops with no modification, which makes our job much easier. The main variables to look at now are i, j, and k.
i indexes each row of A.
j indexes each column of B.
k indexes each column of A and row of B.
Basically, k is responsible for pairing each row of A with each column of B, which are then multiplied. Hence, we can eliminate the middle man here, and directly match them without k. This also...