Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

delphi и обобщенное прораммирование

Страницы: < 1 2
vlk32 © (2011-11-01 15:20:00)
Хотел бы узнать мнение уважаемого сообщества по такой вот скользкой теме как обобщенное программирование. Сразу скажу, что я понимаю под этим два аспекта:
- структуры данных с обобщенным типом элементов (контейнеры)
- обобщенные алгоритмы над контейнерами

Недавно я предпринял попытку написать свою библиотеку, используя генерики (несмотря на то, что они пока "сырые"). Прошелся по нескольким граблям, посмотрел как сделаны коллекции по умолчанию в Delphi, как тоже самое устроено в STL и C#. И пришел к таким выводам (поправьте меня, если в чем то неправ), о том как можно все устроить.

0. Эталонный подход STL
[container] <--> [iterator] <--> [generic algorithm]

Пример
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
for ( ; first!=last; ++first ) f(*first);
return f;
}

Использование
for_each (myvector.begin(), myvector.end(), myfunction);

Обратите внимание - никакой информации об обобщенном типе в вызове for_each не используется. Возможно это тема для дискуссии, но мое мнение - реализовать подобную функциональность и синтаксис в таком же примерно виде в delphi даже с использованием генериков и анономных процедур не представляется возможным

Остаются следующие варианты

1.
Контейнеры выполнены индивидуально.
Каждый контейнер максимально эффективно реализует собственную функциональность с учетом особенностей внутренней структуры хранения элементов.
Семантически идентичные функции вполне могутиметь различный синтаксис. Например, добавление элемента в конец контейнера:
для массива procedure Add(item:T);
для списка procedure AddNode(node:TListNode);
для стека procedure Push(const Value: T); и т.д. и т.п.
Так сделано в Generics.Collections где все контейнеры унаследованы от TEnumerable<T> - беспонтового класса необходимого только для того чтобы с этими контейнерами писать for item in <container> do begin ..do some with item end;
Естественно, что ни о каких обобщенных алгоритмах речи не идет. Т.е. вся экстра-функциональность впихивается либо в базовый контейнер либо в его потомков. И так для каждого контейнера по отдельности.

2.
Контейнеры унаследованы от некоего базового класса (TIterator), который описывает максимально возможную функциональность итератора/курсора, т.е. возможность устанавливать курсор на требуемый элемент контейнера, перемещать курсор, читать/писать в элемент под курсором, вставлять/удалять элементы т.д. Каждый наследник переопределяет те функции курсора, которые он реально поддерживает, а на остальные вешает генерацию исключений. Кроме того наследник определяет несколько функций которые возвращают готовые курсоры на начало, конец, произвольную позицию в контейнере. Сам курсор может быть записью такого типа
Cursor = record flags : <состояние курсора>; Owner : TIterator; <<< ссылка на владельца курсора case <тип контейнера> of Array: ( position : Integer); List: (dnode : TListNode); < и т.д. > end;
Обобщенные алгоритмы получают на вход контейнеры и курсоры для реализации своей функциональности.
Этот подход хорош тем, что в объявлении Cursor не указан никакой обобщенный тип, соответственно все курсоры это один и тот же тип, а вся конкретика реализована через функции владельца курсора. Курсоры могут копироваться и присваиваться. Никаких новых объектов при этом не создается.
Так сделано в мощнейшей для своего времени библиотеке DeCAL.

jack128_ (2011-11-04 23:03:00) [21]
Скажу как бы я делал, если бы не глюки компилятора, то есть в будущих(выше 2010) версиях такое( может быть) и прокатит.

Собственно - копия LINQ. Без хелперов к интерфейсам и дженерик классам - это выглядело бы примерно так:

ILinqEnumerable<T> = interface(IEnumerable<T>) function Select<T, TResult>(Selector: TFunc<T, TResut>): ILinqEnumerable<TResult>; function Where<T, T>(Predicte: TFunc<T, boolean>): ILinqEnumerable<T>; .... // и так далее end; TLinqEnumerableImpl<T> = class contructor Create(AEnum: IEnumerable<T>); function Select<T, TResult>(Selector: TFunc<T, TResut>): ILinqEnumerable<TResult>; function Where<T, T>(Predicte: TFunc<T, boolean>): ILinqEnumerable<T>; // и так далее end; TMyList<T> = class(TInterfacedObject, IEnumerable<T>, ILinqEnumerable<T>) private LinqEnum: ILinqEnumerable<T> read FLinqEnum implements ILinqEnumerable<T>; // FLinqEnum := TLinqEnumerableImpl<T>.Create(Self); public property Items[Index: Integer]: T read; write; end;
В зависимости от реализации TLinqEnumerableImpl генерация последовательностей может быть ленивая или нет.

