Язык программирования J, введение.

[dr_klm]

Предлагаю вашему вниманию краткое введение в язык программирования J, которое я написал на протяжении последних выходных. Познакомился я с этим языком чуть больше месяца назад, когда искал способ удобного программирования на КПК. Весь этот месяц в свободное время я читал книги и статьи по J, K и APL. Игрался с чужими программами, писал свои, тривиальные и написал недавно свою первую, нетривиальную (которая в этом введении разобрана и улучшена). Мое общее впечатление от J -- восхищение.

Так что читайте, комментируйте... если найдете ошибки или неясности -- говорите.


Язык программирования J, введение.

© 2004 Константин Л. Метлов <metlov@fti.dn.ua>
All rights reserved.
Эволюционные ветви.

В наше время всеобщей компьютерной грамотности сложно найти активного человека, который не имел бы представления о языках программирования, позволяющих управлять работой компьютера. Но даже среди специалистов можно услышать мнение -- "все языки похожи." И действительно, среди популярных языков (таких как С, С++, Java, Python), произошедших от Fortran-а, спор идет разве-что о деталях реализации и синтаксиса. При всем отличии этих деталей, программа, написанная на одном из этих языков, как правило, легко читабельна человеком, знакомым с любым другим...

В основе этого подобия лежит историческая постановка программирования, как задачи о перемещении (с обработкой) данных из одиних ячеек оперативной памяти компьютера в другие, причем, перемещение поэлементное. Ассемблер (в противоположность программированию в машинном коде) дал возможность называть ячейки и их группы символическими именами. В Fortran-е над именованными ячейками были введены платформно и архитектурно-независимые операции. Потом, язык С предоставил еще бОльший архитектурно-независимый доступ к ресурсам компьютера, позволив непосредственно оперировать ссылками и указателями на ячейки в линейной оперативной памяти. Даже в языках C++ и Java программа -- всего-лишь линейная (с разветвлениями и циклами) инструкция по перемещению (с обработкой) данных, расположенных в линейной-же памяти, а языки эти -- всего-лишь варианты языка линейной машины Алана Тьюринга (которому и принадлежит, упомянутая в начале этого абзаца историческая постановка), где операторы представляют из себя комбинации тьюригновских команд. Эволюция этих языков шла в направлении сокрытия различий между различными реализациями тьюринговских машин, тем не менее, предоставляя как можно более прямой доступ к тому, что, собственно, между этими машинами общего (тоесть к тьюринговским одномерным "ленте-памяти" и "ленте-программе" с пронумерованными командами для осуществления переходов). Апофеозом этой эволюции являются, наверное, языки для виртуальных машин Python и Java, где межплатформные различия сглажены наиболее сильно, но все равно программы выглядят и читаются как Fortran.

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

Обобщая, можно сказать, что упомянутая ветвь языков развивалась по принципу: "Быть как можно ближе к 'железу' (т.е. тьюринговской машине), абстрагируя отличия между разными его реализациями." Ничего плохого во всем этом конечно-же нет, но факт есть факт: железо в этих языках определило ход их эволюции, и его особенности удастся спрятать только в пределе. К тому-же, железо тоже постоянно эволюционирует и уже, на сегодняшний день, далеко от скалярного, одномерного, однопроцессорного тьюринговского.

Параллельно с описанной ветвью развивалась и другая. Ее отсчет, наверное, следует начать с книги "A Programming Language" Кена Иверсона (Kenneth E. Iverson, 1961), где автор описал язык APL. За создание и работу над этим языком Иверсон получил, впоследствии, премию Тьюринга. Его тьюринговская лекция (Kenneth E. Iverson: Notation as a Tool of Thought. Commun. ACM 23(8): 444-465(1980)) утверждает основные принципы, положенные в основу APL, главным из которых, с моей точки зрения, является отказ следовать при разработке языка за тонкостями реализации тьюринговских машин (предоставив это разработчикам компиляторов и интерпретаторов), а сделать язык программирования отражением математических идей и обьектов по аналогии с математической записью, сделать его настолько компактным, чтобы с его помощью можно было не только управлять вычислениями компьютера, но и думать...

