Katahdin

Katahdin
Семантика	императивный, объектно-ориентированный, duck-typed, языково-ориентированный
Класс языка	язык программирования
Тип исполнения	интерпретатор
Появился в	2007
Автор	Крис Ситон (Chris Seaton)
Выпуск	0.2
Система типов	динамическая
Повлиял на	PFront

Katahdin — язык программирования, в котором синтаксис и семантика могут изменяться во время исполнения. Katahdin использует РВ-грамматики и packrat-парсер. Новые конструкции, такие как выражения или операторы, или даже новый язык программирования могут быть созданы с нуля. Единственная реализация языка использует платформу .NET (реализацию Mono).

Введение

Katahdin позволяет вводить новые конструкции также легко, как в обычных языках программирования: можно создавать функции и типы данных.

Например, во многих языках программирования присутствует операция взятия остатка (mod). Если используемый язык программирования не содержит такой операции и не позволяет каким-то образом её перегрузить, то реализация подобной операции выльется в изучение реализации языка, изменение грамматики и сборку нового транслятора. Katahdin позволяет описать операцию взятия остатка в несколько строк:

class ModExpression : Expression {
    pattern {
        option leftRecursive;
        a:Expression "%" b:Expression
    }

    method Get() {
        a = this.a.Get...();
        b = this.b.Get...();
        return a - (b * (a / b));
    }
}

Этот код выполнится во время исполнения программы, и сразу после этого операция взятия остатка станет частью языка. Таким образом, после объявления новой операции, она может быть использована дальше в программе. Katahdin не содержит специальных конструкций, которые не могут быть изменены (даже пробелы и ключевые слова не являются исключением). Если описать все конструкции какого-либо языка программирования подобным образом, то Katahdin превратится в интерпретатор этого языка. Таким образом, Katahdin может быть использован в качестве универсального интерпретатора. Также можно использовать один язык в рамках другого, просто описав оба языка в Katahdin. На сегодняшний момент существуют подобные описания для языков Фортран и Python.

Иногда программист хочет использовать один язык в рамках другого. Например, SQL используется повсеместно в рамках других языков, при этом код на SQL записывается в строках. Katahdin позволяет совместить основной язык с SQL, чтобы тот использовался как часть основного языка. Также иногда возникает желание определить новый оператор во время исполнения. Например, в Java 1.5 был добавлен оператор for-each. Но пока эта реализация языка не была выпущена, программисты не могли использовать эту возможность. Использование Katahdin в этом случае позволило бы программистам использовать эту конструкцию, не дожидаясь следующей версии Java. Реализация этого оператора выглядела бы примерно следующим образом:

class ForStatement : Statement {
    pattern {
        "for" "(" init:Expression ";"
            cond:Expression ";" inc:Expression ")"
        body:Statement
    }

    method Run {
        init.Get...();
        while (cond.Get...()) {
            body.Run...();
            inc.Get...();
        }
    }
}

Грамматика

Описание шаблонов

Грамматики в Katahdin представляют собой измененные РВ-грамматики. Запись очень близка также КС-грамматикам.

Просто текст помещается в кавычки ("текст") и может включать в себя стандартные Escape-последовательности. Диапазон символов может быть выражен при помощи оператора .. : "a".."z". Оператор . соответствует любому символу. Другие структуры обозначаются именами (value).

Последовательность представляется словами, разделенными пробелами: a b c Операторы ? * + переводятся как ноль-или-один, ноль-или-больше, один-или-больше, соответственно. Выражения могут группироваться в скобки для определения приоритета вычисления.

Операторы & и ! проверяют текст, но не убирают его. Оператор & проходит тогда, когда проходит, если выражение подходит. Оператор ! — наоборот.

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

Примеры шаблонов.

Универсальный конец строки:
    "\r" "\n"? | "\n"
Список параметров:
    "(" (Value, ("," Value)*)? ")"
Комментарий в С:
    "//" (!EndOfLine .)*

Рекурсивные шаблоны

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

$Expression\leftarrow Number$

$Expression\leftarrow Expression'-'Expression$

Применим такое определение к выражению: $a-b-c$

Исходя из определения, выражение может быть распознано двояко: $((a-b)-c)$ или $(a-(b-c))$

