Jak działa interpreter języka programowania: Od Brainfuck do NanoBASIC

Interpreter to narzędzie, które tłumaczy kod źródłowy programu na język zrozumiały dla komputera, umożliwiając jego wykonanie. W kontekście programowania, interpreter to element, który łączy kod napisany przez programistę z maszynowym językiem komputerów, decydując, jak kod ma zostać przetworzony i wykonany. W tej części książki przyjrzymy się dwóm przypadkom budowania interpreterów: jednym dla minimalnego języka programowania Brainfuck, a drugim dla bardziej złożonego NanoBASIC. Oba przypadki ilustrują podstawy działania interpreterów w kontekście nowoczesnych języków programowania.

Brainfuck to jeden z najmniejszych możliwych języków programowania, zaprojektowany w 1993 roku przez Urban Müller. Jego struktura opiera się na jedynie ośmiu poleceniach, które wykonują operacje na prostych danych, głównie w postaci komórek pamięci. Pomimo swojej prostoty, Brainfuck może być uznany za Turing-complete, co oznacza, że teoretycznie może wykonać każde obliczenie, które jest możliwe do wykonania przez komputer. Język ten, choć z pozoru absurdalny, jest bardzo efektywny w nauce zasad działania interpreterów, ponieważ zmusza do zrozumienia podstawowych operacji, takich jak manipulacja wskaźnikami, zmiennymi czy iteracjami.

Interpretacja Brainfucka w Pythonie polega na stworzeniu odpowiedniego środowiska, które potrafi wykonać wszystkie instrukcje tego języka, przy zachowaniu logicznej spójności i integralności procesu. Interpretery muszą posiadać mechanizmy do ładowania kodu źródłowego, jego analizowania oraz uruchamiania w czasie rzeczywistym. Przy tym należy pamiętać o zarządzaniu pamięcią oraz cyklicznych operacjach, które odbywają się w przestrzeni zapamiętywania danych.

Kolejnym interesującym przypadkiem jest NanoBASIC – uproszczona wersja klasycznego języka BASIC, która zachowuje wszystkie cechy składni i semantyki swojego pierwowzoru, ale jest znacznie bardziej zwięzła i dostosowana do edukacji w zakresie tworzenia interpreterów. NanoBASIC, mimo swojej prostoty, posiada wszystkie elementy strukturalne, które znajdują się w zaawansowanych językach programowania: zmienne, operacje arytmetyczne, instrukcje warunkowe oraz pętle. Przykład prostego programu w NanoBASIC może wyglądać następująco:

nginx
Copy code
PRINT "Hello, World!"

Stworzenie interpreterów dla takich języków wymaga nie tylko implementacji mechanizmów zarządzania pamięcią i analizowania kodu źródłowego, ale także opracowania procesu przetwarzania tokenów, które stanowią podstawowe elementy kodu w analizie składniowej. Tokeny są rozpoznawane przez tzw. tokenizer, który dzieli kod na mniejsze, zrozumiałe jednostki (np. słowa kluczowe, operatory, zmienne). Następnie parser przetwarza te tokeny na strukturę danych, którą interpreter może łatwo obsługiwać. Kolejnym wyzwaniem jest zarządzanie błędami w czasie wykonania programu, ponieważ wiele języków programowania pozwala na wykrywanie błędów tylko w trakcie uruchamiania programu.

Testowanie interpreterów jest kluczowym krokiem, który pozwala na upewnienie się, że wszystkie funkcje działają zgodnie z oczekiwaniami. Każdy program musi być uruchomiony w celu weryfikacji poprawności przetwarzania instrukcji i błędów, które mogą wystąpić w czasie jego wykonania. Sprawdzanie poprawności działania interpreterów jest szczególnie istotne w kontekście języków takich jak NanoBASIC, które mają zastosowania w prostych projektach edukacyjnych, ale także mogą być używane w aplikacjach wymagających szybkiej analizy danych.

Ważnym aspektem, który należy uwzględnić przy budowie interpreterów, jest zrozumienie różnicy między językami kompilowanymi i interpretowanymi. Kompilacja to proces, który tłumaczy cały kod na maszynowy język przed jego wykonaniem, co pozwala na optymalizację i szybsze działanie programów. Z kolei interpreter wykonuje kod bezpośrednio, instrukcja po instrukcji, co może prowadzić do wolniejszego działania, ale oferuje elastyczność i ułatwia proces debugowania. Współczesne języki, takie jak Python, łączą te dwie koncepcje, dając programistom zarówno szybkość, jak i elastyczność w pracy z kodem.