Язык APL был реализован на больших ЭВМ (тех самых, что занимали когда-то этажи и подвалы некоторых зданий), использовался в областях, требующих эффективную обработку больших обьемов данных (прежде всего в банках и на биржах), но широкой популярности "в народе" не получил. Причин тут несколько: во-первых, народные компьютеры, начиная с оснащенных процессорами Z80 были абсолютно скалярными; во-вторых, большие обьемы данных (где, собственно, и проявлялась сила APL) в эти компьютеры не помещались в принципе; а кроме того, в APL широко использовались нестандартные символы (не попавшие в ASCII), отсутствующие на "обычных" клавиатурах и в стандартных, прошитых в ПЗУ "народных" знакогенераторов шрифтах. За нестандартные символы ныне седеющие злые языки прозвали APL "китайским бейсиком". ;-) Язык этот, хоть жив и поныне, оказался обречен на существование (хоть далеко и небезуспешное) в рамках отдельно взятых элитарных клубов.

Но история на этом не закончилась, вмешались закон Мура и интернет. В силу первого, мощность "домашних" процессоров возросла на порядки, в них (как, например, в процессоры серии i386) даже начали добавлять векторные инструкции. В силу второго (а так-же гигантского прорыва в области магнитной записи, приведшему к появлению в городских супермаркетах терабайтных жестких дисков), каждому стали доступны те самые "гигантские" обьемы данных, для обработки которых так удобен APL. Казалось-бы, APL должен пережить второе рождение, но его символы так и не вошли в стандартные кодировки, затрудняя обмен программами в интернете, а значит и широкое распространение языка. Барьер входа оказался очень высок.

Видя и предвидя, в 1980-е годы Иверсон, вместе с коллегами, из которых я упомяну здесь Роджера Хуи (Roger Hui) и Артура Уитни (Arthur Whitney)), начали проэкт по разработки новой версии языка APL, окончательно получившей название J. В этом языке, официально ведущем свою историю с 1990-го (впервые упомянут в статье R. K. W. Hui, K. E. Iverson, E. E. McDonnell, and A. T. Whitney, "APL/?," APL90 Conference Proceedings, APL Quote Quad 20, No. 4, ACM, New York 1990, описан в книге Kenneth E. Iverson: J Introduction and Dictionary. Iverson Software, Toronto, Canada, 1991), был учтен опыт APL во многих областях. В частности, были систематически введены векторные операции над многомерными массивами (используя "ранг" оператора и "k-ячейки"). Алфавитом этого языка стал, наконец, ASCII. Разницу между APL и J можно, наверное, сравнить с разницей между Fortran-ом и C (или даже с C++, если учесть, что J поддерживает обьектно-ориентированное программирование).

