Двойная диспетчеризация

[@maxim_0_o]

На сколько я понял, мы условились, что в интерфейсе не будет свойства Color. Однако в блоке кода под заголовком «Применение посетителя к задаче» это свойство в интерфейсе есть. Я что-то не правильно понял?

[@Johanan]

Вы всё правильно поняли, Color в ICell действительно не нужен. Опечатку поправил.

[@dougrinch]

А как же

private string Do(ICell a, ICell b)
{
    return a.Color + "\t-->\t" + b.Color;
}

?

Хотя в данной реализации и не уйти от свойства в интерфейсе. Разве что создавать метод Do на все варианты, благо апи позволяет. Действительно удобное получилось.

[@Johanan]

А! Точно. Внимательно читаете — спасибо. Сперва у меня как раз был цвет в интерфейсе, а добыть нужно было, скажем, целое число, которым обладала только красная ячейка. На идее решения эта оплошность никак не скажется, но нужно подумать, как лучше поправить статью.
Что нам нужно в методе Do? Знать цвет первой и второй ячейки, причём обе им обладают независимо друг от друга. Значит, нам нужен простой («классический») визитёр, который цвет добудет.

[@lasalas]

Зачем так много кода для такой тривиальной задачи?

[@Johanan]

А как иначе вы её предлагаете решать, если отмести варианты с динамическим приведением типов?

[@lasalas]

Как-то так, например

public static string Match(ICell t1, ICell t2) { return Patterns .Select(x => x(t1, t2)) .First(x => x != null) (); } private static readonly Func<ICell, ICell, Func<string>>[] Patterns = { (t1, t2) => Match<RedCell, RedCell>(t1, t2, () => "красное на красном"), (t1, t2) => Match<GreenCell, BlueCell>(t1, t2, () => "побережье"), (t1, t2) => (() => t1.Color + "\t-->\t" + t2.Color) }; private static Func<string> Match<T1, T2>(ICell t1, ICell t2, Func<string> f) where T1 : ICell where T2 : ICell { return t1 is T1 && t2 is T2 ? f : null; }

[@lasalas]

Как-то так, например

public static string Match(ICell t1, ICell t2)
{
return Patterns
.Select(x => x(t1, t2))
.First(x => x != null)
();
}

private static readonly Func<ICell, ICell, Func>[] Patterns =
{
(t1, t2) => Match<RedCell, RedCell>(t1, t2, () => «красное на красном»),
(t1, t2) => Match<GreenCell, BlueCell>(t1, t2, () => «побережье»),
(t1, t2) => (() => t1.Color + "\t-->\t" + t2.Color)
};

private static Func Match<T1, T2>(ICell t1, ICell t2, Func f)
where T1: ICell
where T2: ICell
{
return t1 is T1 && t2 is T2? f: null;
}

PS: Похоже не работает форматирование

[@lasalas]

Можно сделать еще компактнее, но более грубо

public static string Match(ICell a, ICell b)
{
return (Match<RedCell, RedCell>(a, b, () => «красное на красном»)
?? Match<GreenCell, BlueCell>(a, b, () => «побережье»)
?? (() => a.Color + "\t-->\t" + b.Color))
();
}

[@Johanan]

Понял теперь вашу идею. Смотрите, вы всё равно не уходите от динамического приведения типов. Например, если я прошу вас вывести не «красное на красном», а что-нибудь из открытых свойств ячейки, вам всё равно придётся приводить тип. А если так, то наша беседа сводится к другому вопросу: что лучше — обычный посетитель или перебор типов через switch? Убийственного аргумента в пользу первого у меня нет. Но, например, если добавляем новый элемент, а использована динамическая типизация, уже куда сложнее найти все места, которые нужно обновить, чтобы поддержать его (предполагаем, что таких switch'ей у нас довольно много), легче что-то пропустить и получить потом runtime exception.
В нашем случае, когда обработка по умолчанию задана исключений не будет, но мы получим какой-то общий объект вместо интересующего нас частного случая. Узнаем об этом тоже, скорее всего, в runtime.

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

Обобщая вышесказанное: 1) при явном приведении типов больше вероятности получить ошибку на этапе исполнения 2) мне было интересно решить задачу без явного приведения типов, что тоже немаловажно.

