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

[@VoidEx]

Когда я прочёл спеку VM, сразу решил писать на C++, о чём в последствии ни разу не пожалел.
Кода получилось меньше, чем на Nemerle, кстати:
orbit.hpp + orbit.cpp
А дальше этой VM можно воспользоваться из чего угодно.

[@sse]

Это я так подробно расписал просто :) На самом деле в первом рабочем варианте кода получалось ~40 строк вместе с загрузкой из файла.

Еще, в P.S. я упоминал, что на c# у меня так же получилось — выборка/декодирование/исполнение. На Nemerle не так — во время загрузки программы происходит и декодирование, а затем просто из готового списка вызываются замыкания, никакие инструкции во время исполнения программы декодировать уже не надо.

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

[@VoidEx]

В 40 не верю. Одна свёртка + соответстующие типы уже 30; да и я за краткостью не гнался.
Насчёт замыканий, это да, на RSDN была тема про то, как такое решение на OCaml обогнало решение на Си в лоб. Интересно было бы сравнить OCaml и Nemerle, так как их решения в данном случае совпадают.
Кстати, на Nemerle же потенциально возможно грузить файл в compile-time и макросами генерировать код выполнения на самом же Nemerle, а не писать VM. Так не пробовали? По крайней мере такое предлагали для ЛИСПа, но на Nemerle тоже реально. Получается та же кодогенерация, но не в текст, а более прямым методом.

[@sse]

Нет, в самом деле порядка 40-50 строк. Альясы я не считал, enum были представлены как константы, код написан на верхнем уровне вне класса, а вместо класса OVMState юзался кортеж.

Вот так выглядит все декодирование (~30 строк).

decode_instr( addr : int, instr : int ) : INSTR {  
  match(( instr & OP_MASK ) >> OP_SHIFT) {
    | 0x0 => {
      def (op,r1,imm) = (((instr & S_OP_MASK ) >> S_OP_SHIFT) :> SOpCodes, (instr & S_R1_MASK ) >> S_R1_SHIFT, imm = ((instr & S_IMM_MASK ) >> S_IMM_SHIFT) :> ImmOpcodes);
      match(op){
        | SOpCodes.Noop => fun(s : OVMState ) { s; };
        | SOpCodes.Cmpz => match(imm) {    
            | ImmOpcodes.Ltz => fun(s) { s.STATUS = (s.MEM[r1] < 0.0); s }
            | ImmOpcodes.Lez => fun(s) { s.STATUS = (s.MEM[r1] <= 0.0);  s }
            | ImmOpcodes.Eqz => fun(s) { s.STATUS = (Math.Abs(s.MEM[r1] ) < 1e-10);  s }
            | ImmOpcodes.Gez => fun(s) { s.STATUS = (s.MEM[r1] >= 0.0);  s }
            | ImmOpcodes.Gtz => fun(s) { s.STATUS = (s.MEM[r1] > 0.0); s}
          }
        | SOpCodes.Sqrt => fun(s) { s.MEM[addr] = Math.Sqrt(Math.Abs(s.MEM[r1]));s };
        | SOpCodes.Copy => fun(s) { s.MEM[addr] = s.MEM[r1]; s };
        | SOpCodes.Input => fun(s) { s.MEM[addr] = s.INS[r1];s };      
      }
    | _ => {
      def (r1,r2) = ((instr & D_R1_MASK ) >> D_R1_SHIFT, (instr & D_R2_MASK ) >> D_R2_SHIFT);
      match(opcode) {
      | DOpCodes.Add => fun(s : OVMState) { s.MEM[addr] = s.MEM[r1] + s.MEM[r2]; s }
      | DOpCodes.Sub => fun(s : OVMState) { s.MEM[addr] = s.MEM[r1] - s.MEM[r2];s;}
      | DOpCodes.Mult => fun(s) { s.MEM[addr] = s.MEM[r1] * s.MEM[r2]; s }
      | DOpCodes.Div => fun(s) { s.MEM[addr] = if( Math.Abs( s.MEM[r2] ) < 1e-10 ) 0.0 else s.MEM[r1] / s.MEM[r2]; s}
      | DOpCodes.Phi => fun(s) { s.MEM[addr] = if( s.STATUS ) s.MEM[r1] else s.MEM[r2]; s}
      | DOpCodes.Output => fun(s) { s.OUTS[r1] = s.MEM[r2]; s; }
    }
  }
}

* This source code was highlighted with Source Code Highlighter.

Если сравнивать OCalm и Nemerle, то не думаю, что была бы какая-то качественная разница.
Насчет макросов — то, что вы предложили (AST-генерация), более чем реально. Просто в настоящее время отлаживать макросы несколько сложнее по сравнению с обычным кодом в Nemerle, потому я и не пошел этим путем — то решение, что я предложил, и так вполне шустрое.

Кстати, некоторые умельцы на контесте подхачили VM, чтобы считать только положение своего спутника, а не остальных (дабы «отточтить» исключительно собственную траекторию), в итоге VM стала считать в 10 раз быстрее. Вот где оптимизация! :)

[@VoidEx]

Про такой хак не слышал, интересно :)
Слышал, что некоторые реализовывали по формулам из спеки нативный симулятор, но не помню, совпадали ли результаты.

