🚀 go-pugleaf

Followup-To: pl.comp.programming,pl.comp.objects

On Sat, 16 Jan 1999, Adam Karpierz wrote:

> A jesli chodzi o referencje to i owszem.
> Byloby to i lekarrstwo na szalenstwo wskaznikowe w C++
> gdyby nie... No wlasnie
> Gdyby nie to ze nie mozna zmienic obiektu "referowanego".
> Moze mi ktos wytlumaczy dlaczego ?.
> Skutek ?. Dalej wskazniki kroluja.

Ostatnio myślałem nad referencjami (w oderwaniu od języka - a raczej
projektując język) i wychodzi mi, że ogólnie sprawa nie jest taka prosta.
Albo że źle do niej podchodzę.

Chciałem zrobić tak, żeby referencje całkowicie zastąpiły wskaźniki.
W C++ zakaz przestawienia referencji pociąga zakaz kopiowania obiektów
zawierających referencje; nie można też używać referencji do referencji
(ani wskaźników do referencji). Chciałem też, żeby można było definiować
własne typy zachowujące się jak referencje.

Przy wielokrotnych referencjach z początku wydaje się, że wszystko jest
dobrze, mimo pewnej dziwności dla nieprzyzwyczajonego. Na przykład
(składnia C++owata):

{
    int wart1 = 1, wart2 = 2, &ref, & &ref_ref;
    &ref = &wart1;
    ref = 3;                // wart1 = 3
    & &ref_ref = & &ref;
    &ref_ref = &wart2;      // &ref = &wart2
    ref_ref = 4;            // ref = 4, wart2 = 4
}

Co robi operator &? Wydaje się, że przekształca referencję we wskaźnik.
Jednak muszą istnieć wskaźniki, przynajmniej jako tymczasowe wartości -
same referencje nie wystarczą. Czymś w końcu ten przypisywany adres musi
być - nie może być referencją, bo przypisanie referencji polega na wzięciu
referowanego obiektu i przypisaniu jego...

Tak naprawdę w C++ & przekształca l-wartość we wskaźnik. AFAIK formalnie
jest rozróżnienie między referencją a l-wartością. Nie mam pojęcia,
dlaczego.

Operator & referencję do referencji przekształca w referencję do
wskaźnika! Czyli z typu int **& & & robi int ***& &. Hmm, jak to zapisać,
kiedy chcemy zdefiniować własny rodzaj referencji? W moim modelu typów
z parametrami (pełniących taką funkcję jak szablony klas) i "szablonów
funkcji" definiowanych różnie dla typów o różnych właściwościach (czyli
bardziej elastycznych niż szablony funkcji w C++) nie da się tego wyrazić.
Potrzeba by chyba typów z parametrami, które mają różną definicję dla
parametrów o różnych właściwościach - a wtedy wszystko się komplikuje
(szablony typów i szablony funkcji to zupełnie różne rzeczy, zwłaszcza
że nie uznaję metod jako składników typu - takie moje prawo heretyka)
i powstają niejednoznaczności.

Zostawmy na chwilę referencje do referencji.

Załóżmy, że mamy strukturę zawierającą referencję. Naturalnym znaczeniem
przypisania takich struktur jest skopiowanie referencji - nie tak
jak bezpośrednie przypisanie zmiennych referencyjnych (które kopiują
referowany obiekt), tylko przypisanie adresów, tak jak by to były
wskaźniki. To się na szczęście bardzo łatwo wyraża, a więc jest w tym
logika: przypisanie jest równoważne wykonaniu kopii prawego obiektu,
destrukcji lewego i przeniesieniu tej kopii w nowe miejsce (żeby poprawnie
zadziałało przypisanie obiektu na niego samego). A jest rzeczą oczywistą,
że konstruktor kopiujący dla struktur zawierających referencje powinien
zrobić kopię samej referencji, a nie referowanego obiektu (który przecież
w docelowym miejscu jeszcze nie istnieje). Tak więc domyślne przypisanie
struktury nie jest równoważne przypisaniu poszczególnych elementów, tylko
destruktorowi + konstruktorowi kopiującemu całej struktury.

