Предыдущая статья цикла Язык программирования J. Взгляд любителя. Часть 3. Массивы
Мы уже столкнулись с тем, что существительное в J — это массив. Даже над одиночными константными значениями допустимы векторные операции. В совокупности все это составляет удобную векторную гомогенную среду программирования.
Однако, очевидно, что у массивов есть и свои ограничения. В связи с тем, что в J по умолчанию только прямоугольные массивы, то и нет возможности стандартными средствами создавать т.н. ступенчатые (jagged) массивы. Кроме того, для списков, состоящих из разнородных элементов, массивы также не подходят.
Для решения этих проблем, в J предусмотрены средства для создания и использования гетерогенных последовательностей – коробок (box). Коробка – это своего рода контейнер, который может хранить в себе произвольный элемент. Массив же из коробок — это, соответственно, своего рода массив из элементов типа (void *). Поэтому, например, первым элементом коробочной последовательности может быть одномерный массив, вторым — число, а третьим — матрица целых чисел.
Для того, чтобы создать коробку надо вызвать монадный глагол «<», чтобы извлечь («раскрыть») элементы из коробки — монадный глагол «>»:
Сама коробка рисуется в ASCII-графике. Извлечем теперь значение коробки:
Для того, чтобы добавить в коробку несколько элементов, предназначен глагол «;», который связывает элементы в последовательность коробок:
Для перечисления элементов такой коробочной последовательности можно использовать уже известные нам части речи. Например, наречие «между»:
Или композиция глаголов:
Далее воспользуемся глаголом «{» для извлечения второго элемента коробки:
В этом примере следует обратить внимание на следующий момент: индексное обращение возвращает коробочный элемент массива, не распаковывая его автоматически.
Из предыдущего выражения можно сделать вывод, что, если мы хотим применить к каждому элементу коробки некоторый глагол, то каждый раз глагол будет принимать операндом обернутое в коробку существительное. Для того чтобы при каждом обращении «вытаскивать» элемент из массива, а после действия «засовывать» результат назад в коробку, можно воспользоваться уже известным нам союзом «&.».
Союз «&.» применяет правый глагол к операнду, и к результату применяется левый глагол. Затем к результату применяется глагол, обратный правому глаголу. Таким образом, мы фактически повторили описанный абзацем выше алгоритм. Воспользуемся этой схемой для удвоения каждого элемента коробки
В связи с тем, что выражение &.> применяется достаточно часто, то оно по умолчанию связано с символом each:
Заметим, что в скорости обработки данных коробки значительно (до 3 порядков!) отстают от численных массивов.
Не всегда есть возможность представить глагол в тацитной форме. Для этого в J есть специальные конструкции, которые мы будем называть императивными. В первую очередь это операции «3 :» и «4 :» (не путайте с константными глаголами «3:» и «4:»). Правый операнд по умолчанию называется «y», левый «x». Например:
Если вы чувствуете, что ваше императивное определение можно записать и в тацитной форме, но вы не знаете как, то можно воспользоваться замечательным стандартным глаголом-преобразованием:
Для записи многострочных глаголов используются схожие конструкции. Причем, как и в большинстве функциональных языках, возвращается последнее высчитанное значение и потому аналога оператора return не требуется. В многострочных глаголах можно также использовать локальные переменные — они определяются с помощью операции «=.». Символом окончания определения глагола является символ «)»
В J также есть и специальные конструкции для проверок условия (.if), циклов(.while) и некоторые другие. За более подробной информацией рекомендуем обратиться к документации.
Рекурсивная функция быстрой сортировки была показана еще во введении. Разберем другой пример. Запишем на Python простую функцию определения длины последовательности так, как будто встроенной такой функции нет.
Для того, чтобы записать в J рекурсивную функцию вычисления длины вектора, нам придется ввести дополнительный глагол-предикат для определения того, является ли существительное последовательностью с хотя бы одним элементом. Назовем этот предикат isa от фразы «is array». Напишем в начале пример использования этого глагола:
Будем определять, является ли операнд вектором длины более чем 1, через глагол извлечения из вектора элемента на определенной позиции. Это глагол «{»
Таким образом, если выражение «1&{» отрабатывает корректно, то считаем, что операнд является массивом с длиной большей, чем 1. Иначе возвращаем ложь (нуль). Мы также добавили в определение запрет на диадный вызов глагола.
Для того, чтобы сымитировать проверку условия воспользуемся союзом @., который вызывает из коробки глагол на той позиции, которая определяется правым операндом. Т.е.
Нам необходимо возвращать длину=1 в том случае, если правый операнд является вектором длиной=1, т.е. если предикат isa на этом существительном возвращает 0.
На месте многоточия мы должны реализовать рекурсивный вызов вычисления длины для хвоста переданной последовательности. Воспользуемся тем, что рекурсивный вызов в J реализуется глаголом «$:». Т.о. получим
Следующим шагом перепишем наш глагол таким образом, чтобы рекурсивный вызов стал хвостовым. Для этого будем хранить накапливаемое значение в левом операнде, и глагол, следовательно, становится диадным:
Определение глагола выглядит достаточно неаппетитным, и в самом деле оно такое и есть. Проиллюстрируем алгоритм глагола len2 примером на языке Python:
Интересно сравнить скорость написанного нами кода. Для этого воспользуемся глаголом «6!:2», который исполняет свой правый операнд столько раз, сколько указано в левом операнде и возвращает среднее время работы каждого запуска в секундах.
Как видим, в данном случае использование встроенных средств J на 3 порядка быстрее наших самостоятельных реализаций. Кроме того, в J есть ограничение на глубину рекурсии и нет оптимизации хвостовой рекурсии.
Необходимо заметить, что использование подобных рекурсивных выражений рекомендуется лишь для обучения и в случае крайней необходимости.
Подробно на использовании в J объектно-ориентированного подхода к программированию мы останавливаться не будем. Интересующимся же скажем, что поддержка ООП в J есть. Подробней читайте, например, в «Learning J».
Отметим, однако, что в J есть специальные конструкции для использования пространств имен, которые имеют схожий с ООП-инструментарием синтаксис.
Начало нового пространства имен следует начинать с выражения:
Где в кавычках надо писать имя пространства имен, которое станет текущим. По умолчанию используется пространство имен '
При обращении к инкапсулированным членам пространства имен необходимо добавлять к каждому элементу суффикс _name_, где «name» – имя пространства имен. Рекомендуется называть пространства имен в верхнем регистре. Приведем наглядный пример:
В заключении раздела приведем один хрестоматийный пример – глагол быстрой сортировки. Сортировку Хоара на J можно записать следующим образом:
Разберем определение построчно:
Как мы уже показывали ранее, быструю сортировку можно записать и одной строкой:
Напомним, что «$:» означает рекурсивный вызов глагола, а выражение «@» — определяет последовательное вычисление глаголов.
Здесь необходимо отметить, что код гуру-программистов на J нередко нарушает все указанные выше рекомендации.
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