Komputer małego człowieka - Little man computer

Little Man Computer ( LMC ) jest instruktażowe modelu z komputerem , stworzony przez dr Stuart analizy Madnicka w 1965 LMC jest powszechnie stosowany do studentów uczyć, ponieważ modelom prosty Architektura von Neumanna komputer, który posiada wszystkie podstawowe funkcje nowoczesnego komputera. Można go zaprogramować w kodzie maszynowym (choć raczej w postaci dziesiętnej niż binarnej) lub w kodzie asemblera.

Model LMC opiera się na koncepcji małego człowieczka zamkniętego w zamkniętej sali pocztowej (analogicznie do komputera w tym scenariuszu). Na jednym końcu pomieszczenia znajduje się 100 skrzynek pocztowych ( pamięć ), ponumerowanych od 0 do 99, z których każda może zawierać 3-cyfrową instrukcję lub dane (w zakresie od 000 do 999). Ponadto na drugim końcu znajdują się dwie skrzynki pocztowe oznaczone INBOX i OUTBOX, które służą do odbierania i wysyłania danych. Na środku pokoju znajduje się obszar roboczy zawierający prosty dwufunkcyjny kalkulator (dodawanie i odejmowanie) zwany akumulatorem oraz resetowalny licznik zwany licznikiem programu. W Liczniku Programów znajduje się adres następnej instrukcji, którą Mały Człowieczek wykona. Ten licznik programu jest zwykle zwiększany o 1 po wykonaniu każdej instrukcji, umożliwiając Małemu Człowiekowi sekwencyjną pracę z programem. Instrukcje rozgałęzienia umożliwiają włączenie do programu iteracji (pętli) i struktur programowania warunkowego . To ostatnie osiąga się przez ustawienie licznika programu na niesekwencyjny adres pamięci, jeśli spełniony jest określony warunek (zazwyczaj wartość przechowywana w akumulatorze jest zerowa lub dodatnia).

Zgodnie z architekturą von Neumanna każda skrzynka pocztowa (oznaczająca unikalną lokalizację w pamięci) może zawierać instrukcję lub dane. Dlatego należy uważać, aby licznik programu nie dotarł do adresu pamięci zawierającego dane - w przeciwnym razie Mały Człowiek spróbuje potraktować to jako instrukcję. Można to wykorzystać, pisząc instrukcje do skrzynek pocztowych, które mają być interpretowane jako kod, aby stworzyć samomodyfikujący się kod. Aby skorzystać z LMC, użytkownik ładuje dane do skrzynek pocztowych, a następnie sygnalizuje Małemu Człowiekowi rozpoczęcie wykonywania, zaczynając od instrukcji przechowywanej pod adresem zerowym pamięci. Zresetowanie licznika programu do zera skutecznie ponownie uruchamia program, chociaż w potencjalnie innym stanie.

Cykl wykonania

Zobacz też: Cykl instrukcji

Aby wykonać program, mały człowiek wykonuje następujące kroki:

  1. Sprawdź licznik programu dla numeru skrzynki pocztowej, która zawiera instrukcję programu (tj. zero na początku programu)
  2. Pobierz instrukcję ze skrzynki pocztowej o tym numerze. Każda instrukcja zawiera dwa pola: kod operacyjny (wskazujący operację do wykonania) oraz pole adresowe (wskazujące, gdzie znaleźć dane do wykonania operacji).
  3. Zwiększ licznik programu (tak, aby zawierał numer skrzynki pocztowej następnej instrukcji)
  4. Odszyfruj instrukcję. Jeżeli dyspozycja korzysta z danych zapisanych w innej skrzynce to w polu adresowym odszukaj numer skrzynki dla danych, na których będzie działać, np. 'pobierz dane ze skrzynki 42')
  5. Pobierz dane (z wejścia, akumulatora lub skrzynki pocztowej o adresie określonym w kroku 4)
  6. Wykonaj instrukcję na podstawie podanego kodu operacyjnego
  7. Rozdziel lub zapisz wynik (w wyjściu, akumulatorze lub skrzynce pocztowej pod adresem określonym w kroku 4)
  8. Wróć do licznika programu, aby powtórzyć cykl lub zatrzymać

