J: Self-reference in bubble sort tacit implementation

Question

Since I'm beginner in J I've decided to solve a simple task using this language, in particular implementing the bubblesort algorithm. I know it's not idiomatically to solve such kind of problem in functional languages, because it's naturally solved using array element transposition in imperative languages like C, rather than constructing modified list in declarative languages. However this is the code I've written:

    (((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #

Here's the structure of the statement:

┌────────────────────────────────────────────────────────────────────────────┬──┬─┐
│┌───────────────────────────────────────────────────────────────┬──┬───────┐│^:│#│
││┌───────────────────┬─┬───────────────────────────────────────┐│^:│┌─┬─┬─┐││  │ │
│││┌──────┬─┬────────┐│,│┌──┬─┬────────────────────────────────┐││  ││1│<│#│││  │ │
││││┌──┬─┐│@│┌─┬─┬──┐││ ││$:│@│┌───────────────────┬─┬────────┐│││  │└─┴─┴─┘││  │ │
│││││<.│/││ ││2│&│{.│││ ││  │ ││┌──────┬─┬────────┐│,│┌─┬─┬──┐││││  │       ││  │ │
││││└──┴─┘│ │└─┴─┴──┘││ ││  │ │││┌──┬─┐│@│┌─┬─┬──┐││ ││2│&│}.│││││  │       ││  │ │
│││└──────┴─┴────────┘│ ││  │ ││││>.│/││ ││2│&│{.│││ │└─┴─┴──┘││││  │       ││  │ │
│││                   │ ││  │ │││└──┴─┘│ │└─┴─┴──┘││ │        ││││  │       ││  │ │
│││                   │ ││  │ ││└──────┴─┴────────┘│ │        ││││  │       ││  │ │
│││                   │ ││  │ │└───────────────────┴─┴────────┘│││  │       ││  │ │
│││                   │ │└──┴─┴────────────────────────────────┘││  │       ││  │ │
││└───────────────────┴─┴───────────────────────────────────────┘│  │       ││  │ │
│└───────────────────────────────────────────────────────────────┴──┴───────┘│  │ │
└────────────────────────────────────────────────────────────────────────────┴──┴─┘

Let's apply it to an array:

    (((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: # 5 3 8 7 2
2 3 5 7 8

The thing that confuses me is $: referring to the statement within the outermost parentheses. Help says that:

$: denotes the longest verb that contains it.

The other book (~ 300 KiB) says:

    3+4 
7  
    5*20  
100  

Symbols like + and * for plus and times in the above phrases are called verbs and represent functions. You may have more than one verb in a J phrase, in which case it is constructed like a sentence in simple English by reading from left to right, that is 4+6%2 means 4 added to whatever follows, namely 6 divided by 2.

Let's rewrite my code snippet omitting outermost ()s:

    ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # 5 3 8 7 2
2 3 5 7 8

Reuslts are the same. I couldn't explain myself why this works, why only ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is treated as the longest verb for $: but not the whole expression ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # and not just (<./@(2&{.)), $:@((>./@(2&{.)),2&}.), because if ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is a verb, it should also form another verb after conjunction with #, i. e. one might treat the whole sentence (first snippet) as a verb. Probably there's some limit for the verb length limited by one conjunction.

Look at the following code (from here):

    factorial =: (* factorial@<:) ^: (1&<)
    factorial 4
24

factorial within expression refers to the whole function, i. e. (* factorial@<:) ^: (1&<).

Following this example I've used a function name instead of $::

    bubblesort =: (((<./@(2&{.)), bubblesort@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #
    bubblesort 5 3 8 7 2
2 3 5 7 8

I expected bubblesort to refer to the whole function, but it doesn't seem true for me since the result is correct.

Also I'd like to see other implementations if you have ones, even slightly refactored.

Thanks.

Answer 1

According to this reference (175 KiB) conjunction is:

A part of speech that takes two arguments and typically results in a verb. For example, *:^:3 is a function that iterates squaring three times (^: is a conjunction).

As ^: falls into above-mentioned category, applying it to the arguments results in the longer verb:

((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)

Because $: denotes the longest verb that contains it, it refers to the code just written above.

Similarly, the next ^: makes a new longer verb from ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) and #:

(((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #

which in turn is referred to by $: because it's longer than the previous one.

Since it's the undesirable behaviour, probably the only solution is to split the whole verb so that $: refers to the ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) though it's not a oneliner:

    bubbleiter =: ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)
    bubblesort =: bubbleiter ^: #
    bubblesort 3 1 2 9 2 9 86 5 9 6 9 6 45
1 2 2 3 5 6 6 9 9 9 9 45 86

This article has some comments as to $::

Explaining what $: (self-reference) is and how it's used turned out to be a rather unfortunate starting point for some of those completely new to the language as this is an advanced feature and is atypical of the way things are usually done in J. John mentioned that Roger has commented that he wouldn't include this if he were designing the language now.

Once more, to sum up:

• ^: is a conjunction and makes a new verb from its arguments;
• $: denotes the longest verb that contains it.

Thanks fly out to estanford for dataset 3 1 2 9 2 9 86 5 9 6 9 6 45 in his answer.

Answer 2

I'm looking into it. In the meantime, are you implementing bubblesort because you need bubblesort specifically, or because you just plain need a sort (i.e. could you get away with using /:~ instead)?

EDIT: Have you tried running your bubble sort on a dataset like 3 1 2 9 2 9 86 5 9 6 9 6 45? The system hung when I tried it on my machine, but it works if you replace the ending # with a _.

Answer 3

Here's another approach for implementing bubble sort in J: http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#J