Spurningar Flashcards
1
Q
Hvað er “mál”?
A
Mál er einfaldlega mengi strengja. Strengur er endanleg runa tákna úr einhverju
mengi, sem við þá köllum táknróf eða stafróf (alphabet) málsins.
2
Q
BNF stendur fyrir ?
A
Backus-Naur Form, til heiðurs John Backus, sem fann upp FORTRAN forritunarmálið og Peter Naur, ritstjóri skilgreiningarinnar á ALGOL-60 forritunarmálinu
3
Q
Hvað er BNF?
A
BNF er aðferð, svokallað meta-mál, til að skilgreina mál. Með BNF er í grundvallaratriðum átt við það sama og átt er við þegar talað er um samhengisfrjálsar mállýsingar
4
Q
En BNF á sér einnig rætur í málvísindum, hver skilgreindi samhengisfrjálsar mállýsingar áður en Backus og Naur skilgreindu BNF?
A
Málvísindamaðurinn Noam Chomsky
5
Q
útleiðsla?
A
Þegar gefin er BNF skilgreining eins og að ofan má yfirleitt leiða út ótakmarkaðan fjölda strengja í málinu
6
Q
Mállýsing er margræð ef ?
A
Strenginn má leiða út á fleiri en einn hátt.
7
Q
Málið er samhengisfrjálst ef?
A
Ef unnt er að lýsa tilteknu máli með BNF (þ.e. með samhengisfrjálsri mállýsingu)
8
Q
Hvaða aðferðið eru notaðar til að lýsa málfræði forritunarmála ?
A
BNF, EBNF (Extended BNF) og málrit (syntax diagrams).
9
Q
Regluleg mál (regular language).
A
Frumeiningar forritunarmála, svo sem lykilorð, strengfastar, heiltölufastar, fleytitölufastar, o.s.frv., eru yfirleitt regluleg mál (regular language).
10
Q
Regluleg mál eru undirmengi samhengisfrjálsra mála, þ.e. ?
A
þ.e. öll regluleg mál eru samhengisfrjáls, en ekki öfugt.
11
Q
Reglulegar segðir?
A
Ein aðferð til að skilgreina regluleg mál er reglulegar segðir
12
Q
Endanlegar stöðuvélar ?
A
Enn ein aðferð til að skilgreina regluleg mál.
13
Q
Hvernig er EBNF?
A
EBNF er svipað og BNF, en þar hefur verið bætt við hugmyndum úr reglulegum segðum.
14
Q
BNF | ?
A
Eða
15
Q
-> 0|1|2|3|4
A
digit getur breyst í 0 eða 1,2,3 eða 4
16
Q
Nonterminals í BNF?
A
<>, Það sem er inn í getur breyst í eitthvað annað
17
Q
Hvað inniheldur BNF ?
A
terminals, non-terminals og production reglur
18
Q
Hvað þýðir ::= í BNF?
A
is defined by
19
Q
Hvað er LHS í BNF?
A
left hand side, alltaf non-terminal
20
Q
Hvað er RHS í BNF?
A
right hand side, terminals eða non-terminals
21
Q
málrit
A
BNF myndrænt
22
Q
Í endanlegum stöðuvélum eru lokastöður teiknaðar hvernig?
A
Með tvöföldum hring.
23
Q
Að breyta endanlegri stöðuvél í málrit?
A
Kassar samsvara stikum í stöðuvélinni
24
Q
Hvernig er lokatáknin merkt sérstaklega í EBNF?
A
Með því að setja gæsalappir utan um þau
25
Hvernig má tákna endurtekningar í EBNF?
Nota má slaufusviga til að tákna endurtekningar: {X} er látið standa fyrir núll eða fleiri X.
26
Hvernig má tákna einstakan valkost í EBNF ?
Nota má hornklofa til að tákna einstakan valkost: [X] er látið standa fyrir núll eða eitt X.
27
Hvernig má aðskilja valkosti eða safna saman?
Nota má sviga til að safna saman, og nota má | til að aðskilja valkosti: Til dæmis er (X | Y )Z jafngilt XZ | Y Z.
28
Samkeyting í EBNF?
Samskeyting í EBNF táknuð með aðgerðinni , (komma)
29
Í forritunarmálum eru eru notuð fjögur til fimm afbrigði viðfangaflutninga (parameter
passing), hver eru þau?
Gildisviðföng (call by value), Tilvísunarviðföng (call by reference), Afritsviðföng (call by value-result), Nafnviðföng (call by name), Löt viðföng (call by need, lazy evaluation).
30
Í Pascal og C++ eru notuð hvernig viðfangaflutningar?
gildisviðföng og tilvísunarviðföng.
31
Í C, Java, Scheme og CAML eru notuð hvernig viðfangaflutningar?
Aðeins gildisviðföng
32
Hvernig viðgangalfutningar eru notaðir í Morpho?
Í Morpho eru gildisviðföng og einnig er hægt að líkja eftir tilvísunarviðföngum, nafnviðföngum
og lötum viðföngum.
33
Hvernig viðgangalfutningar eru notaðir í Ödu?
Gildisviðföng, Tilvísunarviðföng , Afritsviðföng
34
Hvernig viðgangalfutningar eru notaðir í FORTRAN?
Bæði tilvísunarviðföng og afritsviðföng
35
Hvernig viðgangalfutningar eru notaðir í Algol?
Í Algol gamla voru gildisviðföng og nafnviðföng.
36
Hvernig viðgangalfutningar eru notaðir í Haskell?
Í Haskell eru löt viðföng.
37
Hvernig viðgangalfutningar eru notaðir í λ-reikningi?
Einnig má halda því fram að λ-reikningur, sem fundinn var upp löngu áður en tölvur urðu til, noti nafnviðföng eða löt viðföng.
38
Hvernig virkar gildisviðfang?
Gildisviðfang (call by value) er gildað (evaluated) áður en kallað er á viðkomandi stef, gildið sem út kemur er sett á viðeigandi stað inn í nýju vakningarfærsluna (activation
record) sem verður til við kallið.
39
Hvernig virkar Tilvísunarviðfang ?
Tilvísunarviðfang (call by reference), t.d. var viðfang í Pascal eða viðfang með &
í C++, verður að vera breyta eða ígildi breytu (t.d. stak í fylki). Það er ekki gildað
áður en kallað er heldur er vistfang breytunnar sett á viðeigandi stað í nýju vakningarfærsluna. Þegar viðfangið er notað inni í stefinu sem kallað er á er gengið beint í
viðkomandi minnissvæði, gegnum vistfangið sem sent var.
40
Hvernig virkar Afritsviðfang ?
Afritsviðfang (call by value/result, einnig kallað copy-in/copy-out) verður að vera breyta, eins og tilvísunarviðfang. Afritsviðfang er meðhöndlað eins og gildisviðfang, nema að þegar kalli lýkur er afritað til baka úr vakningarfærslunni aftur í breytuna.
41
Hvernig virkar Nafnviðföng ?
Nafnviðföng virka þannig að þegar kallað er á fall eða stef er ekki reiknað úr nafnviðföngunum áður en byrjað er að reikna inni í fallinu eða stefinu sem kallað er á, heldur er reiknað úr hverju viðfangi í hvert skipti sem það er notað.
42
Hvernig virkar Löt viðföng ?
Löt viðföng eru eins og nafnaviðföng,
| nema hvað aðeins er reiknað einu sinni, í fyrsta skiptið sem viðfangið er notað.
43
Í Scheme viljum við forrita án hliðarverkana, hvað þýðir það?
Það þýðir að við viljum ekki nota neinar gildisveitingar. Breytur fá því gildi þegar þær verða til og fá aldrei nýtt gildi.
44
Hvað þurfum við að gera til þess að forrita án hliðarverkana í Scheme?
Við notum endurkvæmni (recursion) í stað lykkju.
45
Hvað gerir endurkvæmt fall?
Kallar á sjálft sig
46
Hvað gerir hala endurkvæmt fall ?
Endurkvæmt fall sem endar á að kalla á sjálft sig (eða jafnvel annað endurkvæmt fall) er kallað halaendurkvæmt (tail recursive).
47
Afhverju er halaendurkvæmni hagstæð í Scheme ?
Þegar Scheme fall endar á að kalla á annað fall (eða sjálft sig) er strax hætt í núverandi falli og næsta fall tekur við og skilar sínu gildi til þess sem kallaði á upphaflega fallið.
48
Listavinnsla í Scheme byggist á föllunum?
car, cdr og cons
49
Hvað gerir car í Scheme ?
Gefur þér fyrsta stak í lista
50
Hvað gerir cdr í Scheme ?
Gefur þér allt sem kemur á eftir fyrsta stakinu
51
Hvernig myndi ég fá stak 2 í lista?
Með því að kalla á car af cdr af listanum, eða cadr sem er short fyrir það
52
Hvað gerir cons?
Setur stak fremst í lista
53
Umdæmi/Scope
Til þess að komast að niðurstöðu skilgreinum við umdæmi (scope) hverrar breytuskilgreiningar. T.d. er breytan i skilgreind í formúlu, og hefur væntanlega eitthvert vel skilgreint umdæmi, þ.e. það
er væntanlega eitthvert vel skilgreint svæði innan formúlunnar þar sem i hefur þá merkingu, sem skilgreiningin gefur. Ef við vitum umdæmi tiltekinnar skilgreiningar eigum við að geta skipt um nafn á
viðkomandi breytu án þess að merking formúlunnar breytist.
54
Hver skilgreindi fyrir daga tölvunnar formúlur, sem kallast λ-formúlur (lambda formúlur)?
Alonzo Church
55
λ-formúlur eru skilgreindar á eftirfarandi hátt:
Ef x er breytunafn þá er x lögleg λ-formúla,
Ef x er breytunafn og N er lögleg λ-formúla þá er λx.N lögleg λ-formúla,
Ef M og N eru löglegar λ-formúlur þá er MN lögleg λ-formúla,
Ef M er lögleg λ-formúla þá er (M) lögleg λ-formúla.
Engar aðrar formúlur eru löglegar λ-formúlur.
56
Tilvísunin (occurrence) í breytuna x í λ-formúlunni x er frjáls ?
Já
57
Breytutilvísun, sem ekki er frjáls, er sögð vera ?
bundin.
58
Breytan x í undirformúlunni N í formúlinni λx.N er sögð vera bundin eða frjáls?
bundin
59
Í λ-reikningi eru skilgreindar innsetningar á formúlur, hvernig?
Tilteknar frjálsar breytur fá „gildi“.
60
Breytutilvísun er frjáls ef að?
Breytutilvísun er frjáls þá og því aðeins að innsetning hafi áhrif á hana
61
Vakningarfærslur á ensku
activation records, stack frames
62
Hvar eru vakningarfærslur í Scheme geymdar ?
Í kösinni (heap)
63
Hvað er vakningarfærsla?
Vakningarfærsla er það minnissvæði sem einstök vakning af falli eða stefi notar meðan það keyrir.
64
Hvar er algengast að vakningarfærslur eigi sér stað?
Í flestum tilfellum eru vakningarfærslur geymdar á hlaða (stack.
65
Nokkur forritunarmál sem hafa vakningarfærslur í kös (heap) ?
Scheme, Haskell, Morpho og ML
66
Í bálkmótuðum forritunarmálum (block-structured programming languages) innihalda vakningarfærslur (activation records) hvaða upplýsingar:
Viðföng (arguments), Staðværar breytur (local variables)., Vendivistfang (return address), Stýrihlekk (dynamic link, control link), Tengihlekk (access link, static link).
67
Hvað er lokun (closure) ?
Lokun (closure) er fyrirbæri, sem í bálkmótuðum málum er notað á sama hátt og fallsbendar eru notaðir í C og C++.
68
Lokun inniheldur:
Fallsbendi á vélarmálsþulu viðkomandi falls, Aðgangshlekk, sem bendir á viðeigandi vakningarfærslu þess stefs, sem inniheldur viðkomandi fall
69
Til er annað skylt fyrirbæri sem kallast framhald (continuation). Framhald inniheldur ?
stýrihlekk og vendivistfang.
70
hver er munurinn á cons, car og cdr annars vegar, og cons-stream, stream-car og stream-cdr hins vegar?
cons-stream er ekki fall, heldur lykilorð, og seinna viðfangið í cons-stream er ekki reiknað fyrr en fallinu stream-cdr er beitt á útkomuna úr segðinni (cons-stream x y)
71
Hvernig virkar lykilorðið delay?
Þannig að segðin (delay e), þar sem e er hvaða segð
sem er, skilar svokölluðu loforði (promise), sem inniheldur segðina e, án þess að segðin hafi enn verið gilduð (evaluated).
72
Sé fallinu force beitt á loforð?
Þá verður segðin gilduð og gildinu skilað.
73
Rökstudd forritun ?
Krafan er sú að öll föll hafi lýsingu þar sem fram komi forskilyrði, eftirskilyrði og hvernig kalla skuli á fallið.
74
Hvað einkennir ML og CAML ?
Tögunin (typing) í þeim. Þau eru rammtöguð
(strongly typed) og nota sömu tögunaraðferð, sem er sérstök að því leyti að þýðandinn sér mikið til um að finna út úr því hvert tagið á að vera á hinum magvíslegustu gildum og segðum.
75
Tagskilgreiningar í CAML (og ML) geta innihaldið frjálsar tagbreytur?
já
76
Hvers vegna er gerður greinarmunur á pörum og listum í CAML en ekki Morpho og LISP ?
Vegna tögunarinnar
77
Aðalatriðin í notkun Morpho ?
Listavinnsla og einingaforritun.
78
Í keyrslu Morpho sýndarvélarinnar eru nokkur gisti (register) í gangi, þau eru ?
code., pc., stack., ret., ex., ac.
79
code. er ?
Fylki af Morpho vélarmálsskipunum sem verið er að framkvæma.
80
pc. er ?
Vísir inn í code sem bendir á þá vélarmálsskipun sem verið er að framkvæma.
81
Samanlagt skilgreina code og pc ?
Staðsetningu í vélarmálsþulu sem líta má að
| sé sambærilegt við vendivistfang eða fallsbendi í forritunarmálum sem hafa einfaldara keyrsluumhverfi.
82
stack. er?
Keðja af hlekkjum sem hver og einn inniheldur eina breytu. Þessi gildahlaði
er umhverfið (environment) sem verið er að keyra í. Hér eru bæði staðværar
breytur og breytur í efri földunarhæðum.
83
ret. er ?
Eðlilegt framhald úr núverandi falli.
84
ex. er ?
Afbrigðilegt framhald úr núverandi falli.
85
ac. er ?
Gisti sem fær nýtt gildi í hvert sinn sem Morpho segð skilar gildi (accumulator).
Þegar fall skilar gildi er gildið sett í ac áður en snúið er til baka úr fallinu.
86
Þegar við köllum á fall í Morpho og Scheme, þá sendum við fallinu ?
Bæði viðföng (á hlaðanum) og framhald
| continuation
87
Framhaldið virkar þannig?
Almennt er framhald gildi sem er dálítið keimlíkt og lokun en í stað þess að innihalda bendi á vakningarfærslu sem verður í næstu földunarhæð þegar lokunin er nytjuð (kallað er á lokunina), þá inniheldur framhald bendi á vakningarfærslu sem verður núverandi vakningarfærsla þegar framhaldið er nytjað. Halaendurkvæmni er þá útfærð með því að halaendurkvæmt kall fær sama framhald
og sá sem kallar, í stað þess að búið sé til nýtt framhald til að snúa til baka til þess
sem kallar. Lykilatriði er að framhaldið inniheldur stýrihlekk í stað þess að innihalda
aðgangshlekk eins og lokun gerir.
88
Á hverju andartaki í keyrslu Morpho eru tvö framhöld tiltæk, hver eru þau?
Annað framhaldið er í gistinu ret og er eðlilegt framhald sem nytjað er þegar núverandi fall skilar gildi.
Hitt framhaldið er í gistinu ex, sem nytjað er þegar afbrigði gerist í keyrslu (þ.e.
exception).
89
Keyra má Morpho í samtalsham (interactive mode) með skipuninni?
java -jar morpho.jar
90
Til að þýða Morphoforrit úr textaskrá x.morpho má nota eftirfarandi skipun:
java -jar morpho.jar -c x.morpho
91
Út úr þýðingu gæti, til dæmis, komið út keyrsluhæf skrá x.mexe, sem þá má keyra með skipuninni
java -jar morpho.jar x
92
Í forritun í stórum stíl (programming in the large) er skynsamlegt að líta á einingu
frá þremur sjónarhornum?
Frá sjónarhorni notenda, smiða og hönnuðar.
93
Hönnunarskjal skal uppfylla eftirfarandi skilyrði:
Gefa skal notanda einingar nægilega miklar upplýsingar um smíð einingarinnar til að hann geti notað hana, en ekki meiri upplýsingar.
Gefa skal smið einingar nægilega miklar upplýsingar um notkun einingarinnar til að hann geti smíðað hana, en ekki meiri upplýsingar.
94
Aðferðatafla
Virtual Method Table, skammstafað VMT.
95
Í öllum hlutbundnum forritunarmálum fylgir hverjum hlut vörpun sem varpar boði í
aðferð. Oftast er þetta gert þannig að hverjum klasa fylgir slík vörpun, og oft er vörpunin útfærð sem einfalt fylki þar sem vísirinn er heiltala sem stendur fyrir boðið og
gildið er fallsbendir eða lokun sem stendur fyrir aðferðina. Hvað kallast þetta?
Aðferðatafla/Virtual Method Table, skammstafað VMT.
96
Þegar boð er sent til hlutar ?
Þegar boð er sent til hlutar er leitað að boðinu í aðferðatöflunni og ef aðferð finnst fyrir boðið er hún framkvæmd. Ef ekki þá er athugað hvort hluturinn erfir frá einhverjum öðrum hlut. Ef svo er þá er leitað að aðferðinni í erfða hlutnum, og svo koll af kolli. Ef engin aðferð finnst fyrir boðið þá er það villa.
97
Í töguðum hlutbundnum forritunarmálum svo sem Java, C++ og Object Pascal fylgir hverjum klasa aðeins ein aðferðatafla, jafnvel þótt um arfgengi sé að ræða. Hvernig varpar sú aðferðatafla boði?
Sú aðferðatafla varpar boði beint í aðferð, hvort sem aðferðin er útfærð í viðkomandi klasa eða í yfirklasa.
98
Í Morpho er yfirklasi ekki þekktur á þýðingartíma, hvenær verður hann þekktur?
Yfirklasi ekki þekktur fyrr en hluturinn verður til.
99
Í Morpho er boð því tilvísun á aðferð, þegar gefinn er hlutur eða klasi. Útskýrðu nánar.
Boð er ekki aðferð því mismunandi hlutir hafa mismunandi aðferðir fyrir sama boð. Það
er einmitt stóri kosturinn við hlutbundna forritun að sama boð getur haft mismunandi aðferðir í mismunandi hlutum.
100
Forritunarmálið Haskell er tagað fallsforritunarmál með latri gildun. True/False
True
101
Viðföng falla eru ekki gilduð fyrr en ?
Nauðsyn krefur.
102
Listar í Haskell eru keimlíkir ?
Straumum í Scheme.
103
List comprehension
Listaritháttur í Haskell, hannaður til að vera svipaður í útliti og merkingu eins og mengjarithátturinn sem við eigum að venjast.
104
Með hjálp fallanna concatMap, map og filter má ?
Gera allt það sem gera má með listarithættinum.
105
Ruslasöfnunaraðferðir/ garbage collection methods
Reference Count, Mark and Sweep, Stop and Copy, Generation Scavenging
106
Reference Count/ tilvísunartalning
Í hverju minnissvæði í kös er teljari, sem ávallt inniheldur fjölda beinna tilvísana á þann hlut (það minnissvæði) úr breytum í forritinu eða öðrum hlutum - Þegar þessi teljari verður núll má skila minnissvæðinu.
.
107
Mark and Sweep, hvernig veit maður hvenær þarf að ruslasafna?
Þessi aðferð vinnur þannig að ónotuð minnissvæði eru geymd í lista, sem kallaður er frjálsi listinn. Þegar reynt er að úthluta minni er athugað hvort eitthvað er tiltækt á
frjálsa listanum. Ef svo er ekki þarf að ruslasafna.
108
Hvernig ruslasafnar Mark and Sweep ?
Sérhvert minnissvæði s þarf að hafa einn bita, s.merki, sem er notaður til merkingar á meðan á ruslasöfnun stendur. Reiknað er með því að sérhvert minnissvæði sé ómerkt þegar ruslasöfnun hefst.
109
Stop and Copy / afritunaraðferðin
Hún felst í því að nota tvö jafnstór minnissvæði fyrir kös, og er aðeins annað svæðið í notkun hverju sinni (nema meðan á ruslasöfnun stendur). Minni er ávallt úthlutað aftast í því svæði sem er í notkun.
Í byrjun ruslasöfnunar er víxlað á svæðum og öll svæði í gamla svæðinu sem eru í notkun eru afrituð í nýja svæðið. Reiknað er með því að sérhvert minnissvæði s hafi einn bita s.merki fyrir merki og sá biti er ekki notaður í neitt annað. Einnig er reiknað með því að sérhvert minnissvæði hafi pláss fyrir framvísunarbendi, s.framvísun, en það pláss má nota í annað þegar ruslasöfnun er ekki í gangi. Minnissvæði sem lifa af
ruslasöfnun eru afrituð yfir í nýju kösina og eru þá um leið merkt og fá framvísunarbendi sem bendir á samsvarandi minnissvæði í nýju kösinni. Eins og í merkja og sópa
aðferðinni er reiknað er með því að öll minnissvæði séu ómerkt þegar ruslasöfnun hefst.
110
Einstæða (Monad) í Haskell hefur ýmsar hliðar. Einstæða er:
oft geymsla fyrir gildi af ýmsu tagi (safn gilda),
aðferð til að skipuleggja útreikninga,
aðferð til að vinna með hliðarverkanir án þess að fórna kostum fallsforritunar,
aðferð til forrita í Haskell á svipaðan hátt og í skipanaforritunarmálum
(procedural programming language) og
aðferð til að stunda upplýsingahuld og gera seinni breytingar auðveldar.
111
Monad er sem sagt klasi í Haskell, sem er allt annað fyrirbæri en klasi í hlutbundnum forritunarmálum. Í Haskell er klasi ?
Flokkur taga, eða réttara sagt flokkur tagsmiða. Í skilgreiningunni stendur m fyrir tagsmið (type constructor).
112
Í Java eru fyrirbæri sem kallast generics og generic types, hvað er það og hvað gerir það?
Þýða mætti sem fjölnota forritun og fjölnota tög. Þau gera okkur kleift að forrita fjölnota einingar og aðferðir.
113
1. Notkun
2. Fyrir
3. Gildi
1. Hvernig við köllum á fallið
2. Undir hvaða kringumstæðum má kalla á fallið
3. Hvað gerir fallið
