?

Log in

No account? Create an account
entries friends calendar profile homepage Previous Previous Next Next
Язык программирования J, введение. - Записки К.Л.М.
dr_klm
dr_klm
Язык программирования J, введение.

Предлагаю вашему вниманию краткое введение в язык программирования 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.

Метки:

118 комментариев or Оставить комментарий
Comments
Страница 1 из 2
[1] [2]
From: maths_fan Date: Июнь, 17, 2004 05:46 (UTC) (Ссылка)
Супер!
dr_klm From: dr_klm Date: Июнь, 17, 2004 07:32 (UTC) (Ссылка)
Спасибо !

К.Л.М.
(Удалённый комментарий)
dr_klm From: dr_klm Date: Июнь, 17, 2004 07:32 (UTC) (Ссылка)
не то слово, что красота !

Для отладки есть трассировка (загружается командой load 'system/packages/misc/trace.ijs') и отладчик (доступен из меню Tools/Debug...). Трассировка -- штука удобная (показывает результаты промежуточных составных глаголов). Отладчик не пробовал, но кнопки "run", "step", "step into", "step over", и т.д. в нем есть.

Читать. Читать... Ну дык это-ж дело привычки... В любом случае, чтение будет медленнее (если мерять в прочтенных строчках в минуту), по сравнению с эквивалентом на других языках, но это потому, что концентрация информации в программе на J гораздо выше. Тут не получится читать путем "пробежал глазами" (потому что пробегать особо нечего), а, скорее, путем "разглядывания".

Помочь разглядыванию призваны различные варианты визуального представления глаголов (хотя, я уже насобачился читать линейное представление сразу). Возьмем, например, глагол "s" из программы выше. Если просто ввести:

   s
+---------------------------------------------+-+
|+--------------------------------------+-+--+|~|
||+--+-+-------------------------------+|@|/:|| |
|||{.|,|+--+--+-----------------------+|| |  || |
|||  | ||}.|/:|+--------+--+---------+||| |  || |
|||  | ||  |  ||+--+-+-+|o.|+--+-+--+|||| |  || |
|||  | ||  |  |||12|"|_||  ||}.|-|{.||||| |  || |
|||  | ||  |  ||+--+-+-+|  |+--+-+--+|||| |  || |
|||  | ||  |  |+--------+--+---------+||| |  || |
|||  | |+--+--+-----------------------+|| |  || |
||+--+-+-------------------------------+| |  || |
|+--------------------------------------+-+--+| |
+---------------------------------------------+-+


получаем коробчатое представление, являющееся представлением по умолчанию. Изменить представление для глаголов можно внешним (foreign) глаголом (9!:3), получающим список представлений, которые нужно отображать. Например:
   9!:3 (5 6 4 2)

   s
