Есть табак, да нечем нюхать

Coders at Work

2012-01-09T13:31:00.000+04:00

Coders at Work — коллекция интервью с разными компьютерными отцами, местами довольно интересная.

Jamie Zawinski, разработчик Netscape Navigator, вспоминает о кошмаре отладки на системе с упреждающим выполнением команд:

I’d gotten to the point where it’s running the executable and it’s trying to bootstrap Lisp and it gets 500 instructions in and crashes. So there I am leaning on the S key, stepping through trying to figure out where it crashes. And it seems to be crashing at a different place each time. And it doesn’t make any sense. I’m reading the assembly output of this architecture I only barely understand. Finally I realize, “Oh my god, it’s doing something different when I step; maybe it’s timing-based.” Eventually I figure out that what’s going on is this is one of the early machines that did speculative execution. It would execute both sides of the branch. And GDB would always take the branch if you single-stepped past a branch instruction. There was a bug in GDB!

перевод:

Я докопался до места, где оно исполняет программу и бутстрапит Лисп и после выполнения 500 инструкций падает. Начинаю долбить клавишу S шаг за шагом, пытаясь вычислить, где оно падает. И так получается, что оно падает в новом месте каждый раз. И совершенно непонятным образом. Читаю ассемблерный код для этой архитектуры, в котором я едва разбираюсь. Это приводит к догадке «Боже мой, во время прохода по шагам оно работает иначе; может баг зависит от времени». В конце концов я понимаю, что это одна из тех ранних машин, на котором выполнение команд было упреждающим. При ветвлении исполнялись обе ветки; а GDB, при пошаговом выполнении, шёл только по одной. Это был баг в GDB!

Brad Fitzpatrick, создатель Livejournal, делится впечатлениями о современных IDE:

My coworkers try to tell me—if they see me doing something in Emacs—that Eclipse or IntelliJ does it for them automatically. So every six months I try out one of them, Eclipse or IntelliJ. And the damn thing just sits there spinning forever, consuming memory and maybe crashes in the middle of me typing or can’t keep up with me typing. Come on—syntax-highlight in the background or compile in a different thread. Why are you blocking my typing to do this? OK, I’ll try it again in six months, guys. So I’m glad I’m not forced to use that.

перевод:

Мои коллеги, когда видят, как я делаю что-то в Emacs, спешат сообщить мне, что в Eclipse и IntelliJ всё это делается автоматически. Каждые полгода я пробую то или другое. И эта хрень только и делает, что без конца шуршит чем-то, расходуя память, и легко может упасть во время набора, или не может угнаться за мной. Неужели так сложно осуществлять подсветку в фоновом режиме и компилировать в отдельном треде. Какой смысл мешать мне печатать? Ладно, чуваки, приходите ещё через полгода. Как я рад, что всё это не является обязаловкой.

Douglas Crockford, создатель ECMAScript 3.1, критически оценивает прогресс ПО:

Progress isn’t always forward. Sometimes we’re leaping forward and sometimes we’re leaping backwards. When we leaped to the PC, we lost a whole lot of stuff. In the timesharing era, we had social systems online. A timesharing system was a marketplace. It was a community and everybody who was a part of that system could exchange email, they could exchange files, they could chat, they could play games. They were doing all this stuff and all that got lost when we went to PCs. It took another 20 years or so to get that back.

перевод:

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

Brendan Eich, создатель Javascript вообще, оправдывается за то, что в его детище нет макросов:

So we were concerned that if we went off to do macros we were doing research, and if we were doing research we were not going to have Microsoft engaged and we were not going to be putting competitive pressure on them. So macros have had to wait.

перевод:

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

(Microsoft, в итоге, одобрила Javascript, а макросы в нём так никогда и не появились.)

Joshua Bloch, создатель Java Collections, хвастается своим чутьём:

Were real engineers bitching about the lack of generics? I think the unfortunate answer to that question is, no, they weren’t. I think I was guilty of putting in something because it was neat. And because it felt like the right thing to do. That said, a lot of engineering is from the gut. Had people been telling me to put in foreach? No. They hadn’t been telling me to do that either. But I just knew that it was the right thing to do. And I was right—everybody likes it.

перевод:

Думаете, обычные программисты обламывались по поводу отсутствия дженериков? Как ни печально, им было по барабану. Я под свою ответственность включил в язык что-то клёвое. Потому что считал, что это как раз то, что надо. Вообще многое в технологии чуется нутром. Думаете, люди меня просили добавить foreach? Нет, они молчали и о нём тоже. Но я словно знал, как правильно. И всем нравится — значит, я был прав.

Joe Armstrong, создатель Erlang, даёт рецепт бутстрапа:

So then Mike did the virtual machine in C and I did the compiler in Prolog. Then the compiler compiled itself and produced byte-code and you put it in the machine and then we changed the grammar and the syntax and compiled the compiler in itself and came out with an image that would bootstrap and then we’re flying. We’ve lost our Prolog roots and we’re now a language.

перевод:

И тогда Майк сделал виртуальную машину на C, а я написал компилятор на Прологе. Затем компилятор скомпилировал самого себя и получился байт-код, который мы запустили в машину, а затем мы изменили грамматику и синтаксис и снова скомпилировали компилятор самим собой, и получился образ, который бутстрапился, короче мы взлетели. Забыли свои прологовские корни и сделали новый язык.

Simon Peyton Jones, создатель Haskell, восхищается программной транзакционной памятью:

A sequential implementation of a double-ended queue is a first-year undergraduate programming problem. For a concurrent implementation with a lock per node, it’s a research paper problem. That is too big a step. It’s absurd for something to be so hard. With transactional memory it’s an undergraduate problem again. You simply wrap “atomic” around the insert and delete operations—job done. That’s amazing, I think.

перевод:

Последовательная реализация двусвязной очереди — это школьная задачка. Параллельная реализация того же самого с поэлементными локами — уже исследовательская проблема. Разница слишком разительна. Не должны быть вещи такими сложными, это бред. А с транзакционной памятью это снова задача для школьника. Просто объявляешь операции вставки и удаления атомарными, и дело сделано. Изумительная штука.

(Также он признаётся, что так и не выучил таблицу умножения.)

Peter Norvig, глава исследовательского отдела Google, раскрывает интересные детали катастрофы Mars Climate Orbiter (в то время Питер работал в исследовательском центре Эймса):

It was a joint effort between JPL in Pasadena and Lockheed-Martin in Colorado. There were two people on two different teams and they just weren’t sitting down and having lunch together. I’m convinced that if they had, they would have solved this problem. But instead, one guy sent an email saying, you know, “Something not quite right with these measurements, seems like we’re off by a little bit. It’s not very much, it’s probably OK, but—" [...] During the flight they had chance and chance to catch it. They knew something was wrong and they sent this email but they did not put it into the bug-tracking system. If they had, NASA has very good controls for bug tracking and at later points in the flight somebody would have had to OK it. Instead it was just an informal email that never got an answer back, and JPL said, “Oh, I guess Lockheed-Martin must have solved this problem.” And Lockheed says, “Oh, JPL’s not asking anymore—they must not be concerned.”

перевод:

Это была совместная программа JPL в Пасадене и Lockheed-Martin в Колорадо. Были два человека, один тут, другой там, и им не случалось сидеть в одной комнате, обедать вместе. Если бы не это, я уверен что проблема была бы решена. Один парень послал другому письмо, типа, «что-то тут не так с единицами измерения, мы где-то напутали, не очень сильно, но—» [...] Во время полёта они не раз могли это выяснить. Они точно знали, что что-то не так, и они послали это письмо, но оно не было занесено в баг-трекер. Если бы они это сделали, то благодаря отменным средствам контроля NASA, кто-то обязательно должен был этот баг закрыть. Но вместо этого было лишь одно неформальное письмо, на которое никто не ответил, и в JPL подумали «ага, видимо Lockheed-Martin решили эту проблему». А там подумали «ага, JPL замолчали, значит это их не тревожит».

(А ещё он признаётся, что не очень-то читал тома Кнута, но подпирал ими монитор.)

Guy Steele, один из авторов SICP, отмечает, что случись вьетнамские протесты в Америке чуть раньше — не знать бы ему Лиспа и не работать в MIT в возрасте 16 лет:

Then around the beginning of July I heard that Bill Martin at MIT was looking for Lisp programmers. I thought, “Aha, I know Lisp.” I’d hung around MIT so much and had obtained copies of Lisp documentation from the Artificial Intelligence Lab and I would sneak into the labs and play with the computers. The doors were open in those days—the Vietnam protests had not yet happened, which is what caused them to put locks on the doors.

перевод:

В начале июля я узнал, что Билл Мартин из MIT ищет программистов на лиспе. Я подумал: «ага, а я знаю лисп». Потому что я постоянно ошивался в MIT, делал копии лисповой документации из лаборатории искуственного интеллекта, тайком проникал в комнаты и игрался с компьютерами. Двери в то время были открыты — вьетнамские протесты, из-за которых им пришлось повесить замки, ещё не случились.

(Речь идёт про лето 1971 года; нашествие хиппи на университеты случилось в апреле 1972.)

Dan Ingalls, автор первых реализаций Smalltalk, признаётся, что если бы он любил Lisp конца 1960-х, то за Smalltalk он бы не взялся.

When I got to Xerox there wasn’t much interactive except the Lisp guys’ stuff. I happened not to be into Lisp. Things would have been different if I were, I expect. [...] I think what I worked on with Alan had that same kind of nice, lively, expression feel, but it included the notion of objects and messages more naturally. I think if I had been as comfortable in a system like Lisp, I never would have bothered. I would have tried working around it to get objects, but starting with the notions of objects from the get-go and then making that nice and interactive and convenient was, I think, a contribution.

перевод:

Когда я попал в Xerox, с интерактивными средами было не особо, за исключением хозяйства лисперов. Так вышло, что лисп мне не пришёлся по душе. А так, думаю, всё сложилось бы иначе. [...] То, над чем я работал с Аланом, создавало схожее впечатление живой, выразительной системы, но при этом объекты и сообщения представлялись в ней более естественно. Думаю, если бы меня устраивали лисповые системы, я бы не стал этим заниматься. Я бы скорее навесил на лисп объекты. Но я начал первым делом с объектов, после чего сделал работу с ними приятной, интерактивной и удобной — в этом был мой вклад.

L Peter Deutsch, создатель Ghostscript, даёт урок расставания с надоевшим проектом:

I basically burned out on Ghostscript. Ghostscript was one of my primary technical interests starting in 1986 and it was pretty much my only major technical project starting somewhere around 1992–’93. By 1998, roughly, I was starting to feel burned out because I was not only doing all the technical work; I was also doing all the support, all the administration. I was a one-person business, and it had gotten to be too much. I hired someone to basically build up a business, and he started hiring engineers. Then it took another two years to find the right person to replace me. And then it took another two years after that to get everything really handed over. By 2002, I had had it. I didn’t want to ever see Ghostscript again.

перевод:

В сущности, Ghostscript меня вывел из строя. Он был одним из моих главных технических увлечений в 1986 году, и где-то с 1992-93 он стал практически единственным моим большим проектом. Приблизительно в 1998 я стал чувствовать, что выдыхаюсь. Я делал не только всю техническую работу, то и целиком осуществлял поддержку, вёл все дела. Это был бизнес для одного, и он стал слишком тяжёлым. Я нанял человека, чтобы расширить дело, и он стал нанимать программистов. Поиск замены мне занял два года. Ещё два года ушло на то, чтобы передать все полномочия. К 2002 для меня всё было закончено. Я больше не хотел слышать о Ghostscript.

(Ещё через полтора года Питер решил вовсе расстаться с программированием, в возрасте 57 лет.)

Ken Thompson, один из создателей UNIX и Plan 9, раскрывает секрет успеха C++:

Stroustrup campaigned for years and years and years, way beyond any sort of technical contributions he made to the language, to get it adopted and used. And he sort of ran all the standards committees with a whip and a chair. And he said “no” to no one. He put every feature in that language that ever existed. It wasn’t cleanly designed—it was just the union of everything that came along. And I think it suffered drastically from that.

перевод:

Страуструп затеял многолетнюю кампанию, далеко превосходившую всю его техническую работу над языком, ради того, чтобы язык был принят к использованию. Он типа как укротитель с хлыстом, обошёл все комитеты по стандартам и ни единому не сказал «нет». Он все когда-либо предложенные фичи запихнул в язык. В результате получилось нелепое объединение всего подряд. Мне кажется, язык от такого подхода колоссально пострадал.

Fran Allen, первая (из двух) женщина-лауреат премии Тьюринга, сетует на победу низкоуровнего программирования над высокоуровневым:

The motivation for the design of C was three problems they couldn’t solve in the high-level languages: One of them was interrupt handling. Another was scheduling resources, taking over the machine and scheduling a process that was in the queue. And a third one was allocating memory. And you couldn’t do that from a high-level language. So that was the excuse for C. [...] By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities.

перевод:

У истоков создания C стоят три проблемы, которые не могли быть решены в языках высокого уровня. Во-первых, обработка прерываний. Во-вторых, распределение ресурсов: забрав управление у машины, управлять процессом, который стоит в очереди. В-третьих, выделение памяти. Ничего из этого нельзя было сделать в высокоуровневых языках. Это оправдывает появление C. [...] К 1960 году у нас было большое количество замечательных языков: Lisp, APL, COBOL, Algol 60. Все они были более высокоуровневыми, чем C. С развитием C мы сильно откатились назад. C придушил развитие автоматической оптимизации, автоматического распараллеливания, автоматического перевода высокоуровневых команд на машинный язык. Это одна из причин, по которым компиляторы ... практически исчезли из курсов колледжей и университетов.

(Данный феномен достаточно хорошо объясняется в статье «The Rise of Worse is Better».)

Bernie Cosell, разработчик софта для первых роутеров, вспоминает, как его программа DOCTOR (ныне существующая в своей Emacs-реинкарнации), прошла тест Тьюринга:

I got a little glimmer of fame because Danny Bobrow wrote up “A Turing Test Passed”. That was one of the first times I actually got some notice for my stupid hacking: I had left Doctor up. And one of the execs at BBN came into the PDP-1 computer room and thought that Danny Bobrow was dialed into that and thought he was talking to Danny. For us folk that had played with ELIZA, we all recognized the responses and we didn’t think about how humanlike they were. But for somebody who wasn’t real familiar with ELIZA, it seemed perfectly reasonable. It was obnoxious but he actually thought it was Danny Bobrow. “But tell me more about—” “Earlier, you said you wanted to go to the client’s place.” Things like that almost made sense in context, until eventually he typed something and he forgot to hit the go button, so the program didn’t respond. And he thought that Danny had disconnected. So he called Danny up at home and yelled at him. And Danny has absolutely no idea what was going on. Except Danny knew about my terminal. So he came in and tore the typescript off of the thing, to save it.

перевод:

На меня упал тусклый луч славы, когда Дэнни Бобров написал статью «Тест Тьюринга пройден». Это был первый раз, когда я стал известен благодаря своим дурацким занятиям: я оставил Doctor-а включённым, и кто-то из начальства BBN зашёл в комнату с PDP-1 и подумал, что это пишет Дэнни Бобров, и стал с ним общаться. Мы-то, наигравшись с ELIZA, знали все ответы наизусть и не задумывались об их правдоподобности. А для тех, кто об ELIZA не знал, они казались весьма осмысленными. Программа глумилась над ним, а он реально думал, что это Дэнни Бобров. «Давайте поговорим об этом». «Вы говорили, что хотите нанести клиенту визит». Всё шло гладко, до тех пор пока он не забыл нажать кнопку, программа не ответила, и он подумал что Дэнни отсоединился. Он позвонил ему домой и наорал на него. Дэнни сначала не понял, в чём дело, но потом вспомнил про мой терминал, приехал и забрал себе ленту с копией разговора, чтобы не потерялось.

Donald Knuth, автор сами знаете чего, отрицает 64-битные указатели:

Pointers have gone out of favor to the point now where I had to flame about it because on my 64-bit computer that I have here, if I really care about using the capability of my machine I find that I’d better not use pointers because I have a machine that has 64-bit registers but it only has 2 gigabytes of RAM. So a pointer never has more than 32 significant bits to it. But every time I use a pointer it’s costing me 64 bits and that doubles the size of my data structure. Worse, it goes into the cache and half of my cache is gone and that costs cash—cache is expensive. So if I’m really trying to push the envelope now, I have to use arrays instead of pointers. I make complicated macros so that it looks like I’m using pointers, but I’m not really.

перевод:

К указателям я сейчас охладел настолько, что не могу не высказаться: у меня здесь 64-битный компьютер, и если исходить из стремления эффективно использовать его ресурсы, то я против указателей, потому что в моей машине 64-битные регистры при всего лишь двух гигабайтах памяти, что означает, что указателям хватило бы и 32 бит. Но каждый указатель стоит мне 64 бит, и это удваивает размер моей структуры данных. Хуже того, оно попадает в кеш, и половина кеша тратится зазря, а кеш это дорогая штука. Так что сейчас я пытаюсь выйти за рамки привычного, используя массивы вместо указателей. Я пишу хитрые макросы, которые позволяют мне использовать как бы указатели, которые в действительности ими не являются.

Dynamic linking considered harmful?

2011-12-09T23:54:00.001+04:00

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

Про поломку бинарной совместимости и говорить нечего, см. DLL Hell. Версионирование библиотек, придуманное для решения этой проблемы, по большому счёту только усугубляет её.

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

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

Ещё одна причина, по которой используют динамически связываемые библиотеки — это разного рода плагины. Но для механизма плагинов этого динамическое связывание не является необходимостью. Достаточно динамической загрузки кода. Кстати, Windows DLL это как раз и есть динамически загружаемые, а не связываемые, библиотеки. Динамического связывания в Windows вообще нет. Код DLL не является position-independent.

Тут бы и подумать, что Windows со своими DLL идёт впереди прогресса, не поддаваясь на провокации. Но нет. Во-первых, само присутствие DLL как отдельных системных файлов порождает проблемы, о которых сказано в первых четырёх абзацах. Почему-то принято завязываться на DLL, а не линковать всё статически. Почему? Неизвестно.

Во-вторых, в Windows очень капризная libc. Она не переносит, когда память, выделенная в одном экземпляре, освобождается в другом! Из личного опыта скажу, что даже strcpy-ровать её нельзя, хотя по ссылке этого не написано. Что делает статическую линковку с libc бессмысленной в том случае, когда у вам есть более-менее сложные плагины. Приложения и их плагины должны линковаться с динамической libc. И вообще, в Windows море проблем с написанием плагинов.

