Jak stworzyć działający prototyp języka programowania: przykłady i zasady

W wielu przypadkach, gdy budujemy nowy język programowania, w tym język specyficzny dla domeny (DSL), jego początkowa implementacja nie musi zapewniać wysokiej wydajności. Przykładem mogą być popularne w praktyce języki programowania, które rozpoczęły swoje istnienie od prostych implementacji, a z biegiem czasu przekształciły się w bardziej zaawansowane rozwiązania. Jako przykład możemy przywołać język Ruby, który początkowo był interpretatorem przechodzącym przez abstrakcyjny drzewo składniowe (AST) na wzór NanoBASIC. Z czasem Ruby zaczął kompilować kod do bajtów i wykonywać go na maszynie wirtualnej. Nowsze wersje tego języka wprowadziły także kompilator JIT (Just-In-Time). Niezależnie od tego, czy implementacja języka przechodzi przez AST, używa bajtów, czy posiada kompilator JIT, fundamenty omawiane w tym rozdziale są zawsze niezbędne.

Pierwszym krokiem przy budowie języka programowania jest zrozumienie, jak działa tokenizacja, analiza składniowa oraz jak skonstruować środowisko wykonawcze, które będzie mogło obsługiwać kod użytkownika. Przede wszystkim warto zacząć od prostego języka, takiego jak NanoBASIC, który będzie dobrym przykładem na początek. Dzięki temu, że NanoBASIC jest wystarczająco prosty, pozwala na zrozumienie mechanizmów, które leżą u podstaw każdego bardziej zaawansowanego języka.

Prosty interpreter NanoBASIC mógłby zawierać tylko podstawowe instrukcje, takie jak "PRINT", "INPUT" i zmienne. Można rozwinąć ten projekt, wprowadzając dodatkowe funkcje, takie jak możliwość obliczeń numerycznych, a także umożliwiając użytkownikowi interakcję z interpreterem poprzez wprowadzenie danych. Implementacja takich instrukcji wymaga zrozumienia kilku kluczowych pojęć, w tym działania na zmiennych, tworzenia funkcji i zarządzania pamięcią, a także interakcji między parserem a środowiskiem wykonawczym.

Kolejnym krokiem może być rozszerzenie interpretera o możliwość interpolacji zmiennych w ciągach znaków. Przykład takiej operacji w NanoBASIC mógłby wyglądać tak: jeśli ciąg zawiera znak dolara przed nazwą zmiennej, interpreter powinien sprawdzić, czy dana zmienna jest zdefiniowana, a następnie zamienić ją na odpowiednią wartość. Na przykład, dla ciągu "Wartość X wynosi $X", jeśli zmienna X ma wartość 24, wynik wyświetlony na ekranie powinien brzmieć: "Wartość X wynosi 24". Tego typu operacja wymaga nie tylko modyfikacji tokenizera, ale także parsera i środowiska wykonawczego, aby prawidłowo obsługiwały nowe zasady.

Kiedy interpreter NanoBASIC będzie obsługiwał podstawowe instrukcje i zmienne, warto dodać możliwość interaktywnego wykonywania kodu. Aby to zrobić, należy zaimplementować tzw. tryb REPL (Read-Eval-Print Loop), w którym użytkownik może wprowadzać instrukcje, które będą natychmiastowo interpretowane i wykonywane przez system. Wprowadzenie takich komend jak "CLEAR", "LIST", "RUN" oraz "END" umożliwia użytkownikowi pełną kontrolę nad jego programem w trybie interaktywnym. Dzięki temu interpreter stanie się bardziej funkcjonalny, a jego możliwości zostaną poszerzone, co jest kluczowe w tworzeniu bardziej zaawansowanych narzędzi.

