J is a pretty cool
programming language. Here's a function
that outputs
Fibonacci numbers:
fib=:1:`((],+/@(_2&{.))@$:@<:)@.*
If you've never seen J before, it's probably not easy to
try to figure out what it does, so I'll try to explain what
it does. I'll begin with pointing out a few things that
will be
helpful:
Functions may take one or two arguments, as in !4
(monadic verb) or 1+2 (dyadic verb). Each verb
may behave differently depending on its use. Arguments
can be functions or values.
Evaluation happens right to left which is, when you get
used to it, pretty intuitive. The idea is that A+B+C is
really "A plus the result of B plus C". There is no
operator precedence.
Finally, arguments in J are always treated as arrays, even
scalars - they're just arrays of rank 0. Thus all functions
can be used on arrays of any rank and size where that
makes sense.
Let's call fib, for example like this:
fib 7
1 1 2 3 5 8 13 21
The argument 7 will be "appended" at the right side of the
expression. Note that negative arguments don't make sense
here since the Fibonacci numbers start at index 0.
The monadic verb *
("sign") is applied to our argument, resulting in
1 if it's positive, 0 if it's zero (and -1 if it's negative)
. The result is passed on to the verb on the left, which is...
@. ("agenda"). This dyadic function acts as something like an
if- or switch-statment of some languages; depending on
the value of its right argument it will return one of the
functions on its left. 0 yields the first, 1 the second
and so on, these functions being separated by `
("gerund").
The first function is 1:, which is basically a
constant function returning the value 1 regardless of its
argument, and it will only get called with argument 0.
Positive arguments will be applied to the function
(],+/@(_2&{.))@$:@<:
(parentheses are only used for "grouping" words into
separate "statements"). This is where the magic happens.
Monadic <: ("decrease") will return its argument minus 1.
@ doesn't really do anything other than passing its argument
on to the left; it's there to prevent the language from
treating this expression as a "fork", a concept that will
be explained below.
$: is a "self reference" i.e. refers to the whole
function again, making a recursion. Here we can see that,
while the argument to fib is positive, the
function will keep calling itself, each time decreasing
the argument by one. However, as we saw above, as soon as
the argument reaches zero, 1 will be returned, and the
recursion can start "unwrapping" itself.
This result is passed on, to the function
],+/@(_2&{.)
The statement
_2&{. returns the two last elements
in it's argument. The dyadic verb
{. ("head") normally
returns elements from the beginning of an array, but the negative left
argument (_2) makes it "wrap around".
& ("compose")
ties an argument to a function, creating a new function.
This is also known as "currying" a function.
@ again passes this result to +/. Dyadic + is
the old familiar plus operator, but the / function
causes it to be inserted between all the elements in the argument,
effectively acting as a "sum over" function. So, now we
have the sum of the two last elements.
] ("right") just gives the right argument back
and , ("append") will put the surrounding arguments
together, creating an array. This way, the first argument
gets appended to itself ({. 1 returns 0 1, filling
the empty parts of the array with zeros), yielding 1 1.
The next time this "inner" function gets called, it's with
this as argument, producing 1 1 2 (since 2=1+1). And so
on, until all recursions have returned. The end result
is the Fibonacci numbers with indexes 0 through 7.
Ahem, "tadaa".