Return of the Little Man
Ukens innlevering er en fortsettelse av oppgaven fra forrige uke. Da lagde vi et en prosedyre som leste inn et LMC-program og ga tilbake minnestrukturen til LMC.
Vi har lagt ut en fasit fra forrige uke, s? alle kan gj?re denne oppgaven. Dersom dere ?nsker ? bruke deres egen implementasjon b?r dere teste at dere f?r ut samme resultat som fasiten gir for de forskjellige programmene dere skal kj?re. Det kan dere gj?re slik:
## les_lmc er fasiten. Legg denne fila i samme mappe som deres program, og legg til dette:
from les_lmc import les_program as test_les
programfil = "add.txt"
assert tuple(les_program(programfil)) == tuple(test_les(programfil)), \
"Programmene gir ikke samme minneoppsett"
For de som ikke var her forrige gang s? skal vi g? gjennom litt om LMC og fasiten slik at alle kommer seg greit i gang med dette. Dere kan og se p? oppgaveteksten fra sist for mer informasjon om hva vi gjorde.
Oppgave 1
I denne oppgaven skal vi lage prosedyren kjor_program(minne), som tar minnebildet dere lager i les_program fra forrige uke. N?r et LMC-program starter ser den p? hva som ligger p? den f?rste posisjonen i minnet og utf?rer den, og ?ker programtelleren. Deretter finner den instruksjonen som er lagret p? minneposisjonen til programtelleren helt til den kommer til en hlt-instruksjon.
def kjor_program(minne):
opperasjoner = {
0 : hlt,
9 : IO
}
# Dette er alle registrene til LMC
akkumulator = 0 # Hovedregister
programteller = 0 # peker p? neste instruksjon i minnet
instruksjons_register = 0 # Holder p? opperasjonskoden
minneadresse_register = 0 # Viser til minneadressen assosiert med en instruksjon.
Hvis dere ikke har gjort den forrige oppgaven, eller er usikker p? om den fungerer riktig, kan dere bruke prosedyren fra fasiten. Dere kan enten kopiere prosedyren inn i run_lmc.py eller bruke import til ? hente den.
1.1 Oppsett
Last ned fila run_lmc.py fra gruppesiden. Den inneholder kodeskjelletet vi skal fylle. Dersom du ikke allerede har gjort det kan du og laste ned .txt-filene som inneholder forskjellige LMC-program. Det f?rste vi skal f? til ? fungere er det som heter "add.txt".
1.2 Kontroll?kke
Det f?rste vi m? gj?re er ? lage en kontroll?kke. L?kka skal kj?re s? lenge programtelleren er mindre enn 100 (som vil si at den fortsatt peker innenfor minnelista). I kontroll?kka skal vi dele opp instruksjonene inn i registrene. N?r LMC kommer over en ny instruksjon skal det h?yeste siffret bli plassert i instruksjonsregisteret, og de to laveste siffrene skal plasseres i minneadresseregisteret.
N?r instruksjonsregistert er 0 skal vi kalle hlt-prosedyren for ? avslutte programmet.
Hint: For ? dele instruksjonene kan vi bruke litt barneskolematte som ingen husker, nemlig heltallsdivisjon og rest. Begge disse opperasjonene kommer overraskende ofte opp i programering, spesielt n?r man jobber med lister. I python kan man gj?re heltallsdivisjon med // og finne resten med %.
def heltallsdivisjon(a, b):
# a og b er heltall
# a = 5, b = 2 gir 5/2 rundet ned, alts? 4.
# Hva skjer hvis a er 901 og b er 100?
return a // b
def rest(a, b):
# a og b er heltall
# a = 5, b = 2 gir resten n?r man deler 5/2, alts? 1.
# Hva skjer hvis a er 901 og b er 100?
return a % b
Skriv ut verdiene til instruksjonsregisteret og minneregisteret for hver iterasjon av l?kka n?r du kj?rer add-programmet, hvis du har gjort alt riktig skal du f? denne outputen:
9 1
3 99
9 1
1 99
9 2
0 0
Oppgave 2
N? er vi klare til ? begynne ? tolke programmer. For ? gj?re det enkelt for oss plasserer vi funksjonene som utf?rer instruksjoner inn i ei ordbok. Vi skal fylle ut ordboken etterhvert som vi oppretter nye instruksjonsprosedyrer. Alle instruksjoner skal kalles ved ? sl? opp i ordboken, p? den m?ten trenger vi ingen if-sjekker til ? finne ut hva som skal gj?res. (Du skal alts? fjerne if-sjekken du har laget til ? kalle hlt-prosedyren i forrige oppgave)
opperasjoner = {
0 : hlt,
9 : IO
}
2.1 IO
Det f?rste vi skal gj?re er ? fullf?re IO-prosedyren. IO st?r for input/output og alle slike instruksjoner skal utf?res av denne prosedyren. I f?rste omgang holder det ? gj?re det slik at den skiller mellom en input og en output-opperasjon.
def IO():
"""
IO-opperasjoner, opkode 9.
Definerte opperasjoner er
addr = 1 : input
addr = 2 : output
addr = 22: ASCII-output
"""
pass
IO fungerer slik at n?r instruksjonsregisteret er 9 og minneregisteret er 1 skal man ta brukerinput. Input skal v?re et heltall som skal lagres i akumulatoren. Dere kan anta at dere alltid f?r lovlig input fra brukeren. Returverdien skal alts? v?re den nye verdien som skal lagres i akumulatoren.
N?r minneregisteret er 2 skal vi printe ut verdien i akkumulatoren til terminalen.
Siden vi m? vite verdien til minneregisteret og akumulatoren m? vi ta det som parametre til prosedyren.
2.2 add og sta
N? skal dere lage add- og store-instruksjonene. Add legger sammen verdien som ligger i akkumulatoren med verdien som er lagret p? plassen til minneregisteret i minnet (alts? et oppslag i minnelista).
Sta lagrer verdien som er i akkumulatoren p? plassen til minneregisteret i minnet (alts? skrive over verdien p? den plassen i lista.)
Oppdater opperasjoner-ordboken til ? inneholde de nye funksjonene og opperasjonskodene.
2.3 kj?re add.txt-programmet
Hvis dere n? fors?ker ? kj?re programmet vil dere merke at det kanskje ikke fungerer. Det er fordi alle prosedyrene er n?dt til ? ha et likt grensesnitt. Det vil si at alle m? ta n?yaktig de samme parametrene, i samme rekkef?lge, og returnere akkumulatorverdien for at dette skal fungere, siden vi ikke kan vite hva vi trenger n?r vi gj?r et oppslag i ordboken.
Endre prosedyrene til ? ha et felles grensesnitt.
2.4 utvide med sub, lda, otc
Implementer sub, lda og otc-funksjonene. Sub fungerer som add, men trekker fra verdien i minnet fra akkumulatoren.
Test programmet p? addsub.txt for ? sjekke at det fungerer
lda setter verdien til akkumulatoren lik verdien i minnet.
otc er en spesialversjon av output som skriver ut verdien i akkumulatoren som et ASCII-tegn. Dette er en IO-instruksjon, med opkode = 9, og skal kj?re hvis verdien i minneregisteret er 22. Endre IO-prosedyren til ? gj?re dette.
hint Python har en funksjon som heter chr() som kan v?re nyttig.
For ? verifisere lda og otc kan dere kj?re programfilen ascii.txt, som skriver ut alle ascii-tegnene.
Opgave 3 Turingkomplett
For at systemet skal kunne kj?re alle tenkelige programmer er vi n?dt til ? kunne hoppe rundt i koden, alts? implementere branch-opperasjonene. I LMC har vi instruksjonene BRA, BRP og BRZ. Felles for alle er at de endrer verdien til programtelleren. Til n? har vi bare lagt til 1 til programtelleren for hver instruksjon, men det vil ikke fungere med branch, s? vi m? derfor gj?re noen flere endringer i programmet v?rt.
3.1 endre grensesnitt
Det f?rste vi m? gj?re er ? legge til en returverdi fra alle instruksjonsprosedyrene v?re, de m? n? ikke bare returnere den nye akkumulatorverdien men og programtelleren.
def add(akkumulator, minne, addr, programteller):
...
return akkumulator, programteller + 1
Hint N?r en prosedyre har flere returverdier kan vi hente begge n?r vi kaller funksjonen.
akkumulator, programteller = add(akkumulator, minne, addr, programteller)
3.2 branch
Branch-opperasjonene fungerer slik at de tar verdien i minneadresseregisteret og setter programtelleren til den verdien.
BRA hopper alltid, BRP hopper bare hvis akkumulatoren har en positiv verdi, mens BRZ hopper bare hvis akkumulatoren har verdien 0.
Hvis en branch-instruksjon ikke hopper skal fortsatt programtelleren ?ke med 1.
N?r dere er ferdige med dette kan dere teste dette p? alle programfilene.
3.3 ekstra
Kj?r factorial.txt. Oppgi 5 som input. Dette programmet regner ut n! = 120. Kj?r programmet p? nytt ? oppgi 7 som input, hva er outputen da? Er dette riktig?
Til slutt
Dette kan v?re en litt krevende oppgave, men dersom dere f?r til dette kan dere alt som kreves fra de f?rste 5 ukene av pensum.
Dersom du har sp?rsm?l eller kommentarer til oppgaven kan dere sende meg sp?rsm?l p? jonaen@ifi.uio.no.