Jednak samo stworzenie interpreterów czy języków programowania to tylko jeden z kroków w tworzeniu nowoczesnych aplikacji. Zrozumienie, jak implementować algorytmy, które są wykorzystywane w bardziej rozbudowanych systemach, takich jak np. algorytmy ditheringu w grafice komputerowej, jest równie ważne. Dzięki algorytmom takim jak dithering, możliwe jest wyświetlanie zdjęć na ekranach o ograniczonej liczbie kolorów, co może być przydatne w urządzeniach takich jak pierwsze komputery Macintosh z wyświetlaczami monochromatycznymi.

Nie można zapominać o tym, że algorytmy ditheringu nie tylko mają swoje zastosowanie w sztuce i grafice komputerowej, ale są również fundamentem w rozwoju wielu technologii związanych z wyświetlaniem obrazów w ograniczonych przestrzeniach kolorystycznych. Dlatego też umiejętność ich implementacji jest niezbędna, szczególnie w kontekście pracy z urządzeniami, które nie wspierają wyświetlania pełnej palety kolorów.

Jak stworzyć własny język programowania i осигналizować maszynę wirtualną: praktyczne podejście

Z jakiegoś powodu nasz świat komputerów jest zbudowany na fundamentach, które często nie są widoczne gołym okiem. Działają one jak skomplikowane mechanizmy, które potrafią przeprowadzać obliczenia na poziomie, o którym większość użytkowników komputerów nie ma pojęcia. Zrozumienie tych mechanizmów może stanowić wyzwanie, ale może również otworzyć przed nami zupełnie nową perspektywę na tworzenie oprogramowania, jego działanie oraz możliwości rozwoju.

Podstawowym celem tej książki jest ukazanie tych fundamentów poprzez projektowanie i implementację różnych technologii, które – choć w swojej istocie mogą być techniczne – oferują wgląd w sposób, w jaki działają komputery. W książce przedstawiam siedem projektów, które pozwalają przejść przez kluczowe zagadnienia informatyki, od języków programowania po emulatory maszyn, a kończąc na pierwszych krokach w kierunku uczenia maszynowego.

Zanim jednak zaczniemy budować konkretne projekty, warto zrozumieć, do kogo kierowana jest ta książka. Jeśli jesteś programistą Python o średnim lub zaawansowanym poziomie, to będziesz w stanie podjąć się tego wyzwania. Jeśli jesteś początkującym, lepiej wrócić do tej książki po zdobyciu nieco większej wiedzy na temat składni Pythona, struktur danych oraz podstawowych bibliotek. Co istotne, książka ta nie wymaga wiedzy z zakresu zaawansowanej matematyki czy informatyki. Oznacza to, że nawet jeśli nie ukończyłeś formalnych studiów informatycznych, nadal możesz wykorzystać tę książkę, by zdobyć solidne podstawy w takich dziedzinach jak kompilatory, emulatory czy wstęp do uczenia maszynowego.

Kiedy rozmawiamy o implementacji języków programowania, jednym z pierwszych projektów w książce jest stworzenie interpretatora dla Brainfuck, minimalistycznego języka, który, mimo swojej prostoty, jest doskonałym punktem wyjścia do nauki o językach programowania. Gdy nauczysz się implementować interpreter Brainfuck, będziesz mógł łatwiej zrozumieć, jak działa każdy interpreter i jak są realizowane bardziej zaawansowane mechanizmy.

Również interesującą częścią książki jest projektowanie maszyny wirtualnej (VM) w kontekście gier komputerowych. CHIP-8, bardzo prosty system stworzony w latach 70. do programowania gier, jest doskonałym przykładem tego, jak emulować zachowanie maszyny. Stworzenie emulatora CHIP-8 to doskonały sposób, by zapoznać się z najważniejszymi aspektami projektowania emulatorów. Choć nasz emulator będzie miał ograniczenia, jego tworzenie pozwoli zrozumieć mechanizmy emulacji oraz jak niskopoziomowe operacje wpływają na działanie komputera.