Говорят (по самой первой ссылке) что в plan9 статическая линковка и всё при этом просто и удобно, в том числе с плагинами. Хотя и плагины там не очень нужны, при наличии 9P. Сам не пробовал, подтвердить не могу.

Из фидов

2011-12-02T10:11:00.001+04:00

Иногда стартапы — это не так уж и круто, по сравнению с большими компаниями.
Иногда Clojure — это не так уж и круто, по сравнению с динамическими лиспами.

Обе статьи написаны на английском русскоговорящими чуваками.

Разработка языка программирования на Racket

2011-11-03T02:40:00.001+04:00

Racket — современная платформа для разработки языков программирования, одна из самых прогрессивных, наследница Lisp.

Пара слов о Лиспе: будучи созданным 50 лет назад, он живёт и развивается до сих пор, причём последние 20 лет практически без финансирования. Что означает, что язык действительно хорош. Надо отметить, что Джон Маккарти (автор термина «искусственный интеллект», AI) изобрёл Лисп как подручное средство для создания этого самого AI. Маккарти умер, AI как не было так и нет, но идеи, заложенные в Лисп, в течение полувека находят применение в совершенно не связанных с AI областях. Что означает, что идеи действительно хороши.

Цель авторов Racket можно сформулировать так: дать разработчикам возможность создавать свои языки, не лишая их при этом прелестей Лиспа. «Лисп как основа и любой ваш каприз вдобавок» — звучит как предложение, от которого невозможно отказаться. В отличие от Common Lisp, где новые языки как правило создаются на базе грамматики S-выражений, в Racket для них допустима любая грамматика. Плюс к тому, отладчик и редактор с подсветкой синтаксиса — практически даром. Решительно невозможно отказаться.

По какой-то причине в сети нет подробного руководства по созданию своего языка в Racket «от и до». Впрочем, уже есть, раз вы его читаете. Оно было собрано по кускам из одного короткого примера, документации Racket и кода встроенных в Racket языков (Algol, Datalog). Для руководства такие изыски ни к чему, поэтому мы сейчас сделаем в Racket калькулятор. Типа такого:

X = 2.8
Y = (X + 1) * 5
print X / Y

с блекдж... пардон, с пошаговым выполнением, бектрейсами и REPL.

Вещи, относящиеся к языкам, Racket желает видеть в одной из своих «системных» директорий, поэтому лучше с самого начала работать в директории $HOME/.racket/$VERSION/collects/, или создать симлинк из неё в место, где лежат исходники. Пусть язык называется calc, тогда нужно сделать примерно следующее

mkdir /home/username/calc
ln -s /home/username/calc /home/username/.racket/5.1.3/collects/

(Кажется, в Windows тоже можно создавать симлинки, начиная с Vista, но я не проверял.)

Этап 1: базовый комплект

Начнём с лексического анализатора, который будет в файле calc/lexer.rkt:

#lang racket

(require
  ; lex -- стандартное средство для построения лексических анализаторов
  parser-tools/lex 
  ; Библиотека регулярных выражений для lex. Символы, импортированные из неё,
  ; будут предваряться знаком двоеточия, в целях избежания конфликтов имён
  (prefix-in : parser-tools/lex-sre))

; Указанные вещи из этого модуля идут на экспорт
(provide value-tokens op-tokens
         position-line position-col position-offset
         calc-lexer)

