Держать тип универсального без η-расширения

StackOverflow https://stackoverflow.com/questions/4013363

Вопрос

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

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 Типы связаны с типами любых данных и контекста, которые я сначала предоставляю, и интерпретатор становится навсегда несовместимым с любыми другими типами данных и контекстами.

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

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-расширение приемлемым решением? Спасибо!

Это было полезно?

Решение

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

 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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top