Языки

Как я уже говорил, я никогда не повторяюсь.
(с) некто

Как я уже говорил, языки мне нравятся, но только не естественные. Английский довольно (относительного русского) прост своей грамматикой. Но в нем есть такая гадость, что нельзя синтаксически отличить существительного от глагола и существительное от прилагательного.

Вот тут есть лекции Охотина в csclub про формальные грамматики (советую посмотреть, ибо про булевы грамматики вы вряд ли где найдете), где упоминается классический пример:

Time flies like an arrow.

Fruit flies like a banana.

Время летит как стрела.
Временные мухи любят стрелы.

Фруктовые мухи любят бананы.
Фрукт летит как банан.

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

Слов мало, а терминов много. Проблемы.

Если же перейти к языкам программирования, то тут стоит напомнить цитату из "1984" Оруэлла : "новояз - единственный на свете язык, чей словарь с каждым годом сокращается".

В реальности все наоборот. Только чистые языки стабильны, остальное превращается в непонятно_во_что. Вы когда-нибудь писали на С++ ? (провокационный вопрос :) ). А знаете хотя бы одного человека, который бы мог сказать, что знает С++? Советую найти спецификацию языка и сосчитать количество страниц спецификации, которые вы использовали. Если будет более 5%, то вы гуру.

Пожалуй, только функциональщина за счет \lambda-абстракции может не расширяться. И в этом ее прелесть.

update (01.08.10).
Хотя вот немного пошлый пример на русском, показывающий проблему с глаголом/существительным:

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

abracadabra, квайн

В теории строк в качестве примеров исторически используют только три слова: "banana", "mississippi", "abracadabra". Слова содержат малое число различных букв, довольно регулярны (есть повторы подстрок).

Переписываю некоторые вещи, прогоняю тесты. Упало на сабже, смотрю на результат. Нулевая мысль - "Мда, и в самом деле херня какая-то".

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

Постановка, исходник, комментарий

Покажем, что постановка задачи оторвана от исходника, точнее в другую сторону (исходник от задачи).

В cs есть такая теорема Райса (Райса-Шапиро, в некоторых вариациях встречается фамилия Успенского, но может быть это уже оффтопик). По исходному коду нельзя понять никакие нетривиальные свойства вычисляемого алгоритма. "Как же так ?" - спросит читатель. Вот исходник, сейчас почешу голову и пойму как оно все там работает.

Перейдем к примерам. Вот, например, некий код (уж извините, императивщина):

Pair[int, int] Some(int a, int b)
{
 int p;
 p = b;
 while (a > p)
 {
  p *= 2;
 }
 int q = 0;
 while (p != b)
 {
  p /= 2;
  q *= 2;
  if (a > p)
  {
   a -= p;
   q++;
  }
 }

 return [q, a];
}

Делается ли здесь что-либо полезное?

Some(56, 8) = [6, 8]

Фиг его знает. Я не фиг, я не знаю (странный логический вывод). Если вы найдете смысл в этой программе - сообщите мне (подумайте с полчаса).

Можно ли сказать, что исходник бессмыслен или неправилен? Конечно... нет. Любой исходник туп по своей сути, формальная система лишь исполняет команды. Смысл находится вне системы.

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

Давайте рандомом поменяем два символа в исходнике.

Pair[int, int] Some1(int a, int b)
{
 int p;
 p = b;
 while (a >= p)
 {
  p *= 2;
 }
 int q = 0;
 while (p != b)
 {
  p /= 2;
  q *= 2;
  if (a >= p)
  {
   a -= p;
   q++;
  }
 }

 return [q, a];
}

Найдите два отличия (даже три) :) .

А сейчас есть ли смысл у программы? Еще раз - конечно, нет. Есть ли смысл у мясорубки? Она тупо делает фарш из всего, что ей подадут на вход. И из мяса, и из хлеба, и из карандашей (если их подать на вход). Так и программа - тупо исполняет то, что в ней написано.

Но приведем несколько тестов
Some(56, 8) = [7, 0]
Some(25, 4) = [6, 1]
Тут уже можно заметить закономерность. Внезапно, программа начала делить нацело числа! Подумайте с полчаса, как же это работает.

Является ли первая программа неправильной, а вторая - правильной? Опять же - нет. Обе программы - тупые, они лишь делают то, что в них написано. Мясорубки, что с них взять...

А вот если бы у нас была постановка задачи ранее исходников, то кое что можно было бы сказать. Заметим, что вторая программа не идеальна: деление на 0, деление только натуральных, возможен глюк при переполнении p (p *= 2;)

Так вот, из исходного кода получить постановку (Райс-Шапиро - нельзя) (я - трудновато :) ). То есть желательно двигаться от постановки задачи к исходнику. А это уже синтез программ, и тут лет на n*10 пока глуховато.

