Politechnika Śląska wydział AEiI
WSZ kierunek Informatyka
Podstawy Informatyki - Laboratorium.
Sprawozdanie - ćw. 2: Programowanie w języku symbolicznym maszyny W.
Skład sekcji:
Jan Baranek
Witold Ossera
Krzysztof Dubrowski
Wstęp.
Ćwiczenie polegało na napisaniu kilku programów dla symulatora maszyny W. W pierwszej części
ćwiczenia korzystaliśmy ze standardowych rozkazów maszyny w architekturze W. Druga część miała na celu przećwiczenie procedur związanych z obsługą stosu, oraz napisanie kilku nieco bardziej skomplikowanych rozkazów dla architektury L.
A) Pierwsza część ćwiczenia - programowanie dla symulatora maszyny W w podstawowej architekturze.
Obliczenie iloczynu dwóch liczb naturalnych:
petla:pob zm2
ode st1
ład zm2
som wyn
pob zm1
dod wynik
ład wynik
sob petla
wyn:stop
zm1:rst 5
zm2:rst 4
st1:rst 1
wynik:rpa
Komentarz: Działanie tego programu zmienia zawartość komórki pamięci zapisanej w programie jako stała (rst). Można było tego uniknąć, ale prowadzący laboratorium zgodził się na takie uproszczenie. Samo działanie programu polega na dodawaniu do siebie zmiennej zapisanej pod etykietą zm1 tylokrotnie, ile wynosi wartość zmiennej zapisanej w zm2. Wyjście z pętli następuje, gdy wartość zmiennej zm1 jest ujemna.
Obliczenie reszty z dzielenia dwóch liczb naturalnych:
licz:pob dzielna
ode dzielnik
som reszta
ład dzielna
sob licz
reszta:pob dzielna
ład wynik //czyli reszta z dzielenia
stop
dzielna:rst 26
dzielnik:rst 7
wynik:rpa
Przedostatnie wykonanie pętli oznaczonej etykietą licz powoduje zapisanie do zmiennej oznaczonej etykietą dzielna ostatniego nieujemnego wyniku odejmowania dzielnika od dzielnej. Ta liczba jest właśnie resztą z dzielenia, zapisywaną do etykiety wynik.
Obliczenie długości tabeli zakończonej określonym znakiem.
Jako „określony znak” przyjęliśmy wartość -1, lub dowolną inną ujemną liczbę.
et1:pob tab
som koniec // sprawdzanie czy jest ujemna wartość
pob et1 // przesuwanie się po tablicy
dod st1
ład et1
pob dlugosc //zliczanie długości
dod st1
ład dlugosc
sob et1 // powrót do pętli
koniec: stop
tab: rst 1
rst 2
rst 4
rst 43
rst -1
st1 :rst 1
dlugosc: rpa
Komentarz: Przesuwanie się po elementach tablicy odbywa się za pomocą zwiększania wartości etykiety et1 o 1 w każdym obrocie pętli.. Program nie liczy ostatniego elementu (-1), gdyż uznałem że jest to tylko znacznik końca tablicy, a nie pełnoprawny element.
Wyszukiwanie maksymalnej wartości w tablicy o znanej wielkości.
et1:pob tab
ład czy
som koniec // spr. czy to już koniec tablicy
et2:pob max // etykieta tylko do powrotu z „nowe”
ode czy
som nowe //aktualny el. większy od aktualnego max - nowe max
pob et1 //4 następne linie to przechodzenie po tablicy
dod st1
ład et1
sob et1
koniec: stop
nowe: pob czy // te 3 linie kodu wywoływane są przy wykryciu nowego max
ład max
sob et2
tab: rst 1
rst 2
rst 4
rst 43
rst 11
rst 3
rst -1
czy:rpa // przechowuje „kandydata na maksimum” czyli aktualnie //sprawdzany element
max:rpa //wynik działania programu - maksymalna liczba z tablicy
st1:rst 1
Komentarz : Ogranicznik tablicy, tak jak w poprzednim programie, jest dowolną liczbą ujemną. Można zamiast tego zastosować liczenie elementów tablicy, program właściwie niewiele się zmieni.
Obliczenie liczby wystąpień określonego znaku w tablicy o określonej długości.
et1:pob tab
som koniec //sprawdzanie, czy nie koniec tablicy
ode param
som et2 //liczba była większa od parametru
ode st1
som rowne // liczba nie była mniejsza od parametru, licznik++
et2:pob et1 // przechodzenie do kolejnego elementu tablicy
dod st1 // czyli przesuwanie etykiety
ład et1
sob et1
rowne:pob ile // zwiększanie licznika znalezionych parametrów
dod st1
ład ile
sob et2
koniec:stop
tab: rst 4
rst 8
rst 4
rst 5
rst 11
rst 4
rst -1
st1 :rst 1
param: rst 8 //szukany parametr
ile:rpa //licznik szukanych parametrów
Komentarz : Tak jak w poprzednich zadaniach założyliśmy, że liczba ujemna oznacza koniec tabeli.
Obliczanie i zapisywanie wartości bezwzględnej każdego elementu tablicy o danej długości.
et1:pob tab
som ujemna //jeśli liczba jest ujemna, wykonuje się dodatkowy kod
et2:ład tab
pob dl
ode st1
som koniec // czy tablica się skończyła?
ład dl
pob et1 // przesuwanie pierwszej etykiety na kolejny element tablicy
dod st1
ład et1
pob et2 // przesuwanie drugiej etykiety na kolejny element tablicy
dod st1
ład et2
sob et1
ujemna:ład temp
ode temp
ode temp
sob et2
koniec: stop
tab: rst 4
rst 8
rst -4
rst -5
rst -11
rst 4
rst -33
st1:rst 1
dl:rst 7
temp:rpa // tu przechowywana jest ujemna zawartość komórki pamięci w czasie
// zamiany
Komentarz: Uzyskanie wartości bezwzględnej zawartości komórki wymaga sprawdzenia czy liczba ta jest ujemna. Jeśli tak, to dwukrotnie odejmujemy ją od siebie, jeśli nie to pozostawiamy liczbę dodatnią jako wartość bezwzględną. Prawdziwą trudnością w tym programie było jednoczesne przesuwanie dwu etykiet tak, by pokazywały na właśnie zamieniany element.
Zamiana parami elementów N -elementowej tablicy (N jest parzyste)
p1: pob tab
ład temp1
pob p1
dod st1
ład p2
p2: pob tab
ł1: ład tab
pob ł1
dod st1
ład ł2
pob temp1
ł2: ład tab
pob N
ode st2// każdy obrót pętli to dwa miejsca tabeli, wiec odejmujemy 2
som koniec
ład N
pob p1 // przesuwanie obu etykiet do I zamienianej liczby o 2
dod st2
ład p1
pob ł1
dod st2
ład ł1
sob p1
koniec:stop
tab: rst 1
rst 2
rst 3
rst 4
rst 5
rst 6
rst 7
rst 8
st1 :rst 1
st2: rst 2
N:rst 8
temp1:rpa
Komentarz: Etykiety p1 i p2 odpowiadają odpowiednio pobieraniu pierwszej liczby z pary i pobieraniu drugiej liczby z pary. Etykiety ł1 i ł2 oznaczają zapisywanie do pamięci odpowiednio pierwszej i drugiej liczby z pary. Algorytm zamiany jest dość prosty: wartość pierwszej zamienianej liczby zapisywana jest w elemencie temp, następnie wartość drugiej liczby jest zapisywana w miejsce pierwszej, a wartość temp zapisywana w miejsce drugiej. Etykiety pierwszej liczby są w każdym obrocie przesuwane o 2, natomiast etykiety drugiej liczby są przesuwane o 1 względem etykiety pierwszej.
Odwracanie tablicy o znanej długości.
pob p1
dod rozmiar
ode st1
ład p2
pob ł1
dod rozmiar
ode st1
ład ł2
p1:pob tab
ład temp
pob rozmiar //czy koniec
ode st2
som koniec
ład rozmiar
p2:pob tab
ł1:ład tab
pob temp
ł2:ład tab
pob p1 // przesuwanie etykiet
dod st1
ład p1
pob ł1
dod st1
ład ł1
pob p2
ode st1
ład p2
pob ł2
ode st1
ład ł2
sob p1
koniec:stop
st1:rst 1
st2:rst 2
rozmiar: rst 7
temp:rpa
tab: rst 1
rst 2
rst 3
rst 4
rst 5
rst 6
rst 7
Komentarz: W pierwszych liniach programu, przed etykietą p1, następuje ustawianie etykiet p2 i ł2 tak, by wskazywały na odpowiednie komórki pamięci, to znaczy na koniec tabeli. Odejmowanie jedynki od wartości rozmiar zapewnia, że ta odległość jest prawidłowa. Samo działanie pętli polega na zamienianiu wartości komórek pamięci pokazywanych przez etykiety z numerem 1 i 2. Przesuwanie etykiet polega na dodawaniu jedynki do tych pierwszych (przesuwanie w przód w tabeli) i odejmowaniu jedynki od tych drugich (przesuwanie w tył w tabeli).
Program w gruncie rzeczy jest bardzo podobny do poprzedniego. Działa zarówno dla parzystych jak i nieparzystych rozmiarów tablicy.
B) Druga część ćwiczenia - programowanie w rozszerzonej architekturze L, z dodatkowymi rozkazami do operowania na stosie.
Pierwszym krokiem w drugiej części ćwiczenia było zaprojektowanie dodatkowych rozkazów pozwalających na obsługę stosu przy pomocy rejestru X. Rozkazy te zostały napisane przez prowadzącego.
DNS (daj na stos)
Działanie tego rozkazu polega na zapisaniu zawartości akumulatora do komórki pamięci wskazywanej przez dekrementowaną zawartość rejestru X, czyli na szczyt stosu. Ten adres jest następnie zapisywany w rejestrze X jako nowy adres szczytu stosu.
PZS (pobierz ze stosu)
Ten rozkaz odczytuje zawartość komórki pamięci aktualnie wskazywanej przez zawartość rejestru X, czyli szczyt stosu. Wartość rejestru X następnie jest inkrementowana, tak by pokazywała na następny element stosu, a odczytana zawartość komórki pamięci trafia do AK.
SDP (skok do podprogramu)
Rozkaz zapisuje na szczycie stosu zawartość licznika w podobny sposób jak rozkaz DNS, a następnie wartość rejestru AD zapisuje do L i A (właściwy skok).
PWR (powrót z podprogramu)
To jakby odwrotność poprzedniego rozkazu. Ze szczytu stosu pobrana jest wartość licznika (rejestru L) i rejestru A. Pozostała część rozkazu przypomina zwykłe pobranie ze stosu, czyli rozkaz PZS.
Następną częścią ćwiczenia było napisanie kilku programów z wykorzystaniem powyższych rozkazów:
Obliczanie silni n!
pob st1 //0! = 1
ład wynik
p1:pob liczba
dns
sdp mnoz
pob liczba
ode st1
som koniec
ład liczba
sob p1
koniec: stop
mnoz:
pzs
ład licz
pzs
ode st1 //mnożenie wykonuje się ile+1 razy, wiec trzeba
ład ile //zmniejszać wartość ile o 1.
pob wynik // aby za każdym razem mnożyć przez tę samą liczbę.
ład temp
et1:pob ile
ode st1
som wyjdz
ład ile
pob wynik
dod temp
ład wynik
sob et1
wyjdz:
pob licz
dns
pwr
licz:rpa
temp:rpa
ile:rpa
wynik:rpa
liczba:rst 4
st1:rst 1
stos:
Komentarz: Program można było napisać bez użycia podprogramu mnożącego, a więc bez wykorzystania wszystkiego co daje użycie stosu, ale dzięki takiemu rozwiązaniu osiągnięte zostały dwie korzyści:
kod głównego programu został znacznie skrócony, oraz
kawałek kodu wykorzystany do zaimplementowania mnożenia może zostać ponownie wykorzystany w innych programach.
Działanie samego programu polega na wywoływaniu podprogramu mnoz dla kolejnych, zmniejszanych w każdym obrocie o 1 wartości liczby. Podprogram mnoz dodaje do siebie aktualny wynik działania programu tylokrotnie, ile wynosi wartość zapisana na stosie.
2. Potęgowanie Xª
pob st1
ład wynik
pob wyk
ode st1
som koniec // dlatego, że x^0=1
ład wyk
pob pod
ład wynik // dlatego, że x^1=x
p1:pob wyk // właściwe potęgowanie
ode st1
som koniec
ład wyk
pob pod
dns
sdp mnoz
sob p1
koniec: stop
mnoz:
pzs
ład licz
pzs
ode st1
ład ile
pob wynik
ład temp
et1:pob ile
ode st1
som wyjdz
ład ile
pob wynik
dod temp
ład wynik
sob et1
wyjdz:
pob licz
dns
pwr
licz:rpa
temp:rpa
ile:rpa
wynik:rpa
pod:rst 4
wyk:rst 3
st1:rst 1
stos:
Komentarz: Powyższy program zawiera podprogram mnożący identyczny jak w programie do liczenia silni, dlatego nie umieszczono komentarzy do tego fragmentu kodu. Główny program najpierw sprawdza, czy nie mamy do czynienia z potęgowaniem z wykładnikiem 0, a następnie przystępuje do mnożenia.
Obliczanie wartości symbolu Newtona.
pob n
dns
sdp silnia
pob wynik
ład dzielna
pob n
ode k
dns
sdp silnia
pob wynik
ład temp2
pob k
dns
sdp silnia
pob wynik
ład temp3
dns
pob temp2
ład wynik
sdp mnoz
pob wynik
ład dzielnik
sdp dziel
pob wynik
ład SYMBOL
stop
silnia:
pzs
ład licz1
pzs
ład liczba
pob st1
ład wynik
p1:pob liczba
dns
sdp mnoz
pob liczba
ode st1
som kon_s
ład liczba
sob p1
kon_s: pob licz1
dns
pwr
mnoz:
pzs
ład licz
pzs
ode st1
ład ile
pob wynik
ład temp
et1:pob ile
ode st1
som wyjdz1
ład ile
pob wynik
dod temp
ład wynik
sob et1
wyjdz1:
pob licz
dns
pwr
dziel:
pzs
ład licz
pob st0
ład wynik
pob dzielna
ład temp
et2:pob dzielna
ode dzielnik
ład dzielna
som wyjdz2
pob wynik
dod st1
ład wynik
sob et2
wyjdz2:
pob licz
dns
pwr
licz1:rpa
licz:rpa
temp:rpa
ile:rpa
wynik:rpa
liczba:rpa
dzielna:rpa
dzielnik:rpa
temp2:rpa
temp3:rpa
n:rst 5
k:rst 2
st1:rst 1
st0: rst 0
SYMBOL:rpa
stos:
Komentarz: Podprogramem powyższego programu jest opracowany wcześniej i odpowiednio zmodyfikowany program do liczenia silni. Oprócz tego potrzebny był również podprogram dzielący dwie liczby, w swojej budowie podobny do mnożącego. W podprogramie dzielącym nie operowałem już zmiennymi umieszczanymi na stosie, gdyż jest to ostatnia operacja do wykonania w programie i w związku z tym można użyć zmiennych dzielna i dzielnik, których wartość obliczono w potęgowaniu i mnożeniu. Sam główny kod programu jest liniowy i nie zawiera żadnych pętli, dlatego uznałem, że umieszczanie tam komentarzy jest zbędne. Kolejno liczona jest w podobny sposób: n!, (n-k)!, k!, następnie odpowiednie wyniki są mnożone i dzielone.
Program wymagał aż 7 bitów adresowych maszyny W, ale prawdopodobnie nie jest to najbardziej optymalne rozwiązanie.
Wnioski:
Posługując się symulatorem maszyny W do pisania prostych programów, mieliśmy okazję zdobyć pewne pojęcie o programowaniu w językach symbolicznych. Co prawda język symboliczny maszyny W ma inaczej nazwane rozkazy niż rzeczywisty procesor, ale samo programowanie wygląda do pewnego stopnia podobnie. Dzięki porównaniu pierwszej i drugiej części ćwiczenia mieliśmy też okazję docenić wartość udogodnień, jakimi są podprogramy i operacje na stosie. Bez użycia podprogramów napisanie ostatnich programów byłoby możliwe, ale o wiele bardziej czasochłonne i trudniejsze w testowaniu.