A kiedy przypisujemy same referencje? Wtedy nie można zdać się na
ową definicję przypisania przez destruktor + konstruktor, bo wyjdzie
właśnie przypisanie adresów, jak dla wskaźnika. Zatem po prostu
przedefiniowujemy przypisanie referencji jako przypisanie wartości
referowanych. Inne typy nie muszą mieć jawnie zdefiniowanego operatora
przypisania, chyba że dla efektywności. Oczywiście u mnie - w C++ trzeba
definiować przypisanie jawnie (chyba że ma być trywialne).

Struktura zawierająca samą referencję domyślnie przypisuje się jak inne
struktury: kopiując swoje pola, czyli samą referencję - a nie referowany
obiekt. Czyli zachowuje się dokładnie jak wskaźnik! Można więc zdefiniować
wskaźniki mając referencje. Wskaźnik to struktura zawierająca referencję
jako swoje jedyne pole. Z każdego rodzaju referencji można utworzyć dualny
rodzaj wskaźnika pakując go w taką strukturę. Przy okazji wychodzi łatwa
definicja uogólnionej referencji: jest to taki typ, który inaczej się
kopiuje bezpośrednio, a inaczej, kiedy jest składnikiem struktury.

Referencje są oczywiście konwertowalne na wartości danego typu. Spróbujmy
teraz zdefiniować operatory brania adresu referencji i dereferowania
wskaźnika (wyłuskiwania - brr, nie podoba mi się to słowo). Z tym drugim
nie ma problemu: zwracamy jedyne pole wskaźnika, który jest strukturą.
Gorzej w drugą stronę, z tworzeniem wskaźników.

Weźmy deklarację:
    int & &r, &s;
Wyrażenie r jest typu int & & & (każda zmienna jako wyrażenie jest
referencją, skoro ma adres i można z niej zrobić wskaźnik). Rozważmy
przypisanie &r = &s. Jeśli operator & jest zdefiniowany w ten sposób,
że z dowolnej wartości robi "wskaźnik" przez wsadzenie tej wartości
do pudełka, to jest tragedia. Jeśli zrobimy pudełko z r jako potrójnej
referencji, nie będzie można do tego przypisać - lewy argument przypisania
musi być referencją. Trzeba więc dodatkowo zdefiniować & od referencji
do referencji jako zamianę w referencję na wskaźnik (widać z tego, że
to pudełko implementujące wskaźnik musi mieć taką samą budowę jak sama
referencja, czyli że struktura zawierająca jedno pole musi mieć taką samą
budowę jak wartość odpowiedniego typu - nie wiem, czy tak jest w C / C++).

Ale dalej jest nie tak. Otrzymamy referencję na pudełko zawierające
podwójną referencję, tymczasem chcieliśmy uzyskać referencję na
pudełko zawierające referencję na int - czyli sięgnąć jak najdalej
w dereferowaniu, a nie jak najbliżej! Dopiero & &r powinno dać referencję
na pudełko zawierające referencję na pudełko zawierające referencję.

Trzeba w jakiś sposób zapisać, że wartość będąca referencją bardzo stara
się zdereferować - nawet bardziej niż pozostać w oryginalnej postaci! To
znaczy żeby konwersja typu polegająca na dereferencji referencji miała
większy priorytet niż brak konwersji. W ten sposób &r najpierw zdereferuje
r, a potem przekształci odtrzymaną podwójną referencję w referencję
na pudełko zawierające pojedynczą referencję...

Stop! Jeśli & wkłada dowolną wartość do pudełka, to przedobrzyliśmy -
otrzymamy pudełko zawierające liczbę całkowitą, które zachowuje się
tak samo jak liczba całkowita. Trzeba więc zdefiniować jawnie & dla
poszczególnych rodzajów referencji. Trudno, tych rodzajów nie będzie tak
wiele (na pewno oprócz "standardowej" będzie samozwalniająca się).