Итого, мы пришли что двигаться от программы к постановке (смыслу?) очень трудно.

Перейдем к комментариям. Тут та же фигня. Комментарий может вообще никак не быть привязан к коду, а тем более к постановке. Хуже кривого кода может быть только неадекватные комментарии.

Не могу сказать, что полностью понял идею Кнутовского грамотного программирования (literate programing); а вот контрактное программирование (Мейера, Eiffel) близко к пред/пост-условиям, и мне по душе. Текущее состояние с текстовыми комментариями, да еще в часто изменяемом коде, выглядит страшновато. Заметим, что все быстрые agile методологии предпочитают тесты вместо комментариев.

В итоге мы получили три основные сущности (постановка, код, комментарий), которые никак друг с другом не связаны.

Четверть

Пытался сегодня побаловаться с виртуализацией на старой машинке (ибо кроме mercurial-а там сейчас ничего полезного для меня нету). После ревизии железяк оказалось, что есть только 1 (из 4) рабочий ДВД. Но приложенице настоятельно требует 64-bit CPU, а это опять четверть моего парка, на котором я не готов экспериментировать. Так что эксперименты отложены на непонятное будущее.

Часть парка отдается на донашивание родителям. Если ранее они донашивали одежду, потом перешли на сотовые телефоны, сейчас донашивают машины. Ну не выбрасывать же...

Что-то среднее

Патологоанатомы утверждают, что слухи о внутренней красоте человека сильно преувеличины.

Д

П

Не существующие люди. Сгенерено при помощи. Имхо, среднее получилось поболее любой части.

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

Ранее мужской эталон красоты был тупо-сильно-прокачен => большее количество мамонтов сможет загасить. Сейчас же тупо-на-фоне-лексуса. Хотя если вы будете брать себе охранника, то выбирайте тупо-сильно-прокачен.

Женские идеалы за историю мало изменились, в основном выражают производящие функции : сиськи-попа грудь-талия-бедра.

Основная проблема, чтобы оценить внутренность одного взгляда не достаточно.

С программами иногда проще, если есть исходники или можно залезть рефлектором.

Проще всего с конфетами, их не так много, ошибиться сложно и некритично.

ЗЫ. Выяснилось, что резюме 3/4 девушек присылает с фотокарточками, с другой стороны тождественный нуль. Факт.

Не конструктивно

string-и

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

Я конечно понимаю, что там все тупо. Тупо по подстроке выдается реклама. Но где вы видели суффиксные деревья/массивы из женского белья? Алгоритмы поиска женского белья? У меня абстракции не хватает этого представить...

Быстрее, выше, сильнее (2) ...

Вы уже задолбали меня цитировать.
Станиславский.

В шоке.

Только что играл в сапер, о чем то задумался. Выскочило окно с рекордом, посмотрел на результат. В шоке. Мои предыдущий на 100 минах был 71 (причем, давно). В этом году несколько раз (около 3) делал 70 + n. Пересчитал количество мин на поле, сходится. В шоке. Написано, что 53. В шоке. Не может быть, не верю.

Видимо, очень сильно повезло со структурой. Очень регулярна.

Блин, уметь бы сериализовывать такие ситуации. Кроме как песни Цоя "Группа крови" и отрывков мысли в голове ничего не осталось.

Не верю. Плохо, что я себе не верю. И даже в скорой помощи мне не поверят, а это еще хуже. Сриншот конечно есть, но если никто никому не верит.

В шоке.

Хитрость

Умный начинает с конца, дурак - с начала, программист - с середины.
Николай Н.

Найдите биекцию с [хитрый, хитро-умный, хитро-жопый]. Такое ощущение, что последний вариант будет с середины.

Наконец-то

John C. Mitchell, Foundations for Programming Languages.

Как один из двух основных переводчиков, могу сказать "Сабж".

Книжка конечно полезная, но не всем :) . Сейчас НАКОНЕЦ-то смогу нормально по-русски почитать, и всю...

От начала до продаж прошло года 4, причем 80% перевода было сделано за полгода.

Дела и проблемы

Если на вопрос "Как дела?" вам отвечают "Нормально", значит вы не входите с группу доверия этого человека.

Прикольно, но для меня это даже не рефлексивно. Лично я изобрел фразу: "Ты бы еще спросил как у меня дела..."

А еще в последнее время от меня можно услышать фразу "Это твои проблемы". С большой вероятностью, это означает что мы более-менее хорошо знакомы. Если мы не знакомы, и вы услышали от меня эту фразу - значит мы точно не будем знакомы. А если мы малознакомы, и вы начинаете на что-то жаловаться, то я буду тупо улыбаться, так как природная скромность не позволит мне честно сказать.

Фразу "Это моя проблема" я произношу довольно часто.