Polecenia

Chociaż LMC odzwierciedla rzeczywiste działanie procesorów binarnych , wybrano prostotę liczb dziesiętnych, aby zminimalizować złożoność dla uczniów, którzy mogą nie czuć się komfortowo w pracy w trybie binarnym/ szesnastkowym .

Instrukcje

Niektóre symulatory LMC są programowane bezpośrednio przy użyciu 3-cyfrowych instrukcji numerycznych, a niektóre używają 3-literowych kodów mnemonicznych i etykiet. W obu przypadkach zestaw instrukcji jest celowo bardzo ograniczony ( zazwyczaj około dziesięciu instrukcji ), aby ułatwić zrozumienie. Jeśli LKM używa kodów mnemonicznych i etykiet, to podczas tworzenia programu są one konwertowane na 3-cyfrowe instrukcje numeryczne.

Poniższa tabela przedstawia typowy zestaw instrukcji numerycznych i odpowiadające im kody mnemoniczne.

Instrukcje
Kod numeryczny Kod mnemoniczny Instrukcja Opis
1xx DODAJ DODAJ Dodaj wartość przechowywaną w skrzynce pocztowej xx do dowolnej wartości aktualnie znajdującej się w akumulatorze (kalkulatorze).
Uwaga: zawartość skrzynki nie jest zmieniana, a działania akumulatora (kalkulatora) nie są zdefiniowane dla instrukcji dodawania, które powodują sumy większe niż 3 cyfry. Podobnie jak w przypadku SUBTRACT, można było ustawić flagę ujemną na przepełnienie.
2xx POD ODEJMOWAĆ Odejmij wartość przechowywaną w skrzynce pocztowej xx od dowolnej wartości aktualnie znajdującej się w akumulatorze (kalkulatorze).
Uwaga: zawartość skrzynki nie jest zmieniana, a działania akumulatora nie są zdefiniowane dla instrukcji odejmowania, które powodują negatywne wyniki - jednak zostanie ustawiona flaga ujemna, aby można było użyć 7xx (BRZ) i 8xx (BRP) odpowiednio.
3xx STA SKLEP Przechowuj zawartość akumulatora w skrzynce pocztowej xx (destrukcyjna).
Uwaga: zawartość akumulatora (kalkulatora) nie jest zmieniana (nieniszcząca), ale zawartość skrzynki pocztowej jest zastępowana niezależnie od tego, co w niej było (niszcząca)
5xx LDA ZAŁADUJ Załaduj wartość ze skrzynki pocztowej xx (niedestrukcyjna) i wprowadź ją do akumulatora (destrukcyjna).
6xx BIUSTONOSZ ODDZIAŁ (bezwarunkowo) Ustaw licznik programu na podany adres (wartość xx). Oznacza to, że następną wykonywaną instrukcją będzie wartość w skrzynce pocztowej xx.
7xx BRZ ODDZIAŁ JEŻELI ZERO ( warunkowy ) Jeżeli akumulator (kalkulator) zawiera wartość 000, ustaw licznik programu na wartość xx. W przeciwnym razie nic nie rób. To, czy flaga ujemna jest brana pod uwagę, jest nieokreślone. Kiedy SUBTRACT przekracza wartość akumulatora, ta flaga jest ustawiana, po czym akumulator jest niezdefiniowany, potencjalnie zero, powodując niezdefiniowane zachowanie BRZ przy niedomiarze. Sugerowanym zachowaniem byłoby rozgałęzienie, jeśli akumulator ma wartość zero i nie jest ustawiona flaga ujemna.
Uwaga: ponieważ program jest przechowywany w pamięci, dane i instrukcje programu mają ten sam format adresu/lokalizacji.
8xx BRP ODDZIAŁ JEŚLI DODATNI (warunkowo) Jeżeli akumulator (kalkulator) jest 0 lub dodatni, ustaw licznik programu na wartość xx. W przeciwnym razie nic nie rób. Ponieważ komórki pamięci LMC mogą przechowywać tylko wartości z zakresu od 0 do 999, instrukcja ta zależy wyłącznie od ujemnej flagi ustawionej przez niedomiar na SUBTRACT i potencjalnie na przepełnienie na ADD (nieokreślony).
Uwaga: ponieważ program jest przechowywany w pamięci, dane i instrukcje programu mają ten sam format adresu/lokalizacji.
901 W P WEJŚCIE Przejdź do SKRZYNKI ODBIORCZEJ, pobierz wartość od użytkownika i umieść ją w akumulatorze (kalkulatorze)
Uwaga: spowoduje to nadpisanie dowolnej wartości w akumulatorze (destrukcyjne)
902 NA ZEWNĄTRZ WYJŚCIE Skopiuj wartość z akumulatora (kalkulatora) do OUTBOX.
Uwaga: zawartość akumulatora nie ulega zmianie (nieniszcząca).
000 HLT/COB ZATRZYMANIE/PRZERWA KAWOWA Przestań działać/zakończ program.
DAT DANE Jest to instrukcja asemblera, która po prostu ładuje wartość do następnej dostępnej skrzynki pocztowej. DAT może być również używany w połączeniu z etykietami do deklarowania zmiennych. Na przykład DAT 984 zapisze wartość 984 w skrzynce pocztowej pod adresem instrukcji DAT.

