Exam in Programmes as Data

...

svare til venstre, ligeud, ligeud.

1 iteration: l, vl, hl

2 iteration: ll, lvl, lhl, vll, vlvl, vlhl, hll, hlvl, hlhl

3 iteration: lll, llvl, llhl, lvll, lvlvl, lvlhl, : : :

Det regulære udtryk består af en enkelt repeterende komponent, som kan iterere 1 eller flere gange. Ovenfor

ses hvorledes strenge genkendes af henholdsvis 1, 2 og delvist 3 iterationer af den repeterende komponent.

For eksempel er strengene l, vl og hl samtlige strenge, som fås med bidrag af en enkelt iteration.

Angiv et regulært udtryk der beskriver denne mængde af ikke tomme strenge.

Følgende eksempler genkendes ikke af det regulære udtryk: lv, lh, lvv, lvh, lhv og lhh.

Hint: Der er 3n strenge når den repeterende komponent itererer n gange, fx 3 for n = 1 og 9 for n = 2

ovenfor.

2

BSWU BPRD IT University, E2015

Opgave 2 (25 %): Referencer i Funktionssprog

Kapitel 5 i Programming Language Concepts (PLC) introducerer evaluering af et højereordens funktionssprog og

kapitel 6 introducerer polymorf typeinferens.

Opgaven er at udvide funktionssproget med referencer, således at de kan evalueres. I den abstrakte syntaks

repræsenteres en reference med Ref e, hvor e er et vilkårligt udtryk. Et udtryk e derefereres med Deref e og et

referenceudtryk e1 opdateres med værdien af e2 ved UpdRef(e1,e2).

1. Udvid typen expr i Absyn.fs med Ref, Deref og UpdRef, således at

_ referencer kan skabes, for eksempel Ref(CstI 1).

_ referencer kan derefereres, for eksempel Deref(Ref(CstI 1)).

_ referencer kan opdateres, for eksempel UpdRef(Ref(CstI 1), CstI 2).

Vis (i udklip) de modifikationer du har lavet til Absyn.fs

2. Udvid typen value i HigherFun.fs med følgende konstruktion således at referenceværdier kan håndteres:

RefVal of value ref

3. Udvid funktionen eval i HigherFun.fs, med evaluering af Ref, Deref og UpdRef, således at de

opfylder følgende:

Ref e: Udtrykket e evalueres til værdien v og en referenceværdi returneres: RefVal (ref v).

Deref e: Udtrykket e evalueres til værdien v. Hvis v er en referenceværdi, dvs. på formen RefVal v0, så

returneres indholdet af v0. Evalueringen skal fejle, hvis v ikke er en referenceværdi.

UpdRef(e1,e2): Udtrykket e1 evalueres til værdien v1. Hvis v1 er en referenceværdi, RefVal v01

, evalueres e2 til

værdien v2 og indholdet af v01

opdateres til v2. Resultatet v2 returneres. Evalueringen skal fejle, hvis

v1 ikke er en referenceværdi.

Hint: Du skal anvende F#’s support af referencer, dvs. ref, ! og :=. Bemærk at vores implementation af

UpdRef er anderledes end := i F#, hvor værdien unit returneres.

Følgende to eksempler illustrerer definitionerne ovenfor. Det første udtryk evaluerer til værdien Int 2.

Let("x",Ref(CstI 1),

If (Prim("=",Deref(Var "x"),

CstI 1),

UpdRef(Var "x", CstI 2),

CstI 42))

Det andet udtryk evaluerer til værdien Int 6.

Let ("x",Ref (CstI 2),

Prim ("+",UpdRef (Var "x",CstI 3),

Deref (Var "x")))

Vis (i udklip) de modifikationer du har lavet til HigherFun.fs og giv en skriftlig forklaring af modifikationerne

på 5–10 linjer.

4. Erklær mindst fire eksempler på udtryk af type expr hvori Ref, Deref og UpdRef indgår. Eksemplerne

skal inkludere mindst en reference hvis værdi opdateres. Vis resultatet af at evaluere eksemplerne med

eval. Du kan benytte funktionen run i ParseAndRunHigher.fs.

5. Udvid lexer og parser, således at referencer er understøttet med samme syntaks, som vi kender fra F#.

Det skal for eksempel være muligt at skrive "ref 1", "!(ref 1)" og "(ref 1) := 2" svarende

til eksemplerne ovenfor (pind 1). Vis (i udklip) de modifikationer du har lavet til FunLex.fsl og

FunPar.fsy og giv en skriftlig forklaring af modifikationerne på 5–10 linjer.

3

BSWU BPRD IT University, E2015

6. Omskriv de to eksempler fra pind 3 og dine egne eksempler fra pind 4 ovenfor således at de giver samme

resultat når lexer og parser anvendes inden evaluering. Vis resultatet af at evaluere eksemplerne.

7. Figur 6.1 på side 98 i PLC viser typeinferensregler for funktionssproget vi har udvidet med referencer. Til

at beskrive typen af referenceudtryk introducerer vi en ny type t ref. Eksempelvis