А если в решении проблемы заинтересовано более одного субъекта, то это проблема. Поэтому надо делить до "Это моя проблема"/"Это твоя проблема". Только очень маленький класс проблем будет решен парой качественно (тут проблемы с внимательностью). Все остальное надо делить на эгоистические подзадачи.

Дерево

Таки реализовал порядковую статистику с поиском минимума на отрезке.
Декартовы деревья (они же дерамиды, они же treap, они же cartesian tree, они же деревья приоритетного поиска (по Вирту)) рулят. Смесь дерева и пирамиды. Дерево - для поиска, свойства кучи - для балансировки (у каждого узла есть дополнительный признак - приоритет, выбирается рандомом - по которому имеется свойства кучи). Вставка/удаление/поиск - как дерево, балансировка - как куча (два тривиальных поворота).

В Б-дереве удаление (точнее, сжатие узлов при удалении) - штука довольно нетривиальная при реализации.

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

На Б-дереве (с плотностью более 2) поиск минимума будет еще не тривиальнее.

Странно, все влезло в 10К. Теперь стоит написать комментарии, вынести минимум в сущность моноида и еще пара моментов. В 15К точно буду.

Update:
Дженерики более второго порядка в современном программировании - зло.
Как же называется коммутативная полугруппа? Моноид - не то, промахнулся я с абстракцией. Абелевы полугруппы? В мое время были только абелевы группы, let it be...
Вынес сущность, на (min, +\inf) все работало, на (+, 0) перестало. Где-то дважды хожу по дереву. Все не тривиальнее и не тривиальнее...

Update2:
забыл я алгебру... это просто коммутативный моноид.

Современность

HTC Hero очень современный телефон.

Вставив и достав наушники, он почему-то считает что уши еще есть, и поэтому при звонке голос собеседника отправляется в /dev/null (ну, или в /dev/куда_не_надо). Стоимость двух fake-звонков в Мск составляет двухмесячный бюджет моих звонков, не то что дорого, просто я звоню мало. Помог только перегруз телефона, да и потом я решил звонить с городского.

В первый раз

Сегодня впервые смог оттянуть свояка в невке. Понравилось.

Недавно за пять минут (ибо Haskell) реализовал "почти Рабина-Миллера". Не совсем классический, тупо рандомом выбираю числа и проверяю малую теорему Ферма. Начал тестировать. На двух числах, которые я был уверен что они Кармайкловы (561 как минимальное, и Рамануджан) тест выдает что составные. Что бы разобраться "что за фигня" потребовалось больше времени, чем на написание. Оказывается, все правильно. Казалось бы, что такой тест должен пропускать все Кармайкловы числа, но мы очень часто случайно выбираем число не взаимно простое с числом (561 вообще делится на 3, 11,17; 1729 на 7,13,19). Хотя из определения Кармайкловости "казалось" что должно быть "Кармайкловым".

Сейчас сижу и реализовываю Б-дерево. Вставка/замена/доступ работает, удаление пока в отладке. Найти нормальную реализацию сбалансированного дерева почему-то для меня в 2010 году еще составляет нетривиальную задачу, что проще самому написать.

Нашел несколько реализаций красно-черных и других, но там код "вонючий". Если есть приватная филда с именем "tempNode", которая инициализируется в одном методе, а используется в другом - то код для меня "вонючий". В другой реализации кода порядка 130 Кб - что-то много нетривиального, видимо. А мне не надо просто дерево, мне надо динамическую статистику (понятие из Кормена), то есть удаление/добавление/индексный_доступ за log(n), и еще расширив потребуется поиск минимума на отрезке то же за log(n).

Хотя недавно видел на Haskell реализацию красно-черного - там все повороты красиво описаны в 5-ти строках. Я же решил писать Б-дерево, так как оно интуитивно понятно (нет никаких странных поворотов), правда с удалением не совсем все тривиально.

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

n-юродность

Я долгое время не мог понять родственные отношения с n-юродностью, n >= 3. "Троюродная сестра" или "двоюродный дядя" - эти абстракции не помещались у меня в голове. Двоюродные братья/сестры у меня есть, дяди/тети тоже имеются, а всех кто дальше я причисляю к дальним родственникам.

Таки въехал. Оказывается все просто. Берем две вершины. Ищем lca. n = min(r(lca, v_1), r(lca, v_2)). \ldots Дедушка/дядя/брат/племянник/внук /ldots определяется простой разницей: r(lca, v_1) - r(lca, v_2), где r(i, j) - расстояние между прямыми потомками, не симметрично; lca - по определению :) .

Объективно пол определяется по записи в свидетельстве о рождении. Хотя я знаю нескольких физиологически-мальчиков с головами девочек, и несколько физиологически-девочек с головами мальчиков. Так что пол для меня вещь субъективная.