Przykłady

Korzystanie z numerycznych kodów instrukcji

Ten program (od instrukcji 901 do instrukcji 000 ) jest pisany tylko przy użyciu kodów numerycznych. Program pobiera dwie liczby jako dane wejściowe i wyprowadza różnicę. Zwróć uwagę, że wykonanie rozpoczyna się na Mailbox 00 i kończy na Mailbox 07. Wady programowania LMC przy użyciu kodów instrukcji numerycznych omówiono poniżej.

Skrzynka pocztowa Kod numeryczny Operacja Uwagi
00 901 SKRZYNKA ODBIORCZA --> AKUMULATOR WPROWADŹ pierwszą liczbę, wejdź do kalkulatora (kasując to, co tam było)
01 308 AKUMULATOR --> PAMIĘĆ[08] ZAPISZ bieżącą wartość kalkulatora (aby przygotować się do następnego kroku...)
02 901 SKRZYNKA ODBIORCZA --> AKUMULATOR WPROWADŹ drugą liczbę, wejdź do kalkulatora (kasując to, co tam było)
03 309 AKUMULATOR --> PAMIĘĆ[09] ZACHOWAJ aktualną wartość kalkulatora (ponownie, aby przygotować się do następnego kroku...)
04 508 PAMIĘĆ[08] --> AKUMULATOR (Teraz obie wartości INPUT są PRZECHOWYWANE w skrzynkach pocztowych 08 i 09...)

ZAŁADUJ pierwszą wartość z powrotem do kalkulatora (kasując to, co tam było)

05 209 AKUMULATOR = AKUMULATOR - PAMIĘĆ[09] ODEJMIJ drugą liczbę od bieżącej wartości kalkulatora (która właśnie została ustawiona na pierwszą liczbę)
06 902 AKUMULATOR --> SKRZYNKA WYJŚCIOWA WYŚLIJ wynik kalkulatora do OUTBOX
07 000 (nie wykonano żadnej operacji) ZATRZYMAJ LKM

Korzystanie z mnemotechniki i etykiet

Asembler jest językiem programowania niskiego poziomu, który używa mnemoników i etykiet zamiast numerycznych kodów instrukcji. Chociaż LMC używa tylko ograniczonego zestawu mnemoników, wygoda używania mnemotechniki dla każdej instrukcji wynika z języka asemblera tego samego programu pokazanego poniżej - programista nie musi już zapamiętywać zestawu anonimowych kodów numerycznych i może teraz zaprogramuj zestaw bardziej zapadających w pamięć kodów mnemonicznych. Jeśli mnemonik jest instrukcją, która obejmuje adres pamięci ( rozgałęzienie lub ładowanie/zapisywanie danych ), to do nazwania adresu pamięci używana jest etykieta.