[@lasalas]

1. Не совсем понятно, почему надо бояться приведения типов и откуда должны взяться runtime exceptions, раз типизация статически проверяется компилятором.
2. То что я описал — тот же самый visitor, только в профиль и без макияжа.
3. Можно слегка доработать Match<>(), чтобы стали доступны фичи конкретных типов:

private static Func Match<T1, T2>(ICell t1, ICell t2, Func<T1, T2, string> f)
where T1: ICell
where T2: ICell
{
if (t1 is T1 && t2 is T2)
return () => f((T1)t1, (T2)t2);
return null;
}

…
(t1, t2) => Match<GreenCell, BlueCell>(t1, t2, (x,y) => «побережье: » + x.GreenFeature + ", " + y.BlueFeature),
…

[@DrReiz]

Производительность! Производительность — основное преимущество двойной диспетчеризации по сравнению с pattern matching-ом.
Двойная диспетчеризация — это два virtcall-а на один вызов. Паттерн матчинг — это N проверок типов на каждый вызов.

[@lasalas]

Зависит от реализации. Но особой разницы быть не должно.

[@DrReiz]

Какие компиляторы умеют разворачивать паттерн матчинг по двум произвольным параметрам в C*O(1) и с C близкой к 1?

[@Lol4t0]

stackoverflow.com/questions/4767908/erlang-pattern-matching-performance

[@DrReiz]

Цитата от туда «The internals usually have a pattern match compiler which turns an advanced pattern match into a simpler series of checks with the goal to minimize the number of checks».
Соответственно, это будет С*O(кол-во правил) с C меньше 1 (приблизительно: 0.3 — 0.7), а не O(1).

[@Lol4t0]

Ну, ортогонализация проверок все-таки позволяет сократить количество проверок в разы. Конечно, некоторое их колчество остается. Но дело в том, что в реальной жизни количество вариантов паттеронов не слишком велико. И хотя ассимптотически они будут медленнее двух виртуальных вызовов, не надо забывать, что virtual call является большим барьером оптимизации, чем сравнение.

Я бы устроил тестирование, но не могу придумать задачку под него

[@DrReiz]

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

[@lasalas]

Можно представить (и реализовать) компилятор с любой степенью оптимизации сопоставления: со сбалансированныеми деревьями, хэшами, кэшами…

Но это скорей рассуждения из серии «может ли бог создать такой камень, который не сможет поднять?» :)

Что-то мне подсказывает, что если список сопоставления очень велик и разнообразен, то, видимо, имеются серьезные проблемы в архитектуре и решать надо именно их

[@Mrrl]

А если ввести список пар (Match — обработчик), который можно пополнять снаружи, то и код функции Match(ICell,ICell) при добавлении нового цвета менять не придётся. Правда, от операции as внутри обработчиков избавиться не удастся.

[@Trueteller]

На мой взгляд, показать выразительность языка не очень удалось. На F# с pattern matching получилось бы гораздо выразительные.
Обильное применение паттернов для решения задачи, которую можно было бы решить в несколько строк, свидетельствует скорее о нехватке языковых конструкций.
Плюс нарушение SOLID принципов, дупликация кода…
Возможно, это решение имело больше плюсов в вашей бизнес задаче из реальной жизни.
Спасибо за статью!

[@Johanan]

Вам спасибо отзыв!
Не было цели доказать, что C# — самый выразительный язык. На F# match действительно куда проще решил бы эту задачу, ну так там и наследования не приветствуется, а вместо него Union.
Я хотел скорее показать, то такая задача на C# в принципе разрешима при условии, что мы не создаём (N + const) классов. Для меня, по крайней мере, это было не очевидно.

Про SOLID вы что именно имеете в виду? Что я смешал строителя и посетителя, или что-то другое?

[@Trueteller]

В основном, Open-closed. Если надо будет добавить класс YellowCell, придется менять все вспомогательные классы.

[@Johanan]

А, ну тут иначе не совладать с задачей. И я бы даже не сказал, что это так уж плохо. Да, мне придётся менять вспомогательные классы, но, меняя их, я хотя бы задумаюсь, какими именно правилами должны пользоваться все мои конкретные обработчики для жёлтой клетки.
Раз речь зашла о F# — что будет если мы добавим новый тип в unit? Нам придётся обновить все использования его и указать, что делать функции в случае жёлтой клетки. И так ли это плохо?

[@Trueteller]

Если новый тип не требует специального поведения, F# код или реализация «в лоб» (как у lasalas) не изменятся.
Если требует специального поведения — изменится в одном месте, а не 3х связаных классах.

[@Johanan]

Тут мне остаётся вам поверить — я не так хорошо знаю F#. Или, может, вы пример приведёте? Любопытно разобраться.

[@Lol4t0]

И ТУТ В ТРЕД ВРЫВАЕТСЯ HASKELL

-- цвета (кто же рабоатет со строками)
data Color = Red | Blue | Green deriving (Show)

-- интерфес
class Colored a where
	getColor :: a -> Color

--- проверка
process :: Colored a => a -> a -> String
process a b = process' (getColor a) (getColor b)

process' Red Red = "Red on Red"
process' Green Blue = "Coast"
process' a b = show a ++ " --> " ++ show b


data MyColor = MyRed | MyGreen | MyBlue deriving (Read)

-- имплементация интерфейса
instance Colored MyColor where
	getColor MyRed = Red
	getColor MyGreen = Green
	getColor MyBlue = Blue


main = interact $ unlines . map ((\[a, b] -> process (read a::MyColor) (read b)) . words) . lines

Извините

[@Johanan]

Ну, да. Кто бы спорил, что функциональные языке с такой задачкой на раз справляются. Но за пример спасибо, хороший!

[@michael_v89]

Мне почему-то кажется, что наследовать красную ячейку от ячейки — это примерно то же самое, как наследовать квадрат от прямоугольника. Если не секрет, какая была реальная задача?

[@Johanan]

Было дерево, где элементы — узлы. Наружу выставлены потомки списком и только. А в значении своя логика, вот с ней и нужно было разбираться.

[@middle]

А вот как это выглядит в языке с нормальной множественной диспетчеризацией. Common Lisp:

(defclass icell ()
  ())

(defclass red-cell (icell)
  ())

(defclass blue-cell (icell)
  ())

(defclass green-cell (icell)
  ())


(defgeneric colors (arg1 arg2)
  )

(defmethod colors ((a icell) (b icell))
  (format nil "~S --> ~S" a b))

(defmethod colors ((a green-cell) (b blue-cell))
  "побережье")

(defmethod colors ((a red-cell) (b red-cell))
  "красное на красном")

[@Johanan]

А если определить, кроме generic только два метода с такой сигнатурой (icell, red-cell) и (red-cell, icell), а потом вызвать с двумя красными, то какой вызовется метод?

[@middle]

В стандартном способе топологической сортировки методов вызовется (red-cell, icell). Можно сделать свой, если надо по-другому.

[@lasalas]

match(red, red, «красное на красном» ).
match(green, blue, «побережье»).
match(X,Y, S) :- concat([X,' --> ', Y], S).

:- match(green, white, S), write(S).

(Prolog)

[@middle]

Провокационный вопрос: а можно сделать подкласс от атома red? ;) Насколько это гибко и расширяемо?

[@lasalas]

Разумеется, Prolog (классический) не поддерживает ООП. Но извратиться всегда можно ;)

expands(X, X).
expands(dark_red, red).
expands(light_green, green).
…

match(X, Y, «красное на красном» ) :- expands(X, red), expands(Y, red).
match(X, Y, «побережье» ) :- expands(X, green), expands(Y, blue).
…

:- match(dark_red, red, S), write(S).