Klong Introduction
================================================================
| KLONG ** A SIMPLE ARRAY LANGUAGE |
================================================================
A Really Short Introduction
By Nils M Holm
n m h @ t 3 x . o r g
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Klong tends to be terse. This is a table formatter:
fmtc::{(-|/{#$x}'x)$x}
fmtt::{+fmtc'+x}
"fmtc" (format column) converts the elements of a list to
strings and right-justifies them so that all strings have the
same length.
"fmtt" (format table) does the same for a two-dimensional array.
In case you are confused now, note that Klong is a mathematical
notation rather than a programming language. If you expect it to
be a programming language, you will only be frustrated and
dismiss it as a "write-only language" and think that it looks
like "line-noise".
While you read program code in most languages line by line, or
maybe even just scan over blocks of text, this will bring you
nowhere when trying to understand Klong. You will have to take
your time and read and write programs one character at a time.
This makes sense, because a single operator, like :^ (Reshape)
may do something quite complex, like reshaping an array:
[2 2 2]:^[1 2 3 4 5 6 7 8]
means: reshape the vector [1 2 3 4 5 6 7 8] to an array of the
dimensions (2,2,2). It will give you:
[[[1 2] :" 1------2 "
[3 4]] :" / /| "
[[5 6] :" / / | "
[7 8]]] :" 3------4 6 "
:" | | / "
:" | |/ "
:" 7------8 "
(:"something" is a comment.)
Klong expressions consist of monadic (single-operand) prefix
operations, dyadic (two-operand) infix operations, and function
applications. They have no precedence rules and evaluate from
the right to the left, i.e.
1-2-3
means
1-(2-3)
but, as usual, parentheses can be used to regroup operations.
A Klong function is simply a program in braces. The function
{x+1}
would increment its argument by 1. There are no argument lists;
a function containing the symbol "x" is automatically a monadic
function receiving its only argument in "x".
A function (or any object) can by assigned to a variable using
the "::" (Define) operator:
inc::{x+1}
However, since Klong is terse, it often does not make sense to
assign a name to a function. For instance, here is factorial:
*/1+!x
(Times Over (one Plus Enumerate x)). It generates a list of the
numbers from 0..x-1, adds one to each element, resulting in 1..x,
and then multiplies all elements of that list. Giving a name to
the function would not really help, especially once you got used
to spotting idioms:
*/1+!x
fac(x)
Functions (which are also called "verbs") can be augmented by
"adverbs". For example,
#'x
(Size-Each x) will return a list containing the size of each
element of x:
#'["hi" "world" [1 2 3]] --> [2 5 3]
The Times-Over in factorial is also an augmented verb. "/"
(Over) folds a verb over an object:
f/[1 2 3 4] = f(f(f(1,2),3),4)
*/[1 2 3 4] = ((1*2)*3)*4
It would be called "fold" or "reduce" in other languages.
Let's get back to the table formatter.
Once you get used to it, it's quite readable. You just have to
adjust your code-reading habits a bit. Here's how to approach
a function like the above:
fmtc::{(-|/{#$x}'x)$x}
There is a parenthesized group, so we deal with that first:
fmtc::{(-|/{#$x}'x)$x}
^^^^^^^^^^^^
In the group there's another function, Size of Format of x,
applied to each member of x:
fmtc::{(-|/{#$x}'x)$x}
^^^^^^^
(Size of Format of x)-Each x. Note that the "x" of the inner
function is different from the "x" of the outer function! This
expression computes the size of the representation (Format) of
each member of a list:
{$x}'[1 23 456] --> ["1" "23" "456"] :"Format-Each"
{#$x}'[1 23 456] --> [1 2 3] :"(Size of Format)-Each"
The next step is
fmtc::{(-|/{#$x}'x)$x}
^^^
(Negate Max-Over it, "it" being the result of the previous
operation). "It", in this context, is the list of sizes obtained
in the previous step. "Max-Over it" is the maximum of the sizes,
"Negate Max-Over it" is the negative maximum size:
|/[1 2 3] --> 3
-|/[1 2 3] --> -3
The rest of the function:
fmtc::{(-|/{#$x}'x)$x}
^^
(Format x with it, "it" here being the negative maximum size
from the previous step.) "$" is an "atomic operator", i.e. it
is automatically applied to each member of a list, e.g.:
3$[1 23 456] --> ["1 "
"23 "
"456"]
So each member of "x" is being formatted with "it". Dyadic
Format (Format2) with a negative left value "v" right-adjusts
its right value in a field of size #v (magnitude of v). So the
function right-justifies all members of its argument in strings
of the length of the greatest member:
(-3)$[1 23 456] --> [" 1"
" 23"
"456"]
and hence:
fmtc([1 23 456]) --> [" 1"
" 23"
"456"]
Now for fmtt:
fmtt::{+fmtc'+x}
(Transpose fmtc-Each Transpose x). Remember to read from the
right to the left:
- Transpose x
- fmtc-Each it
- Transpose it
So +fmtc'+x swaps rows and columns of a table, formats each row,
and transposes the result back. Because fmtc'x would format the
rows of a table, +fmtc'+x formats its columns. Voila, a table
formatter.
BTW, you can really try the above with Klong, because it always
binds the result of the most recent computation to the variable
"it" (user input indented):
fmtc::{(-|/{#$x}'x)$x}
:monad
fmtt::{+fmtc'+x}
:monad
:"Factorials, ordered by column"
+[3 3]:^*\1+!9
[[1 24 5040]
[2 120 40320]
[6 720 362880]]
+it
[[1 2 6]
[24 120 720]
[5040 40320 362880]]
fmtc'it
[["1" "2" "6"]
[" 24" "120" "720"]
[" 5040" " 40320" "362880"]]
+it
[["1" " 24" " 5040"]
["2" "120" " 40320"]
["6" "720" "362880"]]
Nice, isn't it? A table formatter in just 38 characters of code.
One thing that is interesting about this program is that there
are no loops or conditionals in it. This does not mean that
there are no such things in Klong, it only means you do not need
them very often. You use adverbs to do most of the heavy-lifting.
This program computes the square root of 2:
{(x+2%x)%2}:~2
The part in front of the :~ adverb is the formula that computes
the next iteration in Newton's method:
(x Plus 2 Divide x) Divide 2
The :~ (Converge) adverb applies that function to its right
argument initially and then to its own result over and over
again until it finds a fixpoint, i.e. a point where x = f(x).
The :~ operator has a cousin called \~ (Scan-Converge) that
collects the intermediate results:
{(x+2%x)%2}\~2 --> [2
1.5
1.41666666666666666
1.4142156862745098
1.41421356237468991
1.41421356237309504]
(As we can see, Newton's methods converges really fast!)
Of course, Klong has more control constructs. Here is a function
that computes the maximal depth of a tree (a list of lists):
dp:{:[@x;0;1+|/dp'x]}
(If Atom x Then 0 Else 1 Plus Max-Over dp-Each x)
It uses the :[a;b;c] syntax that means "if a then b else c".
The function works as follows: If "x" is an atom (@x, Atom x),
then the result is 0. Else the result is 1 Plus Max-Over
dp-Each x -- the depth of the deepest element of x plus 1.
Are you getting the hang of it?
There are looping constructs, too, but they are rarely used.
{x<1000}{x*2}:~1 --> 1024
When :~ has a left argument, it is called While, and the above
expressions reads "While x Less 1000, x Times 2, starting at 1".
While also has a cousin that scans intermediate results:
{x<1000}{x*2}\~1 --> [1 2 4 8 16 32 64 128 256 512]
However, the above result could be retrieved more easily and
more readably using
{2^x}'!10
(2 Power x)-Each Enumerate 10. !x creates a list of integers
from 0 to x-1 and {2^x}' maps them to their respective powers
of two.
If you have to resort to conditionals and recursion, though,
Klong has those, too. Here's the Peter-Ackermann function:
ack::{:[0=x;y+1:|0=y;ack(x-1;1);ack(x-1;ack(x;y-1))]}
or, if you prefer a multi-line version:
ack::{:[0=x;y+1
:|0=y;ack(x-1;1)
;ack(x-1;ack(x;y-1))]}
The :| means "else-if". The ";" in a function call, like f(1;2),
separates arguments to a dyadic or triadic function, while in a
conditional expression, it separates the predicate and the "true"
and "false" branches.
In programs (but outside of argument lists and conditionals),
it indicates a sequence:
sqr::{[a];a::x;{(x+a%x)%2}:~a}
Here it separates three parts. The first one, [a], indicates
that the function bound to "sqr" has a local variable called
"a". The second one (a::x, a Define x) assigns the value of the
argument "x" to "a". The third one is a generalized form of the
expression computing the square root of two, as shown earlier.
When "sqr" is called, the first part is skipped (because it is
a declaration), the subsequent expressions are evaluated from
left to right, and the result of the last one is returned. So
"sqr" computes the square root of any (positive) number.
Klong programs typically manipulate arrays or lists as a whole
rather than operating on individual elements. They also use
adverbs for finding fixpoints or creating sequences. This is
quite an abstract approach that requires careful planning and
thinking. Typing speed does not really matter when solving
problems in Klong. Understanding the problem properly does.
================================================================