В последнее время на Хабре зачастило упоминание о Nemerle. Хотите узнать, что это такое и как его едят, а вернее — как с его помощью едят (задачки)?
Попробую показать на простом примере, но для этого вам придется
Прежде всего
Сразу скажу, чего я вам не скажу :)
Я не буду вам рассказывать в подробностях особенности синтаксиса и проч. — любой может самостоятельно прочесть это на http://www.nemerle.org/ и нагуглить подробности. Вкратце, Nemerle — гибридный язык программирования для платформы .net. Гибридный — означает то, что он сочетает свойства императивного ООП и процедурности, cи-подобный синтаксис и гибкость и способности функционального языка.
Я не буду рассказывать об особенностях парадигмы, гигиенических макросах, и о том, как в этом полностью компилируемом языке со статической типизацией менять его синтаксис.
Я не расскажу вам, что Nemerle «не любит» переменные, и что по умолчанию в языке недоступны многие императивные вещи: if, циклы for, return, много чего еще. По правде говоря, их и нет в самом языке — все реализовано
Наконец, я не расскажу о том, что Nemerle с феноменальной скурпулезностью-рулезностью умеет выводить типы объектов — да так, что с# 4.0 отдыхает :)
В общем, это будет плохая статья, потому что я просто расскажу, как красиво решить задачу в функциональной парадигме, воспользовавшись феньками Nemerle. Ну а задачка у нас будет под стать языку — с недавно прошедшего контеста icfp2009. Вернее, ее часть — мы будем писать Orbital VM на Nemerle, в функциональном стиле.
Для тех, кому строки выше сказали мало или почти ничего, привожу ссылку на спецификацию контеста, а также кратко поясню ниже, в чем суть.
Предыдущий контест (за 2008 год) в качестве полигона для запуска решения использовал LiveCD Knoppix, укомплектованный разными «батарейками», чтобы никто не чувствовал себя обиженным — JRE, gcc, ghc (Haskell), CLOS (Lisp), Python. Практика показала, что из-за различий в работе с плавающей точкой не все языки выдавали одинаковые результаты, что вносило определенную трудность, если не сказать больше. Поэтому в текущем году (т.е. в 2009) организаторы выкатили однозначные спеки на VM, сделав которую, можно было бы доводить свое решение задачи.
Задач было 4 группы по 4 варианта (внутри группы задачи отличались начальными условиями, между группами — целями), для каждой из групп задач предлагался бинарничек с байткодом и начальным состояние памяти данных для OVM. После загрузки программы в OVM необходимо было ее сконфигурировать установкой числа (1000+N варианта) на особом входном порту машины и прогнать 1 такт выполнения. А дальше — в полет.
Излагаю своими словами — задача в целом заключалась в том, чтобы читая показания датчиков и управляя серводвигателями спутника, выполнить им «фигуры высшего пилотажа»: вывести его на заданную орбиту; догнать и перегнать чужой спутник
Так как от команд требовался только лог решения (а именно — последовательность команд на серводвигатели с привязкой ко времени), то, в принципе, задачу можно было решить исключительно «в уме»; но, как показала суровая реальность, все команды-победители использовали VM для отладки результатов. (Более того, похоже, что все команды без исключения использовали VM; некоторые, правда, не свою :)).
Подробно о злоключениях разных команд, и кто у кого «утащил» машину, если вы еще не знаете, можно посмотреть тут
Ее мы и будем реализовывать.
За дело
Почитав спеки, можно представить себе в общем виде эту самую Orbital VM (OVM): регистровая машина с пространством памяти данных в 16К, а так же с отдельным 16K адресным пространством под порты I/O (под I и O — раздельно).
Руки так и чешутся набросать цикл, в котором в цикле увеличивается program counter, а результат, вычитанный им из файла программы, разбирается при помощи битовых операций и подается на огромный switch, который обновляет содержимое памяти и регистров.
Все правильно; так можно? Да. Но я предлагаю не торопиться и проследовать по пути ФП-дао, проектируя сверху вниз :)
Итак, рассмотрим состояние OVM в момент T0. После выполнения одной инструкции состояние машины изменится. Таким образом, одну инструкцию OVM для наших целей можно рассматривать как функцию: на входе — состояние машины S, на выходе S*.
Sn+1 = INSTRn(Sn);
Маленькое следствие — если каждая инструкция возвращает новое состояние, то это означает, что мы можем сохранить его в отдельный списочег с отметками времени, чтобы вести историю. Мелочь, а приятно
Соответственно, вся программа для OVM — это поток инструкций, который представлен списком функций-замыканий; чтобы выполнить программу, необходимо вызвать все функции по очереди, начиная с самой первой из списка, передавая в каждую следующую состояние, которое вернула предыдущая. В самую первую функцию мы передадим начальное состояние S0. Математически выражаясь, мы выполняем левую (в прямом смысле) свертку (fold left).
Итак, ближе к коду. На Nemerle, на нем, родимом. Буду краток (с), но с пояснениями.
Определим алиасы типов:
- type INSTR = OVMState -> OVMState;
- type PROGRAMM = list[INSTR] * OVMState;
* This source code was highlighted with Source Code Highlighter.
INSTR — это тип, определяющий функцию, которая принимает на вход состояние OVM, и возвращает OVM.
PROGRAMM — программа для OVM; кортеж, состоящий из: списка инструкций (это поток команд) и начального состояния. Синтаксис '*' как раз и говорит, что эти два типа нужно сцепить в кортеж.
Наша функция Main проста до смеха:
- Main() : void {
- def(instructions, initialState) = load_program("bin1.obf"); // exception
-
- // configure
- vmi_set_problem(1001, initialState);
- def state = exec_one_cycle(instructions, initialState); // exception
- vmi_set_problem(0000, state);
-
- // since that we can read all data
- Console.WriteLine( "x={0}, fuel={1}",
- vmi_get_x(state), vmi_get_fuel(state));
- }
* This source code was highlighted with Source Code Highlighter.
В первой строке (там, где def), кортеж типа PROGRAMM разбивается на поток и начальное состояние, которое возвращает процедура загрузки программы из бинарного файла.
Далее мы устанавливаем номер варианта (1001), выполняем один такт, очищаем регистр варианта (так надо) и выдаем
Функция, исполняющая 1 секунду симуляционного времени, согласилась выглядеть так:
- exec_one_cycle( program : list[INSTR], fromState : OVMState ): OVMState {
- List.FoldLeft(
- program, // <-- кого ?
- fromState, // <-- с чего? (с какого?)
- fun( instruction : INSTR, currState : OVMState ) { // клиент делает execute каждой instruction
- instruction( currState )
- }
- )
- }
* This source code was highlighted with Source Code Highlighter.
Как и договорились, делаем свертку слева. FoldLeft — стандартный метод библиотеки работы со списками в Nemerle.
Здесь fun в 5ой строке — это не потому, что мне стало особенно весело, а конструкция языка Nemerle, определяющая анонимную функцию «по месту». В принципе, можно использовать и синтаксис делегата, но так нагляднее. Слегка.
Обратите внимание на отсутствие return — дело в том, что в Nemerle последнее выражение и есть то, что будет значением, возвращаемым из функции.
Кстати, fun — это тоже макрос из бибилиотеки Nemerle; он позволяет определить функцию и тут же ее возвращает
Из неосвещенного, но важного, осталась структура OVMState. Срываем покровы.
- class OVMState
- {
- public MEM : array[double] = array(16384);
- public OUTS : array[double] = array(16384);
- public INS : array[double] = array(16384);
- public mutable STATUS : bool = false;
- }
* This source code was highlighted with Source Code Highlighter.
No magic. Один момент — если ваша хотеть иметь переменная в Nemerle, то это нужно указать явно (mutable). По умолчанию все readonly, от греха подальше.
Что у нас осталось? Ответ — загрузка программы, и преобразование байткода в список функций (а точнее — замыканий, начиненных конкретными данными каждой инструкции). Я думаю, вы уже поняли, что будет дальше.
- load_program( file : string ) : PROGRAMM {
-
- // многа букаф опущено ну почти без вреда для смысла
-
- // do
- using(stream = File.OpenRead(file)) {
- def frames = read_frames(stream);
- (load_instructions(frames), load_state(frames))
- }
- }
* This source code was highlighted with Source Code Highlighter.
Входной файл (спеки говорят, что он разбит на фреймы) читается по фреймам же, и декодируется. Если не вдаваться в подробности о наличии двух типов байткода (S и D) и проч., и проч., то декодер для D, например, будет выглядеть так, как приведено ниже:
- /// decodes d-type instruction
- defdecode_d_type(addr : int, opcode: DOpCodes, r1: int, r2: int ) : INSTR {
- match(opcode) {
- | DOpCodes.Add => make_add(addr, r1, r2 );
- | DOpCodes.Sub => make_sub(addr, r1, r2 );
- | DOpCodes.Mult => make_mult(addr, r1, r2 );
- | DOpCodes.Div => make_div(addr, r1, r2 );
- | DOpCodes.Phi => make_phi(addr, r1, r2 );
- | DOpCodes.Output => make_out(r1, r2);
- | _ => throw InvalidOperationException(); // exception
- }
- }
* This source code was highlighted with Source Code Highlighter.
Для S-инструкций — аналогично. match — это операция сопоставления с образцом, этакий расширенный switch с мощными возможностями.
Последний штрих — собственно, сами конструкторы замыканий — «make_bla_bla». Для примера — «создаватор» инструкции add — умножение:
- make_add( addr : int, r1 : int, r2: int ) : INSTR {
- fun(s) {
- s.MEM[addr] = s.MEM[r1] + s.MEM[r2];
- s
- }
- }
* This source code was highlighted with Source Code Highlighter.
Т.е. мы создаем замыкание, которое сможет выполнять сложение двух операндов, и возвращаем новоявленную инструкцию. Обратите внимание, что я указал типы функция, что не обязательно — Nemerle их выведет самостоятельно.
На закуску
Некоторое количество сервисного кода пропустил, но надеюсь, мысль была понятна — проектируем сверху вниз, в процедурной манере, которая проще и в простых задачах понятнее, чем огород из ООП. Гибрид ООП с ФП в Nemerle способствует этому, позволяя сосредоточиться на задаче.
Желающим поупражняться с данной OVM и порулить спутником могут быть полезны следующие советы:
— скурить спеки на icfp2009
— оформить OVM в виде класса, подключить к проекту на CSharp, например, и в нем писать стратегию управления.
Весь код из статьи и остальной, который не был приведен, но понадобится, доступен на pastebin.org тут. Скорострельность на штатном ноутбуке (Core2Duo 2GHz) — ~30 000 симуляционных секунд за секунду (симсек/с), т.е. вполне есть возможность с комфортом обкатать алгоритмы управления.
P.S. Как-то так. Приятных полетов. Телеграфируйте с орбиты, если что :)
P.P.S. Едва не забыл. Интереса для реализовал прямую VM (выборка + декодирование инструкций на каждом шаге) на C# — вышло порядка 24000 симсек/секунду. К сожалению, это не значит, что Nemerle такой быстрый (на 20% быстрее) — это значит, что в C# неплохо оптимизированы операции над битами, которые использованы в декодере.