({. , }. /: 12"_ o. }. - {.)@/:~                  |<--- линейное
(({. , (}. /: ((12"_) o. (}. - {.))))@/:)~        |<--- с полными скобками
                 +- {.                
                 +- ,                 
                 |    +- }.           
            +----+    +- /:           
            |    |    |          +- 12
            |    +----+    +- " -+- _ 
            |         |    +- o.      
-- ~ --- @ -+         +----+     +- }.            |<--- дерево
            |              +-----+- --
            |                    +- {.
            +- /:                     
+---------------------------------------------+-+
|+--------------------------------------+-+--+|~|
||+--+-+-------------------------------+|@|/:|| |
|||{.|,|+--+--+-----------------------+|| |  || |
|||  | ||}.|/:|+--------+--+---------+||| |  || |
|||  | ||  |  ||+--+-+-+|o.|+--+-+--+|||| |  || |
|||  | ||  |  |||12|"|_||  ||}.|-|{.||||| |  || |
|||  | ||  |  ||+--+-+-+|  |+--+-+--+|||| |  || |  |<--- коробчатое
|||  | ||  |  |+--------+--+---------+||| |  || |
|||  | |+--+--+-----------------------+|| |  || |
||+--+-+-------------------------------+| |  || |
|+--------------------------------------+-+--+| |
+---------------------------------------------+-+
   9!:3 (2)

Последняя команда возвращает обратно к выводу коробчатого представления при печати следующих глаголов. В коробчатом представлении хорошо видны крючки и вилки... его по-началу удобнее разглядывать, чем линейное... Но разглядывать приходится по-любому...

К.Л.М.
mishanja From: mishanja Date: Июнь, 18, 2004 01:45 (UTC) (Ссылка)
Класс, серьезная работа. Я правда дошел до середины пока только, настолько непривычный язык все-таки.

Можешь обьяснить подробнее вот это

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

points /: points
_2 1j_6 2j4 4j_2 5j_4 5j1 7j_2 7j2 8j5 9 10j_1
...

Я как человек впервые столкнувшийся с таким языком этого совсем не понимаю. Что такое диадная версия? почему вообще все так устроено с глаголами - это стандартные какие-то знания, которые должны знать все программисты?
dr_klm From: dr_klm Date: Июнь, 18, 2004 07:59 (UTC) (Ссылка)
нет-нет, как раз ВСЕ программисты (даже если под ВСЕ понимать "большинство") об этом не знают. Но я вроде в тексте обьяснял чуть раньше, наверное недостаточно акцентировал. Спасибо!

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

Существительное -- это данные. Тоесть это число, символ, массив чисел, матрица чисел, строка чисел, и т.д. Тоесть просто данные.

Глагол обозначает некоторое действие над данными. В классическом программировании глаголу языка J соответствуют как операторы ("+", "-", "%"), так и функции. В предложениях (выражениях, по-программистски) языка J каждый глагол (например глагол "-") может быть использован в двух формах: монадной, когда существительное стоит только справа от глагола, а слева стоит другая часть речи (в монадном случае "-" означает "отрицание", как в выражении "- 2"); и в диадной, когда существительные стоят по обе стороны глагола (в диадном случае "-" означает "вычитание", как в выражении "4 - 2"). Операции, выполняемые одним и тем-же глаголом в диадном и монадном случае, как правило, связаны концептуально, но различны...

Причастие -- это часть речи, изменяющая действие глагола. Ее результатом является некоторый новый измененный глагол. Причастие в J, фактически, эквивалентно понятию оператора в математики. Т.е. это нечто, производящее из функции (глагол по-математически есть функция) другую функцию. Например причастие "~", которое означает "окружить" производит из диадного глагола монадный, подавая единственный аргумент монады в качестве обоих аргументов диады. Таким образом "*~2" эквивалентно "2*2", "+~2" эквивалентно "2+2", а "/:~ points" эквивалентно "points /: points".

В разговорнике при описании каждого глагола указано на его действие как в диадном, так и в монадном случае. Как, например, в описании глагола "/:" (на английском) монадное действие описано слева (Grade Up, построить упорядочивающую перестановку), а диадное справа (Sort Up, отсортировать элементы массива слева, в порядке, заданном элементами массива справа)

К.Л.М.


_alena_ From: _alena_ Date: Июнь, 18, 2004 07:30 (UTC) (Ссылка)
Ну прочитал , ну вопервых на Java тоже можно значительно сократить - просто автор программы не задавался целью этого сделать - во вторых
отсутствие объектов = это як , в третих очень малая толика программ состоит из подобного рода сложных алгоритмов с обработкой массивов - большинство просто набор тупой логики if () else бла ла ла и тут уже вряд ли ты получиш ксолько нибудь значимый выигрыш в размере. В третьих скорость работы ?.
dr_klm From: dr_klm Date: Июнь, 18, 2004 09:09 (UTC) (Ссылка)
До одной строчки нельзя... Здесь, для того, чтобы расширить эту программу до обьема хоть четверти явовской нужно конкретно задаться целью... ;-)))

Обьекты в J есть. Логика "if then else" в огромном количестве случаев легко записывается на языке массивов. Возьмем, например, задачу выбросить из массива (ну а куда без массивов... вся память компьютера -- это массив) отрицательные числа, и оставить положительные на J эта задача решается составным глаголом "#~0&<", работающим так
   a =: 1 2 _3 3 _4 4 _5 5 _6 6 7 8 9 _20 10
   (#~0&<) a
1 2 3 4 5 6 7 8 9 10
а на C она потребовала-бы цикл (в нем if), а потом еще один if. Тоесть, "один к одному" перевести с C на J нельзя, приходится переосмысливать... но результат впечатляет... Гляньте, например, на kdb. K -- это почти что J, а в базе данных if-ов (если писать классически) должно быть до черта (ведь правда ?). И ничего, обошлись, и выигрыш в размере получили значительный... в 200k этот лидер рынка укладывается... сравните с Oracle ? MS SQL ?

Да, и лидером рынка KDB является как раз по скорости ! ;-)

Со скоростью фишка в том, что программирование на J представляет из себя компоновку больших блоков, и основное время процессов проводит ВНУТРИ глаголов, а уж там, внутри интерпретатора, все оптимизировано до невозможности, можете не сомневаться.

Кроме того, во многих случаях более важной оказывается алгоритм, а не скорость выполняющего его процессора. Например, время работы той программы на Java, на которую я сослался растет как N^2 с ростом количества точек, а моей N log N, и потому моя программа, интерпретируемая, ту программу по скорости забьет. Почему аспирант Хублер (с неплохими бумажными credentials, преподававший Java, между прочим) использовал пузырьковую сортировку (убивающую весь смысл алгоритма Грехема) -- я не знаю. Могу только предположить, что он как раз и хотел (возвращаясь в начало) "сократить" программу. При программировании на C, Java, Python подобные компромиссы типичны, на J их приходится делать гораздо меньше... Просто программы короче получаются... стимулируют к "подумать" над каждым символом... да и время для этого экономится, время потраченное ранее на набор текста... к тому-же, как я уже говорил, примитивы на J сразу делают большие блоки работы и внутри их можно до предела оптимизировать, раз и навсегда.

Ну и, наконец, самое главное, концептуальное... Я конечно, буду тут аргументировать... но выбирает, конечно, каждый для себя сам. Ни в коем случае не подумайте, что я хочу язык J всем навязать и заставить все программы на нем переписывать (хотя на Java, кстати, такое переписывание уже давно идет полным ходом). Я просто говорю, что есть такой язык, и он позволяет делать удивительные вещи, просто. Может быть, и не является языком на все случаи жизни, но сильные стороны у него однозначно имеются...

Имеются и перспективы. Например:

1) J удобен на КПК (а это очень перспективный девайс), в J я на КПК могу программировать без компромиссов. Моя, бескомпромиссная (относительно времени работы для большого количества точек) программа по вычисленю комплексной оболочки помещается на экран наладонника, а программа Хублера (компромиссная, между прочим) на моем 19-ти дюймовом мониторе на экран нормальным шрифтом не помещается, да еще и из двух файлов состоит.

2) J, потенциально (пока на эту тему идут только исследования) отлично подходит для параллелных вычислений. Ведь с точки зрения человека, пишущего программу на J не важно каким именно образом реализованы глаголы, важно -- что они делают. Это дает немалую свободу в реализации. Глаголы можно перевести в C и выполнить на Тьюринговской машине, а можно совершенно прозрачно распараллелить и выполнить на кластере ! Сечете фишку ? Распараллелить программу на С или Java -- непросто...

К.Л.М.
APL - (Anonymous) - Развернуть
_alena_ From: _alena_ Date: Июнь, 18, 2004 07:41 (UTC) (Ссылка)
предыдущий комментарий Олега =)
dr_klm From: dr_klm Date: Июнь, 18, 2004 08:26 (UTC) (Ссылка)
Ну слава богу... то-ж я подумал -- ну и девушки боевые пошли... Держат территорию... ;-)) Для Олега это нормально, попробуем найти взаимопонимание.