Co istotne, w kontekście tworzenia interpreterów, warto również zaznaczyć, jak istotną rolę w tym procesie odgrywa dobór odpowiednich struktur danych oraz algorytmów, które pozwolą na efektywne zarządzanie pamięcią i operacjami. Dobre zrozumienie działania interpreterów nie tylko ułatwia tworzenie nowych języków programowania, ale także pomaga w lepszym zrozumieniu podstawowych zasad działania komputerów, takich jak zarządzanie zasobami, przechowywanie i przetwarzanie informacji.

Jak zbudować interpreter Brainfuck w Pythonie: od podstaw do praktyki

W projektach opisanych w tej książce każde zadanie jest zorganizowane jako pakiet Pythona. Każdy z tych pakietów znajduje się w osobnym folderze, zawierającym plik main.py, który inicjuje wykonanie programu, gdy projekt jest uruchamiany z poziomu linii poleceń. Kod źródłowy dla każdego projektu dostępny jest w repozytorium GitHub książki, pod adresem https://github.com/davecom/ComputerScienceFromScratch. Zasadniczo jednak, cały kod będzie również zawarty bezpośrednio w książce, o ile nie zostanie to inaczej wskazane. Każda lista kodu będzie zawierała nazwę pliku Pythona, z którym jest związana, co ułatwi lokalizowanie jej w repozytorium książki.

W tym rozdziale skupimy się na tworzeniu prostego interpretera dla języka Brainfuck. Nasza aplikacja będzie odpowiedzialna za przyjęcie ścieżki do pliku zawierającego kod Brainfuck i przekazanie jej do głównego interpretera. Oczywiście, w celu zaimplementowania tego procesu, niezbędne będzie wykorzystanie funkcji do obsługi argumentów wiersza poleceń, takich jak ArgumentParser z biblioteki argparse.

python
Copy code
from argparse import ArgumentParser

from Brainfuck.brainfuck import Brainfuck
if __name__ == "__main__":
    # Parse the file argument
    file_parser = ArgumentParser("Brainfuck")
    file_parser.add_argument("brainfuck_file", help="A file containing Brainfuck source code.")
    arguments = file_parser.parse_args()
    Brainfuck(arguments.brainfuck_file).execute()

W tym przykładzie kodu używamy ArgumentParser, aby pobrać ścieżkę do pliku zawierającego kod źródłowy w Brainfucku, a następnie przekazać ją do klasy Brainfuck, która zrealizuje interpretację kodu. ArgumentParser umożliwia łatwą obsługę argumentów wiersza poleceń, co będziemy wykorzystywać w każdym projekcie tej książki.

Kolejnym krokiem jest napisanie samego interpretera. Interpretor Brainfuck będzie odpowiedzialny za utrzymanie stanu maszyny (czyli za komórki, wskaźnik komórki oraz wskaźnik instrukcji) oraz za przetwarzanie każdego polecenia Brainfuck zawartego w pliku źródłowym.

python
Copy code
from pathlib import Path
class Brainfuck:
    def __init__(self, file_name: str | Path):

        with open(file_name, "r") as text_file:

            self.source_code: str = text_file.read()
    def execute(self):
        cells: list[int] = [0] * 30000
        cell_index = 0
        instruction_index = 0
        while instruction_index < len(self.source_code):
            instruction = self.source_code[instruction_index]
            match instruction:
                case ">": cell_index += 1
                case "<": cell_index -= 1
                case "+": cells[cell_index] = clamp0_255_wraparound(cells[cell_index] + 1)
                case "-": cells[cell_index] = clamp0_255_wraparound(cells[cell_index] - 1)
                case ".": print(chr(cells[cell_index]), end='', flush=True)
                case ",": cells[cell_index] = clamp0_255_wraparound(int(input()))
                case "[": 
                    if cells[cell_index] == 0:
                        instruction_index = self.find_bracket_match(instruction_index, True)
                case "]":
                    if cells[cell_index] != 0:
                        instruction_index = self.find_bracket_match(instruction_index, False)
            instruction_index += 1

Każde polecenie w języku Brainfuck (takie jak >, <, +, -, [, ], . i ,) wpływa na stan maszyny lub wykonuje operacje wejścia/wyjścia w zależności od tego, jakie instrukcje pojawiają się w kodzie źródłowym. Warto zauważyć, że polecenie match zostało wprowadzone w Pythonie 3.10 i jest podobne do znanych konstrukcji switch z innych języków. Z kolei przy każdej iteracji kodu sprawdzamy, która instrukcja jest aktualnie przetwarzana i wykonujemy odpowiednią operację na stanie maszyny.