Kolejnym krokiem jest implementacja emulatora konsoli NES, jednej z najpopularniejszych konsol w historii gier wideo. Stworzenie emulatora NES jest bardziej zaawansowane, ale jest doskonałym sposobem na naukę działania komputerów na poziomie sprzętowym. Podobnie jak w przypadku CHIP-8, proces ten nie tylko przybliża nas do technologii, ale także pozwala na zrozumienie, jak w prosty sposób komputer może symulować inne maszyny.

Z drugiej strony, książka zawiera również tematykę bardziej artystyczną – algorytmy do tworzenia obrazów. Projekt, który polega na zaimplementowaniu algorytmu ditheringowego w celu wyświetlania zdjęć na klasycznym Macintoshu z lat 80., jest przykładem tego, jak algorytmy komputerowe mogą być używane w sztuce. Z kolei algorytm stochastyczny do tworzenia abstrakcyjnych obrazów pokazuje, jak matematyczne podejście może być zastosowane w sztuce generatywnej.

Chociaż książka skupia się na implementacji praktycznych projektów, nie można zapominać, że każdy z tych projektów wiąże się z głębszymi zagadnieniami teoretycznymi. Każdy projekt zawiera wstęp teoretyczny, który pomaga zrozumieć podstawowe mechanizmy działania, co stanowi nieocenioną pomoc w nauce. Przy czym, w każdym rozdziale znajduje się nie tylko implementacja, ale także osobiste doświadczenia autora oraz odniesienia do zastosowań w rzeczywistym świecie, które mogą zainspirować do dalszych eksploracji.

Na zakończenie warto zwrócić uwagę na to, że projektowanie własnych interpreterów, emulatorów, algorytmów do tworzenia sztuki czy rozwiązań z zakresu uczenia maszynowego pozwala na głębsze zrozumienie, jak działa komputer oraz jakie mechanizmy są za nim ukryte. Celem tej książki jest więc nie tylko dostarczenie gotowych projektów, ale także przekazanie narzędzi, które umożliwią czytelnikom rozwiązywanie bardziej skomplikowanych problemów informatycznych w przyszłości.

Jak działa ditherowanie Atkinsona i Floyd-Steinberga?

Ditherowanie to technika stosowana w grafice komputerowej, której celem jest odwzorowanie większej liczby odcieni szarości lub kolorów na urządzeniach o ograniczonej liczbie kolorów, takich jak stare ekrany CRT czy drukarki. Dwa popularne algorytmy ditherowania to algorytmy Atkinsona i Floyd-Steinberga. Chociaż oba mają na celu rozproszenie błędów w sąsiednich pikselach, różnią się w sposobie dystrybucji tego błędu, co daje różne efekty wizualne.

Algorytm Atkinsona różni się od Floyd-Steinberga tym, że rozdziela błąd między sześć sąsiednich pikseli, wprowadzając różne proporcje, w których każdy z tych pikseli otrzymuje część błędu. W efekcie, zamiast rozpraszać całość błędu na cztery najbliższe piksele (jak w przypadku Floyd-Steinberga), w Atkinsonie tylko trzy czwarte całkowitego błędu jest rozprowadzane. Ta różnica w dystrybucji błędu powoduje, że dithering Atkinsona ma tendencję do uwydatniania kontrastów i ostrych krawędzi, podczas gdy dithering Floyd-Steinberga generuje bardziej płynne przejścia tonalne.

Kiedy przyjrzymy się różnicom w strukturze macierzy, łatwo zauważymy, że w algorytmie Atkinsona błąd jest rozpraszany na sześć miejsc: jeden na lewo i w dół, jeden na prawo i w dół, jeden bezpośrednio poniżej oraz dwa poniżej w różnych proporcjach. Macierz Atkinsona wygląda następująco:

diff
Copy code
Δ    -1   0   +1   +2

0    X    1/8  1/8
+1   1/8  1/8  1/8
+2   1/8

Z kolei macierz Floyd-Steinberga wykorzystuje cztery piksele do rozprzestrzeniania błędu w proporcjach: 7/16, 3/16, 5/16 i 1/16. Dzięki temu rozkładowi, wynikowy obraz jest bardziej wygładzony.

Implementacja w Pythonie

