TheSlowestLisp В продолжение темы вываливаю еще один мой коротенький проект в открытый доступ: TheSlowestLisp.
В действительности это не LISP, а чудовищный кастрат Scheme, но поскольку большинство людей бесконечно далеки от функционального программирования и не знают что такое Scheme и чем различаются диалекты LISP, я сделал название производным от LISP, что с точки зрения формализма конечно не совсем корректно.
Отличительные особенности реализации:
1. Целью было написать максимально краткую и простую реализацию, не обращая внимания на то «как правильно». Весь проект был написан за вечер.
2. Еще одной целью было интенсивное использование нового стандарта C++11. Он, правда, используется довольно половинчато, т.к. я писал под MSVC2010, а там многие вещи не поддерживаются (из-за этого в коде много некрасивых for; поскольку std::for_each всё равно по сути сменяется новым range-based-for, я решил не использовать именно для него STL).
3. Обозначенные причины делают мою реализацию крайне медленной.
4. Функционал очень сильно кастрирован. Реализация построена таким образом, что расширение её представляется крайне простым занятием, то есть каждый может доточить этот LISP под себя. Исключение составляют пожалуй только макросы и континуации, которые так просто тут не реализуешь (об этом чуть ниже), а так же всякие специальные символы типа ', ` и ,.
5. Во много это переложение Lispy на C++, хотя нельзя сказать, что всё совсем уж такое же — C++ накладывает много своих ограничений на используемый инструментарий, плюс я реализовывал некоторые вещи по-другому.
Собственно перечень доступных функций:
Арифметика: +, - (бинарный), /, *, =.
Пары: cons, car, cdr, null?.
Предопределенная константа: nil.
Выход из REPL: exit.
Специальные формы: if, define (обычный, не MIT), lambda (только одна процедура в последнем параметре, т.е. необходим begin), set!, begin.
Типы данных: целые, вещественные, пары.
Скажу пару слов о быстродействии.
Основная проблема с быстродействием связана с неэффективным внутренним типом данных, который представляет собой разновидность класса variant, только реализованную топорно руками, а внутри везде используются switch-и.
У нормального программиста на C++ сразу должен возникнуть сигнал в бошке: switch — это плохо. На самом деле в данном конкретном случае это действительно плохо, но совсем по другой причине. Дело в том, что во внутреннем union помимо примитивных типов могут лежать так же string, vector и function, а union позволяет хранить их только в виде указателей. Это приводит к излишне частому выполнению операций new и delete, которые сами по себе тяжелы.
Использование объектного полиморфизма (есть интерфейс LispData и унаследованные от него Integer, Float, List и прочие) именно по этой причине было бы в разы эффективнее: вместо указателей можно было бы хранить собственно сами объекты. Доступ до них был бы примерно таким же быстрым, но не приходилось бы постоянно выделять и деаллоцировать память под них. То есть приходилось бы всё равно, но сильно реже.
Дополнительно к этому нужно было бы конечно реализовать свои аллокаторы памяти и сборку мусора, COW-оптимизации, сделать более эффективный класс для пар (сейчас это vector из двух элементов — именно таким образом я поступил, т.к. у меня уже был тип List для синтаксического анализа и я в угоду скорости разработки не стал придумывать что-то новое).
Работа с памятью в общем-то является главным узким местом, хотя дополнительно можно сказать и то, что всё выполнение тут построено на интерпретации конструкций LISP в терминах структур C++. Выполнение на виртуальной машине могло бы быть эффективнее, и опять же из-за памяти: реальных аллокаций в случае виртуальной машины в рантайме не происходило бы вообще, а просто рос бы стек. Но такая реализация уже на порядок сложнее.
Две проблемные возможности, которые реализовать не так просто, это уже упомянутые макросы и call/cc. Первые реализовать принципиально не сложно, но потребуются усилия. Это просто должен быть отдельный код, а не две строчки на функцию, просто в силу самой умности макросов в LISP.
call/cc можно реализовать либо с помощью CPS, что, на мой взгляд, довольно адовая техника, либо на виртуальной машине, используя стеки. И то и другое требует довольно существенной переработки, поэтому я этим заниматься не стал, хотя CPS может быть прикручу.
На этом в общем-то всё. Опять же, может быть кому и сгодится, я сам может быть иногда буду туда еще комитить.