Rozważmy teraz definiowaną listę sparametryzowaną dowolnym typem.
W jej implementacji zapewne będziemy chcieli przypisywać elementy listy
(wartości typu tego parametru, a nie całe węzły zawierające wskaźniki
na inne węzły). Jeśli jednak po prostu użyjemy operatora przypisania, to
wszystko się posypie, jeśli typem elementów okaże się referencja. Nasuwa
się jedno rozwiązanie: wsadźmy elementy do pudełka. To znaczy tak jak
wskaźnik jest pudełkiem (referencja (T)), tak węzeł listy będzie zawierał
pudełko (T).

Niestety przed chwilą założyliśmy, że do pudełka można wkładać tylko
referencje (przynajmniej operatorem &)... W tym miejscu to ograniczenie
tylko przeszkadza. Poza tym byłoby niewygodnie jawnie używać pudełek
(czyli prawie wskaźników) przy wszelkich takich typach parametryzowanych
dowolnym innym. Kiedy robię listę dowolnych wartości, to chciałbym, żeby
można je było kopiować w prosty sposób, nie myśląc o tym, czy nie są
przypadkiem referencjami.

Intuicja mówi, że kiedy mam referencję, to operacje na niej dotyczą
referowanego obiektu; kiedy chcę zrobić coś z samą referencją, użyję np.
operatora & (nie dotyczy to przekazania referencji jako parametr funkcji
spodziewającej się referencji ani inicjalizacji innej referencji). Kiedy
jednak mam wartość dowolnego typu T, to chcę, żeby operacje dotyczyły
raczej jej samej - nawet jeśli on okaże się być referencją!

Wymaga to sprytniejszej idei szablonów niż jest w C++. To nie może polegać
na prostym tekstowym podstawieniu dowolnego typu. Niektóre operacje mają
być wykonywane używając ogólnych definicji tych operacji (np. przypisanie
wyrażone za pomocą destruktora i konstruktora), nawet jeśli są
przedefiniowane dla konkretnego typu będącego parametrem szablonu
(np. przypisanie referencji).

To się ładnie komponuje z ideą szablonów zdefiniowanych dla typów mających
pewne własności - a nie dla dowolnych typów, dla których dany napis ma
sens. Stwórzmy więc pojęcie wieloparametrycznej sygnatury - a może nazwać
to interfejsem? Kompilator g++ oferuje rozszerzenie C++, które nazywa
sygnaturami. Można zadeklarować wskaźnik na dowolny obiekt implementujący
wymienione metody, i potem podstawić na niego obiekt dowolnej klasy
implementującej te metody i wykonywać te metody. Podobnie jak klasy
abstrakcyjne, ale bardziej elastyczne, bo w miejscu definicji klasy nie
trzeba jawnie określać, jakie interfejsy ona obiecuje implementować.

Ja chcę użyć tego do parametryzacji szablonów funkcji. Szablon funkcji
jest zdefiniowana dla typów pasujących do danych sygnatur, czyli
implementujących dane funkcje. W odróżnieniu od sygnatur z g++ to muszą
być wieloargumentowe relacje na typach, żeby np. dało się zdefiniować
funkcję, gdzie typ jednego argumentu ma być indeksowalny wartościami
typu drugiego. Taka wieloargumentowość nie ma sensu w przypadku zwykłych
zmiennych wskaźnikowych, bo wtedy pojawia się tylko jeden nieznany typ
naraz - typ obiektu wskazywanego przez tę zmienną, a inne zmienne są
ustawiane niezależnie. W przypadku funkcji wszystkie argumenty są
przekazywane równocześnie, więc można określić warunki, jakie muszą
spełniać wszystkie typy argumentów naraz. (Kompilator ma wtedy wolną wolę,
czy zaimplementować funkcję w jednej kopii, wołając wirtualne funkcje
przez jakieś wskaźniki, czy też wyprodukować też wersje dla konkretnych
typów, tak jak zwykłe szablony w C++. Podobnie jak z funkcjami inline,
tylko na innym poziomie.)