; Регулярные выражения для букв, цифр и всяких пробелов
(define-lex-abbrevs
  (lex:letter (:or (:/ #\a #\z) (:/ #\A #\Z)))
  (lex:digit (:/ #\0 #\9))
  (lex:whitespace (:or #\newline #\return #\tab #\space #\vtab)))

; Токены, имеющие значения -- идентификатор (например X) и число (например 2.8)
(define-tokens value-tokens (IDENTIFIER NUMBER))

; Токены, не имеющие значений -- арифметические операции, скобки, присваивание,
; операция печати (PRINT) и специальный токен EOF
(define-empty-tokens op-tokens
  (EOF ASSIGN PLUS MINUS MULTIPLY DIVIDE LEFT-PAREN RIGHT-PAREN PRINT))

; calc-lexer -- это функция, полученная в результате вызова lexer-src-pos
(define calc-lexer
  ; lexer-src-pos отличается от lexer тем, что выдаёт не просто токены,
  ; а position-token -- токены с информацией об их положении в исходном файле
  (lexer-src-pos
   ; пробелы и прочее пропускаем, рекурсивно запуская lexer дальше
   ((:+ lex:whitespace) (return-without-pos (calc-lexer input-port)))
   ; токены операций
   ("=" (token-ASSIGN))
   ("+" (token-PLUS))
   ("-" (token-MINUS))
   ("*" (token-MULTIPLY))
   ("/" (token-DIVIDE))
   ("(" (token-LEFT-PAREN))
   (")" (token-RIGHT-PAREN))
   ("print" (token-PRINT))
   ; идентификатор = буква + [произвольный набор букв и цифр]
   ((:: lex:letter (:* (:or lex:letter lex:digit)))
    (token-IDENTIFIER (string->symbol lexeme)))
   ; число = [знак] + не менее одной цифры + [точка [с цифрами]]
   ((:: (:? #\-) (:+ lex:digit) (:? (:: #\. (:* lex:digit))))
    (token-NUMBER (string->number lexeme)))
   ; специальный токен EOF необходимо вернуть при достижении конца файла
   ((eof) 'EOF)))

Теперь парсер, calc/parser.rkt:

#lang racket

(require
  ; модуль с генератором парсеров
  parser-tools/yacc
  ; модуль, содержащий нужную нам функцию raise-read-error
  syntax/readerr
  ; наш лексический анализатор
  calc/lexer)

(provide calc-read-syntax
         calc-read)

; Функция, которую мы будем вызывать при ошибке парсинга
(define (on-error source-name)
  (lambda (tok-ok? tok-name tok-value start-pos end-pos)
    ; генерирует исключение
    (raise-read-error 
             "Parser error" ; текст исключения
             source-name                  ; имя файла
             (position-line start-pos)    ; номер строки с ошибкой
             (position-col start-pos)     ; номер колонки с ошибкой
             (position-offset start-pos)  ; смещение от начала файла
             (- (position-offset end-pos) ; длина фрагмента с ошибкой
                (position-offset start-pos)))))

; calc-parser -- это функция, возвращающая функцию, полученную
; в результате вызова функции parser из модуля parser-tools/yacc
(define (calc-parser source-name)
  (parser
   (src-po  s)   ; это нужно для того, чтобы в функцию обработки ошибки
                 ; передавалась позиция проблемного куска
   (start start) ; стартовый нетерминал у нас называется start
   (end EOF)     ; конец файла у нас называется EOF
   (tokens value-tokens op-tokens) ; две группы токенов, определённые в calc-lexer
   (error (on-error source-name))  ; функция обработки ошибок (см. выше)
   
   ; Грамматика

   (grammar
    ; программа = команды
    (start
     ((statements) $1))
    
    (statements
     ; команды = ничто
     (() '())
     ; или команда + команды
     ; $1 и $2 обозначают соответственно первый и второй элементы
     ; сопоставления, то есть statement и statements
     ((statement statements) (list* $1 $2)))
    
    (statement
     ((assignment) $1)
     ((printing) $1))
    
    (constant
     ((NUMBER) $1))
    
    (expression
     ; выражение = терм
     ((term) $1)
     ; или выражение плюс/минус токен.
     ; PLUS и MINUS здесь -- терминалы, взятые из op-tokens из calc/lexer.
     ((expression PLUS term) (list 'plus $1 $3))
     ((expression MINUS term) (list 'minus $1 $3)))
    
    (term
     ((factor) $1)
     ((term MULTIPLY factor) (list 'multiply $1 $3))
     ((term DIVIDE factor) (list 'divide $1 $3)))
    
    (factor
     ((primary-expression) $1)
     ((MINUS primary-expression) (list 'negate $2))
     ((PLUS primary-expression) $2))
    
    (primary-expression
     ((constant) $1)
     ((IDENTIFIER) (list 'value-of $1))
     ((LEFT-PAREN expression RIGHT-PAREN) $2))
    
    (assignment
     ((IDENTIFIER ASSIGN expression) (list 'assign $1 $3)))
    
    (printing
     ((PRINT expression) (list 'print $2))))))

Теперь свяжем лексический и синтаксический анализаторы в одно целое с помощью функции, которая принимает некоторый входной поток (в Racket это называется «порт») и соответствующее ему имя файла, и возвращает результат граматического разбора. Правим дальше calc/parser.rkt:

(define (parse-calc-port port file)
  ; посчитать номера строк заранее
  (port-count-lines! port)
  ; создать и сразу вызвать парсер
  ((calc-parser file)
   ; и передать в него функцию, которая должна выдавать токены один за другим
   (lambda ()
     ; calc-lexer как раз это и делает 
     (calc-lexer port))))

Поскольку наш анализатор должен будет работать в среде Racket на тех же правах, на которых работает «родной» анализатор, мы должны реализовать функции calc-read и calc-read-syntax, которые придут на замену стандартным read и read-syntax. Окончание calc/parser.rkt:

(define (calc-read in)
  (syntax->datum
   (calc-read-syntax #f in)))

(define (calc-read-syntax source-name input-port)
  (parse-calc-port input-port source-name))

Пояснение: в то время как calc-read возвращает прочитанные данные (datum) вида ((assign X (+ 1 2)), calc-read-syntax возвращает синтаксические объекты, что есть по сути те же самые данные, но с привязкой к участкам исходного файла и прочей информацией. В зависимости от режима работы Racket пользуется либо read, либо read-syntax, и во избежание неожиданностей лучше сделать их одинаковыми. Что и сделано: calc-read просто берёт синтаксические объекты из calc-read-syntax и превращает их в данные с помощью syntax->datum.

Настало время встроить наш анализатор в среду Racket. Это очень просто: нужно создать файл calc/lang/reader.rkt следующего содержания:

(module reader syntax/module-reader
  #:language 'racket              ; об этом позже
  #:read calc-read                ; переопределение стандартного read
  #:read-syntax calc-read-syntax  ; переопределение стандартного read-syntax
  #:whole-body-readers? #t ; этот флаг устанавливается в том случае, когда наши
                           ; read и read-syntax всегда читают входной поток до
                           ; конца (calc-read и calc-read-syntax так и делают)
  (require calc/parser))   ; модуль, в котором лежат calc-read и calc-read-syntax

Racket, увидев #lang calc в начале файла, будет искать calc/lang/reader.rkt в системных директориях, включая $HOME/.racket/5.1.3/collects/, где мы всё и делаем. Поэтому мы уже можем начинать писать код на calc в среде Racket. Создадим файл test.calc:

#lang calc
X = 3
Y = X + 1
Print X * X + Y * Y

pi = 3.1415926535
r = 12.2
l = 40
Print pi * r * (2 + l)

Запускать файл на выполнение ещё рано, т.к. реализации языка пока ещё нет. Но уже можно посмотреть на результат синтаксического анализа кода, для чего в Racket есть удобный инструмент под названием Macro stepper. Нажимаем...

и видим сообщение «Parser error» из нашего calc/parser.rkt. Ошибка состоит в том, что слово Print написано с большой буквы, тогда как лексический анализатор допускает только «print» без вариантов. Сделаем его нечувствительным к регистру (calc/lexer.rkt):

; вспомогательная функция, преобразующая строку в выражение, нечувствительное
; к регистру, например "foo" -> (:: (:or #\f #\F) (:or #\o #\O) (:or #\o #\O))
(define-for-syntax (string->ci-pattern s)
  (cons ':: (map (lambda (c)
                   (list ':or (char-downcase c) (char-upcase c)))
                 (string->list s))))

; специализированный макрос для применения в лексическом анализаторе
(define-lex-trans lex-ci
  (lambda (stx)
    (syntax-case stx ()
      ((_ id) ; здесь id -- это строка, которую мы преобразуем, т.е. "print"
       (with-syntax ((result (string->ci-pattern
                              (syntax->datum #'id))))
         #'result)))))

(define calc-lexer
  (lexer-src-pos
   ((:+ lex:whitespace) (return-without-pos (calc-lexer input-port)))
   ("=" (token-ASSIGN))
   ("+" (token-PLUS))
   ("-" (token-MINUS))
   ("*" (token-MULTIPLY))
   ("/" (token-DIVIDE))
   ("(" (token-LEFT-PAREN))
   (")" (token-RIGHT-PAREN))
   ((lex-ci "print") (token-PRINT))
   ((:: lex:letter (:* (:or lex:letter lex:digit)))
    (token-IDENTIFIER (string->symbol lexeme)))
   ((:: (:? #\-) (:+ lex:digit) (:? (:: #\. (:* lex:digit))))
    (token-NUMBER (string->number lexeme)))
   ((eof) 'EOF)))

Запускаем Macro stepper вторично на test.calc и видим

Парсер успешно отработал и выдал в качестве результата набор конструкций вида

(assign X 3)
(assign Y (plus (value-of X) 1))

Что не является валидным кодом на Racket, что подтверждается сообщением «unbound identifier in module». Но по замыслу — полученный код и не должет являться кодом на Racket! Для исполнения этого кода мы должны создать набор макросов, преобразующих его в код на Racket, а точнее — в синтаксические объекты. Декларация #:language в calc/lang/reader.rkt — именно об этом. Мы написали #:language 'racket исключительно потому, что совсем ничего не писать система не позволяет. На самом деле, в этом месте нужно указать путь к модулю с макросами:

(module reader syntax/module-reader
  #:language 'calc/language
  #:read calc-read
  #:read-syntax calc-read-syntax
  #:whole-body-readers? #t
  #:language-info '#(calc/lang/lang-info get-info #f)
  (require calc/parser))

каковой модуль мы сейчас и создадим (calc/language.rkt):

#lang racket

(provide
 ; Системные вещи, на которых мы не будем заострять внимание.
 ; Достаточно знать, что #%module-begin и #%datum из racket
 ; годятся и для calc, поэтому мы переэкспортируем их без изменений
 #%module-begin #%datum
 ; Макросы для выполнения операций языка calc
 assign plus minus divide multiply negate value-of print)

; Окружение = хеш-таблица со значениями переменных
(define current-env (make-hash))

; Присваивание переменной = запись в хеш-таблицу
(define-syntax-rule (assign name value)
  ; Обратите внимание на апостроф перед name: он делает из имени переменной,
  ; переданной в макрос, символ. Таким образом, из (assign X 3) получается
  ; (hash-set! current-env 'X 3), в то время как
  ; (hash-set! current-env X 3) выдало бы ошибку
  (hash-set! current-env 'name value))

; Арифметические операции

(define-syntax-rule (plus a b)
  (+ a b))

(define-syntax-rule (minus a b)
  (- a b))

(define-syntax-rule (divide a b)
  (/ a b))

(define-syntax-rule (multiply a b)
  (* a b))

(define-syntax-rule (negate a)
  (- a))

; Получение значения переменной по имени
(define-syntax-rule (value-of name)
  ; То же самое с апострофом, см. макрос assign
  (hash-ref current-env 'name))

; Печать
(define-syntax-rule (print value)
  (printf "~v\n" value))

Теперь можно наконец выполнить (Run) наш test.calc:

Запустив Macro stepper снова и выключив в нём опцию «macro hiding», мы можем наблюдать, во что в конечном итоге раскрылся наш код:

На этом этапе можно считать, что у нас есть парсер и компилятор. Всё это занимает 110 строк, не считая пустых строк и комментариев.

Этап 2: необходимые примочки

Если мы сейчас попробуем запустить отладчик (Debug) и поставить брекпоинт в код программы, нас ждёт неудача. Объясняется это просто: парсер в calc/parser.rkt возвращает не синтаксические объекты, а простые списки, т.е. datum-ы. Они преобразуются в синтаксические объекты позже, автоматически, но дела это в принципе не меняет, т.к. информации о местоположении синтаксических единиц в исходном коде не появляется. Эта информация известна только парсеру. Он её «забывает» везде, кроме функции on-error. И поставить брекпоинт невозможно, т.к. система просто не знает, какой синтаксический объект к какому месту исходного кода относится. Сейчас мы это исправим (calc/parser.rkt):

(define-syntax (build-so stx)
  (syntax-case stx ()
    ((_ value start end)
     ; вытаскиваем из контекста (stx) $i-start-pos и $j-end-pos, где i и j --
     ; числа, переданные в макрос как start и end; а также source-name
     (with-syntax ((start-pos (datum->syntax
                               stx
                               (string->symbol 
                                (format "$~a-start-pos"
                                        (syntax->datum #'start)))))
                   (end-pos (datum->syntax
                             stx
                             (string->symbol 
                              (format "$~a-end-pos"
                                      (syntax->datum #'end)))))
                   (source (datum->syntax
                            stx
                            'source-name)))
       (syntax
        (datum->syntax
         #f
         value
         ; конструируем уже знакомую по on-error пятёрку значений
         (list source 
               (position-line start-pos)
               (position-col start-pos)
               (position-offset start-pos)
               (- (position-offset end-pos)
                  (position-offset start-pos)))))))))

(define (calc-parser source-name)
  (parser
   (src-pos)
   (start start)
   (end EOF)
   (tokens value-tokens op-tokens)
   (error (on-error source-name))
   
   (grammar
    (start
     ; Числа 1 и 1, переданные в макрос build-so, раскрываются соответственно в
     ; $1-start-pos и $1-end-pos, каковые переменные доступны благодаря указанию
     ; (src-pos) выше и содержат начальную и конечную позиции первого нетерминала
     ; в списке (в данном случае он всего один и есть). 
     ((statements) (build-so $1 1 1)))
    
    (statements
     (() '())
     ((statement statements) (list* $1 $2)))
    
    (statement
     ((assignment) $1)
     ((printing) $1))
    
    (constant
     ((NUMBER) $1))
    
    (expression
     ((term) $1)
     ; Числа 1 и 3 раскрываются макросом build-so в $1-start-pos и $3-end-pos
     ; соответственно, т.е. от начала первого нетерминала до конца третьего.
     ((expression PLUS term) (build-so (list 'plus  $1 $3) 1 3))
     ((expression MINUS term) (build-so (list 'minus $1 $3) 1 3)))
    
    (term
     ((factor) $1)
     ((term MULTIPLY factor) (build-so (list 'multiply $1 $3) 1 3))
     ((term DIVIDE factor) (build-so (list 'divide $1 $3) 1 3)))
    
    (factor
     ((primary-expression) $1)
     ((MINUS primary-expression) (build-so (list 'negate $2) 1 2))
     ((PLUS primary-expression) $2))
    
    (primary-expression
     ((constant) $1)
     ((IDENTIFIER) (build-so (list 'value-of $1) 1 1))
     ((LEFT-PAREN expression RIGHT-PAREN) (build-so $2 1 3)))
    
    (assignment
     ((IDENTIFIER ASSIGN expression) (build-so (list 'assign $1 $3) 1 3)))
    
    (printing
     ((PRINT expression) (build-so (list 'print $2) 1 2))))))

И о чудо, теперь работает отладчик, можно ставить брекпоинты, ходить по шагам, даже стек вызовов имеется:

Racket позволяет отладчику заходить в реализацию вашего языка в лисповых функциях, если в момент отладки модули с этими функциями открыты. Но нашего calc/language.rkt это не касается, поскольку ни одной функции у нас нет — мы обошлись макросами. То есть ближайший уровень, в который может попасть отладчик после кода на calc — это реализация hash-set, + и прочих примитивных вызовов. На такой уровень нам нет необходимости опускаться.

Обратим теперь внимание на то, что для языка calc не работает REPL! Об этом честно собщается после выполнения программы (Run) чёрным текстом на жёлтом фоне. REPL не работает потому, что в реализации (calc/language.rkt) не определён макрос #%top-interaction, который собственно и должен раскрывать полученные в REPL синтаксические объекты. Стандартный макрос из Racket не годится, так что мы напишем свой, очень простой:

#lang racket

(provide
 #%module-begin #%datum
 ; Переопределять #%top-interaction внутри модуля нельзя, поэтому мы
 ; сделаем макрос top-interaction и переименуем его при экспорте.
 (rename-out (top-interaction #%top-interaction))
 assign plus minus divide multiply negate value-of print)

; Макрос действительно такой -- с троеточиями. Это часть синтаксиса.
(define-syntax-rule (top-interaction body ...)
    (begin body ...))

Но этого недостаточно. Проблема в том, что декларации #:read и #:read-syntax в calc/reader.rkt по какой-то причине не распространяются на REPL. REPL в DrRacket принадлежит самой DrRacket и подлежит настройке отдельно, по строго определённым правилам. Нужно добавить декларацию #:language-info в calc/reader.rkt:

(module reader syntax/module-reader
  #:language 'calc/language
  #:read calc-read
  #:read-syntax calc-read-syntax
  #:whole-body-readers? #t
  #:language-info '#(calc/lang/lang-info get-info #f)
  (require calc/parser))

Затем нужно создать модуль calc/lang/lang-info.rkt такого содержания:

#lang racket/base

(provide get-info)

(define (get-info data)
  (lambda (key default)
    (case key
      ((configure-runtime)
       '(#(calc/lang/configure-runtime configure #f)))
      (else
       default))))

Наконец, нужно создать модуль calc/lang/configure-runtime.rkt, содержащий функцию конфигурации рантайма:

#lang racket/base

(require calc/parser)
(provide configure)

(define (configure data)
  ; Конфигурация заключается в установке параметра current-read-interaction
  ; (Параметры в Racket -- что-то вроде динамических переменных в Common Lisp.)
  ; Мы меняем этот параметр на нашу функцию, которая вызывает наш парсер.
  (current-read-interaction even-read))

(define (even-read source-name input-port)
  (begin0
    (parse-calc-port input-port source-name)
    ; Почему-то нужно делать так, чтобы последующий вызов
    ; current-read-interaction вернул EOF. С этой целью производится
    ; нижеследующий трюк с заменой параметра на odd-read. 
    (current-read-interaction odd-read)))

; Вторая часть трюка заключается в замене параметра обратно на even-read.
; Среди разработчиков нет согласия по поводу того, правильно ли так делать;
; оставим этот вопрос на их совести, в любом случае все имеющиеся примеры
; работают именно так.
(define (odd-read src ip)
  (current-read-interaction even-read)
  eof)

И вот, у нас работает REPL:

Благодаря умной работе механизма модулей, два и более открытых одновременно окна с программами на calc не конфликтуют и не засоряют окружение друг друга:

Самое время заметить, что ошибки с необъявленными переменными возникают на этапе выполнения программы, тогда как во всех нормальных средах они должны отлавливаться на этапе компиляции. Полноценный компилятор мы писать не будем, ограничимся проверкой того, что все используемые переменные встретились перед использованием в левой части. Файл calc/compiler.rkt:

#lang racket

(provide compile-program
         compile-statement)

; Хеш-таблица имён переменных
; (не путать с current-env в language.rkt, это разные этапы)
(define variables (make-hash))

(define (compile-program p)
  ; проверить все подвыражения (syntax-e раскрывает синтаксический
  ; объект-список в список синтаксических объектов)
  (for-each check-syntax (syntax-e p))
  ; вернуть исходную синтаксическую конструкцию как результат
  ; (приличный компилятор вернул бы новую, оптимизированную конструкцию)
  p)

(define (compile-statement s)
  (check-syntax s)
  s)

(define (check-syntax s)
  ; Что за объект? Преобразуем в данные и посмотрим.
  (match (syntax->datum s)
    ; Команда присваивания
    ((list 'assign a b)
     ; Сначала проверим правую часть, чтобы поймать ошибки вида X = X
     (check-syntax (third (syntax-e s)))
     ; Теперь занесём левую часть в словарь
     (hash-set! variables a a))
    ; Доступ к переменной
    ((list 'value-of a)
     ; Есть ли она в словаре?
     (unless (hash-has-key? variables a)
       ; Если нет -- ошибка со ссылкой на соответствующий синтаксический объект
       (raise-syntax-error
        #f "access to unassigned variable" (second (syntax-e s)))))
    ; Все прочие команды
    ((list x ...)
     ; проверяются рекурсивно
     (for-each check-syntax (syntax-e s)))
    ; Константы не подлежат проверке
    (_ #f)))

Попросим парсер вызывать "компилятор" перед возвращением результата (calc/parser.lisp):

(require parser-tools/yacc
         syntax/readerr
         calc/lexer
         calc/compiler)

(define (calc-read-syntax source-name input-port)
  (compile-program
   (parse-calc-port input-port source-name)))

Насладимся результатом:

Попросим REPL делать то же самое (calc/lang/configure-runtime.rkt):

(require calc/parser
         calc/compiler)

(define (even-read source-name input-port)
  (begin0
    (compile-statement (parse-calc-port input-port source-name))
    (current-read-interaction odd-read)))

Насладимся результатом и здесь:

Отметим, что ошибки времени выполнения всё же случаются, и снабжены бектрейсом:

На данный момент у нас есть всё необходимое, а написали мы всего 208 строк кода.

Этап 3: элементы роскоши

Такая беда: REPL не позволяет переводить строку. Нажатие Enter ведёт к немедленному отправлению строки на синтаксический анализ. Мы собирались дописать команду на следующей строке, но REPL безжалостен.

Хорошая новость: поведение REPL можно настроить. Открываем снова calc/lang/lang-info.rkt:

(define (get-info data)
  (lambda (key default)
    (case key
      ((configure-runtime)
       '(#(calc/lang/configure-runtime configure #f)))
      ((drracket:submit-predicate)
       (dynamic-require 'calc/tool/submit 'repl-submit?))
      (else
       default))))

и создаём модуль calc/tool/submit.rkt с функцией repl-submit?, которая возвращает #t, если перевод строки завершающий, и #f, если промежуточный. Определить это не так просто, учитывая, что пользователь может вводить в REPL всё, что ему заблагорассудится. Будем считать, что строка готова к синтаксическому анализу, если она не пустая, не завершается оператором (+, -, /, *, =, print) и если скобки в ней сбалансированы. Весьма уместно использовать уже готовый лексический анализатор для выполнения этой задачи:

#lang racket

(require calc/lexer
         parser-tools/lex)

(provide repl-submit?)

(define (repl-submit? ip has-white-space?)
  (let loop ((blank? #t)      ; строка пустая?     
             (pending-op? #f) ; строка завершается оператором?
             (paren-count 0)) ; баланс скобок
    ; Все ошибки лексического анализатора мы обязаны пропускать
    (with-handlers ((exn:fail:read?
                     (lambda (e)
                       #t)))
      (let ((token (position-token-token (calc-lexer ip))))
        (case token
          ((EOF)
           (and (zero? paren-count)
                (not blank?)
                (not pending-op?)))
          ((PLUS MINUS MULTIPLY DIVIDE ASSIGN PRINT)
           (loop #f #t paren-count))
          ((LEFT-PAREN)
           (loop #f #f (+ paren-count 1)))
          ((RIGHT-PAREN)
           (loop #f #f (- paren-count 1)))
          (else
           (loop #f #f paren-count)))))))

Вроде работает:

Почти всё. Осталось только добавить подсветку синтаксиса. Ну и, например, комментарии, чтобы было что подсвечивать. Пусть комментарии будут в стиле bash — от символа «#» до конца строки. Обновляем calc/lexer.rkt, попутно экспортируя из него некоторые вещи, которые скоро понадобятся:

(provide value-tokens op-tokens
         position-line position-col position-offset
         calc-lexer
         lex:comment lex:identifier lex:number lex-ci)

(define-lex-abbrevs
  (lex:letter (:or (:/ #\a #\z) (:/ #\A #\Z)))
  (lex:digit (:/ #\0 #\9))
  (lex:comment (:: "#" (:* (:: (char-complement #\newline))) (:? #\newline)))
  (lex:whitespace (:or #\newline #\return #\tab #\space #\vtab))
  (lex:identifier (:: lex:letter (:* (:or lex:letter lex:digit))))
  (lex:number (:: (:? #\-) (:+ lex:digit) (:? (:: #\. (:* lex:digit))))))

(define calc-lexer
  (lexer-src-pos
   ((:+ lex:whitespace) (return-without-pos (calc-lexer input-port)))
   ; комментарии пропускаем так же, как и пробелы
   ((:+ lex:comment) (return-without-pos (calc-lexer input-port)))
   ("=" (token-ASSIGN))
   ("+" (token-PLUS))
   ("-" (token-MINUS))
   ("*" (token-MULTIPLY))
   ("/" (token-DIVIDE))
   ("(" (token-LEFT-PAREN))
   (")" (token-RIGHT-PAREN))
   ((lex-ci "print") (token-PRINT))
   (lex:identifier (token-IDENTIFIER (string->symbol lexeme)))
   (lex:number (token-NUMBER (string->number lexeme)))
   ((eof) 'EOF)))

Информация о подсветке синтаксиса задаётся определённым образом в директиве #:info файла calc/lang/reader.rkt:

(module reader syntax/module-reader
  #:language 'calc/language
  #:read calc-read
  #:read-syntax calc-read-syntax
  #:whole-body-readers? #t
  #:language-info '#(calc/lang/lang-info get-info #f)
  #:info (lambda (key defval default)
           (case key
             ((color-lexer)
              (dynamic-require 'calc/tool/syntax-color 'get-syntax-token))
             (else (default key defval))))
  (require calc/parser))

Собственно подсветку осуществляет отдельный модуль calc/tool/syntax-color.rkt. В нём находится, по сути, ещё один лексический анализатор, но такой, который выдаёт не токены, а особые «пятёрки» значений: лексема, её тип (комментарий/константа/ключевое слово/символ/etc), «скобочность», а также начало и конец лексемы в исходном файле:

#lang racket

(require parser-tools/lex
         (prefix-in : parser-tools/lex-sre)
         calc/lexer)

(provide get-syntax-token)

(define (syn-val lexeme type paren start end)
  (values lexeme type paren (position-offset start) (position-offset end)))

(define get-syntax-token
  (lexer
   ((:+ whitespace)
    (syn-val lexeme 'whitespace #f start-pos end-pos))
   (lex:comment
    (syn-val lexeme 'comment #f start-pos end-pos))
   (lex:number
    (syn-val lexeme 'constant #f start-pos end-pos))
   ; "Print" у нас будет единственным ключевым словом
   ((lex-ci "print")
    (syn-val lexeme 'keyword #f start-pos end-pos))
   ; Имена переменных у нас будут идентфикаторами
   (lex:identifier
    (syn-val lexeme 'symbol #f start-pos end-pos))
   ; Арифметические операции и "=" будут считаться за скобки
   ; (Операций кроме скобок Racket, похоже, не знает)
   ((:or #\+ #\- #\/ #\* #\=)
    (syn-val lexeme 'parenthesis #f start-pos end-pos))
   ; Сами скобки тоже считаются за скобки, и вдобавок к тому обладают свойством
   ; "скобочности", чтобы редактор Racket подсвечивал открывающие и закрывающие,
   ; опять же, скобки.
   (#\( (syn-val lexeme 'parenthesis '|(| start-pos end-pos))
   (#\) (syn-val lexeme 'parenthesis '|)| start-pos end-pos))
   ((eof) (syn-val lexeme 'eof #f start-pos end-pos))
   (any-char (syn-val lexeme 'error #f start-pos end-pos))))

Внимание: чтобы подсветка синтаксиса заработала, надо перезапустить Racket! Если вдуматься, это значит, что при выполнении всех предыдущих операций Racket не надо было перезапускать! И даже test.calc можно было не закрывать. При том, что мы там «резали по живому» во многих местах. Racket истинно динамическая платформа. Вот что получится после перезапуска:

Подсветка синтаксиса в действии. В REPL, правда, она не работает (то есть работает, но не наша, а стандартная), но не будем придираться к мелочам. Racket — прекрасная вещь. Всё вышеописанное мы сделали, написав 268 строк кода. То, что получилось, можно скачать здесь. Вообще-то можно ещё сделать так, чтобы язык calc включался без #lang calc, и ещё можно научить DrRacket смотреть переменные в отладчике, и ещё можно собрать DrRacket, кастомизированный под calc и готовый к распространению, но обо всём этом как-нибудь в другой раз.

Как создавать DSL

2011-09-27T12:12:00.000+04:00

Необходимость создания предметно-ориентированных языков (domain-specific languages, DSL) может быть продиктована разными причинами. Например, появлением новой технологической ниши, как было с HTML и SQL. Или крайней неуклюжестью давно занявших свои ниши языков общего назначения... не будем их называть. Ещё бывают причины чисто исторические. Неважно. Пусть вам пришла в голову идея сделать DSL. Сочинили вы язык, описали грамматику, продумали семантику, а дальше что? Как получить транслятор, отладчик, где взять удобную среду для написания кода на этом DSL? Не самому же всё делать с нуля. Вот об этом и речь.

Прежде всего надо определиться: DSL или EDSL? Второй вариант, который расшифровывается как «встроенный предметно-ориентированный язык» (embedded DSL, или internal DSL), сделает вашу жизнь значительно легче. Вы выбираете язык общего назначения, для которого все средства разработки уже сделаны до вас, и создаёте свой язык как надстройку над первым, оставаясь в рамках его грамматики. Фактически, вы делаете библиотеку. Само собой, если изначальный язык (хост-язык) недостаточно гибок в плане грамматических конструкций, то и от DSL особенного удобства ждать не приходится. Тем не менее, можно на Ruby, C#, Scala создавать вполне удобные EDSL. Даже на C++ с шаблонами можно создавать совершенно потрясающие вещи.

Вообще говоря, если вы выбрали EDSL — т.е. готовы жертвовать грамматикой языка ради готовых средств разработки — то почему бы не жертвовать до конца. Откажитесь от грамматики и задавайте программу сразу как экземпляр метамодели (что принято называть абстрактным синтаксическим деревом, хотя оно не абстрактное, да и к синтаксису отношения не имеет). Возьмите платформу, которая заточена под работу с такими программами. Речь, конечно, о семействе лиспов (Common Lisp, Scheme, Clojure). Никакого синтаксиса, кроме простейших S-выражений. Динамическая типизация. Система компилируемых макросов. Культура инкрементальной разработки. Лиспам нет равных в быстроте и удобстве создания EDSL. В знаменитой книге SICP мини-языки в рамках Scheme создаются практически под каждую задачу, и даже без использования макросов.

Мы подошли к месту, когда нельзя не упомянуть JetBrains MPS. Это весьма оригинальная вещь. В компании, где пишут среды разработки для мейнстримных языков программирования, зародилась идея создания IDE для создания IDE для создания DSL. По качеству аналогичных мейнстримным. С автодополнениями, рефакторингами, удобными отладчиками. Сами посудите, какой тут может быть лисп. В лиспе отсутствует культура автодополнений и рефакторинга, не развит статический анализ кода, зато повсюду кошмарные скобки. Лисп не годился. Пара вещей, однако, была заимствована из него: отказ от синтаксиса и макросы. Первое было даже не просто заимствовано, а доведено до абсолюта. В MPS нет ни парсера S-выражений, ни какого-либо другого парсера. Потому что в MPS нет кода. Редактор MPS работает не с кодом, а непосредственно с экземпляром метамодели. В целях облегчения перехода разработчиков на данную технологию редактор напоминает текстовый, декорируя и отображая дерево так, что оно выглядит как код, но им не является. Инструментов для импорта кода MPS не предоставляет (за исключением кода на Java). Что касается макросов для кодогенерации в MPS, то они там завязаны на строгую систему типов, что позволяет автоматически делать статическую проверку типов для создаваемого DSL.

Те, кто говорят, что MPS это переизобретение Лиспа, неправы. Скорее, MPS — это скачок к визуальному метапрограммированию будущего. Что не означает, однако, что этот скачок удачный. Время покажет. Возможно, молодое поколение будет очаровано визуальной средой MPS и автодополнениями. С другой стороны, им может помешать изолированность MPS от мира текстовых программ, т.к. сейчас практически все языки текстовые. Их также может отпугнуть тотальная бюрократизация всего процесса программирования (что неудивительно при хост-платформе Java). В общем, выбор делать им, а мы идём дальше, рассматривая тот случай, когда вам нужен именно текстовый DSL, со своей уникальной грамматикой.

Итак, вы желаете реализовать настоящий DSL. С транслятором проблем не будет — связка lex+yacc, портированная, кажется, на все платформы в мире, уже лет 40 выполняет задачу автоматического построения парсеров. Для грамматик, которым не хватает yacc, есть другие инструменты. Но отладчик и IDE придётся писать самостоятельно. Если только не... найти хост-язык с настраиваемой грамматикой и взять существующую IDE для него. Если она не сломается от введения новой грамматики. Фактически, получится EDSL, но без ограничений на синтаксис, которые накладывались бы нерасширяемым хост-языком. Этот подход называется «extensible programming»; он был довольно популярен в 1960-х, потом заглох, и ожил только в XXI веке. Поэтому живых языков с настраиваемой грамматикой не очень много.

Forth — старейший из таких языков. Отличается тем, что «своей» грамматики практически не имеет. Таков же его преемник Factor. Программирование на Forth, однако, может оказаться не таким простым.
Common Lisp отметился и здесь. Помимо defmacro, которые используются для создания «скобочных» EDSL, о которых было сказано выше, в CL есть т.н. reader macros, которые позволяют изменить поведение reader-а, т.е. расширить синтаксис. Чтобы не конфликтовать со стандартным синтаксисом CL, reader macros обычно начинаются с «#», хотя могут начинаться и с любого другого символа. Например, #c(0, 1) — запись мнимой единицы одним из стандартных макросов CL. Есть примеры более развесистых макросов: запуск shell-команд прямо из CL, вызов C-функций, синтаксис для хеш-таблиц, расширенный синтаксис строк, и даже встраивание XML непосредственно в лисповый код. Однако, если, синтаксис вашего DSL конфликтует с синтаксисом S-выражений, то дело может оказаться труднее. В теории, ничто не мешает изменить стандартный reader на собственный, но как это будет на практике, и как на это отреагирует ваша IDE (например SLIME), пока не ясно. Похоже, никто серьёзно не занимался этим вопросом в CL.
Racket — бывшая PLT Scheme — совсем другое дело. Платформа «из коробки» поддерживает концепцию переключения между разными языками, и позволяет создавать новые языки, используя при этом генератор парсеров в стиле yacc. Есть примеры «не-скобочных» языков, созданных на Racket, по мотивам Prolog, Brainfuck и Algol 60. Среда (DrRacket) и её отладчик работают с этими языками. Более того, DrRacket написан на Racket же, что открывает возможности для модификации среды под язык и распространения её в качестве IDE для вашего DSL. Словом, Racket — очень перспективная платформа для создания DSL, и поддерживается в прекрасном состоянии.
Nemerle — статически типизированный язык для .NET с макросами и расширяемым синтаксисом. Возможности расширения, однако, ограничены. Есть проект Nemerle 2, в котором ограничения будут сняты, и который обещает стать чем-то вроде MPS для .NET (но без отказа от грамматик). Пока только обещает, впрочем.
Bigloo — ещё одна реализация Scheme, с упором на быстродействие. Так же, как и Racket, обладает средствами генерации парсеров, и поддерживает макросы, однако не имеет такого удобного механизма переключения языков и создания новых. Кроме того, не факт, что отладчик Bigloo и его IDE (основанное на Emacs) будут нормально работать с новыми языками, ибо, как и с CL, вряд ли кто-то специально занимался этим вопросом, а само собой ничего не делается.
Helvetia — уникальная в своём роде разработка на базе языка Smalltalk, в которой используется то обстоятельство, что вся среда Smalltalk (включая парсер) поддаётся изменению в рантайме. Helvetia — инструмент для произвольного расширения синтаксиса Smalltalk. С сохранением отладки. И даже с подсветкой и автодополнением! Что делает MPS не совсем уникальной средой. Примеры включают SQL, Brainfuck и что-то похожее на CSS. Единственная неприятность — автор Helvetia защитил по ней PhD, ушёл работать в Google и забросил своё творение. Helvetia работает только на Pharo Smalltalk версии 1.1, и не портирована ни на современную версию Pharo (1.3), ни на Squeak. Однако автор иногда что-то делает, всё-таки. Жаль, что кроме него, никто в разработке Helvetia не участвует. Кстати, автор в 2009 г. выбрал в качестве хост-языка Smalltalk (а не Lisp) по причине «однородности» языка и среды. Среды разработки Smalltalk написаны на Smalltalk, а про Scheme или CL такого сказать было нельзя. DrRacket в то время был наполовину написан на C++, и его переписали на чистом Racket только в феврале 2011.

Как видите, в принципе есть инструменты на любой вкус и под любые требования. В наше время создавать DSL стало не только полезно, но и приятно.

Автор признателен LOR-у за подсказки и Ф.А.Новикову за вычитывание черновика.

Горькая правда о Питоне и его Global Interpreter Lock (цитата)

2011-09-20T13:05:00.001+04:00

GIL не уберут никогда. Или, по крайней мере, в ближайший десяток лет. Сейчас никаких работ на эту тему не ведется. Если некий гений предъявит работающую реализацию без GIL, ничего не ломающую и работающую не медленней, чем существующая версия — предложению будет открыт зеленый свет. Пока же «убрать GIL» проходит по части благих, но невыполнимых пожеланий.

В Java и C# никакого GIL нет. Потому что у них иначе устроен garbage collector. Если хотите, он более прогрессивный. Переделать GC Питона, не сломав обратной совместимости со всеми существующими библиотеками, использующими Python C API — невозможно. Сообщество и так уже который год лихорадит в связи с переходом на Python 3.x. Разработчики не желают выкатывать второе революционное изменение, не разобравшись с первым. Ждите Python 4.x (которого нет даже в планах) — до тех пор ничего не поменяется.

Искал работу

2011-09-10T12:49:00.000+04:00

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

Общаться надо с теми самыми, которые (см. выше).

И вы никогда не пожалеете об этом, вне зависимости от своих карьерных планов.

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

Программисты сейчас нужны почти везде, так что для данной профессии «правильный» поиск работы немало расширяет горизонты. В одном Питере, не говоря уже о других городах и странах, делают:

И это только те места, в которых мне ответили. Для полноты следует упомянуть

Софт для фармацевтических компаний и институтов (старое место работы)

Вывод такой: можно выбирать область, которая нравится. Выбор есть. Спасибо сформировавшейся индустрии.

О краткости языка (On the Conciseness of Language)

2011-06-24T04:07:00.014+04:00

Английский язык более ёмкий, чем русский. Каждый русскоговорящий гражданин когда-то узнаёт это в первый раз. Лично я об этом прочёл в 8-м классе в детективе одной современной отечественной писательницы детективов (кажется, в нём же я узнал об асимметричной схеме шифрования с открытым ключом, которая подавалась авторшей как личное изобретение одного из преследуемых милицией злодеев). Впоследствии я не испытывал недостатка в подкрепляющих примерах. Многие английские слова короче своих аналогов на русском, а ещё короче комбинации «прилагательное+существительное». Чего стоят одни только «exit polls» — тележурналисты бросили пытаться их переводить и так и говорят, по-английски. Английский язык гибче и выразительнее, это был очевидный факт.

Шли годы.

Я узнавал больше о языке, и во мне росло сомнение.

Сейчас я убеждён в том, что мнение о ёмкости английского языка по сравнению с русским происходит от недостаточного знания английского. Или русского. Языки по ёмкости не различаются.

Тексты

Часто так бывает: пишет человек письмо или статью на русском, а потом самостоятельно переводит на английский, и второй вариант получается компактнее. Потом оказывается, что у него «is» вместо «is being», «was» вместо «has been», «I will» вместо «I am going to», «for» вместо «in order to», «it’s» вместо «it is» (вариант с апострофом, вообще-то, является разговорным, и допускается только в прямой речи или сильно неформальном письме), артикли забыты в половине мест, и вообще такой текст носитель языка прочтёт лишь изрядно поморщившись, потому что фразы построены неверно. Или ещё бывает наоборот, над английским текстом автор постарается, дабы не уронить лицо, и напишет ясно и лаконично; а в руссском варианте оставит разные там «исходя из вышеизложенного, совершенно очевидно, что».

Тексты, переведённые любителями с английского на русский, тоже зачастую длиннее оригиналов. И большинство их выглядит настолько нелепо, что сразу видно, что это перевод. Читаешь и видишь: по-русски так никогда не написали бы.

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

Так вот: русский вариант содержит 15181 букв и цифр (пробелы и знаки препинания не в счёт), а английский — 16239. Разница в пользу русского, но в пределах статистической погрешности.

Возьмём фрагмент поменьше, из повести Пелевина «Зомбификация», глава «Бульдозер»:

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

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

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

Перевод, выполненный вашим покорным слугой, был отредактирован и заверен расовым носителем британского английского. Перевод точный, ничего не упущено и не добавлено.

Let us picture a village standing on a hill, with some houses being very old and some others designed along up-to-date lines, while the majority is somewhere between the two. A semi-abandoned church stands side by side with an unfinished workers’ club. In some windows, kerosene lamps flicker, while in some others, electric light burns. Barely audible, a balalaika plays, drowned by music from a radio on a street pole. In sum, that is a piece of ordinary life, odds and ends of old and new, twisted around each other in a most cranky way.

Now, let us picture a bulldozer driver who, having overdosed on some brochures or other, has taken the decision to slice away all that backwardness and build up a new village from scratch. So in the middle of a raw October night he sits behind the wheel of his bulldozer and, bit by bit, cuts off the entire top of the hill along with the village and its inhabitants. And now, while the bulldozer is spinning in the mud, leveling out the new building site, something very unexpected happens: the bulldozer suddenly falls into a void and finds itself among half-rotten logs, skeletons of men and horses, some shards and rusty smithers. The bulldozer is caught in a grave. Neither the driver nor the authors of those brochures that inspired him had taken into account that as soon as they wipe away everything that is—in their opinion—obsolete, something deep crops out, something much more ancient.

Human psyche—in exactly the same way—has a lot of cultural layers. If one cuts off the upper layer of the culture, declaring it a pile of superstitions, delusions and class-alien points of view, then the darkness of the unconscious crops out together with some preexistent psychic traits. Everything is successive, yesterday nests into today, like one Russian doll inside another, and whoever takes the liberty of planing away the present in order to paint it with colors of the future, will only fall into a very distant past.

В оригинале 1469 букв, в переводе 1576. Разница опять в пользу русского и в пределах статистической погрешности.

Но это просто примеры. Может быть, есть какое-то теоретическое обоснование ёмкости английского языка перед русским? Мне о таком неизвестно. В английском нет падежей — зато есть частичка «to» и артикли, которые в русском очень редко являются обязательными, а в английском — очень часто. В английском проще словообразование — но при этом жёсткий порядок слов в предложении. В английском нет сложных окончаний — но есть довольно запутанная система «времён». Английский язык аналитический , а русский синтетический — но это ничего не говорит о ёмкости.

Речь

В английской речи допустимы сокращения, такие как «it’s», «I’ll», «you’d», «can’t». С другой стороны, английская речь должна звучать длинно. Чем длиннее, тем вежливее, это закон. В русском для вежливости полезна интонация, обращение на «вы» и перестановка слов — в английском интонация не играет большой роли, «вы» отсутствует, а перестановки слов редки. Когда на русском говорят «[сделайте ч.-л.], пожалуйста», на английском то же самое должно звучать как «could you please [do smth]». Короткое, но вежливо сказанное «нет» переводится как «I don’t think so». И так далее. Короткие фразы уместны в армии, больнице и т.п. местах, где проволочки ни к чему. Бросаться же короткими фразами в бытовом общении — значит быть невежливым (в частности из-за этого хорошо воспитанных русских за границей считают плохо воспитанными).

Софт

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

При желании русский интерфейс можно сделать таким же кратким (например, Cut/Copy/Paste переводить как Режь/Множь/Клей). Это вопрос традиции, а не языка. Сложилась традиция писать длинно, вот и всё.

О плагинах и линковке

2010-12-16T00:42:00.015+03:00

В какой-то момент развития Indigo — кроссплатформенной C++ библиотеки для решения задач химической информатики — мы осознали, что любая нормальная библиотека такого рода должна позволять third-party расширения. Сказано-сделано. Indigo обрела поддержку плагинов. Обёртки на Java, Python и C# также расширяемы, при этом плагин на соответствующем языке является обёрткой бинарного модуля-плагина на C++. Всё это работает на Windows, Linux и Mac OS X. Дальше речь пойдёт о проблемах, с которыми мы столкнулись при линковке бинарных модулей, и о том как эти проблемы решить.

Постановка задачи

Есть библиотека на C++, назовём её «Core». В ней есть какое-то количество классов и некоторый интерфейс на C, который используется для «оборачивания» библиотеки в Java/Python/C# модули.

Есть ещё одна библиотека на C++, назовём её «Plugin». В ней тоже есть классы и C-интерфейс. Plugin имеет доступ к C++ классам Core и её глобальным функциям, тогда как Core не в курсе о существовании Plugin.

Core линкуется в динамическую библиотеку, назовём её libcore. Plugin тоже линкуется в динамическую библиотеку, назовём её libplugin. Эта библиотека не содержит в себе libcore.

Задача 1: libcore должна загружаться в адресное пространство программы на Java/Python/C# при инициализации соответствующей обёртки Core. Тип операционной системы (Windows/Linux/Mac OS X) и «битность» (32/64) должны определяться автоматически, т.е. нужно выбрать из коллекции сборок libcore для всех платформ правильную, и загрузить именно её. Сразу оговоримся, что обёртки поставляются в комплекте со всеми вариантами библиотеки, чтобы таким образом не нарушать «переносимость» и не причинять головную боль разработчикам, которые будут использовать обёртку.

Задача 2: libplugin должен загружаться в адресное пространство программы на Java/Python/C# при инициализации соответствующей обёртки Plugin. Само собой, и в этом случае ОС и битность определяются автоматически. Кроме того, libplugin должна «увидеть» уже загруженную libcore и подцепить из неё нужные C++ классы и глобальные функции.

Решение задачи 1

В Linux и gcc помогут ключи -m32 и -m64, с которыми собирается соответственно 32-битный и 64-битный код. Для кросс-компиляции, т.е. сборки под платформу, не соответствующую той, на которой выполняется компиляция, надо установить пакет gcc-multilib.

В Windows и Visual Studio дело делается установкой платформы Win32 или x64 в свойствах проекта. Чтобы платформа 64 появилась на 32-битных версиях VS, надо при инсталляции VS поставить галочку напротив «x64 Compilers and Tools», ну или доустановить потом отдельно.

На Mac OS X «битность» не является проблемой благодаря технологии универсальных бинарников. Не иначе как для компенсации этого удобства, бинарники, собранные для версии Mac OS X 10.6, не запускаются на 10.5, так что имеет смысл собирать для 10.5 и 10.6 отдельно. Или собирать только для 10.5 и рассчитывать, что они подойдут для 10.6, но мы это не пробовали.

Теперь пара слов о том, как определить платформу на этапе выполнения программы на Java/Python/C# и загрузить нужный модуль libcore.

Java

Узнать тип операционной системы можно с помощью System.getProperty("os.name"). «Битность», соответственно, через System.getProperty("os.arch"). Версия Mac OS X находится в System.getProperty("os.version").

После того, как платформа определена и путь к подходящему бинарнику libcore получен, загрузить бинарник можно вызовом System.load.

Python

Константа os.name равна "nt", если дело происходит на Windows, и "posix", если это Linux или Mac OS X. Последняя отличается тем, что platform.mac_ver() возвращает определённую структуру данных, из которой как раз можно узнать версию системы. Битность можно узнать с помощью platform.architecture()

Загрузку бинарного модуля в Python, как и дальнейшую работу с ним, проще всего осуществлять с помощью ctypes.

C#

Операционная система в данном случае однозначно Windows. (Нет, до Mono мы ещё не добрались.) Битность можно определить, например, проверкой IntPtr.Size. Для вызова C-функций из C# используется DllImport("core.dll"). При вызове любой функции, объявленной с таким атрибутом, CLR попытается загрузить core.dll из системных директорий в память, если библиотека с таким именем ещё не загружена. Поскольку наша core.dll лежит не в системной директории, и вообще существует в двух вариантах (32 и 64 бита), то мы должны загрузить её до того, как будет вызвана любая функция из Core. Для того, чтобы загрузить core.dll из произольной директории, нужно воспользоваться системным вызовом LoadLibrary, который, в свою очередь, доступен через DllImport("kernel32").

Решение задачи 2

Функции, а также методы C++ классов, которые то же самое что функции, в терминологии линковщика называются символами. Символы, которые библиотека «показывает» наружу, называются экспортируемыми символами. Символы, которые библиотека берёт из других библиотек, называются импортируемыми символами. Надо сделать так, чтобы символы libcore, которые используются в libplugin, экспортировались из libcore и импортировались в libplugin. В каждой ОС динамический линковщик работает по-своему, и рецепты соответственно для каждой ОС свои.

Linux

С экспортом и импортом принципиальных сложностей нет. линковщик (ld), который собирает объектные файлы в .so-модуль, все неопределённые (undefined) в библиотеке глобальные символы считает импортируемыми, а все определённые символы считает экспортируемыми (есть возможность экспортировать только избранные символы, но нам это не нужно). Динамический линковщик (который не ld, а часть операционной системы) при загрузке libcore запишет все экспортированные из неё символы, а при загрузке libplugin обнаружит в ней символы, ждущие импорта, и импортирует их в libplugin из libcore.

Есть ещё одна особенность. Символы могут быть помечены импортируемыми «откуда угодно», или импортируемыми из конкретной библиотеки.

Импорт символов из конкретной библиотеки

ld помечает символ импортируемым из конкретной библиотеки если при линковке указать .so-файл, из которого этот самый символ экспортируется. То есть, в libplugin.so будет чётко прописано, что такой-то символ импортируется из библиотеки libcore.so и только из неё. Кроме того, динамический линковщик будет пытаться при загрузке libplugin.so загрузить libcore.so из директорий, записанных в:

Переменной окружения LD_LIBRARY_PATH. При этом, учитывается только значение этой переменной на этапе запуска программы. Фокусы с подменой LD_LIBRARY_PATH по ходу пьесы не работают. Для программ с setuid/setgid LD_LIBRARY_PATH и вовсе игнорируется.
Кэше /etc/ld.so.cache
/lib
/usr/lib

(man ld-linux)

Если libcore.so не будет найдена ни в одной из указанных директорий, то загрузка libplugin.so не пройдёт успешно. Нетрудно понять, что для наших целей такой подход не годится, т.к. libcore мы распространяем в двух вариантах (32 и 64 бита) и обязательно вместе с самой программой, чтобы разработчики на Java и Python не терпели неудобств с непереносимостью своих программ из-за бинарных модулей.

Импорт символов из любой библиотеки

Если в ld при линковке libplugin.so не передавать libcore.so, то он пометит отсутвующие символы как импортируемые, но не укажет откуда именно. Динамический линковщик затем при загрузке libplugin.so не станет пытаться загрузить libcore.so, а попытается найти отсутствующий символ среди всех загруженных на данный момент библиотек (+в самой программе). Конечно, libcore.so будет среди них, т.к. мы инициализировали Core до того, как начали инициализацию Plugin. Всё очень хорошо, но есть ещё одна деталь.

На самом деле, ld перебирает не все загруженные на данный момент библиотеки, а только те из них, которые были загружены с флагом RTLD_GLOBAL (man dlopen). Те библиотеки, которые загружены с флагом RTLD_LOCAL, подходят только для импорта символов конкретно из них (см. предыдущий заголовок). Виртуальная машина Java и её System.load(), что бы вы думали, конечно загружает все библиотеки с RTLD_LOCAL, без вариантов. Но есть обходной путь! Он появился в glibc 2.2 (2000 г.) не иначе как специально для Java: это флаг RTLD_NOLOAD. После вызова System.load("/path/to/libcore.so") можно вызвать (уже не из Java, а из C):

dlopen("/path/to/libcore.so", RTLD_NOLOAD | RTLD_GLOBAL);

и символы из libcore.so, ранее «закреплённые» за libcore.so, станут доступны для импорта по схеме «откуда угодно». Динамический линковщик отдаст их в нужный момент в libplugin. Дополнительная изюминка заключается в том, что вызов dlopen для libcore.so с RTLD_NOLOAD можно оформить в самой libcore.so, в какой-нибудь функции инициализации. Будет работать.

Что касается загрузки .so-файлов в Python, то с ним всё гораздо проще, т.к. ctypes поддерживает произвольные флаги для загрузки библиотек, в т.ч. и RTLD_GLOBAL:

lib = CDLL("/path/to/libcore.so", mode=RTLD_GLOBAL);

Mac OS X

Правила линковки на Mac OS X такие же, как и в линуксе, есть только небольшие различия в терминологии и опциях линковщика. Схема с привязкой символов к библиотеке, описанная в предыдущем разделе, здесь имеет название: two-level namespace (man ld). Альтернативная схема, которая нам и нужна, называется flat namespace. На этапе компиляции libplugin надо выбрать, по какой схеме испортировать в неё символы. Для нас это означает, что надо передать в ld ключ "-flat_namespace".

Использование flat namespace, по замыслу разработчиков, не отменяет необходимости задания в командной строке ld всех зависимых .dylib-файлов (т.е. в нашем случае libcore.dylib). Это странно, но оправдано для более сложных случаев с косвенными зависимостями (indirect dynamic libraries), которые к нашей задаче не имеют отношения. Можно, тем не менее, попросить ld закрыть глаза на неразрешённые зависимости, передав ему ключ "-undefined suppress". В этом случае динамический линковщик будет разрешать их в рантайме, как в Linux.

Трюк с RTLD_NOLOAD | RTLD_GLOBAL в Mac OS X тоже актуален.

Windows

В Windows нет динамического линковщика.

Его там не может быть в принципе из-за отсутствия поддержки position-independent code, но от этого не легче. В Windows есть только загрузчик динамических библиотек (loader), который, мягко говоря, не совсем в курсе про динамическое связывание. Вся работа по динамическому связыванию делается самой загружаемой DLL на этапе инициализации. Компилятор и линковщик (link.exe) должны позаботиться о том, чтобы DLL сделала эту работу правильно. Программист, в свою очередь, должен позаботиться о том, чтобы компилятор и линковщик правильно поняли свою задачу.

Экспортируемые и импортируемые символы

По указанным выше причинам, в DLL не может быть неопределённых (undefined) символов. Никто не проверит на этапе загрузки DLL, какие символы в ней «defined», а какие «undefined». Такого вопроса просто не стоит. Все символы должны быть определены. В том числе и символы, которые импортируются из другой DLL.

Этот парадокс разрешается следующим образом: при компиляции модулей DLL, в которую импортируются символы (в нашем случае plugin.dll) компилятор на месте импортируемых символов создаёт функцию-"прослойку", которая

Загружает в память DLL, в которой находится нужная функция (LoadLibrary("core.dll")). Большая удача, нет мороки с путями. Есди загрузить core.dll из нужной директори заранее (LoadLibrary("\path\to\core.dll")), то plugin.dll не станет искать core.dll в системных директориях, а просто «подхватит» уже загруженную копию.
Получив указатель (handle) на загруженную DLL, ищет в ней нужную функцию (GetProcAddress) и вызывает её с теми параметрами, которые были переданы в неё саму, т.е. в прослойку.

link.exe не догадается сделать такую прослойку для всех C++ функций, которые не определёны в DLL (хотя догадается сделать это для C-функций, слабое утешение). Перед объявлением каждой из C++ функций, которую вы хотите импортировать в plugin.dll, надо писать __declspeс(dllimport).

Более того, link.exe не догадается экспортировать из DLL символы, которые в ней определены. Перед каждой функцией, которую вы хотите экспортировать из core.dll, надо писать __declspec(dllexport). Это касается и C, и C++ функций. При линковке любой DLL помимо собственно DLL возникает маленький файл с расширением .lib — он и содержит вышеуказанные «прослойки» для всех экспортированных функций.

Получается, что одни и те же C++ функции должны объявляться в Core как __declspec(dllexport), а в Plugin — как __declspec(dllimport). Объявляются эти функции в заголовочных файлах, которые одинаково включаются в Core и в Plugin. Самое время воспользоваться препроцессором:

#ifdef _WIN32
#ifdef PLUGIN
#define DLLEXPORT __declspec(dllimport)
#else
#define DLLEXPORT __declspec(dllexport)
#endif
#else
#define DLLEXPORT
#endif

и перед всеми функциями Core, которые нужны в Plugin, писать макрос DLLEXPORT. При сборке plugin.dll надо указать компилятору макрос PLUGIN.

Экспортирование C++ классов

Физически, C++ класс в скомпилированных модулях — это набор его методов, т.е. функций. Экспортирование класса означает экспортирование всех его методов, кроме приватных. Экспорт и импорт классов осуществляется тем же образом, что экспорт и импорт функций. Можно использовать тот же макрос DLLEXPORT, что и для функций.

Написав DLLEXPORT класса, у которого есть суперкласс, или неприватные поля — объекты каких-либо классов, или неприватные методы, возвращающие объекты каких-либо классов, то при компиляции вы заметите следующий варнинг:

warning C4251: *** : class *** needs to have dll-interface to be used by clients of class ***

Это, в принципе, правильное предупреждение. Если Plugin импортирует класс «CoreClass», определённый в Core, то он конечно будет использовать его публичные (public) методы и публичные поля. Или отнаследуется и будет использовать защищённые (protected) методы и поля. Все классы, возникающие в процессе работы с CoreClass, должны быть доступны через импорт так же, как и сам CoreClass. И всех их надо тоже пометить как DLLEXPORT, о том и речь в варнинге C4251. Иначе Plugin ждёт ошибка линковки.

Если бы в проектах Core и Plugin не было бы классов-шаблонов, то на этом бы наше повествование благополучно закончилось. Но шаблоны у нас есть. Нет, сами классы, которые надо экспортировать, не являются шаблонами, но среди их методов есть такие, которые принимают или возвращают объекты шаблонных классов. Вот на тему этих шаблонных классов и возникает C4251.

Можно, конечно, попытаться писать DLLEXPORT при объявлении шаблонов. В простых случаях это даже будет работать. Но на самом деле это лишено всякой логики. Шаблон — это не класс, он никогда не экспортируется. Экспортируется конкретный класс, который создаётся в тот момент, когда компилятор встречает инстанцированный шаблон. Выйдет так, что все классы-экземпляры «экспортируемого» шаблона будут экспортироваться из Core и импортироваться в Plugin. Это хорошо до тех пор, пока Plugin не воспользуется одним из шаблонов Core с параметром, которого нет в Core. (То есть, из Core попросту не экспортируется данный экземпляр шаблона). И даже тогда всё может быть в порядке; но рано или поздно окажется, что компилятор не в состоянии понять, что не надо импортировать данный экземпляр шаблона из Core, а надо его создать. В нашем случае это произошло, когда один «экспортированный» шаблон с неэкспортированным экземпляром инстанцировался в другом, тоже с неэкспортированным экземпляром. Дело закончилось ошибкой вида

error LNK2001: unresolved external symbol "__declspec(dllimport) ..."

Есть ещё один способ обойти C4251, под названием «explicit template instantiation», т.е. явное экспортирование экземпляра шаблона. Он подробно разбирается в этой статье, в применении к STL, с которой кстати приписать DLLEXPORT к объявлению шаблона нет возможности. Код получается немыслимо громоздким, а результаты — неутешительными. В статье отмечен тот факт, что экспортирование шаблонных классов в случае линковки нескольких (независимых друг от друга) DLL, содержащих одни и те же шаблонные классы, приведёт к ошибкам линковки вида

LNK1169: one or more multiply defined symbols found

Да, link.exe, в отличие своего коллеги ld, не умеет определять и отбрасывать дубликаты функций в разных библиотеках.

Короче говоря, экспортировать шаблоны нет смысла и вообще нельзя. Есть два выхода из ситуации с C4251:

Игнорировать, благо это варнинг, а не ошибка. core.dll и plugin.dll просто будут иметь по пачке одинаковых методов для шаблонных классов. Конфликта при загрузке не будет, поскольку классы не экспортированы. Ошибки линковки тоже не будет, если все не-шаблонные классы имеют в своём заголовке DLLEXPORT.
Не экспортировать свои классы, а экспортировать только их методы, с помощью того же DLLEXPORT в объявлении каждого метода. Как ни странно, варнинг при этом исчезает. Странно, потому что опасность-то остаётся. Опасность заключается в том, что core.dll и plugin.dll всё равно будут иметь независимые реализации одних и тех же шаблонных классов; и если окажется так, что plugin.dll была собрана с иной версией этих классов, бинарно несовместимой с той, с которой была собрана core.dll, то они не смогут вместе работать с этими классами. В статье по ссылке выше сказано, что именно это может произойти с классами STL, когда одна библиотека собрана под VS7, а другая под VS8.

Прочие проблемы с Windows

Ещё пара неприятностей, по числу которых Windows и так лидирует с большим отрывом:

Чтобы собрать plugin.dll, надо поставить в проекте Plugin зависимость на проект Core. Однако, если появилась необходимость завести в проектах Plugin и Core конфигурации сборки «Static», и собирать их в plugin-static.lib и core-static.lib, то зависимость останется, и её не убрать. core-static.lib будет вкомпиливаться в plugin-static.lib, вместе со своими глобальными переменными. Проект, который зависит от обеих библиотке Core и Plugin, при сборке обретёт две копии Core, и работать скорее всего не будет из-за наличия двух копий глобальных данных. Придётся создавать отдельные проекты CoreStatic и PluginStatic. Даже тогда, не получится оставить Core и Plugin пустыми и просто поставить им зависимости соответственно от CoreStatic и PluginStatic: при линковке Core и Plugin не будут экспортироваться символы. Придётся дублировать в Core/Plugin и CoreStatic/PluginStatic одинаковые наборы файлов.
В компиляторе VS есть опция /MT, что означает, что рантайм (CRT) будет «вкомпилен» в библиотеку или программу. Это очень удобно, с учётом того что даже в самые современные версии Windows эта CRT не включена! В Windows есть только очень старая версия, а VS линкует с новой, которая доступна для Windows либо в составе VS, либо в виде отдельного пакета. Так вот, опция /MT в случае двух связанных между собой DLL приведёт к ошибке во времени выполнения. Она неизбежно случится, когда например память выделена в одной DLL, а освобождается (или даже копируется) другой DLL. Остаётся использовать опцию /MD и обеспечивать затем присутствие «Redistributable Package» на машине пользователя.

Навигация в мире органических соединений

2010-07-13T18:36:00.019+04:00

Сколько органических соединений вы знаете? А сколько вы знаете лекарств? Каждое лекарство, не считая тех, что производятся из растений, преставляет собой комплект из действующего вещества и оболочки/растворителя, в которой/ом оно проходит свой путь до усваивания организмом пациента. Действующее вещество в лекарственном препарате — это одно конкретное органическое соединение¹. Количество известных органических соединений, которые можно добыть или синтезировать, превышает 30 миллионов, а количество лекарств на рынке — всего несколько тысяч. Создание любого нового лекарства занимает от 10 до 15 лет и является очень дорогостоящим. Расходы на программное обеспечение составляют в этой индустрии (как и почти в любой другой) весьма скромную долю.

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

Роль компьютеров в этом процессе за последние два десятилетия стремительно возросла, и вот почему. Производство лекарственного средства — комплексная задача, в которой есть место пробам и ошибкам.

Представим, что усилиями биологов в организме выявлен «нездоровый» белок, вызывающий болезнь или болезненные ощущения. Дело за малым — найти вещество, которое разрушит или заблокирует белок, не причинив вреда организму в процессе. Затруднение состоит в том, что на эту роль может годиться одна молекула из 30 миллионов. Или ещё не открытая молекула. Современные технологии массового синтеза (т.н. комбинаторная, или сочетательная химия) и массовых биохимических опытов (HTS), позволяют за короткие сроки получать сотни тысяч новых молекул и гигабайты экспериментальных данных.

Опишем карьеру лекарственного вещества от конца к началу. До того, как попасть на прилавки аптек, лекарство должно пройти клинические испытания (clinical trials) на пациентах, под присмотром врачей. Это представляет определённый риск, поэтому до пациентов доходят лишь немногие вещества, прошедшие доклинические тесты (preclinical testing) на животных. Их тоже берегут, поэтому доклиническим испытаниям предшествуют массовые опыты на отдельных живых клетках (in vitro, лат. «в стекле», т.е. в пробирке). Но и в пробирки не бросаются все молекулы подряд. Люди должны выбирать нужные (перспективные для лечения данной болезни) вещества и отбрасывать заведомо неподходящие, и без компьютера им этого не сделать². На самом деле, и с ним не очень удобно. Эффективная система навигации по химическим содинениям пока ещё не создана; и о перспективах создания таковой сейчас пойдёт речь³.

Поиск химических соединений в базах данных

Состояние систем поиска химических соединений в наши дни, увы, примерно соответствует состоянию поисковых систем во всемирной паутине в 90-е годы⁴. Да, именно так. Примитивные алгоритмы поиска (и поиск ведётся далеко не по всем имеющимся источникам); весьма вялая поддержка языковой грамматики; никакого ранжирования результатов.

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

Например, амфетамин является подструктурой мезокарба, и оба препарата подавляют реакцию обратного захвата дофамина (dopamin reuptake) в мозге, что ведёт к повышению активности. Но мезокарб, в отличие от амфетамина, не вызывает тахикардии и повышения артериального давления.

Амфетамин и мезокарб

Вообще говоря, нередко случается так, что добавление или удаление небольшого фрагмента идёт молекуле (точнее, пациентам) на пользу. Чем добавлять и удалять всевозможные фрагменты вручную, проще запустить поиск по базе данных и найти все молекулы, содержащие данную как подструктуру или все молекулы, содержащиеся в данной. Соответствующие виды поиска называются «подструктурный поиск» (substructure search) и «надструктурный поиск» (superstructure search).

Подструктурный поиск в сервисе Bingo с амфетамином в качестве запроса.

Более общий критерий структурного сходства молекул основан на количестве различных фрагментов, которые присутствуют одновременно в обеих молекулах. Поиск молекул по такому критерию назывется поиском по сходству (similarity search).

Салициламид и ацетилсалициловая кислота — схожие по химическим свойствам соединения, использующиеся в медицине. Последнее более известно под названием «аспирин».

Найденные в базе данных молекулы не очень интересны сами по себе; они интересны в контексте. В каких медицинских и химических статьях упомянуто данное соединение? Есть ли на него патент? Представлено ли оно в коммерческих каталогах? Известны ли его свойства, такие как растворимость, кислотность, токсичность, внутренняя абсорбция и другие? Известна ли химическая реакция его синтеза? Доступны ли исходные компоненты этой химической реакции? На эти вопросы и на многие другие должна давать ответ система поиска.

Перечислим наиболее популярные поисковики химических соединений:

PubChem — база данных из 27 миллионов соединений с богатыми возможностями для поиска: по номеру, по названию, по структурной формуле, по подструктуре и по сходству. Химические свойства также можно задавать в качестве дополнительных критериев поиска (например, ограничиться только молекулами, молекулярная масса которых не превышает 120). Базу постоянно пополняют более 80 организаций.
ChemSpider содержит 25 миллионов соединений и имеет важное отличие от PubChem: добавлять молекулы и обновлять информацию о них здесь могут не только избранные организации, но и простые пользователи. Вместе с последними, список источников ChemSpider составляет почти 300 пунктов. Поиск соединений в ChemSpider не имеет такого количества опций, как в PubChem; в частности, отсутствует поиск по сходству.
eMolecules — компиляция из 7 миллионов соединений, собранных в 150 коммерческих каталогах. Возможности поиска минимальны; никакой информации о соединениях, кроме ссылок на каталоги, сайт не показывает. Это скорее платформа для продавцов химических веществ, нежели поисковая система для исследователей.

Поиск химических соединений по научным публикациям.

Пионерами поиска в научных работах по химии были создатели химической реферативной службы (Chemical Abstracts Service, CAS), существующей с 1907 года. В этой службе ведётся учёт всех известных химических соединений. Тысячи людей в течение десятков лет вручную составляют библиографические справки и заполняют базу данных SciFinder, отдельного продукта CAS для поиска публикаций. Аналогичная база данных, поддерживаемая издательством Elsevier, называется «Crossfire Beilstein». Сервисы PubChem и ChemSpider также выдают пользователю вместе с каждой найденной молекулой список публикаций, к которым данная молекула может иметь отношение; но возможности для поиска собственно публикаций в этих сервисах не очень развиты.

SciFinder

Как же, наконец, отправить на отдых тысячи «индексаторов», от рассвета до заката читающих статьи и заполняющих библиографические базы? Эта задача несколько сложнее, чем найти слово «парацетамол» по текстам статей. Во-первых, само вещество может иметь несколько названий (пример альтернативного названия парацетамола — «N-(4-гидроксифенил)ацетамид»). Во-вторых, лекарство, содержащие это вещество, может упоминаться под разными торговыми марками (в данном случае «Панадол», «Эффералган» и десяток других). В третьих, вещество может быть не написано, а нарисовано в статье. В растровом виде (в старых отсканированных статьях), или в векторном (начиная с 90-х годов). Программы по автоматическому распознаванию рисунков с молекулами сегодня находятся в плачевном состоянии. Вот наиболее известные из них:

CLiDE канадской фирмы SimBioSys
OSRA — проект с открытыми исходниками нашего соотечественника, работающего в США
ChemoCR— проект Марка Циммермана из института Фраунгофера в Германии

CLiDE — наиболее развитая программа из перечисленных, но она нередко ошибается, требует вмешательства человека и «не знает» многих особенностей молекул. OSRA активно развивается, но обладает на данный момент худшим качеством распознавания. ChemoCR, похоже, находится в перманентной закрытой разработке: эту программу никто никогда не видел, тем не менее доступно немалое количество публикаций по алгоритмам, используемых в ней. Указанные программы ещё менее пригодны к распознаванию более сложных химических объектов, как-то: химических реакций, таблиц с заместителями. Комбинированный семантический анализ текста и рисунков (например, «молекула на рис. 10a имеет показатель LD50 равный 5.6 г/кг для взрослых крыс») вообще нигде не реализован.

Планирование синтеза

Схема синтеза химического соединения представляет собой цепочку химических реакций.

Многоступенчатая реакция синтеза парацетамола

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

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

Перегруппировка Брука

Перегруппировка Кляйзена

Благодаря этому обстоятельству, значительно увеличивается разнообразие синтезируемых веществ, и в то же время усложняется поиск. Вкупе с «многоступенчатостью», планирование синтеза становится сложной задачей. В некоторой степени эта задача решена в сервисе Reaxys, который, увы, доступен только по подписке.

Reaxys

Заключение

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

В настоящий момент наиболее перспективная система, которая может в будущем стать «Гуглом и Википедией» химиков — это ChemSpider. Её создатели явно принимают в расчёт ключевые элементы успеха глобальных сервисов: кросс-платформенность (работает через броузер и даже с мобильных устройств), доступность для каждого, богатые возможности, «дружба» с многими другими сервисами (включая PubChem), право пользователей публиковать свой контент. ChemSpider имеет недостатки, как общие для индустрии, так и свои собственные, но движется в правильном направлении.

ChemSpider

Попытки создания химических поисковиков также предпринимались и предпринимаются в стенах фармацевтических компаний, для внутреннего пользования. Сказать о них нечего, кроме того, что любая ценная информация рано или поздно выходит на свет, и там, находясь в общем доступе, постепенно очищается и повышается в качестве; а информация «только для своих» обречена стать бесполезной. Когда вы в последний раз находили что-нибудь дельное в локальной сети своей организации?

Благодарности

Автор признателен Н. Велецкому и Д. Лушникову за ценные замечания по тексту статьи.

Сноски

¹ В редких лекарствах их два, например в бисептоле.

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

³ На прочих стадиях роль вычислительных машин не менее важна; однако возникающие там задачи лежат за рамками данной статьи.

⁴ (до появления Google). Тогдашних «королей» информационного поиска (Altavista, Lycos, Rambler) мало кто помнит; в том числе оттого, что они были практически бесполезны.

⁵ Взаимодействие молекулы с белком тоже можно моделировать на компьютере. Этому посвящена отдельная область вычислительной химии под английским названием «docking».

Примеры неудовлетворительной работы OSRA

(Картинки выложены по просьбе Игоря в комментариях). На первых двух и на последней OSRA не выдаёт никакого результата, на 3-й, 4-й и 5-й выдаёт неверный результат.

Symbolic Integration

2010-05-30T15:13:00.024+04:00

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

Классы функций одной переменной

Чем шире класс функции, тем сложнее брать интеграл. Например, интегрирование полиномов одной переменной

p(x) = a_n xⁿ + ... + a₁ x + a₀

не составляет никакого труда. Уже некоторую сложность представляет интегрирование рациональной функции

r(x) =

a_n xⁿ + ... + a₁ x + a₀

b_m x^m + ... + b₁ x + b₀

Если степень числителя n меньше степени знаменателя m, и коэффициенты лежат в поле вещественных чисел, то интегрирование прозводится следующим образом: знаменатель раскладывается на множители вида (x - x_i)^k_i и (x² + b_j x + c_j)^l_j, где каждый x_i — корень кратности k_i, а b_j и c_j задают пару сопряжённых комплексных корней кратности l_j. Затем методом неопределённых коэффициентов дробь r(x) раскладывается на сумму конечного количества дробей вида

A_i

(x-x_i)^k_i

B_j x+C_j

(x² +b_jx + c_j)^l_j

Для каждого из трёх видов слагаемых (трёх, т.к. дробь с B_jx + C_j разбивается на отдельные слагаемые с B_jx и C_j) интеграл находится с помощью формул из справочника. В этих формулах встречаются логарифмы, радикалы, модули и арктангенсы, поэтому интеграл рациональной функции в общем случае не является рациональной функцией.

Если степень числителя n больше или равна степени знаменателя m, то мы можем разделить числитель на знаменатель и получить сумму полинома и «правильной» дроби. Если нас интересуют функции с комплексными коэффициентами, то всё делается точно так же, как и с вещественными, с тем отличием, что квадратичные члены из разложения знаменателя будут упразднены.

Кажется, что интегрирование рациональных функций — уже чисто техническая задача? Это не совсем так. Если степень многочлена больше 4, то его корни в общем случае не записываются в радикалах. Это доказал Абель в 1826 г. Например, вещественный корень уравнения «x⁵ + x + a = 0» невозможно записать, пользуясь арифметическими операциями и операцией извлечения корня.¹

Числа, являющиеся корнями полиномов с рациональными коэффициентами, называются алгебраическими числами. Они приводят нас к обобщению класса рациональных функций — алгебраическим функциям.

Алгебраическая функция y от переменной x задаётся неявным образом, через полином от x и y:

p_n(x) yⁿ + ... + p₁(x) y + p₀(x) = 0

Для примера преобразуем указанное выше уравнение 5-й степени в алгебраическую функцию y от переменной x:

y⁵+y+x=0

Алгебраические числа и функции тоже не являют собой предел выразительности математической записи. Хорошо известны трансцендентные числа (e, π) и трансцендентные функции (экспонента, логарифм, тригонометрические функции), которые невозможно представить через полиномиальные уравнения.

К классу элементарных функций относятся алгебраические функции, экспонента, логарифм и любые их конечные композиции. Подразумевается оперирование над полем комплексных чисел, что означает, что элементарны и все тригонометрические функции, т.к. они выражаются через комбинации e^ix и e^-ix. Обратные тригонометрические функции, соответственно, выражаются через логарифмы. Показательная функция a^x выражается через экспоненту и логарифм: a^x = e^{x ln(a)}.

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

Интегрирование в теории

С рациональными функциями, несмотря на указанные выше неприятности, принципиальных трудностей нет: интеграл всегда существует в виде элементарной функции, и есть процедура, которая его гарантированно найдёт.

С алгебраическими функциями дело обстоит сложнее.

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

Это даёт следующую общую запись для интегрируемых алгебраических функций:

f(x) = v₀'(x) +

m
Σ
i=1

c_i

v_i'(x)

v_i(x)

(1)

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

Гипотезу Лапласа доказал Лиувилль в 1833 г., а ещё через два года он опубликовал доказательство аналогичного факта для некоторого обобщения класса алгебраических функций, т.н. элементарных функций по Лиувиллю. Они имеют форму алгебраических функций, но в роли переменных в них не только x, но ещё конечный набор логарифмов и экспонент от алгебраических функий от x:

y(x) = f(x, z₁(x), ... z_r(x)) — алгебраическая функция от x, z₁(x), ... z_r(x)

z_i(x) = ln(q_i(x)) или exp(q_i(x)), где q_i — алгебраическая функция от x.

Лиувилль показал, что если элементарная (по Лиувиллю) функция имеет элементарную первообразную, то эта первообразная представляется следующим образом:

⌠
⌡

f(x, z₁(x), ... z_r(x)) dx = y₀(x, z₁(x), ... z_r(x)) +

m
Σ
i=1

A_i ln(y_i(x, z₁(x), ... z_r(x)))

Выражаясь менее формальным языком, первообразная функции y — это алгебраическая функция от того, что уже имеется в y, плюс конечное количество логарифмов (с коэффициентами) алгебраических функций того, что уже имеется в y. То есть, принцип Лапласа остаётся в силе.

Результаты Лиувилля, при всей своей значимости, совершенно не помогают в задаче нахождения первообразной, ибо процедуры приведения функции к интегрируемому виду автором предложено не было. Прошло более 80 лет до того, как английский математик Г. Х. Харди... предположил, что такой процедуры не может существовать, и ошибся.

В XX веке новая отрасль математики — дифференциальная теория Галуа — позволила обобщить результат Лиувилля на произвольные элементарные функции и, более того, сделать доказательство конструктивным, т.е. таким, что с его помощью стало возможно получить желанную первообразную. А во второй половине XX века очень кстати подоспели и вычислительные машины, на которых эти конструкции были незамедлительно запрограммированы.

Итак, дифференциальная теория Галуа. Ключевое понятие в ней — это т.н. элементарное расширение поля функций², которое получается последовательным добавлением в него логарифмов, экспонент и алгебраических функций:

ln(f(x)), где f ∈ K
exp(f(x)), где f ∈ K
алгебраической функции, полученной уравнением вида P(f₁(x), ... f_n(x))=0, где f₁, ... f_n ∈ K.

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

Ключевая теорема дифференциальной теории Галуа является обобщением теоремы Лиувилля и говорит о том, что если функция f из поля F имеет первообразную g в поле G — элементарном расширении F, то f записывается в форме (1), где v_i ∈ F, а g соответственно содержит функцию из F и логарифмы функций из F с весами.

Если строить поле F «специально» под функцию f, т.е. подбирать минимальное расширение поля рациональных функций, содержащее F, то станет очевидно, что принцип Лапласа снова не нарушается: первообразная функции f содержит то, что уже имеется в f, а также логарифмы того, что уже имеется в f.

Роберт Риш из Калифорнийского университета в 1969-1970 годах (Харди к тому времени более двадцати лет как не было в живых) опубликовал алгоритм, приводящий любую элементарную функцию к виду (1), или определяющий, что такое приведение невозможно (и следовательно, интеграла как элементарной функции нет). На этом вопрос отнюдь не был закрыт; напротив, началось самое интересное.

Интегрирование на практике

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

Первая реализация алгоритма Риша была выполнена Джоэлом Мозесом в рамках знаменитого «Project MAC» в MIT в 1971 г. Программа под названием SIN интегрировала чисто трансцендентные функции.

Дэвенпорт в 1981 г., основываясь на работе Риша и некоторых глубоких результатах дифференциальной алгебры и комплексного анализа, разработал алгоритм интегрирования чисто алгебраических функций и реализовал его в известной среде символьных вычислений REDUCE-2.

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

Алгоритм Дэвенпорта ещё и обладал большой вычислительной сложностью, что его автор признавал и выражал надежду, что алгоритм можно упростить. Так и произошло: Барри Трагер из MIT в 1984 г. внёс серьёзные улучшения в алгоритм Дэвенпорта. Обновлённый алгоритм обладал гораздо большей практической ценностью и был реализован в математических программах Axiom и Maple.

Решающий шаг к практическому решению вопроса сделал Мануэль Бронштейн в 1990 г, обобщив алгоритм Трагера на произвольные элементарные функции.

В 1998 г. Бронштейн написал монографию по символьному интегрированию, в которой понятным языком изложил лучшие достижения в этой области, начиная с теоремы Лиувилля и заканчивая собственными результатами.

Бронштейн был одним из ведущих разработчиков Axiom. Вместе с Трагером он реализовал в Axiom свой алгоритм, но лишь частично. В 2005 году Бронштейн скончался, спустя два года после смерти основателя Axiom Ричарда Дженкса.

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

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

√

x⁴ + 10 x² - 96 x - 71

равна

ln((x⁶+15 x⁴-80 x³+27 x²-528 x+781)

√

x⁴+10 x²-96 x-71

- x⁸ - 20 x⁶ + 128 x⁵ - 54 x⁴ + 1408 x³ - 3124 x² - 10001),

однако в таком виде её находит только Axiom. Прочие пакеты — Mathematica, Maple, Matlab, Maxima, Reduce — в лучшем случае выдают громоздкий ответ с участием эллиптических интегралов, т.е. неспособны выдать ответ в виде элементарной функции.³

Первообразную функции e^arcsin(x), равную ½(√ 1-x² +x)e^arcsin(x), способны найти Mathematica, Axiom и Reduce.

Неопределённый интеграл ∫√arctan(x) dx невозможно найти (или определить его отсутствие) ни в одном из перечисленных пакетов; при этом Axiom выводит наиболее осмысленное сообщение: implementation incomplete (constant residues).

Нерешённые вопросы

Полная имплементация алгоритма Риша-Трагера-Бронштейна ждёт своего автора. Однако, и это ещё не всё: в теории символьного интегрирования тоже остались открытые вопросы.

Пришло время сказать, что алгоритм Риша (даже для чисто трансцендентных функций) не является «честным» алгоритмом.

Дело в том, что в процессе работы алгоритм Риша выстраивает «башню» элементарных расширений поля рациональных функций, с тем чтобы «верхушка» башни содержала подынтегральное выражение. При этом не всегда понятно, готова ли уже «башня» или нужно добавить в неё ещё один логарифм, экспоненту, или алгебраическую функцию. Например, если в подынтегральном выражении встретилась экспонента e^x, она добавляется в поле (происходит элементарное расширение поля функцией e^x). Если при дальнейшем анализе в подынтегральном выражении встречается e^x², то эту функцию также следует добавить в поле, вырастив таким образом «башню» до двух этажей. Но если после этого попадётся функция e^x+x², то алгоритм должен определить, что она принадлежит сформированному на данный момент элементарному расширению, и не наращивать «башню». Да, в описанном случае это несложно сделать; чуть сложнее определить, например, на языке элементарных функций, что arctan(x) = -arctan(1/x). Но в общем случае эта задача очень сложна⁴, и нынешние реализации алгоритма Риша используют лишь эвристики для её решения, которые по определению ненадёжны.

Как указывает Дэвенпорт и следом за ним Бронштейн, при реализации алгоритма можно «сделать вид», что нам известен т.н. базис трансцендентности для поля констант, то есть например считать e и √ 2 алгебраически независимыми. Это значит, что мы принимаем на веру, что нет никакого полинома от e и √ 2 , который был бы равен 0. Такое решение нужно принимать о каждой новой константе, появляющейся в ходе работы алгоритма, которую эвристика не позволяет связать алгебраическим выражением с ранее учтёнными константами. Если полученный базис трансцендентности окажется неверным, это может отразиться на корректности выданного ответа в том случае, если ответ гласит, что «интеграл не является элементарной функцией» (да, это касается и Axiom, о которой выше было сказано противоположное). Если же интеграл найден, его можно считать правильным.

Известным частным случаем задачи об алгебраической независимости является т.н. Constant Problem: определение того, тождественно ли нулю некоторое математическое выражение. Задача тривиально решается для многочленов, но для более широкого класса функций, как показал Даниэль Ричардсон в 1968 г., эта задача неразрешима.

Не всё, однако, так безнадёжно: Ричардсон в набор «элементарных расширений» включил, помимо экспоненты и логарифма, функцию модуля. В оригинале теорема Ричардсона звучит так:

Если есть функция f, получающаяся с помощью сложения, умножения и композиции из синуса, экспоненты и модуля, а коэффициенты f используют рациональные числа, π и ln(2), то задача проверки утверждения «f тождественно равна нулю» алгоритмически неразрешима.

Функция модуля существенна в доказательстве Ричардсона, и есть основания полагать (да и сам автор теоремы надеется), что без неё задача Constant Problem всё таки разрешима, что даёт надежду на создание абсолютно честного алгоритма символьного интегрирования.

И последнее: класс элементарных функций кажется несколько надуманным, не так ли? Например, функция ошибки

erf(x) =

√

⌠
⌡

x

0

e^-t² dt

не является элементарной, как доказал Лиувилль. Но чем она хуже экспоненты и логарифма, которые мы относим к элементарным функциям? На компьютере она может быть вычислена с произвольной точностью, и даже, как экспонента и логарифм, обладает элементарной производной. Эту функцию вполне можно включить в «надэлементарные» расширения функций, так же как и эллиптические интегралы, ∫x^xdx и многие другие. Тема интегрируемости в «надэлементарных» функциях была затронута ещё автором SIN в 1970-х годах, и ныне представляет обширное поле для исследований.

Благодарности

Автор признателен А. В. Демьянову, П. А. Мозоляко и Н. Н. Васильеву за вычитку черновиков этой статьи и высказанные замечания.

Литература

J. Liouville. Premier memoire sur la determination des integrales dont la valeur est algebrique. Journal de l’Ecole Polytechnique, 14:124–148, 1833

J. Liouville. Second memoire sur la détermination des integrales dont la valeur est algebrique. Journal de l’Ecole Polytechnique, 14:149–193, 1833

J. Liouville. Mèmoire sur l’intégration d’une classe de fonctions transcendantes. J. Reine Angew. Math. Bd. 13, p. 93-118. (1835)

G. H. Hardy. The Integration of Functions of a Single Variable, 1916.

R. H. Risch (1970). The solution of the Problem of Integration in Finite Terms. Bulletin of the American Mathematical Society 76 (3): 605–608.

Joel Moses. Symbolic integration the stormy decade. Proceedings of the second ACM symposium on Symbolic and algebraic manipulation (1971) 427-440.

Дж. Дэвенпорт. Интегрирование алгебраических функций, Москва «Мир» 1985.

B. Trager. Integration of algebraic functions. PhD Thesis, MIT, 1984

M. Bronstein. Integration of elementary functions. Journal of Symbolic Computation, Volume 9, Issue 2 (1990). 117-173

M. Bronstein. Symbolic Integration Tutorial. ISSAC'98, Rostock.

Richardson, D. Some Unsolvable Problems Involving Elementary Functions of a Real Variable. J. Symbolic Logic 33, 514-520, 1968.

Сноски:

¹Кстати, это число называется корнем Бринга Br(a), и с его помощью можно записать все комплексные корни более общего уравнения «x⁵ + px + q = 0».

²Формально говоря, дифференциальная теория Галуа оперирует дифференциальными полями характеристики 0, но мы в эти термины погружаться не станем и будем считать по-прежнему, что имеем дело с различными классами функций.

³Проверялись следующие версии программ: Axiom 2010, Mathematica 7, Maple 13, Matlab R2007, Maxima 5.21, Reduce 2009.

⁴Например, до сих пор никто не знает, является ли e + π рациональным числом (хотя известно, что e и π по отдельности — трансцентентные числа). Известно только равенство e^{i π} = -1 и бесконечная дробь Рамануджана, связывающая e и π.

Mark Tarver и Qi

2010-02-21T23:36:00.003+03:00

Qi (произносится «чи») — функциональный язык программирования, с проверщиком типов полным по Тьюрингу, как и в Haskell и C++. Автор (Марк Тарвер, профессор в отставке) при этом утверждает, что его творение затмевает все существующие разработки и останется непревзойдённым навсегда, по причине использования наиболее гибкой нотации для описания типов. К тому же, оно работает поверх Лиспа и разрешает использовать функции на Лиспе.

О практическом применении языка речи не идёт; на вопрос, а что такого есть в мире написанного на Qi, автор гордо отвечает, что сам Qi на себе и написан, не считая вспомогательных библиотек к нему же. Скорее, Qi — исследовательский инструмент для разработки новых систем типов; ну и для саморазвития, конечно.

По части последнего Марк вообще увлечённая личность: в августе прошлого года помпезно попрощался с Qi и вообще с программированием, и уехал в Индию заниматься йогой. В ноябре посетовал, что-де в ашраме туго с интернетом, а в декабре (уже не с такой помпой) оповестил сообщество, что «phase of travels is over», вернулся в Англию и продолжает развивать Qi.

Как тут не пожелать доктору Тарверу всяческих успехов.

Indigo

2009-10-29T01:54:00.008+03:00

Мы открыли сайт с программными продуктами для органической химии, которые разрабатывались с 2004 года. Продукты реализованы на C++ и объединены в тулкит под названием Indigo.

Bingo: картридж (плагин) к СУБД Oracle с реализацией различных видов «химического» поиска молекул и реакций.
Dingo: библиотека для рендеринга молекул и реакций, с обёрткой на C# и command-line утилитой.
Cano: библиотека для подсчёта canonical SMILES — уникального представления молекулы, с обёрткой на C#.
Deco: библиотека и command-line утилита для разложения набора молекул на общую часть и заместители (R-Group deconvolution)
Nucleo: библиотека для работы с нуклеотидными цепочками, с обёрткой на Java.

Поддерживаемые платформы — Windows, Linux, Mac OS X, Solaris на SPARC.

Дистрибутивы и исходники бесплатно выложены под GPL v3. В исходниках, кроме всего необходимого для работы с молекулами и реакциями, можно добыть немало реализаций общих алгоритмов на графах:

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

Краткий перечень этих и других реализованных алгоритмов находится на странице ресурсов.

Мы открыли три публичные почтовые рассылки:

http://groups.google.com/group/indigo-dev — для разработчиков
http://groups.google.com/group/indigo-bugs — для баг-репортов
http://groups.google.com/group/indigo-general — для всего остального

Ещё раз адрес сайта: http://ggasoftware.com/opensource/indigo/.

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

HTML + SVG -> PDF

2009-07-04T20:24:00.009+04:00

Продолжаем тему вики-документации с векторной графикой. Вот у нас есть Dokuwiki с плагином svg_pureinsert, и иллюстрации прекрасно выглядят в броузерах, поддерживающих SVG. Добавив &do=export_html в конец адресной строки документа в dokuwiki, можно получить «чистый» HTML, без элементов управления самой вики. Но когда возникает необходимость преобразовать эту страницу в PDF, то оказывается, что сделать это, не потеряв иллюстрации, практически невозможно. Есть два способа:

Сохранить в PDF прямо из браузера (Firefox 3 это умеет).
Открыть страницу в OpenOffice и сохранить PDF из него.

Если мы хотим добавить в документ оглавление с номерами страниц, то первый способ нам никак не подойдёт. Второй способ имеет особенности, о которых сейчас пойдёт речь.

svg_pureinsert вставляет svg-иллюстрации в <iframe>. Это не единственный способ вставки SVG в HTML, но по случайности — единственный подходящий для OpenOffice; теги <object> и <embed> он не замечает. Есть ещё одна неприятность: когда oowriter открывает HTML-страницу, все такие iframe преобразуются в т.н. «floating frames», в которые помимо самой картинки втиснут интерфейс oodraw:
Чтобы превратить каждую floating frame в обычный embedded object, ссылающийся на тот же svg-файл, надо выполнить следующий макрос на OpenOffice Basic:

Sub ConvertFloatingFrames
  doc = ThisComponent
  found = True

  While found
    found = False
    For i = 0 To doc.getDrawPage().getCount() - 1
      If Not found Then
        obj = doc.getDrawPage().getByIndex(0)
        If obj.getImplementationName() = "SwXTextEmbeddedObject" then
          emb = obj.getExtendedControlOverEmbeddedObject
          url = emb.Component.frameUrl
          size = obj.getSize()
          oText = obj.getAnchor().getText()
          EmbedGraphic(doc, obj.getAnchor(), url, size.Width, size.Height)
          oText.removeTextContent(obj)
          found = True
        End If
      End If
    Next
  Wend
End Sub

Вспомогательный к нему макрос был позаимствован из известной книги про макросы OpenOffice.

Sub EmbedGraphic (doc, anchor, url, width, height)
  shape = doc.createInstance("com.sun.star.drawing.GraphicObjectShape")
  obj = doc.createInstance("com.sun.star.text.GraphicObject")
  doc.getDrawPage().add(shape)

  provider = createUnoService("com.sun.star.graphic.GraphicProvider")

  Dim props(0) as new com.sun.star.beans.PropertyValue
  props(0).Name  = "URL"
  props(0).Value = url

  shape.Graphic = provider.queryGraphic(props())

  obj.graphicurl = shape.graphicurl
  obj.width = width
  obj.height = height
  obj.AnchorType = com.sun.star.text.TextContentAnchorType.AS_CHARACTER

  anchor.getText().insertTextContent(anchor, obj, false)
  doc.getDrawPage().remove(shape)
End Sub

Проверял на OpenOffice.org 3.1. Макрос работает всегда со второго раза, из-за каких-то трудностей с ThisComponent, которые я не знаю как решить. Да, и поддерживаются только самые примитивные SVG. Сторонний фильтр SVG для OpenOffice 2.0 поддерживает формат в большей мере, но при отрисовке embedded-объектов не задействуется, к сожалению.

Graph automorphisms, canonical labeling, nauty

2009-06-12T01:34:00.017+04:00

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

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

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

Проверка изоморфизма двух графов — непростая задача. Она очевидно принадлежит к классу NP, но принадлежность её к классам P или NP-полных до сих пор под вопросом. (В комментариях дана ссылка на алгоритм, возможно решающий эту задачу за полиномиальное время.) Пока что для этой задачи придуман собственный класс сложности в NP, под названием GI. Но пусть даже у нас будет эффективная процедура для проверки изоморфизма графов; в любом случае, если записей в базе — миллион, то на проверку присутствия нового образца уйдут многие минуты.

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

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

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

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

Любой канонический код состоит из (i) определённой схемы кодирования графа и (ii) процедуры переупорядочения вершин. Нас не интересует схема кодирования; это может быть обход в глубину, или в ширину, или развёрнутая в строку матрица смежности, или просто списки вершин и рёбер... как бы то ни было, кодирование графа подразумевает какой-то порядок его вершин. Наша задача — упорядочить вершины так, чтобы результат не зависел от изначального порядка. Это называется каноническая нумерация (canonical numbering, canonical labeling).

Похоже, что пионерами этой задачи являются Арлазаров, Зуев, Усков и Фараджев, написавшие в 1973 году статью «Алгоритм приведения неориентированных графов к каноническому виду». Насколько большую роль сыграли их идеи — это отдельная тема, выходящая за рамки данной заметки (более того, в оффлайн); мы же останемся в реалиях нынешней сетевой эпохи.

Реалии, однако, мало изменились за последние 15 лет. Австралийский профессор Брендан МакКей (Brendan McKay) в 1980-х годах написал статью «Practical Graph Isomorphism» и соответствующий программный пакет под названием nauty. Долгое время никому не удалось превзойти nauty по быстродействию; хотя для некоторых частных случаев более эффективные алгоритмы всё же появляются, например вот, вот. Особого упоминания заслуживают библиотеки bliss (2007) и saucy2 (2008), которые на больших разреженных графах уверенно обгоняют nauty. Но эти алгоритмы, фактически, не более чем nauty с модификациями.

Печально другое: мало кто из программистов сумел хотя бы подойти близко к пониманию того, как работает nauty. Если мы посмотрим на современные программные пакеты, то окажется, что они либо напрямую используют эту библиотеку: Magma, MuPAD, GRAPE, Planarity, Cyberaide, igraph (использует bliss), либо используют более примитивные алгоритмы: OpenBabel, Marvin. В любом случае, об осмыслении nauty речи не идёт. Приятным исключением является InChI, в которой присутствует алгоритм, явно сделанный с оглядкой на nauty. Настоящая популярность к алгоритму МакКея придёт тогда, когда в каждом пакете он будет реализован по-своему.

Перестановки и упорядоченные разбиения

Говоря здесь о разбиениях, мы подразумеваем упорядоченные разбиения множества вершин графа, т.е. представления этого множества вершин виде упорядоченного набора его попарно непересекающихся непустых подмножеств. [a b c | d e] и [a c b | e d] — одно и то же разбиение, но [d e | a b c] от него отличается. Подмножества [a b c] и [d e] называются ячейками (cells).

Если каждая ячейка разбиения π₁ является подмножеством какой-либо ячейки разбиения π₂, то π₁ называется подразбиением π₂, а π₂ — надразбиением π₁. Также говорят, что π₁ мельче π₂, а π₂ крупнее π₁. Мы подразумеваем, что при подразбиении сохраняется порядок ячеек. Например, [a b | c | d e] является подразбиением [a b c | d e] и [a b | c d e], но не [c | a b d e].

Разбиение, в котором все подмножества состоят из одного элемента, называется дискретным (discrete partition). Дискретное разбиение очевидным образом образует перестановку (permutation) вершин. Например, дискретное разбиение [b | c | a | d | e] образует перестановку (b, c, a, d, e).

Разбиение, состоящее из одной ячейки, называется элементарным (unit partition). Любое разбиение является подразбиением элементарного.

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

function AllPermutations(π = [V₀|...|V_k])
   if π — дискретное разбиение:
      yield π
   else:
      выбрать V_i ∈ π : |V_i| ≠ 1
      for v ∈ V_i:
         AllPermutations([V₀|...|{v}|V_i\v|...|V_k])

На этом месте у читателя может возникнуть вопрос: зачем нужны разбиения, если наша цель — перебор перестановок? Да, для перебора всех перестановок не нужно вводить понятие разбиений. Но на самом деле, все перестановки нам не нужны, а нужна одна перестановка — каноническая, которую мы выбираем как «лучшую» среди какого-то класса перестановок (не обязательно всех). Очевидно, что чем меньше этот класс, тем лучше, но есть условие: состав этого класса перестановок не должен зависеть от исходной нумерации вершин. Именно здесь нам поможет идея разбиений: мы будем не отбрасывать перестановки, а уточнять разбиения, участвующие в переборе.

Годные разбиения

Мы называем разбиение π годным (equitable), если для него выполняется следующее свойство: для любых двух ячеек V₁, V₂ ∈ π (не обязательно различных) и для любых v₁, v₂ ∈ V₁ выполняется равенство d(v₁, V₂)=d(v₂, V₂), где d(v,V) — количество вершин в V, смежных с v. Очевидно, что все дискретные разбиения являются годнымы.

В работе МакКея доказано, что для каждого разбиения π существует единственное его наикрупнейшее подразбиение, являющееся годным. Процедура уточнения (refine) разбиения находит это годное подразбиение. В упрощённом виде она выглядит так:

function Refine(π = [V₀|...|V_k])
   for V_i ∈ π :
      for V_j ∈ π:
         подразбить V_j, сгруппировав элементы v ∈ V_j по d(v, V_i) и отсортировав по возрастанию d(v, V_i)
         заменить V_j в π на результат этого подразбиения, удлиняя цикл по V_i, но не удлиняя цикл по V_j
   return π

Следовательно, чтобы перебрать все годные подразбиения и все происходящие от них перестановки, нам нужно всего лишь вставить вызов процедуры Refine в перебор:

function AllEquitablePermutations(π = [V₀|...|V_k])
   Refine(π)
   if π — дискретное разбиение:
      yield π
   else:
      выбрать V_i ∈ π : |V_i| ≠ 1
      for v ∈ V_i:
         AllPermutations([V₀|...|{v}|V_i\v|...|V_k])

Процесс перебора перестановок можно изобразить как дерево разбиений, которое обходится слева направо. Среди листьев первым при обходе встречается самый левый. Обозначим его ξ.

(Правая половина дерева показана не целиком. Вызовы Refine, которые не уточняют подразбиение, также опущены.)

Сравнения перестановок и автоморфизмы

Наша задача — найти каноническую перестановку множества вершин исходного графа. Для этого нужно обзавестить функцией сравнения перестановок cmp, которая бы определяла, которая из двух «лучше» (или они одинаковые). Функция должна задавать транзитивное отношение, а её результат не должен зависеть от первоначальной нумерации вершин графа. Пример такой функции: по исходному графу G и перестановкам π₁ и π₂ построить графы G₁ и G₂, вычислить их матрицы смежности, и в качестве cmp(π₁, π₂) вернуть результат лексикографического сравнения матриц, развёрнутых в строки. Таким образом, канонической перестановкой будет считаться та, для которой матрица смежности наибольшая; если таких перестановок две и более, то они считаются неразличимыми и в качестве канонической можно взять любую из них.

Какой смысл для нас имеют «неразличимые» перестановки? Пусть cmp(π₁, π₂)=0. Несложно доказать, что в этом случае перестановка γ=π₂^-1∘π₁ (композиция π₁ и перестановки, обратной π₂) является автоморфизмом вершин исходного графа.

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

Есть следующий способ найти генераторы группы автоморфизмов графа: при обработке первого встретившегося дискретного разбиения ξ оно сохраняется. Каждое последующее дискретное разибение π сравнивается с ξ: если перестановка ξ^-1∘π является автоморфизмом графа, то эта перестановка записывается в группу генераторов.

Сокращение перебора 1: автоморфизм ξ^-1∘π

После обнаружения автоморфизма ξ^-1∘π, обход можно «поднять» по дереву до общего предка π и ξ, поскольку поддерево этого предка, в котором находится π, «изоморфно» поддереву, в котором находится ξ, и не содержит новой информации. Строгое доказательство приведено в работе МакКея.

Сокращение перебора 2: автоморфизм ρ^-1∘π

Как было сказано, поиск канонической нумерации — только опция в алгоритме нахождения автоморфизмов. Когда эта опция включена, мы храним ещё одну перестановку ρ, которая является «лучшей» на данный момент (best so far, BSF). При обнаружении первой перестановки ξ мы копируем её в ρ. Каждую последующую перестановку π мы сравниваем с ρ. Если cmp(π, ρ) > 0, то мы копируем π в ρ. Если cmp(π, ρ) < 0, то ничего не делаем. Если же cmp(π, ρ) = 0, то ρ^-1∘π является новым автоморфизмом, и обход можно «поднять» по дереву до общего предка π и ρ.

Сокращение перебора 3: орбиты

Орбита вершины v — это подмножество вершин, в которые может перейти v в результате действия автоморфизмов. Например, на следующем рисунке показаны орбиты вершин графа:

В начале работы nauty каждая вершина принадлежит своей собственной орбите. По мере открывания новых автоморфизмов орбиты увеличиваются, а их количество — сокращается. Например, если найден автоморфизм (a, b, c, d, e) → (b, a, c, e, d), то список орбит из [a][b][c][d][e] становится [a b] [c] [d e]. Если после этого найден автоморфизм (a, b, c, d, e) → (a, c, b, d, e), то список орбит становится [a b c] [d e]

Рассмотрим «линию предков» первого дискретного разбиения ξ. Предположим, мы в процессе обхода дерева вернулись к какому-либо из предков ξ (назовём его ν), чтобы продолжить обход других потомков ν, перебирая другие элементы ячейки V_i. Если рассматриваемый элемент v_k ∈ V_i лежит на одной орбите с уже рассмотренным элементом v_j ∈ V_i, то существует автоморфизм, открытый в процессе обхода более ранних узлов, который переводит v_j в v_k. В работе МакКея доказано, что в этом случае нет смысла рассматривать всё поддерево, произведённое отделением v_k: все листья этого поддерева будут изоморфны ранее открытым листьям, и все автоморфизмы, которые будут найдены при обходе этого поддерева, будут повторять предыдущие.

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

Для всех графов, однако, верно то, что разбиение по орбитам является подразбиением уточнения тривиального разбиения.

Сокращение перебора 4: fix и mcr

С узлами, которые не являются предками ξ, предыдущее сокращение перебора делать нельзя. Для них есть менее сильный, но тоже действенный критерий отсечения потомков. Для применения этого критерия необходимо сохранять информацию о каждом автоморфизме в отдельности (вместо множества орбит, которое накапливает информацию о всех автоморфизмах в совокупности). Для каждого найденного автоморфизма γ запоминаются два множества: fix(γ) и mcr(γ). fix(γ) — это множество вершин, которое при действиии автоморфизма остаются на своих местах. mcr(γ) — это множество вершин, которые являются минимальными по номеру в своих орбитах. Имеются в виду орбиты, составленные по одному автоморфизму γ, а не те, которые используются в предыдущем способе отсечения.

Рассмотрим множество V_i, элементы которого мы перебираем для продолжения обхода дерева из какого-то узла, глубины l. В процессе пути от корня дерева до этого узла l вершин были «зафиксированы», когда мы отделяли их от их ячеек. Назовём множество этих вершин fixed.

В работе МаКея доказано следующее: если fixed ⊂ fix(γ), то можно присвоить в V_i пересечение V_i ∩ mcr(γ) без ущерба для алгоритма. Фактически, речь идёт об автоморфизмах, которые «не затрагивают» вершины, которые мы зафиксировали. Их орбиты можно эксплуатировать так же, как и в предыдущем разделе, что и делается путём пересечения V_i и mcr(γ). Означенная операция выполняется для всех γ, fix и mcr которых мы успели сохранить на данный момент. Следует отметить, что генераторов группы автоморфизмов графа может быть очень много, и сохранять все fix и mcr не всегда возможно. МакКей рекомендует ограничивать количество сохраняемых fix и mcr числом, пропорциональным количеству вершин в графе, с коэффициентом пропорции больше 1 (у него почему-то 50/32).

Алгоритм целиком

В коде имеются глобальные переменные:

getcanon — опция получения канонической нумерации в ρ
gca_first — уровень общего предка текущего узла и ξ
gca_canon — уровень общего предка текущего узла и ρ
orbits — массив индексов орбит; содержит для каждой вершины номер минимальной вершины в её орбите
Ψ — списов посчитанных множеств fix и mcr для найденных автоморфизмов

function AutomorphismSearch(π)
   FirstNode(1, π)

function FirstNode(level, π = [V₀|...|V_k])
   π ← Refine(π)
   if π — дискретное:
      ξ ← π
      gca_first ← level
      if getcanon:
         ρ ← π
         gca_canon ← level
      return level-1
   V_i ← первая ячейка π, в которой больше 1 вершины
   for v ∈ V_i
      if orbits[v] ≠ v:
         continue (сокращение 3)
      π'←[V₀|...|{v}|V_i\v|...|V_k]
      fixed ← fixed ∪ v
      if v — первая вершина в V_i:
         rtnlevel ← FirstNode(level+1, π')
         gca_first ← level
      else:
         rtnlevel ← OtherNode(level+1, π')
      fixed ← fixed \ v
      if rtnlevel < level:
         return rtnlevel
      if level < gca_canon:
         gca_canon ← level
   return level-1

function OtherNode(level, π = [V₀|...|V_k])
   π ← Refine(π)
   if π — дискретное:
      if cmp(π,ξ)=0:
         AddFixMcr(ξ^-1∘π)
         JoinOrbits(ξ^-1∘π)
         return gca_first (сокращение 1)
      if getcanon:
         comp ← cmp(π, ρ)
         if comp=0:
            AddFixMcr(ρ^-1∘π)
            JoinOrbits(ρ^-1∘π)
            return gca_canon (сокращение 2)
         if comp>0:
            ρ ← π
      return level-1
   V_i ← первая ячейка π, в которой больше 1 вершины
   for (fix, mcr) ∈ Ψ:
      if fixed ⊂ fix:
         V_i ← V_i ∩ mcr (сокращение 4)
   for v ∈ V_i:
      π'←[V₀|...|{v}|V_i\v|...|V_k]
      fixed ← fixed ∪ v
      rtnlevel ← OtherNode(level+1, π')
      fixed ← fixed \ v
      if rtnlevel < level:
         return rtnlevel
      if level < gca_canon:
         gca_canon ← level
   return level-1

Детали реализации

Авторская имплементация nauty содержит трюки для увеличения быстродействия и уменьшения расхода памяти:

Для хранения графа и множеств используются битовые массивы
Вся цепочка подразбиений от корня дерева к текущему узлу кодируется всего двумя массивами (lab и ptn). При возвращении к родительскому узлу разбиение восстанавливается функцией recover

Подробности можно узнать в nauty User’s Guide и в коде самой nauty.

Применение

Прелесть изложенного алгоритма в том, что в нём не много завязок на то, что исходное множество вершин — это вершины простого графа. Фактически, можно находить автоморфизмы и каноническую нумерацию для чего угодно, например:

Для ориентированных графов. Никаких изменений в алгоритме не требуется. МакКей в статье упоминает ориентированные графы, и в nauty есть соответствующая опция digraph
Для графов с раскрашенными вершинами. Всё, что требуется — начинать не с элементарного разбиения, а сгруппировать вершины по цветам. Эта опция также описана у МакКея и имеется в nauty
Для графов с раскрашенными рёбрами. Всё, что требуется — изменить функцию cmp так, чтобы она учитывала цвета рёбер. Также, можно более эффективно написать процедуру Refine (уточнение разбиения)
Для молекул со стереохимическими свойствами. Опять же, модификации требуются только в функции cmp

Модификации алгоритма

Не было упомянуто об огромном количестве дополнительных оптимизаций, имеющихся в коде nauty. МакКей признаёт, что у него самого не все они задокументированы. Вот только некоторые:

«Даровые» автоморфизмы (cheap automorphisms, implicit automorphisms), для обнаружения которых не требуется доходить до дискретного разбиения. Работают в nauty только для неориентированных графов (цвета вершин допускаются)
Проверка автоморфизма cmp(π,ξ) может делаться более эффективно без вызова cmp, с учётом того, что ξ никогда не меняется и нас интересует только то, есть ли изоморфизм
Псевдо-канонические коды разбиений, благодаря которым можно выявить отсутствие автоморфизма, не проверяя его явно. Они же используются для предварительного определения знака функции cmp
При выборе ячейки V_i для подразбиения можно применять различные эвристики, с целью сокращения перебора

Рекурсивные функции на Common Lisp

2009-03-31T10:35:00.006+04:00

1. Перебор всех подписков данного списка

(defun for-all-subsets (list func)
(unless list
  (funcall func nil))
(when list
  (for-all-subsets
   (cdr list)
   (lambda (s) (funcall func (cons (car list) s))))
  (for-all-subsets (cdr list) func)))

func — функция одного параметра — вызывается для каждого подсписка.

2. Перебор всех подсписков заданного размера

(defun for-all-subsets-size (list size func)
(if (zerop size)
    (funcall func nil)
    (when list
      (for-all-subsets-size
       (cdr list) (1- size)
       (lambda (s) (funcall func (cons (car list) s))))
      (when (< size (length list-set))
         (for-all-subsets (cdr list-set) size func)))))

func — функция одного параметра — вызывается для каждого подсписка.

3. Перебор всех подсписков, полученных из данного удалением одного элемента

(defun for-all-cuts (list func)
(declare (list list) (function func))
(when list
  (funcall func (car list) (cdr list)))
(when (cdr list)
  (for-all-cuts (cdr list)
   (lambda (elem cut)
     (funcall func elem (cons (car list) cut))))))

func — функция двух параметров — вызывается для каждого элемента и соответствующего подсписка, который получен его удалением из исходного списка.

4. Перебор максимальных по включению подсписков, удовлетворяющих какому-либо условию

(defun for-all-max-subsets (set func)
(if set
    (let ((saved))
      (for-all-max-subsets
       (cdr set)
       (lambda (s)
         (when (funcall func (cons (car set) s))
           (push s saved))))
      (for-all-max-subsets
       (cdr set)
       (lambda (s)
         (or (position s saved :test #'equalp)
             (funcall func s)))))
    (progn
      (funcall func nil)
      nil)))

func — функция одного параметра — получает список и должна возвращать nil, если список не годится. Если для какого-то списка func вернула ненулевое значение, все подсписки этого списка не будут проверяться.

5. Перебор всех циклических перестановок данного списка

(defun for-all-cyclic-permutations (list func)
  (funcall func list)
  (do ((iter (cdr list) (cdr iter))
             (prev list))
      ((not iter))
    (when prev
       (setf (cdr prev) nil)
       (funcall func (append iter list))
       (setf (cdr prev) iter))
       (setf prev iter)))

func — функция одного параметра — вызывается для каждой циклической перестановки.

Примеры:

> (for-all-subsets '(a b c) #'print)

(A B C)
(A B)
(A C)
(A)
(B C)
(B)
(C)
NIL

> (for-all-subsets-size '(a b c d) 2 #'print)

(A B)
(A C)
(A D)
(B C)
(B D)
(C D)

> (for-all-cuts '(a b c d) (lambda (a b) (format t "~a ~a~%" a b)))

A (B C D)
B (A C D)
C (A B D)
D (A B C)

> (for-all-max-subsets
   '(2 10 2 5 4)
   (lambda (x) (if (> (apply #'+ x) 10) nil (progn (print x) t))))

(2 2 5)
(2 2 4)
(10)
(5 4)

> (for-all-cyclic-permutations '(a b c d e) #'print)

(A B C D E) 
(B C D E A) 
(C D E A B) 
(D E A B C) 
(E A B C D)

[Oracle] Построчное хранение данных

2009-01-31T23:59:00.002+03:00

Минимальная единица информации в хранилище Oracle называется блок.

Таблицы хранятся в блоках построчно. Чем меньше суммарный объём полей в записях, тем больше записей помещается в одном блоке.

При чтении какой-либо записи Oracle берёт с диска (или из кеша) весь блок, в котором находится эта запись.

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

Пример на Oracle 11:

create table a (n number, s varchar2(4000));
create table b (n number);
begin
  for i in 1..1000000 loop
    insert into a values(i, lpad('a', 4000, 'a'));
    insert into b values(i);
  end loop;
end;

set timing on;

select sum(n) from a;

    SUM(N)
----------
5.0000E+11

Elapsed: 00:02:04.51

select sum(n) from b;

    SUM(N)
----------
5.0000E+11

Elapsed: 00:00:00.11

Хранения «по колонкам» в Oracle не предусмотрено. Для лучшего быстродействия следует избегать объединения в одной таблице полей, которые могут быть востребованы по отдельности.

practical-common-lisp.{fb2, pdf}

2008-12-07T07:20:00.004+03:00

Перегнал Practical Common Lisp в формат fb2, не без помощи OpenOffice с ooofbtools, а также ручной правки.
Сноски, таблицы, иллюстрации, цитаты и код оформлены правильными fb2-тегами. Книга будет нормально выглядеть на LBook и прочих карманных девайсах.
Скачать можно здесь.
Алсо, pdf-файл с книгой раньше находился на сайте издательства Apress, но почему-то пропал. Здесь лежит копия.

Реверсивный поиск и перебор поддеревьев графа

2008-11-25T02:45:00.020+03:00

Большинство комбинаторных и оптимизационных проблем содержат в себе задачу обхода вершин некоего связного графа. Граф, как правило, имеет большой размер и не задан явно, иначе перебор его вершин не составил бы труда. Известна лишь какая-то начальная вершина; также для каждой полученной в процессе перебора вершины можно узнать список смежных с ней вершин. Задача проста: посетить все вершины графа по одному разу.

Существуют два классических алгоритма для решения этой задачи: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Оба алгоритма требуют, кроме памяти для хранения «фронта» (стека или очереди) вершин, которые будут посещены, дополнительной памяти для запоминания тех вершин, которые уже посещены.

При некотором условии можно написать рекурсивный алгоритм обхода, не требующий запоминания посещённых вершин. Алгоритм был предложен в 1996 году и называется «реверсивный поиск» (reverse search) [1]. Для его работы требуется, чтобы для каждой вершины v графа была определена соседняя вершина f(v), имеющая максимальный «приоритет». f должна быть задана так, чтобы любой путь вида v → f(v) → f(f(v)) → ... заканчивался, и обязательно в одной и той же вершине v^*. Для определённости положим f(v^*)=v^*.

Простейший пример: пронумеруем вершины графа натуральными числами (p(v)) и определим f(v) как вершину, имеющую максимальный номер среди множества nei(v) всех соседей v. Конечно, не любая нумерация будет соответствовать критерию. На множестве V вершин графа функция p должна иметь единственный локальный максимум, он же и глобальный.

Рассмотрим граф T, множество вершин которого совпадает с V, а ребро между u и w есть, когда u=f(w) или w=f(u). Несложно показать, что этот граф будет деревом. На рисунке рёбра дерева обозначены стрелками, ведущими от v к f(v), по возрастанию номера вершины.

Собственно алгоритм реверсивного поиска очень прост:

Выбрать произвольную вершину v
Если v≠f(v), то присвоить v←f(v) и перейти к шагу 1
Положить на стек вершину v
Пока стек не пуст:
1. Снять со стека вершину u
2. «Посетить» u
3. Для каждой вершины w ∈ nei(u):
  - Если f(w)=u, то положить w на стек

Шаги 1 и 2 предназначены для обнаружения корня дерева, а шаги 3 и 4 обходят это дерево в глубину. Обойдя все вершины дерева, процедура обойдёт все вершины исходного графа. Обход дерева делается в направлении, противоположном возрастанию функции p, отсюда название алгоритма.

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

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

(Кроме того, рассматривается модификация алгоритма, допускающая наличие нескольких «локальных максимумов» в графе поиска.)

Мы покажем алгоритм перебора всех поддеревьев произвольного графа G, основанный на реверсивном поиске. Множество вершин V графа поиска соответствует множеству поддеревьев G. Мы будем считать, что между вершинами u и w есть ребро, если u получается из w добавлением или удалением одного ребра из графа G. Допустим, что рёбра графа G как-то упорядочены. Будем считать, что u=f(w), если u получается из w удалением максимального ребра (не считая тех рёбер, после удаления которых получается два дерева вместо одного). Нетрудно понять, что вершина v^* в таком случае будет соответствовать пустому подграфу G.

Небольшой пример: построим граф поиска всех поддеревьев графа из трёх вершин:
Каждый узел графа поиска соответствует одному из поддеревьев нашего графа; пустое поддерево не является исключением.

Направления стрелок соответствуют удалению рёбер с максимальным номером в исходном графе.

Шаги 1 и 2 алгоритма перебора поддеревьев соответствуют шагам 3 и 4 общего алгоритма реверсивного поиска, т.к. известно, что начальное поддерево — пустое и искать его не надо. Кроме того, держать поддеревья на стеке не требуется; можно вместо поддерева класть на стек рёбра исходного графа. Каждое ребро кладётся на стек дважды: первый раз для добавления в поддерево, второй раз для удаления из него.

Для каждого ребра e графа G
- Положить e на стек
S ← пустой граф
Пока стек не пуст:
1. Снять ребро j со стека
2. Если j ∈ S:
  - Удалить j из S
3. Иначе:
  1. Добавить j в S
  2. «Посетить» S
  3. Положить j на стек
  4. Для каждого ребра h графа G, соседнего с одним из рёбер S и не принадлежащего S:
    - S’ ← S + h
    - Если S’ — дерево и если h — максимальное ребро S’, содержащее вершину степени 1, то положить h на стек

Поддерево S’ получается добавлением ребра h к S. «Соседи» S’ в графе поиска — это поддеревья, полученные удалением одного ребра из S’. Поскольку соседи также должны являться деревьями, то из S’ можно удалять только «висячие» рёбра, т.е. такие, которые имеют вершину со степенью 1. S=f(S’), если h является максимальным из всех таких рёбер. Можно сказать, что h должно быть максимальным ребром из всех, которые могли быть добавлены в S' на последнем шаге. В этом и только в этом случае мы переходим к поддереву S'. Это даёт гарантию, что ни одно поддерево не будет посещено дважды. При обходе в ширину или в глубину избежать повторений так просто не получилось бы.

[1] David Avis, Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics 65, pp. 21-46, 1996.

Канонический код дерева

2008-09-07T22:06:00.001+04:00

Канонический код графа (graph canonical code) — это уникальная строка, которая не зависит от порядка нумерации вершин. У изоморфных графов одинаковые канонические коды, у неизоморфных — разные.

Вершины и рёбра графа могут быть снабжены дополнительными метками (цветами). В этом случае канонический код включает в себя цветовые идентификаторы.

Канонические коды графов позволяют избавиться от дорогостоящей процедуры проверки изоморфизма (graph isomorphism), и определять совпадение графов по сравнению строк.

Например, как найти дубликаты в множестве N графов? Вычислить N канонических кодов, отсортировать их и последовательно сравнить. Гораздо выгоднее, чем делать N*(N-1)/2 проверок изоморфизма. Можно сказать, что канонический код — это хеш-код без промахов.

Канонический код может выглядеть по-разному: как матрица смежности, развёрнутая в строку, или как маршрут обхода графа в ширину, или в глубину. Какое представление выбрать, не столь важно. Задача в любом случае сводится к вычислению канонической нумерации вершин (canonical numbering, canonical labeling). Каноническая нумерация — это нумерация (перестановка) вершин графа, гарантирующая, что изоморфные графы будут пронумерованы одинаково. Получив нужную перестановку, уже не составит труда построить канонический код, например, по обходу графа в глубину: начать обход с вершины под номером 1 и при ветвлении выбирать ту вершину, «канонический номер» которой меньше.

Наличие полиномиального алгоритма для задачи канонической нумерации означало бы, что задача изоморфизма графов полиномиально разрешима. На данный момент, для задачи изоморфизма графов полиномиального алгоритма не найдено, но и не доказана NP-полнота (в отличие от известной задачи изоморфизма подграфу, subgraph isomorphism). По некоторым признакам можно предполагать, что она не является NP-полной.

В ряде частных случаев существуют полиномиальные алгоритмы проверки изоморфизма и канонической нумерации. Мы рассмотрим простейший случай: когда граф является деревом.

В книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов» приводится алгоритм для определения изоморфизма двух деревьев (tree isomorphism), работающий за линейное время от количества вершин. На его основе нетрудно составить алгоритм канонической нумерации вершин дерева, работающий за то же линейное время.

Этап 1. Выделение корня

Отрубим от дерева все листья. Получится дерево меньшего размера. Будем повторять процедуру до тех пор, пока не останется одна вершина (center) или две вершины, соединённых ребром (bicenter).

Если осталась одна вершина, мы делаем её корнем и располагаем остальные вершины по уровням, считая от корня:

Если осталось ребро, мы располагаем остальные вершины по уровням, считая от этого ребра, обе вершины которого помещаются на первый уровень:

Мы разделили N вершин на K уровней так, что у каждой вершины на уровне k>1 есть «родитель» из уровня k-1. Вспомним ещё, что вершины и рёбра снабжены цветами. В наших обозначениях вершины будут красные и синие, а рёбра — чёрные и зелёные.

Этап 2. Поуровневая сортировка

Для алгоритма нужно задать условный порядок на цветах. Пусть красный цвет будет старше синего, а зелёный старше чёрного. Введём обобщённый код вершины, состоящий из цветового кода ребра, которое соединяет её с родителем, и из цветового кода самой вершины. Сгруппируем вершины нижнего уровня, имеющие одинаковый обобщённый код, и присвоим каждой группе ранг, соответствующий старшинству цветов. Цвет ребра имеет больший приоритет, чем цвет вершины. Ранг 0 считается самым старшим:

Составим обобщённые коды родителей этих вершин, которые расположены на предыдущем уровне. Кроме цветовых кодов ребра к родителю и самой вершины, включим в обобщённый код отсортированный список рангов её детей. Ранги детей имеют меньший приоритет, чем цветовые коды вершины и ребра:

Повторяем описанную процедуру:

и ещё раз:

Пока не дойдём до уровня 1. В нашем случае на первом уровне одна вершина, поэтому её ранг нулевой, в случае двух вершин на первом уровне нужно сравнить их обобщённые коды и присвоить им ранги 0 и 1 (или 0 и 0).

Этап 3. Нумерация

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

Построение канонического кода

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

Для построения такого кода не нужен даже третий этап предыдущего алгоритма (нумерация). Мы начинаем обход с корня и для каждой посещённой вершины обходим её детей в порядке старшинства. Для определения старшинства детей хватит «внутриуровневых» кодов, полученных на этапе 2.

Анализ сложности

Этап 1, очевидно, требует O(N) операций. Нетрудно также понять, что на этапе 2 мы, двигаясь от последнего уровня к первому, проходим все вершины по одному разу. Затруднения может вызвать только процесс «ранжирования» вершин на уровне, но при использовании поразрядной сортировки он занимает время, пропорциональное количеству вершин, и суммарно по уровням получается тоже O(N) операций. Этап 3 и построение самого кода также занимают линейное время.

Каноническая нумерация в общем случае

Австралийский профессор Brendan McKay написал библиотеку на C под названием nauty. Она предназначена для поиска групп автоморфизмов произвольных графов; одним из её «побочных» результатов является каноническая нумерация вершин.
Nauty работает очень быстро. Цвета рёбер она не поддерживает, но при необходимости всегда можно добавить в граф псевдо-вершины таким образом, что каноническая нумерация получившегося графа без учёта цветов рёбер будет являться канонической для исходного графа.