ООП в Окамле

[thedeemon]

Сегодня впервые столкнулся с ситуацией, где использование ООП фич Окамла показалось уместным. Понадобилось по-разному трансформировать дерево программы в моем конпеляторе Leo. Например, нужно заменить переменные с заданными именами на заданные выражения. Или заменить везде один оператор на другой. В обоих случаях нужно аккуратно рекурсивно обойти все дерево и построить точно такое же, но в одном аспекте отличающееся. Дерево описывается набором ссылающихся друг на друга алгебраических типов - стейтменты, выражения, условия и т.д. Был бы это один тип, можно было бы следать универсальную функцию map, рекурсивно применяющую функцию-аргумент к узлам дерева, а так получается, что функций и аргументов понадобится много. Поэтому сделал иначе: объединил функции рекурсивного обхода в один класс, у которого можно переопределить нужные куски, остальное отдав на откуп унаследованной функциональности.

class mapper =  
  object(self) 
    method map_code code = List.map self#map_stmt code 
     
    method map_stmt = function 
      | Break | DefVar _ as x -> x 
      | Assign(lv, rv) -> Assign(self#map_lvalue lv, self#map_rvalue rv)    
      | Call(name, rvs) -> Call(name, List.map self#map_rvalue rvs)         
      | Comp code -> Comp(self#map_code code) 
      ... 
       
    method map_lvalue = function  ... 
    method map_rvalue = function  ... 
    method map_cond = function  ...  
  end 

Например, замена переменных по переданному набору имя-значение выглядит так:

let subst_vars smap code = 
  let o = object 
      inherit mapper as super 
      method map_lvalue = function 
        | Var name as x -> (try M.find name smap with Not_found -> x) 
        | something_else -> super#map_lvalue something_else 
    end  
  in o#map_code code

Тут создается объект неназванного типа, унаследованного от класса mapper, в нем переопределен один метод, а в нем фактически переопределен только один вариант АТД, все остальное делает базовый класс, рекурсивно проходя по всем закоулкам и вариантам дерева. Это можно еще упростить. Например, для трансформации стейтментов была добавлена такая функция:

let subst_code_by_stmt f code =  
  let o = object 
      inherit mapper as super 
      method map_stmt st =  
        match f st with Some st' -> st' | None -> super#map_stmt st 
    end  
  in o#map_code code

Использование которой для совершения конкретной трансформации сводится вообще к одной строчке:

C.subst_code_by_stmt (function C.Print x -> Some(C.Prchar x) | _ -> None) code

Кажется, без ООП так просто не получилось бы.

Comments

[vshabanov.livejournal.com]

Можно и без объектов:

type mapper =
    { map_stmt : mapper -> stat -> stat;
      map_lvalue : mapper -> expr -> expr;
    }

let default_mapper =
  { map_stmt = (fun _ s -> s);
    map_lvalue = (fun _ e -> e);
  }
      
let map_code m code = List.map (m.map_stmt m) code

let subst_code_by_stmt f = 
  map_code { default_mapper with
     map_stmt = fun m st ->
       match f st with Some st' -> st' | None -> m.map_stmt m st 
      }

Тут, конечно надо вместо self#map_stmt писать m.map_stmt m, что не очень симпатишно и лишние скобки вокруг fun в default_mapper, зато наследование делается обычным обновлением полей в записи и объекты не нужны (плюс работать должно чуть шустрее).

По моему опыту, объекты в кемле необходимы только для расширяемого duck typing-а, когда можно сделать
val f : < woof : () > -> ()
val g : < quack : () > -> ()
val h : < meow : () > -> ()

а потом делать
val mutant1 : < woof : (); quack : () >
val mutant2 : < quack : (); meow : () >

Во всех остальных случаях у меня как-то получалось обходиться без объектов.

[vshabanov.livejournal.com]

Чуть напутал в f/g/h (нерасширяемые вышли), надо
val f : < woof : (); .. > -> ()
val g : < quack : (); .. > -> ()
val h : < meow : (); .. > -> ()

после чего можно g mutant1; g mutant2; h mutant2

[thedeemon.livejournal.com]

Так это ручное повторение тех же объектов.

[vshabanov.livejournal.com]

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

[thedeemon.livejournal.com]

>По моему опыту, объекты в кемле необходимы только для расширяемого duck typing-а

А можно примеров из практики? Мне до этого объекты не пригождались как-то.

[vshabanov.livejournal.com]

Да скорее всего и не пригодятся. Когда-то давно одни товарищи (Гай Стил и Сассман) хотели сделать объектный язык (scheme), но оказалось, что достаточно замыканий и изменяемых ячеек. Примерно та же история и в кемле.

У меня был достаточно извратский случай (по крайней мере, для кемла). Я делал игрушку с использованием чего-то, отдаленно напоминающего FRP. Были там всякие изменяемые во времени значения.

Так вот, этим значениям передавался неявный параметр -- состояние мира. Мне захотелось не хардкодить это состояние мира, а сделать его независимым от базовых комбинаторов.

В итоге у меня были

mouse_x : (< viewer : Viewer.t; .. >, float) value
time    : (< dt : Time.t; .. >, float) value
button_max_bet : (< peripherals : Peripherals.t; .. >, bool) value

Все они жили в разных модулях и ничего не знали о том, кто и как их будет использовать. Но они знали, что в состоянии есть поля viewer/dt/peripherals.

При стыковке этих комбинаторов получались выражения с общим типом, например (< dt : Time.t; viewer : Viewer.t; .. >, Matrix.t) value.

В общем, жесть. В хаскеле такое делается обычными классами типов:

class HasDt simState where
    getDt :: simState -> Dt

Пока писал коммент, понял, что сейчас я сделал бы все то же самое через функторы, которым передается ф-ия, выдирающая нужное подсостояние из общего состояния. Все равно не так удобно, как в хаскеле, но заметно лучше, чем с объектами -- очень уж часто < st : St.t; '_a .. > появлялись -- у функтора с фиксированным типом таких проблем будет поменьше.

Еще, в самом начале работы на кемле, я использовал объекты для графа сцены -- тоже глупость.

Собственно больше я нигде объекты и не использовал. Да и в этих двух случаях оказалось зря.

[thedeemon.livejournal.com]

Интересно, спасибо!

+1

[nealar.livejournal.com]

Мне тоже кажется, что параметрического полиморфизма достаточно. Либо тут: Был бы это один тип, можно было бы следать универсальную функцию map, рекурсивно применяющую функцию-аргумент к узлам дерева, а так получается, что функций и аргументов понадобится много. ошибка и проблема в другом (например, полиморфная ФВП обходит дерево слишком единообразно, а надо хитрить), либо я чё-то где-то не понял.

Re: +1

[thedeemon.livejournal.com]

>параметрического полиморфизма достаточно

Каким образом? В дереве сидят значения (поддеревья) разных типов, какой тип должен быть у аргумента map? Какой тип должен быть у самой map?

Re: +1

[nealar.livejournal.com]

Тип у дерева какой? Я в этом коде не нашёл.

Re: +1

[gds.livejournal.com]

типы разные у разных кусков дерева (map_code кушает список элементов, которые могут быть обработаны map_stmt, а map_stmt кушает некоторый индуктивный тип данных). Благодаря объектам нет нужды выписывать тип, а компилятор знает тип через type inference. У любителей ФП это модно.

Re: +1

[thedeemon.livejournal.com]

Примерно такой:

type name = string 
type code = statement list 
and statement =  
  | DefVar of name 
  | Assign of lvalue * rvalue 
  | Call of name * rvalue list 
  | Ret of rvalue list 
  | If of condition * code * code 
  | Print of rvalue 
  | Comp of code 
  | Break 
  ... 
 
and lvalue = Var of name | PVar of name  | PArith of oper * lvalue * rvalue 
 
and rvalue = 
  | Val of int 
  | LV of lvalue 
  | Arith of oper * rvalue * rvalue 
  | FCall of name * rvalue list 
  | Byte of rvalue 
 
and condition =  
  | Less of rvalue * rvalue 
  | Eq of rvalue * rvalue 
  | And of condition * condition 
  | Or of condition * condition 
  | Not of condition

[thesz.livejournal.com]

Обязательно надо упомянуть Scrap your boilerplate в целом и Uniplate в частности.

http://research.microsoft.com/en-us/um/people/simonpj/papers/hmap/
http://community.haskell.org/~ndm/uniplate/

[thedeemon.livejournal.com]

Ага, тоже про SYB вспоминал. Я правильно понимаю, что оно основывается на GHC-шных расширениях (вроде LANGUAGE DerivingDataTypeable) и в чистом Хаскеле (98) невыразимо?

[thesz.livejournal.com]

Сам Data.Typeable довольно обычный класс типов.

Его deriving - да, делается компилятором.

[permea-kra.livejournal.com]

из специфичного там rank 2 полиморфизм, без которого некоторые вкусности из class Data.Data не типизируются.