ну и пример использования:

MyList .Where(MyFilterFunc) .GroupBy(MyGroupProc) .Select(MySelectProc);

но естественно - все это не взлетит. Синтаксис лямбд убог и с этин котжировцы ничего не хотят делать..

vlk32 (2011-11-04 14:58:00) [22]
b.range(0,8) - да тут объект b создает новый объект типа TRange - обобщенное описание некоего подмножества элементов из b. Конечно сами элементы в этом новом объекте не хранятся. Т.к. этот объект нужен исключительно в обобщенном алгоритме то логично будет его в этом же алгоритме и освободить в конце когда он уже не нужен.

Anatoly Podgoretsky (2011-11-04 14:48:00) [23]
А вам бежать на C# или не делать странного.

_Юрий (2011-11-04 14:29:00) [24]

> vlk32 (04.11.11 11:27) [14]

> Ну как бы я исходил из того что тот же ForEach - это ведь
> просто перебор элементов контейнера (заметьте, не обязательно
> всех от первого до последнего) и выполнение некой операции
> с этими элементами. Т.е. такую штуку можно сделать с любым
> контейнером. Т.е. это обобщенный алгоритм. Я его написал
> один раз и для любого контейнера который поддерживает итераторы
> его можно применить.

ну и в случае через GetEnumeator тоже самое - не обязательно все элементы возвращаются, зависит от реализации.
Объявить интерфейс IEnumerable<T> c методом GetEnumerator. В D2010 такой ход не прошел по причине ошибок компилятора
Если бы язык позволял делать хелперы к интерфейсам, то можно было бы раскрутиться отсюда, было бы все удобно. Но поддержки хелперов вроде не предвидится.

по поводу let.foreach<TMyRec>(b.range(0,8),MyPerfectAction);
Тут возникает единственный вопрос - кто управляет временем жизни этого самого результата от b.range? Это ведь некий контейнер, результат фильтрации изначального, очевидно, уже другой инстанс.
В этих ваших сишарпах все просто - там сборщик мусора. А нам тут как быть?

vlk32 (2011-11-04 11:27:00) [25]
Ну как бы я исходил из того что тот же ForEach - это ведь просто перебор элементов контейнера (заметьте, не обязательно всех от первого до последнего) и выполнение некой операции с этими элементами. Т.е. такую штуку можно сделать с любым контейнером. Т.е. это обобщенный алгоритм. Я его написал один рази для любого контейнера который поддерживает итераторы его можно применить. И таких алгоритмов - около сотни. Вы на минутку можете себе представить контейнер который все это будет реализовать внутри себя? А если контейнеров десять штук?

Идем далее. Я например могу написать вот так

var a,b : TBaseArray<TMyRec>; .. init a .. b := let.extract<TMyRec>(a.range(MySelector)); let.foreach<TMyRec>(b.range(0,8),MyPerfectAction);

Вот и функция экстракт стала обобщенным алгоритмом - и ее теперь не надо тулить во все контейнеры. А ForEach уже умеет перебирать в заданном диапазоне. А диапазон может быть указан вот так

var indexes : Array_Of_<integer>; N : Integer; b.range(iAll) b.range(7,N) b.range(Indexes) b.range(function(const Item:TMyRec; const I:Integer):Boolean begin Result := (Item.MyField > N) and (Item.MyField2 in [colBlack,colRed,colGreen]); end;)

Удобно, правда?

Конечно, надо понимать, что вся эта универсальность и гибкость в ущерб производительности.

_Юрий (2011-11-04 10:15:00) [26]

> jack128_ (04.11.11 00:14) [10]

> кстати, а какой интерфейс для выборок у вас получился??

В общем то, такой же. Только там вместо 'select... ' RTTI-шный построитель запроса на аттрибутах.

> vlk32 (04.11.11 00:46) [12]
> О ла ла. А а в XE2 все нормально. Это радует.
>
>

Вот так. Интересно. Мы на 2010 тренировались.

> class procedure let.foreach<T>(const C:TIterable<T>; const
> Action:TActionProc1<T>);

Я не понял, почему вы делаете это через внешний статический класс, почему не сделать ForEach у самого контейнера?
И кстати, учитывая громоздкость лямбд, лучше на мой взгляд делать обычный цикл через стандартный энумератор.

Сравните:

for X in Container do
Summa := Summa + X.Value;

или же

