RuMetaErl

Введение

Здесь я (Alexey Shchepin) буду выкладывать свои идеи о создании языка (MetaErl), объединяющего функциональную парадигму программирования со строгой типизацией и модель параллельного программирования используемую в Erlang. Определённые попытки добавить проверку типов в Erlang уже были (например Dialyzer), но проверка эта неполная. Например, можно послать в процесс сообщение, которое он не обрабатывает и оно никогда не будет извлечено из очереди, или которое содержит данные, которые процесс в дальнейшем не сможет обработать. Поэтому логичной кажется попытка подойти к проблеме с другой стороны, а именно добавить идеи Erlang в функциональный язык со строгой типизацией. В качестве основы будет использоваться OCaml.

Процессы

Основой для параллельного программирования в Erlang являются процессы и связь между ними. Связь осуществляется с помощью посылки асинхронных сообщений. У каждый процесс есть очередь сообщений из которой он может вынимать сообщения подходящие под определённый образец (pattern).

Каждый процесс имеет идентификатор. Его тип будем обозначать как pid 'a, где 'a -- тип сообщений которые процесс может принимать, причём этот тип должен быть polymorphic variant. Например, процесс который может принимать любые сообщения имеет тип pid [> ], только сообщения вида `A of int или `Stop -- pid [`Add of int | `Stop].

Принимать сообщения процесс может с помощью конструкции receive, с синтаксисом аналогичным match ... with в OCaml и семантикой конструкции receive в Erlang. Например:

 receive
   | `Add n -> loop (m + n)
   | `Stop -> ()
   | after 1000 -> loop (m - 1)

Тип функции теперь содержит не только информацию о том какой тип в какой функция отображает (например f : string -> int), но и тип сообщений, который она может принимать (например f : string -> int recv [`Add of int | `Stop]). Конструкция recv относится к ->, а не к типу аргумента или результата. Отсутствие recv равносильно recv []. Например,

 int -> (int -> float recv [`A of float | `B]) -> float -> float recv [`A of float | `B | `X | `Y]

равносильно

 int -> ((int -> float recv [`A of float | `B]) -> (float -> float recv [`A of float | `B | `X | `Y]) recv []) recv []

При выводе типа функции, recv в её результате содержит все варианты в recv функций вызваных в ней.

Создание нового процесса происходит с помощью функции spawn:

 spawn : (unit -> 'a recv 'b) -> pid 'b

Посылка сообщения процессу происходит с помощью функции (!!):

 (!!) : pid ([> ] as 'a) -> 'a -> unit

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

 f : string -> int recv [`Add of int | `Stop]

то self внутри неё будет иметь тип

 self : [`Add of int | `Stop]

Примеры

Эхо-процесс N1

 let start () =
   spawn init
 
 let init () =
   loop ()
 
 let loop () =
   receive
     | `EchoRequest (sender, uniq) ->
 	sender !! `EchoReply uniq;
 	loop ()
 
 let ping proc =
   let uniq = make_uniq () in
     proc !! `EchoRequest (self, uniq);
     receive
       | `EchoReply u when u = uniq ->
 	  true
       | after 5000 ->
 	  false

Компилятор должен вывести следующие типы:

 val start : unit -> pid [`EchoRequest of (pid [`EchoReply of uniq]) * uniq]
 val init : unit -> 'a recv [`EchoRequest of (pid [`EchoReply of uniq]) * uniq]
 val loop : unit -> 'a recv [`EchoRequest of (pid [`EchoReply of uniq]) * uniq]
 val ping : pid [`EchoRequest of (pid [`EchoReply of uniq ]) * uniq] -> bool
 	    recv [`EchoReply of uniq]

Эхо-процесс N2

 let loop () =
   receive
     | `EchoRequest sender ->
 	sender !! `EchoReply self;
 	loop ()
 
 let ping proc =
   proc !! `EchoRequest self;
   receive
     | `EchoReply p when p = proc ->
 	true
     | after 5000 ->
 	false

 val loop : unit -> 'b recv ([`EchoRequest of pid [`EchoReply of 'a]] as 'a)
 val ping : (pid [`EchoRequest of pid [`EchoReply of 'a]] as 'a) -> bool
 	    recv [`EchoReply of 'a]

Эхо-процесс N3

 let loop () =
   receive
     | `EchoRequest (sender, msg) ->
 	sender !! msg;
 	loop ()
 
 let ping proc =
   proc !! `EchoRequest (self, `EchoReply proc);
   receive
     | `EchoReply p when p = proc ->
 	true
     | after 5000 ->
 	false

 val loop : unit -> 'b recv [`EchoRequest of (pid ([> ] as 'a), 'a)]
 val ping : (pid [`EchoRequest of (pid 'b, [`EchoReply of 'a])] as 'a) -> bool
 	    recv ([`EchoReply of 'a] as 'b)

Map

 let rec map f =
   function
     | [] -> []
     | x :: xs -> f x :: map f xs
 
 val map : ('a -> 'b recv ([> ] as 'c)) -> 'a list -> 'b list recv 'c