Пользователь
0,0
рейтинг
20 октября 2013 в 01:38

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

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

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (10)

  • +2
    Скажите, пожалуйста, а каким образом в J реализована работа с памятью (я не уловил, но возможно, я что-то пропустил)? Есть ли указатели?
    Какие примитивные типы поддерживаются (в качестве элементов массивов, например) — были упомянуты числа и строки, есть ли другие возможности? Есть ли другие составные структуры данных, кроме массивов и коробок — и можно ли реализовать свои (что, в сущности, возвращает нас к первому вопросу)?
    • +2
      J написан на С. Можно найти исходники. Правда их изучить не представляется возможным, потому что они на С пишут как на джее ))

      Работа с памятью — сишные malloc. Выделяются массивы в куче. Единица данных — n-мерный массив. 0-мерный — скаляр, 1-мерный — вектор, 2-мерный — матрица и т.д. На счет, выделяются ли и скаляры в куче — не знаю, не интересовался.
      Массив имеет всегда одинаковый тип элементов — булевский (0,1), целый, целый с любым количеством знаков, действительный с плавающей точкой, рациональный, комплексный, символьный, symbol ('sdf, 'sdfsfd — нечто похожее на символьный тип в Scheme) и боксы. Боксы — это некий аналог нетипизированных указателей. В массивах из боксов можно хранить разнотипные данные. В боксе можно хранить и другие массивы, поэтому боксами реализуются деревья, например.
      Также есть специальные значения — +бесконечность, -бесконечность, неопределенность.
      Надеюсь, ничего с типами не пропустил.
      • 0
        То есть если нужно реализовать чистый связный список без массивов (например, для графов), использование J никаких преимуществ перед С не дает?
        • +1
          В J связный список не нужен. Такой список – это слишком что-то низкоуровневое. Если Вы пишете программу на относительно низкоуровневом языке, на С, то Вы создаете структуру данных из совсем слабых абстрактно примитивов. И когда Вам для некоторого алгоритма достаточно связного списка, то не нужно создавать больше функционала, на этом Вы и останавливаетесь.

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

          С помощью массивов из боксов (коробок, как здесь написано), можно создавать деревья. Так что можно работать с задачами, которые естественно решаются с помощью деревьев. Графы таким образом, понятно, не создадите, разве что искусственные метки придумать, потому что указателей или ссылок нет и массивы имутабельны. Но задачи с графами можно прекрасно решать матричным способом. Создаете вектор вершин и матрицу переходов.

          Есть еще в J классы. Можно создать кусок кода, любой по форме, который допустим будет хранить и существительные (т.е. данные). А потом создавать экземпляры классов и каждый экземпляр будет иметь свои отдельные данные. Так что можно создать и какую-то сложную абстракцию.

          J написан на С и он, конечно, не может его обогнать по гибкости и возможности оптимизаций. Он дает преимущество – рассматривание задач в другом совершенно виде, в виде матриц/массивов. Совершенно меняется взгляд на алгоритмы. Позволяет задачи решать очень кратко. При этом его быстродействие сравнимо с С.
          • +1
            PS. «по гибкости» — я конечно подразумевал — какие структуры данных можно на С сделать. На джее попросту об этом не заморачиваются. Пусть оптимальную структуру данных подбирает интерпретатор
          • 0
            Большое спасибо, стало гораздо понятнее!

            Безусловно, матрицу смежности как вариант задания графов в памяти никто не отменял.
  • –1
    Офтопик, конечно, но языки прибывают с такой скоростью, что скоро закончатся буквы в латинице. Что безусловно радует )
    • +1
      Они уже закончились :)
  • 0
    Статьи хорошие, да и сам J — очень интересный язык программирования. Однако меня несколько удивило наличие всех этих цифровых глаголов: «1 :» и «4 :» ещё более-менее понятно (т.к., очевидно, эти константы связаны с представлением AST в трансляторе), но «6:!» — это уже что-то за гранью разумного. Есть какое-нибудь логичное объяснение, откуда такие названия?
  • 0
    В дополнение к ссылкам крайне рекомендую J Reference Card for 6.02
    www.jsoftware.com/jwiki/HenryRich?action=AttachFile&do=view&target=J602_RefCard_color_letter_current.pdf

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.