Container.ForEach(procedure(X: TMyObject)
begin
Summa := Summa + X.Value;
end);

второй вариант более громоздкий, следовательно он хуже.

А вот реализация энумератора должна быть своя для каждого типа контейнера, и пользователь должен быть абстрагирован от этой реализации.
В варианте цикла for in это как раз и достигается.

vlk32 (2011-11-04 00:46:00) [27]
О ла ла. А а в XE2 все нормально. Это радует.

vlk32 (2011-11-04 00:22:00) [28]
Удалено модератором

jack128_ (2011-11-04 00:14:00) [29]

> _Юрий (03.11.11 17:18) [9]

кстати, а какой интерфейс для выборок у вас получился?? Мы в результате что то типа такого получили
for Obj in Storage.Select<TMyObject>('select ... ', True) do begin end; // если второй параметр - True, объект Obj сам уничтожится в конце итерации, если False - сами должны уничтожать.

Ну набор вспомогательных хелперов типа:

MyObjectList := Storage.SelectList<TMyObject>('select ...'); MyObj := Storage.SelectObject<TMyObject>('select ...'); for Obj in Storage.SelectAll<TMyObject>(True) do // имя таблицы берется из атрибута навешанного на класс TMyObject и т д..

_Юрий (2011-11-03 17:18:00) [30]

> я пока до таких
> ситуаций не доходил

C ORM как раз дошли. Причем сам по себе фреймворк компилировался. Не компилировалась попытка его использования уже в приложении. Причем интерфейс фреймворка был пока без реализации, а других вариантов интерфейса особо и не было, учитывая громоздкость языка.
Вот и думай тут, какие изменения отменять. В результате пляски с бубном, попытки скомплироваться за счет ухудшения качества интерфейса, испорченное настроение, демотивация. Как то так

_Юрий (2011-11-03 17:07:00) [31]

> vlk32 (02.11.11 22:41) [7]
>

> Правда иногда возникает такая комбинация кода когда уже
> и это не помогает и тогда надо смотреть что ты написал в
> крайние пять минут и отказаться от этого. я пока до таких
> ситуаций не доходил. но это чисто техническая проблема и
> я надеюсь эмбаркодеро её пофиксит.

особенно весело бывает, когда проводишь рефакторинг, и проект пару дней вообще не собирается, а потом наконец то должен собраться - и нате вам, internal error, отменяйте последние изменения. На "пофиксит" надежда слабая.

> jack128_ (02.11.11 22:19) [6]

> меня от написания своей библиотеки алгоритмов для коллекций
> остановило прежде всего внезапные глюки компилятора в неожиданных
> местах. Это я говорю по итогам написания light ORM, которую
> у нас в конторе написали. Наверно процентов 40% времени
> было потрачено на переделку кода, что бы он банально скомпилировался,
> банально всякие интернал ерроры запарили.

Во, у нас тоже самое случилось.
И лямбды эмберкадеро сделали ужасно. И мусор не собирается. И yield return нету. В общем, не взлетит.
Берем Generics.Collections и наслаждаемся тем, что имеем )

vlk32 (2011-11-02 22:41:00) [32]
интернал ероры решаются периодическим жмаком по клавишам Shift+F9

Правда иногда возникает такая комбинация кода когда уже и это не помогает и тогда надо смотреть что ты написал в крайние пять минут и отказаться от этого. я пока до таких ситуаций не доходил. но это чисто техническая проблема и я надеюсь эмбаркодеро её пофиксит.

let.foreach(a);

[DCC Error] test.pas(169): E2010 Incompatible types: 'TBaseArray<test.let.foreach.T>' and 'TBaseArray<System.Real>'

let.foreach<real>(a);

OKAY

так что я уверен что иначе - никак. компилятор требует точно указать тип в конце концов. по другому он пока не может.

jack128_ (2011-11-02 22:19:00) [33]

> algo.reverse<integer>(mylist);

ты уверен, что нужно писать именно так??
такой код: algo.reverse(mylist);
не работает??

> уже честно говоря задумываюсь, а нафига оно надо? Но именно
> потому я и пишу в теме. Может я слепой и просто не вижу
> правильного логичного и красивого варианта реализации этой
> кухни в делфи?

меня от написания своей библиотеки алгоритмов для коллекций остановило прежде всего внезапные глюки компилятора в неожиданных местах. Это я говорю по итогам написания light ORM, которую у нас в конторе написали. Наверно процентов 40% времени было потрачено на переделку кода, что бы он банально скомпилировался, банально всякие интернал ерроры запарили.

