УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Использование автоматов для вычислений в комбинаторах

© И.В. Сорокин

Санкт-Петербургский государственный университет информационных технологий механики и оптики

Проектная документация
Исходные тексты

Аннотация

В последнее время существенно возросла популярность функциональных языков программирования (Haskell, OCaml), появилось много гибридных языков программирования (Nemerle, Boo), а в существующие императивные языки программирования (C++, C#) были включены элементы функционального программирования. Однако скорость исполнения кода, написанного на функциональных языках программирования, остается не очень высокой.

Для удобства в статье рассматривается наиболее простой функциональный язык программирования - лямбда-исчисление. Программы, записанные на нем, являются функциями (лямбда-выражениями), а комбинаторы - абстракцией, удобной для быстрого вычисления лямбда-выражений.

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