К.Л.М.
dr_tim From: dr_tim Date: Июль, 2, 2004 06:57 (UTC) (Ссылка)
Наконец-то собрался дочитать и написать на эту тему.
Идейка конечно интересная, не тянуть кишку и съедать по одной конфетке, а грысть их поперёк!

но вопросики- на чём писан ентот монстр? Тогда будет понятно и откуда ростут его ноги. И как он зачищает за собой память! Если как Ява- на СИ или недай бог си-плю-плю, то понятно и чем болеет. Если на Фортране. то я-пас, лезть разбираться с ним-чур меня! времени и так ...

Со всеми понятиями и векторами понятно, вопрос такой-а как он работает с более чем с 1-ой мерой векторами? т.е. матрицами и 3-векторами? и особенно с функционалами?
и ещё как он всё таки лезет в память(не простозатак же скорость увеличиться).

Ваще-то изучать новое-дело прикольное, но решать надо задачи по-мере поступления. Вот как выучу латынь и возьмусь за это!
dr_klm From: dr_klm Date: Июль, 5, 2004 09:53 (UTC) (Ссылка)
Да, именно грызть поперек... Метко ! ;-)

Ну и ответики... Язык писан на бумаге, сам язык... Тот интерпретатор, который можно скачать с jsoftware писан на C и местами на ассемблере (там, где можно использовать векторные инструкции x86)...

Но, раз мы говорим о языке, большая-ли разница на чем писан и как памятью управляет конкретный интерпретатор ? Язык программирования ведь это-ж не более чем способ сказать компьютеру -- что мы от него хотим... Причем выполнить то, что мы сказали компьютер может, как правило, не единственным способом... Естественно, что любой язык программирования не позволяет управлять отдельно взятым компьютерным железом настолько-же детально, как это позволяет язык ассемблера для этого отдельно взятого железа... Но народ ведь все равно пользуется C, C++... Хотя, любую программу можно переписать на ассемблере и она будет при этом быстрее (или в редчайших исключительных и очень локальных случаях такая-же по скорости), как и эквивалент, скомпилированный с C даже самым лучшим компилятором...

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

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

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

