Можно ли полностью кодировать ML-функторы в.NET (C#/F#)?
Можно ли практически выразить функторы ML с помощью.NET-интерфейсов и обобщений? Есть ли продвинутый пример использования функтора ML, который бросает вызов таким кодировкам?
Резюме ответов:
В общем случае ответ НЕТ. Модули ML предоставляют функции (такие как совместное использование спецификаций через сигнатуры [ 1]), которые напрямую не сопоставляются с концепциями.NET.
Тем не менее, для определенных случаев использования идиомы ML могут быть переведены. Эти случаи включают в себя не только основные Set functor [ 2], но также и функторное кодирование монад [ 3], и даже более продвинутые способы использования Haskell, такие как, наконец, интерпретаторы без тегов [ 4, 5].
Практические кодировки требуют компромиссов, таких как полубезопасные откаты. Ваш пробег будет осторожным.
Блоги и код:
5 ответов
Одной из ключевых особенностей модулей ML является совместное использование спецификаций. В.NET нет механизма, который бы мог их подражать - необходимый механизм просто слишком отличается.
Вы можете попытаться сделать это, превратив общие типы в параметры, но это не может точно эмулировать возможность определения подписи, а затем применить к ней общий доступ, возможно, несколькими различными способами.
По моему мнению, .NET выиграет от чего-то, что имеет такой механизм - тогда оно станет ближе к реальной поддержке разнообразия современных языков. Надеюсь, в том числе более поздние достижения в системах модулей, таких как в MixML, что, на мой взгляд, является будущим модульных систем. http://www.mpi-sws.org/~rossberg/mixml/
HigherLogics - мой блог, и я потратил много времени на изучение этого вопроса. Ограничением действительно является абстракция над конструкторами типов, иначе говоря, "дженерики над дженериками". Похоже, что лучшее, что вы можете сделать для имитации модулей ML и функторов, - это как минимум один (полу-безопасный) приведение.
Это в основном сводится к определению абстрактного типа и интерфейса, который соответствует сигнатуре модуля, работающей с этим типом. Абстрактный тип и интерфейс имеют общий параметр типа B, который я называю "брендом"; бренд - это всего лишь подтип, реализующий интерфейс модуля. Марка гарантирует, что передаваемый тип является правильным подтипом, ожидаемым модулем.
// signature
abstract class Exp<T, B> where B : ISymantics<B> { }
interface ISymantics<B> where B : ISymantics<B>
{
Exp<int, B> Int(int i);
Exp<int, B> Add(Exp<int, B> left, Exp<int, B> right);
}
// implementation
sealed class InterpreterExp<T> : Exp<T, Interpreter>
{
internal T value;
}
sealed class Interpreter : ISymantics<Interpreter>
{
Exp<int, Interpreter> Int(int i) { return new InterpreterExp<int> { value = i }; }
Exp<int, Interpreter> Add(Exp<int, Interpreter> left, Exp<int, Interpreter> right)
{
var l = left as InterpreterExp<int>; //semi-safe cast
var r = right as InterpreterExp<int>;//semi-safe cast
return new InterpreterExp<int> { value = l.value + r.value; }; }
}
}
Как видите, приведение в основном безопасно, поскольку система типов гарантирует, что марка типа выражения совпадает с маркой интерпретатора. Единственный способ это испортить, если клиент создает свой собственный класс Exp и указывает марку Interpreter. Существует более безопасное кодирование, которое также позволяет избежать этой проблемы, но оно слишком громоздкое для обычного программирования.
Позже я использовал эту кодировку и перевел примеры из одной из статей Олега, написанных на MetaOCaml, для использования C# и Linq. Интерпретатор может прозрачно запускать программы, написанные с использованием этого встроенного языка на стороне сервера в ASP.NET или на стороне клиента, как JavaScript.
Эта абстракция над интерпретаторами является особенностью окончательного кодирования Олега без тегов. Ссылки на его статью приведены в блоге.
Интерфейсы являются первоклассными в.NET, и, поскольку мы используем интерфейсы для кодирования сигнатур модулей, модули и сигнатуры модулей также являются первоклассными в этой кодировке. Таким образом, функторы просто используют интерфейс непосредственно вместо сигнатур модулей, т.е. они будут принимать экземпляр ISymantics и делегировать ему любые вызовы.
Я не знаю функторов ML достаточно хорошо, чтобы действительно ответить на ваш вопрос. Но я скажу, что одним ограничивающим фактором.Net, который я всегда нахожу при монадическом программировании, является невозможность абстрагироваться над "M" в смысле "для любого выражения некоторого типа с M
Теперь я разместил подробное описание моего перевода модулей ML, подписей и функторов в эквивалентную кодировку C#. Я надеюсь, что кто-то найдет это полезным.
Комментарий Брайана - точный. Вот код OCaml, который использует функторы для (строгой) реализации Haskell sequence :: (Monad m) => [m a] -> m [a] параметризован по рассматриваемой монаде:
module type Monad =
sig
type 'a t (*'*)
val map : ('a -> 'b) -> ('a t -> 'b t)
val return : 'a -> 'a t
val bind : 'a t -> ('a -> 'b t) -> 'b t
end
module type MonadUtils =
sig
type 'a t (*'*)
val sequence : ('a t) list -> ('a list) t
end
module MakeMonad (M : Monad) : MonadUtils =
struct
type 'a t = 'a M.t
let rec sequence = function
| [] ->
M.return []
| x :: xs ->
let f x =
M.map (fun xs -> x :: xs) (sequence xs)
in
M.bind x f
end
Это выглядит сложно выразить в.NET.
ОБНОВЛЕНИЕ:
Используя технику naasking Я был в состоянии закодировать многоразовое sequence функция в F# в основном типобезопасным способом (использует downcasts).