Data-Directed Programming

В началото на годината, аз и няколко приятели се организирахме в SICP Study Group. Макар повечето материал досега да е основен, научих любопитни неща. Искам да разпиша едно от тях – data-directed programming.

Това е интересна идея, която продължава тази тема. Понятието „data-directed programming“ идва от SICP. Наподобява multi-dispatch (или visitor design pattern). Примерите в книгата са на Scheme, но аз ще се опитам да ги преведа на Python. Това няма да бъде най-идиоматичният Python, но пък ще бъде добра илюстрация. Направил съм gist, съдържащ целия код, така че да може да го разгледате спокойно.

Ще покажа няколко синтетични примера, които едва ли ще направя в практиката (например класове Integer и Rational). Все пак, идеите имат приложение. Първото, което ми хрумва, е работа с абстрактни синтактични дървета. Далеч не е единственото.

Проблемът

Проблемът е следният: имаме няколко типа (Circle, Square) които могат да работят с генерични операции (area, perimeter). Въпросът е как бихме могли да организираме типовете и операциите и какви биха били последствията от всеки различен начин на представяне, който изберем. Друг възможен пример е система с четири вида числа – цели, рационални, реални и комплексни, които трябва да поддържат аритметичните операции – събиране, умножение и т.н.

Ще ползвам първия пример – типове Circle и Square с операции area и perimeter. Това е изключително опростен пример, но ще свърши работа. Имайте предвид, че принципите, които предстои да илюстрирам, важат и за операции с повече от един аргумент (например събиране на две числа).

Структури и обекти

Писал съм по-рано за двата стандартни начина за организация. Ще ги припомня.

Първият е да поставим проверката на типа във всяка от операциите:

class Square:
    def __init__(self, side):
        self.side = side

class Circle:
    def __init__(self, radius):
        self.radius = radius

def area(shape):
    if isinstance(shape, Circle):
        return PI * shape.radius ** 2
    elif isinstance(shape, Square):
        return shape.side ** 2

def perimeter(shape):
    if isinstance(shape, Circle):
        return 2 * PI * shape.radius
    elif isinstance(shape, Square):
        return shape.side * 4

Чичо Боб нарича това „структури“, докато в SICP е известно като „generic operations with explicit dispatch“. Обърнете внимание, че това е стила, който идва по-естествено в езици като C.

Ето и втория вариант:

class Square:
    def __init__(self, side):
        self.side = side

    def area(self):
        return self.side ** 2

    def perimeter(self):
        return self.side * 4

class Circle:
    def __init__(self, radius):
        self.radius = radius

    def area(self):
        return PI * self.radius ** 2

    def perimeter(self):
        return 2 * PI * self.radius

Чичо Боб го нарича „обекти“, докато в SICP е „message-passing style“. Това е стила, който идва по-естествено в езици от типа на Java и Python.

Избягвайки конкретна терминология, аз ще ги наричам „първия вариант“ и „втория вариант“. Та, как изглежда сравнението между тях?

При първия вариант, добавянето на нова операция е лесно, понеже изисква добавяне на една функция. Добавянето на нов тип е по-трудно, понеже изисква да променим всички операции. Последното не е локализирана промяна – трябва да променим Х различни функции, вероятно в Х различни файла. Това се нарича shotgun surgery.

При втория вариант е обратното – нов тип се добавя лесно, но добавянето на нова операция изисква промяна на всички типове. Отново – shotgun surgery.

Data-Directed Programming

Има и трети вариант. Ще държим операциите и типовете разделени. Ще имаме една глобална таблица, която ще съпоставя операции и типове на функции. Ще дадем уникално име на всяка операция. Извикването на операция ще представлява търсене на запис в таблицата, отговарящ на съответните име на операция и типове данни. Ако не бъде намерено съвпадение, ще приемаме, че не можем да приложим желаната операция над въпросните типове данни и ще хвърляме грешка.

Ето как изглеждат типовете в този вариант:

class Square:
    def __init__(self, side):
        self.side = side

class Circle:
    def __init__(self, radius):
        self.radius = radius

Ето как изглеждат операциите:

def area(shape):
    return apply_generic(‘area’, shape)

def perimeter(shape):
    return apply_generic(‘perimeter’, shape)

Ето свързващото звено:

put(‘perimeter’, (Circle,), lambda c: 2 * PI * c.radius)
put(‘area’, (Circle,), lambda c: PI * c.radius ** 2)
put(‘perimeter’, (Square,), lambda s: s.side * 4.0)
put(‘area’, (Square,), lambda s: s.side ** 2)

И ето нужната инфраструктура:

operations = {}

def get(name, types):
    return operations.get((name,) + types)

def put(name, args, code):
    operations[(name,) + args] = code

def apply_generic(name, *args):
    types = tuple(map(type, args))
    code  = get(name, types)

    if not code:
        raise TypeError(‘Undefined operation {0} for types {1}’.format(
            name, [t.__name__ for t in types]))

    return code(*args)

Има няколко неща, на които трябва обърнем внимание. Но първо, вижте как се добавя нов тип:

class Rectangle:
    def __init__(self, a, b):
        self.a, self.b = a, b

put(‘perimeter’, (Rectangle,), lambda r: 2 * r.a + 2 * r.b)
put(‘area’, (Rectangle,), lambda r: r.a * r.b)

Ще покажа и как се добавя нова операция. Операцията ще бъде съвсем глупава – ще се казва double и ще връща същата фигура но с два пъти по-голямо лице:

def double(shape):
    return apply_generic(‘double’, shape)

SQRT2 = 2 ** 0.5
put(‘double’, (Circle,), lambda c: Circle(c.radius * SQRT2))
put(‘double’, (Square,), lambda s: Square(s.side * SQRT2))
put(‘double’, (Rectangle,), lambda r: Rectangle(r.a * SQRT2, r.b * SQRT2))

И нов тип и нова операция могат да бъдат добавени без промяна на съществуващ код (и без shotgun surgery). Това е много приятно свойство на този вариант, което, разбира се, идва на определена цена:

  • Dispatch-ът е по-бавен, понеже е имплементиран от нас на Python, а не е част от интерпретатора.
  • При създаване и на тип, и на операция, има известен overhead.
  • Кодът не е от най-идиоматичните за Python. Това е нормално, понеже Python тласка към обекти, а не към структури. В Scheme е по-различно.
  • Има известен Greenspun – имаме чувството, че имплементираме нещо, което би трябвало да е вградено в езика.
  • Вече зависим от реда на зареждане на кода. put и get трябва да са заредени преди да добавим типовете в таблицата. Отделно, double знае, че Rectangle е добавен преди него. Но това е друг проблем.

Въпреки това, в тази система няма проблемите на първия и втория вариант.

Следват малко по-общи разсъждения.

Type coercion

Да разгледаме случая, в който типовете данни са числа различни видове числа, а операциите са аритметичните. Тогава ще имаме следната таблица:

put(‘add’, (Integer, Integer), lambda a, b: Integer(a.n + b.n))
put(‘add’, (Rational, Rational),
    lambda a, b: Rational(a.num * b.den + b.num * a.den, a.den * b.den))

Въпросът е как да подходим със следния код:

add(Integer(1), Rational(1, 4))

Бихме могли да променим apply_generic, така че да се опитва да конвертира аргументите до типове, за които операцията се поддържа. Например, ако първият операнд се обърне до рационално число, ще можем да ползваме дефиницията на операцията 'add' за (Rational, Rational).

Имплементирането на такъв алгоритъм е по-сериозна задача. В gist-а можете да намерите реализация, засягаща изключително частен случай на гореописаното. Разбира се, може да изградите типова йерархия и да се опитвате да вдигате операндите до „по-високи“ типове, ако операцията не е дефинирана за текущата комбинация на типове данни. Или пък да се опитате да намерите подходящ запис в таблицата с помощта на дефинираните операции и някакви налични функции за конвертиране. Не е толкова интересно как – по-интересно е, че има такава възможност.

Синтактична захар

Както казах, кодът е неидиоматичен. Един Python програмист ще очаква да може да напише circle.area() или Rational(1, 4) + Integer(1). Това може да се постигне с базов клас, който да делегира към apply_generic. Например:

class Figure:
    def perimeter(self):
        return apply_generic(‘perimeter’, self)

    def area(self):
        return apply_generic(‘area’, self)

class Square(Figure):
    …

class Circle(Figure):
    …

Gist-ът съдържа целия пример за фигурите и целия пример за числата.

Общи разсъждения

Преди всичко, мисля, че този проблем рядко възниква в практиката. Мога да се сетя за няколко ситуации, в които съм имплементирал система с генерални операции. Не съм сигурен дали за тях data-directed programming щеше да е по-подходящо от праволинейното обектно-ориентирано решение.

Отделно, можем лесно да добавяме нов тип или нова операция, без да променяме съществуващия код. Но би било хубаво той да е организиран консистентно – по тип (обектно) или по операция (структурно). Тази липса на консистентност ще направи кода по-труден за ориентиране.

Има и друг проблем. По-рано добавихме един тип (Rectangle) и една операция (double). Едното трябва да знае за другото. В нашия пример операцията знаеше, че преди нея сме добавили тип Rectangle и даваше имплементация за него. Можеше да го направим наобратно – първо да добавим операцията и чак след това да добавим нов тип, който да я поддържа. Но генерално, всяко следващо разширение трябва да знае за предишното. Това е същия проблем като този с организацията от предишния абзац.

Допълнително, Python кода, който показах, далеч не е идиоматичен. Всъщност, ако трябва да решавам същия проблем в Python, вероятно щях да прибегна до анотации. Тоест, нещо от рода на:

@multi
def add(a: Integer, b: Integer):
    return Integer(a.n + b.n)

@multi
def add(a: Rational, b: Rational)
    return Rational(a.num * b.den + b.num * a.den, a.den * b.den)

Обърнете внимание, че горното е въпрос на интерфейс или просто синтактична захар в Python. Имплементацията пак ще разчита на подобна таблица и това отново ще бъде data-directed programming.

Също така, този код ме навежда на интересни размисли. Трите подхода са напълно концептуални. В по-примитивен език (като Scheme), реализация и на трите изглежда идиоматично. Други езици, обаче, натискат кода в различни посоки. Например, в Java определено очаквам да видя обектния подход (вариант две) и първоначално бих бил скептичен към структурния (вариант едно). В Ruby би било подобно на Java, макар че там структурите няма да изглеждат толкова лошо заради по-мощния case оператор. В Haskell и C ще очаквам да видя структурния подход – обектният изглежда чужд. В език като Scala ще очаквам да видя и двата – Scala поддържа както добро ООП, така и добро ФП.

За финал – все пак ще има случаи, в които ще трябва да извъртите езика в неидиоматична за него посока, когато прилагате data-directed programming. Това може да се окаже Greenspun-ване (например @multi в Python). А може и да излезе по-добрата идея. В крайна сметка, създаването на малки domain-specific езици драматично подобрява изразителността на една система. Тук не сме толкова „domain-specific“ – вместо това разширяваме езика. В някои езици се получава много добре (Scheme), в други е поносимо (Python, Ruby, Scala), а при трети съпротивлението е жестоко (Java, C).

И въпросът за един милион е: Кога разширяваме езика и кога се вписваме в рамките му, макар това да е компромис?

5 thoughts on “Data-Directed Programming”

  3. Добре, след като говорихме и си направих труда да го прочета цялото, факт е, че няма много общо с моста.

    По този повод (видях и въпроса отдолу), проблемът с разширяването и мърдането от езика е доста наболял, основно заради програмисти, които мигрират към нов език и директно apply-ват всички стари концепции в нов език (за JavaScript е направо класически пример, тъй като всеки го ползва, идва от различен друг свят и много концепции са силно нестандартни).

    За проекти, в които скоростта не е единственото най-важно нещо, бих предпочел да се пише според спецификите на езика. Това усложнява проблемите с трудно четене на код и навлизане на нови хора, както и вкарването на фреймуърци и библиотеки, които работят на принципа convention over configuration.

  5. Третият вариант качва значително сложността на решението въпреки, че изглежда елегантно, ако имаш един куп различни обекти и методи. Всичко се свежда до това дали наистина имаш един куп обекти и методи и този дизайн ще ти спести главоболия или не. И дали това не е твърде голямо погрозняване на кода – бягане от стила и структурите, които езикът за програмиране предполага.

    Изглежда като нещо, което бих направил преди години, просто защото изглежда яко :P. Сега мотивиращия фактор е ясният и прост дизайн.

Вашият коментар

Вашият имейл адрес няма да бъде публикуван.