Przykładowy program można skompilować i uruchomić na symulatorze LMC dostępnym na stronie York University ( Toronto , Ontario , Kanada) lub w aplikacji desktopowej autorstwa Mike'a Coley'a. Wszystkie te symulatory zawierają pełne instrukcje i przykładowe programy, asembler do konwersji kodu asemblera na kod maszynowy, interfejsy sterujące do wykonywania i monitorowania programów oraz szczegółowy opis każdej instrukcji LMC krok po kroku.
INP
STA FIRST
INP
STA SECOND
LDA FIRST
SUB SECOND
OUT
HLT
FIRST DAT
SECOND DAT

Etykiety

Bez etykiet programista jest zobowiązany do ręcznego obliczania adresów skrzynek pocztowych ( pamięci ). W przykładzie kodu numerycznego , jeśli nowa instrukcja miałaby zostać wstawiona przed ostatnią instrukcją HLT, wówczas ta instrukcja HLT przesunęłaby się z adresu 07 na adres 08 (etykietowanie adresu zaczyna się od adresu 00). Załóżmy, że użytkownik wprowadził 600 jako pierwsze wejście. Instrukcja 308 oznaczałaby, że ta wartość byłaby przechowywana pod adresem adresowym 08 i nadpisywałaby instrukcję 000 (HLT). Ponieważ 600 oznacza „odgałęzienie do adresu skrzynki pocztowej 00”, program zamiast się zatrzymać, utknął w nieskończonej pętli.

Aby obejść tę trudność, większość języków asemblera (w tym LMC ) łączy mnemoniki z etykietami . Etykieta to po prostu słowo używane do nazwania adresu pamięci, w którym przechowywane są instrukcje lub dane, lub do odniesienia się do tego adresu w instrukcji.

Po złożeniu programu:

  • Etykieta po lewej stronie mnemonika instrukcji jest konwertowana na adres pamięci, pod którym przechowywane są instrukcje lub dane. tj. loopstart INP
  • Etykieta po prawej stronie mnemonika instrukcji przyjmuje wartość adresu pamięci, o którym mowa powyżej. tj. loopstart BRA
  • Etykieta połączona z instrukcją DAT działa jako zmienna, oznacza adres pamięci, pod którą przechowywane są dane. tj. jeden DAT 1 lub numer 1 DAT

W przykładzie języka asemblerowego, który używa mnemoniki i etykiet, jeśli nowa instrukcja została wstawiona przed ostatnią instrukcją HLT wtedy adresowa lokalizacja oznaczona FIRST będzie teraz w lokalizacji pamięci 09 zamiast 08 a instrukcja STA FIRST zostanie przekonwertowana na 309 (STA 09) zamiast 308 (STA 08), kiedy program był montowany.

Etykiety są zatem używane do:

  • zidentyfikować konkretną instrukcję jako cel dla instrukcji BRANCH.
  • zidentyfikować lokalizację pamięci jako nazwaną zmienną (za pomocą DAT) i opcjonalnie załadować dane do programu w czasie asemblacji do wykorzystania przez program (to użycie nie jest oczywiste, dopóki nie uzna się, że nie ma możliwości dodania 1 do licznika. Można poproś użytkownika o wpisanie 1 na początku, ale byłoby lepiej, aby to było załadowane w momencie montażu za pomocą jednego DAT 1 )

Przykład

Poniższy program pobierze dane wprowadzone przez użytkownika i odliczy do zera. 

     INP
     OUT      // Initialize output 
LOOP BRZ QUIT // Label this memory address as LOOP. If the accumulator value is 0, jump to the memory address labeled QUIT
     SUB ONE  // Subtract the value stored at address ONE from the accumulator
     OUT
     BRA LOOP // Jump (unconditionally) to the memory address labeled LOOP
QUIT HLT      // Label this memory address as QUIT
ONE  DAT 1    // Store the value 1 in this memory address, and label it ONE (variable declaration)

