J для смертных. Коробки и циклы

Предыдущая статья цикла J для смертных. Массивы

Коробки

Мы уже столкнулись с тем, что существительное в J - это массив. Даже над одиночными константными значениями допустимы векторные операции. В совокупности все это составляет удобную векторную гомогенную среду программирования.

Однако, очевидно, что у массивов есть и свои ограничения. В связи с тем, что в J по умолчанию только прямоугольные массивы, то и нет возможности стандартными средствами создавать т.н. ступенчатые (jagged) массивы. Кроме того, для списков, состоящих из разнородных элементов, массивы также не подходят.

Для решения этих проблем, в J предусмотрены средства для создания и использования гетерогенных последовательностей – коробки (box). Коробка – это своего рода контейнер, который может хранить в себе произвольный элемент. Массив же из коробок - это, соответственно, своего рода массив из элементов типа (void *). Поэтому, например, первым элементом коробочной последовательности может быть одномерный массив, вторым - число, а третьим - матрица целых чисел.

Для того, чтобы создать коробку надо вызвать монадный глагол «<», чтобы извлечь («раскрыть») элементы из коробки - монадный глагол «>»:

xxxxxxxxxx
> ]x =. <1 2 3 
+-----+ 
|1 2 3| 
+-----+  

Сама коробка рисуется в ASCII-графике. Извлечем теперь значение коробки:

xxxxxxxxxx
> >x 
1 2 3  

Для того, чтобы добавить в коробку несколько элементов, предназначен глагол «;», который связывает элементы в последовательность коробок:

xxxxxxxxxx
> 1;2;2 
+-+-+-+ 
|1|2|2| 
+-+-+-+ 
> (i.10) ; 42 ; (i. 2 3) 
+-------------------+--+-----+ 
|0 1 2 3 4 5 6 7 8 9|42|0 1 2|
|                   |  |3 4 5|
+-------------------+--+-----+  

Для перечисления элементов такой коробочной последовательности можно использовать уже известные нам части речи. Например, наречие «между»:

xxxxxxxxxx
> ;/ i.3 
+-+-+-+ 
|0|1|2| 
+-+-+-+  

Или композиция глаголов:

xxxxxxxxxx
> (#@>)"0 (1 2 3; 2; 3 4) NB. узнаем длину содержимого каждой (ранг = 0) коробки из последовательности 
3 1 2  

Далее воспользуемся глаголом «{» для извлечения второго элемента коробки:

xxxxxxxxxx
> 1 { ;/i.3 
+-+ 
|1|
+-+ 

В этом примере следует обратить внимание на следующий момент: индексное обращение возвращает коробочный элемент массива, не распаковывая его автоматически.

Из предыдущего выражения можно сделать вывод, что, если мы хотим применить к каждому элементу коробки некоторый глагол, то каждый раз глагол будет принимать операндом обернутое в коробку существительное. Для того чтобы при каждом обращении «вытаскивать» элемент из массива, а после действия «засовывать» результат назад в коробку, можно воспользоваться уже известным нам союзом «&.».

Союз «&.» применяет правый глагол к операнду, и к результату применяется левый глагол. Затем к результату применяется глагол, обратный правому глаголу. Таким образом, мы фактически повторили описанный абзацем выше алгоритм. Воспользуемся этой схемой для удвоения каждого элемента коробки

xxxxxxxxxx
> (+: &. >) ;/ i.3 
+-+-+-+ 
|0|2|4| 
+-+-+-+  

В связи с тем, что выражение &.> применяется достаточно часто, то оно по умолчанию связано с символом each:

xxxxxxxxxx
> each 
&.> 
> (+: each) ;/ i.3 
+-+-+-+ 
|0|2|4| 
+-+-+-+  

Заметим, что в скорости обработки данных коробки значительно (до 3 порядков!) отстают от численных массивов.

Определение многострочных глаголов

Секрет того, как создать элегантный язык программирования, заключается в том, чтобы он выполнял то, что вы от него ожидаете

Кеннет Айверсон

Не всегда есть возможность представить глагол в тацитной форме. Для этого в J есть специальные конструкции, которые мы будем называть императивными. В первую очередь это операции «3 :» и «4 :» (не путайте с константными глаголами «3:» и «4:»). Правый операнд по умолчанию называется «y», левый «x». Например:

xxxxxxxxxx
v1 =: 3 : '- y' NB. монада 
v2 =: 4 : 'x + y' NB. диада

Если вы чувствуете, что ваше императивное определение можно записать и в тацитной форме, но вы не знаете как, то можно воспользоваться замечательным стандартным глаголом-преобразованием:

xxxxxxxxxx
> 13 : 'x + y' 
+ 
> 13 : 'x - (y + 1)' 
[ - 1 + ]  

Для записи многострочных глаголов используются схожие конструкции. Причем, как и в большинстве функциональных языках, возвращается последнее высчитанное значение и потому аналога оператора return не требуется. В многострочных глаголах можно также использовать локальные переменные - они определяются с помощью операции «=.». Символом окончания определения глагола является символ «)»

xxxxxxxxxx
> v =: 4 : 0 NB. диада 
  z =. y + 1 NB. выражение "z =: ..." создало бы глобальную переменную z 
  x - z 
  ) NB. Именно так, с непарной закрывающей скобкой
> 3 4 v 1 2 
1 1  

В J также есть и специальные конструкции для проверок условия (.if) , циклов(.while) и некоторые другие. За более подробной информацией рекомендуем обратиться к документации.

Рекурсия

Рекурсивная функция быстрой сортировки была показана еще во введении. Разберем другой пример. Запишем на Python простую функцию определения длины последовательности так, как будто встроенной такой функции нет.

xxxxxxxxxx
def len(xs): 
    """>>> len([1,2,3]) 
    3""" 
    if xs == []: 
        return 0 
    return 1+len(xs[1:])  

Для того, чтобы записать в J рекурсивную функцию вычисления длины вектора, нам придется ввести дополнительный глагол-предикат для определения того, является ли существительное последовательностью с хотя бы одним элементом. Назовем этот предикат «isa» от фразы «is array». Напишем в начале пример использования этого глагола:

xxxxxxxxxx
isa 1 NB. ожидаем 0 
isa i.0 NB. ожидаем 0 
isa 1 2 3 NB. ожидаем 3  

Будем определять, является ли операнд вектором длины более чем 1, через глагол извлечения из вектора элемента на определенной позиции. Это глагол «{»

xxxxxxxxxx
> isa =: ((1: 1&{) :: 0:) : [:  

Таким образом, если выражение «1&{» отрабатывает корректно, то считаем, что операнд является массивом с длиной большей, чем 1. Иначе возвращаем ложь (нуль). Мы также добавили в определение запрет на диадный вызов глагола.

Для того, чтобы сымитировать проверку условия воспользуемся союзом @., который вызывает из коробки глагол на той позиции, которая определяется правым операндом. Т.е.

xxxxxxxxxx
> 3:`4: @. 1 
4: 
> 3:`4: @. 0 
3:  

Нам необходимо возвращать длину=1 в том случае, если правый операнд является вектором длиной=1, т.е. если предикат isa на этом существительном возвращает 0.

xxxxxxxxxx
len =: 1:`(.....) @. isa  

На месте многоточия мы должны реализовать рекурсивный вызов вычисления длины для хвоста переданной последовательности. Воспользуемся тем, что рекурсивный вызов в J реализуется глаголом «$:». Т.о. получим

> len =: 1:`(>:@$:@}.) @. isa 
> len 1 2 3 
3 
> len 17 
1  

Следующим шагом перепишем наш глагол таким образом, чтобы рекурсивный вызов стал хвостовым. Для этого будем хранить накапливаемое значение в левом операнде, и глагол, следовательно, становится диадным:

> len2 =: [`((>:@[) $: (}.@])) @. (isa@]) 
> 1 len2 i.7 
7

Определение глагола выглядит достаточно неаппетитным, и в самом деле оно такое и есть. Проиллюстрируем алгоритм глагола len2 примером на языке Python:

def len2(acc,xs): 
    if xs == []: 
        return acc 
    else: 
        return len2(acc+1, xs[1:])  

Интересно сравнить скорость написанного нами кода. Для этого воспользуемся глаголом «6!:2», который исполняет свой правый операнд столько раз, сколько указано в левом операнде и возвращает среднее время работы каждого запуска в секундах.

> time =: 6!:2 
> x =: i.1000 
> 10 time 'len x' NB. тест рекурсивного глагола 
0.00614873 
> 10 time '1 len2 x' NB. тест глагола с хвостовой рекурсией 
0.00553225 
> 10 time '# x' NB. тест встроеннго глагола для вычисления длины массива 
1.67641e_6  

Как видим, в данном случае использование встроенных средств J на 3 порядка быстрее наших самостоятельных реализаций. Кроме того, в J есть ограничение на глубину рекурсии и нет оптимизации хвостовой рекурсии.

Необходимо заметить, что использование подобных рекурсивных выражений рекомендуется лишь для обучения и в случае крайней необходимости.

Пространства имен

Подробно на использовании в J объектно-ориентированного подхода к программированию мы останавливаться не будем. Интересующимся же скажем, что поддержка ООП в J есть. Подробней читайте, например, в «Learning J».

Отметим, однако, что в J есть специальные конструкции для использования пространств имен, которые имеют схожий с ООП-инструментарием синтаксис.

Начало нового пространства имен следует начинать с выражения:

cocurrent 'name'  

Где в кавычках надо писать имя пространства имен, которое станет текущим. По умолчанию используется пространство имен 'base'. Следовательно, как только блок кода в пространстве имен закончен, надо возвращаться в область видимости по умолчанию с помощью выражения:

cocurrent 'base'  

При обращении к инкапсулированным членам пространства имен необходимо добавлять к каждому элементу суффикс name, где «name» – имя пространства имен. Рекомендуется называть пространства имен в верхнем регистре. Приведем наглядный пример:

> cocurrent 'INNER' 
> rate =: 10 
> v =: 3 : 'rate + y' 
> cocurrent 'base' 
> v_INNER_ 1 
11 
? rate_INNER_ =: 1 
> v_INNER_ 1 
2

Еще один пример

В заключении раздела приведем один хрестоматийный пример – глагол быстрой сортировки. Сортировку Хоара на J можно записать следующим образом:

sel=: 1 : 'x # [' 
quicksort=: 3 : 0 
    if. 1 >: #y do. y 
    else. 
        (quicksort y <sel e),(y =sel e),quicksort y >sel e=.y{~?#y 
    end.
)  

Разберем определение построчно:

• 1 строка. Остановимся вначале на вспомогательном выражении «sel», определенным на первой строке нашего примера. Во-первых, отметим, что выражения типа «1 : 'выражение'» указывают на то, что выражение в кавычках является наречием. Напомним, что под наречием мы понимаем специальную конструкцию, которая модифицирует поведение глагола, вместе с которым это наречие и применяется. В данном случае наречие sel копирует (глагол «#») из левого операнда (глагол «[») те элементы, которые указаны в «x».
• 2 строка. Само же определение глагола быстрой сортировки начинается с выражения 3 : 0, что означает, что у этого глагола допустим только один аргумент.
• 3 строка. На следующей строке проверяется, если 1 больше или равно («>:») длине («#») операнда, то возвращается значение этого операнда, т.к. сортировка не требуется.
• 4-6 строка. Иначе объединяются (глагол «,») результаты 3х рекурсивных вызовов quicksort в массиве. Причем, первыми идут те элементы, которые меньше, чем случайно выбранный элемент «e», потом идут элементы, равные «e», затем элементы, большие «е». В конце выражения определяется значение «е». Причем «{» означает выбор элемента на случайной («?») позиции на отрезке 0..длина_операнда («#y»).
• 7 строка. Завершение определения глагола.

Как мы уже показывали ранее, быструю сортировку можно записать и одной строкой:

> quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)  

Напомним, что «$:» означает рекурсивный вызов глагола, а выражение «@» - определяет последовательное вычисление глаголов.

Заключительная статья цикла J для смертных. Заключение

20 октября 2013