Implementacja funkcji find_bracket_match() jest nieco bardziej skomplikowana, ponieważ musimy obsługiwać zagnieżdżone pętle Brainfucka. Pętla w tym języku jest reprezentowana przez parę nawiasów kwadratowych, więc kluczowe jest, aby odpowiednio obsługiwać sytuacje, w których jeden nawias znajduje się wewnątrz drugiego. Funkcja ta przeszukuje kod źródłowy, porównując nawiasy otwierające i zamykające, a kiedy napotka parę nawiasów, może przejść do odpowiedniego miejsca w kodzie.

python
Copy code
def find_bracket_match(self, start: int, forward: bool) -> int:
    in_between_brackets = 0
    direction = 1 if forward else -1
    location = start + direction

    start_bracket = "[" if forward else "]"

    end_bracket = "]" if forward else "["
    while 0 <= location < len(self.source_code):
        if self.source_code[location] == end_bracket:
            if in_between_brackets == 0:
                return location
            in_between_brackets -= 1
        elif self.source_code[location] == start_bracket:
            in_between_brackets += 1
        location += direction
    print(f"Error: could not find match for {start_bracket} at {start}.")
    return start

Co więcej, przy implementacji interpretera warto zwrócić uwagę na efektywność, ponieważ interpreter Brainfuck jest bardzo prosty, a każda operacja wpływa bezpośrednio na stan maszyny. W związku z tym rozważmy, w jaki sposób zorganizować kod, aby był nie tylko efektywny, ale także przejrzysty i łatwy do rozbudowy o dodatkowe funkcjonalności, takie jak obsługa większych programów czy rozbudowa o inne komendy.

Jak rozwój języka BASIC wpłynął na ewolucję komputerów osobistych i ich oprogramowania?

Pomimo, że BASIC stał się standardem na wielu maszynach, pojawiły się również inne inicjatywy, które zmieniały jego oblicze. Jednym z takich przykładów jest Tiny BASIC, który powstał w odpowiedzi na rosnące ceny interpreterów BASIC firmy Microsoft. Pomimo, że był to język o ograniczonych możliwościach, spełniał on swoją rolę, oferując programistom bardziej dostępną alternatywę, która zmieściła się w bardzo ograniczonych zasobach pamięci mikrokomputerów tamtych lat. Warto dodać, że rozwój Tiny BASIC wiązał się także z ideą wolnego oprogramowania, które wówczas zaczynało zdobywać popularność.

NanoBASIC, na którym skupiamy się w tej książce, jest rozwinięciem tego minimalistycznego podejścia. Jego celem było zachowanie prostoty i wydajności, przy jednoczesnym umożliwieniu użytkownikowi programowania w środowisku komputerów o bardzo ograniczonych zasobach. Język ten, będąc odmianą Tiny BASIC, zachowuje prostotę swoich poprzedników, ale jest bardziej elastyczny dzięki możliwościom takich języków jak Python.

NanoBASIC, jak wiele innych wersji BASIC, to język imperatywny, ale z pewnymi ograniczeniami, które sprawiają, że nie jest to w pełni funkcjonalny język proceduralny. Brak w nim takich elementów jak funkcje, parametry czy wartości zwracane, które są obecne w bardziej zaawansowanych językach programowania. Dodatkowo, brak pętli i innych nowoczesnych struktur kontrolnych powoduje, że programy w NanoBASIC mogą stać się trudne do zarządzania, a programowanie w nim ma swoje ograniczenia. Jednym z powodów tego stanu rzeczy jest fakt, że początkowe wersje BASIC nie oferowały mechanizmów organizacji kodu, jak funkcje czy obiekty, przez co programy często były określane mianem "spaghetti code", czyli kodu nieuporządkowanego i trudnego do śledzenia.

Polecenie LET pozwala na przypisanie wartości do zmiennej, gdzie zmienna jest zawsze liczbą całkowitą. Mimo że w pierwotnych wersjach BASIC ograniczano się do zmiennych jednowyrazowych (A, B, C...), w NanoBASIC programista może używać zmiennych o dowolnej długości, co daje większą elastyczność. Operacje matematyczne w tym języku są proste, obejmując podstawowe operatory arytmetyczne takie jak dodawanie, odejmowanie, mnożenie i dzielenie. Dzięki temu użytkownik, nawet nieznający zaawansowanych koncepcji programistycznych, jest w stanie wykonać podstawowe obliczenia i operacje logiczne.

Z kolei polecenie PRINT umożliwia wyświetlanie tekstów i wyników obliczeń na ekranie, co w połączeniu z innymi instrukcjami, takimi jak IF, GOTO i GOSUB, pozwala na tworzenie prostych, ale funkcjonalnych programów. NanoBASIC pozostaje wciąż bardzo "bliski" maszynie, co oznacza, że programista musi być świadomy ograniczeń swojego środowiska, szczególnie w kontekście pamięci i mocy obliczeniowej komputera.