[@Dimchansky]

Я на F# написал компилятор/конвертатор кода виртуальной машины спутника в .NET сборку (фактически один класс на C#).
Сначала я сделал тупую конвертацию в лоб, когда в классе были все нужные массивы памати, входа и выхода.
Например, для первой задачи сгенерированный код получился таким (не приведен код класса, от которого происходит наследование, но он тривиальный).
На моем компе (DualCore Intel Core 2 Duo E8500, 3166 MHz) 10 миллионов шагов (каждый шаг — одна секунда виртуального времени) выполнялись за 10,7695036 секунд, т.е. для первой задачи (266 инструкций в одном шаге) скорость получалась 928'547 виртуальных шагов за единицу нашего реального времени.
После этого я решил, что компилятор не знает, что некторые ячейки памяти фактически являются временными переменными и нигде глобально не используются. Тогда я решил немного оптимизировать кодогенеряцию — просто разделил ячейки памяти на локальные, глобальные и константы, а также отказался от использования массивов для памяти и сам класс ни от кого не наследуется. Новый сгенерированный код выглядит так.
Такая простая оптимизация увеличила скорость в 4,36 раза. :) Теперь для первой задачи 10 миллионов шагов выполнялись за 2,4674865 секунды, таким образом скорость возросла до 4'052'707 виртуальных шагов за единицу нашего реального времени.
Код, которым мерялясь скорость.

[@Dimchansky]

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

[@sse]

Ага, я видел такую штуку, но на С. Могу сказать только «О_о, жестя» :)

[@Dimchansky]

Вариант на C, наверное, должен еще быстрее работать, хотя… тут бабушка надвое сказала. :) Было бы интересно сравнить.

[@kosiakk]

правильно ли я понимаю, что на каждый вызов make_add создаётся новое замыкание?
насколько это дорого? если код хранится отдельно от данных, то получается совсем ничего… правда?

[@sse]

Ага, правильно. Всего создается замыканий по числу инструкций в программе (для первой задачи ~220).
Не знаю, что считать дорогим, поэтому не могу ответить на вопрос, дорого ли это.

[@Vayun]

Список замыканий для этой задачи — первое, что приходит в голову)

У меня тоже все начиналось со списка замыканий (в Питоне), который был потом за 5 минут переделан в компилятор в Питон-код, а еще позднее так же быстро в машинный код с помошью Cython.

На мой взгляд было бы интересней сделать VM задания 2006 года на Немереле)

[@sse]

Это он приходит в голову, если вы пишете в ФП. Для императивщиков куда более привлекательным выглядит прямое решение cycle_on( read->decode->execute ). Вот я и пытался «расширить сознание» :) — в принципе, с последними вещами того же CSharp подобное можно провернуть даже в нем )

До 2006 — еще не добрался =) Кстати, решение 2004 (про VM для муравьев) — идет в samples к Nemerle: там реализован DSL на N-макросах, на котором и описаны стратегии поведения. Кажется, победители так и делали.
Вот это уже не напишеш в CSharp, по крайней мере — пока что.

…

Почитал ваш отчет, порадовался точной аналитике; я делал простой расчет стартового импульса для выхода в зону ± 5-50км + PID-регулятор на конечном участке траектории, доруливающий в заданную траекторию =)