Oto pytanie teoretyczne - takie, które w żadnym wypadku nie daje łatwej odpowiedzi, nawet trywialnej.

W Game of Life Conwaya istnieją konstrukcje takie jak metapiksel, które pozwalają Game of Life na symulację dowolnego innego systemu reguł Game-of-Life. Ponadto wiadomo, że gra w życie jest kompletna.

Twoim zadaniem jest zbudowanie automatu komórkowego przy użyciu zasad gry Conwaya, która pozwoli na grę w Tetris.

Twój program otrzyma dane wejściowe poprzez ręczną zmianę stanu automatu na konkretnej generacji, aby reprezentować przerwanie (np. Przesunięcie elementu w lewo lub w prawo, upuszczenie, obrócenie lub losowe wygenerowanie nowego elementu do umieszczenia na siatce), licząc określoną liczbę pokoleń jako czas oczekiwania i wyświetlanie wyniku gdzieś w automacie. Wyświetlany wynik musi wyraźnie przypominać rzeczywistą siatkę Tetris.

Twój program będzie oceniany według następujących elementów, w kolejności (z niższymi kryteriami działającymi jako rozstrzygające dla wyższych kryteriów):

• Rozmiar ramki granicznej - wygrywa prostokątne pudełko o najmniejszym obszarze, które całkowicie zawiera dane rozwiązanie.

• Mniejsze zmiany na wejściu - najmniej komórek (w najgorszym przypadku w automacie), które należy ręcznie dostosować, aby wygrać przerwanie.

• Najszybsza realizacja - wygrywa najmniej pokoleń, które awansują o jeden tik w symulacji.

• Początkowa liczba żywych komórek - mniejsza liczba wygrywa.

• Pierwszy post - wcześniejszy post wygrywa.

To zaczęło się jako misja, ale zakończyło się jako odyseja.

Wyprawa po procesor Tetris, 2940928 x 10 295 296

Plik wzorców, w całej okazałości, można znaleźć tutaj , dostępny w przeglądarce tutaj .

Ten projekt jest zwieńczeniem wysiłków wielu użytkowników w ciągu ostatnich 1 i 1/2 roku. Chociaż skład zespołu zmieniał się w czasie, uczestnicy w chwili pisania są:

• PhiNotPi
• El'endia Starman
• K Zhang
• Niebieski (Muddyfish)
• Kwak krowy (Kritixi Lithos)
• Mego
• Quartata

Chcielibyśmy również podziękować 7H3_H4CK3R, Conorowi O'Brienowi i wielu innym użytkownikom, którzy włożyli wiele wysiłku w rozwiązanie tego problemu.

Ze względu na bezprecedensowy zakres tej współpracy odpowiedź ta jest podzielona na części na wiele odpowiedzi napisanych przez członków tego zespołu. Każdy członek napisze o konkretnych podtematach, mniej więcej odpowiadających obszarom projektu, w które byli najbardziej zaangażowani.

Rozdaj wszelkie pozytywne głosy lub nagrody wszystkim członkom zespołu.

Spis treści

1. Przegląd
2. Metapiksele i VarLife
3. Sprzęt komputerowy
4. QFTASM i Cogol
5. Montaż, tłumaczenie i przyszłość
6. Nowy język i kompilator

Rozważ również sprawdzenie naszej organizacji GitHub, w której umieściliśmy cały kod, który napisaliśmy jako część naszego rozwiązania. Pytania można kierować do naszego pokoju rozmów programistycznych .

Część 1: Przegląd

Ideą tego projektu jest abstrakcja . Zamiast opracowywać grę Tetris bezpośrednio w Life, powoli przyspieszaliśmy abstrakcję w kilku krokach. Na każdej warstwie oddalamy się od trudności życia i zbliżamy się do budowy komputera, który jest tak łatwy do zaprogramowania jak każdy inny.

Po pierwsze, wykorzystaliśmy metapiksele OTCA jako podstawę naszego komputera. Te metapiksele są w stanie emulować dowolne reguły „podobne do życia”. Wireworld i komputer Wireworld służyły jako ważne źródła inspiracji dla tego projektu, dlatego staraliśmy się stworzyć podobną konstrukcję z metapikselami. Chociaż nie jest możliwe emulowanie Wireworld za pomocą metapikseli OTCA, możliwe jest przypisanie różnych metapikseli innym regułom i zbudowanie zestawów metapikseli, które działają podobnie do drutów.

Następnym krokiem było zbudowanie szeregu podstawowych bramek logicznych, które miałyby stanowić podstawę komputera. Już na tym etapie mamy do czynienia z koncepcjami podobnymi do projektowania procesorów w świecie rzeczywistym. Oto przykład bramki OR, każda komórka na tym obrazie jest w rzeczywistości całą metapikselą OTCA. Możesz zobaczyć, jak „elektrony” (każdy reprezentuje pojedynczy bit danych) wchodzą i opuszczają bramę. Możesz również zobaczyć wszystkie różne typy metapikseli, których użyliśmy w naszym komputerze: B / S jako czarne tło, B1 / S w kolorze niebieskim, B2 / S w kolorze zielonym i B12 / S1 w kolorze czerwonym.

Stąd opracowaliśmy architekturę naszego procesora. Poświęciliśmy wiele wysiłku na zaprojektowanie architektury, która byłaby zarówno tak ezoteryczna, jak i możliwie najłatwiejsza do wdrożenia. Podczas gdy komputer Wireworld zastosował podstawową architekturę wyzwalaną przez transport, ten projekt wykorzystuje znacznie bardziej elastyczną architekturę RISC wraz z wieloma kodami operacyjnymi i trybami adresowania. Stworzyliśmy język asemblera, znany jako QFTASM (Quest for Tetris Assembly), który kierował budową naszego procesora.

Nasz komputer jest również asynchroniczny, co oznacza, że ​​nie ma globalnego zegara sterującego komputerem. Danym raczej towarzyszy sygnał zegarowy, który przepływa wokół komputera, co oznacza, że ​​musimy skupić się tylko na lokalnych, ale nie globalnych czasach komputera.

Oto ilustracja naszej architektury procesorów:

Odtąd jest to tylko kwestia wdrożenia Tetris na komputerze. Aby to osiągnąć, pracowaliśmy nad wieloma metodami kompilowania języka wyższego poziomu do QFTASM. Mamy podstawowy język o nazwie Cogol, drugi, bardziej zaawansowany język w trakcie opracowywania, a na koniec mamy w przygotowaniu backend GCC. Obecny program Tetris został napisany / skompilowany z Cogola.

Po wygenerowaniu końcowego kodu Tetris QFTASM, ostatnim krokiem było połączenie tego kodu z odpowiednim ROM, a następnie z metapikseli do podstawowej Gry Życia, kończąc naszą budowę.

Uruchamianie Tetris

Dla tych, którzy chcą grać w Tetris bez konieczności korzystania z komputera, możesz uruchomić kod źródłowy Tetris na interpretera QFTASM . Ustaw adresy wyświetlania RAM na 3-32, aby wyświetlić całą grę. Oto bezpośredni link dla wygody: Tetris w QFTASM .

Funkcje gry:

• Wszystkie 7 tetrominoes
• Ruch, obrót, miękkie krople
• Czyszczenie linii i punktowanie
• Podgląd utworu
• Wejścia graczy wprowadzają losowość

Pokaz

Nasz komputer reprezentuje tablicę Tetris jako siatkę w swojej pamięci. Adresy 10-31 wyświetlają tablicę, adresy 5-8 wyświetlają fragment podglądu, a adres 3 zawiera wynik.

Wejście

Wprowadzanie do gry odbywa się poprzez ręczną edycję zawartości adresu RAM 1. Korzystanie z interpretera QFTASM oznacza wykonywanie bezpośrednich zapisów na adres 1. Poszukaj „Bezpośredniego zapisu do RAM” na stronie tłumacza. Każdy ruch wymaga edycji tylko jednego bitu pamięci RAM, a ten rejestr wejściowy jest automatycznie czyszczony po odczytaniu zdarzenia wejściowego.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

System oceniania

Otrzymujesz bonus za usunięcie wielu linii w jednej turze.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Część 2: OTCA Metapixel i VarLife

OTCA Metapixel

( Źródło )

OTCA Metapixel jest konstruktem w Gra w życie, które mogą być wykorzystane do symulacji żadnego życia podobny automatów komórkowych. Jak mówi LifeWiki (link powyżej),

Metapiksel OTCA to komórka jednostkowa z okresu 35328 o wymiarach 2048 × 2048 zbudowana przez Brice Due ... Ma wiele zalet ... w tym możliwość emulacji dowolnego automatu komórkowego podobnego do Życia oraz fakt, że po pomniejszeniu ON i komórki OFF są łatwe do odróżnienia ...