К.Л.М.
(Удалённый комментарий)
muchandr From: muchandr Date: Октябрь, 23, 2004 13:17 (UTC) (Ссылка)

Re: kdb

Оффициальных результатов бенчмарков нет. Это связано с тем, как администрируются бенчмарки TPC. У бенчмарков TPC нет стандарной имплементации. Вместо этого, членам TPC (а само членство тоже стоит нетривиальных бабок), выдается rulebook, следуя которому они имплементируют бенчмарк сами и сопровождают его целым талмудом, описывающим их имплементацию. Если побивается рекорд, новый рекордсмен как правило обвиняется в жухлеже и долго и нудно отбрехивается, пока результаты его бенчмарка оффициально не признаются. Поэтому у больших контор типа Oracle или IBM за имплементацию TPC и ее сопровождающую документацию отвечает целый департамент. Маленькая фирма типа kx просто не может себе позволить себе членства в этом эксклюзивном клубе.

Впрочем, неоффициальную и неблагословленную TPC имплементацию TPC-D можно сгрузить здесь:

http://kx.com/a/kdb/examples/

и погонять ее самому. kx кстати как пить дать обвинили бы в жульничестве, поскольку практически вся реляционная аналитика, которая в других базах идет на массивно-денормализированных данных (cube schema, snowflake schema и тп.), в kdb можно (и нужно) гонять на точно такой же нормализированной схеме, как и для трансакциональной базы.

Вас вообще-то больше интересует аналитика или transaction processing? (Т.е вы из базы будете скорее читать или в нее писать)? По поводу трансакциональных бенчмарков (например TPC-C) kdb тоже может бегать круги вокруг других баз, но это все тоже сплошное жульничество :)
potan From: potan Date: Декабрь, 21, 2004 11:11 (UTC) (Ссылка)
Спасибо за полезную статью.
Я могу поместить ссылку в ru_declarative (в том числе в userinfo)?

IMHO, в подобных языках не хватает статической типизации. Было бы заманчиво проверять все размерности массивов на этапе компиляции, да и эффективности это не помешало.
dr_klm From: dr_klm Date: Декабрь, 21, 2004 18:38 (UTC) (Ссылка)

Конечно ! Мне было-бы очень приятно !

Да, компилятор с такого языка -- не решенная задача. С другой стороны, APL-подобные языки в принципе имеют низкие накладные расходы на интерпретацию. Фишка в том, что операции в этих языках емкие (могут оперировать с гигантскими массивами), но: 1) самих операций мало (программа короткая); 2) отсутствуют (либо не поощряются) циклы (а значит -- нет реинтерпретации глаголов). Из этого следует, что накладные расходы на интерпретацию пропорциональны длине программы (сюда-же относится и проверка длины массивов, перед выполнением каждого глагола). Полезные-же операции пропорциональны обьему скормленных глаголам данных.

Это значит, что если на вход программ на J подавать немного данных -- относительные накладные расходы на интерпретацию будут большими. Но, поскольку данных мало, программа все равно будет выполняться, фактически, мгновенно.

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

Тут могут быть, конечно, ньюансы... Можно написать и неэффективную программу на J, но в общем и целом где-то так...

К.Л.М.
From: 9000 Date: Декабрь, 28, 2004 12:17 (UTC) (Ссылка)
Очень здорово и красиво.
Важный непонятный момент: что происходит, когда возникает ошибка выполнения? Деление на ноль посреди массива, timeout при работе с сетью, нехватка памяти, etc. Как такие ситуации обрабатываются, чтобы программа была устойчива?
muchandr From: muchandr Date: Январь, 1, 2005 20:25 (UTC) (Ссылка)
В К кидается exception. Если у тебя нету хендлера для этой ошибки (а их в К аж 6? видов), тебя выкидывает во встроенный дебаггер, где можно эвалюировать пошагово.
From: (Anonymous) Date: Февраль, 18, 2005 11:14 (UTC) (Ссылка)

Не вижу ничего оригинального.

Знаком ли автор с другими (и более развитыми) функциональными языками - Ocaml, Erlang, Haskell?
dr_klm From: dr_klm Date: Февраль, 18, 2005 11:31 (UTC) (Ссылка)

Прям таки и ничего ? ;-)

Попробуйте прочитать еще раз, может все-таки кое что оригинального там есть. :-)

К.Л.М.

P.S. Знаком я и с другими функциональными языками. А так же с тем, что очень глупо сравнивать яблоки и апельсины, определяя -- что из них более развито, а что менее.
From: (Anonymous) Date: Февраль, 27, 2005 13:37 (UTC) (Ссылка)

