Dear Bruce, Thank you for your welcome in Bristol last week. Following you can find the TeX-files with the exam questions and solutions outline. I am now sending them to you by regular mail as well as a summary of my expenses. Cheers, Luis --------------------------------------------------------------------- Luis Soares Barbosa lsb@di.uminho.pt Departamento de Informatica Universidade do Minho - Gualtar 4700 Braga - Portugal --------------------------------------------------------------------- ------ cut here ----------------------------------------------------- % EXAME QUESTIONS %%%%%%% \documentstyle{article} % \documentstyle[11pt,a4wide,alltt,epsf]{article} \setlength{\headheight}{0pt} \setlength{\headsep}{0pt} \begin{document} \noindent {\sf \Large Systems Engineering Course (Fast Prototyping Module)} ~\\ \noindent {\sf CSE3 --- University of Bristol, 1994-95} ~\\ ~\\ {\sf \Large Exam Questions} ~\\ ~\\ \noindent {\sf Question 1} ~\\ \noindent A possible specification of a generic multiset in {\sf CAMILA} is as following\footnote{Recall A multiset (or bag) is just a set with replications.}. \begin{verbatim} TYPE Bag = Item -> Nat; Item = STR; Nat = INT; ENDTYPE \end{verbatim} \begin{description} \item [a.] Complete the definition of the following {\sf CAMILA} specification of (a fragment of) an algebra of multisets: \begin{verbatim} FUNC BagIns (i:Item, n:Nat, b:Bag) : Bag RETURNS ... ; inserts n copies of item i in bag b FUNC BagRmv (i:Item, n:Nat, b:Bag) : Bag RETURNS ... ; removes n copies of item i of bag b FUNC BagRep (i:Item, b:Bag) : Nat RETURNS ... ; finds how many copies of item i are there in bag b FUNC BagUni (b:Bag, c:Bag) : Bag RETURNS ... ; computes the union of two bags b and c FUNC BagUNION (bs:Bag-set) : Bag RETURNS ... ; computes the (iterated) union of a set of bags bs \end{verbatim} \item [b.] Suppose you have to use the multiset prototype as a soft kernel of a {\sf C} program. Describe how to do this and write down the (main part) of the interface code. ~\\ \end{description} \noindent {\sf Question 2} \begin{description} \item [a.] Consider the following definition of {\tt AddressDB} which is part of an address control component in a hypothetical academic network. \begin{verbatim} TYPE AddressDB = User -> System-list; System = Machine | Network; Network :: N:System-list; Machine :: Id:STR T:MachineType; MachineType = STR; User = STR; Table = MachineType -> Nat; Nat = INT; ENDTYPE \end{verbatim} Complete the specification of an event {\tt MachinesByUser} whose effect is to produce a table recording how many machines of each type a user is connected to (either directly or through another network). Warning: the same machine may appear in different networks but should not be counted twice! (Hint: Notice that {\tt Table} is a multiset and so you may use the operations on multisets described in Question 1 when needed. You do not have to prototype them in your answer.) \begin{verbatim} FUNC MachinesByUser (u:User) : Table PRE u in dom(A) RETURNS ... \end{verbatim} \item [b.] Explain briefly the role of the prototyping phase in the Design Cycle of an information system and relates to the implementation subsequent phases. In particular explain what is meant by {\em Prototype Embedding} and comment to what extent this methodology is supported in {\sf CAMILA}. \end{description} \end{document} % SOLUTIONS TO THE EXAME QUESTIONS %%%%%%% \documentstyle{article} \setlength{\headheight}{0pt} \setlength{\headsep}{0pt} \begin{document} \noindent {\sf \Large Systems Engineering Course (Fast Prototyping Module)} ~\\ \noindent {\sf CSE3 --- University of Bristol, 1994-95} ~\\ ~\\ {\sf \Large Solutions to the Exam Questions (Outline)} ~\\ ~\\ \noindent {\sf Question 1} \begin{description} \item [a.] ~\\ \begin{verbatim} FUNC BagIns (i:Item, n:Nat, b:Bag) : Bag RETURNS let (x = f(i,b)) in b + [i -> (n .+ x)]; f(i,b) = if (i in dom(b)) then b[i] else 0; FUNC BagRmv (i:Item, n:Nat, b:Bag) : Bag PRE i in dom(b) /\ n <= b[i] RETURNS if ( i in dom(b) /\ n == b[i] -> b\{i}, i in dom(b) /\ n < b[i] -> b + [i -> (b[i] .- n)] ); FUNC BagRep (i:Item, b:Bag) : Nat RETURNS if ( i in dom(b) -> b[i], i notin dom(b) -> 0 ); FUNC BagUni (b:Bag, c:Bag) : Bag RETURNS b\dom(c) + c\dom(b) + [x -> b[x] .+ c[x] | x <- dom(b) * dom(c)]; FUNC BagMul (n:Nat, b:Bag) : Bag RETURNS [x -> n .* b[x] | x <- dom(b)]; FUNC BagUNION (bs:Bag-set) : Bag RETURNS BagUni-orio([],bs); \end{verbatim} \item [b.] ~\\ This is a direct question about how to embed {\sf CAMILA} prototypes in an implementation programming language. All the details are supplied on the Lecture Notes, in the chapter {\em Prototype Embedding}. Some interface primitives must be used in every embedding of the multiset package in a {\sf C} program. Students are expected to comment on the purpose of: {\tt libxminit}, {\tt libxmeval} and the S-expressions constructors and selectors. The interface scheme is as follows, assuming the functions on the prototype have been turned to events acting on a state variable of type {\tt Bag} (this conversion is straightforward and is not required to be written down). \begin{verbatim} char *argv[]={"multiset.cam"}; #include "xmc.h" #define BAGINS(i,n) libxmeval(f2("BagIns",strsexp(i),intsexp(n))) #define BAGRMV(i,n) libxmeval(f2("BagRmv",strsexp(i),intsexp(n))) ... main() { SEXP ...; libxminit(1,argv); ... ... } \end{verbatim} \end{description} \noindent The conversion of bags to {\sf C}-structures is a little bit harder --- the general scheme reported in the Lecture Notes applies. However, the answer will be considered complete even if this is point is only mentioned but not solved. \newpage \noindent {\sf Question 2} \begin{description} \item [a.] ~\\ \begin{verbatim} FUNC MachinesByUser (u:User) : Table PRE u in dom(A) RETURNS Build(A[u]); FUNC Build(l:System-list) : Table ;STATE h <- pp(l) RETURNS if ( l == <> -> [], l != <> -> if ( is-Machine(hd(l)) -> BagIns(T(hd(l)),1,Build(tl(l))), is-Network(hd(l)) -> if ( N(hd(l)) == <> -> Build(tl(l)), N(hd(l)) != <> -> BagUni(Build(N(hd(l))),Build(tl(l))) ))); \end{verbatim} \item [b.] ~\\ The first part is a direct question. All the information needed can be found on the Lecture Notes, namely in the chapters {\em Introduction to the Prototyping Tool}, and {\em Prototype Embedding}. The second part aims to assess the students capacity to understand the potentialities and limits of the tool with respect to developing implementations from prototypes. The bi-directional communication between the prototype and ({\sf C})-implementation levels is expected to be addressed as well as some methodological issues such as environment emulation as high level prototypes. \end{description} \end{document} --------------------------------------------------------------------------------------