- PVSM.RU - https://www.pvsm.ru -
Предыдущая статья цикла Язык программирования 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 порядков!) отстают от численных массивов.
«Что нужно для того, чтобы создать элегантный язык программирования?».
Айверсон: «Секрет в том, чтобы он выполнял то, что вы от него ожидаете"
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) и некоторые другие. За более подробной информацией рекомендуем обратиться к документации.
Рекурсивная функция быстрой сортировки была показана еще во введении. Разберем другой пример. Запишем на 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 есть ограничение на глубину рекурсии и нет оптимизации хвостовой рекурсии.
Необходимо заметить, что использование подобных рекурсивных выражений рекомендуется лишь для обучения и в случае крайней необходимости.
Подробно на использовании в 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 копирует (глагол «#») из левого операнда (глагол «[») те элементы, которые указаны в «x».
Как мы уже показывали ранее, быструю сортировку можно записать и одной строкой:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)
Напомним, что «$:» означает рекурсивный вызов глагола, а выражение «@» — определяет последовательное вычисление глаголов.
Хотите узнать секрет того, как хорошо писать статьи? Напишите 500 статей.
Roger Hui, «Remembering Ken Iverson», 2004
Здесь необходимо отметить, что код гуру-программистов на J нередко нарушает все указанные выше рекомендации.
Никогда не давайте более одного объяснения происходящему — последнее всегда будет правильным
Кеннет Айверсон.
Однажды я сказал Кену «Знаете, Кен, вы — мой любимый проектировщик языков программирования, а Дон Кнут — мой любимый программист». Кен сразу же спросил: «А что не так с моим программированием?»
— Joey Tuttle, A Celebration of Kenneth Iverson, 2004-11-30
Автор: basp
Источник [7]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/funktsional-noe-programmirovanie/46097
Ссылки в тексте:
[1] Язык программирования J. Взгляд любителя. Часть 3. Массивы: http://habrahabr.ru/post/198228/
[2] http://vector.org.uk: http://vector.org.uk
[3] http://nsl.com: http://nsl.com
[4] http://www.jsoftware.com/jwiki/Links: http://www.jsoftware.com/jwiki/Links
[5] http://jsoftware.com/forums.htm: http://jsoftware.com/forums.htm
[6] http://www.jsoftware.com/jwiki/Essays: http://www.jsoftware.com/jwiki/Essays
[7] Источник: http://habrahabr.ru/post/198230/
Нажмите здесь для печати.