Однако история и тут оказалась нелинейной (см. Kenneth E. Iverson: A Personal View of APL, IBM Systems Journal, Vol. 30 No. 4 1991 на английском). В начале разработки J от группы отделился Артур Уитни и занялся разработкой собственного языка, который он назвал K. Одним из разногласий (ни в коем случае не личного характера) между Уитни и Иверсоном было чрезмерное (по мнению Уитни) усложнение языка J понятиями ранга (в K операторы просто действуют поэлементно), а так-же избыток возможностей (комплексные числа, трехмерная графика). Хотя, кстати, центральная идея о рангах принадлежит именно Уитни, который представил ее Иверсону в 1982-м на конференции по APL в Гейдельберге, заметив, что свертка массива вдоль одной из осей (+/[I] A) может быть записана при помощи оператора присвоения ранга (+/"I A), такая вот запутанная история. Тем не менее, в K ранга нет. Язык K получился проще, компактнее, и оказался отлично приспособлен к сфере баз данных. Компания Уитни (Kx Systems) разработала на этом языке реляционную базу данных под названием kdb, являющуюся на сегодняшний день продуктом-лидером в этой области и превосходящую, в частности, широко разрекламированный Oracle по скорости на тестах TPC. Ходят слухи, что исходники базы данных kdb (поддерживающей SQL, ODBC, JDBC, удаленный доступ по http и множество других функций, стандартных в этой области) хранятся в 26-ти, названных однобуквенными именами, текстовых файлах, содержащих, каждый, примерно один полный стандартный экран кода, просмотреть который можно без скроллинга. Еще говорят, что в kdb нет ни одного цикла. Может быть эти слухи и неправда, но то, что дистрибутив kdb полностью (вместе с интерпретатором K, примерами), занимает (всего !) 200 килобайт -- это доступный независимой проверке факт. И все-же, дальше мы будем говорить о языке J, который реально предоставляет больше возможностей чем K для широкого не специализированного круга задач. Продолжая натянутые аналогии, скажу, что разница между J и K примерно как между C и Pascal-ем (ну, или C++ и обьектным Паскалем, поскольку в K тоже можно программировать с обьектами).

Итак, давайте-же засучим рукава и начнем баловаться...

Для баловства нам понадобятся: установленная последняя версия интерпретатора J, ссылки на словарь и разговорник (включены в дистрибутив).
Выпуклая оболочка (convex hull)

Наверное, лучшим способом "почувствовать" язык является написание на нем некоторой нужной (а потому, как правило, классической ;-) программы. Конечно, написание не-классических программ, если только они окажутся кому-нибудь нужны, сулит бОльшие барыши, но написание классических для баловства с новым языком подходит лучше, позволяя сравнить результат с другими.

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

Что такое выпуклая оболочка ? Представьте себе, что плоскость -- кусок резины, а в нее мы случайным образом натыкали булавок (это будут наши точки), если мы теперь возьмем нитку и затянем ее вокруг всех булавок, то она коснется только некоторых (внешних), а форма ее как раз и будет соответствовать "выпуклой оболочке". Задачей нашего алгоритма будет -- найти и перечислить по порядку булавки, которых коснется нитка.

Взляните на картинку:
^ | 5+ [*] | 4+ [*] | 3+ | 2+ [*] | 1+ [*] | --[*]--+---+---+---+---+---+---+---+---+---+---*---+---+----> -2 -1 0| 1 2 3 4 5 6 7 8 9 10 11 -1+ [*] | -2+ [*] [*] | -3+ | -4+ [*] | -5+ | -6+ [*] |
Выпуклой оболочкой этого множества будут (в порядке обхода против часовой стрелки) точки с координатами (-2,0), (1,-6), (5,-4), (10,-1), (8,5), (2,4). Теперь нам нужно написать программу, которая так-же легко решила-бы эту задачу... а так-же и любую другую, подобную, в которой точек был-бы хоть миллион...

Что делать ?

Задача эта тоже имеет свою историю, с алгоритмами, начиная от наивного, время работы которого растет как N^2 при увеличении количества точек, и заканчивая очень хитрыми, рандомизированными, время работы которых зависит от результата (количества точек в окончательной оболочке), с промежуточным, надежно масштабирующимся как N log N, алгоритмом Грехема, который мы здесь и реализуем.

Алгоритм этот заключается в том, чтобы отсортировать (время сортировки N log N) точки по углам, относительно самой левой из них (которая по определению принадлежит оболочке). А потом, пройдя по образовавшемуся звездообразному контуру последовательно (за время ~N), начиная с левой точки, удалить все, угол при которых (относительно внутренности многоугольника) выгнут наружу (>180ˆ). Те точки, что останутся, будут образовывать вогнутые углы, а значит оболочка получится выпуклой.

Давайте теперь с Вами запустим интерпретатор J и займемся решением поставленной задачи. Установили ? Запустили ?

Когда Вы запустите интерпретатор перед вами в окошке появится мерцающий курсор, отстоящий от левого края окна ровно на 3 пробела. Это поле для ввода. Если набрать что-нибудь, а потом нажать <ВВОД> выражение будет вычислено, а в следующей строке появится ответ. Давайте-ка что-нибудь наберем ! Например:

2+2 4
О ! Работает !

В языке J отрицательные числа отмечаются знаком подчеркивания (_) вместо минуса (-) как в других языках. Это позволяет легко отличить минусы, которые являются частью определения констант, от минусов, являющихся операциями. В частности:

2-4 _2
Тоесть минус 2. Вообще, примитивные операции в J (глаголы, verbs, как назвали их создатели языка, подчеркивая, что они обозначают действие) кодируются комбинациями символов из ASCII, одиночными и парными. Причем, операция, обозначаемая одной и той-же комбинацией символов, зависит от количества переданных глаголу аргументов. Аргументов этих может быть либо два (справа и слева от глагола), тогда мы имеем дело с диадным случаем глагола; либо один (справа), тогда перед нами монадный случай. Вот например, только что мы использовали глагол "-" (минус) в диадном случае, когда он обозначает "вычитание". В монадном случае "-" (минус) обозначает "отрицание".

-_2 2
Тут все просто. Усложним векторами, все-таки J -- векторный язык. Вот, например вектор из трех чисел

1 2 3 1 2 3
При вводе, элементы вектора отделяются просто пробелами. Монадные операции действуют на одномерные векторы поэлементно (с многомерными все сложнее, но пока нам это не нужно).

-_2 1 2 3 2 _1 _2 _3
Смотрим разговорник... Вот есть глагол "%:", который в монадном случае соответствует операции извлечения квадратного корня.

%: 4 2 2 1.41421
А теперь так:

%: _1 0j1
О ! J, оказывается, поддерживает комплексные числа !!! Квадратный корень из минус единицы -- есть мнимая единица. Вооот значит как эти числа тут обозначаются ! Попробуем теперь вот так

0j1 * 0j_1 1
Тоесть мнимая единица, умноженная на сопряженную (т.е с мнимой частью обратного знака) мнимую единицу дает просто единицу, тоесть модуль мнимой единицы, тоесть совершенно верно... Если мы глянем в разговорник, то увидим, что операция "+" в монадном варианте соответствует комплексному сопряжению. Тоесть, действительные числа она не меняет,

+1 1
как и в других языках, оперирующих только с действительными числами, где операция "+" таки определена (как ничего не делающая) для "симметрии" с операцией "-". А вот у комплексных аргументов "+" меняет знак мнимой части

+ 0j1 0j_1
Воот... А ведь комплексные числа -- очень естественная форма для того, чтобы представить координаты точек на плоскости. Мы умеем вводить комплексные числа, умеем составлять списки... Ну-ка составим список наших точек, да назовем его

points=: 1j_6 5j_4 7j_2 4j_2 10j_1 _2j0 9j0 5j1 7j2 2j4 8j5
Заметьте, что здесь J ничего не выводит, но это не главное... Главное, в отличие от C (например), что в J мы не переменной (месту в памяти) присваиваем значение, а значению присваиваем имя. Тоесть points -- это не переменная, это имя для массива наших точек. Мы можем вызвать этот массив по имени

points 1j_6 5j_4 7j_2 4j_2 10j_1 _2 9 5j1 7j2 2j4 8j5
А можем и присвоить это имя какому-нибудь другому значению, но, до тех пор пока не присвоили, значение имени поменять нельзя (тоесть никто, ни по какому коварному указателю, не может влезть и поменять даже одну из точек в списке points, даже только ее мнимую или действительную часть). По терминологии J, операция -- это глагол (verb), а операнд -- существительное (noun). Наше имя "points" -- местоимение (pronoun), не называющее предмет, а указывающее на него, отсылая к существительному (предмету), упомянутому ранее.

Язык J силен своими примитивными операциями, полный список которых можно посмотреть в словаре и разговорнике. Обилие операций обьясняется тем, что язык векторный, а вариантов действий с массивами гораздо больше, чем со скалярами (даже матрицу на вектор можно перемножить уже двумя способами -- либо по строкам, либо по столбцам). Для того, чтобы "из головы" писать и "в лёт" понимать программы на J разговорник прийдется выучить наизусть. Чтобы "просто" писать программы -- достаточно пробежаться несколько раз по оглавлению разговорника и составить общее представление об имеющихся в нашем распоряжении операциях. Читать вначале прийдется со словарем, ну а потом нужное само осядет в памяти.

Смотрим разговорник... В J, оказывается, операция сортировки массива является встроенной, и обозначается как "/:" (сортировка по возрастанию), и "\:" (сортировка по убыванию). Причем, при сортировке комплексных чисел, сравниваются их действительные части. Тоесть, мы можем наши точки отсортировать

/: points 5 0 9 3 1 7 2 8 10 6 4
результатом монадного применения глагола "/:" (сортировать) является перестановка индексов внутрь сортируемого массива. Получить собственно отсортированный массив можно, применив диадную версию глагола сортировки.

points /: points _2 1j_6 2j4 4j_2 5j_4 5j1 7j_2 7j2 8j5 9 10j_1
Теперь самая левая из точек идет первой в массиве, а самая правая -- последней. Запись только получилась длинновата. Избежать написания слова points дважды нам помогут наречия (adverbs). Наречия изменяют действие глагола, стоящего слева от них, и образуют, таким образом, новый, производный, глагол. В частности, есть наречие отражения "~", оно превращает диадный глагол в монадный по правилу: "u~ x" -> "x u x", как-бы "окружая" глагол u существительными. Например "2*2" можно записать, при помощи этого наречия как "*~2", а нашу сортировку сделать командой

/:~ points _2 1j_6 2j4 4j_2 5j_4 5j1 7j_2 7j2 8j5 9 10j_1
Тоесть, возвращаясь к алгоритму Грехема, самая левая точка, относительно которой нам нужно будет сортировать все остальные по углам, определяется выражением

{./:~ points _2
где "{." в монадном применении всего-лишь берет первый элемент из списка, стоящего справа (т.е. нашего отсортированного списка). Эффективно-ли сортировать весь массив для того, чтобы выбрать только один, минимальный, элемент ? Сортировать не эффективно, но ничто не мешает интерпретатору распознать сочетание глаголов "{./:~" и заменить его просто вычислением минимума, без сортировки. Не знаю -- распознает ли эту комбинацию текущая версия интерпретатора J, но она распознает многие другие, перечисленные в приложении к словарю (J Dictionary).
Итак, мы нашли самую левую точку. Теперь нам нужно отсортировать остальные по углам вокруг этой. Что для этого нужно ? Правильно, нужно поместить начало координат в найденную нами точку, тоесть вычесть ее из остальных

points - {./:~ points 3j_6 7j_4 9j_2 6j_2 12j_1 0 11 7j1 9j2 4j4 10j5
И снова у нас points упоминается дважды. Это, конечно, не плохо, но было-бы красивее иметь один простой монадный глагол (наш собственный), ведь у проведенного нами вычисления всего один аргумент -- точки, значит и глагол, по идее, должен быть монадным. Чтобы записать такой глагол, нужно воспользоваться крючком (hook). Крючок возникает если два глагола идут в выражении подряд "(u v) y", где u и v -- глаголы, а y -- существительное. Заметьте, что в отсутствии скобок крючка нет, а есть просто последовательное применение глаголов u и v к y. Т.е. "u v y" -> "u(v y)" или, с использованием связки (conjunction) "@" ("поверх", см. разговорник), "u v y" -> "(u @ v) y" -> "u(v y)", как мы до сих пор и делали. Выражение с крючком вычисляется, однако, совсем по-другому, в монадном "(u v) y" и диадном "x (u v) y" случае крючок проще всего представить в виде следующих диаграмм:

монада диада u u / \ / \ y v x v | | y y
отсюда сразу видно, что если "u" -> "-", "v"->"{.@/:~" (заметьте здесь, связку "@", обьединяющую два глагола в один, соответствующий последовательному применению исходных), а "y"->"points" монадный крючок эквивалентен нашему последнему выражению.

(- {.@/:~) points 3j_6 7j_4 9j_2 6j_2 12j_1 0 11 7j1 9j2 4j4 10j5
Как видим, результат тот-же. То, что получилось в скобках -- наш собственный составной глагол, который, получая в виде аргумента массив точек, переносит центр системы координат в самую левую из них. Мы можем этот наш глагол назвать, образовав составной именованный глагол (proverb):

centerleft =: -{.@/:~
и использовать его

centerleft points 3j_6 7j_4 9j_2 6j_2 12j_1 0 11 7j1 9j2 4j4 10j5
в таком-же виде нам нужно будет оформить и окончательный глагол, вычисляющий выпуклую оболочку. Может показаться, что мы идем к этому черепашьими шагами... Да, действительно, но это только потому, что построение оболочки не есть нашей основной целью. Цель в том, чтобы заострить внимание на встречающихся нам по ходу особенностях программирования на языке J. И прошли мы уже немало. Мы умеем вводить и называть данные, в т.ч. в комплексном виде, умеем их сортировать, освоили крючки, и написали программу из 7-ми символов (!), центрирующую точки на плоскости вокруг самой левой из них.

Но, едем дальше. Теперь нам нужно эти точки отсортировать по углам, а углы нужно сначала вычислить. Для вычисления аргумента комплексного числа, а так-же других КРУГОВЫХ функций в J есть диадная операция, обозначаемая (как ни парадокасально ;-) "o.". Левый аргумент диады o. -- целое число, определяющее тип вычисляемой функции. Вычислению аргумента комплексного числа "y" соответствует диада "12 o. y".

Но перед тем как сортировать давайте все-таки немного передумаем... Проблема в том, что левую точку, которую мы поместили в начало координат нужно исключить из сортировки, а потом вставить в начало отсортированного списка (потому что она заведомо принадлежит выпуклой оболочке).

Введем временное имя для отсортированного по X массива

spoints=: /:~points spoints _2 1j_6 2j4 4j_2 5j_4 5j1 7j_2 7j2 8j5 9 10j_1
тогда отсортированный список без первой точки будет (см разговорник для "}.")

}. spoints 1j_6 2j4 4j_2 5j_4 5j1 7j_2 7j2 8j5 9 10j_1
первая точка

{. spoints _2
массив с помещенной в начало системы координат и выколотой первой точкой

(}. spoints) - ({. spoints) 3j_6 4j4 6j_2 7j_4 7j1 9j_2 9j2 10j5 11 12j_1
Для сокращения этой записи воспользуемся вилкой (fork). Вилка работает примерно так-же как крючок (hook), только немного сложнее, поскольку состоит она не из двух, а из трех, следующих друг за другом, глаголов. Диадный "x (u w v) y" и монадный "(u w v) y" случаи применения вилки иллюстрируются диаграммой

монада диада w w / \ / \ u v u v | | / \ / \ y y x y x y
тоесть, вилка

(}. - {.) spoints 3j_6 4j4 6j_2 7j_4 7j1 9j_2 9j2 10j5 11 12j_1
воспроизводит нужный нам результат. Теперь вычислим углы

(12"_ o. }. - {.) spoints _1.10715 0.785398 _0.321751 _0.519146 0.141897 _0.218669 0.218669 0.463648 0 _0.0831412
где мы воспользовались цепочкой глаголов и константной функцией (12"_). Как работает эта цепочка ? Нет, ничего сложнее вилки в J нет ! Если цепочка глаголов длиннее чем 3, она разбивается на тройки (с завершающей парой, если не хватит глаголов), и каждая из групп вычисляется по правилам вилки или крючка (если осталась пара). Тоесть, в последнем выражении можно поставить скобки '(12"_ o. (}. - {.)) spoints' и оно эквивалентно двум вилкам '((12"_ spoints) o. ((}. - {.) spoints))', причем '12"_' -- это не существительное, а глагол, образованный из существительного -- функция, возвращающая константу "12", независимо от своего аргумента (добавлением '"_' можно образовать константную функцию из любой константы). Понятно как работает цепочка ?

Добавим теперь вилку (т.е еще два глагола) с диадной сортировкой:

(}. /: 12"_ o. }. - {.) spoints 1j_6 5j_4 4j_2 7j_2 10j_1 9 5j1 7j2 8j5 2j4
Диадный вариант сортировки упорядочивает левый аргумент (получающийся здесь, за счет вилки отбрасыванием первой точки "}. spoints") в порядке, заданном правым (тоесть углами, вычисленными нами ранее). В результате получаем точки, отсортированные по углам. Все, кроме выброшенной нами первой. Теперь осталось добавить эту первую в начало еще одной вилкой, и назвать полученный составной глагол. Сшивка двух массивов обозначается диадной операцией "," потому

({. , }. /: 12"_ o. }. - {.) spoints _2 1j_6 5j_4 4j_2 7j_2 10j_1 9 5j1 7j2 8j5 2j4
пришьет нам в начало отсортированного массива первую точку из spoints, которая в сортировке участия не принимала. Итого, обьединяя с сортировкой, вынесенной временно в spoints, запишем наш глагол

s =: ({. , }. /: 12"_ o. }. - {.) @ /:~
Применяя его к неотсортировынному исходному массиву точек, получаем эти-же точки, отсортированные в виде "звезды", относительно самой левой из них, причем левая эта идет в списке первой.

s points _2 1j_6 5j_4 4j_2 7j_2 10j_1 9 5j1 7j2 8j5 2j4
Тут самое время глянуть на первую картинку, где изображены точки, чтобы оценить -- насколько близко мы подобрались к построению выпуклой оболочки. Нам осталось выбросить у звезды те углы, которые выгнуты наружу, тогда останутся только те, которые вогнуты вовнутрь и результирующий многоугольник будет по-определению выпуклым, что нам и нужно. Решать эту задачу мы будем итеративно, выбрасывая на каждой итерации все углы, до которых мы только можем дотянуться и определить, что они вогнутые.

Рассмотрим один угол, состоящий из трех точек, причем обход идет в порядке от первой к третьей, а рассматриваем мы угол при второй точке. Итак, картинка:

\ [*] 1 \ \ \ \ \ [*] \ 3 [*] 2 \ [*] \ 3' \
Здесь нарисованы два варианта расположения третьей точки. Вариант 3, при котором угол 123 выгнутый (то, что нам нужно) и вариант (3'), при котором угол 123' вогнутый (то, что нам не нужно, поскольку говорит, что точка 2 в этой ситуации точно НЕ принадлежит к выпуклой оболочке, и ее нужно выбросить). Как нам различить ситуации 3 и 3' ? На помощь прийдет знание того, что векторное произведение двух векторов на плоскости направлено строго перпендикулярно этой плоскости и пропорционально СИНУСУ угла между векторами. Угол в между векторами 12 и 13 положительный, а между векторами 12 и 13' отрицательный, синус, соответственно, имеет тот-же знак. Значит нам нужно сосчитать векторное произведение [12 x 13]. Как это сделать ? Для векторного произведения векторов A=(Ax,Ay,Az) и B=(Bx,By,Bz) есть известная формула в виде определителя:

| i j k | | i j k| |(x2-x1) (y2-y1)| | Ax Ay Az | = |(x2-x1) (y2 - y1) 0| = k |(x3-x1) (y3-y1)| = | Bx By Bz | |(x3-x1) (y3 - y1) 0| = k ((x2-x1)(y3-y1)-(x3-x1)(y2-y1))
где i, j, k -- векторные орты в направлении координатных осей x,y,z (соответственно), xi и yi -- координаты соответствующих точек (i=1,2,3). Значит, нам необходимо вычислить величину (x2-x1)(y3-y1)-(x3-x1)(y2-y1), знак которой, если положительный, скажет нам, что мы имеем дело с ситуацией 123, и, если отрицательный, что ситуация подобна 123'. Выражение это равно нулю, если точки 1, 2 и 3 лежат на одной прямой (в этом случае мы будем считать, что точка 2 все-же принадлежит выпуклой оболочке [*]). Как вычислить ?

Пусть даны три точки, заданные в комплексном виде p1 = x1 + I y1, p2 = x2 + I y2, p3 = x3+ I y3. Рассмотрим произведение
(p2-p1)*Conjugate[(p3-p1)], его мнимая часть в точности равна "-((x2-x1)(y3-y1)-(x3-x1)(y2-y1))". Проверьте, заметив появившийся знак минус, который проще оставить, инвертировав условие в дальнейшем.
Глагол, на языке J, вычисляющий этот тест, получив в качестве аргумента массив из трех комплексных точек, запишется как

l =: 11"_ o. [: (* +)/ }. - {.
Понятно ? Здесь мы сначала вычитаем первую точку из остальных, и отбрасываем ее. Потом вставляем, используя наречие "/", операцию "*+" (умножить "*" на комплексно сопряженное "+") между двумя оставшимися элементами массива. Глагол "[:" называется "шапка", он просто отбрасывает соответствующую ветку вилки, делая операцию на ее вершине монадной. Ну, и, наконец, выделяем у результата мнимую часть при помощи круговой функции o., с левым аргументом 11.

Теперь нам нужно применить этот тест к последовательным тройкам отсортированных точек. Для построения такого движущегося "окна" в J есть готовое наречие "\", оно производит диадный глагол, левым аргументом которого является количество точек, которое помещается в движущемся окне оператора, а правым массив, к которому оператор этот применяется.

3 l\ (s points) _30 _10 6 _3 _4 _3 6 _5 _17
Заметьте, что точек на две меньше, чем в исходном массиве. Это потому, что вокруг первой и последней точек нельзя построить тройки. Тест на то, что соответствующий угол многоугольника выгнут можно записать как

0 > 3 l\ s points 1 1 0 1 1 1 0 1 1
результат -- двоичный массив, с единичками напротив вершин с выгнутыми углами. Вспомним, однако, что первая и последняя вершины не вошли в наш тест. Вспомним так-же, что мы сортировали вокруг самой левой точки, а потому первая и последняя вершины точно принадлежат оболочке. Значит, мы можем просто добавить к полученному булевскому списку две единички -- одну в начало, другую в конец.

1, 0 > 3 l\ s points , 1 1 1 1 0 1 1 0 1 0 1 1
Теперь находим в словаре диаду "#", которая просто убирает из правого списка элементы, напротив которых стоит нолик в левом, булевском, списке.

(1, (0 > 3 l\ s points) , 1) # s points _2 1j_6 5j_4 7j_2 10j_1 9 7j2 8j5 2j4
Это-же можно записать в виде цепочки глаголов

rr =: (1"_ , (0"_ > 3: l\ ]) , 1"_) # ] rr s points _2 1j_6 5j_4 7j_2 10j_1 9 7j2 8j5 2j4
Но ! После удаления, у нас еще могут остаться тупые углы, и повторная итерация их удалит

rr rr s points _2 1j_6 5j_4 10j_1 8j5 2j4
а когда тупых углов больше не осталось, и удалять больше нечего -- результат и является той самой выпуклой оболочкой, которую мы искали. В данном случае это происходит на третьей итерации

rr rr rr s points _2 1j_6 5j_4 10j_1 8j5 2j4
для повторного применения глагола, некоторое количество раз, служит наречие "^:n" (где n -- количество раз).

rr^:3 s points _2 1j_6 5j_4 10j_1 8j5 2j4
Фактически, это соответствует возведению глагола в степень. Возведение глагола в бесконечную степень (бесконечность обозначается одиночным символом подчеркивания "_" в J) означает применение его до тех пор, пока результат перестает меняться (в нашем случае, пока не осталось вогнутых углов), что, собственно, нам и нужно. Таким образом, мы приходим к определению окончательного глагола hull, решающего задачу построения выпуклой оболочки:

hull =: [: rr^:_ s
На русском языке это определение читается как: "применять до упора итерацию по удалению выгнутых углов к звездообразно отсортированному списку точек". Применяя его к нашему исходному списку получим

hull points _2 1j_6 5j_4 10j_1 8j5 2j4
Гляньте теперь на исходную картинку ! Это оно ?

Итак, полностью, текст нашей программы для нахождения выпуклой оболочки запишется так:

s =: ({. , }. /: 12"_ o. }. - {.) @ /:~ l =: 11"_ o. [: (* +)/ }. - {. rr =: (1"_ , (0"_ > 3: l\ ]) , 1"_) # ] hull =: [: rr^:_ s
И эту программу еще можно сократить, я уверен ! ;-)))
Эквивалентная программа на Java:
http://www.cs.rpi.edu/~hulber/cgeom/grahamScan.java
http://www.cs.rpi.edu/~hulber/cgeom/newPoint.java
при том, что она использует, для краткости, сортировку "пузырьком", а потому время ее работы масштабируется как N2. Замена сортировки, скажем, на "quicksort" программу эту существенно-бы удлиннила.
Выводы делайте сами... Я только скажу, что мне, написание программы на J больше напоминает вывод формулы, чем тыкание компьютера носом в каждую мельчайшую деталь вычислений...

ПРИМЕЧАНИЕ: рассмотрение здесь носит иллюстративный характер и полученная программа может быть оптимизирована. Время ее работы имеет асимптотику N log N, как и положено алгоритму Грехема, однако, константный множитель в этой асимптотике может быть улучшен. Например, можно избежать самой правой сортировки в "s", заменив ее на перестановку одной самой левой точки (с минимальной действительной частью) на первое место в массиве. Такая перестановка может быть сделана за время ~N (в отличие от сортировки, требующей N log N). Предлагаю читателям проделать это усовершенствование в качестве упражнения.

[*] если считать такую точку НЕ принадлежащей оболочке -- это может привести к некоторой экономии ресурсов в дальнейшем, поскольку присутствие такой точки на контуре явно избыточно. Желающим использовать эту реализацию алгоритма Грехема для дальнейших рассчетов может показаться хорошей идеей такие точки выбрасывать. Для образовательных целей, чтобы не вызывать вопросов у неискушенного человека, задавшего целочисленные координаты точек (потенциально приводящие к такого рода ситуациям), точки, лежащие на одной прямой, лучше оставить в контуре, потому что интуитивно (методом затягивания нитки) оболочке они принадлежат.
ПРИЛОЖЕНИЕ:

Перевод некоторых терминов, использующихся в языке J.
verbглагол. Оператор, операция, обозначение действия. nounсуществительное. Предмет для действия глаголов, данное, число, вектор, матрица. pronounместоимение. Ссылка на существительное, упомянутое ранее, имя для данных (НЕ переменная, в смысле языка C). proverbсложный глагол. Именованый глагол, составленный пользователем из простых. adverbнаречие. Слово, изменяющее некоторым определенным и универсальным способом действие соседнего с ним глагола. Вместе с глаголом представляет из себя некоторый новый, измененный, глагол). verb trainцепочка глаголов. Цепочка глаголов, идущих в тексте подряд (как правило, используется для обозначения цепочек из четырех и более глаголов). forkвилка. Цепочка из трех глаголов. hookкрючок. Цепочка из двух глаголов. J Dictionaryсловарь языка J, словарь. Полное и определяющее описание языка J. J Vocabularyразговорник. Краткое перечисление встроенных в J глаголов с описанием осуществляемых ими операций. monadic caseмонадный случай, монада. Частный случай применения глагола к одному аргументу, стоящему справа. dyadic caseдиадный случай, диада. Частный случай применения глагола к двум аргументам, стоящим по обе его стороны. Действие, обозначаемое одним и тем-же глаголом в монадном и диадном случае, как правило, различно, но часто связано концептуально. update (24.12.2006): По ссылкам здесь Вы найдете авторизованный русский перевод словаря языка J.