Dr klm – Записки К.Л.М.

Записки К.Л.М.

Эта мысль оказалась не новой. Еще в 1979-м Burge, Moses и Pratt задавались вопросом «APL and LISP—should they be combined, and if so how?». Эта статья мне, к сожалению, недоступна, но и lisp и APL с тех пор здорово изменились. Каким бы ни был ответ — возможно, сейчас стоит задать тот-же вопрос заново. Мой ответ: «Да, должны. И понятно — как».

«Священный грааль» в виде компиляции APL в машинный код или C тоже был «взят» неоднократно. Был частичный компилятор фирмы STSC, написал свою книгу «An APL Compiler» Timothy Budd и свой компилятор APEX Robert Bernecky. Но то APL. Для J, насколько я знаю, на сегодня компилятора нет.

С другой стороны, компилятор есть в большинстве популярных реализаций Common Lisp. Причем такой, что компилирует программу как целыми модулями, так и по одной функции «на лету». Замыкания, созданные во время работы программы тоже транслируются в машинный код. Идея компиляции в замыкания тоже не нова, но для APL и J так, насколько я понял, никто не делал. Так почему бы не сделать ?

Написание компилятора в замыкания по трудозатратам сопоставимо с написанием интерпретатора. Да и структура его подобна. Если использовать опыт, накопленный при написании интерпретатора J. Добавив, развитую Бернецким, морфологию массивов — можно, мне кажется, получить весьма высокопроизводительную вещь. Другое дело, что примитивы в J очень нетривиальны, реализация полной спецификации J с существующими на сегодня оптимизациями займет, наверное, целую человеко-жизнь. Прелесть, однако, в том, что компиляцию в замыкания несложно реализовывать поэтапно, добавляя по одному глаголу, наречию или союзу. Такая работа, по идее, должна хорошо распараллеливаться.

И так, в чем я здесь не прав ? Стоит ли этим заняться ?

( Чтобы не быть голословным…Свернуть )

Метки: j, progr

dr-klm.livejournal.com

Язык программирования J, введение. — Записки К.Л.М.

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

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

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

&copy 2004 Константин Л. Метлов <[email protected]>
All rights reserved.

Эволюционные ветви.

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

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

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

Обобщая, можно сказать, что упомянутая ветвь языков развивалась по принципу: «Быть

Параллельно с описанной ветвью развивалась и другая. Ее отсчет, наверное, следует начать с книги «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, но она распознает многие другие, п

dr-klm.livejournal.com

крыски — Записки К.Л.М.

dr-klm.livejournal.com

Виртуальный Фонд Свободных Программ — Записки К.Л.М.

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

В принципе, идея несложная. Можно сделать сайт (эдакую электронную биржу тех. заданий), на котором пользователи (кто угодно) смогут запросить изменения (как, например, добавить менюшку, сделать поддержку русских букв где-то, написать драйвер некоторого нового устройства и т.д.) в любых из свободных программ (распространяемых под GNU GPL и некоторыми другими лицензиями). Техническое задание предполагает указание на то — в какой программе должны быть сделаны изменения и какие, четкий критерий, позволяющий установить его выполнение (в частности — требовать ли от исполнителя включение соответствующих изменений в официальную версию программы). Продуманность и качество тех. заданий обеспечивается тем, что заказчик за его размещение на сайте платит (точнее, вносит деньги, в фонд). Впоследствии, другие пользователи системы смогут добавить взносы в фонд одного или нескольких заданий. Когда задание наберет за собой некоторую сумму, оно могло-бы заинтересовать программиста, который бы за него «взялся» и начал бы его выполнять. По сигналу со стороны программиста о том, что задание выполнено, система отправила бы запросы на проверку данного факта некоторым случайно выбранным из наиболее активных заказчиков и программистов фонда анонимным «проверяющим». При достижении консенсуса между ними, задание считается выполненным, закрытым, а средства фонда выполненного задания переходят программисту. Заказчики имеют право забирать внесенные ими в фонд того или иного задания деньги (минус проценты за транзакции) при условии, что данное задание не находится в процессе выполнения (т.е. за него пока никто не взялся; или кто-то взялся, но не выполнил).

Что получают заказчики ? Заказчики получают возможность направлять развитие свободных программ в нужном им направлении (облегчая себе работу в собственных предметных областях) за небольшие деньги (поскольку основная функция системы — разделить расходы на разработку).

Программисты получают возможность выбирать себе задания по силам (и знать, при этом, что деньги за его выполнение реально «уже есть»).

Качество обеспечивается независимыми анонимными оценщиками.

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

