Dane oryginału

Copyright © 2019 by Joanathan E. Steinhart. Title of English-language original: The Secret Life of Programs: Understand Computers – Craft Better Code, ISBN 978-1-59327-970-7, published by No Starch Press. Polish-language edition copyright © 2020 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna. All rights reserved.

Przekład Tomasz Lewandowski na zlecenie WITKOM Witold Sikorski

Projekt okładki polskiego wydania INT-MEDIA Dawid Mazur na podstawie oryginału

Wydawcy Edyta Kawala, Joanna Banasiak-Lach

Redaktor prowadzący Jolanta Kowalczuk

Redaktor Małgorzata Dąbkowska-Kowalik

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN

Aneta Pudzisz/Woblink

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Copyright © for the Polish edition by Wydawnictwo Naukowe PWN SA

Warszawa 2021

ISBN 978-83-01-21775-4

eBook został przygotowany na podstawie wydania papierowego z 2021 r., (Wydanie I)

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl; reklama@pwn.pl

www.pwn.pl

Dla Julie i Hanalei – za to,

że nauczyli mnie, jak wyjaśniać

skomplikowane technologie laikom.

Dla niesamowitego miejsca, jakim było

Bell Telephone Laboratories,

i dla wszystkich,

którzy tam pracowali – zwłaszcza dla Carla

za stworzenie tam miejsca dla mnie,

gdy byłem nastolatkiem.

O autorze

Jonathan E. Steinhart zajmował się inżynierią od lat 60. XX wieku. W szkole średniej zaczął projektować sprzęt komputerowy, a oprogramowanie w college’u. Dzięki tym zainteresowaniom dostał się na praktyki letnie do Bell Telephone Laboratories. W 1977 roku uzyskł tytuł magistra (BSEE) z inżynierii elektronicznej i informatyki na Uniwersytecie w Clarkson. Po zakończeniu studiów pracował dla Tektronix, by potem spróbować szczęścia w startupach. W 1987 roku został konsultantem wyspecjalizowanym w inżynierii systemów wysokiej niezawodności. Wycofał się nieco na początku lat 90. XX wieku, by założyć winnicę Four Winds Vineyard.

O recenzencie technicznym

Aubrey Anderson zdobył tytuł BSEE z inżynierii elektronicznej i informatyki na Uniwersytecie w Tufts. Podczas studiów prowadził zajęcia i pomagał poprawiać programy nauczania dla kursów wstępnych z nauk komputerowych. Zaczął programować w wieku 14 lat i od tego czasu pracował nad wieloma projektami z zakresu robotyki, projektowania systemów i technologii sieciowych. Aubrey aktualnie pracuje w Google jako inżynier oprogramowania.

Spis treści

PODZIĘKOWANIA

WSTĘP

WPROWADZENIE

Dlaczego dobre programowanie jest ważne

Nauka programowania to dopiero początek

Znaczenie podstawowej wiedzy

Kto powinien przeczytać tę książkę?

Czym jest komputer?

Czym jest programowanie?

Kodowanie, programowanie, inżynieria i informatyka

Krajobraz

Co się znajduje w tej książce

1. JĘZYK WEWNĘTRZNY KOMPUTERÓW

Czym jest język?

Język pisany

Bit

Operacje logiczne

Algebra boolowska

Prawo de Morgana

Przedstawianie liczb naturalnych za pomocą bitów

Przedstawianie liczb dodatnich

Dodawanie binarne

Przedstawianie liczb ujemnych

Przedstawianie liczb rzeczywistych

Postać stałoprzecinkowa

Postać zmiennoprzecinkowa

Standard liczb zmiennoprzecinkowych IEEE

Zapis dziesiętny kodowany dwójkowo

Łatwiejsze sposoby pracy z liczbami dwójkowymi

Postać ósemkowa

Postać szesnastkowa

Przedstawienie kontekstu

Nazewnictwo grup bitów

Przedstawianie tekstu

Amerykański standardowy kod do wymiany informacji (ASCII)

Rozwój innych standardów

8-bitowy format transformacji Unicode

Używanie znaków do przedstawiania liczb

Kodowanie Quoted-Printable

Kodowanie Base64

Kodowanie URL

Przedstawianie barw

Dodanie przejrzystości

Kodowanie kolorów

Podsumowanie

2. UKŁADY KOMBINACYJNE

W obronie komputerów cyfrowych

Różnica między analogowym a cyfrowym

Dlaczego rozmiar sprzętu ma znaczenie

Cyfrowe urządzenia są stabilniejsze

Cyfrowe urządzenia w analogowym świecie

Dlaczego używamy bitów zamiast cyfr

Krótkie wprowadzenie do elektryczności

Analogia hydrauliczna

Przełączniki elektryczne

Budowanie sprzętu do obsługi bitów

Przekaźniki

Lampy próżniowe

Tranzystory

Układy scalone

Bramki logiczne

Histereza jako sposób na zwiększenie odporności na szum

Przesyłanie różnicowe

Czas propagacji

Rodzaje wyjść

Budowa bardziej skomplikowanych obwodów

Budowa sumatora

Budowa dekoderów

Budowa demultiplekserów

Budowa selektorów

Podsumowanie

3. UKŁADY SEKWENCYJNE

Przedstawianie czasu

Oscylatory

Zegary

Przerzutniki

Przerzutniki bramkowane

Flip-flopy

Liczniki

Rejestry

Organizacja i adresowanie pamięci

Pamięć o dostępie swobodnym (RAM)

Pamięć tylko do odczytu (ROM)

Urządzenia blokowe

Pamięć typu Flash oraz napędy SSD

Wykrywanie i naprawianie błędów

Sprzęt kontra oprogramowanie

Podsumowanie

4. ANATOMIA KOMPUTERA

Pamięć

Wejście i wyjście

Jednostka centralna

Jednostka arytmetyczno-logiczna

Przesuwalność

Jednostka wykonawcza

Plan instrukcji

Instrukcje

Tryby adresowania

Instrukcje kodów warunkowych

Instrukcje rozgałęzienia

Ostateczny plan instrukcji

Ostateczny projekt

Rejestr instrukcji

Ścieżki danych i sygnały kontrolne

Sterowanie ruchem

Zbiory instrukcji RISC i CISC

Procesor graficzny

Podsumowanie

5. ARCHITEKTURA KOMPUTERA

Podstawowe elementy architektoniczne

Rdzenie procesora

Mikroprocesory i mikrokomputery

Procedury, podprogramy i funkcje

Stosy

Przerwania

Adresowanie względne

Jednostki zarządzania pamięcią

Pamięć wirtualna

Przestrzeń użytkownika i przestrzeń systemowa

Hierarchia pamięci i wydajność

Koprocesory

Układ danych w pamięci

Wykonywanie programów

Zasilanie pamięci

Podsumowanie

6. ANALIZA KOMUNIKACJI

Niskopoziomowe we/wy

Porty we/wy

Powciskaj mi przyciski

Niech się staną światełka

Światła, akcja, …

Jaśnie oświeceni

2n twarzy Graya

Kwadratura

Komunikacja równoległa

Komunikacja szeregowa

Złap falę

Uniwersalna magistrala szeregowa

Sieć

Współczesne sieci LAN

Internet

TCP/IP

Adresy IP

System nazw domen

World Wide Web (WWW)

Urządzenia analogowe w świecie cyfrowym

Konwersja cyfrowego na analogowe

Konwersja analogowego na cyfrowe

Cyfrowy dźwięk

Obrazy cyfrowe

Filmy

Urządzenia do interakcji z człowiekiem

Terminale

Terminale graficzne

Grafika wektorowa

Grafika rastrowa

Klawiatura i mysz

Podsumowanie

7. ORGANIZACJA DANYCH

Podstawowe typy danych

Tablice

Bitmapy

Łańcuchy tekstowe

Złożone typy danych

Listy powiązane

Dynamiczna alokacja pamięci

Wydajniejsza alokacja pamięci

Zbieranie śmieci

Listy podwójnie powiązane

Hierarchiczne struktury danych

Magazyny dla mas

Bazy danych

Indeksy

Przenoszenie danych

Wektorowane wejście/wyjście

Pułapki programowania obiektowego

Sortowanie

Mieszanie

Wydajność oprogramowania a parametry sprzętowe

Podsumowanie

8. PRZETWARZANIE JĘZYKA

Język asemblera

Języki wysokopoziomowe

Programowanie strukturalne

Analiza leksykalna

Maszyny stanowe

Wyrażenia regularne

Od słów do zdań

Klub języka dnia

Drzewa wyprowadzenia

Interpretery

Kompilatory

Optymalizacja

Ostrożnie ze sprzętem

Podsumowanie

9. PRZEGLĄDARKI INTERNETOWE

Języki znaczników

Ujednolicony format określania lokalizacji

Dokumenty HTML

DOM

Leksykon drzewa

Interpretacja DOM

Kaskadowe arkusze stylów (CSS)

XML i przyjaciele

JavaScript

jQuery

SVG

HTML5

JSON

Podsumowanie

10. PROGRAMOWANIE APLIKACYJNE I SYSTEMOWE

Zgadnij co to za zwierzę, wersja 1: HTML i JavaScript

Szkielet poziomu aplikacji

Element <body> strony internetowej

JavaScript

CSS

Zgadnij co to za zwierzę, wersja 2: C

Terminale i wiersz poleceń

Budowanie programu

Terminale i sterowniki urządzeń

Przełączanie kontekstów

Standardowe wejście/wyjście

Bufory cykliczne

Lepszy kod dzięki dobrym abstrakcjom

Nieco mechaniki

Przepełnienie bufora

Program w C

Trening

Podsumowanie

11. SKRÓTY I PRZYBLIŻENIA

Wyszukiwanie w tabeli

Konwersja

Teksturowanie

Klasyfikacja znaków

Metody typu całkowitego

Linie proste

Zakręcone krzywe

Wielomiany

Rekursywne podziały

Spirale

Geometria konstruktywna

Przesuwanie i maskowanie

Więcej unikania matmy

Przybliżenia za pomocą szeregu potęgowego

Algorytm CORDIC

Rzeczy nieco losowe

Krzywe wypełniające płaszczyznę

L-systemy

Wejście w stochastykę

Kwantyzacja

Podsumowanie

12. ZAKLESZCZENIA I WYŚCIGI

Co to jest wyścig?

Zasoby współdzielone

Wątki i procesy

Blokady

Transakcje i ziarnistość

Czekając na semafor

Zakleszczenia

Implementacja zamka krótkoterminowego

Implementacja zamka długoterminowego

JavaScript przeglądarki

Funkcje asynchroniczne i obietnice

Podsumowanie

13. BEZPIECZEŃSTWO

Przegląd zagadnień z tematyki bezpieczeństwa i prywatności

Model zagrożenia

Zaufanie

Zabezpieczenia fizyczne

Zabezpieczenia komunikacji

Współczesność

Metadane i nadzór

Kontekst społeczny

Uwierzytelnienie i autoryzacja

Kryptografia

Steganografia

Szyfry podstawieniowe

Szyfry przestawieniowe

Bardziej złożone szyfry

Szyfry z kluczem jednorazowym

Problem wymiany kluczy

Kryptografia klucza publicznego

Utajnianie przekazywania

Kryptograficzne funkcje mieszające

Podpisy cyfrowe

Infrastruktura klucza publicznego

Blockchain

Zarządzanie hasłami

Higiena oprogramowania

Chroń właściwe rzeczy

Sprawdzaj logikę do upadłego

Szukaj błędów

Minimalizuj powierzchnię ataku

Pozostań w wyznaczonych granicach

Wygenerowanie dobrej liczby losowej jest trudne

Znaj swój kod

Skrajny spryt to twój wróg

Zrozum, co jest widoczne

Nie przesadzaj ze zbieraniem danych

Nie gromadź

Dynamiczna alokacja pamięci nie jest twoim przyjacielem

Zbieranie śmieci też nie jest twoim przyjacielem

Dane jako kod

Podsumowanie

14. SZTUCZNA INTELIGENCJA

Ogólny zarys

Uczenie się maszyn

Bayes

Gauss

Sobel

Canny

Ekstrakcja cech

Sieci neuronowe

Zastosowanie uczenia się maszyn

Sztuczna inteligencja

Big Data

Podsumowanie

15. ŚWIAT REALNY

Propozycja wartości

Jak się tu znaleźliśmy

Historia w skrócie

Otwarte oprogramowanie

Creative Commons

Gwałtowny wzrost przenośności

Systemy zarządzania pakietami

Kontenery

Java

Node.js

Chmura obliczeniowa

Maszyny wirtualne

Urządzenia mobilne

Środowisko programistyczne

Czy jesteś doświadczony?

Nauka szacowania

Planowanie projektów

Podejmowanie decyzji

Współpraca z różnymi osobowościami

Poruszanie się wśród kultury miejsca pracy

Podejmowanie decyzji na podstawie wiedzy

Metodologie rozwoju oprogramowania

Planowanie projektu

Spiszmy to

Szybkie prototypowanie

Projekt interfejsu

Ponowne użycie kodu kontra pisanie własnego

Rozwój projektu

Rozmowa

Dojrzała relacja z komputerami

Terminale i powłoki

Edytory tekstu

Kod przenośny

Kontrola wersji

Testowanie

Raportowanie i śledzenie błędów

Refaktoryzacja

Utrzymywanie

Dbaj o styl

Naprawiaj, a nie pisz od nowa

Podsumowanie

PRZYPISY

PODZIĘKOWANIA

