( Read more... )

Как развернуть список на окамле.

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

Раз все молчат, напишу я. На днях вышел Окамл 4.0, в котором появились GADT. Рассказать о них можно на классическом примере: AST. Пусть у нас есть язычок с целыми числами, которые можно складывать и сравнивать. Результат сложения - целое число, результат сравнения - булев. Есть выражение if, в котором должно быть булево условие и пара выражений ( Read more... )

Решил на июньском конкурсе _darkus_'a испытать в деле язык D, о котором недавно читал книжку Александреску*. Первый вариант, написанный без мыслей об оптимизации (кроме общего выбора алгоритма), работает на моем рабочем Core 2 Quad 59 секунд. Стал пробовать его ускорить и быстро увидел, что почти все время уходит на сборку мусора, т.к. в процессе ( Read more... )

Лемму Йонеды называют самой сложной тривиальной вещью в математике. Сегодня мы попробуем закодировать ее на Окамле и понять ее связь с продолжениями (continuations). Лемма эта из теории категорий, я буду объяснять на пальцах, не слишком строго. В категории у нас есть коллекция объектов (порой очень большая, настолько, что это даже не обязательно ( Read more... )

Сегодня впервые столкнулся с ситуацией, где использование ООП фич Окамла показалось уместным. Понадобилось по-разному трансформировать дерево программы в моем конпеляторе Leo. Например, нужно заменить переменные с заданными именами на заданные выражения. Или заменить везде один оператор на другой. В обоих случаях нужно аккуратно рекурсивно обойти ( Read more... )

Некоторое время назад меня пытались убедить, что Окамл недостаточно хорош для парсер-комбинаторов, потому что стоит попытаться добавить в парсеры состояние, как тут же возникают трудности, связанные с нехваткой полиморфизма. Проблема там вот в чем. Мой вариант простых парсеров не содержал состояния, и парсером там была функция типа char list -> 'a ( Read more... )

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

Итак, получив работающую виртуальную машину, я принялся за написание компилятора снизу-вверх. Первым делом система команд ВМ была описана в виде набора типов:

type dst = RegDest of int | PntDest of int;;
type src = Reg of int | Pnt of int | Val of int;;

type 'loc command =
| Arith of oper * dst * src * src
| Mov of dst * src
| Movb of dst * ( Read more... )

Почти все классические книжки и курсы по компиляторостроению начинаются с приемов разбора текста. И, я смотрю, многие разработчики тоже начинают писать свои компиляторы с парсинга. Не делайте этого! Это имеет смысл, только если разбираемый язык дан свыше каким-нибудь уважаемым божеством, а жрецы уже написали к нему сутры, шастры и кандидатские ( Read more... )