To, co przypominają Życiowe automaty komórkowe , to zasadniczo to, że komórki rodzą się, a komórki przeżywają w zależności od tego, ile ich ośmiu sąsiednich komórek żyje. Składnia tych reguł jest następująca: litera B, po której następuje liczba żywych sąsiadów, która spowoduje poród, następnie cięcie, następnie litera S, po której następuje liczba żywych sąsiadów, którzy utrzymają komórkę przy życiu. Trochę nieprzyjemnie, więc myślę, że przykład pomoże. Kanoniczną Grę Życia można przedstawić za pomocą reguły B3 / S23, która mówi, że każda martwa komórka z trzema żywymi sąsiadami ożyje, a każda żywa komórka z dwoma lub trzema żywymi sąsiadami pozostanie przy życiu. W przeciwnym razie komórka umiera.

Pomimo tego, że jest komórką o wymiarach 2048 x 2048, metapiksel OTCA faktycznie ma ramkę graniczną o wymiarach 2058 x 2058 komórek, ponieważ zachodzi on na pięć komórek w każdym kierunku ze swoimi ukośnymi sąsiadami. Nakładające się komórki służą do przechwytywania szybowców - emitowanych w celu zasygnalizowania sąsiadom metacells, że jest włączony - aby nie zakłócały innych metapikseli ani nie odlatywały w nieskończoność. Reguły narodzin i przeżycia są kodowane w specjalnej części komórek po lewej stronie metapiksela, poprzez obecność lub brak zjadaczy w określonych pozycjach wzdłuż dwóch kolumn (jedna do porodu, druga do przeżycia). Jeśli chodzi o wykrywanie stanu sąsiednich komórek, oto jak to się dzieje:

Strumień 9-LWSS krąży następnie wokół komórki zgodnie z ruchem wskazówek zegara, tracąc LWSS dla każdej sąsiedniej komórki „on”, która wywołała reakcję miododajną. Liczbę brakujących LWSS zlicza się przez wykrycie pozycji przedniego LWSS przez rozbicie innego LWSS z przeciwnego kierunku. Ta kolizja uwalnia szybowce, które wyzwalają jedną lub dwie reakcje pszczół miodnych, jeśli zjadacze wskazujące na brak warunków porodu / przeżycia są nieobecne.

Bardziej szczegółowy schemat każdego aspektu metapikselu OTCA można znaleźć na jego oryginalnej stronie internetowej: Jak to działa? .

VarLife

