-- Leo's gemini proxy
-- Connecting to gemini.sh0.xyz:1965...
-- Connected
-- Sending request
-- Meta line: 20 text/gemini
For a little background...
Every year I try to pick up a new programming language to increase the size of my development toolbox. Learning new and different paradigms, trying to pick a language based on the problem. In 20+ years of development I've probably got 15 different languages out in production in some shape or form.
Last year my interest was peaked when YouTube started suggesting I watch some presentations on APL. This was my first Array programming language, and first language to use a very esoteric glyph syntax. Its interesting to look at, requires a special keyboard setup or a special IDE. To find all prime numbers up to R...
(~R∊R∘.×R)/R←1↓⍳R
After a while I struggled to keep up with studying APL when its use was difficult to integrate into any aspect of my daily development life. I use dc or my HP-35 calculator when I have to do math and R when I need to do statistical analysis and graphing. So I dropped learning it until I found out that a new language existed, created by the same developers, and it used ASCII characters in place of the UTF-8 glyphs. That was how I started learning J.
In this post I wanted to run through a simple example of a problem to show the process. The expressive nature of J (and APL and BQN) allows you to think mathematically and just write what you're thinking. I picked the first problem from Project Euler as it will demonstrate just enough to show J's power.
> If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
>
> Find the sum of all the multiples of 3 or 5 below 1000.
The task is a play on the well known FizzBuzz problem, finding multiples within an arbitrary range of numbers. Its a perfect problem for an array language.
tl;dr - here is my solution
sln =: {{ x +/ @ ~. @ , @ (] #~ =&0 @ |/) i.&.<: y }}
Now to walk through how to get there.
This post is going to be a 100mph crash course. I'm writing it to show just how easy and intuitive the problem solving process is. If it looks interesting then I suggest the book "Learning J" as a great place to start. The J Language website also has a vocabulary list hosted on their wiki.
There are two types of methods in J: Monadic and Dyadic. Monadic verbs take a single argument (f y) and Dyadic takes two (x f y). The arguments can be a single number (scalar), a list of numbers (array) or multi dimensional arrays (report). There are a few other interesting bits we will hit along the way, but for now lets start up the repl and get solving.
Oh and everything in J is based on parts of grammar (verbs, nouns, adverbs, etc). Methods are verbse, values are nouns, adverbs modify verbs, conjunctions connect verbs together. It makes the whole process of reading the code much easier once you understand this design.
*Note* Repl input is indented, output isn't.
Lets start with the example solution: Find the values from 1 to 9 that are divisible by 3 or 5 and sum them. The first step is to create the list from 1 to 9. Using the Integers verb (i. y) ...
i. 10 0 1 2 3 4 5 6 7 8 9
...the list result is slightly off. It contains 0. One possible solution is to make the list from 0 to 8 and add 1 to the list. With an array language the math operators understand how to deal with different shaped arrays.
1 + i. 9 1 2 3 4 5 6 7 8 9
The next step is to figure out which values are divisible by 3 or 5. Using the Residue verb (x | y) we can create a list of remainders.
3 | 1 2 3 4 5 6 7 8 9
1 2 0 1 2 0 1 2 0
5 | 1 2 3 4 5 6 7 8 9
1 2 3 4 0 1 2 3 4
Being an array language we want the two different results returned in a single result.
3 5 | 1 2 3 4 5 6 7 8 9 |length error | 3 5 | 1 2 3 4 5 6 7 8 9
The problem is we are trying to apply a 2x1 array to a 10x1 array. What we need is to run Residue (x | y) with 3 and then with 5 resulting is a 10x2 array. To do this we use the adverb Table (v/) to convert the Residue (x | y) into one expecting an array for the left argument (x |/ y):
3 5 |/ 1 2 3 4 5 6 7 8 9 1 2 0 1 2 0 1 2 0 1 2 3 4 0 1 2 3 4
Rewriting it to use everything so far:
3 5 |/ 1 + i.9 1 2 0 1 2 0 1 2 0 1 2 3 4 0 1 2 3 4
The last step is to find all of the positions that give remainders of 0. We can test a value with the Equal (x = y).
3 = 0
0
0 = 0
1
To make a new monadic verb where we don't have to pass in the 0 we can use the Bond conjunction (v & n):
(= & 0) 3
0
(= & 0) 0
1
3 5 (= & 0) |/ 1 + i. 9
1 1
That doesn't look right. Turns out that we have run into another oddity of the language: combinators.
It turns out that in J if you are writing point free code (composing methods together without arguments) there are built in combinators that automatically arrange arguments and methods in defined orders. The two combinators used are Hook (u v) and Fork (f g h).
Hook is a combinator that takes two verbs (u and v), one (y) or two (x y) nouns and returns a noun. From the diagram you can see it looks like a "hook".
(u v) y <=> y u (v y)
x (u v) y <=> x u (v y)
result
|
u
/ \
x or y v
|
y
This makes it easy to write an operation that requires both a modified and unmodified version of an argument. For example, if you have an array and wanted to get the ratio of each element compared to the sum of the array you could write
a =: 1 2 3
a % (+/ a)
0.166667 0.33333 0.5
But with the Hook combinator putting two verbs together the noun doesn't need to be duplicated.
(% +/) a 0.166667 0.33333 0.5
Fork is combinator that takes three verbs (f g h), one (y) or two (x y) nouns and returns a noun. From the diagram you can see it looks like a "fork".
(f g h) y <=> (f y) g (h y)
x (f g h) y <=> (x f y) g (x h y)
result
|
g
/ \
/ \
/ \
f h
[/]\ [/]\
[x] y [x] y
Calculating the average of an array is made much more simple using a Fork:
(+/ 1 2 3 4 5) % (# 1 2 3 4 5)
3
(+/ % #) 1 2 3 4 5
3
If you coming from a procedural background you're probably used to writing code with a lot of variables. Arguments passed in are stored in a variable, the results of many steps in the process are stored in variables. In languages that support a point free paradigm, or sometimes called tacit programming, expressions are connected together without the use of variable. Function composition allows you to connect each step piping the result from one step into the arguments of the next. This works great if everything is one argument in, one value out. But when you start creating more complex code you need to be able to rearrange how the piping of data occurs. Combinators allow this to happen without the use of variables.
3 5 (= & 0) |/ 1 + i. 9 1 1
On a second look we can see that a Hook is being executed here.
u =: = & 0 NB. Equal to 0
v =: |/ NB. Create a table of y modulo x
3 5 (u v) 1 2 3 4 5 6 7 8 9
1 1
3 5 u (v 1 2 3 4 5 6 7 8 9)
1 1
What we want is for the "equal to zero" check only be performed on the results of the modulo operation. The problem is that in a Hook J assumes you want to pass two nouns to the second verb (u), the modified noun (v y) and the original (y). What we really want is for the second verb to only get a single noun, the modified (v y).
To do this we can use a Fork instead of a Hook, only there is still a problem. Fork also assumes the last verb run takes two nouns. What we need is a verb that returns no noun. That verb is called Cap ([:).
f =: [: NB. Cap
g =: = & 0 NB. Equal to Zero
h =: |/ NB. Create a table of y modulo x
3 5 (f g h) 1 2 3 4 5 6 7 8 9
0 0 1 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0
3 5 ([: =&0 |/) 1 + i. 9
0 0 1 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0
Now we have a truth table indicating which values from our right argument is divisible by 3 or 5. We can use Copy (x # y) to convert a list of values and bitmask to just the masked values:
0 1 0 1 # 1 2 3 4
2 4
1 0 0 1 # 9 8 7 6
9 6
The problem we have now is that the value on the left is the mask and the value on the right is the data to mask. As J is read right to left the mask will be on the wrong side. We can use the adverb Reflex (u~) to reverse the way the nouns are passed to the verb.
0 1 0 1 # 1 2 3 4
2 4
1 2 3 4 #~ 0 1 0 1
2 4
To insert the 1 to 9 array into the correct position we can access it using the Same (x ] y) verb. There are two forms, one calling the right value and one calling the left.
3 ] 5
5
3 [ 5
3
Add the Reflex Copy using Same and we get...
3 5 (] #~ [: =&0 |/) 1 + i. 9 3 6 9 5 0 0
The results on the top row are the values divisible by 3 (3, 6, 9). The bottom is for 5. The two extra zeros in the bottom row are added for padding to maintain the shape of the table. The next step is to create a single array from the two row and remove the duplicates. 15 is divisible by both 3 and 5 but per the instructions it should be counted only once which is why we remove duplicates.
Joining two rows can be done using Ravel (, y). It takes a two dimensional array and converts it to a list.
] x =: 3 3 $ i. 9
0 1 2
3 4 5
6 7 8
, x
0 1 2 3 4 5 6 7 8
Ravel (, y) also as a dyatic version called Append (x , y) which we do not want to call. To make sure a Hook or Fork doesn't add a left side argument we use Cap ([:) again.
3 5 ([: , ] #~ [: =&0 |/) 1 + i. 9 3 6 9 5 0 0
To remove duplicates we use the verb Nub (~. y)
~. 0 1 0 2 2 3 0 1 2 3
Since Nub is monadic and the last operation ended in a Cap, rather than continuing that sequence we can use Atop (u @ v). This conjunction creates a combinator that executes v first as a monad (v y) or dyad (x v y) and then u always as a monad (u (x v y)).
u =: +: NB. Double
v =: * NB. Times
u 2
4
u 4
8
1 2 3 (u @ v) 10 100 1000 NB. x * y * 2
20 400 6000
Adding Nub and Atop into our solutions we have a Set of multiples.
3 5 ([: ~.@, ] #~ [: =&0 |/) 1 + i. 9 3 6 9 5 0
The last step is to add the list together with Add Table (+/ y).
3 5 ([: +/ [: ~.@, ] #~ [: =&0 |/) 1 + i. 9 23
Matches our example. Problem Solved!
There are a few refactors that can be done to make things more simple or easier to read.
First lets fix the right hand list. Rather than making a list from 9 and adding 1, we want to just supply 10. To do this we can the conjunction Under ([x] u&.v y). This conjunction runs verb v and then applies u to each cell of the result. Then it does the inverse of the verb v on the result of u. At first this might not seem useful but lets look at what we are doing.
We want to input the value 10 and get a list 1 to 9. To do this we create a list (i.) with 9 and then increment by 1. We Decrement (<: y) 10 by 1, make a list (i. y) , then increment (>: y) the list by 1. v, then u, then the opposite of v.
<: 10
9
i. 9
0 1 2 3 4 5 6 7 8
>: 0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
i. &. <: 10
1 2 3 4 5 6 7 8 9
Our solution is now
3 5 ([: +/ [: ~.@, ] #~ [: =&0 |/) i.&.<: 10 23
The code has quite a few Cap ([:) verbs to force Forks instead of Hooks. To force a Fork we can use the conjunction Atop ([x] u@v y).
3 5 ([: +/ [: ~.@, ] #~ [: =&0 |/) i.&.<: 10
23
3 5 +/ @ ([: ~.@, ] #~ [: =&0 |/) i.&.<: 10
23
3 5 +/ @ ~. @ , @ (] #~ [: =&0 |/) i.&.<: 10
23
3 5 +/ @ ~. @ , @ (] #~ =&0 @ |/) i.&.<: 10
23
Our final solution can be written with the Direct Definition control operators ({{) and (}}). These allow you to directly place the nouns x and y.
sln =: {{ x +/ @ ~. @ , @ (] #~ =&0 @ |/) i.&.<: y }}
3 5 sln 10
23
3 5 sln 1000
233168
This results in the following steps
(i.&.<: y) Given y, create a list of integers 1 to y exclusive
(x |/) Create a table of remainders when dividing the array by x
(=&0) From this table find all instances where the remainder is 0
(] #~) Map the new truth table against the list of integers
(,) Join the rows of multiples
(~.) Remove any duplicates
(+/) Finally sum the list to get our solution
There are certainly much prettier solutions, shorter solutions that use more complex computation and other "tricks" that make this language so nice. Reading from right to left each operator does exactly the mathamatical operation we expect in how to solve this problem. No complicated loops or indexing. The solution does not assume a number of divisors on the left nor the size of the list of numbers on the right.
When we write a procedural solution we may think in this same way, but it always has to be modified to handle all the steps required by the language that aren't directly related to the math of the solution. Often times these are steps that we screw up. The math looks right but we get a wron answer. With languages like J those steps often do not exist.
If you're in the market for a new language and want to try array programming, I highly recommend taking a look at J. In the beginning its difficult to read other's programs but eventually it will just click.
$ published: 2023-01-01 22:50 $
$ tags:j,programming $
-- CC-BY-4.0 jecxjo 2023-01-01
-- Response ended
-- Page fetched on Tue May 21 20:34:50 2024