https://github.com/razetime/ngn-k-tutorial/blob/main/c-thinking-in-k.md

Skip to content
 
Sign up

  * Product
      + Features
      + Mobile
      + Actions
      + Codespaces
      + Packages
      + Security
      + Code review
      + Issues
      + Integrations
      + GitHub Sponsors
      + Customer stories
  * Team
  * Enterprise
  * Explore
      + Explore GitHub
      + Learn and contribute
      + Topics
      + Collections
      + Trending
      + Learning Lab
      + Open source guides
      + Connect with others
      + The ReadME Project
      + Events
      + Community forum
      + GitHub Education
      + GitHub Stars program
  * Marketplace
  * Pricing
      + Plans
      + Compare plans
      + Contact Sales
      + Education

[                    ] 

  *  
    #
    In this repository All GitHub |
    Jump to |

  * No suggested jump to results

  *  
    #
    In this repository All GitHub |
    Jump to |
  *  
    #
    In this user All GitHub |
    Jump to |
  *  
    #
    In this repository All GitHub |
    Jump to |

Sign in
Sign up
{{ message }}

razetime / ngn-k-tutorial Public

  * Notifications
  * Fork 2
  * Star 38

  * Code
  * Issues 1
  * Pull requests 0
  * Actions
  * Projects 0
  * Wiki
  * Security
  * Insights

More

  * Code
  * Issues
  * Pull requests
  * Actions
  * Projects
  * Wiki
  * Security
  * Insights

Permalink
main
Switch branches/tags
[                    ]
Branches Tags
Could not load branches
Nothing to show
{{ refName }} default View all branches
Could not load tags
Nothing to show
{{ refName }} default
View all tags

ngn-k-tutorial/c-thinking-in-k.md

Go to file

  * Go to file T
  * Go to line L
  * 
  * Copy path
  * Copy permalink

This commit does not belong to any branch on this repository, and may
belong to a fork outside of the repository.
@razetime
razetime fix link again
Latest commit 1d54f48 May 14, 2022 History
1 contributor

Users who have contributed to this file

148 lines (121 sloc) 5.36 KB
  
Raw Blame
 

  * Open with Desktop
  * View raw
  * 
  * View blame

 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. Most K programming happens through the REPL, because it
is very useful to iterate upon previous code. ngn/k with rlwrap 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
Let C be a new matrix of the appropriate size
For i from 1 to n:
  For j from 1 to p:
    Let sum = 0
    For k from 1 to m:
      Set sum - sum + Aik x Bkj
  Set Cij - sum
Return C

If you want, you can try translating this to K. A direct translation
would be:

matmul: {
  A::x
  B::y
  n::#A
  m::#*A
  p::#*B
  C::(n;p)#0
  i::0
  j::0
  k::0
  sum::0
  {
    i::x
    {
      j::x
      sum::0
      {
        k::x
        sum::sum+A[i;k]*B[k;j]
      }'!m
      C[i;j]::sum
    }'!p
  }'!n
  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
{
  k::x
  sum::sum+A[i;k]*B[k;j]
}'!m
C[i;j]::sum

The first and simplest fix we can make is summing using a fold (/).

C[i;j]::+/{
  k::x
  A[i;k]*B[k;j]
}'!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
    {
      j::x
      +/{
        k::x
        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
eliminates one loop, and removes the need for m.

{
  j::x
  +/A[i]*B[;j] }'!p }'!n}

Next, to remove j, we need to take each column of B and pair it with
A[i]. To do this, we transpose B and pair each element with eachright
(/:).

matmul: {
  A::x
  B::y
  n::#A
  i::0
  {
    i::x
      A[i]{+/x*y}/:+B}'!n }

In order to remove i, we do a similar thing: Use eachleft to pair
each row of A with each column of B.

matmul: {
  A::x
  B::y
  A{+/x*y}/:\:+B }

We need no more globals!

matmul: {x{+/x*y}/:\:+y}

Now that is matrix multiplication in K. This is the most direct
algorithmic conversion of matrix multiplication. Now we will look at
ways to shorten it, and remove more loops.

+ (transpose) is costly, and we can remove it. What we are currently
doing is naive. Instead of multiplying each row of x with each column
of y, we can conform each row of B to the whole of A, doing the same
thing implicitly.

matmul: {x{+/x*y}\:y}

Now, we have a function which can be easily made tacit. With the
rules from Chapter 3, we get our final result:

matmul: (+/*)\:

A matrix multiplication function you can be proud of. This process
may seem like it has a lot of steps, but condensing code will become
much easier and intuitive as you practice your skill in K.

Matrix multiplication is a simple procedure which works well with K's
array support. We will be seeing more algorithms that don't play well
with K, and how to handle them in future chapters.

[                    ] Go
  *  (c) 2022 GitHub, Inc.

  * Terms
  * Privacy
  * Security
  * Status
  * Docs
  * Contact GitHub
  * Pricing
  * API
  * Training
  * Blog
  * About

You can't perform that action at this time.
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session.