Где-то так…

Что Вы думаете по поводу такого проэкта ? Не знаете ли подобного, уже функционирующего ? Думаете — полетит ? Нет ? В общем, пока я буду путешествовать — пишите, отвечу по приезду.

Если будет ясно, что делать стоит (точнее, что «не стоит не делать» 😉 — я мог-бы наваять работающий прототип за пару-тройку недель.

dr-klm.livejournal.com

додекаэдр — Записки К.Л.М.

В чем-же причина, в чем корень ошибки (хоть и небесплодной 😉 древних геометров и философов начиная с неизвестного первооткрывателя додекаэдра, Теэтета, Эвклида и Платона (и многих математиков поныне) ? Суть, здесь, кроется в стремлении выдать желаемое за действительное. Математика, как кривое зеркало, отражает божественную красоту природы, коверкая и деформируя ее по человеческим канонам. Именно поэтому, с точки зрения человека, математические обьекты божественно правильны и красивы. Математика-же в самой сути своей является самообманом, причем, самообманом, не воспринимающим никаких доводов, кроме (опять-же) математических.

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

Дело в том, что додекаэдр обладает осью симметрии 5-го порядка. Такая симметрия (как говорит современная математика) не совместима с трансляционной инвариантностью, а значит никакой идеальный кристалл (типа пирита) обладать такой симметрией не может, а потому принципиально (в математическом смысле) не может расти в виде додекаэдра (в отличие от других правильных многогранников). На самом деле, грани пирита всегда являются неправильными пятиугольниками, а кристалл этот имеет тетраэдрическую симметрию. И вот когда-то древний грек посмотрел на божественно правильный кристалл пирита, немного его «исправил», сделав пятиугольники правильными, и получил новый математический обьект — «додекаэдр». С этого, фактически, начиналась математика…

Но самый крутой парень во всей этой истории — Теэтет. Он сформулировал такие критерии «правильности», поставил такие жесткие рамки, что «правильных» многогранников оказалось всего (!) пять. Вот это был эстет ! ;-))

^*Платон «Теэтет» (комментарий А.Ф. Лосева)

Спасибо aleksei за вопрос о пирите.

update(09/07/2007): ну и немного о квази-кристаллах, раз уж пошли такие серьезные разговоры. 😉 Да, есть в природе одна очень хрупкая «штука», которая «сама» (в очень точно контролируемых условиях) растет в виде додекаэдра.Создатели (видимо в насмешку) назвали эту вещь «квази-кристалл», хотя кристаллом там и не пахнет. Больше всего эта вещь похожа на металлическое стекло, только атомы расположены не в случайных позициях, а в более-менее определенных (но не повторяющихся периодически), расположенных как узлы в покрытии Пенроуза. Сразу оговорюсь, что явно отказывая этой вещи в статусе кристалла, ничуть не хочу принизить ее потенциальную полезность (аморфные металлические стекла, где атомы расположены вообще случайно, вон как полезны оказались, целая индустрия родилась). Просто не кристалл это и все. (дельный обзор квази-кристаллов здесь)

dr-klm.livejournal.com

как написать компилятор языка J

Эта мысль оказалась не новой. Еще в 1979-м Burge, Moses и Pratt задавались вопросом «APL and LISP—should they be combined, and if so how?». Эта статья мне, к сожалению, недоступна, но и lisp и APL с тех пор здорово изменились. Каким бы ни был ответ — возможно, сейчас стоит задать тот-же вопрос заново. Мой ответ: «Да, должны. И понятно — как».

«Священный грааль» в виде компиляции APL в машинный код или C тоже был «взят» неоднократно. Был частичный компилятор фирмы STSC, написал свою книгу «An APL Compiler» Timothy Budd и свой компилятор APEX Robert Bernecky. Но то APL. Для J, насколько я знаю, на сегодня компилятора нет.

С другой стороны, компилятор есть в большинстве популярных реализаций Common Lisp. Причем такой, что компилирует программу как целыми модулями, так и по одной функции «на лету». Замыкания, созданные во время работы программы тоже транслируются в машинный код. Идея компиляции в замыкания тоже не нова, но для APL и J так, насколько я понял, никто не делал. Так почему бы не сделать ?

Написание компилятора в замыкания по трудозатратам сопоставимо с написанием интерпретатора. Да и структура его подобна. Если использовать опыт, накопленный при написании интерпретатора J. Добавив, развитую Бернецким, морфологию массивов — можно, мне кажется, получить весьма высокопроизводительную вещь. Другое дело, что примитивы в J очень нетривиальны, реализация полной спецификации J с существующими на сегодня оптимизациями займет, наверное, целую человеко-жизнь. Прелесть, однако, в том, что компиляцию в замыкания несложно реализовывать поэтапно, добавляя по одному глаголу, наречию или союзу. Такая работа, по идее, должна хорошо распараллеливаться.