Zbudowałem internetowy symulator zasad podobnych do Życia, w którym możesz sprawić, by każda komórka zachowywała się zgodnie z dowolną zasadą podobną do życia i nazwałam ją „Wariacjami życia”. Nazwę tę skrócono do „VarLife”, aby była bardziej zwięzła. Oto zrzut ekranu (link do niego tutaj: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Ważne funkcje:

• Przełączaj komórki pomiędzy żywymi / martwymi i maluj planszę według różnych zasad.
• Możliwość uruchomienia i zatrzymania symulacji oraz zrobienia jednego kroku na raz. Możliwe jest również wykonanie określonej liczby kroków tak szybko, jak to możliwe lub wolniej, z szybkością ustawioną w polach tyknięcia na sekundę i milisekund na tyknięcie.
• Wyczyść wszystkie żywe komórki lub całkowicie zresetuj tablicę do stanu pustego.
• Może zmieniać rozmiary komórek i płytek, a także umożliwia owijanie toroidalne w poziomie i / lub w pionie.
• Permalinki (które kodują wszystkie informacje w adresie URL) i krótkie adresy URL (ponieważ czasami jest po prostu zbyt wiele informacji, ale i tak są ładne).
• Zestawy reguł ze specyfikacją B / S, kolorami i opcjonalną losowością.
• I wreszcie, ale zdecydowanie nie mniej ważne, renderowanie gifów!

Funkcja renderowania do gif jest moją ulubioną, ponieważ wymagało mnóstwo pracy, więc było naprawdę satysfakcjonujące, gdy w końcu złamałem ją o 7 rano, i ponieważ bardzo łatwo jest dzielić konstrukcje VarLife z innymi .

Podstawowe obwody VarLife

Podsumowując, komputer VarLife potrzebuje tylko czterech typów komórek! Osiem stanów we wszystkich zliczających stany martwe / żywe. Oni są:

• B / S (czarno / biały), który służy jako bufor między wszystkimi składnikami, ponieważ komórki B / S nigdy nie mogą być żywe.
• B1 / S (niebieski / cyjan), który jest głównym typem komórki używanym do propagacji sygnałów.
• B2 / S (zielony / żółty), który służy głównie do sterowania sygnałem, zapewniając, że nie będzie się on rozmnażał.
• B12 / S1 (czerwony / pomarańczowy), który jest wykorzystywany w kilku wyspecjalizowanych sytuacjach, takich jak skrzyżowanie sygnałów i przechowywanie odrobiny danych.

Użyj tego krótkiego adresu URL, aby otworzyć VarLife z już zakodowanymi regułami: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Przewody

Istnieje kilka różnych konstrukcji drutów o różnych właściwościach.

Jest to najłatwiejszy i najbardziej podstawowy drut w VarLife, niebieski pasek otoczony zielonymi paskami.

Krótki adres URL: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Ten drut jest jednokierunkowy. Oznacza to, że zabije każdy sygnał próbujący podróżować w przeciwnym kierunku. Jest także o jedną komórkę węższy niż podstawowy drut.

Krótki adres URL: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Istnieją również ukośne druty, ale nie są one w ogóle używane.

Krótki adres URL: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Bramy

Istnieje wiele sposobów na zbudowanie poszczególnych bram, więc pokażę tylko jeden przykład każdego rodzaju. Ten pierwszy gif pokazuje odpowiednio bramki AND, XOR i OR. Podstawową ideą jest to, że zielona komórka działa jak AND, niebieska komórka działa jak XOR, a czerwona komórka działa jak OR, a wszystkie pozostałe komórki wokół nich są po to, aby właściwie kontrolować przepływ.

Krótki adres URL: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Bramka AND-NOT, w skrócie „bramka ANT”, okazała się istotnym elementem. Jest to bramka, która przekazuje sygnał z A wtedy i tylko wtedy, gdy nie ma sygnału z B. Stąd „A AND NOT B”.

Krótki adres URL: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Chociaż nie jest to dokładnie brama , kafelek przecinający drut jest nadal bardzo ważny i przydatny.

Krótki adres URL: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Nawiasem mówiąc, nie ma tutaj bramy NIE. Dzieje się tak, ponieważ bez sygnału wejściowego należy wytworzyć stałą moc wyjściową, która nie działa dobrze z różnorodnością taktowania wymaganą przez obecny sprzęt komputerowy. W każdym razie bez problemu się dogadywaliśmy.

Ponadto, wiele elementów celowo zaprojektowano tak, aby pasowały do ​​ramki ograniczającej 11 na 11 ( kafelek ), gdzie zabiera sygnały 11 tyknięć od wejścia do płytki, aby opuścić płytkę. To sprawia, że ​​komponenty są bardziej modułowe i łatwiej łączą się ze sobą w razie potrzeby, bez konieczności martwienia się o dostosowanie drutów do odstępów lub rozrządu.

Aby zobaczyć więcej bram, które zostały odkryte / zbudowane w trakcie eksploracji elementów obwodów, sprawdź ten wpis na blogu autorstwa PhiNotPi: Building Blocks: Logic Gates .

Opóźnij komponenty

Podczas projektowania sprzętu komputerowego KZhang opracował wiele elementów opóźniających, pokazanych poniżej.

Opóźnienie o 4 tiki: krótki adres URL: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Opóźnienie 5 zaznaczeń: Krótki adres URL: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Opóźnienie 8 tyknięć (trzy różne punkty wejścia): Krótki adres URL: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Opóźnienie o 11 znaków: krótki adres URL: http://play.starmaninnovations.com/varlife/kfoADussXA

Opóźnienie o 12 tików: Krótki adres URL: http://play.starmaninnovations.com/varlife/bkamAfUfud

Opóźnienie 14 tików: Krótki adres URL: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Opóźnienie 15 tyknięć (weryfikowane przez porównanie z tym ): Krótki adres URL: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Cóż, to wszystko w przypadku podstawowych elementów obwodów w VarLife! Zobacz stanowisko sprzętowe KZhanga dla głównych obwodów komputera!

Część 3: Sprzęt

Dzięki naszej wiedzy na temat bramek logicznych i ogólnej struktury procesora możemy rozpocząć projektowanie wszystkich elementów komputera.

Demultiplekser

Demultiplekser, czyli demultiplekser, jest kluczowym składnikiem ROM, RAM i ALU. Kieruje sygnał wejściowy do jednego z wielu sygnałów wyjściowych na podstawie niektórych danych selektora. Składa się z 3 głównych części: konwertera szeregowo-równoległego, kontrolera sygnału i rozdzielacza sygnału zegara.

Zaczynamy od konwersji danych selektora szeregowego na „równoległy”. Odbywa się to poprzez strategiczne dzielenie i opóźnianie danych tak, że najbardziej lewy bit danych przecina sygnał zegara na skrajnym lewym kwadracie 11 x 11, następny bit danych przecina sygnał zegara na następnym kwadracie 11 x 11 i tak dalej. Chociaż każdy bit danych będzie wyprowadzany w każdym kwadracie 11 x 11, każdy bit danych przecina się z sygnałem zegara tylko raz.

Następnie sprawdzimy, czy dane równoległe odpowiadają ustalonemu adresowi. Robimy to za pomocą bramek AND i ANT na zegarze i danych równoległych. Musimy jednak upewnić się, że dane równoległe są również wyprowadzane, aby można je było ponownie porównać. Oto bramy, które wymyśliłem:

Wreszcie, po prostu podzieliliśmy sygnał zegara, ułożyliśmy kilka kontrolerów sygnału (po jednym dla każdego adresu / wyjścia) i mamy multiplekser!

ROM

ROM powinien przyjmować adres jako dane wejściowe i wysyłać instrukcje pod tym adresem jako dane wyjściowe. Zaczynamy od użycia multipleksera, aby skierować sygnał zegara do jednej z instrukcji. Następnie musimy wygenerować sygnał za pomocą niektórych skrzyżowań przewodów i bramek OR. Przecinanie drutu umożliwia przesunięcie sygnału zegarowego w dół wszystkich 58 bitów instrukcji, a także wygenerowanie sygnału (obecnie równoległego), który może zostać przesunięty w dół przez ROM, aby zostać wyprowadzony.

Następnie wystarczy przekonwertować sygnał równoległy na dane szeregowe, a ROM jest gotowy.

ROM jest obecnie generowany przez uruchomienie skryptu w Golly, który przetłumaczy kod asemblera ze schowka na ROM.

SRL, SL, SRA

Te trzy bramki logiczne są używane do przesuwania bitów i są bardziej skomplikowane niż typowe AND, OR, XOR itp. Aby te bramki działały, najpierw opóźnimy sygnał zegara o odpowiednią ilość czasu, aby spowodować „przesunięcie” w danych. Drugi argument podany dla tych bram określa liczbę bitów do przesunięcia.

W przypadku SL i SRL musimy to zrobić

1. Upewnij się, że 12 najbardziej znaczących bitów nie jest włączone (w przeciwnym razie wyjście to po prostu 0) i
2. Opóźnij dane o prawidłową ilość na podstawie 4 najmniej znaczących bitów.

Jest to możliwe dzięki wiązce bramek AND / ANT i multiplekserowi.

SRA jest nieco inny, ponieważ musimy skopiować bit znaku podczas zmiany. Robimy to, ANDując sygnał zegarowy bitem znaku, a następnie kopiując to wyjście kilka razy za pomocą rozgałęźników drutowych i bramek OR.

Zatrzask Set-Reset (SR)

Wiele części funkcji procesora opiera się na możliwości przechowywania danych. Za pomocą 2 czerwonych komórek B12 / S1 możemy to zrobić. Dwie komórki mogą się nawzajem włączać, a także mogą trzymać się razem. Używając dodatkowego zestawu, resetowania i odczytu obwodów, możemy wykonać prostą zatrzask SR.

Synchronizator

Konwertując dane szeregowe na dane równoległe, a następnie ustawiając wiązkę zatrzasków SR, możemy przechowywać całe słowo danych. Następnie, aby ponownie pobrać dane, możemy po prostu odczytać i zresetować wszystkie zatrzaski i odpowiednio opóźnić dane. To pozwala nam przechowywać jedno (lub więcej) słowo danych podczas oczekiwania na kolejne, pozwalając na synchronizację dwóch słów danych przybywających w różnych momentach.

Czytaj licznik

To urządzenie śledzi, ile razy trzeba adresować z pamięci RAM. Robi to za pomocą urządzenia podobnego do zatrzasku SR: klapki typu T. Za każdym razem, gdy przerzutnik T odbiera dane wejściowe, zmienia stan: jeśli był włączony, wyłącza się i na odwrót. Kiedy przerzutnik T jest przerzucany od wł. Do wył., Wysyła impuls wyjściowy, który można wprowadzić do innego przerzutnika T w celu utworzenia 2-bitowego licznika.

Aby dokonać odczytu licznika, musimy ustawić licznik na odpowiedni tryb adresowania z dwiema bramkami ANT i użyć sygnału wyjściowego licznika, aby zdecydować, gdzie skierować sygnał zegara: do ALU lub do pamięci RAM.

Czytaj kolejkę

Kolejka odczytu musi śledzić, który licznik odczytu wysłał dane wejściowe do pamięci RAM, aby mógł wysłać dane wyjściowe pamięci RAM do właściwej lokalizacji. Aby to zrobić, używamy niektórych zatrzasków SR: jeden zatrzask na każde wejście. Gdy sygnał jest wysyłany do pamięci RAM z licznika odczytu, sygnał zegara jest dzielony i ustawia zatrzask SR licznika. Wyjście pamięci RAM jest następnie ANDowane z zatrzaskiem SR, a sygnał zegarowy z pamięci RAM resetuje zatrzask SR.

ALU

ALU działa podobnie do kolejki odczytu, ponieważ używa zatrzasku SR, aby śledzić, gdzie wysłać sygnał. Najpierw zatrzask SR obwodu logicznego odpowiadający kodowi operacji instrukcji ustawia się za pomocą multipleksera. Następnie wartości pierwszego i drugiego argumentu są ANDowane za pomocą zatrzasku SR, a następnie przekazywane do obwodów logicznych. Sygnał zegara resetuje zatrzask, gdy przechodzi, dzięki czemu ALU może być ponownie użyte. (Większość obwodów jest zamknięta w golfa, a tony zarządzania opóźnieniami są wpychane, więc wygląda to na trochę bałaganu)

Baran

Pamięć RAM była najbardziej skomplikowaną częścią tego projektu. Wymagało to bardzo dokładnej kontroli nad każdym zatrzaskiem SR, który przechowywał dane. Do odczytu adres jest wysyłany do multipleksera i wysyłany do jednostek RAM. Jednostki RAM wysyłają równolegle przechowywane dane, które są konwertowane na szeregowe i wysyłane. Do zapisu adres jest wysyłany do innego multipleksera, dane do zapisu są konwertowane z szeregowego na równoległe, a jednostki pamięci RAM propagują sygnał w pamięci RAM.

Każda metapikselowa jednostka RAM 22x22 ma tę podstawową strukturę:

Zestawiając całą pamięć RAM, otrzymujemy coś, co wygląda następująco:

Składając wszystko w całość

Korzystając ze wszystkich tych komponentów i ogólnej architektury komputera opisanej w Omówieniu , możemy zbudować działający komputer!

Pliki do pobrania: - Gotowy komputer Tetris - Skrypt tworzenia pamięci ROM, pusty komputer i główny komputer znajdujący

Część 4: QFTASM i Cogol

Przegląd architektury

Krótko mówiąc, nasz komputer ma 16-bitową asynchroniczną architekturę RISC Harvard. Podczas ręcznego budowania procesora architektura RISC ( komputer z ograniczoną liczbą instrukcji ) jest praktycznie wymagana. W naszym przypadku oznacza to, że liczba kodów jest niewielka i, co ważniejsze, wszystkie instrukcje są przetwarzane w bardzo podobny sposób.

Dla porównania, komputer Wireworld zastosował architekturę wyzwalaną przez transport , w której była jedyna instrukcja MOVi obliczenia były wykonywane przez zapis / odczyt specjalnych rejestrów. Chociaż ten paradygmat prowadzi do bardzo łatwej do wdrożenia architektury, wynik jest również bezużyteczny na granicy: wszystkie operacje arytmetyczne / logiczne / warunkowe wymagają trzech instrukcji. Było dla nas jasne, że chcemy stworzyć znacznie mniej ezoteryczną architekturę.

Aby uprościć procesor i zwiększyć użyteczność, podjęliśmy kilka ważnych decyzji projektowych:

• Brak rejestrów. Każdy adres w pamięci RAM jest traktowany jednakowo i może być wykorzystany jako dowolny argument dla dowolnej operacji. W pewnym sensie oznacza to, że całą pamięć RAM można traktować jak rejestry. Oznacza to, że nie ma specjalnych instrukcji ładowania / przechowywania.
• W podobny sposób mapowanie pamięci. Wszystko, co można zapisać lub odczytać, udostępnia wspólny schemat adresowania. Oznacza to, że licznik programu (PC) ma adres 0, a jedyną różnicą między zwykłymi instrukcjami a instrukcjami przepływu sterowania jest to, że instrukcje przepływu sterowania używają adresu 0.
• Dane są przesyłane szeregowo, równolegle w pamięci. Ze względu na „komputerowy” charakter naszego komputera, dodawanie i odejmowanie jest znacznie łatwiejsze do wdrożenia, gdy dane są przesyłane w postaci szeregowej little-endian (najpierw najmniej znaczący bit). Ponadto dane szeregowe eliminują potrzebę uciążliwych magistral danych, które są zarówno naprawdę szerokie, jak i kłopotliwe w odpowiednim czasie (aby dane pozostały razem, wszystkie „pasy” autobusu muszą doświadczyć tego samego opóźnienia podróży).
• Architektura Harvarda, co oznacza podział między pamięcią programu (ROM) a pamięcią danych (RAM). Chociaż zmniejsza to elastyczność procesora, pomaga to w optymalizacji rozmiaru: długość programu jest znacznie większa niż ilość potrzebnej pamięci RAM, dzięki czemu możemy podzielić program na ROM, a następnie skoncentrować się na kompresji ROM , co jest znacznie łatwiejsze, gdy jest tylko do odczytu.
• 16-bitowa szerokość danych. Jest to najmniejsza z dwóch potęg, która jest szersza niż standardowa tablica Tetris (10 bloków). To daje nam zakres danych od -32768 do +32767 i maksymalną długość programu 65536 instrukcji. (2 ^ 8 = 256 instrukcji wystarcza na najprostsze rzeczy, które chcielibyśmy zrobić z procesorem zabawki, ale nie Tetris.)
• Projekt asynchroniczny. Zamiast centralnego zegara (lub równoważnie kilku zegarów) dyktujących taktowanie komputera, wszystkim danym towarzyszy „sygnał zegarowy”, który przemieszcza się równolegle z danymi przepływającymi wokół komputera. Niektóre ścieżki mogą być krótsze niż inne, i chociaż nastręczałoby to trudności projektowi z centralnym taktowaniem, projekt asynchroniczny może łatwo poradzić sobie z operacjami w czasie zmiennym.
• Wszystkie instrukcje są jednakowej wielkości. Uważaliśmy, że najbardziej elastyczną opcją jest architektura, w której każda instrukcja ma 1 kod operacji z 3 operandami (miejsce docelowe wartości wartości). Obejmuje to operacje na danych binarnych, a także ruchy warunkowe.
• Prosty system trybu adresowania. Posiadanie różnych trybów adresowania jest bardzo przydatne do obsługi takich rzeczy, jak tablice lub rekurencja. Udało nam się wdrożyć kilka ważnych trybów adresowania za pomocą stosunkowo prostego systemu.

Ilustracja naszej architektury znajduje się w poście przeglądowym.

Funkcjonalność i operacje ALU

Odtąd chodziło o określenie, jaką funkcjonalność powinien mieć nasz procesor. Szczególną uwagę zwrócono na łatwość wdrożenia oraz wszechstronność każdego polecenia.

Ruchy warunkowe

Ruchy warunkowe są bardzo ważne i służą zarówno jako przepływ kontrolny na małą skalę, jak i na dużą skalę. „Mała skala” odnosi się do jego zdolności do kontrolowania wykonania określonego przenoszenia danych, podczas gdy „duża skala” odnosi się do jej zastosowania jako operacji skoku warunkowego do przeniesienia przepływu sterowania do dowolnego dowolnego kodu. Nie ma dedykowanych operacji przeskoku, ponieważ z powodu mapowania pamięci ruch warunkowy może zarówno skopiować dane do zwykłej pamięci RAM, jak i skopiować adres docelowy na komputer. Postanowiliśmy również zrezygnować zarówno z bezwarunkowych ruchów, jak i bezwarunkowych skoków z podobnego powodu: oba mogą być realizowane jako ruch warunkowy z warunkiem zakodowanym na TRUE.

Zdecydowaliśmy się na dwa różne typy ruchów warunkowych: „ruch, jeśli nie zero” ( MNZ) i „ruch, jeśli mniej niż zero” ( MLZ). Funkcjonalnie MNZsprowadza się do sprawdzenia, czy dowolny bit w danych ma wartość 1, a MLZsprowadza się do sprawdzenia, czy bit znaku ma wartość 1. Są one przydatne odpowiednio do równości i porównań. Powodem, dla którego wybraliśmy te dwa spośród innych, takich jak „ruch, jeśli zero” ( MEZ) lub „ruch, jeśli jest większy od zera” ( MGZ), było to, MEZże wymagałoby utworzenia PRAWDZIWEGO sygnału z pustego sygnału, podczas gdy MGZjest to bardziej skomplikowana kontrola, wymagająca bit znaku ma wartość 0, a co najmniej jeden inny bit ma wartość 1.

Arytmetyka

Kolejnymi najważniejszymi instrukcjami, pod względem prowadzenia projektu procesora, są podstawowe operacje arytmetyczne. Jak wspomniałem wcześniej, używamy danych szeregowych little-endian, a wybór endianizmu zależy od łatwości operacji dodawania / odejmowania. Dzięki pierwszemu najmniej znaczącemu bitowi, jednostki arytmetyczne mogą łatwo śledzić bit przenoszący.

Zdecydowaliśmy się zastosować reprezentację uzupełnienia 2 dla liczb ujemnych, ponieważ dzięki temu dodawanie i odejmowanie jest bardziej spójne. Warto zauważyć, że komputer Wireworld używał uzupełnienia 1.

Dodawanie i odejmowanie to zakres natywnej obsługi arytmetycznej naszego komputera (oprócz przesunięć bitów, które zostaną omówione później). Inne operacje, takie jak mnożenie, są zbyt skomplikowane, aby mogły być obsługiwane przez naszą architekturę i muszą zostać zaimplementowane w oprogramowaniu.

Operacje bitowe

Nasz procesor ma AND, ORi XORinstrukcje, które mają to, czego można się spodziewać. Zamiast NOTinstrukcji, zdecydowaliśmy się na instrukcję „i nie” ( ANT). Trudność z NOTinstrukcją polega na tym, że musi ona wytwarzać sygnał z braku sygnału, co jest trudne w przypadku automatów komórkowych. ANTInstrukcja zwraca 1 tylko wtedy, gdy pierwszy bit argument jest 1, a drugi bit argument jest 0. W ten sposób, NOT xjest równoważna ANT -1 x(także XOR -1 x). Co więcej, ANTjest wszechstronny i ma swoją główną zaletę w maskowaniu: w przypadku programu Tetris używamy go do usuwania tetromino.

Przesunięcie bitów

Operacje przesuwania bitów są najbardziej złożonymi operacjami obsługiwanymi przez ALU. Pobierają dwa dane wejściowe: wartość do przesunięcia i kwotę do przesunięcia o. Pomimo złożoności (ze względu na zmienną liczbę przesunięć) operacje te są kluczowe dla wielu ważnych zadań, w tym wielu operacji „graficznych” związanych z Tetris. Przesunięcia bitów służyłyby również jako podstawa wydajnych algorytmów mnożenia / dzielenia.

Nasz procesor ma trzy bitowe operacje przesunięcia, „shift left” ( SL), „shift right logical” ( SRL) i „shift right arytmetic” ( SRA). Pierwsze dwa przesunięcia bitowe ( SLi SRL) wypełniają nowe bity wszystkimi zerami (co oznacza, że ​​liczba ujemna przesunięta w prawo nie będzie już ujemna). Jeśli drugi argument zmiany jest poza zakresem od 0 do 15, wynik jest zerowy, jak można się spodziewać. Dla ostatniego przesunięcia bitowego przesunięcie SRAbitowe zachowuje znak wejścia, a zatem działa jak prawdziwy podział na dwa.

Instrukcja Rurociągi

Czas porozmawiać o niektórych drobnych szczegółach architektury. Każdy cykl procesora składa się z następujących pięciu kroków:

1. Pobierz bieżącą instrukcję z ROM

Bieżąca wartość komputera służy do pobrania odpowiedniej instrukcji z pamięci ROM. Każda instrukcja ma jeden kod operacji i trzy operandy. Każdy operand składa się z jednego słowa danych i jednego trybu adresowania. Części te są od siebie oddzielone, ponieważ są odczytywane z pamięci ROM.

Kod operacji to 4 bity, które obsługują 16 unikalnych kodów, z których 11 ma przypisane:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Zapisz wynik (jeśli to konieczne) poprzedniej instrukcji w pamięci RAM

W zależności od stanu poprzedniej instrukcji (np. Wartości pierwszego argumentu dla ruchu warunkowego), wykonywane jest zapisywanie. Adres zapisu jest określany przez trzeci argument poprzedniej instrukcji.

Należy zauważyć, że pisanie następuje po pobraniu instrukcji. Prowadzi to do utworzenia szczeliny opóźnienia rozgałęzienia, w której instrukcja natychmiast po instrukcji rozgałęzienia (każda operacja zapisująca na PC) jest wykonywana zamiast pierwszej instrukcji w miejscu docelowym rozgałęzienia.

W niektórych przypadkach (jak bezwarunkowe skoki) szczelinę opóźnienia gałęzi można zoptymalizować. W innych przypadkach nie jest to możliwe, a instrukcja po gałęzi musi pozostać pusta. Co więcej, ten typ szczeliny opóźniającej oznacza, że ​​gałęzie muszą używać celu gałęzi, który jest o 1 adres mniejszy niż rzeczywista instrukcja celu, aby uwzględnić przyrost PC.

Krótko mówiąc, ponieważ dane wyjściowe poprzedniej instrukcji są zapisywane w pamięci RAM po pobraniu kolejnej instrukcji, skoki warunkowe muszą mieć po nich pustą instrukcję, w przeciwnym razie komputer nie zostanie poprawnie zaktualizowany do skoku.

3. Przeczytaj dane dla argumentów bieżącej instrukcji z pamięci RAM

Jak wspomniano wcześniej, każdy z trzech operandów składa się zarówno ze słowa danych, jak i trybu adresowania. Słowo danych ma 16 bitów, taką samą szerokość jak pamięć RAM. Tryb adresowania to 2 bity.

Tryby adresowania mogą być źródłem znacznej złożoności dla takiego procesora, ponieważ wiele rzeczywistych trybów adresowania wymaga obliczeń wieloetapowych (takich jak dodawanie przesunięć). Jednocześnie wszechstronne tryby adresowania odgrywają ważną rolę w użyteczności procesora.

Staraliśmy się ujednolicić koncepcje używania liczb zakodowanych na stałe jako operandów i używania adresów danych jako operandów. Doprowadziło to do stworzenia opartych na licznikach trybów adresowania: tryb adresowania operandu jest po prostu liczbą reprezentującą ile razy dane powinny być wysyłane wokół pętli odczytu pamięci RAM. Obejmuje to adresowanie bezpośrednie, bezpośrednie, pośrednie i podwójnie pośrednie.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

Po wykonaniu tego dereferencji trzy operandy instrukcji mają różne role. Pierwszy argument jest zwykle pierwszym argumentem dla operatora binarnego, ale służy również jako warunek, gdy bieżąca instrukcja jest ruchem warunkowym. Drugi operand służy jako drugi argument dla operatora binarnego. Trzeci operand służy jako adres docelowy dla wyniku instrukcji.

Ponieważ dwie pierwsze instrukcje służą jako dane, a trzecia służy jako adres, tryby adresowania mają nieco inne interpretacje w zależności od miejsca, w którym są używane. Na przykład tryb bezpośredni służy do odczytu danych ze stałego adresu RAM (ponieważ potrzebny jest jeden odczyt pamięci RAM), ale tryb natychmiastowy służy do zapisywania danych na ustalonym adresie pamięci RAM (ponieważ nie są konieczne żadne odczyty pamięci RAM).

4. Oblicz wynik

Kod operacji i pierwsze dwa operandy są wysyłane do ALU w celu wykonania operacji binarnej. W przypadku operacji arytmetycznych, bitowych i shiftowych oznacza to wykonanie odpowiedniej operacji. W przypadku ruchów warunkowych oznacza to po prostu zwrócenie drugiego operandu.

Kod operacji i pierwszy operand są używane do obliczania warunku, który określa, czy zapisać wynik w pamięci. W przypadku ruchów warunkowych oznacza to albo ustalenie, czy dowolny bit w operandzie ma wartość 1 (dla MNZ), czy ustalenie, czy bit znaku ma wartość 1 (dla MLZ). Jeśli kod operacji nie jest ruchem warunkowym, zapis jest zawsze wykonywany (warunek jest zawsze spełniony).

5. Zwiększ licznik programu

Na koniec licznik programu jest odczytywany, zwiększany i zapisywany.

Ze względu na położenie przyrostu PC między odczytem instrukcji a zapisem instrukcji, oznacza to, że instrukcja, która zwiększa PC o 1, nie działa. Instrukcja, która kopiuje komputer do siebie, powoduje wykonanie następnej instrukcji dwa razy z rzędu. Ale ostrzegamy, że wiele instrukcji na PC z rzędu może powodować złożone efekty, w tym nieskończoną pętlę, jeśli nie zwrócisz uwagi na potok instrukcji.

Wyprawa po zgromadzenie Tetris

Dla naszego procesora stworzyliśmy nowy język asemblera o nazwie QFTASM. Ten język asemblera odpowiada 1 do 1 kodowi maszynowemu w pamięci ROM komputera.

Każdy program QFTASM jest zapisywany jako seria instrukcji, po jednej w wierszu. Każda linia jest sformatowana w następujący sposób:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Lista kodów operacyjnych

Jak wspomniano wcześniej, istnieje 11 kodów operacyjnych obsługiwanych przez komputer, z których każdy ma trzy argumenty:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Tryby adresowania

Każdy z operandów zawiera zarówno wartość danych, jak i ruch adresowania. Wartość danych jest opisana liczbą dziesiętną z zakresu od -32768 do 32767. Tryb adresowania jest opisany jednuliterowym przedrostkiem wartości danych.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Przykładowy kod

Sekwencja Fibonacciego w pięciu wierszach:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Ten kod oblicza sekwencję Fibonacciego z adresem RAM 1 zawierającym bieżący termin. Szybko przelewa się po 28657.

Szary kod:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Ten program oblicza kod Graya i przechowuje kod pod kolejnymi adresami, zaczynając od adresu 5. Ten program wykorzystuje kilka ważnych funkcji, takich jak adresowanie pośrednie i skok warunkowy. Zatrzymuje się, gdy powstanie wynikowy kod Graya 101010, co dzieje się dla wejścia 51 pod adresem 56.

Tłumacz online

El'endia Starman stworzył bardzo przydatnych tłumacza online, tutaj . Jesteś w stanie przechodzić przez kod, ustawiać punkty przerwania, wykonywać ręczne zapisy w pamięci RAM i wizualizować pamięć RAM jako wyświetlacz.

Cogol

Po zdefiniowaniu architektury i języka asemblera, następnym krokiem po stronie „oprogramowania” projektu było stworzenie języka wyższego poziomu, coś odpowiedniego dla Tetris. W ten sposób stworzyłem Cogola . Nazwa ta jest zarówno słowem „COBOL”, jak i akronimem „C of Game of Life”, chociaż warto zauważyć, że Cogol jest dla C tym, czym jest nasz komputer dla rzeczywistego komputera.

Cogol istnieje na poziomie nieco powyżej języka asemblera. Zasadniczo większość linii w programie Cogol odpowiada jednej linii asemblera, ale istnieją pewne ważne cechy języka:

• Podstawowe funkcje obejmują nazwane zmienne z przypisaniami i operatory, które mają bardziej czytelną składnię. Na przykład ADD A1 A2 3staje się z = x + y;ze zmiennymi mapowania kompilatora na adresy.
• Pętle konstrukcje, takie jak if(){}, while(){}i do{}while();kompilator obsługuje rozgałęzienia.
• Tablice jednowymiarowe (ze wskaźnikiem arytmetycznym), które są używane na płycie Tetris.
• Podprogramy i stos wywołań. Są one przydatne do zapobiegania powielaniu dużych fragmentów kodu oraz do obsługi rekurencji.

Kompilator (który napisałem od zera) jest bardzo prosty / naiwny, ale próbowałem ręcznie zoptymalizować niektóre konstrukcje językowe, aby uzyskać krótką długość kompilowanego programu.

Oto kilka krótkich omówień działania różnych funkcji językowych:

Tokenizacja

Kod źródłowy jest tokenizowany liniowo (jednoprzebiegowy), przy użyciu prostych reguł, które znaki mogą przylegać do tokena. Kiedy napotyka się postać, która nie może przylegać do ostatniego znaku bieżącego żetonu, aktualny żeton uznaje się za ukończony, a nowa postać rozpoczyna nowy żeton. Niektóre postacie (takie jak {lub ,) nie mogą sąsiadować z żadnymi innymi postaciami i dlatego są ich własnymi żetonami. Inne (jak >lub =) są dozwolone tylko być obok innych znaków w swojej klasie, a może zatem stanowić znaki takie jak >>>, ==lub >=, ale nie podoba =2. Znaki białych znaków wymuszają granicę między tokenami, ale same nie są uwzględniane w wyniku. Najtrudniejszą postacią do tokenizacji jest- ponieważ może zarówno reprezentować odejmowanie, jak i jednoargumentową negację, a zatem wymaga specjalnej obudowy.

Rozbiór gramatyczny zdania

Parsowanie odbywa się również w trybie jednoprzebiegowym. Kompilator ma metody obsługi każdej z różnych konstrukcji języka, a tokeny są usuwane z globalnej listy tokenów, ponieważ są wykorzystywane przez różne metody kompilatora. Jeśli kompilator kiedykolwiek zobaczy token, którego się nie spodziewa, zgłosi błąd składniowy.

Globalna alokacja pamięci

Kompilator przypisuje każdej zmiennej globalnej (słowu lub tablicy) swój własny wyznaczony adres (adresy) RAM. Konieczne jest zadeklarowanie wszystkich zmiennych za pomocą słowa kluczowego, myaby kompilator wiedział, aby przydzielić dla niego miejsce. Znacznie fajniejsze niż nazwane zmienne globalne jest zarządzanie pamięcią adresu zera. Wiele instrukcji (zwłaszcza warunki warunkowe i wiele dostępów do tablicy) wymaga tymczasowych adresów „scratch” do przechowywania pośrednich obliczeń. Podczas procesu kompilacji kompilator przydziela i przydziela adresy scratch w razie potrzeby. Jeśli kompilator potrzebuje więcej adresów scratch, poświęci więcej pamięci RAM jako adresy scratch. Uważam, że to typowe, że program wymaga tylko kilku adresów scratch, chociaż każdy adres scratch będzie używany wiele razy.

IF-ELSE Sprawozdania

Składnia if-elseinstrukcji jest standardową formą C:

other code
if (cond) {
  first body
} else {
  second body
}
other code

Po przekonwertowaniu na QFTASM kod jest zorganizowany w następujący sposób:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Jeśli pierwsze ciało zostanie wykonane, drugie ciało zostanie pominięte. Jeśli pierwsze ciało zostanie pominięte, drugie ciało zostanie wykonane.

W złożeniu test warunków jest zwykle tylko odejmowaniem, a znak wyniku określa, czy wykonać skok, czy wykonać ciało. MLZInstrukcja jest używana do obsługi takich jak nierówności >lub <=. Do MNZobsługi używana jest instrukcja ==, ponieważ przeskakuje ona nad ciałem, gdy różnica nie jest równa zero (a zatem gdy argumenty nie są równe). Warunki warunkowe z wieloma wyrażeniami nie są obecnie obsługiwane.

Jeśli elseinstrukcja zostanie pominięta, pominięty zostanie również skok bezwarunkowy, a kod QFTASM wygląda następująco:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Sprawozdania

Składnia whileinstrukcji jest również standardową formą C:

other code
while (cond) {
  body
}
other code

Po przekonwertowaniu na QFTASM kod jest zorganizowany w następujący sposób:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

Testowanie warunków i skok warunkowy znajdują się na końcu bloku, co oznacza, że ​​są one ponownie wykonywane po każdym wykonaniu bloku. Gdy warunek jest zwracany jako false, ciało nie jest powtarzane, a pętla kończy się. Na początku wykonywania pętli przepływ sterowania przeskakuje nad korpusem pętli do kodu warunku, więc ciało nigdy nie jest wykonywane, jeśli warunek jest za pierwszym razem fałszywy.

MLZInstrukcja jest używana do obsługi takich jak nierówności >lub <=. W przeciwieństwie do ifinstrukcji, do MNZobsługi używana jest instrukcja !=, ponieważ przeskakuje ona do ciała, gdy różnica nie jest równa zero (a zatem gdy argumenty nie są równe).

DO-WHILE Sprawozdania

Jedyna różnica między whilei do-whilepolega na tym, że do-whileciało pętli nie jest początkowo pomijane, więc zawsze jest wykonywane przynajmniej raz. Zazwyczaj używam do-whileinstrukcji, aby zapisać kilka wierszy kodu asemblera, gdy wiem, że pętla nigdy nie będzie musiała zostać całkowicie pominięta.

Tablice

Tablice jednowymiarowe są implementowane jako ciągłe bloki pamięci. Wszystkie tablice mają stałą długość na podstawie deklaracji. Tablice są deklarowane w następujący sposób:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

W przypadku tablicy jest to możliwe mapowanie pamięci RAM, pokazujące, w jaki sposób adresy 15-18 są zarezerwowane dla tablicy:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

Adres oznaczony alphajest wypełniony wskaźnikiem położenia alpha[0], więc w tym przypadku adres 15 zawiera wartość 16. alphaZmiennej można użyć wewnątrz kodu Cogola, być może jako wskaźnik stosu, jeśli chcesz użyć tej tablicy jako stosu .

Dostęp do elementów tablicy odbywa się za pomocą standardowej array[index]notacji. Jeśli wartość indexjest stała, to odwołanie jest automatycznie wypełniane bezwzględnym adresem tego elementu. W przeciwnym razie wykonuje pewną arytmetykę wskaźnika (tylko dodanie), aby znaleźć pożądany adres bezwzględny. Można również zagnieżdżać indeksowanie, takie jak alpha[beta[1]].

Podprogramy i połączenia

Podprogramy to bloki kodu, które można wywoływać z wielu kontekstów, zapobiegając powielaniu kodu i umożliwiając tworzenie programów rekurencyjnych. Oto program z rekurencyjnym podprogramem do generowania liczb Fibonacciego (w zasadzie najwolniejszy algorytm):

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Podprogram jest deklarowany za pomocą słowa kluczowego sub, a podprogram można umieścić w dowolnym miejscu w programie. Każdy podprogram może mieć wiele zmiennych lokalnych, które są zadeklarowane jako część listy argumentów. Argumentom tym można również nadać wartości domyślne.

Aby obsłużyć wywołania rekurencyjne, lokalne zmienne podprogramu są przechowywane na stosie. Ostatnią zmienną statyczną w pamięci RAM jest wskaźnik stosu wywołań, a cała pamięć później służy jako stos wywołań. Wywołanie podprogramu powoduje utworzenie nowej ramki na stosie wywołań, która zawiera wszystkie zmienne lokalne, a także adres zwrotny (ROM). Każda podprogram w programie ma jeden statyczny adres RAM, który służy jako wskaźnik. Ten wskaźnik podaje lokalizację „bieżącego” wywołania podprogramu na stosie wywołań. Odwołanie do zmiennej lokalnej odbywa się za pomocą wartości tego statycznego wskaźnika plus przesunięcia, aby podać adres tej konkretnej zmiennej lokalnej. W stosie wywołań znajduje się również poprzednia wartość wskaźnika statycznego. Tutaj'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

Ciekawą rzeczą w podprogramach jest to, że nie zwracają one żadnej konkretnej wartości. Zamiast tego wszystkie lokalne zmienne podprogramu można odczytać po wykonaniu podprogramu, dzięki czemu można wywołać różnorodne dane z wywołania podprogramu. Odbywa się to poprzez przechowywanie wskaźnika dla tego konkretnego wywołania podprogramu, którego można następnie użyć do odzyskania dowolnych zmiennych lokalnych z ramki (ostatnio zwolnionego) stosu.

Istnieje wiele sposobów wywoływania podprogramu, wszystkie za pomocą callsłowa kluczowego:

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

Dowolną liczbę wartości można podać jako argumenty wywołania podprogramu. Każdy niedostarczony argument zostanie wypełniony wartością domyślną, jeśli taka istnieje. Argument, który nie został podany i nie ma wartości domyślnej, nie jest usuwany (aby zaoszczędzić instrukcje / czas), więc może potencjalnie przyjąć dowolną wartość na początku podprogramu.

Wskaźniki są sposobem na uzyskanie dostępu do wielu lokalnych zmiennych podprogramu, chociaż należy zauważyć, że wskaźnik jest tylko tymczasowy: dane, na które wskazuje wskaźnik, zostaną zniszczone, gdy zostanie wykonane inne wywołanie podprogramu.

Debugowanie etykiet

Każdy {...}blok kodu w programie Cogol może być poprzedzony wielowątkową etykietą opisową. Ta etykieta jest dołączona jako komentarz do skompilowanego kodu zestawu i może być bardzo przydatna do debugowania, ponieważ ułatwia zlokalizowanie określonych fragmentów kodu.

Optymalizacja czasu opóźnienia gałęzi

Aby poprawić szybkość skompilowanego kodu, kompilator Cogol wykonuje naprawdę podstawową optymalizację szczeliny opóźnienia jako końcowe przejście przez kod QFTASM. W przypadku dowolnego bezwarunkowego skoku z pustym miejscem na opóźnienie gałęzi, miejsce na opóźnienie można wypełnić pierwszą instrukcją w miejscu docelowym skoku, a miejsce docelowe skoku jest zwiększane o jeden, aby wskazać kolejną instrukcję. Generalnie oszczędza to jeden cykl za każdym razem, gdy wykonywany jest bezwarunkowy skok.

Pisanie kodu Tetris w Cogol

Ostateczny program Tetris został napisany w Cogolu, a kod źródłowy jest dostępny tutaj . Skompilowany kod QFTASM jest dostępny tutaj . Dla wygody dostępny jest bezpośredni link : Tetris w QFTASM . Ponieważ celem było sprawdzenie kodu asemblera (nie kodu Cogola), wynikowy kod Cogola jest nieporęczny. Wiele części programu normalnie znajdowałoby się w podprogramach, ale te podprogramy były w rzeczywistości na tyle krótkie, że powielenie kodu zachowało instrukcje przezcallsprawozdania. Kod końcowy ma tylko jeden podprogram oprócz kodu głównego. Dodatkowo wiele tablic zostało usuniętych i zastąpionych albo równo długą listą poszczególnych zmiennych, albo wieloma zakodowanymi liczbami w programie. Ostateczny skompilowany kod QFTASM zawiera mniej niż 300 instrukcji, chociaż jest tylko nieznacznie dłuższy niż samo źródło Cogol.

Część 5: Zgromadzenie, tłumaczenie i przyszłość

Dzięki naszemu programowi asemblera z kompilatora nadszedł czas na skompletowanie pamięci ROM dla komputera Varlife i przetłumaczenie wszystkiego na duży wzorzec GoL!

montaż

Składanie programu asemblującego w ROM odbywa się w podobny sposób jak w tradycyjnym programowaniu: każda instrukcja jest tłumaczona na binarny odpowiednik, a następnie są one łączone w duży binarny obiekt blob, który nazywamy plikiem wykonywalnym. Dla nas jedyną różnicą jest to, że binarny obiekt blob musi zostać przetłumaczony na obwody Varlife i podłączony do komputera.

K Zhang napisał CreateROM.py , skrypt Pythona dla Golly, który wykonuje montaż i tłumaczenie. Jest to dość proste: pobiera ze schowka program asemblujący, składa go w plik binarny i przekształca ten plik binarny na zespół obwodów. Oto przykład z prostym testerem pierwotności dołączonym do skryptu:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Daje to następujący plik binarny:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

Po przetłumaczeniu na obwody Varlife wygląda to tak:

ROM jest następnie łączony z komputerem, który tworzy w pełni funkcjonalny program w Varlife. Ale jeszcze nie skończyliśmy ...

Tłumaczenie na Game of Life

Przez cały ten czas pracowaliśmy nad różnymi warstwami abstrakcji powyżej podstawy Gry Życia. Ale teraz nadszedł czas, aby odsunąć zasłonę abstrakcji i przełożyć naszą pracę na wzór Gry Życia. Jak wspomniano wcześniej, używamy OTCA Metapixel jako podstawy dla Varlife. Ostatnim krokiem jest konwersja każdej komórki w Varlife na metapiksel w Game of Life.

Na szczęście Golly jest wyposażony w skrypt ( metafier.py ), który może konwertować wzorce z różnych zestawów reguł na wzorce Game of Life za pośrednictwem OTCA Metapixel. Niestety, jest on przeznaczony tylko do konwersji wzorców za pomocą jednego globalnego zestawu reguł, więc nie działa w Varlife. Napisałem zmodyfikowaną wersję, która rozwiązuje ten problem, dzięki czemu reguła dla każdej metapikseli jest generowana dla poszczególnych komórek dla Varlife.

Tak więc nasz komputer (z Tetris ROM) ma ramkę graniczną 1436 x 5 082. Z 7 297 752 komórek w tym pudełku 6 075 811 to puste miejsca, pozostawiając faktyczną liczbę populacji 1 221 941. Każda z tych komórek musi zostać przetłumaczona na metapiksel OTCA, który ma ramkę graniczną 2048 x 2048 i populację 64 691 (dla metapikseli ON) lub 23 920 (dla metapikseli OFF). Oznacza to, że produkt końcowy będzie miał obwiednię o wymiarach 2940928 x 10 409 936 (plus kilka tysięcy dodatkowych na obramowanie metapikseli), z populacją między 29 228 882 720 i 79 048 585 2531. Z 1 bitem na komórkę na żywo, potrzeba od 27 do 74 GiB do reprezentowania całego komputera i pamięci ROM.

Uwzględniłem tutaj te obliczenia, ponieważ zaniedbałem ich uruchomienie przed uruchomieniem skryptu i bardzo szybko zabrakło mi pamięci na komputerze. Po spanikowanym killpoleceniu zmodyfikowałem skrypt metafiera. Co 10 linii metapikseli wzór jest zapisywany na dysku (jako plik RLE spakowany gzipem), a siatka jest opróżniana. Dodaje to dodatkowe środowisko wykonawcze do tłumaczenia i zużywa więcej miejsca na dysku, ale utrzymuje zużycie pamięci w dopuszczalnych granicach. Ponieważ Golly korzysta z rozszerzonego formatu RLE, który obejmuje lokalizację wzorca, nie powoduje to żadnych komplikacji przy ładowaniu wzorca - wystarczy otworzyć wszystkie pliki wzorców na tej samej warstwie.

K Zhang opracował tę pracę i stworzył wydajniejszy skrypt metafierowy, który wykorzystuje format pliku MacroCell, który jest ładowany bardziej wydajnie niż RLE w przypadku dużych wzorców. Ten skrypt działa znacznie szybciej (kilka sekund, w porównaniu do wielu godzin w przypadku oryginalnego skryptu metafierowego), tworzy znacznie mniejsze dane wyjściowe (121 KB w porównaniu do 1,7 GB) i może metafiować cały komputer i pamięć ROM jednym zamachem bez użycia ogromnej ilości pamięciowy. Wykorzystuje fakt, że pliki MacroCell kodują drzewa opisujące wzorce. Za pomocą niestandardowego pliku szablonu metapiksele są wstępnie ładowane do drzewa, a po niektórych obliczeniach i modyfikacjach w celu wykrywania sąsiadów można po prostu dołączyć wzór Varlife.

Plik wzorców całego komputera i pamięci ROM w Game of Life można znaleźć tutaj .

Przyszłość projektu

Teraz, kiedy stworzyliśmy Tetris, skończyliśmy, prawda? Nawet nie blisko. Mamy jeszcze kilka celów dla tego projektu, nad którymi pracujemy:

• muddyfish i Kritixi Lithos kontynuują prace nad językiem wyższego poziomu, który jest kompilowany do QFTASM.
• El'endia Starman pracuje nad aktualizacjami internetowego tłumacza QFTASM.
• quartata pracuje nad backendem GCC, który umożliwi kompilację wolnostojącego kodu C i C ++ (i potencjalnie innych języków, takich jak Fortran, D lub Objective-C) do QFTASM przez GCC. Umożliwi to tworzenie bardziej wyrafinowanych programów w bardziej znanym języku, choć bez standardowej biblioteki.
• Jedną z największych przeszkód, które musimy pokonać, aby osiągnąć większy postęp, jest fakt, że nasze narzędzia nie mogą emitować kodu niezależnego od pozycji (np. Skoki względne). Bez PIC nie możemy wykonać żadnego łączenia, dlatego tracimy korzyści wynikające z możliwości łączenia się z istniejącymi bibliotekami. Pracujemy nad tym, aby znaleźć sposób na poprawne wykonanie PIC.
• Omawiamy kolejny program, który chcemy napisać dla komputera QFT. W tej chwili Pong wygląda na fajny cel.

Część 6: Nowszy kompilator do QFTASM

Chociaż Cogol jest wystarczający do podstawowej implementacji Tetris, jest on zbyt prosty i zbyt niski dla programowania ogólnego przeznaczenia na poziomie łatwym do odczytania. Prace nad nowym językiem rozpoczęliśmy we wrześniu 2016 r. Postępy w tym języku były powolne z powodu trudnych do zrozumienia błędów oraz prawdziwego życia.

Zbudowaliśmy język niskiego poziomu o podobnej składni do Pythona, w tym prosty system typów, podprogramy obsługujące rekurencję i wbudowane operatory. Kompilator z tekstu do QFTASM został utworzony w 4 krokach: tokeniser, drzewo gramatyki, kompilator wysokiego poziomu i kompilator niskiego poziomu.

Tokeniser

Programowanie rozpoczęto przy użyciu Pythona przy użyciu wbudowanej biblioteki tokeniserów, co oznacza, że ​​ten krok był dość prosty. Wymaganych było tylko kilka zmian domyślnego wyjścia, w tym usuwanie komentarzy (ale nie #includes).

Drzewo gramatyczne

Drzewo gramatyki zostało utworzone w taki sposób, aby można je było łatwo rozszerzać bez konieczności modyfikowania kodu źródłowego.

Struktura drzewa jest przechowywana w pliku XML, który zawiera strukturę węzłów, które mogą tworzyć drzewo, oraz sposób, w jaki są one tworzone z innymi węzłami i tokenami.

Gramatyka potrzebna do obsługi zarówno powtarzających się, jak i opcjonalnych węzłów. Osiągnięto to poprzez wprowadzenie metatagów opisujących sposób odczytywania tokenów.

Generowane tokeny są następnie analizowane zgodnie z regułami gramatyki, tak aby dane wyjściowe tworzyły drzewo elementów gramatycznych, takich jak subs igeneric_variables które z kolei zawierają inne elementy gramatyczne i tokeny.

Kompilacja w kod wysokiego poziomu

Każda funkcja języka musi być możliwa do skompilowania w konstrukcje wysokiego poziomu. Należą do nich assign(a, 12) i call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Funkcje takie jak wstawianie elementów są wykonywane w tym segmencie. Są one zdefiniowane jako operators i wyróżniają się tym, że są wstawiane za każdym razem, gdy operator taki jak +lub% używany . Z tego powodu są bardziej ograniczone niż zwykły kod - nie mogą używać własnego operatora ani żadnego operatora, który polega na tym, który jest definiowany.

Podczas procesu wstawiania zmienne wewnętrzne są zastępowane zmiennymi wywoływanymi. To faktycznie się zmienia

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

w

int i = __ADD__(3, 3)

Takie zachowanie może jednak być szkodliwe i podatne na błędy, jeśli zmienna wejściowa i zmienna wyjściowa wskazują na to samo miejsce w pamięci. Aby użyć zachowania „bezpieczniejszego”, unsafesłowo kluczowe dostosowuje proces kompilacji w taki sposób, że dodatkowe zmienne są tworzone i kopiowane do i z wbudowanego w razie potrzeby.

Zmienne zadrapania i złożone operacje

Operacje matematyczne, a += (b + c) * 4których nie można obliczyć bez użycia dodatkowych komórek pamięci. Kompilator wysokiego poziomu radzi sobie z tym, dzieląc operacje na różne sekcje:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Wprowadza to pojęcie zmiennych rysujących, które są używane do przechowywania pośrednich informacji obliczeniowych. Są one przydzielane zgodnie z wymaganiami i po zakończeniu przydzielane do ogólnej puli. Zmniejsza to liczbę lokalizacji pamięci scratch wymaganych do użycia. Zmienne zarysowania są uważane za globalne.

Każdy podprogram ma swój własny sklep VariableStore, który przechowuje odwołanie do wszystkich zmiennych używanych przez podprogram, a także ich typu. Pod koniec kompilacji są one tłumaczone na względne przesunięcia od początku sklepu, a następnie podane rzeczywiste adresy w pamięci RAM.

Struktura pamięci RAM

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Kompilacja niskiego poziomu

Jedyne rzeczy kompilator niski poziom ma do czynienia są sub, call_sub, return, assign, ifi while. To znacznie zredukowana lista zadań, które można łatwiej przetłumaczyć na instrukcje QFTASM.

sub

To lokalizuje początek i koniec podanego podprogramu. Kompilator niskiego poziomu dodaje etykiety, aw przypadku mainpodprogramu dodaje instrukcję wyjścia (przejście do końca ROM).

if i while

Zarówno tłumacze, jak whilei tłumacze ifniskiego poziomu są dość prosta: otrzymują wskaźniki do warunków i skaczą w zależności od nich. whilePętle różnią się nieco tym, że są kompilowane jako

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub i return

W przeciwieństwie do większości architektur komputer, dla którego kompilujemy, nie obsługuje sprzętu do wypychania i wyskakiwania ze stosu. Oznacza to, że zarówno wypychanie, jak i wyskakiwanie ze stosu wymaga dwóch instrukcji. W przypadku wyskakiwania zmniejszamy wskaźnik stosu i kopiujemy wartość na adres. W przypadku wypychania kopiujemy wartość z adresu na adres pod bieżącym wskaźnikiem stosu, a następnie zwiększamy.

Wszystkie ustawienia lokalne dla podprogramu są przechowywane w stałej lokalizacji w pamięci RAM określonej w czasie kompilacji. Aby rekurencja działała, wszystkie ustawienia lokalne funkcji są umieszczane na stosie na początku wywołania. Następnie argumenty podprogramu są kopiowane do ich pozycji w lokalnym sklepie. Wartość adresu zwrotnego jest umieszczana na stosie i wykonuje się podprogram.

Po returnnapotkaniu instrukcji górna część stosu jest usuwana, a licznik programu jest ustawiany na tę wartość. Wartości dla miejscowych podprogramu wywołującego są wyskakujące ze stosu i na ich poprzednią pozycję.

assign

Przypisania zmiennych są najłatwiejszymi rzeczami do skompilowania: biorą zmienną i wartość i kompilują w jednym wierszu: MLZ -1 VALUE VARIABLE

Przypisywanie celów skoku

Na koniec kompilator opracowuje skoki docelowe dla etykiet dołączonych do instrukcji. Określane jest bezwzględne położenie etykiet, a następnie odniesienia do tych etykiet są zastępowane tymi wartościami. Same etykiety są usuwane z kodu, a na końcu dodawane są numery instrukcji do skompilowanego kodu.

Przykładowa kompilacja krok po kroku

Teraz, gdy przeszliśmy przez wszystkie etapy, przejdźmy krok po kroku przez proces kompilacji rzeczywistego programu.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, dość proste. To powinno być oczywiste, że po zakończeniu programu a = 8, b = 12, c = 96. Po pierwsze, uwzględnijmy odpowiednie części stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, nieco bardziej skomplikowane. Przejdźmy do tokenisera i zobaczmy, co wyjdzie. Na tym etapie będziemy mieć tylko liniowy przepływ tokenów bez jakiejkolwiek struktury

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Teraz wszystkie tokeny przechodzą przez parser gramatyki i generują drzewo z nazwami poszczególnych sekcji. Pokazuje strukturę wysokiego poziomu odczytaną przez kod.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

To drzewo gramatyki konfiguruje informacje do przeanalizowania przez kompilator wysokiego poziomu. Zawiera informacje, takie jak typy struktur i atrybuty zmiennej. Drzewo gramatyki następnie pobiera te informacje i przypisuje zmienne potrzebne do podprogramów. Drzewo wstawia również wszystkie wstawki.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Następnie kompilator niskiego poziomu musi przekonwertować tę reprezentację wysokiego poziomu na kod QFTASM. Zmienne mają przypisane lokalizacje w pamięci RAM, takie jak:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

Proste instrukcje są następnie kompilowane. Na koniec dodaje się numery instrukcji, co powoduje wykonanie kodu QFTASM.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

Składnia

Teraz, gdy mamy już goły język, musimy napisać w nim mały program. Używamy wcięć, takich jak Python, dzieląc logiczne bloki i kontrolując przepływ. Oznacza to, że białe znaki są ważne dla naszych programów. Każdy pełny program ma mainpodprogram, który działa tak jakmain() funkcja w językach C. Funkcja jest uruchamiana na początku programu.

Zmienne i typy

Kiedy zmienne są definiowane po raz pierwszy, muszą być powiązane z typem. Aktualnie zdefiniowane typy to intibool ze składni dla tablic zdefiniowane, ale nie kompilatora.

Biblioteki i operatory

Dostępna jest biblioteka o nazwie, stdint.txtktóra definiuje podstawowe operatory. Jeśli nie zostanie to uwzględnione, nawet proste operatory nie zostaną zdefiniowane. Możemy używać tej biblioteki z #include stdint. stdintdefiniuje operatorów takich jak +, >>a nawet *i% żaden z nich nie jest bezpośrednim kodem operacyjnym QFTASM.

Język umożliwia także bezpośrednie wywoływanie kodów QFTASM __OPCODENAME__.

Dodawanie w stdintjest zdefiniowane jako

operator (int a + int b) -> int
    return __ADD__(a, b)

Który określa, co +robi operator, gdy podano dwa ints.