Szablon funkcji określa więc warunki, jakie muszą spełniać typy
argumentów. W ciele takiej funkcji można używać tylko operacji
wymienionych w danym interfejsie, a argumentem mogą stać się tylko
wartości typu implementującego wszystkie wymagane operacje interfejsu.
W ciele można też używać operacji zdefiniowanych na dowolnych sygnaturach
/ interfejsach, które są nadzbiorem warunków dla danej funkcji. Z tym że
konsekwencja wymaga, żeby tylko te pierwsze operacje były "wirtualne". To
znaczy jeśli w interfejsie wymienię funkcję f, to w funkcji z argumentem
typu tego interfejsu mogę używać na tym argumencie funkcji f i zostanie
wywołana odpowiednia wersja tej funkcji zdefiniowana dla aktualnego typu.
Jeśli zaś funkcja g będzie szablonem funkcji zdefiniowanym dla tego
interfejsu albo jego nadzbioru, to w danej funkcji mogę na tym argumencie
używać również funkcji g. Nie szkodzi, jeśli typ argumentu aktualnego ma
zdefiniowaną własną funkcję g - nie jest wymieniona w interfejsie, więc
nie jest "wirtualna". A jeśli funkcja jest wymieniona w wymaganiach
interfejsu i równocześnie jest zdefiniowana ogólnie na dowolnych
wartościach pasujących do tego interfejsu, to ta definicja określa
domyślną implementację - typ będzie pasował do interfejsu nawet jeśli nie
zaimplementuje jawnie tej funkcji i wtedy będzie użyta ta domyślna
implementacja.

W ten sposób można załatwić przypisania referencji. Przypisanie nie
będzie wymienione w żadnym interfejsie. Wymieniony będzie tylko (być może
niejawnie we wszystkich interfejsach) konstruktor kopiujący i destruktor,
a ogólne przypisanie jest przez nie zdefiniowane.

W takiej formie to nie będzie optymalne pod względem efektywności
(przypisanie może być dla konkretnych typów zdefiniowane w bardziej
efektywny sposób niż konstruktor + destruktor + przeniesienie), ale
na szczęście da się to uratować, o ile dobrze rozumuję. Wystarczy
w interfejsie umieścić pomocniczą funkcję zamiast przypisania, która dla
przeciętnych typów będzie równoważna przypisaniu, a przypisanie będzie
równoważne jej (kompilator będzie musiał wykrywać takie cykle przy
sprawdzaniu, czy typ pasuje do interfejsu, ale chyba jest to dobrze
zdefiniowane). Wirtualizacja będzie się odbywała przez nią. Tylko
referencje będą miały ją zdefiniowaną inaczej niż przypisanie: owa funkcja
kopiuje adres, a prawdziwe przypisanie dereferuje argumenty i przypisuje
je. W ten sposób przypisanie wartości nastąpi tylko gdy skądinąd wiemy,
że to jest referencja; jeśli odwołujemy się do czegoś jako do wartości
bliżej nieznanego typu T, to w przypadku referencji będzie ono skopiowane
jak wskaźnik.

Wciąż nie mam jak zdefiniować operatora brania &. Nawet nie ma jak
napisać nagłówka - nie ma jak zapisać typu, który zostanie wydedukowany
(sięgnięcie w głąb referencji do przedostatniej pozycji i wsadzenie do
pudełka tamtej referencji). Oczywiście odpada idea, żeby to był operator
wbudowany w kompilator - moje założenie jest takie, żeby każdą operację
dało się zdefiniować w języku, a przynajmniej napisać jej nagłówek.
Trudności w opisaniu tego w języku mogą świadczyć o tym, że i ludzie
będą mieli kłopoty z używaniem tego.

Mam trochę inne wyjście... Najpierw muszę jednak opowiedzieć ogólniej.

