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

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

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 также могут войти в игру, но они, как правило, полезны для экзистенциальных типов первого класса, тогда как здесь мы часто используем универсальные типы.

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

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

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

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