Wiele osób wpłynęło na mnie w sposób, który przyczynił się do powstania tej książki. Należy zacząć od moich rodziców, Roberta i Rosalyn Steinhart, dzięki którym w ogóle miałam tę możliwość, a także dostałem od nich wsparcie w moim zainteresowaniu nauką – przynajmniej do momentu, gdy zaczęło to ich przerażać. Wówczas sprawę przejęło wielu wspaniałych nauczycieli, w tym Beatrice Seagal, William Mulvahill czy Miller Bugliari. Ogromne podziękowania należą się Paulowi Rubenfieldowi za to, że powiedział mi zarówno o Obronie Cywilnej, jak i Skautach Bell Labs.

Nie sposób dać tutaj wyraz wszystkiemu, co zawdzięczam moim drużynowym ze skautingu: Carlowi Christiansenowi i Heinzowi Lycklamie. Oni zmienili moje życie. Dzięki nim poznałem wielu niesamowitych ludzi pracujących w Bell Laboratories, w tym Joe Condona, Sandy’ego Frasera, Dave’a Hegelbargera, Dicka Hause’a, Jima Kaisera, Hanka McDonalda, Maxa Mathewsa, Dennisa Ritchie, Kena Thompsona i Dave’a Wellera. Od każdego z nich wiele się nauczyłem.

Dziękuję Aubrey Anderson, Clemowi Cole, Lee Jalovec, A.C. Mendiones, Edowi Post i Betsy Zeller – każde z nich przynajmniej raz przeczytało całość. W szczególności podziękowania należą się Aubrey za edycję techniczną.

Dziękuję także Mattowi Blaze, Adamowi Cacchettiemu, Sandy Clark, Tomowi Duff, Natalie Freed, Frankowi Heidt, DV Henkel-Wallacowi (znanemu również jako „Grumby”), Lou Katz, Sarze-Jay Terp i Paulowi Vixie za konsultacje w sprawie poszczególnych rozdziałów.

No i dziękuję wszystkim osobom, które odbierały telefony, gdy dzwoniłem do nich z różnymi pytaniami; wśród nich są Ward Cunningham, John Gilmore, Evelyn Mast, Mike Perry, Alex Polvi, Alan Wirfs-Brock i Mike Zuhl. No i oczywiście specjalne podziękowania dla Rakel Hellberg, dziewczyny na wyciągu narciarskim, za danie mi jednego ze szturchnięć motywujących do skończenia tego projektu.

Powstanie tej książki nie byłoby możliwe bez pomocy i zachęty ze strony różnych środowisk gikowskich, włączając w to AMW, Hackersów i TUHS.

Dziękuję Hanalei Steinhart za skomponowanie utworu pokazanego na rysunku 6.36 oraz Julie Donnelly za szalik z rysunku 11.41.

Dziękuję Antoniemu Kotu za pozwolenie na używanie jego podobizny i za utrzymanie mojej klawiatury w stanie należytego zafutrzenia.

WSTĘP

Urodziłem się nerdem. Według mojego ojca, włączałem huśtawkę za pomocą wyimaginowanego włącznika przed użyciem, po zabawie zaś pilnowałem, by w ten sam sposób ją wyłączyć. Maszyny po prostu mówiły do mnie o swej wewnętrznej budowie, a ja je rozumiałem. Byłem jak C-3PO, który rozumiał „język binarny parowników wilgoci”. Miałem to szczęście, że dorastałem w czasie, gdy można było rozkręcić większość rzeczy, by dowiedzieć się, jak działają i nie był do tego potrzebny mikroskop.

Z perspektywy postrzegam swoje dzieciństwo w New Jersey jako dość surrealistyczne. Majsterkowałem przy wszystkim – często ze szkodą dla układu nerwowego mojej mamy. Rodzice kupowali mi wiele zestawów do majsterkowania w stylu „50 w jednym”, ale zaczęli się nieco niepokoić, gdy zacząłem łączyć je ze sobą dla projektów, których próżno by szukać w dołączonych do zestawów książkach. Znalazło to swoją kulminację w Alarmie Przeciw Poduszkowym Włamywaczom, który złapał na gorącym uczynku Wróżkę Zębuszkę. Okazało się to wyborem ekonomicznie nietrafionym, co nie przeszkodziło w odczuwaniu wielkiej satysfakcji. Zbierałem popsute telewizory i inne tego typu urządzenia, które ludzie wynosili w dzień przyjazdu śmieciarki – tak, że mogłem je rozebrać na kawałki, dowiedzieć się, jak działają i zbudować coś z otrzymanych w ten sposób części. Jedną z moich ulubionych zabawek był zestaw Erectora mojego taty z 1929 roku. Program kosmiczny sprawił, że był to doskonały czas na to, by być zainteresowanym technologią. Pamiętam, jak pewnej nocy staliśmy z moim tatą w ogródku przed domem i obserwowaliśmy przelot Echo 1.

Podczas gdy wielu moich rówieśników roznosiło gazety po domach, ja naprawiałem telewizory i zestawy stereo. Mój tata pracował w IBM, więc gdy okazjonalnie zabierał mnie z sobą do pracy, mogłem ze zdumieniem podziwiać ogromne komputery. Gdy miałem osiem lat, zabrał mnie też na Electro Show w Atlantic City. Pamiętam, jak bawiłem się IBM 1620. Pamiętam również własną fascynację sprzętem wystawionym na stoisku Tektronix, co być może wpłynęło na mnie na tyle, że później zdecydowałem się na pracę w tej firmie. Rok później wybrałem się na Światowe Targi w Nowym Jorku i osłupiałem na widok wystawy Bell Systems; tak się zdarzyło, że później współpracowałem z jednym z jej projektantów.

Otrzymałem niesamowitą edukację w szkole publicznej epoki posputnikowej – nie ma już dziś w Ameryce niczego podobnego. W piątej klasie podawaliśmy sobie z ławki do ławki słoik rtęci. W szóstej klasie wysadziłem w powietrze szkolne laboratorium chemiczne – zamiast zostać ukaranym, miałem możliwość nauczenia się wiele z tego doświadczenia (nadal na pamięć znam przepis na wytworzenie trijodku azotu). Pamiętam, jak w ósmej klasie nasz nauczyciel wyprowadził nas ze szkoły i zabrał do Nowego Jorku na film 2001: Odyseja kosmiczna tylko dlatego, że uważał, że ten film jest ważny. Zrobił to, mimo że nie dysponował pisemną zgodą żadnego z rodziców. Nauczyciel, który spróbowałby tego dzisiaj, zapewne straciłby pracę, lub gorzej. Wytwarzaliśmy proch strzelniczy na lekcjach chemii, strzelaliśmy do siebie rakietami na boisku szkolnym w ramach lekcji fizyki nakłuwaliśmy własne palce, by zbadać swoją krew na biologii. To epoka odległa od dzisiejszej, kiedy tak wiele milionów istnień kończy się w pięciogalonowych wiaderkach, że potrzebują one drukowanych ostrzeżeń (wiaderka, nie istnienia), kiedy mokra podłoga sieje postrach w sercach mężczyzn, a urzędnicy rządowi wypowiadają się lekceważąco o nauce, podczas gdy sami nie potrafią odróżnić majsterkowania od terroryzmu.

Poza szkołą rodzice zapisali mnie do skautingu, który kochałem i do małej ligi baseballu, której nienawidziłem. Skauting nauczył mnie wiele o świecie fizycznym: od jazdy konnej, przez bezpieczne zabawy z ogniem, po sztukę przetrwania. Mała liga nauczyła mnie, że nie lubię gier zespołowych.

Krótkofalarstwo było w tych czasach w modzie. To tutaj majsterkowanie się przydawało. Zapisałem się do lokalnego oddziału awaryjnej łączności radiowej Obrony Cywilnej tylko po to, by móc eksperymentować z urządzeniami. Moja jednostka dysponowała prymitywnym dalekopisem, który przeprojektowałem, przez co wkrótce musiałem budować podobne jednostki dla innych okręgów. Uwielbiałem to trójwymiarowe mechaniczne urządzenie, które zwano dalekopisem.

Kiedy uczęszczałem do liceum, przyjaciel opowiedział mi o grupie skautów, którzy w każdy poniedziałkowy wieczór spotykali się w laboratoriach Bell Telephone w pobliskim Murray Hill. Dołączyłem do nich, dzięki czemu mogłem bawić się komputerami w czasach, gdy były one rozmiarów większych domów. Wciągnęło mnie. Już wkrótce urywałem się ze szkoły po to, by autostopem przedostawać się do laboratoriów i namawiać ludzi, by mnie wpuścili. Przerodziło się to w serię cudownych praktyk letnich ze wspaniałymi ludźmi. To zmieniło moje życie. Nauczyłem się bardzo dużo, chodząc od laboratorium do laboratorium, wpraszając się i pytając ludzi, co robią. Wkrótce pisałem dla nich oprogramowanie, mimo że planowałem studiować inżynierię elektroniczną. Projektów sprzętowych jednak nie dało się skończyć w czasie jednego lata, w przeciwieństwie do oprogramowania.

Myślałem, że najlepszym sposobem na uhonorowanie moich przewodników skautowskich jest pójście w ich ślady i pomaganie nowym pokoleniom wschodzących gwiazd technologii, gdy tylko już będę miał taką możliwość. To jednak okazało się trudne, ponieważ złote lata amerykańskiej nauki przeminęły, ustępując miejsca zwiększaniu udziałów akcjonariuszy. Same produkty nie są cenione tak bardzo jak zysk, który generują – a to sprawia, że trudno jest uzasadnić istnienie badań o charakterze naukowym. Firmy rzadko już dają dzieciom szwendać się po biurach, bo nie byłoby to uważane za odpowiedzialne. Z początku sądziłem, że będę mógł działać w ramach skautingu, jednak okazało się to niemożliwe. Organizacje skautowskie wprowadziły pewne zasady, pod którymi nie mogłem się podpisać – w każdym razie nigdy nie zdobyłem odznaki za zasługi na polu dyskryminacji płciowej. Zamiast tego więc zgłosiłem się do wolontariatu w moim lokalnym systemie szkolnictwa.

Zacząłem pisać niniejszą książkę jako zbiór materiałów uzupełniających dla klasy, którą w ramach mojego wolontariatu zdecydowałem się uczyć. Robiłem to jeszcze w czasach, w których Internet nie był tak powszechnie dostępny jak dzisiaj. Obecnie żyję w dość biednej społeczności wiejskiej, więc starałem się, aby oryginalna wersja tej książki zawierała wszystko, co może być potrzebne uczniom przy założeniu, że najprawdopodobniej nie stać ich na jakiekolwiek materiały uzupełniające. To zadanie okazało się niemożliwe do wykonania.

Dzisiaj wiele materiałów na temat różnych języków programowania i różnych technik programistycznych jest już dostępnych w sieci, a większość ludzi ma dostęp do Internetu – jeśli nie w swoim domu, to w swojej bibliotece czy szkole. Napisałem całą książkę od początku z założeniem, że czytelnicy mogą teraz o wiele łatwiej wyszukać w sieci informacje uzupełniające. Jeśli coś więc komuś wyda się niejasne w trakcie lektury, zachęcam do samodzielnego wyszukania informacji na ten temat.

Ostatnio sporo znanych mi studentów wyraziło frustrację związaną ze sposobem, w jaki uczy się ich programowania. Chociaż mogą znaleźć informacje w sieci, wciąż pytają, gdzie mogą znaleźć wszystko, czego potrzebują, zebrane w jednym miejscu. Niniejsza książka została tak napisana, by być właśnie takim miejscem.

Miałem to szczęście, że dorastałem wraz z komputerami. Ja i komputery rozwijaliśmy się razem. Trudno mi sobie wyobrazić, jak by to było wskoczyć w środek w pełni rozwiniętej dziedziny wiedzy, jaką są dziś nauki komputerowe, nie mając jakichkolwiek podstaw. Największym wyzwaniem w czasie pisania książki było dla mnie decydowanie, jak daleko sięgnąć do przeszłości w poszukiwaniu dobrego przykładu i wybór elementów współczesnej technologii do omówienia. Zdecydowałem się na pewnego rodzaju styl retro, ponieważ większości potrzebnych zagadnień można się nauczyć na przykładzie starszej technologii, prostszej w działaniu i przez to łatwiejszej do pojęcia. Nowsze, bardziej złożone rozwiązania techniczne budowane są z tych samych bloków składowych co rozwiązania starsze. Znajomość tych bloków znacząco ułatwia poznanie nowych technologii.