Podstawowa implementacja algorytmu Atkinsona w języku Python wykorzystuje bibliotekę Pillow do manipulowania obrazami. Algorytm ten działa na obrazie w odcieniach szarości (tryb "L" w Pillow), zmieniając każdy piksel na czarny lub biały, w zależności od wartości progowej (127). Następnie, błąd (różnica pomiędzy starym a nowym pikselem) jest rozprzestrzeniany na sąsiednie piksele według wzorca określonego w macierzy Atkinsona.

Przykładowy kod implementacji wygląda następująco:

python
Copy code
from PIL import Image
from array import array
from typing import NamedTuple
THRESHOLD = 127
class PatternPart(NamedTuple):
    dc: int  # zmiana w kolumnie
    dr: int  # zmiana w wierszu
    numerator: int
    denominator: int
ATKINSON = [
    PatternPart(1, 0, 1, 8),
    PatternPart(2, 0, 1, 8),
    PatternPart(-1, 1, 1, 8),
    PatternPart(0, 1, 1, 8),
    PatternPart(1, 1, 1, 8),
    PatternPart(0, 2, 1, 8)
]
def dither(image: Image.Image) -> array:
    def diffuse(c: int, r: int, error: int, pattern: list[PatternPart]):
        for part in pattern:
            col = c + part.dc
            row = r + part.dr

            if col < 0 or col >= image.width or row >= image.height:

                continue
            current_pixel: float = image.getpixel((col, row))  # pobranie wartości piksela
            error_part = (error * part.numerator) // part.denominator
            image.putpixel((col, row), current_pixel + error_part)
    result = array('B', [0] * (image.width * image.height))
    for y in range(image.height):
        for x in range(image.width):
            old_pixel: float = image.getpixel((x, y))
            new_pixel = 255 if old_pixel > THRESHOLD else 0
            result[y * image.width + x] = new_pixel
            difference = int(old_pixel - new_pixel)
            diffuse(x, y, difference, ATKINSON)
    return result

Wydajność i optymalizacja

Choć ta implementacja jest prosta i czytelna, ma swoje ograniczenia wydajnościowe. Metody getpixel() i putpixel() w bibliotece Pillow są stosunkowo wolne, a iterowanie po każdym pikselu i rozprzestrzenianie błędów za pomocą wbudowanej macierzy jest nieefektywne. W rzeczywistych aplikacjach lepszym rozwiązaniem jest użycie bezpośredniego dostępu do danych pikseli w tablicy lub macierzy, co pozwala na szybszą manipulację obrazami.

Jednak dla celów edukacyjnych, ta implementacja jest wystarczająca, aby pokazać podstawy algorytmu ditherowania. W praktyce, optymalizacje te mogą okazać się konieczne, szczególnie przy większych obrazach.

Dodatkowe informacje

Oprócz różnic w samych algorytmach, warto zauważyć, że dithering wpływa na estetykę końcowego obrazu, szczególnie w przypadku obrazów o dużym kontraście. W przypadku Atkinsona, efekt jest wyraźniejszy i bardziej kontrastowy, podczas gdy Floyd-Steinberg daje obraz bardziej subtelny i zrównoważony. Wybór metody zależy więc od tego, jaki efekt wizualny chcemy osiągnąć. Algorytmy te można również modyfikować lub dostosowywać do własnych potrzeb, na przykład zmieniając wzorzec dystrybucji błędu na inny.

Wnioski

Zrozumienie działania ditherowania, w tym różnic między metodą Atkinsona a Floyd-Steinberga, pozwala lepiej dostosować te techniki do swoich potrzeb w przetwarzaniu obrazów. Ditherowanie to ważna część historii grafiki komputerowej, a opanowanie tej techniki jest krokiem ku zrozumieniu bardziej zaawansowanych metod przetwarzania obrazu. Choć algorytmy te mają swoje ograniczenia, to dzięki ich prostocie pozostają nieocenionym narzędziem w wielu dziedzinach grafiki komputerowej.

