Парсеры с состоянием и нехватка полиморфизьма

[thedeemon]

Некоторое время назад меня пытались убедить, что Окамл недостаточно хорош для парсер-комбинаторов, потому что стоит попытаться добавить в парсеры состояние, как тут же возникают трудности, связанные с нехваткой полиморфизма. Проблема там вот в чем. Мой вариант простых парсеров не содержал состояния, и парсером там была функция типа char list -> 'a parse_result, где тип результата выглядел так:

type 'a parse_result = Parsed of 'a * char list | Failed

В определенном смысле какое-то состояние в таких парсерах есть - это текущая позиция в разбираемом тексте, определяемая неразобранным остатком текста, возвращаемым в случае успеха. Для разбора контекстно-зависимых грамматик иногда хочется, чтобы парсер имел какое-то дополнительное состояние. Например, при разборе текста на С++ хорошо бы помнить имена описанных ранее классов, чтобы понимать, что означает some_name(42). Расширим наше определение парсера и добавим передачу произвольного состояния:

type ('res, 'state) parse_result =  
  Parsed of 'res * ('state * char list) | Failed

Парсер будет принимать на вход не просто список символов, а пару из состояния и списка символов. На выходе будет только что описанный parse_result, возможно с новым состоянием.

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

let p_pred p (st, lst) =     
  match lst with 
  | [] -> Failed 
  | h::t -> if p h then Parsed(h, (st, t)) else Failed

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

let isdigit c = c>='0' && c<='9' 
let p_digit = p_pred isdigit

При попытке это скомпилировать окамл ругается:
The type of this expression, '_a * char list -> (char, '_a) parse_result, contains type variables that cannot be generalized.
Фишка в том, что мы использовали карринг, опустив последний параметр p_pred, но этот параметр должен быть полиморфным - он содержит состояние, тип которого еще не определен. Алгоритм вывода типов в окамле умеет выводить полиморфные типы для имен, заданных в конструкции let, но не для тех, что были опущены при карринге. Простейшим решением проблемы было бы дописать недостающий параметр:

let p_digit s = p_pred isdigit s

Такой вариант компилируется нормально, но это некрасиво, т.к. придется везде писать эти лишние параметры, код раздуется, потеряется DSL-ность. Однако выход есть, и очень простой!

Вынесем типовый параметр состояния на уровень выше - в параметр модуля.
Заключим нашу библиотеку комбинаторов в функтор:

module Parsers(S : sig type t end) = struct 
  type 'res parse_result = Parsed of 'res * (S.t * char list) | Failed 
  ...(* здесь все базовые комбинаторы *) 
end

Теперь
let p_digit = p_pred isdigit
прекрасно компилируется, т.к. тип опущенного параметра известен, он содержит тип состояния S.t, который будет передан функтору при его использовании.

Базовые комбинаторы выглядят практически так же, как в случае без состояния:

let p_many p =  
  let rec loop s =  
    match p s with   
    | Parsed(_, s') -> loop s'  
    | Failed -> Parsed((), s) in   
  loop 
 
let (>>>) p1 p2 s = 
  match p1 s with 
  | Parsed(_, s') -> p2 s' 
  | Failed -> Failed 
 
let p_many1 p = p >>> p_many p 
 
let (>>=) p1 f s = 
  match p1 s with 
  | Parsed(x, s') -> f x s' 
  | Failed -> Failed 
 
let return x s = Parsed(x, s)

let updateState f (st, lst) = Parsed((), (f st, lst))

А вот так выглядит их использование. Сделаем парсер, принимающий непустую последовательность маленьких латинских букв и подсчитывающий количество вхождений буквы 'e', причем это количество будет храниться в состоянии парсера, т.е. в данном случае тип состояния - int:

let isalpha c = c>='a' && c<='z' 
 
module P = Parsers(struct type t = int end) 
open P 
 
let myletter =  
  p_pred isalpha >>= fun c -> 
  if c='e' then updateState ((+) 1) else return () 
   
let parser = p_many1 myletter

Используем его для подсчета вхождений буквы 'e' в слове 'engineering':

let lst = String.explode "engineering" in 
match parser (0, lst) with 
| Parsed(_, (n, _)) -> print_int n 
| Failed -> print_string "failed"

Запускаем, получаем ответ - 3. Парсеры с состоянием готовы, все базовые комбинаторы от типа состояния абстрагированы, использование их требует лишь пары дополнительных строк: передать в функтор тип состояния и открыть получившийся модуль.

Comments

[vshabanov.livejournal.com]

Только теперь появляется проблема с модульностью. Все комбинаторы должны быть внутри module Parsers. Разнести их не получится.

[thedeemon.livejournal.com]

Только самые базовые, их достаточно описать один раз.
Все юзер-левел парсеры (вроде описанного в примере myletter) могут быть описаны где угодно.

[vshabanov.livejournal.com]

Да. Я про базовые и писал. См. тот же Parsec -- там вмеру много разных базовых комбинаторов -- и они разнесены по модулям. В кемле придется делать один монстро-модуль.

Плюс функторы не очень удобно тестить в интерпретаторе. Надо весь функтор перегружать.

Вариант с расширением модулей через include -- не очень хорошо. Получается использование модуля определяется самими модулями, а не снаружи.

В общем для небольших задач решение подходит (хотя и не очень удобно), для чего-то большего становится совсем неудобно.

[thedeemon.livejournal.com]

Я не вижу, откуда тут возьмется монстро-модуль. Базовых комбинаторов не так уж много, остальное через них выражается. Т.е. проблема понятна, но, имхо, преувеличена.

[thedeemon.livejournal.com]

К тому же, модули в окамле расширяемые: описываешь новый с тем же именем, импортируешь старый, добавляешь свое. См. тот же ExtLib, там многие модули стандартной библиотеки так расширили.