Czasy się zmieniły. Gadżety o wiele trudniej rozłożyć na części, naprawić czy zmodyfikować. Firmy nadużywają teraz praw takich jak Digital Millenium Copyright Act (DMCA) po to, aby utrudnić użytkownikom naprawę posiadanych przez nich urządzeń. To na szczęście prowadzi tu i ówdzie do `„praw do naprawy”. Jako Amerykanie otrzymujemy od naszych rządzących niejasny przekaz. Z jednej strony jesteśmy zachęcani do kształcenia w kierunku STEM[1], a z drugiej strony widzimy, jak naukę się oczernia, a zadania STEM zleca w outsourcingu. Gdyby taka była atmosfera pół wieku temu, wcale nie jestem przekonany, czy Stany Zjednoczone stałyby się tą potęgą technologiczną, jaką są dzisiaj.

Są też i jasne strony. Przestrzenie dla twórców są teraz w rozkwicie. Niektórym dzieciom pozwala się budować i odkrywają, jaka jest to frajda. Części elektroniczne są teraz tańsze niż kiedykolwiek, pod warunkiem, że nie szuka się takich z już gotowym okablowaniem. Smartfony mają więcej mocy obliczeniowej niż wszystkie komputery świata z czasów mojej młodości razem wzięte. Komputery są tańsze niż ktokolwiek kiedykolwiek mógł to sobie wyobrazić: małe komputery, takie jak Raspberry Pi czy Arduino kosztują mniej niż pizza i tak jak pizzę sprzedaje się je w wielu dostępnych rodzajach.

Przy tak łatwo dostępnej mocy obliczeniowej istnieje wielka pokusa, by skoncentrować się wyłącznie na funkcjonalnościach wysokiego rzędu. To trochę jak zabawa z LEGO. Rodzice kupili mi jeden z pierwszych zestawów LEGO, jakie były w sprzedaży; w zasadzie składał się on z prostokątnych klocków. Miałem jednak wyobraźnię i mogłem zbudować w zasadzie cokolwiek, co tylko chciałem. Dzisiaj możesz kupić zestaw LEGO Star Wars i złożyć prefabrykowanego Yodę. O wiele trudniej zbudować teraz jakąś nową postać. Wydumane kształty klocków blokują wyobraźnię.

W klasycznym filmie z 1939 roku Czarnoksiężnik z krainy Oz jest scena, w której tytułowy czarnoksiężnik ujawnia się i krzyczy: „Nie zwracaj uwagi na człowieka za zasłoną”. Ta książka jest dla tych, którzy nie chcą usłuchać tego wezwania i chcą wiedzieć, co kryje się za zasłoną. Moim zamiarem jest rzucić nieco światła na podstawowe klocki, z których zbudowana jest funkcjonalność wysokiego poziomu. Ta książka jest dla tych, których wyobraźnia nie zadawala się samymi tylko funkcjonalnościami wysokiego poziomu – jest ona dla tych, którzy chcą tworzyć nowe funkcjonalności. Jeśli chcesz zostać czarnoksiężnikiem, a nie tylko wciąż posługiwać się gotowymi przedmiotami magicznymi, ta książka jest dla ciebie.

WPROWADZENIE

Kilka lat temu jechałem wyciągiem narciarskim z naszą szwedzką studentką z wymiany międzynarodowej. Zapytałem, czy zastanawiała się, co będzie robić po zakończeniu liceum. Powiedziała, że rozważała inżynierię i w poprzedniej klasie uczęszczała na kurs programowania. Zapytałem, czego tam uczyli. Opowiedziała: „Javy”. Odruchowo odpowiedziałem wtedy: „Szkoda”.

Dlaczego tak powiedziałem? Zrozumienie tego zajęło mi trochę czasu. Nie chodzi o to, jakoby Java była złym językiem programowania; tak naprawdę jest całkiem przyzwoitym. Powiedziałem to z powodu sposobu, w jaki teraz Java (i inne języki) używana jest do nauki programowania – tzn. bez uczenia niczego o komputerach. Jeśli to wydaje ci się dziwne, to jest to książka dla ciebie.

Język programowania Java został wynaleziony przez Jamesa Goslinga, Mike’a Sheridana i Patryka Naughtona w latach 90. XX wieku w Sun Microsystems. Został on częściowo ukształtowany na wzór języka C, który był w tych czasach w powszechnym użyciu. C nie zawiera automatycznego zarządzania pamięcią, a błędy związane z zarządzaniem pamięcią były wówczas częstą przyczyną bólów głowy. Java z założenia wyeliminowała tę klasę błędów programistycznych; ukryła przed programistą całe zarządzanie pamięcią. To między innymi dlatego Java jest tak dobrym językiem do uczenia początkujących programistów. Aby stworzyć dobrego programistę i dobre programy, potrzeba jednak znacznie więcej niż dobrego języka programowania. Okazało się, że Java wprowadziła nową klasę o wiele trudniejszych do debugowania problemów programistycznych związanych z niską wydajnością wywołaną ukrytym zarządzaniem pamięcią.

Jak można się przekonać, czytając tę książkę, zrozumienie działania pamięci jest kluczową umiejętnością dla programisty. Podczas nauki programowania łatwo wykształcić nawyki, które trudno potem będzie zmienić. Badania wykazały, że dzieci, które w dzieciństwie bawiły się na tzw. „bezpiecznych” placach zabaw, mają potem w życiu większy odsetek kontuzji niż te dzieci, które tak nie robiły. Prawdopodobnie dlatego, że na bezpiecznym placu zabaw trudno się nauczyć, że upadek boli. Programowanie jest sytuacją analogiczną. Bezpieczne środowiska programistyczne czynią start o wiele mniej przerażającym, ale trzeba się prędzej czy później przygotować na wyjście w świat zewnętrzny. Ta książka pomoże w takim przejściu.

Dlaczego dobre programowanie jest ważne

Aby zrozumieć, dlaczego uczenie programowania bez jednoczesnego uczenia o komputerach jest problematyczne, warto uświadomić sobie, jak wszechobecne stały się teraz komputery. Ich cena spadła tak drastycznie, że teraz ich użycie jest najtańszym sposobem wytworzenia wielu rzeczy. Na przykład wykorzystanie komputera do wyświetlenia obrazu zegara wskazówkowego w starym stylu na desce rozdzielczej auta jest teraz tańsze niż użycie zegara mechanicznego. Jest to rezultat aktualnie stosowanego sposobu produkcji podzespołów komputerowych: są one teraz w mniejszym lub większym stopniu drukowane. Nie jest już specjalnie trudnym zadaniem wyprodukowanie chipa z miliardami części: wychodzą one niemal dosłownie spod „stempla”. Należy zauważyć, że mowa tu o cenie samych komputerów, a nie o cenie przedmiotów zawierających te komputery. Ogólnie rzecz biorąc, chipy komputerowe kosztują teraz mniej niż opakowanie, w którym się je przesyła. Ich koszt jednostkowy liczony jest w groszach. Już wkrótce zapewne nadejdzie czas, gdy trudno będzie znaleźć cokolwiek, co nie zawiera komputera.

Wiele komputerów wykonujących wiele zadań oznacza wiele programów komputerowych. Ponieważ komputery są tak wszechobecne, programowanie komputerów stało się dziedziną niezwykle zróżnicowaną. Podobnie jak ma to miejsce na polu medycyny, wielu programistów zostaje specjalistami. Można specjalizować się w grafice, animacjach, stronach internetowych, aplikacjach na telefon, nadzorze przemysłowym, sprzęcie medycznym i tak dalej.

Dziwną rzeczą wyróżniającą programowanie jest to, że inaczej niż w medycynie, łatwo zostać specjalistą, nie będąc wcześniej wszechstronnym programistą. Prawdopodobnie nikt nie chciałby się oddać w ręce kardiochirurga, który nie ma pojęcia o ludzkiej anatomii, ale odpowiednik tej sytuacji stał się w zasadzie normą jeśli chodzi o dzisiejszych programistów. Ale czy rzeczywiście jest to problem? Tak naprawdę istnieje bogaty materiał dowodowy na to, że to nie działa zbyt dobrze, począwszy od niemal codziennych doniesień o naruszeniu bezpieczeństwa, po wycofywanie produktów z rynku. Istnieją zapisy spraw sądowych, w których oskarżeni o prowadzenie po pijanemu kierowcy uzyskiwali prawo do wglądu w kod alkomatu. Okazywało się, że kod jest pełen błędów, a to z kolei doprowadzało do obalenia wyroków. Niedawno program antywirusowy zawiesił sprzęt medyczny w trakcie operacji serca. Ludzie ginęli z powodu problemów z oprogramowaniem w samolocie Boeing 737 MAX. Wielka liczba podobnych wypadków nie wzbudza dużego zaufania.

Nauka programowania to dopiero początek

Częściowym powodem takiego stanu rzeczy jest fakt, że naprawdę nie jest trudno napisać program komputerowy, który wydaje się działać, lub taki, który działa w większości przypadków. Jako analogii użyjmy zmian w muzyce (nie disco!) lat 80. XX wieku. W dawniejszych czasach, by tworzyć muzykę, trzeba było najpierw nauczyć się podstaw. Obejmowało to naukę teorii muzyki i kompozycji, grę na instrumencie, trening słuchu i wiele, wiele praktyki. Wtedy pojawił się standard cyfrowego interfejsu instrumentów muzycznych (Musical Instrument Digital Interface), w skrócie MIDI. Opracowany przez Ikutaro Kakehashi z Roland, pozwalał każdemu na tworzenie muzyki na własnym komputerze i nikt nie musiał przy tym „dostawać odcisków”. Uważam, że tylko niewielki procent „muzyki” wytwarzanej komputerowo jest tak naprawdę muzyką – w większości jest to po prostu hałas. Muzyka jest tworzona przez prawdziwych muzyków, którzy mogą, lecz nie muszą korzystać z MIDI, by tworzyć na bazie własnej wiedzy i umiejętności. Programowanie zaczęło ostatnio przypominać używanie MIDI. Nie trzeba już się pocić czy spędzać lat na praktyce, czy nawet nauce teorii, by napisać jakiś program. Ale nie znaczy to, że są to programy, na których można polegać.

Ta sytuacja najprawdopodobniej tylko się pogorszy, przynajmniej w Stanach Zjednoczonych. Bogaci ludzie mający własne interesy, tacy jak na przykład właściciele firm produkujących oprogramowanie, od dawna lobbowali za ustawodawstwem zmuszającym każdego do nauki programowania w szkole. To brzmi świetnie w teorii, ale nie jest dobry pomysł w praktyce, ponieważ nie każdy ma predyspozycje, aby zostać dobrym programistą. Nie każemy wszystkim uczyć się gry w futbol, bo zdajemy sobie sprawę, że nie jest to sport dla każdego. Prawdziwym celem takiej inicjatywy nie jest najprawdopodobniej wykształcenie świetnych programistów, a raczej zwiększenie zysków firm przez zalanie rynku słabymi programistami, co doprowadziłoby do obniżenia płac. Ludzie stojący za tymi działaniami nie dbają zbytnio o jakość kodu, domagają się również wprowadzenia przepisów, które ograniczą ich odpowiedzialność za działanie wadliwych produktów. Oczywiście można sobie programować dla zabawy tak samo, jak można dla zabawy grać w futbol. Nie należy tylko spodziewać się przez to udziału w grze o Super Bowl.

W 2014 roku prezydent Obama stwierdził, że nauczył się kodowania. Poprzesuwał kilka rzeczy w skądinąd doskonałym narzędziu wizualnego programowania Blockly, a nawet napisał jeden wiersz kodu w JavaScripcie (języku programowania całkowicie niezwiązanym z Javą, wynalezionym w Netscape, poprzedniku Mozilla Foundation, na bazie której działa wiele pakietów webowych, w tym przeglądarka internetowa FireFox). Kto jednak myśli, że to oznacza, iż on naprawdę nauczył się programowania? Mała podpowiedź: jeśli ktoś uważa, że tak, to oprócz przeczytania tej książki powinien prawdopodobnie popracować nad umiejętnością krytycznego myślenia. Pewnie, mógł może się przyswoić jakiś mały fragment wiedzy o programowaniu, ale nie, nie nauczył się programować. Jeśli można by się było nauczyć programować w ciągu mniej więcej godziny, to programowanie musiałoby być na tyle trywialne, że nauczanie go w szkołach byłoby stratą czasu.

Znaczenie podstawowej wiedzy

Interesujący i nieco przeciwny do mojego pogląd na temat tego, jak uczyć programowania, został wyrażony na blogu przez Stephena Wolframa, twórcę programu Mathematica i języka Wolfram, we wpisie zatytułowanym „How to Teach Computational Thinking” (Jak nauczyć myślenia obliczeniowego). Wolfram definiuje myślenie obliczeniowe jako „formułowanie problemów na tyle jasno i systematycznie, by móc dzięki temu powiedzieć komputerowi, jak ma je rozwiązać”. Całkowicie się zgadzam z tą definicją. W rzeczywistości jest to w dużej mierze motywacja do napisania tej książki.

Stanowczo jednak nie zgadzam się ze stanowiskiem Wolframa, że ci, którzy uczą się programować, powinni rozwinąć swoje umiejętności myślenia obliczeniowego za pomocą potężnych narzędzi wysokiego poziomu, podobnych do tych, które on wynalazł, zamiast uczyć się podstawowych technologii. Na przykład na podstawie rosnącego zainteresowania statystyką w stosunku do rachunku różniczkowego, widać wyraźnie, że przekształcanie danych jest rozwijających się obszarem wiedzy. Co jednak się dzieje, gdy ludzie po prostu wrzucają stosy danych w program, z którego działaniem nie są dobrze obeznani?

Jednym z możliwych rezultatów jest generowanie wyników ciekawie wyglądających, lecz albo nieprawidłowych, albo wręcz bezsensownych. Niedawne badania (np. „Gene Name Errors are Widespread in the Scientific Literature” autorstwa Marka Ziemanna, Yotama Erena i Assama El-Osta) wykazały, że jedna piąta opublikowanych artykułów z dziedziny genetyki zawiera błędy powstałe przez nieprawidłowe posługiwanie się arkuszami kalkulacyjnymi. Pomyślmy o możliwych błędach i ich następstwach, gdyby jeszcze potężniejsze narzędzia znalazły się w rękach jeszcze większej liczby ludzi! Dokładne wykonanie jest bardzo ważne tam, gdzie rezultaty wpływają na życie ludzkie.

Zrozumienie podstawowych technologii pozwala wykształcić wyczucie tego, co może pójść źle. Znajomość jedynie narzędzi wysokiego poziomu sprawia, że zadaje się nie te pytania, co trzeba. Warto nauczyć się obsługi młotka, zanim przejdzie się do użycia gwoździarki. Innym powodem, dla którego warto poznać podstawowe systemy, jest fakt, że daje to możliwość budowania nowych narzędzi. Jest to bardzo ważne, ponieważ zawsze istnieje zapotrzebowanie na twórców narzędzi, nawet jeśli to użytkowników jest o wiele więcej. Poznanie budowy komputera na tyle, by zachowanie programu nie było tajemnicą, pozwala na pisanie lepszego kodu.

Kto powinien przeczytać tę książkę?

Ta książka jest dla tych, którzy chcą zostać dobrymi programistami. Co sprawia, że programista jest dobry? Przede wszystkim dobry programista ma wyrobione myślenie krytyczne i zdolność analizy. Do rozwiązywania złożonych problemów niezbędna jest umiejętność oceny, czy dany program rozwiązuje poprawnie dane zagadnienie. To jest o wiele trudniejsze, niż się wydaje. Nie jest niczym niecodziennym, gdy doświadczony programista patrzy na kod kogoś innego i złośliwie komentuje: „To bardzo skomplikowane nierozwiązanie bardzo prostego nieproblemu”.

Czytelnik może być obeznany z klasycznym motywem literatury fantastycznej, gdzie czarnoksiężnik zdobywa władzę magiczną nad przedmiotem przez poznanie jego prawdziwego imienia. Biada wtedy czarnoksiężnikowi, który by zapomniał o jakimś szczególe. Dobry programista jest jak czarnoksiężnik, który może uchwycić swoim umysłem istotę rzeczy bez pomijania szczegółów.

Dobry programista ma w sobie też pierwiastek artyzmu, jak wykwalifikowany rzemieślnik. Nie jest niczym niecodziennym znalezienie kawałka kodu, który jest całkowicie nieczytelny, tak jak wiele osób posługujących się językiem angielskim jest całkowicie zbitych z tropu powieścią Jamesa Joyce’a Finneganów tren. Dobry programista pisze kod, który nie tylko działa, ale też jest łatwy do zrozumienia i utrzymania dla innych.

I wreszcie, dobry programista musi dogłębnie rozumieć działanie komputerów. Nie można dobrze rozwiązywać skomplikowanych problemów, posługując się płytką bazą wiedzy. To jest książka dla tych, którzy uczą się programowania, ale są niezadowoleni z braku tej szczegółowej wiedzy. Jest ona również dla tych, którzy już programują, ale chcą czegoś więcej.

Czym jest komputer?

Powszechną odpowiedzią na to pytanie jest, że komputer jest urządzeniem, którego ludzie używają do zadań, takich jak sprawdzanie e-maili, zakupy internetowe, pisanie artykułów, porządkowanie zdjęć i gry komputerowe. Podobne odpowiedzi są rezultatem niedokładnej terminologii, która stała się powszechna wraz z pojawieniem się produktów konsumpcyjnych zawierających komputery. Inną powszechnie spotykaną odpowiedzią na to pytanie jest to, że komputery są mózgami, które pozwalają działać naszym zaawansowanym technicznie zabawkom, takim jak telefony komórkowe czy odtwarzacze muzyki. To już jest bliższe prawdy.

Wysyłanie e-maila czy granie jest możliwe dzięki programom działającym na komputerach. Sam komputer jest jak nowo narodzone dziecko. Nie bardzo wie, co ma robić. Zdecydowanie zbyt rzadko myślimy o podstawowej maszynerii ludzkiej, ponieważ mamy kontakt przeważnie tylko z konkretnymi osobowościami, które działają na tej maszynerii tak, jak programy działają na komputerze. Na przykład gdy przeglądasz stronę internetową, nie robisz tego z użyciem tylko swojego komputera: przeglądasz ją za pomocą programu, który napisał kto inny, a program ten działa na twoim komputerze, na komputerze hostującym stronę internetową i na wszystkich tych komputerach pomiędzy nimi, które sprawiają, że Internet działa.

Czym jest programowanie?

Nauczyciele są ludźmi, którzy trenują podstawową maszynerię ludzką do tego, by wykonywała ona określone zadania. Podobnie, programując, stajemy się nauczycielami komputerów. Programiści uczą komputery robić to, czego chcą.

Wiedza o tym, jak nauczyć czegoś komputery, bywa przydatna, zwłaszcza wtedy, gdy chciałoby się, by robiły coś, czego jeszcze nie umieją robić i gdy nie można po prostu pójść do sklepu i kupić do tego programu, ponieważ nikt jeszcze podobnego programu nie napisał. Na przykład większość czytelników zapewne uważa sieć WWW za coś oczywistego, ale została ona wynaleziona nie tak dawno temu, gdy Sir Tim Bernes-Lee potrzebował bardziej wydajnego sposobu komunikacji między naukowcami Europejskiej Organizacji Badań Jądrowych (Organisation Européenne pour la Recherche Nucléaire, CERN). I otrzymał za to tytuł rycerski[2]. Nieźle, prawda?

Uczenie komputerów jest skomplikowane, ale mimo wszystko prostsze niż uczenie ludzi. O wiele lepiej znamy funkcjonowanie komputerów niż ludzi. No i komputer raczej na nikogo nie zwymiotuje.

Programowanie komputera to proces dwuetapowy:

1. Zrozum wszechświat.

2. Wyjaśnij go trzylatkowi.

Co to oznacza? Nie można napisać programu komputerowego służącego do robienia rzeczy, których samemu się nie rozumie. Na przykład nie można napisać programu do sprawdzania pisowni, jeśli nie zna się zasad pisowni, i nie można napisać dobrej gry komputerowej, jeśli się nie zna fizyki. Tak więc pierwszym krokiem do pozostania dobrym programistą jest nauczenie jak najwięcej o wszystkim innym . Rozwiązania problemów można znaleźć często w bardzo zaskakujących miejscach, więc nie należy ignorować czegoś tylko dlatego, że nie od razu wydaje się istotne.

Drugi etap procesu wymaga wyjaśnienia tego, co się wie, maszynie, która ma, tak jak małe dzieci, bardzo sztywne spojrzenie na świat. Ta sztywność u dzieci jest naprawdę oczywista, gdy mają one około trzech lat. Powiedzmy, że próbujesz wyjść z dzieckiem na dwór. Pytasz go: „Gdzie są twoje buty?”, a ono odpowiada: „Tam”. Odpowiedziało przecież na pytanie. Problem polega na tym, że nie rozumie ono, że tak naprawdę mówisz mu, żeby założyło buty, byście oboje mogli wyjść z domu i pójść gdzieś. Elastyczność i zdolność do wyciągania wniosków to umiejętności, których dzieci nabywają w miarę dorastania. Ale komputery są jak Piotruś Pan: nigdy nie dorastają.

Komputery przypominają małe dzieci pod jeszcze jednym względem: nie potrafią generalizować. Są oczywiście bardzo pożyteczne, bo gdy już wykombinuje się, jak przekazać im jakieś instrukcje, będą to robić bardzo szybko i bez znużenia, choć same nie mają ani trochę zdrowego rozsądku. Komputer bez znużenia będzie wykonywał zadaną czynność bez wnikania w to, czy jest to właściwe zadanie – tak jak zaczarowana miotła z Ucznia czarnoksiężnika, fragmentu filmu Fantazja z 1940 roku. Proszenie komputera o zrobienie czegoś jest jak proszenie dżina z magicznej lampy (tylko nie w wersji FBI) o spełnienie życzenia. Trzeba być naprawdę ostrożnym w wyborze życzenia!

Możesz wątpić z to, co tu mówią, gdyż komputery wydają się o wiele bardziej zdolne niż rzeczywiście są. Kiedy używa się komputera, może on wiedzieć na przykład, jak rysować rysunki, poprawiać czyjąś pisownię, rozumieć wypowiadane słowa, odtwarzać muzykę i tak dalej. Należy jednak pamiętać, że to nie komputer – to skomplikowany zbiór programów komputerowych, które ktoś wcześniej napisał, a które pozwalają komputerowi wykonywać te wszystkie zadania. Komputery należy oddzielić od programów, które na nich są wykonywane.

To trochę jak obserwowanie samochodu na drodze. Wydaje się, że samochód całkiem nieźle się zatrzymuje i rusza w odpowiednich momentach, unika przeszkód, dociera do celu, je, gdy jest głodny i tak dalej. Ale to nie jest tylko samochód. To samochód i kierowca zapakowane razem. Komputery są jak samochody, a programy są jak kierowcy. Nie mając wiedzy, nie można orzec, która czynność wykonywana jest przez kierowcę, a która przez samochód (patrz wiersz autorstwa May Swenson, Southbound on the Freeway. Odpowiedź na ostatnie pytanie postawione w tym wierszu może zmieniać się z wiekiem czytającego).

Podsumowując, programowanie komputerowe wymaga nauczenia się tego, co jest potrzebne, by rozwiązać zadany problem, a potem wytłumaczyć to małemu dziecku. Ponieważ istnieje wiele sposobów na rozwiązanie problemu, programowanie w równym stopniu jest sztuką i nauką. Polega ono na znajdowaniu eleganckiego rozwiązania w przeciwieństwie do siłowego rozwiązywania problemów. Tak, można wyjść z domu, robiąc dziurę w ścianie, ale zapewne łatwiej jednak wyjść drzwiami. Wiele osób potrafi napisać coś takiego jak HealthCare.org w milionach wierszy kodu, ale potrzeba umiejętności, by zmieścić to w tysiącach wierszy.

Zanim jednak można cokolwiek wytłumaczyć trzylatkowi, trzeba się nieco nauczyć na temat trzylatków oraz tego, co mogą zrozumieć. I nie jest to jakiś zwykły trzylatek – to obca forma życia. Komputer nie gra według tych samych zasad co my. Zapewne wielu z was słyszało o sztucznej inteligencji (AI), która stara się, by komputery zachowywały się bardziej jak ludzie. Postęp w tej dziedzinie zachodzi o wiele wolniej, niż to z początku przewidywano. Głównie dlatego, że tak naprawdę w większości nie rozumiemy problemu: nie wiemy dostatecznie wiele na temat tego, jak myśli człowiek. Tak jak można sobie wyobrazić, nie jest łatwo nauczyć ufoludka myśleć tak jak my, jeśli my sami mamy niewielkie pojęcie o tym, jak to dokładnie się odbywa.

Ludzki mózg pozwala nam robić rzeczy bez konieczności świadomego myślenia o nich. Nasze mózgi są na początku czystym, niezapisanym sprzętem, który następnie jest programowany. Na przykład uczymy się poruszać palcami, by następnie nauczyć się chwytać przedmioty. Po odpowiedniej praktyce można po prostu złapać jakąś rzecz, nie myśląc o każdym ruchu, jaki w tym celu trzeba wykonać. Tacy filozofowie, jak Jean Piaget (1898–1980, francuski psycholog) czy Noam Chomsky (ur. 1928, amerykański lingwista) opracowali różne teorie na temat tego, jak odbywa się ten proces uczenia się. Czy mózg jest w miarę jednorodną maszyną ogólnego przeznaczenia, czy też ma specjalny sprzęt do takich funkcji jak język? Ta kwestia nadal jest badana.

Nasza niezwykła zdolność do nieświadomego wykonywania czynności sprawia, że nauka programowania jest trudna, ponieważ programowanie wymaga, by każde zadanie rozłożyć na części składowe, na kroki, które komputer jest w stanie wykonać. Na przykład większość czytelników najprawdopodobniej wie, jak grać w kółko i krzyżyk. Dla eksperymentu warto zebrać razem grupę ludzi i niech każdy niezależnie wypisze ruchy, jakie powinien wykonać gracz w zależności od sytuacji na planszy (z pewnością można znaleźć w Internecie pełną listę ruchów, ale nie warto psuć sobie zabawy). Gdy już każdy zakończy swoją listę, zróbcie zawody. Dowiecie się, czyje reguły wygrywają! Jak dobre były twoje reguły? Czego w nich zabrakło? Czy wiedziałeś, co tak naprawdę robisz, gdy grasz w tę grę? Najprawdopodobniej części czynników zabrakło w spisie, ponieważ gracz rozumie je intuicyjnie i zapomniał je wypisać.

Na wypadek, jeśli jeszcze nie jest to oczywiste: pierwszy krok, zrozumienie wszechświata, jest o wiele ważniejszy niż ten drugi, wyjaśnienie wszystkiego trzylatkowi. Wystarczy chwilę pomyśleć: jaki jest pożytek z wiedzy o sposobie mówienia, skoro się nie wie, co powiedzieć? Mimo to aktualnie nauczanie programowania skupia się na drugim kroku. Dzieje się tak dlatego, że o wiele łatwiej nauczać i oceniać mechaniczne aspekty zadania niż jego aspekty kreatywne. Po części również dlatego, że nauczyciele przeważnie nie mają doświadczenia w przedmiocie, który wykładają i korzystają z programów nauczania opracowanych gdzie indziej. Ta książka jednak skupia się na pierwszym kroku. Chociaż nie może ona obejmować opisu całego wszechświata, skupia się ona na opisie problemów i ich rozwiązań w świecie komputerów, zamiast zajmować się dokładną składnią programowania potrzebnego do implementacji tych rozwiązań.

Kodowanie, programowanie, inżynieria i informatyka

Do opisu prac nad oprogramowaniem używa się szeregu różnych terminów. Nie mają one oficjalnych definicji, chociaż z czasem nabrały dość określonego znaczenia.

Kodowanie jest względnie nowym terminem, spopularyzowanym jako część ruchu „uczenia się kodowania” – może być ono rozumiane jako mechaniczna praca tłumaczenia. Porównajmy kodowanie komputerowe do kodowania medycznego. Podczas wizyty u lekarza postawienie diagnozy to łatwa część. Trudną częścią zadania jest przetłumaczenie diagnozy na jeden z ponad stu tysięcy kodów składających się na najnowszy standard ICD (w czasie, kiedy to piszę, jest to standard ICD-10). Certyfikowany koder zawodowy, który nauczył się wszystkich tych kodów na pamięć, wie, że jeśli doktor wymyśli diagnozę „uderzony przez krowę”, trzeba będzie przypisać choremu kod W55.2XA. To jest tak naprawdę trudniejsze niż większość kodowania w branży programistycznej, chociażby z powodu ilości dostępnych kodów. Sam jednak proces jest podobny do tego, co dzieje się, gdy poinstruujemy kodera, by „pogrubił ten tekst” na stronie internetowej – koder wie, jakiego kodu użyć, by to się stało.

Standard ICD-10 jest tak skomplikowany, że niewielu jest koderów, którzy znają go w całej rozciągłości. Koderzy medyczni certyfikują się zamiast tego w obszarach specjalizacji, na przykład „choroby układu nerwowego” czy „zaburzenia mentalne i behawioralne”. Podobnie programista może być biegły w konkretnym języku, takim jak HTML czy JavaScript.

Ale programowanie – tzn. bycie programistą – oznacza zna się na czymś więcej niż tylko jednena czy dwa obszary specjalizacji. W naszej analogii odpowiednikiem programisty jest lekarz. Stawia on diagnozę przez zbadanie pacjenta. To zadanie może być bardzo skomplikowane. Na przykład, jeśli pacjent ma poparzenia i jest przemoczony, to czy jest to przypadek „dziwacznego wyglądu osobistego” (R46.1), czy też „poparzenia w wyniku pierwszego zetknięcia z płonącymi nartami wodnymi” (V91.07XA)? Gdy już lekarz wystawi diagnozę, można opracować plan leczenia. Plan musi być skuteczny, lekarz prawdopodobnie nie chciałby zobaczyć tego samego pacjenta ponownie, tym razem jako ofiary ostrego przypadku „nadopiekuńczości rodzicielskiej” (Z62.1).

Tak jak czyni to lekarz, programista ocenia problem i określa rozwiązanie. Istnieje, być może, potrzeba utworzenia strony internetowej, na której użytkownicy mogliby tworzyć ranking najbardziej niemądrych kodów ICD-10. Programista jest w stanie określić najlepszy algorytm przechowywania danych i operowania na nich, strukturę komunikacji klienta z serwerem, interfejs użytkownika i tak dalej. To nie jest proste „wklejanie kodu”.

Inżynieria to kolejny krok w kierunku złożoności. Ogólnie rzecz biorąc, inżynieria to sztuka zastosowania posiadanej wiedzy do wykonywania jakichś zadań. Można uznać stworzenie standardu ICD za przykład inżynierii: wzięto ogromny obszar diagnozy lekarskiej i zredukowano go do zestawu kodów, które można o wiele łatwiej śledzić i analizować niż notatki lekarskie. Jest kwestią opinii, czy system tak bardzo skomplikowany jest przykładem dobrej inżynierii. Jako przykład inżynierii komputerowej, wiele lat temu pracowałem w projekcie mającym na celu wyprodukowanie tanich monitorów medycznych, takich jakie widać niekiedy w szpitalach. Moim zadaniem było opracowanie systemu, który doktor albo pielęgniarka mogliby rozgryźć w pięć minut bez pomocy dokumentacji. Jak można sobie wyobrazić, zadanie wymagało o wiele więcej niż tylko wiedzy dotyczącej programowania. Ja wykonałem zadanie nawet lepiej – moje rozwiązanie wymaga mniej więcej 30-sekundowej nauki.

Programowanie jest często mylone z informatyką. Choć wielu informatyków programuje, większość programistów nie jest informatykami. Informatyka jest nauką o obliczeniach. Odkrycia z zakresu informatyki wykorzystywane są zarówno przez inżynierów oprogramowania, jak i przez programistów.

Kodowanie, programowanie, inżynieria programowania i informatyka są oddzielnymi, choć powiązanymi ze sobą dyscyplinami. Różnią się od siebie rodzajem i ilością wiedzy, jakiej wymagają. Bycie informatykiem, inżynierem oprogramowania lub koderem nie czyni nikogo automatycznie dobrym programistą. Ta książka daje jakieś pojęcie o tym, jak myślą inżynierowie i informatycy, ale nikogo nie uczyni ani jednym, ani drugim. To wymaga kierunkowego wykształcenia połączonego ze zdobyciem doświadczenia. Inżynieria i programowanie podobne są muzyki lub malarstwa – to po części umiejętności, a po części sztuka. Przedstawienie obu tych aspektów w tej książce powinno pomóc każdemu w rozwoju jego umiejętności programistycznych.

Krajobraz

Projektowanie i programowanie komputerów jest ogromną dziedziną wiedzy, której nie będę mógł tutaj umówić w pełni. Można ją sobie wyobrazić w postaci warstw, tak jak to pokazano na rysunku 1.

Rysunek 1. Krajobraz komputerowy

Należy pamiętać o tym, że rysunek 1 jest uproszczeniem i że linie oddzielające od siebie poszczególne warstwy w rzeczywistości nie są aż tak wyraźne.

Większość ludzi jest użytkownikami systemów komputerowych. Czytelnicy tej książki zapewne są teraz w tej grupie. Istnieje wydzielony rodzaj wyspecjalizowanych użytkowników nazywanych administratorami systemu, których zadaniem jest utrzymanie nieprzerwanego działania systemu. To oni instalują oprogramowanie, zarządzają kontami użytkowników, robią kopie zapasowe i tak dalej. Zazwyczaj mają specjalne uprawnienia, których nie nadaje się zwykłym użytkownikom.

Ludzi, którzy piszą programy, takie jak strony internetowe, aplikacje na smartfony, czy odtwarzacze muzyki, nazywamy programistami aplikacji. Tworzą oni oprogramowanie, którego użytkownicy używają do interakcji z komputerami. Korzystają przy tym z bloków utworzonych przez innych. Programowania aplikacji uczy się na większości kursów w stylu „naucz się kodować”, tak jakby wszyscy programiści musieli się nauczyć, jak importować te czy inne bloki składowe i skleić je razem. Chociaż w większości przypadków wystarcza to do wykonania zadania, o wiele lepiej poznać zarówno te bloki, jak i klej, którego się używa.

Programy aplikacyjne nie rozmawiają bezpośrednio z sprzętem komputerowym – to tutaj programowanie systemowe wchodzi do gry. Programiści systemowi budują bloki używane przez programistów aplikacji. Muszą oni znać budowę sprzętu, ponieważ ich kod się z nim komunikuje. Jednym z celów tej książki jest nauczenie czytelnika rzeczy, które trzeba wiedzieć, by być dobrym programistą systemowym.

Sprzęt komputerowy (hardware) zawiera nie tylko część wykonującą właściwe obliczenia, lecz także określa, jak ta część komunikuje się ze światem zewnętrznym. Sprzęt jest wyrażony poprzez układy logiczne. Układy logiczne stanowią fizyczne wcielenie tej samej logiki, która jest używana do pisania programów komputerowych i jest kluczowa do zrozumienia pracy komputera. Układy logiczne są zbudowane z różnego rodzaju obwodów elektronicznych. Projektowanie obwodów wykracza poza zakres tej książki, ale można się wiele się o nich dowiedzieć, studiując elektrotechnikę. Jeśli chcesz rządzić światem, rozważ podwójny dyplom: z elektrotechniki i informatyki.

Oczywiście u podstaw tego wszystkiego kryją się nauki podstawowe, które dają nam wszystko – od zrozumienia elektryczności po wiedzę chemiczną niezbędną do budowy mikroprocesorów.

Tak jak to pokazano na rysunku 1, każdy poziom bazuje na tym, co znajduje się pod nim. Oznacza to, że błędy lub nieoptymalne wybory na niższych poziomach będą wpływały na wszystko powyżej. Błąd projektanta w procesorach Intel Pentium około 1994 roku sprawił, że niektóre operacje dzielenia dawały niedokładne wyniki. To miało wpływ na całe oprogramowanie, które korzystało z dzielenia zmiennoprzecinkowego wykonywanego na tych procesorach.

Jak widać, programowanie systemowe znajduje się na dole hierarchii oprogramowania. Jest ono podobne do infrastruktury, takiej jak drogi, elektryczność, woda. Zawsze jest ważne, żeby być dobrym programistą, ale jest to tym ważniejsze, jeśli jesteś programistą systemowym, ponieważ inni opierają swą pracę na zbudowanej przez ciebie infrastrukturze. Widać również, że programowanie systemowe jest umieszczone między programowaniem aplikacji a sprzętem komputerowym, co oznacza, że programista systemowy musi sporo wiedzieć o jednym i o drugim. Słowo „joga” w sanskrycie tłumaczy się jako „jedność”, i tak jak praktykujący jogę poszukują zjednoczenia swojego umysłu i ciała, programiści systemowi są techno-joginami, którzy jednoczą sprzęt z oprogramowaniem.

Nie trzeba uczyć się programowania systemowego, by pracować na którymś z pozostałych poziomów. Ale jeśli się tego nie nauczymy, będziemy zdani na pomoc innej osoby w rozwiązaniu problemów spoza własnej dziedziny, zamiast po prostu rozwiązać je samemu. Rozumienie istotnych technologii prowadzi również do lepszego wyboru rozwiązań na wyższym poziomie. To nie jest jedynie moja opinia: zachęcam do przeczytania postu z 2014 roku: „The Resource Leak Bug of Our Civilisation” („Błąd wycieku zasobów naszej cywilizacji”) autorstwa Ville-Matias Heikkila.

Celem tej książki jest także opisanie wielu historii retro. Większość programistów nie uczy się historii własnego rzemiosła, ponieważ i bez tego jest mnóstwo materiału do opanowania. W rezultacie większość ludzi popełnia te same błędy, które już wielokrotnie były popełnianie w przeszłości. Poznanie nieco historii programowania umożliwia przynajmniej robienie nowych i „lepszych” błędów zamiast powtarzania starych. Należy też pamiętać, że nowe, pionierskie technologie ery dzisiejszej bardzo szybko staną się technologiami retro dla jutra.

Skoro już mowa o historii, w książce tej pełno jest interesujących technologii i nazwisk ich wynalazców. Warto poświęcić nieco czasu, aby dowiedzieć się czegoś więcej zarówno na temat technologii, jak i ludzi. Większość z wymienionych tu osób rozwiązała w życiu przynajmniej jeden interesujący problem i warto dowiedzieć się, jak postrzegali oni swój świat i w jaki sposób podchodzili do problemów i je rozwiązywali. W powieści Neala Stephensona z 2008 roku Anatema znajduje się świetna wymiana zdań:

– Nasz przeciwnik to statek kosmiczny obcych wypchany bombami atomowymi. My dysponujemy kątomierzem.

– Dobrze. Pójdę do domu i zobaczę, czy uda mi się znaleźć linijkę i kawałek sznurka.

Zwróćmy uwagę na to opieranie się na rzeczach podstawowych. Żadnego „zobaczmy w Wikipedii, jak to zrobić” czy „zamieszczę zapytanie na Stack Overflow”, czy też „znajdę jakiś pakiet na GitHubie”. Nauczenie się rozwiązywania problemów, których jeszcze nikt przed nami nie rozwiązał, jest kluczową umiejętnością programisty.

Wiele przykładów umieszczonych w tej książce opiera się na starych technologiach, takich jak komputery 16-bitowe. A to dlatego, że na ich podstawie można nauczyć się niemal wszystkiego, co jest potrzebne, a jednocześnie łatwiej zmieścić je na stronie.

Co się znajduje w tej książce

Książka ta jest konceptualnie podzielona na trzy części. Pierwsza z nich omawia sprzęt komputerowy – zarówno to, czym on jest, jak i jego budowę. Druga część opisuje zachowanie oprogramowania działającego na tym sprzęcie. Ostatnia część omawia sztukę programowania – współpracy z innymi w celu wytworzenia dobrego oprogramowania.

Rozdział 1: Język wewnętrzny komputerów

W tym rozdziale zaczynamy przyglądać się mentalności trzylatka. Komputery to gracze bitowi; ich zawód to hodowla bitów. Nauczysz się, czym są bity i co można z nimi zrobić. Zabawimy się w udawanie, aby nadać znaczenie bitom i zbiorom bitów.

Rozdział 2: Układy kombinacyjne

W tym rozdziale poznasz powody, dla których używa się bitów zamiast cyfr i przeanalizujemy uzasadnienie dla komputerów cyfrowych. Rozważania te obejmują omówienie jednej z najstarszych technologii, jakie przetarły ścieżki dla tych, których obecnie używamy. Poznasz podstawy układów kombinacyjnych. Nauczysz się, jak budować bardziej skomplikowane funkcjonalności z bitów i układów.

Rozdział 3: Układy sekwencyjne

Tutaj dowiesz się, jak użyć układów logicznych do zbudowania pamięci. Obejmuje to zagadnienie wytworzenia czasu, gdyż pamięć jest niczym innym jak stanem, który utrzymuje się w czasie. W tym rozdziale poznasz podstawy układów sekwencyjnych i omówimy różne technologie pamięci.

Rozdział 4: Anatomia komputera

W tym rozdziale dowiesz się, w jaki sposób komputery zbudowane są z układów logicznych i elementów pamięci omawianych we wcześniejszych rozdziałach. Przeanalizujemy kilka różnych metodologii implementacyjnych.

Rozdział 5: Architektura komputera

W tym rozdziale zajmiemy się z kilkoma dodatkami do prostego komputera, jaki widzieliśmy w rozdziale 4. Dowiesz się, w jaki sposób zapewniają one istotne funkcjonalności i wydajność.

Rozdział 6: Rozkład komunikacji

Komputery powinny komunikować się ze światem zewnętrznym. W tym rozdziale poznasz urządzenia wejścia i wyjścia. Przeanalizujemy też różnicę między tym, co cyfrowe a tym, co analogowe i zastanowimy się, jak cyfrowe komputery mogą działać w świecie analogowym.

Rozdział 7: Organizacja danych

Gdy już wiesz, jak działają komputery, zobaczymy, jak z nich efektywnie korzystać. Programy komputerowe operują na danych w pamięci, jest więc istotne, by odwzorować sposób korzystania z pamięci na problem, jaki chcemy rozwiązać.

Rozdział 8: Przetwarzanie języka

Języki (programowania) wynaleziono po to, by ułatwić ludziom programowanie komputerów. W tym rozdziale przyjrzymy się procesowi przemiany języków w coś, co naprawdę działa na komputerze.

Rozdział 9: Przeglądarki internetowe

Wiele prac programistycznych wykonuje się na potrzeby przeglądarek internetowych. W tym rozdziale przyjrzymy się sposobowi działania przeglądarki internetowej oraz jej głównym częściom składowym.

Rozdział 10: Programowanie aplikacyjne i systemowe

W tym rozdziale utworzymy dwie różne wersje programu, które działają na dwóch poziomach z rysunku 1. W ten sposób pokażemy główne różnice między programowaniem aplikacyjnym a systemowym.

Rozdział 11: Skróty i przybliżenia

Bardzo ważne, aby tworzyć wydajne programy. W tym rozdziale przyjrzymy się niektórym sposobom na to, by programy były bardziej wydajne i nie wykonywały niepotrzebnej pracy.

Rozdział 12: Zakleszczenia i wyścigi

Wiele systemów składa się z więcej niż jednego komputera. W tym rozdziale poznasz kilka problemów, które mogą wystąpić, gdy staramy się zmusić komputery do współpracy.

Rozdział 13: Bezpieczeństwo

Bezpieczeństwo komputerowe to zaawansowany temat. W tym rozdziale przedstawiamy podstawy tego zagadnienia, unikając przy tym ciężkiej matematyki.

Rozdział 14: Sztuczna inteligencja

W tym rozdziale znów zmierzymy się ze skomplikowanym zagadnieniem. Z połączenia wielkich danych, sztucznej inteligencji i uczenia się maszyn powstają nowe aplikacje – od prowadzenia samochodu aż po doprowadzenie wszystkich do załamania nerwowego za pomocą reklam.

Rozdział 15: Świat realny

Programowanie jest procesem bardzo metodycznym i logicznym. Jednak w określanie co i jak programować zaangażowani są również ludzie, a ludziom często brakuje logiki. W tym rozdziale omówiono kilka zagadnień dotyczących programowania w świecie rzeczywistym.

Podczas lektury książki warto pamiętać, że wiele spośród wyjaśnień jest uproszczonych, a przez to mogą nie być prawidłowe we wszystkich szczegółach. Dalsze udoskonalenie tych wyjaśnień wymagałoby jednak zbyt wielu rozpraszających szczegółów. Jeśli w miarę postępów nauki zaczniesz odkrywać takie nieścisłości, nie bądź tym zaskoczony. Można uznać tę książkę za skrótową broszurę biura podróży reklamującą wycieczkę do krainy komputerów. Nie jest możliwe, aby zawierała wszystko w najdrobniejszych szczegółach, a gdy już się tam wybierzesz, odkryjesz wiele subtelnych różnic między broszurą a rzeczywistością.

1

Język wewnętrzny komputerów

Całym sensem istnienia języka jest możliwość przekazywania informacji. Zadaniem programisty jest przekazanie instrukcji do komputera. Komputery nie rozumieją języka programisty, więc on musi nauczyć się ich języka.

Język ludzki jest owocem tysięcy lat ewolucji. Nie wiemy zbyt wiele o tym, jak dokładnie ewoluował, ponieważ wczesny rozwój języka nie był na tyle zaawansowany, by umożliwić tworzenie historii (najwyraźniej nikt nie tworzył ballad o rozwoju języka). Języki komputerowe to zupełnie inna historia, ponieważ są wynalazkiem stosunkowo nowym, który pojawił się długo po rozwoju języka ludzkiego i dzięki temu jesteśmy w stanie o nich pisać.

Języki ludzkie i komputerowe mają wiele wspólnych cech, takich jak pisane symbole i reguły ich prawidłowego ułożenia i użycia. Jedyne, czego nie mają ze sobą wspólnego, to język mówiony; komputery dysponują jedynie językiem pisanym.

W tym rozdziale zaczniemy uczyć się języka komputerów. Ten proces odbywa się etapami, dokładnie tak jak w przypadku języków ludzkich. Musimy zacząć od liter, zanim przejdziemy do słów i zdań. Na szczęście języki komputerowe są znacznie prostsze niż ich ludzkie odpowiedniki.

Czym jest język?

Język jest wygodnym skrótem. Pozwala nam komunikować złożone pojęcia bez konieczności ich pokazywania. Pozwala nawet na przekazywanie pojęć na odległość, a nawet za pomocą nośników pośrednich.

Każdy język – czy to pisany, mówiony, czy wyrażany jako seria gestów lub przez uderzanie dwóch kamieni o siebie – to znaczenie zakodowane jako seria symboli. Zakodowanie znaczeń w symbolach jednak nie wystarczy. Język działa jedynie wtedy, gdy wszystkie komunikujące się między sobą strony mają ten sam kontekst, dzięki czemu mogą przypisać to samo znaczenie do tych samych symboli. Na przykład słowo Toto mogłoby wielu ludziom sugerować psa z Czarnoksiężnika z krainy Oz, podczas gdy dla pozostałych byłaby to raczej nazwa japońskiej firmy trudniącej się wytwarzaniem podgrzewanych desek sedesowych. Niedawno natrafiłem na spore zamieszanie dookoła terminologii odzieżowej z jednym z moich francuskich studentów z wymiany międzynarodowej. Okazuje się, że podczas gdy w Ameryce najczęstszą interpretacją słowa camisole jest „podkoszulek”, po francusku znaczy to „kaftan bezpieczeństwa”! W obu przypadkach równokształtne symbole mogą być rozróżnione tylko przez kontekst, a ten nie zawsze łatwo rozpoznać. Języki komputerowe też mają swoje problemy.

Język pisany

Język pisany jest ciągiem symboli. Słowa tworzymy przez odpowiedni układ symboli. Na przykład w języku polskim możemy uformować słowo dam przez ustawienie trzech symboli (tj. liter) od lewej do prawej strony w następującej kolejności: d, a, m.

Istnieje wiele możliwych symboli i ich kombinacji. W języku polskim mamy 32 podstawowe symbole (A–Ż), których uczymy się jeszcze w przedszkolu (35, jeśli liczyć pojawiające się w zapożyczonych słowach X, Q i V). Pomijamy przy tym niuanse, takie jak rozróżnienie liter na wielkie i małe, interpunkcję, ligatury i tak dalej. Inne języki mają inną liczbę symboli lub inne ich typy. Niektóre języki, takie jak chiński czy japoński zapisywany za pomocą alfabetu kanji, mają bardzo wiele różnych znaków, przy czym każdy z tych symboli sam w sobie jest już pełnoprawnym słowem.

W językach stosuje się też różne kolejności symboli, na przykład w hebrajskim czyta się od prawej do lewej, a w chińskim – pionowo. Kolejność symboli oczywiście jest ważna: masło to nie to samo, co słoma.

Chociaż oczywiście styl może być rozpatrywany jako język sam w sobie, nie będziemy tu rozróżniać symboli ze względu na krój pisma: a, a i a są takim samym symbolem.

Ramy technologii języka pisanego, w tym także języka komputerowego, tworzą trzy części składowe:

- pojemniki zawierające symbole,

- symbole, które dopuszczamy w pojemnikach,

- kolejność pojemników.

W niektórych językach przyjmuje się bardziej skomplikowane reguły ograniczające rodzaje dostępnych symboli w pojemnikach na podstawie symboli, które już pojawiły się w innych pojemnikach. Na przykład niektóre symbole nie mogą nigdy zajmować sąsiadujących z sobą pojemników.

Bit

Zacznijmy od pojemnika. W ludzkim języku będzie nim litera, w języku zaś komputerowym – bit. Słowo bit jest nieco dziwnym rezultatem ożenienia z sobą dwóch angielskich słów – binary („dwójkowa”) i digit ( „cyfra”). Może się to wydawać nieco niezręczne, ponieważ dwójkowy oznacza coś, co składa się z dwóch części, cyfra zaś jest słowem, którego zazwyczaj używamy w celu nazwania jednego z 10 symboli (0–9), bo tak wygląda nasz codzienny, zwyczajny system numeryczny. W następnym rozdziale dowiesz się, dlaczego używa się właśnie bitów, a do tego czasu wystarczy wiedzieć, że bity są tanie i łatwe do zbudowania.

Bit jest dwójkowy, co oznacza, że pojemnik bitowy może zawierać tylko jeden z dwóch symboli, trochę jak kreska i kropka z kodu Morse’a. Kod Morse’a używa tylko dwóch symboli do przedstawienia złożonej informacji przez łączenie tych dwóch symboli w ciągi o różnych kombinacjach. Na przykład litera A to kropka-kreska. B to kreska-kropka-kropka-kropka, C to kreska-kropka-kreska-kropka i tak dalej. Kolejność występowania symboli jest tak samo ważna tak samo jak w języku naturalnym: kreska-kropka oznacza N, nie A.

Symbole jest pojęciem abstrakcyjnym. Naprawdę nie ma znaczenia, z jaki sposób są one przedstawiane – może to być włączone-wyłączone, noc i dzień czy kaczka i gęś. Ale pamiętajmy, że język nie działa bez kontekstu. Sprawy mogłyby potoczyć się nieco dziwnym torem, gdyby nadawca sądził, że nadaje U, a odbiorca usłyszał jedynie „kaczka, kaczka, gęś”[3].

W pozostałej części tego rozdziału przyjrzymy się kilku najczęstszym sposobom przypisywania znaczeń bitom w celu wykonywania na nich obliczeń. Pamiętajmy, że sporo w tym zabawy w udawanie – możemy na przykład natknąć się na zdania w stylu „udawajmy teraz, że ten bit oznacza kolor niebieski”. Programowanie w zasadzie działa w ten sposób, zachęcam więc wszystkich, by poza nauczeniem się standardowych sposobów wykorzystywania bitów nie bał się również wynajdywać własnych, gdy zajdzie taka potrzeba.

Operacje logiczne

Jednym z zastosowań bitów jest przedstawienie odpowiedzi „tak” lub „nie” na pytania, takie jak „Czy jest zimno?” lub „Czy podoba ci się mój kapelusz?”. Używamy terminu prawda dla „tak” i fałsz dla „nie”. Na pytania w stylu „Gdzie odbywa się przyjęcie dla psów?” nie ma odpowiedzi „tak” lub „nie”, nie mogą więc one być reprezentowane przez jeden bit.

W języku naturalnym często łączymy kilka klauzul „tak/nie” w jednym zdaniu. Możemy na przykład powiedzieć „Noś kurtkę, jeśli jest zimno lub pada deszcz” albo „Można iść na narty, jeśli leży śnieg i nie jest to dzień szkoły”. Innym sposobem na powiedzenie tego samego mogłoby być „Noś kurtkę, jeśli zimno jest prawdą lub deszcz jest prawdą” oraz „Pójście na narty jest prawdą, jeśli padanie śniegu jest prawdą i dzień szkolny nie jest prawdą”. Używamy tutaj operatorów logicznych, które wytwarzają nowe bity w zależności od zawartości innych bitów.

Algebra boolowska

Tak samo jak algebra jest zestawem zasad rządzących działaniami na liczbach, algebra boolowska, wynaleziona w XIX wieku przez angielskiego matematyka George’a Boole’a, jest zestawem zasad rządzących działaniami na bitach. Tak jak w zwyczajnej algebrze, tu również obowiązują zasady łączności, przemienności i rozdzielności działań.

Istnieją trzy podstawowe działania boolowskie, NOT, AND i OR oraz jedno złożone[4] działanie XOR (exclusive-or – alternatywa wykluczająca ). Poniżej opisujemy je wszystkie:

NOT, czyli polskie „nie”, odpowiadające logicznej negacji – to działanie oznacza przeciwieństwo. Jeśli, na przykład, dany bit jest fałszem, operacja NOT na tym bicie daje prawdę. Jeśli bit jest prawdą, operacja NOT na tym bicie daje fałsz.

AND, czyli polskie „i”, odpowiadające logicznej koniunkcji – to działanie na dwóch lub większej liczby bitów. W dwubitowej wersji tego działania wynik jest prawdą tylko wtedy, gdy zarówno pierwszy, jak i drugi bit są prawdą. W wielobitowej wersji tego działania rezultat jest prawdą tylko wtedy, gdy wszystkie bity są prawdą.

OR, czyli polskie „lub”, odpowiadające logicznej alternatywie – to działanie również na dwóch lub większej liczbie bitów. W dwubitowej wersji tego działania wynik jest prawdą, jeśli pierwszy lub drugi bit jest prawdą, a w przeciwnym przypadku wynik jest fałszem. W wersji wielobitowej wynik jest prawdą, jeśli przynajmniej jeden z bitów jest prawdą.

XOR, odpowiadające logicznej alternatywie rozłącznej – to działanie jest prawdą, jeśli pierwszy i drugi bit mają różne wartości. Zachodzi jeden z nich, ale nie oba (tj. albo jeden, albo drugi). Ponieważ nazwa tego działania jest zbyt długa do wymawiania, często używamy skrótu XOR (wymawiany po ang. „eks-or”).

Na rysunku 1.1 podsumowano wymienione wyżej działania boolowskie w sposób graficzny z użyciem czegoś, co nazywamy tabelą prawdy. Bity wejściowe wymienione są na zewnątrz tabeli, a bity wyjściowe w środku. Prawdę oznaczamy jako T (od ang. true), a fałsz jako F (od ang. false).

Rysunek 1.1. Tabele prawdy dla działań boolowskich

Rysunek 1.2 podpowiada nam, jak taka tabela działa na przykładzie operacji NOT i AND. Możemy odnaleźć bity wyjściowe, śledząc ścieżkę prowadzącą od bitu lub bitów wejściowych.

Rysunek 1.2. Użycie tabel prawdy

Jak widać wyraźnie, operacja NOT po prostu odwraca stan wejściowy. Jednocześnie operacja AND zwraca prawdę tylko wtedy, gdy oba bity wejściowe są prawdą.

UWAGA

Operacja XOR składa się z innych działań. Na przykład XOR dwóch bitów, a i b, jest tym samym co (a OR b) AND NOT (a AND b). To pokazuje, że podstawowe operacje boolowskie mogą być łączone na różne sposoby po to, by dać te same wyniki.

Prawo de Morgana

W XIX wieku brytyjski matematyk Augustus de Morgan odkrył prawo, które stosuje się wyłącznie do algebry boolowskiej, nazwane z czasem prawem de Morgana. Prawo to głosi, że działanie a AND b jest równoważne działaniu NOT(NOT a OR NOT b), tak jak to pokazano na rysunku 1.3.

Rysunek 1.3. Tabela prawdy dla prawa de Morgana

Zauważmy, że wyniki działania a AND b w drugiej kolumnie są takie same jak wyniki wymienione w ostatniej kolumnie reprezentującej NOT(NOT a OR NOT b). Oznacza to, że przy dostatecznej liczbie operacji NOT możemy zamienić operację AND na operację OR (i vice versa). To jest bardzo użyteczne, ponieważ komputery operują na wejściach z rzeczywistego świata, których nie mogą kontrolować. Co prawda byłoby bardzo miło, gdyby wejścia zawsze miały formę zimno albo pada, niemniej często mają postać NOT zimno albo NOT pada. Podobnie jak podwójna negacja działa w językach takich jak angielski (i tak jak prawie zawsze działa w językach takich jak polski, np. w zdaniu: „Nie poszliśmy nie na narty”), prawo de Morgana jest narzędziem pozwalającym nam operować na tych zdaniach z logiką negatywną obok logiki pozytywnej, którą już widzieliśmy. Rysunek 1.4 proces decyzyjny na temat noszenia kurtki w formie zarówno logiki pozytywnej, jak i logiki negatywnej.

Rysunek 1.4. Logika pozytywna i logika negatywna

Po lewej stronie (logika pozytywna), podejmujemy decyzję z użyciem jednej operacji OR. Po prawej stronie (logika negatywna), prawo de Morgana pozwala nam podjąć decyzję z użyciem jednej operacji AND. Bez prawda de Morgana musielibyśmy zastosować przypadek z logiki negatywnej jako NOT nie-zimno OR NOT nie-pada. I chociaż to by zadziałało, każda operacja ma swój koszt i wydajność, więc minimalizując liczbę operacji, minimalizujemy koszt decyzji. Sprzęt wykonujący operację NOT kosztuje prawdziwe pieniądze, a jak przekonamy się w następnym rozdziale, kaskadowanie operacji wszystko spowalnia.

Prawo de Morgana mówi nam, że jest to ścisłym odpowiednikiem „zimno i pada”, co jest znacznie prostsze.

Przedstawianie liczb naturalnych za pomocą bitów

Pójdźmy teraz w górę łańcucha pokarmowego i zobaczmy, jak może użyć bitów do przedstawiania liczb. Liczby są bardziej skomplikowane niż logika, ale o wiele mniej skomplikowane niż słowa.

Przedstawianie liczb dodatnich

Powszechnie posługujemy się dziesiętnym systemem cyfrowym, ponieważ odpowiada on naszej anatomii. Do pojemników języka idzie dziesięć różnych symboli, które nazywamy cyframi: 0123456789. Pojemniki ułożone są od lewej do prawej. Każdy pojemnik ma nazwę, która jest niezależna od jego zawartości – pojemnik na prawym końcu nazywamy jednościami, następne są dziesiątki, potem setki, tysiące i tak dalej. Nazwy te są tylko aliasami dla kolejnych potęg liczby 10: 10^0 to jeden, 10^1 to dziesięć, 10^2 to sto, 10^3 to tysiąc. System ten nazywamy dziesiętnym, ponieważ 10 jest podstawą liczenia kolejnych potęg. Wartość danej liczby równa jest sumie iloczynów wartości każdego pojemnika i jego zawartości. Na przykład liczba 5028 jest sumą 5 tysięcy, 0 setek, 2 dziesiątek i 8 jedności, lub 5×10^3+0×10^2+2×10^1+8×10^0, tak jak to pokazano na rysunku 1.5.

Rysunek 1.5. Liczba 5028 w notacji dziesiętnej

Podobnego podejścia możemy użyć, jeśli chcemy tworzyć liczby z użyciem bitów. Ponieważ zamiast cyfr używamy bitów, dysponujemy tylko dwoma symbolami: 0 i 1. Ale to żaden problem. W systemie dziesiętnym dodajemy kolejny pojemnik, gdy tylko skończy nam się miejsce w poprzednim, możemy więc zmieścić 9 w jednym pojemniku, ale potrzebujemy dwóch pojemników na 10. Tak samo działa to w systemie dwójkowym, potrzebujemy tylko nowego pojemnika dla wszystkiego, co jest większe od 1. Pojemnik najbardziej na prawo to nadal będzie cyfra jedności, ale co będzie następnym pojemnikiem? Będzie to cyfra dwójek. Wartość następnego pojemnika w systemie dziesiętnym, gdzie mamy 10 cyfr jest 10 razy większa od wartości poprzedniego pojemnika. Tak więc w systemie dwójkowym, gdzie mamy tylko dwa symbole, wartość każdego pojemnika będzie dwa razy większa od wartości pojemnika po jego prawej stronie. Tylko na tym to polega! Wartości kolejnych pojemników są więc potęgami 2, więc jest to system dwójkowy zamiast dziesiętnego.

Tabela 1.1 wymienia kilka potęg liczby 2. Możemy jej użyć jako ściągawki, aby poznać dwójkową postać liczby 5028.

Tabela 1.1. Potęgi liczby 2

Rozwinięcie

Potęga

Postać dziesiętna

2 ÷ 2

2^0

1

2

2^1

2

2 × 2

2^2

4

2 × 2 × 2

2^3

8

2 × 2 × 2 × 2

2^4

16

2 × 2 × 2 × 2 × 2

2^5

32

2 × 2 × 2 × 2 × 2 × 2

2^6

64

2 × 2 × 2 × 2 × 2 × 2 × 2

2^7

128

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^8

256

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^9

512

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^10

1 024

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^11

2 048

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^12

4 096

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^13

8 192

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^14

16 384

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

2^15

32 768

Każda liczba w prawej kolumnie tabeli 1.1 reprezentuje wartość dwójkowego pojemnika. Rysunek 1.6 pokazuje, jak możemy zapisać liczbę 5028 w systemie dwójkowym za pomocą w zasadzie tego samego procesu, jakiego użyliśmy dla notacji dziesiętnej.

Rysunek 1.6. Liczba 5028 w systemie dwójkowym

Wynikiem konwersji na system dwójkowego jest:

1 × 2^12 + 0 × 2^11 + 0 × 2^10 + 1 × 2^9 + 1 × 2^8 + 1 × 2^7 + 0 × 2^6 + 1 × 2^5 + 0 × 2^4 + 0 × 2^3 + 1 × 2^2 + 0 × 2^1 + 0 × 2^0 = 5028

Jak widać powyżej, liczba 5028 ma jeden 4096 (2^12), zero 2048 (2^11), zero 1024 (2^10), jeden 512 (2^9), jeden 256 (2^8) i tak dalej, aż w końcu otrzymujemy 1001110100100. Wykonując to samo działanie, które robiliśmy dla liczb dziesiętnych, zapisujemy 1×2^12+0×2^11+0×2^10+1×2^9+1×2^8+1×2^7+0×2^6+1×2^5+0×2^4+0×2^3+1×2^2+0×2^1+0×2^0. Podstawiając w odpowiednie miejsca liczby z tabeli 1.1, otrzymujemy 4096+512+256+128+32+4, co daje 5028.

Możemy powiedzieć, że w systemie dziesiętnym liczba 5028 jest liczbą czterocyfrową. W systemie dwójkowym jest liczbą 13-bitową.

Liczba cyfr określa zakres wartości, jaki możemy przedstawić w systemie dziesiętnym. Na przykład za pomocą dwóch cyfr można przedstawić 100 różnych wartości w przedziale 0–99. Tak samo liczba bitów określa zakres wartości, które możemy przedstawić w systemie dwójkowym. Na przykład dwa bity mogą reprezentować wartości w przedziale 0–3. Tabela 1.2 podsumowuje zarówno liczbę wartości, jak i ich zakresy, które możemy przedstawić za pomocą różnej liczby bitów.

Tabela 1.2. Zakresy wartości liczb dwójkowych

Liczba bitów

Liczba wartości

Zakres wartości

4

16

0…15

8

256

0…255

12

4 096

0…4 095

16

65 536

0…65 535

20

1 048 576

0…1 058 575

24

16 777 216

0…16 777 215

32

4 294 967 296

0…4 294 967 295

64

18 446 744 073 709 551 616

0…18 446 744 073 709 551 615

Bit położony na prawym końcu w liczbie dwójkowej nazywamy bitem najmniej znaczącym, bit położony zaś na lewym końcu – bitem najbardziej znaczącym. Bierze się to stąd, że zmiana wartości bitu położonego najbardziej na prawo zmieni liczbę w najmniejszym stopniu, natomiast zmiana bitu położonego najbardziej na lewo zmieni liczbę w największym stopniu. Ludzie zajmujący się komputerami są przywiązani do trzyliterowych skrótów, czyli tak zwanych TLA[5], tak więc wspomniane bity są nazywane LSB (Least Significant Bit – bit najmniej znaczący) oraz MSB (Most Significant Bit – bit najbardziej znaczący). Na rysunku 1.7 pokazano przykład liczby 5028 zapisanej za pomocą 16 bitów.

Rysunek 1.7. MSB i LSB

Zauważmy, że chociaż dwójkowa postać liczby 5028 wymaga 13 bitów, rysunek 1.7 pokazuje tę liczbę za pomocą 16 bitów. Podobnie jak w systemie dziesiętnym, zawsze możemy użyć większej liczby pojemników niż najmniejsza wymagana i po prostu dodać kilka zer na początku (leading zeros). W systemie dziesiętnym 05028 ma tę samą wartość co 5028. Liczby dwójkowe często są przedstawiane w ten sposób, ponieważ komputery zbudowane na bazie bloków bitów.

Dodawanie binarne

Gdy już wiemy, jak przedstawić liczbę z użyciem systemu dwójkowego, zobaczmy, jak można w prosty sposób wykonywać na takich liczbach działania arytmetyczne. Dodawanie w systemie dziesiętnym przebiega w ten sposób, że dodajemy każdą cyfrę, zaczynając od prawej strony (od najmniej znaczącej cyfry) i jeśli wynik jest większy niż 9, przenosimy 1. Podobnie, w systemie dwójkowym sumujemy wszystkie cyfry, idąc od najmniej do najbardziej znaczącego bitu, a za każdym razem, gdy wynik dodawania jest większy niż 1, przenosimy 1.

Dodawanie jest w zasadzie nieco łatwiejsze w systemie dwójkowym niż w dziesiętnym, ponieważ istnieją tylko 4 możliwe kombinacje dwóch bitów, podczas gdy w systemie dziesiętnym jest 100 możliwych kombinacji dwóch cyfr. Na przykładu rysunek 1.8 pokazuje, jak dodać do siebie 1 i 5, używając liczb dwójkowych. Nad każdą kolumną widać liczby przenoszone z dodawania poprzedniej kolumny.

Rysunek 1.8. Dodawanie binarne

Liczba 1 to 001 w systemie dwójkowym, natomiast liczba 5 to 101, ponieważ (1×4) + (0×2) + (1×1) = 5. Aby dodać do siebie liczby dwójkowe 001 i 101, zaczynamy od najmniej znaczącego bitu w kolumnie z prawej strony. Dodanie do siebie 1 i 1 w tej kolumnie daje nam 2, ale w systemie dwójkowym nie mamy oddzielnego symbolu na 2. Wiemy, że w tym systemie 2 jest zapisywane 10 ([1×2] + [0×1] = 2), więc wpisujemy 0 jako sumę i przenosimy 1 do następnej cyfry. Ponieważ środkowe bity to zera, mamy tylko 1, które przenieśliśmy z prawej kolumny, i tyle wynosi suma. Na koniec dodajemy bity w kolumnie po lewej stronie: 0 dodać 1 daje nam 1, również w systemie dwójkowym. Wynikiem jest więc liczba 110 w systemie dwójkowym lub 6 w systemie dziesiętnym – i tyle właśnie byśmy otrzymali, gdybyśmy dodali 1 i 5.

Można zauważyć, że zasady dodawania binarnego można wyrazić w postaci działań logicznych, które były omawiane wcześniej, tak jak to ilustruje rysunek 1.9. W rozdziale 2 przekonamy się, że w ten właśnie sposób sprzęt komputerowy wykonuje dodawanie.

Rysunek 1.9. Dodawanie binarne z użyciem operatorów logicznych

Kiedy dodajemy do siebie dwa bity, wartością wyniku jest XOR tych bitów, a wartością przenoszoną jest AND tych bitów. Można się przekonać, że to prawda, patrząc na rysunek 1.9, gdzie dodanie 1 do 1 daje wynik 10. To oznacza, że wartość przenoszona wynosi 1, a to jest wynik, jaki byśmy otrzymali, wykonując działanie (1 AND 1). Podobnie, wyrażenie (1 XOR 1) daje w wyniku 0, co jest wartością, jaką przypisujemy temu bitowi.

Dodawanie do siebie dwóch bitów jest operacją, która rzadko występuje w pojedynkę. Spójrzmy znowu na rysunek 1.8: wydaje się, że w każdej kolumnie dodajemy do siebie dwa bity, ale tak naprawdę dodajemy do siebie trzy bity, ponieważ zawsze przenosimy jakiś bit. Na szczęście nie musimy wiedzieć nic więcej, niż wiemy do tej pory, żeby dodać do siebie trzy bity. A + B + C to dokładnie to samo, co (A + B) + C, zgodnie z regułą łączności. Tak więc możemy dodać do siebie trzy bity, używając do tego pary dwubitowych działań dodawania.

Co jednak się stanie, jeśli wynik nie zmieści się w liczbie bitów, jaką dysponujemy? Wtedy mamy do czynienia z tak zwanym przepełnieniem (overflow), które zdarza się zawsze, gdy będziemy przenosić 1 z najbardziej znaczącego bitu. Na przykład, jeśli mamy liczby czterobitowe i dodajemy do siebie 1001 (910) i 1000 (810), to wynikiem powinno być 10001 (1710), ale otrzymamy jedynie 0001 (110), ponieważ nie ma już miejsca na najbardziej znaczący bit. Jak się później dowiemy w szczegółach, komputery mają rejestry stanu (condition code register), które są miejscem przeznaczonym do przechowywania dodatkowych informacji. Jedną z takich informacji jest flaga przepełnienia (overflow flag), który przechowuje wartość przeniesioną z najbardziej znaczącego bitu. Można sprawdzić tę wartość, by przekonać się, czy doszło do przepełnienia.

Prawdopodobnie zdajesz sobie sprawę z tego, że można również odjąć jedną liczbę od drugiej, dodając do pierwszej liczby liczbę przeciwnej do drugiej. W następnym punkcie nauczymy się przedstawiać liczby ujemne. Pożyczanie bitów poza najmniej znaczący bit nazywamy niedomiarem (underflow). Komputery mają i na to flagę rejestru.

Przedstawianie liczb ujemnych

Wszystkie liczby, które przedstawialiśmy dotychczas w systemie dwójkowym, były dodatnie. Jednak wiele rzeczywistych problemów wymaga użycia zarówno dodatnich, jak i ujemnych wartości. Zobaczmy, jak możemy użyć bitów do przedstawiania liczb ujemnych. Załóżmy na przykład, że dysponujemy czterema bitami. Jak nauczyliśmy się w poprzednim punkcie, cztery bity mogą reprezentować 16 liczb w zakresie od 0 do 15. Ale to, że możemy przechowywać w ten sposób 16 liczb nie oznacza wcale, że muszą to być liczby od 0 do 15. Pamiętajmy, że język działa przez znaczenia i kontekst. To oznacza, że możemy wynaleźć nowy kontekst, w którym będziemy interpretować bity.

Postać „znak-moduł”

Znak jest powszechnie stosowany w celu odróżnienia liczb ujemnych od liczb dodatnich. Znak ma dwie wartości, plus i minus, więc może być przedstawiony za pomocą bitu. Arbitralnie użyjmy do oznaczenia znaku pierwszego bitu z lewej strony (MSB), co pozostawia nam trzy bity do reprezentacji wartości od 0 do 7. Jeśli bit znaku wynosi 0, traktujemy wartość jako dodatnią, a jeśli wynosi 1 – jako ujemną. To pozwala nam przedstawiać w sumie 15 różnych ujemnych liczb, a nie 16, ponieważ istnieje zarówno dodatnie, jak i ujemne 0. Jak widać w tabeli 1.3, pozwala nam to przedstawiać liczb między +7 a –7.

Taki zapis jest reprezentacją w postaci znaku i modułu, ponieważ mamy w niej bit, który reprezentuje znak, i bity, które reprezentują wartość bezwzględną danej liczby (moduł) – innymi słowy to, jak daleko jest ona od zera.

Postać znak-moduł nie jest używana zbyt często z dwóch powodów. Po pierwsze, bity kosztują – nie chcemy więc ich marnować, mając dwie różne reprezentacje zera. Wolelibyśmy użyć jednej z tych kombinacji do przedstawienia czegoś innego. Po drugie, arytmetyka z użyciem XOR i AND nie działa dobrze z tą postacią.

Tabela 1.3. Liczby dwójkowe w postaci znak-moduł

Znak

2^2

2^1

2^0

Postać dziesiętna

0

1

1

1

+7

0

1

1

0

+6

0

1

0

1

+5

0

1

0

0

+4

0

0

1

1

+3

0

0

1

0

+2

0

0

0

1

+1

0

0

0

0

+0

1

0

0

0

–0

1

0

0

1

–1

1

0

1

0

–2

1

0

1

1

–3

1

1

0

0

–4

1

1

0

1

–5

1

1

1

0

–6

1

1

1

1

–7

Powiedzmy, że chcemy dodać +1 do –1. Spodziewamy się otrzymać 0, ale z użyciem postaci znak-moduł otrzymamy inny wynik – jak na rysunku 1.10.

Rysunek 1.10. Dodawanie liczb w postaci znak-moduł]

Jak widać, 0001 reprezentuje dodatnie 1, ponieważ jego znak wynosi 0. 1001 reprezentuje –1, ponieważ bit znaku wynosi 1. Dodanie tych dwóch liczb za pomocą arytmetyki XOR i AND da nam 1010. To oznacza liczbę dziesiętną –2, co nie jest wynikiem sumy –1 i +1.

Moglibyśmy sprawić, że arytmetyka w postaci znak-wielkość będzie działać przez użycie bardziej skomplikowanej logiki, ale zachowanie prostoty ma swoją wartość. Zobaczmy, w jaki sposób można inaczej przedstawiać liczby i znajdźmy lepsze rozwiązanie.

Uzupełnienie do 1

Innym sposobem na otrzymanie liczby ujemnej jest wzięcie liczby dodatniej i odwrócenie wszystkich bitów, co nazywamy uzupełnieniem do jednego (U1). Dzielimy bity podobnie jak w postaci znak-moduł. W tym kontekście uzupełnienie otrzymujemy za pomocą operacji NOT. W tabeli 1.4 podano liczby od –7 do 7 za pomocą uzupełnienia do 1.

Tabela 1.4. Liczby dwójkowe w postaci uzupełnienia do 1

Znak

2^2

2^1

2^0

Postać dziesiętna

0

1

1

1

+7

0

1

1

0

+6

0

1

0

1

+5

0

1

0

0

+4

0

0

1

1

+3

0

0

1

0

+2

0

0

0

1

+1

0

0

0

0

+0

1

1

1

1

–0

1

1

1

0

–1

1

1

0

1

–2

1

1

0

0

–3

1

0

1

1

–4

1

0

1

0

–5

1

0

0

1

–6

1

0

0

0

–7

Jak widać, odwrócenie wszystkich bitów liczby 0111 (+7) daje nam 1000 (–7).

Zapis w postaci uzupełnienia do jednego będzie miał jednak problem z dwoma różnymi postaciami zera. Nadal nie da się tutaj zbyt łatwo wykonać dodawania. Aby wszystko się zgadzało, trzeba dodawać 1 do wyniku, jeśli w czasie dodawania wystąpiło przeniesienie poza bit znaku (end-around carry). Przenosimy wtedy 1 z MSB znowu do LSB. Rysunek 1.11 ilustruje tę procedurę.

Rysunek 1.11. Dodawanie z użyciem reprezentacji uzupełnienia do 1

Aby dodać +2 i –1 z użyciem uzupełnienia do 1, przeprowadzamy dodawanie binarne liczb 0010 i 1110 tak, jakbyśmy to robili normalnie. Ponieważ dodawanie w najbardziej znaczącym bicie (bicie znaku) da w wyniku 10, zapisujemy 0 i przenosimy 1 poza bit znaku. Dysponujemy tylko czterema bitami, więc przenosimy 1 z MSB z powrotem do LSB, co daje nam 0001 albo +1, co jest poprawną sumą +2 i –1. Jak widać, sprawienie, żeby dodawanie działało poprawnie, znacznie skomplikowało system.

Chociaż ostatecznie to działa, to jednak rozwiązanie nie jest optymalne, choćby dlatego, że potrzebujemy dodatkowego kawałka sprzętu do tego, by przeprowadzić przeniesienie poza bit znaku.

Ani postać znak-moduł, ani uzupełnienie do 1 nie są stosowane we współczesnych komputerach. Arytmetyka za pomocą tych metod nie działa poprawnie, chyba, że doda się dodatkowy sprzęt, a to kosztuje. Patrzmy dalej, może uda nam się wymyślić postać, która eliminuje nasz problem.

Uzupełnienie do 2

Co by się stało się, gdybyśmy nie dodawali żadnego sprzętu i trzymali się po prostu operatorów XOR i AND? Zobaczmy, jaki układ bitów, gdy dodamy go do +1, da nam 0 i nazwijmy ten układ –1. Jeśli nadal dysponujemy czterema bitami, +1 to 0001. Dodanie 1111 do tej liczby da nam 0000, tak jak to pokazano na rysunku 1.12, więc będziemy używać tego układu bitów do przedstawienia –1.

Rysunek 1.12. Poszukiwania –1

Taki zapis nazywa się uzupełnieniem do 2 (U2) i jest on aktualnie najpowszechniej stosowaną postacią liczb całkowitych ze znakiem. Możemy otrzymać wartość ujemną każdej liczby przez uzupełnienie (tj. przez przeprowadzenie operacji NOT dla każdego bitu), a następnie dodanie 1 (nie zwracamy tu uwagi na ewentualne przeniesienia z MSB). W ten sposób uzupełnieniem liczby +1, czyli 0001, jest 1110, a po dodaniu 1 otrzymamy 1111 reprezentujące –1. Podobnie, +2 to 0010, jego uzupełnieniem jest 1101, a dodanie 1 da nam 1110 reprezentujące –2. Tabela 1.5 pokazuje nam liczby od –8 do 7 przedstawione za pomocą uzupełnienia do 2.

Tabela 1.5. Liczby w postaci uzupełnienia do 2

Znak

2^2

2^1

2^0

Postać dziesiętna

0

1

1

1

+7

0

1

1

0

+6

0

1

0

1

+5

0

1

0

0

+4

0

0

1

1

+3

0

0

1

0

+2

0

0

0

1

+1

0

0

0

0

+0

1

1

1

1

–1

1

1

1

0

–2

1

1

0

1

–3

1

1

0

0

–4

1

0

1

1

–5

1

0

1

0

–6

1

0

0

1

–7

1

0

0

0

–8

Spróbujmy podstawić 0 do naszego wzoru, żeby przekonać się, czy uzupełnienie do 2 rozwiązuje problem podwójnej reprezentacji zera. Jeśli weźmiemy 0000 i odwrócimy każdy bit, otrzymujemy 1111 jako uzupełnienie. Dodanie 1 do 1111 daje nam [1]0000, ale ponieważ wynik jest liczbą 5-bitową i przekracza liczbę dostępnych bitów, możemy nie zwracać uwagi na 1 w przeniesionym bicie. Zostajemy z 0000, a więc z tym, od czego zaczęliśmy. Wynika z tego, że 0 ma tylko jedną postać w uzupełnieniu do dwóch.

Programiści muszą wiedzieć, ile bitów potrzebna, by przechowywać potrzebne im liczby. To prędzej czy później staje się drugą naturą. Zanim to nastąpi, można zaglądać do tabeli 1.6, w której zapisano zakresy wartości, które możemy przedstawiać z użyciem uzupełnienia do dwóch, w zależności od liczby dostępnych bitów.

Tabela 1.6. Zakresy wartości liczb przedstawionych za pomocą z użyciem uzupełnienia do 2

Liczba bitów

Liczba możliwych wartości

Zakres wartości

4

16

–8…7

8

256

–128…127

12

4 096

2 048…2 047

16

65 536

–32 768…32 767

20

1 048 576

–524 288…524 287

24

16 777 216

–8 388 608…8 388 607

32

4 294 967 296

–2 147 483 648…2 137 483 647

64

18 446 744 073 709 551 616

–9 223 372 036 854 775 808…9 223 372 036 854 775 807

Jak widać z tabeli 1.6, w miarę wzrostu liczby dostępnych bitów, zakres możliwych wartości wzrasta w tempie geometrycznym. Trzeba pamiętać, że zawsze potrzebujemy kontekstu, by móc określić, czy czterobitowa liczba, którą chcemy odczytać, to 15, lub też –1 zapisane z użyciem uzupełnienia do 2, czy może –7 zapisane w postaci znak-moduł albo –0 zapisane z użyciem uzupełnienia do 1. Trzeba wiedzieć, jaki zapis został użyty.

PRZYPISY

[1] Nauka, technologia, inżyniera, matematyka (Science, Technology, Engineering, Mathematics, STEM) – przyp. tłum.

[2] Dokładnie tytuł Rycerza Orderu Imperium Brytyjskiego (przyp. red.).

[3] „Duck, duck, goose” jest w języku angielskim nazwą znanej zabawy dziecięcej, która może budzić w odbiorcy podobne skojarzenia co w języku polskim np. słowa „chodzi lisek koło drogi” (przyp. tłum).

[4] Autor posługuje się tu najwyraźniej bardzo nieformalnymi pojęciami „prostoty” i „złożoności”, według których dany operator jest prosty, jeśli da się go wyrazić za pomocą jednego spójnika z języka naturalnego, jest zaś złożony, jeśli da się go wyrazić tylko za pomocą dwóch lub więcej spójników z języka naturalnego. Ten warunek akurat nie zachodzi dla języka polskiego, w którym alternatywa rozłączna ma intuicyjny odpowiednik w spójniku „albo”, odróżniany od spójnika „lub” (przyp. tłum).

[5] TLA to Three Letter Acronym, czyli trzyliterowy skrót (przyp. tłum).