Неоднозначность пропадает с введением ассоциативности. В данном случае оператор - лево-ассоциативен. Для избежания таких неоднозначностей в Katahdin предусмотрены опции, соответствующие ассоциативности (leftRecursive для левой ассоциативности и rightRecursive для правой):

class Subtract : Expression {
    pattern {
        option leftRecursive;
        Expression '-' Expression
    }
}

Приоритеты

Приоритеты операций определяют порядок, в котором они будут выполнены при вычислении выражения. В математике и большинстве языков программирования операции * и / имеют больший приоритет, чем + и -. Вообще говоря, приоритеты можно описывать просто описывая грамматику, однако добавление новой операции в язык повлечет изменение других правил, причем, если эти правила были описаны в другом модуле, у программиста не будет возможности узнать, какие именно правила нужно менять. Поэтому Katahdin побуждает описывать операции естественным образом, определяя приоритеты потом, при помощи ключевого слова precedence:

class AddExpression : Expression {
    pattern {
        option leftRecursive;
        Expression '+' Expression
    }
}

class SubExpression : Expression {
    pattern {
        option leftRecursive;
        Expression '-' Expression
    }
}

precedence SubExpression = AddExpression;

class MulExpression : Expression {
    pattern {
        option leftRecursive;
        Expression '*' Expression
    }
}

class DivExpression : Expression {
    pattern {
        option leftRecursive;
        Expression '*' Expression
    }
}

precedence DivExpression = MulExpression;
precedence MulExpression > AddExpression;

Достоинства языка

Общая среда исполнения

В настоящее время написание системы на нескольких различных языках довольно затруднено. Для каждого языка требуется своя среда, которую необходимо выбрать, возможно, купить и установить. Каждая среда должна периодически обновляться и дополняться. При смене платформы, все среды должны быть портированы. Katahdin предоставляет единую среду для выполнения кода на различных языках. При смене платформы, должна быть портирована только среда Katahdin.

Простое взаимодействие языков

Взаимодействие между языками, исполняющимися в разных средах исполнения, естественным образом затруднено. Обмен информацией может быть осуществлен посредством создания канала чтения/записи. Доступ к коду (например, к функциям или типам) организовывается ещё сложнее, требуя использование таких инструментов, как CORBA или COM. В программе на Katahdin код и данные свободно разделяются между используемыми языками, не требуя связывания или ввода-вывода.

Пример использования языков FORTRAN и Python в одном исходном файле:

import "fortran.kat";
import "python.kat";

fortran {
    SUBROUTINE RANDOM(SEED, RANDX)

    INTEGER SEED
    REAL RANDX

    SEED = 2045*SEED + 1
    SEED = SEED - (SEED/1048576)*1048576
    RANDX = REAL(SEED + 1)/1048577.0
    RETURN

    END
}

python {
    seed = 128
    randx = 0

    for n in range(5):
        RANDOM(seed, randx)
        print randx
}

Katahdin представляет язык программирования просто как инструмент, не ограничивая программиста в выборе платформы или библиотек. Каждый участок программы, отвечающий за конкретную задачу, может быть реализован на более подходящем языке программирования (в зависимости от задачи, разработчиков и используемых библиотек).

Например, программа на Фортране, предназначенная для вычислений, может плохо справляться с некоторой обработкой текста, требуемой при вводе-выводе. В этом месте лучше использовать более подходящий язык, например, Perl. В программе на Katahdin код, обрабатывающий текст и написанный на Perl, может быть использован в том же файле, что и программа на Фортране.

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

См. также

• seed7 — язык программирования с расширяемым синтаксисом
• Intelib — библиотека классов C++, созданная в качестве инструмента мультипарадигмального программирования.
• CORBA
• Компиляция во время выполнения
• Парадигма программирования

Ссылки

• Официальный сайт
• Growing a Syntax
• Superlanguages: Syntactic and Semantic Supersets of other Languages
• Обсуждение языка на Lambda the Ultimate
• PFront: a language with extensible syntax
• Katahdin: метапрограммирование на грани фантастики, Илья Струков, Хабрахабр
• Статья о языково-ориентированном программировании на RSDN