Zastanawiam się, czy struktury, listy itp. mają się dać składać z
elementów przez użycie samych przecinków pomiędzy elementami (w praktyce
z wzięciem całości w nawias (), ale nawias nie może być operatorem), czy
też potrzeba jawnego zaznaczania, że konstruujemy strukturę, np. wsadzając
listę elementów w []. Oczywiście będzie możliwość ukrycia takiego
konstruktora - chodzi o to, co jest domyślnie. Musi coś takiego być, bo
nie akceptuję tego, żeby inicjalizacja tablicy miała specjalną składnię,
której nie można użyć w wyrażeniu (gcc oferuje rozszerzenie języka
pozwalając pisać (char *[]){"x", "y", "z"} i podobnie dla struktur).

Wolałbym, żeby dało się samymi przecinkami - chyba że to doprowadzi do
nieuniknionych niejednoznaczności, wtedy będę musiał z tego zrezygnować.
Same przecinki mają taką zaletę, że wywołanie funkcji typu exec będzie
wyglądało podobnie jak w C, a będzie to uczciwa lista, a nie jakaś
nieznana liczba argumentów z pominięciem kontroli typów.

Zakładając, że wystarczą same przecinki, pojawia się pytanie, czy
w przypadku pojedynczego elementu można się obyć bez przecinka. Jest
pewne, że czasem to prowadzi do niejednoznaczności, np. kiedy mamy listę
list liczb, to (1,2) może być zarówno jednoelementową listą składającą się
z dwuelementowej listy, jak i dwuelementową listą składającą się z dwóch
singletonów. Ale może wystarczy powiedzieć, że w takich przypadkach
pisze się ((1,2),) albo ((1,),(2,)), a kiedy nie ma niejednoznaczności,
można się obyć bez tego. To znowu daje miłą składnię, że nie trzeba
przedefiniowywać execa itp. dla pojedynczego elementu. Na razie wydaje
mi się, że tak może być - same przecinki, z opcjonalnym przecinikiem
za ostatnim elementem, który może się okazać konieczny dla list
jednoelementowych w niektórych przypadkach. To samo dotyczy struktur.
(W Pythonie dla singletonowych tupli w () jest potrzebny przecinek,
a listy są w [] i nie potrzebują przecinka.)

Skoro teraz wskaźnik jest strukturą zawierającą referencję, może należy
tutaj pozostawić tę niejawną konwersję pola jednoelementowej struktury
na całą strukturę? Czyli operator & jest niejawny! Skutki są takie, że
referencje co prawda można przestawiać, ale jest to dość niewygodne
i najczęściej trzeba wtedy jawnie konwertować referencję na wskaźnik
(chyba że przypisujemy jej inny wskaźnik - singletonowa konwersja zachodzi
też pod referencją (potrzebną do tego, żeby otrzymać l-wartość), czyli
referencja na referencję jest konwertowalna na referencję na wskaźnik).
Zawsze można zadeklarować coś jako wskaźnik, np. łącza między elementami
listy będą pewnie wskaźnikami. Przy przypisywaniu temu wartości
z referencji (przekazanej jako argument procedury) nie trzeba jawnie
uzywać operatora &. Tylko dereferencja jest potrzebna. Wielokrotne
referencje nie są zabronione, ale żeby ich używać, trzeba wiedzieć,
co się robi, i w praktyce pewnie najczęściej wskaźniki okażą się
łatwiejsze (tzn. tutaj np. referencja na wskaźnik zamiast podwójnej
referencji). Czyli z grubsza ograniczenia C++ są w mocy, ale nie są
bezwzględne - ich ominięcie jest legalne, tylko może czasem wprowadzać
w błąd. Jeśli ktoś chce widzieć, co jest przypisywane, może zawsze użyć
wskaźników, a referencjami czasem trzeba uważać - ale to jest chyba
nieuniknione. No i można definiować własne referencje, robić listy
referencji, uczciwe funkcje ze zmienną liczbą argumentów itp.

Czy to ma ręce i nogi? :-)

(Nie opisywałem różnych założeń nie związanych bezpośrednio z tematem.)

-- 
 __("<    Marcin Kowalczyk * qrczak@knm.org.pl http://kki.net.pl/qrczak/
 \__/       GCS/M d- s+:-- a21 C+++>+++$ UL++>++++$ P+++ L++>++++$ E->++
  ^^                W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP->+ t
QRCZAK                  5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-