понедельник, 31 января 2011 г.

Введение в обобщенное программирование (Generics) - 1


Данная статья выполнена на основе материалов подготовленных Felix John COLIBRI и является переводом, выполненным мной с учетом небольших дополнений и разъяснений.
Обобщённое программирование — это парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание.
В Delphi обобщенное программирование представлено в виде новой конструкции языка – обобщении (generics).

Стек классический

Для того, что бы понять и оценить прелести обобщенного программирования, для начала на примере класса, реализующего стек, рассмотрим реализацию данного стека в классической форме, не используя пока обобщения.
Итак, создадим стек, на основе простого класса TintegerStack:

unit integer_stack;

interface

uses
  sysutils;

type
  TIntegerStack = Class
    ArrayStack: Array of Integer;
    TopOfStack: Integer;

    constructor Create(Length: Integer);
    procedure push(Value: Integer);
    function pop: Integer;
  end;

implementation

constructor TIntegerStack.Create(Length: Integer);
begin
  Inherited Create;
  SetLength(ArrayStack, Length);
end;

procedure TIntegerStack.push(Value: Integer);
begin
  if TopOfStack < Length(ArrayStack) then
  begin
    ArrayStack[TopOfStack] := Value;
    Inc(TopOfStack);
  end;
end;

function TIntegerStack.pop: Integer;
begin
  if TopOfStack >= 0 then
  begin
    Dec(TopOfStack);
    Result := ArrayStack[TopOfStack];
  end
  else
  raise Exception.Create('empty');
end;

end.



Пример использования данного класса приведен ниже:
program Stack_Integer;

uses
  SysUtils,
  integer_stack in 'integer_stack.pas';
var
  Stack: TIntegerStack;
begin // main
  Stack := TIntegerStack.Create(5);
  with Stack do
  begin
    push(111);
    push(222);
    push(333);
    // -- refused by the compiler:
    // push('allistair');
    writeln(pop);
    writeln(pop);
    writeln(pop);
  end; // with Stack
  writeln;
  write('=> integer stack');
  Readln;
end. // main

   
Итак, реализуя классический числовой стек, мы уже столкнулись с некоторыми ограничениями накладываемым компилятором на наш класс.
Во-первых, компилятор твердо знает, что массив стека объявлен как Integer. Соответственно  при попытке занести в стек значения отличное от типа Integer компилятор будет вынужден сгенерировать ошибку.
Во-вторых если мы захотели бы построить стек для другого типа (например, типа String) нам нужно было бы реализовать другой аналогичный по функциональности класс. То есть при реализации стека для нескольких типов у нас бы разрастались однотипные по функциональности классы.

Стек на TObject

Можно было бы выйти из этого положения, например, используя массив TObject, тогда в стек можно было бы добавлять любые классы, наследуемые от данного класса.
Такой стек представлен ниже:
unit object_stack;

interface

type
  TObjectStack = class
    ObjArray: Array of tObject;
    TopOfStack: Integer;
    constructor create(length: Integer);
    procedure push(Value: tObject);
    function pop: tObject;
  end;

implementation

uses SysUtils;

// -- TObjectStack
constructor TObjectStack.create(length: Integer);
begin
  Inherited Create;
  SetLength(ObjArray, length);
end;

procedure TObjectStack.push(Value: tObject);
begin
  if TopOfStack < Length(ObjArray) then
  begin
    ObjArray[TopOfStack] := Value;
    Inc(TopOfStack);
  end;
end;

function TObjectStack.pop: tObject;
begin
  if TopOfStack >= 0 then
  begin
    Dec(TopOfStack);
    Result := ObjArray[TopOfStack];
  end
  else
     raise Exception.Create('empty');
end;

end.


Используя данный стек мы могли добавить в него разные элементы, например Integer:

procedure UseIntegerStack;
var
  Stack: TObjectStack;
begin
  Stack := TObjectStack.Create(5);
  with Stack do
  begin
    push(tObject(111));
    push(tObject(222));
    Writeln(Integer(pop));
    Writeln(Integer(pop));
  end;