Poniższy program pobierze dane wejściowe użytkownika, podniesie je do kwadratu, wypisze odpowiedź, a następnie powtórzy. Wpisanie zera kończy program.
( Uwaga: wejście, którego wynikiem jest wartość większa niż 999, będzie miało niezdefiniowane zachowanie ze względu na 3-cyfrowy limit liczby LKM ). 

START   LDA ZERO     // Initialize for multiple program run
        STA RESULT
        STA COUNT
        INP          // User provided input
        BRZ END      // Branch to program END if input = 0
        STA VALUE    // Store input as VALUE
LOOP    LDA RESULT   // Load the RESULT
        ADD VALUE    // Add VALUE, the user provided input, to RESULT
        STA RESULT   // Store the new RESULT
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        SUB VALUE    // Subtract the user provided input VALUE from COUNT
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        BRA LOOP     // Branch to LOOP to continue adding VALUE to RESULT
ENDLOOP LDA RESULT   // Load RESULT
        OUT          // Output RESULT
        BRA START    // Branch to the START to initialize and get another input VALUE
END     HLT          // HALT - a zero was entered so done!
RESULT  DAT          // Computed result (defaults to 0)
COUNT   DAT          // Counter (defaults to 0)
ONE     DAT 1        // Constant, value of 1
VALUE   DAT          // User provided input, the value to be squared (defaults to 0)
ZERO    DAT          // Constant, value of 0 (defaults to 0)

Uwaga: Jeśli po instrukcji DAT nie ma żadnych danych, w adresie pamięci przechowywana jest domyślna wartość 0.

W powyższym przykładzie [BRZ ENDLOOP] zależy od niezdefiniowanego zachowania, ponieważ WARTOŚĆ LICZNIKA może być ujemna, po czym wartość AKUMULATORA jest niezdefiniowana, co powoduje, że BRZ jest rozgałęziony lub nie (AKUMULATOR może być równy zero lub owinięty wokół). Aby kod był zgodny ze specyfikacją, zamień: 

        ...
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        SUB VALUE    // Subtract the user provided input VALUE from COUNT
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        ...

z następującą wersją, która oblicza WARTOŚĆ-LICZBA zamiast LICZBA-WARTOŚĆ, upewniając się, że akumulator nigdy nie jest niedopełniony: 

        ...
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        LDA VALUE    // Load the VALUE
        SUB COUNT    // Subtract COUNT from the user provided input VALUE
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        ...

Innym przykładem jest quine , drukujący swój własny kod maszynowy (źródło wydruku jest niemożliwe, ponieważ litery nie mogą być wyprowadzane): 

LOAD LDA 0     // Load position 0 into the accumulator. This line will be modified on each loop to load the next lines into the accumulator
     OUT       // Output the accumulator's value. The accumulator's value will be the line that was just loaded
     SUB ONE   // Subtract 1 from the value in the accumulator. This is so we can do the BRZ in the next step to see if we are on the last line in the program
     BRZ ONE   // If the previous subtraction has made the accumulator 0 (which means we had the value 001 in the accumulator), then branch to position ONE
     LDA LOAD  // Load the LOAD position into the accumulator, this is in preparation to increment the address digits for this position
     ADD ONE   // Increment the position digits for the LOAD line. The value currently in the accumulator would, if read as an instruction, load the next line into the accumulator, compared to the last line loaded
     STA LOAD  // Store the newly incremented LOAD line back in the LOAD position
     BRA LOAD  // Return to the beginning of the loop
ONE  DAT 1     // The variable ONE. If read as an instruction, this will be interpreted as HLT/COB and will end the program

Ten quine działa przy użyciu samomodyfikującego się kodu . Pozycja 0 jest zwiększana o jeden w każdej iteracji, wyprowadzając kod tej linii, aż kod, który wyprowadza, wynosi 1, w którym to punkcie rozgałęzia się do pozycji JEDEN. Wartość na pozycji ONE ma 0 jako opcode, więc jest interpretowana jako instrukcja HALT/COB.

Zobacz też

Bibliografia

Zewnętrzne linki

Symulatory

online

Inne