пятница, 17 декабря 2010 г.

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

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

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

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

понедельник, 22 ноября 2010 г.

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. Также были правы создатели тёплых ламповых Сей. Правда они сделали это на десятилетия раньше Вирта. А те кто фанатеют от каждого решения Вирта в своих языках -- не правы. Он тоже может ошибаться.

воскресенье, 21 ноября 2010 г.

Оберон & 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. Первоначально этот пост был отправлен на форум оберонщиков всея руси, однако наши оберонщики, как показала практика, критики своего языка-фетиша не выдерживают ни в каком виде, и посему пост был моментально перемещен в закрытую от посторонних глаз секцию форума (видимо, чтобы нагуглить "компромат" на оберон было не возможно).

среда, 19 мая 2010 г.

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

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

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

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


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

четверг, 22 апреля 2010 г.

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

Думал о модульности. О зависимостях, в том числе циклических. О графе зависимостей, способах и методиках его трансформации. О том что же такое модуль вообще (если в синтаксисе ЯП присутствует ключевое слово 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ть, многие из них зависили чуть ли не ото всех остальных модулей. Результат развлечений получился такой:
В общем, хоть в результате в игрушку я и не поиграл, да и отвлечься от модулей не получилось, позабавился на славу. Всякие сапёры, пасьянсы и прочие преферансы по сравнению с этим где-то как-то курят в сторонке.

воскресенье, 14 марта 2010 г.

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

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