end;
Или, например пользовательский объект TPerson:

// -- TPerson stack
type
  TPerson = Class
    FirstName: String;
    Constructor Create(vFirstName: String);
  end;

constructor TPerson.Create(vFirstName: String);
begin
  Inherited Create;
  FirstName := vFirstName;
end;

procedure UsePersonStack;
var
  PersonStack: TObjectStack;
begin
  PersonStack := TObjectStack.Create(5);
  with PersonStack do
  begin
    push(TPerson.Create('ann'));
    // -- accepted here
    push(tObject(222));
    push(TPerson.Create('allistair'));

    writeln(TPerson(pop).FirstName);
    // -- poping an Integer as a TPerson will fail here
    writeln(TPerson(pop).FirstName);
    writeln(TPerson(pop).FirstName);
  end;
end;


Как видите, более универсальный в плане всеядности типов стек все равно породил проблемы, а именно теперь при добавлении числа Integer мы должны приводить данный тип к классу TObject. Фактически преобразование типов выполнено не будет, ведь по сути tObject является 4-байтовым указателем, а тип Integer - 4-байтовым значением.
В мире .Net мире такие вещи реализованы по-другому:
Числовые и строковые значения,  являются классом, у которого есть свои методы, такие как .ToString. Мы можем написать my_integer.ToString, переведя значение переменной в строку, но мы не можем написать 123.ToString. Такие преобразования в классе используются не просто так, как видно на первый взгляд, а довольно сложно на нижнем уровне. Фактически компилятор должен сгенерировать некий код для преобразования.
В нашем же примере как видите, функция Writeln, принимают на печать, переменную tObject как значение типа Integer. Поэтому перед тем как напечатать значение Integer взятое функцией  pop из стека c_person в первом случае
      writeln(pop);
мы можем не делать приведение т.к. возвращаемое значение pop совместимо с Integer (те-же 4-е байта).
Однако если возвращаемое значение является другим объектом (TPerson), то попытка приведения типа Integer к объекту TPerson вызовет ошибку во время выполнения программы. Точно такая же проблема возникнет,  если мы будем приводить некий объект к другому типу (не совместимому с ним). То на этапе компиляции мы не получим ошибку, а на этапе выполнения  - получим. То есть когда мы поместим неправильный объект и попытаемся его извлечь не в той последовательности (пытаясь привести к другому несовместимому типу) мы обнаружим ошибку позже.
Таким образом, данный класс является полиморфным: мы можем хранить объекты разных типов в одном стеке, но поиск и извлечение требует больших усилий и контроля со стороны программиста, фактически чтобы извлечь правильный тип нужно использовать as или is.

Предыдущие примеры были написаны, используя классические возможности Delphi. Однако, несмотря на расширение возможностей класса, мы оказались перед теми же самыми проблемами: или мы пишем код стека, привязанный к определенному типу, или мы используем приведение типов, с риском в процессе работы столкнутся с исключениями.
Например, в Delphi .Net такой код:

//******************************************************************************
//   DELPHI .NET
//******************************************************************************
program ArrayOfObject;

uses
  System.Collections;

type
  TPerson = Class
    FirstName: String;
    Constructor Create(vFirstName: String);
  end; // TPerson

  // -- TPerson

constructor TPerson.Create(vFirstName: String);
begin
  Inherited Create;
  FirstName := vFirstName;
end; // createp_person

procedure UsePersonArrayList;
var
  PersonList: ArrayList;
  Person: TPerson;
begin
  PersonList := ArrayList.Create;

  PersonList.Add(TPerson.Create('Miller'));
  PersonList.Add(TPerson.Create('Smith'));
  // -- this is accepted
  PersonList.Add('xxx');

  // -- the 'xxx' entry will trigger an exception
  for Person in PersonList do
      writeln(Person.FirstName);
end; // UsePersonArrayList

begin
  UsePersonArrayList;
  writeln;
  write('=> type enter');
  Readln;
end.


