О математике.

Занимаюсь раскопками на поприще Рефала. Периодически натыкаюсь на некоторые весьма интересные высказывания. Например вот:

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

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

По моему, очень точно сказано.
Источник: http://www.botik.ru/mail-archive/refal/0583.html

Online syntax highlighter

В процессе написания предыдущих постов долго мучался на тему раскраски и вообще приличного оформления исходников. В конце концов нашел удобный сервис для этого: http://tohtml.com

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

PS. Динамическую раскраску синтаксиса, посредством жабаскрипта, не люблю, ибо оно требует жабаскрипта в брaузере а также иногда неплохо так тормозит рендеринг страницы.

Floor через Trunc

Продолжаем наши игры с плавающими точками (начало тут).

Кто-то заметил, что ENTIER (floor) это такая королевская функция, функция всех функций, из из которой легко получаются все остальные. И что мол Вирт выбрал её именно поэтому, мол самый базисный базис.

Однако я позволил себе в этом несколько усомниться. И на то были причины. Во-первых Trunc (отбрасывание дробной части) давно и успешно применяется в Си, и никто по этому поводу не плачет, во-вторых Trunc явно проще, а следовательно, скорее всего, первичней, ну и наконец, в своем последнем творении -- Оберон-07 Вирт закопал таки EITHER и заменил его на Trunc (обозвав его почему-то словом FLOOR).

Посему я задался вопросом, а как бы мне получить из Trunc'a Floor? Попил чайку, и в результате получилась вот такая вот функция:

int Floor(float a)
{
 int b = (int)a;
 if (a>=0 || (a-b) == 0) return b;
 else return b-1;
}

Причем она почему-то работает быстрее чем стандартная floorf. При чем, если включить sse инструкции то начинает работать ещё раза в два быстрее.

Итак, мы получили свой любимый Floor/ENTIER а дальше можем спокойно сделать с ним всё что угодно. Получать из него Ceil, Round и т.п.

Т.о. функция отбрасывающая дробную часть является таки базисной, основополагающей. И Вирт был прав когда отказался от ENTIER её пользу в Обероне-07. Также были правы создатели тёплых ламповых Сей. Правда они сделали это на десятилетия раньше Вирта. А те кто фанатеют от каждого решения Вирта в своих языках -- не правы. Он тоже может ошибаться.

Оберон & real to integer

Для справки: Oberon, Oberon2 (в дальнейшем O2), ComponentPascal (CP), считается в определенных кругах (в прицнипе не без причин) эталоном базисности и простоты. Эдакий базис императивных языков. BlackBox component builder (в дальнейшем ЧорныйЯщик) -- самая популярная реализация оного Component Pascal'я особенно в постсоветском пространстве.

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

В процессе ковыряния oo2c и, заодно, сообщений о языках O2 и CP выяснил интересную вещь. Оказывается в O2 и CP НЕТ простого и быстрого способа конвертации real -> integer. Т.е. чтобы это выражалось в одну машинную инструкцию. Подобные преобразования в обероне-2 и CP (до оберона я пока не добрался) занимают примерно в ДВА раза больше времени нежели в иных языках. Ну и имеют другую, более сложную семантику. А также не отображается на прямую в одну sse инструкцию. Преобразование real->integer в Обероне2 и CP осуществляется посредством встроенной функции ENTIER.

ENTIER работает аналогично связке стандартной сишной функции floor + преобразование типов. т.е. ENTIER(x) = (int)floor(x); Чего-то более простого в арсенале оберонщика нет.

Вот такой вот код на Обероне-2 собранный oo2c:

MODULE T;
IMPORT Out, SYSTEM;
CONST
 N = 10000;
 PI = 3.1415;
VAR
 r : LONGINT
 I : LONGINT;
 J : LONGINT;
BEGIN
 I := N;
 J := I;
 WHILE I > 0 DO
     WHILE J > 0 DO
         r := ENTIER(PI*J*I);
         DEC(J);
     END;
     DEC(I);
     J := N;
 END;
END T.

Отрабатывает за 3.4 секунды. (никаких оптимизаций).

Вот такой вот код на С++:

int main()
{
  const float pi = 3.1415;
  const int n = 10000;
  int r = 0;

  for (int i = n; i>0; i--)
      for (int j = n; j>0; j--)
          r = (int)(pi*i*j);
}

Отрабатывает за 1.6 секунды.

Если строчку r = (int)(pi*i*j); заменить на r = (int)floorf(pi*i*j); то будут те же самые 3.4 секунды. Да, оптимизация естественно отключена.

С готишным ЧорнымЯщиком вообще всё весело. Код:

MODULE Test;

 IMPORT StdLog, Services;

 CONST
 N = 10000;
 PI = 3.1415;

 PROCEDURE Do*;
    VAR t: LONGINT;
    I : LONGINT;
    J : LONGINT;
    r : LONGINT;
 BEGIN
    t := Services.Ticks();
    I := N;
    J := I;
  
    WHILE I > 0 DO
       WHILE J > 0 DO
          r := ENTIER(PI*J*I);
          DEC(J);
       END;
       DEC(I);
       J := N;
    END;

    t := Services.Ticks() - t;
    StdLog.Int(SHORT(t))
 END Do;

END Test.

Обычно функция Do отрабатывает где-то за 3.7-3.8 секунды. Однако иногда, ВНЕЗАПНО время подскакивает почти в два раза:

3759 3744 4992 3744 ...

3744 3759 3807 7441 3806 3775 4446 7800 3744 3744 3744

Да, система при этом ничем постороннем не загружена.

PS. В Обероне-07 всё это поправлено. Там ENTIER заменен на FLOOR, который не floor, а который простое отбрасывание дробной части, т.е. FLOOR(x) = (int)(x);

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

PPPS. Алсо см. https://lists.inf.ethz.ch/pipermail/oberon/2003/003254.html

Грамматика и её граф.

Моя сестра занимается весьма интересными вещами -- стохастическими грамматиками. Я в этих вещах понимаю далеко не всё, но иногда, в качестве побочных результатов исследований появляются всякие разные штуковины, которые близки и понятны обычному программисту. Так, для исследований, в качестве лабораторной мышки, с моей подачи, был выбран язык Оберон-2, который обладает одновременно двумя важными качествами: во-первых он весьма прост (по сравнению с другими ЯП), во-вторых он реально используется, и, что самое главное, можно найти некоторое количество исходников реальных программ и библиотек писаных на нем. Найти и проанализировать. Т.е. это правильная лабораторная мышка, а не какой-то там сферконь в великом ничто.

Кроме анализа исходников, в процессе анализируется и сама грамматика -- в ней ищутся классы нетерминалов. Для этого строится граф связей оных нетерминалов. И вот тут мы получаем побочный результат который может быть интересен в т.ч. и простому парню от программерской сохи -- визуальное представление оного графа грамматики реального ЯП:

(из графа удалены все терминалы)


Хорошая возможность обозреть весь язык целиком и сразу. Например видно, что имеется подъязык арифметических выражений, который слабо связан со всем остальным. Надо будет, для сравнения, построить подобные графы для других, более распространенных, языков.

Пасьянс для программиста.

Думал о модульности. О зависимостях, в том числе циклических. О графе зависимостей, способах и методиках его трансформации. О том что же такое модуль вообще (если в синтаксисе ЯП присутствует ключевое слово module это ещё ни о чем не говорит), и что это такое в таких странных ЯП как С и С++. Особенно если не полагаться на общепринятые практики и распространенные реализации, а следовать стандарту. Печалился из за отсутствия в современных ЯП явной декларации какие модули данный модуль использует, т.е. нормального import'a (например этого нет ни в java, ни в C# ни в F# или erlang'e). Читал стандарт Haskell'я, удивлялся и радовался, что в Haskell'e с модульностью как раз всё хорошо.

В общем меня это всё в конце концов таки утомило, и я решил во что-нибудь поиграть, дабы отвлечься. Посему запустил FAR (поскольку в тот момент сидел в винде), и решил проинспектировать содержимое винчестера на предмет каких-нибудь игрушек. В ходе инспекции внезапно наткнулся на BlackBox (если кто не знает, это такая среда разработки, и не только для ЯП Компонентный Паскаль, который, несмотря на название, никакой не паскаль, а вовсе модифицированный Oberon-2, см http://ru.wikipedia.org/wiki/BlackBox_Component_Builder и http://oberoncore.ru/). Запустил. Открыл какой-то примерчик. Пошарил по менюшкам. Наткнулся на пункт меню с интригующим названием "Dependencies". Нажал. Оно мне выдало вот такую картинку:

Что, как видимо, оказалось не чем иным, как графом зависимостей модулей. В данном случае -- графом зависимостей модулей подсистемы Hosts. Как видим, картинка довольно убога и не читабельна. Но поскольку оказалось что это не просто картинка, а вполне себе живой граф где узлы можно перетаскивать мышкой, я решил немного поразвлекаться и попробовать сделать картинку более наглядной. Развлекался в результате я где-то с час. Задача усложнялась тем, что хоть модулей всего 12ть, многие из них зависили чуть ли не ото всех остальных модулей. Результат развлечений получился такой:

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

Знакомство с верблюдом.

Верблюд оказался страшноватым, не чистым, и весьма энергичным.