Было интересно почитать :)

Только пример кода на java вызывал рвотный рефлекс.
Понятно, что люди занимающиеся ФЯ могут не понимать ничего в "обычном" программировании и в частности в java, но всё-таки... :)


NotGonnaGetUs.

kastaneda From: kastaneda Date: Апрель, 21, 2005 09:50 (UTC) (Ссылка)
Компилятор? Ха!.. Вот прикрутить бы к этому хотя бы скромный JIT - и был бы рай...

JIT уровня исполнения программы вообще крайне любопытен. Хотел бы я посмотреть на вычислительные алгоритмы, где код (*) прекомпилируется непосредственно перед выполнением с учётом особенностей данных - например, размерностей массивов.

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

Как это влияет на современные скалярные процессоры с большим конвеером, можно даже не обсуждать. ;-)

(*) - есс-но, речь идёт не о всём коде, а о "bottlenesk".
mirritil From: mirritil Date: Июнь, 13, 2005 11:31 (UTC) (Ссылка)

Спасибо!

отличная статья. классный язык.

столько нового и так толково описано.

спасибо.
From: (Anonymous) Date: Апрель, 27, 2006 03:37 (UTC) (Ссылка)

А де взять?

1) по языку: очевидно, что это узкоспециализированный язык (под свою предметную область), а не язык "общего назначения"
2) по статье: ощущается вначале сильная "предвзятость" к другим языкам, видно, что писалась эмоционально :)
==> САМОЕ ГЛАВНОЕ:
3) Я что-то не понял: GPL реализация есть? Открытые исходники есть? Я не нашел ни для K ни для J открытой реализации. Она в природе вообще есть? А то получается как Rebol - все сверх маленькое (сложные программы по две-три строчки), абсолютно платформонезависимое, поддерживает кучу Internet протоколов, и даже создатель смеет вякать о каких-то открытых исходниках, подразумевая какие-то там скрипты, а на самом деле ВСЕ закрыто и лишь базовый Rebol/Core доступен бесплатно, но с закрытыми исходниками (ессно). Если автору не сложно, пришлите ссылку где это можно взять на yosifov(AT)ngs.ru. ЗАРАНЕЕ БЛАГОДАРЕН!
dr_klm From: dr_klm Date: Апрель, 27, 2006 15:10 (UTC) (Ссылка)
1) нет, это не узкоспециализированный язык. Мамой клянусь ! ;-) На нем можно написать все то-же, что и на любом другом, включая GUI, сетевые серверы и т.д. и т.п. "Мамой клянусь" потому что для понимания того, что J является языком "общего назначения" нужно выйти за рамки этого введения и посмотреть -- что на нем вообще пишут. Окажется, что пишут на J самые разные вещи из самых разных предметных областей. Кроме того, есть субъективный момент, связанный с тем, что J настолько хорошо спроектирован, что кажется "специализированным" для многих областей.

Вот K -- да, K больше заточен под базы данных.

2) Ну, эмоции я, конечно, выразил, отрицать не буду. Но это просто такой стиль, западный... С другой стороны, эти эмоции не поддельны, язык J действительно вызывает восхищение.

3) J и K -- проэкты с закрытыми исходниками. Интерпретатор J доступен бесплатно (stable, beta) (в т.ч. и для коммерческого использования). Ранние версии J (вплоть до версии 7.0, предшествующей версии 2.0) доступны в исходниках: версия 7.0 (без обьяснений), версия 6.2 (с сопутствующей документацией). Но по-хорошему все равно нужно компилятор писать...

К.Л.М.
jtootf From: jtootf Date: Декабрь, 23, 2006 19:10 (UTC) (Ссылка)

спасибо ;)

интересный язык, до этой статьи не подозревал о его существовании
из ФЯ работал только с haskell и erlang (ну и SWI-prolog когда-то)
теперь вот буду разбирать J
понравилось ;)
особенно если его можно втянуть в существующий код (как embedded интерпретатор) - тогда восторгам вообще не будет предела ;)
ещё раз спасибо :)
dr_klm From: dr_klm Date: Декабрь, 24, 2006 10:22 (UTC) (Ссылка)
Да, язык очень выразительный.

Интерпретатор (он сделан в виде динамической библиотеки) можно вызывать из других программ, а из под него можно вызывать динамические библиотеки, написанные на других языках; причем так, чтобы функции там, в свою очередь, могли вызывать функции на J (например)...

К.Л.М.
118 комментариев or Оставить комментарий
Страница 1 из 2
[1] [2]