Implication as an Operator

A vast majority of code is dealing with logical conditions by using three dedicated operators: not (negation), and (conjunction), or (alternative). These are often written as !, && and ||, respectively, in C-like programming languages.

In principle, this is sufficient. Coupled with true and false, it’s enough to encode any boolean function of zero, one or two arguments. But language designers didn’t seem to be concerned with minimalism here, because it’s possible to replace those three operators with just one of the following binary functions:

If you can’t immediately see how, start with deriving negation first.
So we already have some redundancy for the sake of readability. While it’s surely a bad idea to try and incorporate all 22 before mentioned functions, isn’t there at least few others that would make sense as operators on their own?

I can probably think of one: the material implication (). It may seem like a weird choice at first, but there are certain common scenarios where such operator would make things more explicit.
Imagine for a second that some mainstream language (like Java) has been enhanced with operator => that acts as implication. Here’s one example of its straightforward usage:

Many situations involving “optionals” could take advantage of logical implication as an operator. Also note how in this case, the alternatives do not look very appealing at all. One could use an if statement to produce equivalent construct:

but this makes a trivial one-liner suddenly look quite involved. We could also expand the implication using the equivalence law :

Reader would then have to perform the opposite transformation anyway, in order to restore the real meaning hidden behind the non-obvious ! and || operators. Finally, we could be a little more creative:

and capture the intent almost perfectly… At least until along comes someone clever and “simplifies” the expression into the not-a-or-b form presented above.

Does any language actually have the implication operator? Not surprisingly, the answer is yes – but it’s most likely a language you wouldn’t want to code in. Older and scripting versions of Visual Basic had the Imp operator, intended to evaluate the logical connective .
Besides provoking a few chuckles with its hilarious name, its usefulness was limited by the fact that it wasn’t short-circuiting. Both arguments were always evaluated, even if the first one turned out false. You may notice that in our NameMatcher example, such a behavior would produce NullPointerException when one of the names is null. This is also the reason why implication implemented as a function:

would not work in most languages, for the arguments are all evaluated before executing function’s code.

At Least Python Got Equality Right

I’m still flabbergasted after going through the analysis of PHP == operator, posted by my infosec friend Gynvael Coldwind. Up until recently, I knew two things about PHP: (1) it tries to be weakly typed and (2) it is not a stellar example of language design. Now I can confidently assert a third one…

It’s completely insane.

However, pondering the specific case of equality checks, I realized it’s not actually uncommon for programming languages to confuse the heck out of developers with their single, double or even triple “equals”. Among the popular ones, it seems to be a rule rather than exception.

Just consider that:

• JavaScript has both == and ===, exactly like PHP does. And the former is just slightly less crazy than its PHP counterpart. For both languages, it just seems like a weak typing failure.
• In C and C++, you may easily use = (assignment) in lieu of == (equality), because the former is perfectly allowed inside conditions for if, while or for statements.
• Java is famously counterintuitive when it comes to comparing strings, requiring to use String.equals method rather than == (like in case of other fundamental data types). Many, many programmers have been bitten by that. (The fact that under certain conditions you can compare strings char-by-char with == doesn’t exactly help either).
• C# complicates stuff even more by allowing to override Equals and overload == operator. It also introduces ReferenceEquals which usually works like ==, except when the latter is overloaded. Oh, and it also has two different kinds of types (value and reference types) which by default compare in two different ways… Joy!

The list could likely go on and include most of the mainstream languages but one of them would be curiously absent: Python.

You see, Python got the == operator right:

• It tests for equality only, not identity (also known as “reference equality”). For that there is a separate is operator.
• All basic objects – not only strings, but also lists or dictionaries (hash tables) – compare by value. Hence e.g. two lists are equal if they contain equal elements in the same order, whether or not they are the same objects.
• Implicit conversions are applied judiciously. Different types of numbers (int, long, float) compare to each other just fine, but there is clear distinction between 42 (number) and "42" (string).
• You can overload == but there are no magical tricks that instantly turn your class into wannabe fundamental type (like in C#). If you really want value semantics, you need to write that yourself.

In retrospect, all of this looks like basic sanity. Getting it right two decades ago, however… That’s work of genius, streak of luck – or likely both.

Więcej niż operatory logiczne

Bardzo przydatną cechą operatorów logicznych w wielu językach programowania jest leniwa ewaluacja (lazy evaluation). Polega ona na pominięciu obliczania tych argumentów operatorów && (and) i || (or), które i tak nie mają szans wpłynąć na ostateczny wynik. To pozwala na tworzenie warunków podobnych do poniższego:

Drugi człon nie wykona się tutaj w ogóle, jeśli pierwszy okaże się fałszywy, więc zmienna obj ustawiona na null nie spowoduje błędu wykonania.
Oczywiście technika ta jest doskonale znana każdemu przynajmniej średnio zaawansowanemu programiście. Okazuje się jednak, że przynajmniej jeden język idzie dalej i uogólnia ją w sposób pozwalający na stosowanie operatorów and i or do argumentów niebędących wartościami logicznymi. Jaki to język?… Python, rzecz jasna :)

