Язык программирования J. Взгляд любителя. Часть 4. Коробки и циклы. Заключение

в 21:38, , рубрики: ненормальное программирование, тацитное программирование, функциональное программирование, метки:

Предыдущая статья цикла Язык программирования 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js