Pull to refresh

Nemerle и спутник, или ФП для самых маленьких

Reading time 7 min
Views 1.4K

В последнее время на Хабре зачастило упоминание о 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 такт выполнения. А дальше — в полет.

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

Так как от команд требовался только лог решения (а именно — последовательность команд на серводвигатели с привязкой ко времени), то, в принципе, задачу можно было решить исключительно «в уме»; но, как показала суровая реальность, все команды-победители использовали 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, на нем, родимом. Буду краток (с), но с пояснениями.

Определим алиасы типов:
  1. type INSTR = OVMState -> OVMState;
  2. type PROGRAMM = list[INSTR] * OVMState;
* This source code was highlighted with Source Code Highlighter.

INSTR — это тип, определяющий функцию, которая принимает на вход состояние OVM, и возвращает OVM.
PROGRAMM — программа для OVM; кортеж, состоящий из: списка инструкций (это поток команд) и начального состояния. Синтаксис '*' как раз и говорит, что эти два типа нужно сцепить в кортеж.

Наша функция Main проста до смеха:
  1. Main() : void {    
  2.   def(instructions, initialState) = load_program("bin1.obf"); // exception   
  3.  
  4.     // configure
  5.   vmi_set_problem(1001, initialState);    
  6.   def state = exec_one_cycle(instructions, initialState); // exception
  7.   vmi_set_problem(0000, state);
  8.     
  9.   // since that we can read all data        
  10.   Console.WriteLine( "x={0}, fuel={1}",
  11.     vmi_get_x(state), vmi_get_fuel(state));
  12. }
* This source code was highlighted with Source Code Highlighter.

В первой строке (там, где def), кортеж типа PROGRAMM разбивается на поток и начальное состояние, которое возвращает процедура загрузки программы из бинарного файла.
Далее мы устанавливаем номер варианта (1001), выполняем один такт, очищаем регистр варианта (так надо) и выдаем на гора на экран начальное состояние (vmi_set_problem вовсе не доставляет проблем программе, а, напротив, устанавливает на конфигурационном порту нужное значение)

Функция, исполняющая 1 секунду симуляционного времени, согласилась выглядеть так:
  1. exec_one_cycle( program : list[INSTR], fromState : OVMState ): OVMState {
  2.   List.FoldLeft(
  3.     program, // <-- кого ?
  4.     fromState, // <-- с чего? (с какого?)
  5.     fun( instruction : INSTR, currState : OVMState ) { // клиент делает execute каждой instruction
  6.       instruction( currState )
  7.     }
  8.   )    
  9. }
* This source code was highlighted with Source Code Highlighter.

Как и договорились, делаем свертку слева. FoldLeft — стандартный метод библиотеки работы со списками в Nemerle.
Здесь fun в 5ой строке — это не потому, что мне стало особенно весело, а конструкция языка Nemerle, определяющая анонимную функцию «по месту». В принципе, можно использовать и синтаксис делегата, но так нагляднее. Слегка.
Обратите внимание на отсутствие return — дело в том, что в Nemerle последнее выражение и есть то, что будет значением, возвращаемым из функции.

Кстати, fun — это тоже макрос из бибилиотеки Nemerle; он позволяет определить функцию и тут же ее возвращает

Из неосвещенного, но важного, осталась структура OVMState. Срываем покровы.
  1. class OVMState
  2. {
  3.   public MEM : array[double] = array(16384);
  4.   public OUTS : array[double] = array(16384);
  5.   public INS : array[double] = array(16384);
  6.   public mutable STATUS : bool = false;
  7. }
* This source code was highlighted with Source Code Highlighter.

No magic. Один момент — если ваша хотеть иметь переменная в Nemerle, то это нужно указать явно (mutable). По умолчанию все readonly, от греха подальше.

Что у нас осталось? Ответ — загрузка программы, и преобразование байткода в список функций (а точнее — замыканий, начиненных конкретными данными каждой инструкции). Я думаю, вы уже поняли, что будет дальше.
  1. load_program( file : string ) : PROGRAMM {
  2.     
  3.   // многа букаф опущено ну почти без вреда для смысла
  4.  
  5.   // do    
  6.   using(stream = File.OpenRead(file)) {     
  7.      def frames = read_frames(stream);      
  8.      (load_instructions(frames), load_state(frames))
  9.   }    
  10. }
* This source code was highlighted with Source Code Highlighter.

Входной файл (спеки говорят, что он разбит на фреймы) читается по фреймам же, и декодируется. Если не вдаваться в подробности о наличии двух типов байткода (S и D) и проч., и проч., то декодер для D, например, будет выглядеть так, как приведено ниже:
  1. /// decodes d-type instruction
  2. defdecode_d_type(addr : int, opcode: DOpCodes, r1: int, r2: int ) : INSTR {
  3.   match(opcode) {
  4.     | DOpCodes.Add => make_add(addr, r1, r2 );
  5.     | DOpCodes.Sub => make_sub(addr, r1, r2 );
  6.     | DOpCodes.Mult => make_mult(addr, r1, r2 );
  7.     | DOpCodes.Div => make_div(addr, r1, r2 );
  8.     | DOpCodes.Phi => make_phi(addr, r1, r2 );
  9.     | DOpCodes.Output => make_out(r1, r2);
  10.     | _ => throw InvalidOperationException(); // exception
  11.   } 
  12. }
* This source code was highlighted with Source Code Highlighter.

Для S-инструкций — аналогично. match — это операция сопоставления с образцом, этакий расширенный switch с мощными возможностями.

Последний штрих — собственно, сами конструкторы замыканий — «make_bla_bla». Для примера — «создаватор» инструкции add — умножение:
  1. make_add( addr : int, r1 : int, r2: int ) : INSTR {
  2.   fun(s) {
  3.     s.MEM[addr] = s.MEM[r1] + s.MEM[r2];
  4.     s
  5.   }
  6. }
* 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# неплохо оптимизированы операции над битами, которые использованы в декодере.
Tags:
Hubs:
+25
Comments 13
Comments Comments 13

Articles