И так, в чем я здесь не прав ? Стоит ли этим заняться ?

Чтобы не быть голословным, я вчера за несколько часов сделал простую версию лексического анализатора языка J. Работает так:

CL-USER> (setf tok (tokenizer "sum=. (i.3 4)+/ .*0j4+pru 4" 0))
#<CLOSURE (LAMBDA ()) {B8C5265}>
CL-USER> (funcall tok)
"sum"
CL-USER> (funcall tok)
"=."
CL-USER> (funcall tok)
"("
CL-USER> (funcall tok)
"i."
CL-USER> (funcall tok)
"3 4"
CL-USER> (funcall tok)
")"
CL-USER> (funcall tok)
"+"
CL-USER> (funcall tok)
"/"
CL-USER> (funcall tok)
"."
CL-USER> (funcall tok)
"*"
CL-USER> (funcall tok)
"0j4"
CL-USER> (funcall tok)
"+"
CL-USER> (funcall tok)
"pru"
CL-USER> (funcall tok)
"4"
CL-USER> (funcall tok)
""

Метки: j, progr

dr-klm.livejournal.com

достали… — Записки К.Л.М.

// (c) 2004 by K.L. Metlov <[email protected]>
//*PMRawBegin
#include "functions.inc"
//*PMRawEnd

global_settings {
   assumed_gamma 1.5
   noise_generator 2
}

light_source {
   <4, 5, -5>, rgb <1, 1, 1>
}

camera {
   perspective
   location <5, 1.5, 0>
   sky <0, 1, 0>
   direction <0, 0, 1>
   right <1.3333, 0, 0>
   up <0, 1, 0>
   look_at <0, 0, 0>
}
sphere_sweep {
   linear_spline,
   2,
   <0, -1, 0>,0.001
   <0, -1.1, 0>,0.05

   pigment {
      color rgb <0.752941, 0, 0>
   }
}

isosurface {
   function { sqrt(pow(x*2,2)+z*z+pow(abs(y*1.1-0.7*sqrt(sqrt(z*z+pow(x/2,2)/
(pow(abs(y+1.5),4)+0.001)))),2))-1+f_noise3d(x*15, y*15, z*15)*0.2 }
   contained_by { box { <-1.4, -1.4, -1.4>, <1.4, 1.4, 1.4> } }
   accuracy 0.005
   max_gradient 5
   max_trace 1

   pigment {
      color rgb <0.752941, 0, 0>
   }
   translate y*0.65
}
sky_sphere {
   pigment {
      gradient <0, 1, 0>

      color_map {
         [ 0 color rgb <0, 0, 1>
         ]
         [ 1 color rgb <0, 0, 0.752941>
         ]
      }
   }

   pigment {
      bozo
      turbulence <0.65, 0.65, 0.65>
      omega 0.7

      color_map {
         [ 0 color rgb <0.85, 0.85, 0.85>
         ]
         [ 0.1 color rgb <0.75, 0.75, 0.75>
         ]
         [ 0.5 color rgbt <1, 1, 1, 1>
         ]
         [ 1 color rgbt <1, 1, 1, 1>
         ]
      }
      scale <0.2, 0.1, 0.2>
   }
}

union {
   difference {
      plane {
         <0, 1, 0>, 0
         scale 1
         rotate <0, 0, 0>
         translate <0, 0, 0>
      }

      cylinder {
         <0, -1, 0>, <0, 0.0001, 0>, 2.25
         scale 1.5
         rotate <0, 0, 0>
         translate <0, 0, 0>
      }

      cylinder {
         <0, -100, 0>, <0, -0.0001, 0>, 1.25
         scale 1.5
         rotate <0, 0, 0>
         translate <0, 0, 0>
      }
   }

   torus {
      2.25, 1
      scale 1.5
      rotate <0, 0, 0>
      translate y*(-1.5)
   }

   texture {
      normal {
         spiral1 20
         0.25
         turbulence <0.1, 0.1, 0.1>
         rotate x*90
         scale <0.25, 0.5, 0.25>
      }

      finish {
         ambient rgb <0.15, 0.15, 0.15>
         diffuse 0.85

         reflection {
            rgb <0.2, 0.2, 0.2>
         }
      }
   }

dr-klm.livejournal.com