ООП в Окамле

[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

[gds.livejournal.com]

мне по нраву. И даже наследование полезным оказалось.
Я же чаще использую объекты как слабо-типизированные записи.

[andy128k.livejournal.com]

Не очень хорошо. Тут ситуация полностью детерминированная, но применяется позднее связывание. Я бы нагородил чего-нибудь на camlp4.

[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]

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

[thedeemon.livejournal.com]

>Я бы нагородил чего-нибудь на camlp4.

Это сложнее. А для набора связанных типов может быть даже сильно сложнее.

[thedeemon.livejournal.com]

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

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

[andy128k.livejournal.com]

Если не заморачиваться и сделать тупой макрос a la #define с текстовой подстановкой, то не сильно и сложно будет.

+1

[nealar.livejournal.com]

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

Вспомнилось подходящее к случаю.

[(Anonymous)]

The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."

Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.

[vshabanov.livejournal.com]

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

[thesz.livejournal.com]

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

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

[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]

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

Re: +1

[thedeemon.livejournal.com]

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

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

Re: Вспомнилось подходящее к случаю.

[thedeemon.livejournal.com]

Ага, помню такую.
Не подскажете, как в замыканиях реализуются виртуальные методы? :)
Выше был вариант, но там и замыканий-то нет, там С-style ООП.

[thedeemon.livejournal.com]

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

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

Re: Вспомнилось подходящее к случаю.

[zoonior.livejournal.com]

>> Не подскажете, как в замыканиях реализуются виртуальные методы? :)
К сожалению, несколько разжеванно:

MIT 6.001 Spring 2005 L16 (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/lecture-notes/lecture16webhan.pdf)
MIT 6.001 Spring 2005 L17 (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/lecture-notes/lecture17_webhan.pdf)
MIT 6.001 Spring 2005 L18 (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/lecture-notes/lecture18_webhan.pdf)

[thesz.livejournal.com]

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

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

[permea-kra.livejournal.com]

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

Re: Только зачем этот map руками писать? ;)

[thedeemon.livejournal.com]

О, круто!
Я просто с camlp4 все никак не подружусь.