Сохранение типа общего без η-расширения

Question

Что я делаю: я пишу небольшую систему интерпретатора, которая может анализировать файл, превращать его в последовательность операций, а затем подавать тысячи наборов данных в эту последовательность для извлечения некоторого окончательного значения из каждого. Скомпилированный интерпретатор состоит из списка чистых функций, которые принимают два аргумента: набор данных и контекст выполнения. Каждая функция возвращает измененный контекст выполнения:

type ('data, 'context) interpreter = ('data -> 'context -> 'context) list

Компилятор по сути является токенизатором с последним этапом отображения токена на инструкцию, который использует описание карты, определенное следующим образом:

type ('data, 'context) map = (string * ('data -> 'context -> 'context)) list

Типичное использование интерпретатора выглядит следующим образом:

let pocket_calc = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  Interpreter.parse map "path/to/file.txt"

let new_context = Interpreter.run pocket_calc data old_context

Проблема: я хотел бы мой pocket_calc интерпретатор для работы с любым классом, который поддерживает add, sub а также mul методы и соответствующие data тип (могут быть целыми числами для одного класса контекста и числами с плавающей точкой для другого).

Тем не мение, pocket_calc определяется как значение, а не как функция, поэтому система типов не делает свой тип универсальным: при первом использовании 'data а также 'context типы связаны с типами данных и контекста, которые я сначала предоставляю, и интерпретатор навсегда становится несовместимым с любыми другими типами данных и контекста.

Жизнеспособное решение состоит в том, чтобы расширить определение интерпретатора, чтобы позволить его типовым параметрам быть общими:

let pocket_calc data context = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  let interpreter = Interpreter.parse map "path/to/file.txt" in
  Interpreter.run interpreter data context

Однако это решение неприемлемо по нескольким причинам:

• Он перекомпилирует интерпретатор при каждом вызове, что значительно снижает производительность. Даже шаг отображения (превращение списка токенов в интерпретатор с использованием списка карт) вызывает заметное замедление.

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

• Иногда я хочу повторно использовать заданный список карт в нескольких интерпретаторах, будь то сам по себе или добавив дополнительные инструкции (например, "div").

Вопросы: есть ли способ сделать тип параметрическим, кроме eta-раскрытия? Может быть, какая-нибудь хитрая уловка с использованием сигнатур модулей или наследования? Если это невозможно, есть ли способ облегчить три проблемы, о которых я говорил выше, чтобы сделать eta-extension приемлемым решением? Спасибо!

Answer 1

Жизнеспособное решение состоит в том, чтобы расширить определение интерпретатора, чтобы позволить его типовым параметрам быть общими:

 let pocket_calc data context = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   Interpreter.run interpreter data context

Однако это решение неприемлемо по нескольким причинам:

• Он перекомпилирует интерпретатор при каждом вызове, что значительно снижает производительность. Даже шаг отображения (превращение списка токенов в интерпретатор с использованием списка карт) вызывает заметное замедление.

Он перекомпилирует интерпретатор каждый раз, потому что вы делаете это неправильно. Правильная форма больше похожа на это (и технически, если частичная интерпретация Interpreter.run в interpreter можно сделать некоторые вычисления, вы должны переместить его из fun тоже).

 let pocket_calc = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   fun data context -> Interpreter.run interpreter data context

Answer 2

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

Предполагая данный тип для примитивов:

type 'a primitives = <
  add : 'a -> 'a;
  mul : 'a -> 'a; 
  sub : 'a -> 'a;
>

Вы можете использовать полиморфизм первого порядка, предоставляемый структурами и объектами:

type op = { op : 'a . 'a -> 'a primitives -> 'a }

let map = [ "add", { op = fun d c -> c # add d } ;
            "sub", { op = fun d c -> c # sub d } ;
            "mul", { op = fun d c -> c # mul d } ];;

Вы получаете следующий не зависящий от данных тип:

 val map : (string * op) list

Изменить: что касается вашего комментария о различных типах операций, я не уверен, какой уровень гибкости вы хотите. Я не думаю, что вы могли бы смешивать операции над разными примитивами в одном и том же списке, и все же извлечь выгоду из специфики каждого из них: в лучшем случае вы могли бы только преобразовать "операцию над add/sub/mul" в "операцию над add /" sub/mul/div" (поскольку мы противоречивы в типе примитивов), но, конечно, не так много.

На более прагматичном уровне, это правда, что при таком дизайне вам нужен отдельный тип "операции" для каждого типа примитивов. Однако вы можете легко построить функтор, параметризованный типом примитивов и возвращающий тип операции.

Я не знаю, как можно представить прямое отношение подтипов между различными примитивными типами. Проблема в том, что для этого потребуется отношение подтипов на уровне функторов, что, как я думаю, не имеет место в Caml. Вы могли бы, однако, использовать более простую форму явного подтипирования (вместо приведения a :> b, используйте функцию a -> b), построить второй функтор, контравариантный, который, учитывая карту от примитивного типа к другому, будет строить карту от одного типа операции к другому.

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

Интерпретирующие накладные расходы и эксплуатационные характеристики

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

По моему опыту, этот подход обычно не избавляет от накладных расходов на интерпретацию, а скорее перемещает его на другой уровень. Если вы создаете свои замыкания наивно, у вас будет поток анализа, воспроизводимый на уровне замыкания: замыкание будет вызывать другие замыкания и т. Д., Поскольку ваш код синтаксического анализа "интерпретировал" входные данные при создании замыкания. Вы устранили стоимость синтаксического анализа, но, возможно, субоптимальный поток управления остается прежним. Кроме того, замыкания, как правило, затрудняют непосредственное манипулирование: вы должны быть очень осторожны с операциями сравнения, например, сериализацией и т. Д.

Я думаю, что вас может заинтересовать долгосрочный промежуточный "упрощенный" язык, представляющий ваши операции: простой алгебраический тип данных для арифметических операций, который вы построите из своего текстового представления. Вы все еще можете попытаться создать замыкания "заранее" из этого, хотя я не уверен, что производительность намного лучше, чем прямая интерпретация, если представление в памяти приличное. Более того, гораздо проще будет подключить промежуточные анализаторы / трансформаторы для оптимизации ваших операций, например, перейти от модели "ассоциативных бинарных операций" к модели "n-арных операций", которая может быть оценена более эффективно.