Вижте силата на параметричния полиморфизъм

Да предположим, че искате да внедрите списъчен клас в Java. Започвате с абстрактен клас, Listи два подкласа Emptyи съответно Consпредставляващи празни и непразни списъци. Тъй като планирате да разширите функционалността на тези списъци, вие проектирате ListVisitorинтерфейс и осигурявате accept(...)куки за ListVisitors във всеки от подкласовете си. Освен това вашият Consклас има две полета firstи restсъс съответните методи за достъп.

Какви ще бъдат типовете на тези полета? Ясно е, че restтрябва да е от тип List. Ако предварително знаете, че вашите списъци винаги ще съдържат елементи от даден клас, задачата за кодиране ще бъде значително по-лесна в този момент. Ако знаете, че всички елементи от списъка ви ще бъдат integers, например, можете да зададете firstда бъдат от тип integer.

Ако обаче, както често се случва, не знаете тази информация предварително, трябва да се задоволите с най-рядко срещания суперклас, който има всички възможни елементи, съдържащи се във вашите списъци, което обикновено е универсалният референтен тип Object. Следователно вашият код за списъци с различни типови елементи има следната форма:

абстрактен клас Списък {публичен абстрактен обект приема (ListVisitor that); } интерфейс ListVisitor {публичен обект _case (Изпразнете това); публичен обект _case (против това); } class Empty extends List {public Object accept (ListVisitor that) {return that._case (this); }} class Cons разширява Списък {first Object first; частен списък почивка; Против (Object _first, List _rest) {first = _first; почивка = _почивка; } public Object first () {return first;} public List rest () {return rest;} public Object accept (ListVisitor that) {return that._case (this); }}

Въпреки че програмистите на Java често използват най-рядко срещания суперклас за дадено поле по този начин, подходът има своите недостатъци. Да предположим, че създавате a, ListVisitorкойто добавя всички елементи от списък от Integers и връща резултата, както е показано по-долу:

клас AddVisitor реализира ListVisitor {private Integer zero = new Integer (0); public Object _case (Empty that) {return zero;} public Object _case (Cons that) {return new Integer (((Integer) that.first ()). intValue () + ((Integer) that.rest (). accept (това)). intValue ()); }}

Обърнете внимание на изричните отливки Integerвъв втория _case(...)метод. Многократно извършвате тестове по време на изпълнение, за да проверите свойствата на данните; в идеалния случай компилаторът трябва да извърши тези тестове вместо вас като част от проверка на типа програма. Но тъй като не ви е гарантирано, че AddVisitorще се прилага само за Lists от Integers, проверката на типа Java не може да потвърди, че всъщност добавяте две Integers, освен ако не са налице ролите.

Потенциално бихте могли да получите по-точна проверка на типа, но само чрез жертване на полиморфизъм и дублиране на код. Можете например да създадете специален Listклас (със съответстващи Consи Emptyподкласове, както и специален Visitorинтерфейс) за всеки клас от елемент, който съхранявате в List. В горния пример бихте създали IntegerListклас, чиито елементи са Integers. Но ако искате да съхраните, да речем, Booleans на друго място в програмата, ще трябва да създадете BooleanListклас.

Ясно е, че размерът на програма, написана с помощта на тази техника, ще се увеличи бързо. Има и други стилистични проблеми; един от основните принципи на доброто софтуерно инженерство е да има една точка за контрол за всеки функционален елемент на програмата и дублирането на код по този начин за копиране и поставяне нарушава този принцип. Това често води до високи разходи за разработка и поддръжка на софтуера. За да разберете защо, помислете какво се случва, когато бъде намерена грешка: програмистът ще трябва да се върне и да коригира тази грешка отделно във всяко направено копие. Ако програмистът забрави да идентифицира всички дублирани сайтове, ще бъде въведена нова грешка!

Но, както илюстрира примерът по-горе, ще ви е трудно да поддържате едновременно контролна точка и да използвате статични проверки, за да гарантирате, че определени грешки никога няма да възникнат при изпълнение на програмата. В Java, както съществува днес, често нямате друг избор, освен да дублирате код, ако искате точна статична проверка на типа. Със сигурност никога не бихте могли да премахнете изцяло този аспект на Java. Някои постулати на теорията на автоматите, доведени до техния логичен завършек, предполагат, че никоя система от звуков тип не може да определи точно набора от валидни входове (или изходи) за всички методи в програмата. Следователно, всеки тип система трябва да постигне баланс между собствената си простота и изразителността на получения език; системата тип Java се навежда твърде много в посока на простотата. В първия пример,една малко по-изразителна система от тип би ви позволила да поддържате точна проверка на типа, без да се налага да дублирате код.

Такава експресивна система от типове би добавила родови типове към езика. Общите типове са променливи на типа, които могат да бъдат създадени с подходящо специфичен тип за всеки екземпляр на клас. За целите на тази статия ще декларирам променливи на типа в ъглови скоби над дефиниции на клас или интерфейс. Тогава обхватът на променлива от тип ще се състои от тялото на дефиницията, в която е декларирана (без extendsклаузата). В този обхват можете да използвате променливата тип навсякъде, където можете да използвате обикновен тип.

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

абстрактен клас Списък {публичен резюме T приема (ListVisitor това); } интерфейс ListVisitor {публичен T _case (Изпразнете това); публичен T _case (Против това); } class Empty extends List {public T accept (ListVisitor that) {return that._case (this); }} class Cons разширява списъка {private T first; частен списък почивка; Против (T _first, Списък _rest) {first = _first; почивка = _почивка; } public T first () {return first;} public List rest () {return rest;} public T accept (ListVisitor that) {return that._case (this); }}

Сега можете да пренапишете, за AddVisitorда се възползвате от общите типове:

клас AddVisitor реализира ListVisitor {private Integer zero = new Integer (0); публичен Integer _case (Изпразнете това) {върнете нула;} public Integer _case (Cons that) {return new Integer ((that.first ()). intValue () + (that.rest (). accept (this)). intValue ()); }}

Забележете, че изричните отливки Integerвече не са необходими. Аргументът thatкъм втория _case(...)метод се декларира като Cons, като създава променлива на типа за Consкласа с Integer. Следователно, статичната проверка на типа може да докаже, че that.first()ще бъде от тип Integerи която that.rest()ще бъде от тип List. Подобни инстанции биха се правили всеки път, когато се появява нов екземпляр на Emptyили Consсе декларира.

В горния пример променливите на типа могат да бъдат създадени с всякакви Object. Можете също така да предоставите по-специфична горна граница на променлива от тип. В такива случаи можете да посочите тази граница в декларацията на променливата на типа със следния синтаксис:

  удължава  

Например, ако искате вашето Lists да съдържа само Comparableобекти, можете да дефинирате трите си класа, както следва:

class List {...} class Cons {...} class Empty {...} 

Въпреки че добавянето на параметризирани типове към Java ще ви даде предимствата, показани по-горе, това не би си струвало, ако това означаваше да жертвате съвместимостта със стария код в процеса. За щастие такава жертва не е необходима. Възможно е автоматично да се превежда код, написан в разширение на Java, който има общи типове, в байт код за съществуващия JVM. Няколко компилатори вече правят това - компилаторите Pizza и GJ, написани от Мартин Одерски, са особено добри примери. Пицата беше експериментален език, който добави няколко нови функции към Java, някои от които бяха включени в Java 1.2; GJ е наследник на Pizza, който добавя само общи видове. Тъй като това е единствената добавена функция, компилаторът GJ може да създаде байт код, който работи безпроблемно с наследения код. Той компилира източник в байт код чрезизтриване на типа, което замества всеки екземпляр на всяка променлива на типа с горната граница на тази променлива. Също така позволява променливите на типа да бъдат декларирани за конкретни методи, а не за цели класове. GJ използва същия синтаксис за родови типове, който използвам в тази статия.

Работа в процес на осъществяване

В университета Райс, технологичната група за програмни езици, в която работя, внедрява компилатор за съвместима нагоре версия на GJ, наречена NextGen. Езикът NextGen е разработен съвместно от професор Робърт Картрайт от отдела за компютърни науки на Райс и Гай Стийл от Sun Microsystems; добавя способността да се извършват проверки по време на изпълнение на променливите на типа към GJ.

Another potential solution to this problem, called PolyJ, was developed at MIT. It is being extended at Cornell. PolyJ uses a slightly different syntax than GJ/NextGen. It also differs slightly in the use of generic types. For example, it does not support type parameterization of individual methods, and currently, doesn't support inner classes. But unlike GJ or NextGen, it does allow type variables to be instantiated with primitive types. Also, like NextGen, PolyJ supports runtime operations on generic types.

Sun has released a Java Specification Request (JSR) for adding generic types to the language. Unsurprisingly, one of the key goals listed for any submission is the maintenance of compatibility with existing class libraries. When generic types are added to Java, it is likely that one of the proposals discussed above will serve as the prototype.

There are some programmers who are opposed to adding generic types in any form, despite their advantages. I'll refer to two common arguments of such opponents as the "templates are evil" argument and the "it's not object oriented" argument, and address each of them in turn.

Are templates evil?

C++ uses templates to provide a form of generic types. Templates have earned a bad reputation among some C++ developers because their definitions are not type checked in parameterized form. Instead, the code is replicated at each instantiation, and each replication is type checked separately. The problem with this approach is that type errors might exist in the original code that don't show up in any of the initial instantiations. These errors can manifest themselves later if program revisions or extensions introduce new instantiations. Imagine the frustration of a developer using existing classes that type check when compiled by themselves, but not after he adds a new, perfectly legitimate subclass! Worse still, if the template is not recompiled along with the new classes, such errors will not be detected, but will instead corrupt the executing program.

Because of these problems, some people frown upon bringing templates back, expecting the drawbacks of templates in C++ to apply to a generic type system in Java. This analogy is misleading, because the semantic foundations of Java and C++ are radically different. C++ is an unsafe language, in which static type checking is a heuristic process with no mathematical foundation. In contrast, Java is a safe language, in which the static type checker literally proves that certain errors cannot occur when the code is executed. As a result, C++ programs involving templates suffer from myriad safety problems that cannot occur in Java.

Moreover, all of the prominent proposals for a generic Java perform explicit static type checking of the parameterized classes, rather than just doing so at each instantiation of the class. If you're worried that such explicit checking would slow down type checking, rest assured that, in fact, the opposite is true: since the type checker makes only one pass over the parameterized code, as opposed to a pass for each instantiation of the parameterized types, the type checking process is expedited. For these reasons, the numerous objections to C++ templates do not apply to the generic type proposals for Java. In fact, if you look beyond what has been widely used in the industry, there are many less popular but very well-designed languages, such as Objective Caml and Eiffel, that support parameterized types to great advantage.

Обектно ориентирани ли са системите от родов тип?

И накрая, някои програмисти възразяват срещу всяка система от общ тип с мотива, че тъй като такива системи първоначално са разработени за функционални езици, те не са обектно ориентирани. Това възражение е фалшиво. Родовите типове се вписват съвсем естествено в обектно-ориентирана рамка, както показват примерите и дискусиите по-горе. Но подозирам, че това възражение се корени в липсата на разбиране за това как да се интегрират родови типове с полиморфизма на наследяване на Java. Всъщност такава интеграция е възможна и е в основата на нашето внедряване на NextGen.