mod Ex12 rem \para \bf 12. CVIČENIE Z PREDMETU ÚVOD DO DEKLARATÍVNEHO PROGRAMOVANIA \end \para* http://ii.fmph.uniba.sk/cl/courses/1-AIN-505-udp/0506ls/ex/ex13.cl rem \para* \it Dátum: \end utorok 19. 5. 2006 \para* \it Odporúčaná verzia CL: \end 5.81.16 \para* \it WWW stránka predmetu: \end http://ii.fmph.uniba.sk/cl/courses/1-AIN-505-udp/0506ls?lang=sk \para* \it Kontakt na cvičiaceho: \end mailto:kluka@fmph.uniba.sk rem \para Scroll down to "EXERCISES". appldisp/0 Cdots Op(Ent('ctdot'),0) fun/0 Fill_in 'Cdots' Fill_in = 20060516 appldisp/2 Sub_d Subsup(Fenced(Op('(',0),Arg(0),Op(')',0)),75,Arg(1),None) appldisp/1 Vt_d Subsup(Id(2,'x',0),75,Arg(0),Op(Ent('bull'),0)) appldisp/1 Ct_d Subsup(Arg(0),75,None,Op(Ent('bull'),0)) appldisp/2 At_d Infix(Arg(0),50,1,Subsup(Op('+',0),75,None,Op(Ent('bull'),0)),Arg(1)) appldisp/2 Mt_d Infix(Arg(0),54,1,Subsup(Op(Ent('times'),0),75,None,Op(Ent('bull'),0)),Arg(1)) appldisp/2 Bar Infix(Arg(0),30,1,Op(Ent('mid'),0),Arg(1)) appldisp/2 Den_d Subsup(Fenced(Op(Ent('lobrk'),0),Arg(0),Op(Ent('robrk'),0)),75,None,Arg(1)) appldisp/1 Vi_d Std('LOAD',0) appldisp/1 Ci_d Std('PUSH',0) appldisp/0 Ai_d Std('ADD',0) appldisp/0 Mi_d Std('MUL',0) appldisp/2 Colon_d Infix(Arg(0),40,1,Op(':',0),Arg(1)) fun L L(0) = 0 L(v,w) = L(w)+1 fun/2 Sub 'Sub_d' Sub((v,w),0) = v Sub((v,w),i+1) = Sub(w,i) fun Vt 'Vt_d' Vt(i) = 0,i fun Ct 'Ct_d' Ct(n) = 1,n fun/2 At 'At_d' At(t1,t2) = 2,t1,t2 fun/2 Mt 'Mt_d' Mt(t1,t2) = 3,t1,t2 pred Term Term Vt(i) <- N(i) Term Ct(n) <- N(n) Term At(t1,t2) <- Term(t1) & Term(t2) Term Mt(t1,t2) <- Term(t1) & Term(t2) rem \para \bf E X E R C I S E S \end rem \para \it \bf Numeric terms with variables \end \end rem \para \bf Assignment 1. \end Define the \it denotation function for numeric terms with variables \end \ft Den(t,v) = Den_d(t,v) \end, which yields the value of the term \ft t \end under the \it valuation of variables \end \ft v \end. A valuation of variables \ft v \end is a list such that the value of variable \ft Vt(i) \end is the \ft i \end-th element of the list \ft v \end. fun/2 Den 'Den_d' Den(t,v) = Fill_in rem \para \it \bf Postfix machine. \end \end rem \para \bf Instructions of the machine. \end fun Vi 'Vi_d' Vi(i) = 0,i fun Ci 'Ci_d' Ci(n) = 1,n fun/0 Ai 'Ai_d' Ai = 2,0 fun/0 Mi 'Mi_d' Mi = 3,0 pred Instr Instr Vi(i) <- N(i) Instr Ci(n) <- N(n) Instr(Ai) Instr(Mi) rem \para \bf Assignment 2. \end \it Programs for the postfix machine \end are lists of instructions. Define a predicate \ft Program \end which holds true for such programs. pred Program Program(Fill_in) rem \para \it Operation of the machine. \end \header* fun/2 Run \end For any programs \ft p \end, \ft q \end, a \it stack \end \ft s \end, and a \it stack frame \end \ft v \end we have \eq* Run(p++q,s++v) = Run(q,a,s++v) \end \para for some \ft a \end. We the say that the \it execution \end of program \ft p \end by the postfix machine \it pushes \end the value \ft a \end \it computed \end by \ft p \end to the \it top \end of the stack \ft s \end. \para The idea of stack frames \ft v \end is to hold the values of variables accessed in \ft p \end by instructions \ft Vi(j) \end. Note that when such an instruction is executed with a \it current \end stack \ft s1 \end we should have \ft j = L(s1)+i \end for some \ft i < L(v) \end and then the value pushed on the top of \ft s1 \end will be taken from the frame \ft v \end as \ft Sub(v,i) \end. rem \para \bf Assignment 3. \end \header* fun/2 Run \end Define a function \ft Run(p,s) \end which simulates the run of the postfix machine for the program \ft p\end and stack \ft s \end. fun/2 Run Run(p,s) = Fill_in rem \para \it \bf Compilation of \ft Terms \end into \ft Programs \end. \end \end rem \para \bf Assignment 4. \end \header* fun/2 Comp \end Define the function \ft Comp(t,j) \end which compiles the term \ft t \end into a program, which expects the stack frame in the depth \ft j \end. If for any \ft t \end, \ft s \end, and \ft v \end such that \ft Term(t) \end we have \ft Comp(t,L(s)) = p \end then we also have for any \ft s \end \eq* Program(p) & Den(t,v) = Run(p,s++v) \end fun/2 Comp Comp(t,j) = Fill_in rem \para \bf Testing workbench. \end You can test the compilation and execution of your arithmetical terms. For instance, the following query: \eq* Try(E1,2,3,0) = Colon_d(x,Resf) \end \para* should produce the result: \eq* x = Mt(At(Vt(0),Mt(Ct(3),Vt(1))),Ct(5)),(2,3,0),55, (Vi(0),Ci(3),Vi(3),Mi,Ai,Ci(5),Mi,0),55 \end fun/2 Try Try(t,v) = t,v,Den(t,v),p,Run(p,v) <- Comp(t,0) = p pred Resf Resf(t,v,d,p,r) <- Term(t) & Ln(v) & N(d) & Program(p) & N(r) fun/0 E1 E1 = Mt(At(Vt(0),Mt(Ct(3),Vt(1))),Ct(5)) fun/0 E2 E2 = Mt(At(Vt(0),Ct(2)),Mt(Vt(1),Ct(4)))