W Pythonie dwa standardowe operatory ‘logiczne’ działają w oparciu o możliwość określenia specyficznie pojmowanej prawdziwości wyrażenia, którego typem niekoniecznie jest bool. Mówiąc w skrócie, każde wyrażenie niepuste i różne od zera – łącznie z odwołaniami do obiektów, liczbami, tablicami, słownikami i innymi kolekcjami – jest uważane za prawdziwe, gdy wystąpi w kontekście wymagającym rozróżnienia prawdy i fałszu.
Takim kontekstem jest chociażby warunek instrukcji if lub while – ale nie tylko. Możliwość “rzutowania na bool” (fachowo nazywanego koercją) jest też wykorzystywana w definicji operatorów and i or, które są z grubsza następujące:

• A and B jest równe:
  • A, jeśli A jest wyrażeniem fałszywym
  • B – w przeciwnym wypadku
• A or B jest równe:
  • A, jeśli A jest wyrażeniem prawdziwym
  • B – w przeciwnym wypadku

W pierwszej chwili mogą one wydawać się dość skomplikowane, ale nietrudno jest zauważyć, że “działają” one zgodnie z oczekiwaniami wobec argumentów typu bool i mogą być obliczane leniwie. Ponieważ jednak dzięki nim rezultatem operatora nie jest po prostu True lub False, lecz jeden z argumentów, możliwe jest stosowanie and i or także wtedy, gdy wynikiem nie ma być wcale wartość logiczna.

Wbrew pozorom ma to czasem wielki sens. Oto bardzo typowy przykład kodu, który korzysta z tej sztuczki:

Co tu się dzieje?… Jeśli wywołanie funkcji zwróci prawdziwą (czyli niepustą i niezerową, więc zapewne sensowną) wartość, jest ona wyświetlona. W przeciwnym razie korzysta się z napisu zastępczego. Dzięki elastycznemu operatorowi or łatwo więc można określić pewnego rodzaju wartość domyślną (czyli fallback) dla wyrażenia.
Z kolei operator and jest często wykorzystywany do warunkowego odwoływania się do “głęboko ukrytej” wartości, wymagającej przejścia przez ciąg kilku potencjalnie pustych odwołań:

Jeśli któreś z nich jest równe None, to taki będzie rezultat całej konstrukcji. W przeciwnym razie wynikiem będzie ostatni argument.

Istnieje szansa, że przynajmniej jeden z powyższych mechanizmów wygląda znajomo, jeśli ma się doświadczenie w językach Java lub C#. Sztuczka z operatorem or odpowiada bowiem podwójnemu znakowi zapytania (??) z C#, zaś przykład z and wprowadzonemu w Javie 7 operatorowi ?. (znak zapytania i kropka).
Zapewne też w tym momencie wszyscy przypomną sobie o starym dobrym operatorze trójargumentowym, występującym we wspomnianych dwóch językach i jeszcze wielu innych. Okazuje się, że w Pythonie jego działanie też można symulować przy użyciu operatorów and i or:

Nie trzeba jednak tego robić, bowiem od wersji 2.5 istnieje nieco inny składniowo odpowiednik takiej konstrukcji:

Warto zwrócić uwagę na inną niż typowa kolejność wyrażeń w tej konstrukcji.

Zabezpieczenie przed NULL-em

Defensywne programowanie wymaga, by zabezpieczać się przed różnymi niepożądanymi sytuacjami. Jedną z częstszych jest próba odwołania się do obiektu czy wartości, która nie istnieje – czyli np. dereferencja wskaźnika pustego czy użycie odwołania zawierającego null. Stąd bardzo częste ify w rodzaju:

Kiedy jednak sprawdzenie nullowatości jest tylko częścią warunku, wtedy w ruch idzie zwykle “sztuczka” z leniwą ewaluacją (lazy evaluation):

Większość języków ją dopuszcza, jako że jest ona przy okazji pewną formą optymalizacji. Jeśli bowiem pierwszy argument operatora logicznego daje informację o prawdziwości/fałszywości całego wyrażenia, nie trzeba już wyliczać drugiego.

Inną typową sytuacją jest zamiana nulla na jakąś inną wartość domyślną:

Tutaj C# oferuje specjalny operator ??, pomyślany właśnie na tego typu okazje:

Działa on dobrze z typami Nullable, czyli specyficznym rodzajem typów pochodnych, które dopuszczają wartość null tam, gdzie typ macierzysty jej nie przewiduje:

Operator ?? przydaje się wtedy do konwersji na typ bazowy z określoną wartością domyślną.

Co może udawać obiekt w C++

Możliwości przeciążania operatorów w C++ dla własnych typów obiektów sprawiają, że mogą one (tj. te obiekty) zachowywać się w bardzo różny sposób. Mogą na przykład “udawać” pewne wbudowane konstrukcje językowe, nierzadko wykonując ich zadania lepiej i wygodniej. Przykładów na to można podać co najmniej kilka – oto one:

• Obiekt może zachowywać się jak funkcja, czyli udostępniać możliwość “wywołania” siebie z określonymi parametrami. Takie twory często nazywa się funktorami i bywają używane podczas pracy ze standardową biblioteką STL.
  Działają one przy tym w bardzo prosty sposób, zwyczajnie przeciążając operator nawiasów okrągłych (). Jest on na tyle elastyczny, że może przyjmować dowolne parametry i zwracać dowolne rezultaty, co pozwala nawet na stworzenie więcej niż jednego sposobu “wywoływania” danego obiektu. Jednym z bardziej interesujących zastosowań dla tego operatora jest implementacja w C++ brakującego mechanizmu delegatów, czyli wskaźników na metody obiektów.
• Na podobnej zasadzie obiekt może udawać tablicę – wie o tym każdy, kto choć raz używał klas STL typu vector. Wymagane jest tu przeciążenie operatora indeksowania []. Daje ono wtedy dostęp do elementów obiektu-pojemnika, który zresztą nie musi być wcale indeksowany liczbami, jak w przypadku tablic wbudowanych (dowodem jest choćby kontener map). Ograniczeniem jest jedynie to, że indeks może być (naraz) tylko jeden, bo chociaż konstrukcja typu:
  1. v[3,4] = 5;

  jest składniowo najzupełniej poprawna, to działa zupełnie inaczej niż można by było się spodziewać :)

• Obiekty mogą też przypominać wskaźniki, które wtedy określa się mianem ‘sprytnych’ (smart pointers). Dzieje się tak głównie za sprawą przeciążenia operatorów * (w wersji jednoargumentowej) i ->. Normalnie te operatory nie mają zastosowania wobec obiektów, ale można nadać im znaczenie. Wtedy też mamy obiekt, który zachowuje się jak wskaźnik, czego przykładem jest choćby auto_ptr z STL-a czy shared_ptr z Boosta.
• Wreszcie, obiekt może też działać jako flaga boolowska i być używany jako część warunków ifów i pętli. Sprytne wskaźniki zwykle to robią, a innymi wartymi wspomnienia obiektami, które też takie zachowanie wykazują, są strumienie z biblioteki standardowej. Jest to spowodowane przeciążeniem operatora logicznej negacji ! oraz konwersji na bool lub void*.

Reasumując, w C++ dzięki przeciążaniu operatorów możemy nie tylko implementować takie “oczywiste” typy danych jak struktury matematyczne (wektory, macierze, itp.), ale też tworzyć własne, nowe (i lepsze) wersje konstrukcji obecnych w języku. Szkoda tylko, że często jest to wręcz niezbędne, by w sensowny sposób w nim programować ;)

Naprawdę duże liczby

Programując, rzadko mamy do czynienia z bardzo dużymi wartościami. Dowodem na to jest choćby fakt, że 32-bitowe systemy dopiero teraz zaczynają być w zauważalny sposób zastępowane 64-bitowymi. Jedynie w przypadku rozmiarów bardzo dużych plików operowanie zmiennymi mogącymi zmieścić wartości większe niż 4 miliardy jest konieczne.
Inne dziedziny życia i nauki przynoszą nam nieco większe wartości. Ekonomia czasami mówi o dziesiątkach bilionów (PKB dużych krajów), a fizyka często posługuje się wielkościami zapisywanymi przy pomocy notacji potęgowej – aż do ok. 10⁸⁰, czyli szacowanej liczby wszystkich atomów we Wszechświecie.

Wydawać by się mogło, że wielkość ta jest bliska górnej granicy wartości, jakich kiedykolwiek moglibyśmy używać w sensownych zastosowaniach. Okazuje się jednak, że tak nie jest; co więcej, jakakolwiek liczba zapisana za pomocą co najwyżej potęgowania jest tak naprawdę bardzo, bardzo mała.
Do zapisywania naprawdę dużych liczb potrzebne są bowiem inne notacje. Jednym z takich sposobów zapisu jest notacja strzałkowa Knutha, która jest “naturalnym” rozszerzeniem operacji algebraicznych. Tak jak dodawanie jest iterowaną inkrementacją, mnożenie jest iterowanym dodawaniem, a potęgowanie – iterowanym mnożeniem:

,

tak każdy następny operator strzałkowy jest iterowaną wersją poprzedniego. I tak pierwszy z nich, to zwykłe potęgowanie , ale już drugi:

jest odpowiednikiem wielokrotnego podnoszenia danej liczby do jej potęgi. W ogólności, skracając ciąg n strzałek do , otrzymujemy definicję:

Na pierwszy rzut oka może wydawać się to nieoczywiste, jednak już dla n = 3 i jednocyfrowych argumentów, wielkość liczb otrzymywanych przy użyciu notacji strzałkowej znacznie przekracza te, które można w wygodny sposób zapisać przy pomocy samego potęgowania. Chcąc je mimo wszystko przedstawić w tej postaci, trzeba się uciekać do sztuczek z klamerkami:

Oczywiście wraz ze wzrostem liczby strzałek nawet takie triki przestają wystarczać.

W tej chwili pewnie nasuwa się proste pytanie: czy z takiego systemu zapisu jest w ogóle jakiś pożytek, jeśli nikt nie posługuje się na poważnie tak wielkimi liczbami?… Odpowiedź jest jak najbardziej twierdząca, mimo że założenie w pytaniu jest nieprawdziwe. Otóż niektóre dziedziny matematyki używają nie tylko takich, ale i znacznie większych wartości – i nie chodzi tu nawet o teorię liczb, którą to jako pierwszą podejrzewalibyśmy o rzucanie liczbami “z kosmosu”.
Według Księgi Rekordów Guinnessa największą skończoną liczbą kiedykolwiek użytą w poważnym dowodzie matematycznym jest bowiem tzw. liczba Grahama, będącą górnym ograniczeniem pewnej wielkości występującej w problemie luźno związanym z grafami. Żeby ją zdefiniować, można użyć notacji strzałkowej – trzeba to jednak zrobić… iteracyjnie, wprowadzając pomocniczy ciąg g_n:

Już pierwszy jego wyraz nie daje się zapisać w postaci potęgowej, ale gwoździem programu jest zauważenie, że kolejne jego elementy posługują się poprzednimi w celu określenia liczby strzałek w operatorze . Innymi słowy, mamy tu wejście na kolejny poziom abstrakcji i stoimy już chyba tak wysoko, że aż strach spoglądać w dół ;)
Co jednak ze wspomnianą wcześniej liczbą Grahama? Teraz na szczęście jej określenie jest już bardzo proste. Jest ona równa ni mniej, ni więcej, jak tylko… g₆₄ :-)

Przypisania złożone

Przy wprowadzaniu operatorów przypisania typu += czy *= w większości kursów C++ stwierdza się, że ich używanie jest głównie skrótem w stosunku do korzystania ze zwykłego przypisania (=) i odpowiednich operatorów binarnych (jak + czy *). Takie wyjaśnienie jest na początek zupełnie wystarczające, a przy tym łatwe do zrozumienia i co ważniejsze, wydaje się poprawne. I tak faktycznie jest – ono tylko “wydaje się” :)
Później dowiadujemy się bowiem, że sprawa jest nieco bardziej skomplikowana. Zapis typu a += b nie musi zawsze nawet w przybliżeniu odpowiadać “wersji długiej” w postaci a = a + b. Trzeba tu wziąć pod uwagę kilka rzeczy – głównie to, co kryje się pod nazwami a i b:

• Jeśli na przykład mamy do czynienia z przeciążonymi operatorami = i np. +, to nie oznacza to, że automatycznie dostajemy też przeciążony operator += (i vice versa). Po “skróceniu” dana instrukcja może się więc w ogóle nie skompilować. Dotyczy to oczywiście sytuacji, w których mamy do czynienia z własnymi typami danych.
• W przypadku, gdy prawa strona przypisania jest bardziej rozbudowana, nieopatrzna zmiana operatora może spowodować niezamierzone błędy. W szczególności np. x = x - y + 2; to nie jest to samo co x -= y + 2;.
• Nawet dla typów podstawowych skompilowany kod będzie najprawdopodobniej inny w zależności od tego, którego wariantu użyjemy – zwłaszcza w bardziej skomplikowanych przypadkach, gdy ewentualne optymalizacje nie są oczywiste.

Pamiętajmy więc, że operatory typu += są właśnie operatorami, całkowicie odrębnymi od wszystkich innych, nie zaś żadnymi skrótami, jak to się często “dla uproszczenia” mówi.