Jak działa emulacja kartridży NES w programie?

Emulacja kartridży NES jest złożonym procesem, który wymaga nie tylko odwzorowania samego sprzętu konsoli, ale także radzenia sobie z różnorodnymi układami scalonymi, które mogły być obecne w oryginalnych kartridżach. Każda gra na NES była przechowywana na kartridżu z układami ROM i RAM, a także mogła zawierać dodatkowe układy logiczne, które umożliwiały m.in. przełączanie banków pamięci, co pozwalało na załadowanie większej ilości danych, niż konsola mogła adresować w jednym czasie.

Podstawowym elementem, który trzeba emulować, jest obsługa przycisków pada, które na NES-ie zostały zamienione na odpowiednie zdarzenia w kodzie. W naszym przykładzie implementujemy detekcję zdarzeń klawiszy, które odpowiadają za symulację naciśniętych przycisków na padzie NES. Dzięki temu, nasza aplikacja emulująca system, potrafi rozpoznać, kiedy użytkownik naciśnie odpowiedni klawisz na klawiaturze komputera, co z kolei wpływa na stan kontrolera gry w emulatorze.

Kluczową częścią emulacji jest także zarządzanie pamięcią kartridża. Kartridże NES nie były prostymi nośnikami danych, lecz składały się z kilku układów ROM, które zawierały kod gry i grafiki. Wspomniane wcześniej banki pamięci, w tym popularny system przełączania banków, pozwalały na dynamiczne ładowanie różnych części ROM w zależności od potrzeb gry. Dzięki takim technologiom możliwe było rozbudowanie gier, które w przeciwnym razie nie zmieściłyby się w ograniczonych zasobach konsoli.

Mówiąc o emulacji NES, warto również wspomnieć o systemie mapowania, który jest jednym z głównych narzędzi wykorzystywanych w procesie odtwarzania kartridży. Mapper to układ scalony w kartridżu, który kontroluje przełączanie banków pamięci. Różne gry na NES wykorzystywały różne mappere, a emulator musi obsługiwać je w sposób umożliwiający prawidłowe ładowanie i wykonywanie kodu gry. Jednym z najprostszych do emulacji mapperów jest NROM, który nie wymaga przełączania banków pamięci i jest stosunkowo łatwy do odwzorowania.

Podstawowym formatem plików, w którym przechowywane są dane kartridży NES, jest format iNES. Pliki ROM w tym formacie zawierają nie tylko dane samej gry, ale także nagłówek, który zawiera istotne informacje o kartridżu, takie jak jego typ, rozmiar ROM czy używane mapowanie pamięci. Nagłówek pliku iNES jest szczególnie ważny, ponieważ pozwala emulatorowi na rozpoznanie, jakie właściwości ma dany plik i jak należy go załadować do pamięci. Struktura tego nagłówka jest ściśle określona, a każda sekcja nagłówka odpowiada za inną informację – od rozmiaru ROM, przez flagi systemowe, aż po identyfikację typu mapera.

Kartridże NES mogły także zawierać układy logiczne, które realizowały bardziej skomplikowane operacje, takie jak np. złożoną logikę sterowania. Dzięki tym układom możliwe było tworzenie bardziej rozbudowanych gier, które oferowały graczom większą swobodę działania i bardziej zaawansowane mechaniki. Emulator, aby w pełni odwzorować działanie takiej gry, musi być w stanie emulować także te dodatkowe układy.

Ważnym aspektem przy emulacji NES jest także zarządzanie pamięcią, w tym rozróżnienie pomiędzy pamięcią RAM a ROM, a także zrozumienie różnic w sposobie przechowywania danych na różnych układach ROM. System mapowania pamięci, który pozwala na przełączanie pomiędzy bankami pamięci, jest jednym z kluczowych mechanizmów, które emulator musi dokładnie odwzorować. Tylko wtedy możliwe będzie odtworzenie pełnej funkcjonalności gier, które korzystały z tych zaawansowanych technologii.