Предыдущая статья цикла Язык программирования J. Взгляд любителя. Часть 3. Массивы
1. Коробки
Мы уже столкнулись с тем, что существительное в J — это массив. Даже над одиночными константными значениями допустимы векторные операции. В совокупности все это составляет удобную векторную гомогенную среду программирования.
Однако, очевидно, что у массивов есть и свои ограничения. В связи с тем, что в J по умолчанию только прямоугольные массивы, то и нет возможности стандартными средствами создавать т.н. ступенчатые (jagged) массивы. Кроме того, для списков, состоящих из разнородных элементов, массивы также не подходят.
Для решения этих проблем, в J предусмотрены средства для создания и использования гетерогенных последовательностей – коробок (box). Коробка – это своего рода контейнер, который может хранить в себе произвольный элемент. Массив же из коробок — это, соответственно, своего рода массив из элементов типа (void *). Поэтому, например, первым элементом коробочной последовательности может быть одномерный массив, вторым — число, а третьим — матрица целых чисел.
Для того, чтобы создать коробку надо вызвать монадный глагол «<», чтобы извлечь («раскрыть») элементы из коробки — монадный глагол «>»:
]x =. <1 2 3
+-----+
|1 2 3|
+-----+
Сама коробка рисуется в ASCII-графике. Извлечем теперь значение коробки:
>x
1 2 3
Для того, чтобы добавить в коробку несколько элементов, предназначен глагол «;», который связывает элементы в последовательность коробок:
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|
+-------------------+--+-----+
Для перечисления элементов такой коробочной последовательности можно использовать уже известные нам части речи. Например, наречие «между»:
;/ i.3
+-+-+-+
|0|1|2|
+-+-+-+
Или композиция глаголов:
(#@>)"0 (1 2 3; 2; 3 4) NB. узнаем длину содержимого каждой (ранг = 0) коробки из последовательности
3 1 2
Далее воспользуемся глаголом «{» для извлечения второго элемента коробки:
1 { ;/i.3
+-+
|1|
+-+
В этом примере следует обратить внимание на следующий момент: индексное обращение возвращает коробочный элемент массива, не распаковывая его автоматически.
Из предыдущего выражения можно сделать вывод, что, если мы хотим применить к каждому элементу коробки некоторый глагол, то каждый раз глагол будет принимать операндом обернутое в коробку существительное. Для того чтобы при каждом обращении «вытаскивать» элемент из массива, а после действия «засовывать» результат назад в коробку, можно воспользоваться уже известным нам союзом «&.».
Союз «&.» применяет правый глагол к операнду, и к результату применяется левый глагол. Затем к результату применяется глагол, обратный правому глаголу. Таким образом, мы фактически повторили описанный абзацем выше алгоритм. Воспользуемся этой схемой для удвоения каждого элемента коробки
(+: &. >) ;/ i.3
+-+-+-+
|0|2|4|
+-+-+-+
В связи с тем, что выражение &.> применяется достаточно часто, то оно по умолчанию связано с символом each:
each
&.>
(+: each) ;/ i.3
+-+-+-+
|0|2|4|
+-+-+-+
Заметим, что в скорости обработки данных коробки значительно (до 3 порядков!) отстают от численных массивов.
2. Определение многострочных глаголов
«Что нужно для того, чтобы создать элегантный язык программирования?».
Айверсон: «Секрет в том, чтобы он выполнял то, что вы от него ожидаете"
Fred Brooks, A Celebration of Kenneth Iverson, 2004-11-30
Не всегда есть возможность представить глагол в тацитной форме. Для этого в J есть специальные конструкции, которые мы будем называть императивными. В первую очередь это операции «3 :» и «4 :» (не путайте с константными глаголами «3:» и «4:»). Правый операнд по умолчанию называется «y», левый «x». Например:
v1 =: 3 : '- y' NB. монада
v2 =: 4 : 'x + y' NB. диада
Если вы чувствуете, что ваше императивное определение можно записать и в тацитной форме, но вы не знаете как, то можно воспользоваться замечательным стандартным глаголом-преобразованием:
13 : 'x + y'
+
13 : 'x - (y + 1)'
[ - 1 + ]
Для записи многострочных глаголов используются схожие конструкции. Причем, как и в большинстве функциональных языках, возвращается последнее высчитанное значение и потому аналога оператора return не требуется. В многострочных глаголах можно также использовать локальные переменные — они определяются с помощью операции «=.». Символом окончания определения глагола является символ «)»
v =: 4 : 0 NB. диада
z =. y + 1 NB. выражение "z =: ..." создало бы глобальную переменную z
x - z
) NB. Именно так, с непарной закрывающей скобкой.
3 4 v 1 2
1 1
В J также есть и специальные конструкции для проверок условия (.if), циклов(.while) и некоторые другие. За более подробной информацией рекомендуем обратиться к документации.
3. Рекурсия
Рекурсивная функция быстрой сортировки была показана еще во введении. Разберем другой пример. Запишем на Python простую функцию определения длины последовательности так, как будто встроенной такой функции нет.
def len(xs):
""">>> len([1,2,3])
3"""
if xs == []:
return 0
return 1+len(xs[1:])
Для того, чтобы записать в J рекурсивную функцию вычисления длины вектора, нам придется ввести дополнительный глагол-предикат для определения того, является ли существительное последовательностью с хотя бы одним элементом. Назовем этот предикат isa от фразы «is array». Напишем в начале пример использования этого глагола:
isa 1 NB. ожидаем 0
isa i.0 NB. ожидаем 0
isa 1 2 3 NB. ожидаем 3
Будем определять, является ли операнд вектором длины более чем 1, через глагол извлечения из вектора элемента на определенной позиции. Это глагол «{»
isa =: ((1: 1&{) :: 0:) : [:
Таким образом, если выражение «1&{» отрабатывает корректно, то считаем, что операнд является массивом с длиной большей, чем 1. Иначе возвращаем ложь (нуль). Мы также добавили в определение запрет на диадный вызов глагола.
Для того, чтобы сымитировать проверку условия воспользуемся союзом @., который вызывает из коробки глагол на той позиции, которая определяется правым операндом. Т.е.
3:`4: @. 1
4:
3:`4: @. 0
3:
Нам необходимо возвращать длину=1 в том случае, если правый операнд является вектором длиной=1, т.е. если предикат isa на этом существительном возвращает 0.
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 есть ограничение на глубину рекурсии и нет оптимизации хвостовой рекурсии.
Необходимо заметить, что использование подобных рекурсивных выражений рекомендуется лишь для обучения и в случае крайней необходимости.
4. Пространства имен
Подробно на использовании в 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
5. Пример
В заключении раздела приведем один хрестоматийный пример – глагол быстрой сортировки. Сортировку Хоара на 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<#)
Напомним, что «$:» означает рекурсивный вызов глагола, а выражение «@» — определяет последовательное вычисление глаголов.
6. Советы
Хотите узнать секрет того, как хорошо писать статьи? Напишите 500 статей.
Roger Hui, «Remembering Ken Iverson», 2004
- Помните, что исходный код читают гораздо чаще, чем пишут. Для J это особенно актуально.
- Давайте глаголам значимые названия. Не используйте имена типа v1, v2 и т.п.
- Обязательно пишите комментарии для каждого глагола с примером вызова глагола.
- Обязательно пишите юнит-тесты.
- Ставьте в тацитных глаголах пробелы и скобки даже там, где они необязательны. Выражения «+/:+*:~1:» и «+ /: (+ *:~ 1:)» вычисляются хоть и одинаково, но последнее читается легче.
Здесь необходимо отметить, что код гуру-программистов на J нередко нарушает все указанные выше рекомендации.
- Учитывайте, что глагол может быть вызван не так, как вы это задумывали: предусмотрите и монадный и диадный вызов. Сообщения об ошибках у J не очень информативны.
- Делайте компактные определения глаголов. Два глагола длиной по 20 символов читаются человеком легче, чем один глагол длиной в 40 символов.
- Если глагол рассчитывает «книжную» математическую формулу, то пишите его в тацитной форме только в том случае, если это значительно повышает эффективность вычислений. В остальных случаях пишите с явным указанием операндов.
- Используйте циклические императивные и рекурсивные конструкции только при необходимости. Хотя они иногда и облегчают чтение программы, но они очень медленны. Используйте наречия «/», «» и подобные им.
- Рассмотрите возможность определять все файлы как ООП-модули.
- По возможности, не используйте глобальные переменные.
- Прочитайте книгу «J for C programmers». Обратите особое внимание на главы с названием «Loopless code».
7. Что читать дальше
Никогда не давайте более одного объяснения происходящему — последнее всегда будет правильным
Кеннет Айверсон.
- http://vector.org.uk — очень солидный журнал от Британской ассоциации APLщиков. Статьи в основном про язык APL, но много статей и по языкам J, Q, K. Все можно скачать в электронном виде. Крайне рекомендуется.
- http://nsl.com — название сайта расшифровывается как «no stinking loops». На сайте много примеров разной степени сложности. В основном на языке K. Есть, к примеру, реализация ленивого подмножества языка К на самом К.
- http://www.jsoftware.com/jwiki/Links — сборник ссылок на полезные ресурсы по языку J.
- http://jsoftware.com/forums.htm — список почтовых рассылок J. (активность достаточно высокая — например, в основном разделе «Programming»в среднем по 8-12 сообщений в день).
- http://www.jsoftware.com/jwiki/Essays — не забывайте и про этот «неиссякаемый источник мудрости»- сборник статей и примеров с комментариями. Среди эссе можно найти, например, решатель судоку в 30 строчек.
Вместо заключения
Однажды я сказал Кену «Знаете, Кен, вы — мой любимый проектировщик языков программирования, а Дон Кнут — мой любимый программист». Кен сразу же спросил: «А что не так с моим программированием?»
— Joey Tuttle, A Celebration of Kenneth Iverson, 2004-11-30
Автор: basp