тоже потенциально опасен. Как видите мы можем добавлять объекты без приведения типа, так как объект  TPerson - потомок TObject. В конструкции FOR IN мы видим, что приведение типов не используется. И тут кроется потенциальная опасность. Фактически компилятор делает приведение для нас внутри, и мы все еще получаем потенциальную  возможность генерирования исключения во время пробега по циклу, если помещенный в массив объект не имеет ожидаемого типа.
Как видите классический подход, имеет свои недостатки, которые мы постараемся избежать с помощью обобщенного программирования.





14 комментариев:

  1. Стиль оформления кода - имхо ужасен.

    ОтветитьУдалить
  2. >> Стиль оформления кода - имхо ужасен.

    Ну сорри,я так и не научился оформлять код, для нормальной публикации на блоге. Может посоветуете инструмент для номального оформления, что бы html генерировал корректно для вставки в блог.

    ОтветитьУдалить
  3. Увы встроенный редактор очень кривой

    ОтветитьУдалить
  4. Дмитрий, гляньте на
    Syntax Highlighter.

    Это то, что стоит у меня в блоге.

    Подключение.

    ОтветитьУдалить
  5. >> Дмитрий, гляньте на
    >> Syntax Highlighter.
    >> Это то, что стоит у меня в блоге.

    Спасибо, попробую разобраться

    ОтветитьУдалить
  6. >> Syntax Highlighter

    Я как понял он использует JavaScript, т.е. для его работы нужно размещать на хостинге скрипты и стили. На бесплатном хостинге увы такое невозможно, тут как раз более нужен инструмент что бы он генерировал страницу в одном html

    ОтветитьУдалить
  7. мне дак кажется что первый коммент был направлен более на именование классов и т.п а не форматирование кода. т.е в такой сишной нотации.
    а-ля c_person вместо TPerson или c_integer_stack и TIntegerStack
    tObject..

    ОтветитьУдалить
  8. >> мне дак кажется что первый коммент был направлен более на именование классов и т.п а не форматирование кода. т.е в такой сишной нотации.
    а-ля c_person вместо TPerson или c_integer_stack и TIntegerStack
    tObject..

    Автор именование делал по правилам:

    Все константы используют префикс k_
    Типы - префикс t_
    global VAR - g_
    local VAR - l_
    параметры - p_
    функции - f_

    и так далее, вернее он придерживался каких-то своих стандартов на описание переменных типов и пр

    ОтветитьУдалить
  9. ну это понятно что исходный код приведен каким он был в оригинале статьи и в нем есть свои принципы именования, но подавляющему большинству он будет непривычен.
    поэтому имхо для хорошей читаемости лучше было бы переписать код используя более распространенные принципы.

    ОтветитьУдалить
  10. Сначала хотел похвалить, мол как здорово, сейчас мне конструктивно покажут пользу дженериков, но стоило дойти до первого примера...

    Дмитрий, Вам стоит прислушаться замечаний, по поводу форматирования кода и по поводу именования идентификаторов.
    Подсветка синтаксиса - это лишь разукрашивание текста, читаемости (особенно для делфистов) она практически не прибавит.
    Тем более статья рассчитана на начинающих, и затуманивать голову своими принципами - ИМХО сродни эгоизму.

    P.S.: для подключения Syntax Highlighter не обязательно хранить скрипты где-то у себя. Посмотрите здесь: http://alexgorbatchev.com/SyntaxHighlighter/hosting.html

    ОтветитьУдалить
  11. >> Николай Зверев

    Ну раз народ просит, тогда переделаем. Хотя на самом деле, т.к. данный пост является так сказать переводом авторских работ с незначительными правками - не хотелось бы изменять код. Ну раз народу не привычно - то переделаю.

    ОтветитьУдалить
  12. Спасибо большое за статью, ждем продолжения с нетерпением, но если не сложно, то еще +1 за нормальное именование.

    ОтветитьУдалить
  13. А по мне это уже избитая тема. По дженерикам информации более чем достаточно. В рунете есть серия переводов на tdelphi. Лучше описывать что-то новое, свое. Да и обобщенный стэк в RTL уже реализован.

    ОтветитьУдалить