Ну и конечно неудобоваримый синтаксис лямбд тоже внес свою лепту.

vlk32 (2011-11-02 19:59:00) [34]
Algo2 = class
class procedure ForEach<T>(C:TContainer<T>; Action:TActionOverSingleItem<T>);
end

хрен редьки не слаще. есть два варианта и оба они к сожалению беспонтовые

algo<integer>.reverse(mylist);

algo.reverse<integer>(mylist);

Вот из за того что каждый раз надо будет прописывать тип и левое имя вместо

reverse(mylist);

уже честно говоря задумываюсь, а нафига оно надо? Но именно потому я и пишу в теме. Может я слепой и просто не вижу правильного логичного и красивого варианта реализации этой кухни в делфи?

jack128_ (2011-11-02 17:52:00) [35]

> Использование
> for_each (myvector.begin(), myvector.end(), myfunction);
>
>
> Обратите внимание - никакой информации об обобщенном типе
> в вызове for_each не используется. Возможно это тема для
> дискуссии, но мое мнение - реализовать подобную функциональность
> и синтаксис в таком же примерно виде в delphi даже с использованием
> генериков и анономных процедур не представляется возможным

Обычному разработчику невозможно. А вот разработчикам компилятора вполне возможно, что они сделали встроив аналог for_each(цикл for .. in .. ) в язык.
Другое дело, что другие алгоритмы по аналогу с std конечно не получится реализовать, хотя бы из за отсутствия в delphi утиной типизации.

> Контейнеры унаследованы от некоего базового класса (TIterator),
> который описывает максимально возможную функциональность
> итератора/курсора, т.е. возможность устанавливать курсор
> на требуемый элемент контейнера, перемещать курсор, читать/писать
> в элемент под курсором, вставлять/удалять элементы т.д.
> Каждый наследник переопределяет те функции курсора, которые
> он реально поддерживает, а на остальные вешает генерацию
> исключений.

ИМХО - отстойный вариант, потому что это по сути отход от статической типизации.

procedure MyFunc(Iter: TIterator<T>)
begin // на этапе компиляции - я не знаю, могу ли я добавлять/удалять элементы в контейнер.
end;

> Использование интерфейсов. Вся функциональность итератора/курсора
> разбивается на несколько интерфейсов по уровню функциональности
> (или какому то другому критерию). Все контейнеры которые
> мы хотим задействовать в обобщенных алгоритмах должны наследовать
> и реализовать интерфейсы курсора. В данном подходе никаких
> отдельных курсоров (в виде объектов или записей) не используется.
>

В C# не используется. Почему в дельфи нельзя использовать?

> Algo<T> = class
> class procedure ForEach(C:TContainer<T>; Action:TActionOverSingleItem<T>);
>
> end;
>
> И вот такой дикий вызов мы в результате получаем Algo<TMyRec>.
> ForEach(MyList,DoClearMyRecord) Кстати этим же будет страдать
> любая попытка сделать обобщенный алгоритм средствами языка
> delphi.

В теории можно написать так:
Algo2 = class
class procedure ForEach<T>(C:TContainer<T>; Action:TActionOverSingleItem<T>);
end

вызов
Algo2.ForEach(C, Action);

А любая попытка сделать обобщенный алгоритм в дельфи будет страдать прежде всего от глюков компилера.

vlk32 (2011-11-02 14:18:00) [36]
Меня такой подход уже не устраивает. Потому что ничего путного по ходу дела не накрутится. Библиотеки с костылями у меня есть. Теперь же хочется изначально все спланировать.

Cobalt (2011-11-02 13:25:00) [37]
я полагаю, что лучше все-таки танцевать от задачи.
А дополнительные слои абстракции сами накрутятся на колеса процесса разработки.

vlk32 (2011-11-01 15:21:00) [38]
<продолжение>
3.
Использование интерфейсов. Вся функциональность итератора/курсора разбивается на несколько интерфейсов по уровню функциональности (или какому то другому критерию). Все контейнеры которые мы хотим задействовать в обобщенных алгоритмах должны наследовать и реализовать интерфейсы курсора. В данном подходе никаких отдельных курсоров (в виде объектов или записей) не используется. В обобщенные алгоритмы передаются контейнеры и дополнительные параметры необходимые для выполнения конкретной операции (например индекс стартового элемента, индексы начала и конца диапазона и т.п.).
Так сделано в C#. Этот подход кажется мне не совсем удачным в таком плане:
- в обобщенные алгоритмы надо будет передавать индексы элементов вместо курсора. При этом для каких то типов контейнеров лучше чтобы это были именно целочисленные индексы, а для других указатели на элемент контейнера, т.о. на лицо нарушение общности.
- т.к. контейнер объявлен с обобщенным типом, то и обобщенная процедура также должна быть объявлена с обобщенным типом, т.е.
procedure ForEach<T>(C:TContainer<T>; Action:TActionOverSingleItem<T>); что не даст нам реализовать это через глобальную процедуру. Один из выходов сделать так:

Algo<T> = class class procedure ForEach(C:TContainer<T>; Action:TActionOverSingleItem<T>); end; И вот такой дикийвызов мы в результате получаем Algo<TMyRec>.ForEach(MyList,DoClearMyRecord) Кстати этим же будет страдать любая попытка сделать обобщенный алгоритм средствами языка delphi.

4. Подход который я тестирую в настоящее время

Описываются курсоры двух типов:
TIterator<T> = class(TObject) - для одиночного значения
TRange<T>= class(TObject) - для диапазона значений (от А до Б, массив индексов и т.д.)

Все контейнеры наследуются от

TIterable<T> = class abstract

public

function Iterator(const S:TIteratorState):TIterator<T>; overload; virtual; abstract;
function Iterator(const I:Integer):TIterator<T>; overload; virtual; abstract;
function Iterator(const V:T):TIterator<T>; overload; virtual; abstract;
// function Range(const A,B:Integer):TRange<T>; overload; virtual; abstract;
// function Range(const Indexes:array of Integer):TRange<T>; overload; virtual; abstract;

end;

т.е. каждый контейнер должен уметь вернуть курсор (см. как в Generics.Collections возвращается енумератор). При этом в курсор внедряются все необходимые данные, методы, эффективно переопределяются существующие методы с учетом местной специфики и т.п. (естественно все это не будет доступно в обобщенном алгоритме, кроме определенного в TIterator) Само объявление курсора примерно такое

// uniform access to TContainer<T> via single item TIterator<T> = class(TObject) protected FFlags : TIteratorFlags; FInd : Integer; FPtr : Pointer_To_<T>.Ptr; function GetIsBack: Boolean; function GetIsBidirectional: Boolean; function GetIsFirst: Boolean; function GetIsForward: Boolean; function GetIsFront: Boolean; function GetIsItem: Boolean; function GetIsLast: Boolean; function GetIsRandom: Boolean; function GetItem: T; procedure SetIndex(const Value: Integer); procedure SetItem(const Value: T); public constructor Create; // positioning function Prev(const By:Integer=1):Integer; virtual; function Next(const By:Integer=1):Integer; virtual; // modify container storage function Insert(const Item:T):Integer; virtual; abstract; function Remove:Integer; virtual; abstract; // compare with other iterator function eq(const i:TIterator<T>):Boolean; virtual; function ab(const i:TIterator<T>):Boolean; virtual; function ls(const i:TIterator<T>):Boolean; virtual; function le(const i:TIterator<T>):Boolean; virtual; function ae(const i:TIterator<T>):Boolean; virtual; function dist(const i:TIterator<T>):Integer; virtual; // item access property Val:T read GetItem write SetItem; property Ptr:Pointer_To_<T>.Ptr read FPtr; property Ind:Integer read FInd write SetIndex; // state property IsForward:Boolean read GetIsForward; property IsBidirectional:Boolean read GetIsBidirectional; property IsRandom:Boolean read GetIsRandom; property Flags:TIteratorFlags read FFlags; property IsFront:Boolean read GetIsFront; property IsFirst:Boolean read GetIsFirst; property IsLast:Boolean read GetIsLast; property IsBack:Boolean read GetIsBack; property IsItem:Boolean read GetIsItem; end;

Тут есть проблемы с безопасностью курсора т.к. дается прямая ссылка на элемент в контейнере
property Ptr:Pointer_To_<T>.Ptr read FPtr;
С другой стороны это эффективный доступ к элементу и кроме того возможность использовать его как позицию (вместо индекса) для списков и деревьев.
Вторая плохая новость это то что итератор требует обобщенного типа, что не даст возможность объявить обобщенный алгоритм как

interface

procedure SomeAlgorithm(FromPos:TIterator; ToPos:TIterator; const Action:TActionFunc);

И вот наконец вопрос уважаемой общественности. Какой же все таки метод использовать с учетом текущих возможностей и ограничений языка delphi для реализации обобщенной библиотеки контейнеров и алгоритмов? Возможно есть какие то более продвинутые подходы чем те, которые описал я?

Страницы: < 1 2

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »