Project #2
Project #2 is due Monday November 17th at the start of class. The text of the assignment ("assignment.pdf") along with all of the provided skeleton code are included in the archives below. You only need to download one of the archives; all of the archives are identical except for the manner in which they were encoded/compressed.
Questions and Answers
Q1
I have a quick question about what is meant with this phrase:
"The general rule about inheritance is that obligations (passwords) accumulate and that capabilities (methods) can be granted by exactly one authority (i.e., a class) at any given time."
Does this mean that if I define classes A and B, both with some capabilities, that defining C inherits A,B will only provide one of those capabilities? I thought that C should have all passwords of A,B, as well as all capabilities of A,B, as well as its own defined passwords and capabilities.
A1
The passwords required by C include all the passwords required by C, itself, and also all the passwords required by the parents of C. The capabilities available to objects of type C include all capabilities provided by exactly one parent of C and all capabilities provided by C, itself. To make this a little more concrete...
Suppose C derives from A and B, and that both A and B declare capability "authenticateAsRoot", and that C does not declare this same capability. It is possible that the definition of "authenticateAsRoot" provided by A is different from the definition of "authenticateAsRoot" provided by B. So which definition should C use? If you program in C++, consider the following:
class A
{
public:
A(){}
virtual ~A(){}
virtual int f(){ return 0; }
};
class B
{
public:
B(){}
virtual ~B(){}
virtual int f(){ return 1; }
};
class C : public A, public B
{
public:
C(){}
virtual ~C(){}
};
int main(int argc, char* argv[])
{
C instance_of_c;
return instance_of_c.f();
}
In the above, which definition of f does C use? This is an ambiguity, and a conforming C++ compiler will issue an error message and reject this code. If I remember correctly, the Python programming language will choose the first definition it sees, so it would use the definition of f provided by A, since A was listed first in the list of C's parents. In any event, this paragraph is saying that we will deal with the issue of multiple inheritance by simply discarding any capabilities in C for which the definition of that capability is ambiguous. To answer your initial question ("Does this mean that if I define...will only provide one of those capabilities?"), no; an instance of C will have all capabilities from both A and from B, so long as its definition is unambiguous. An instance of C will also have the capabilities provided by C.
Q2
Ah I understand now.... So then will a password x defined in an inherited class merely be overridden by the instantiating classes x password? I would only assume so, as that mirrors standard inheritance.
A2
No. Overriding only applies to member functions/methods. A required password is more like a member variable.
The question here, then, is if A, B, and C declare "x" as a required password, then is A::x different from B::x and different than C::x? And, if A and B list "x" as a required password, then does C::x refer to A::x or to B::x? To answer this question, think about the application in question. If there is some password database which maps the name of a password to the text of that password, and suppose that to access the capabilities of A you must type-in or have in your keychain the "sql_database_admin_password", and suppose that to access the capabilities of B you must type-in or have in your keychain the "sql_database_admin_password", what makes more sense to you: that you type in the same password twice? Or that it is sufficient to authenticate for both A and B with the same password?
Q3
I wanted to make sure my BFN (EBNF) is legitimate:
P ::= L L ::= L1; L2 | S S ::= grant C to id; | check id; | define C1 inherits ( ( C2(, C3)* ) | none ) [passwords pw1(,pw2)*]? [capabilities cap1 (,cap2)*]? ;
I am a little confused about if I need to then define the types password and capability, or not. I think I wouldn't need to define the type of password or capability.
Also, I take it we are _not_ supposed to implement this language/interpreter with actual classes in java? We are really supposed to write structures to track classes, their inheritances, passwords, and such?
A3
I'm glad you brought up this topic, since this seems to have been a point of confusion in project #1. Backus-Naur Form (BNF) and Extended Backus-Naur Form (EBNF) are *NOT* the same thing. While points were not deducted in project #1 for submitting an EBNF grammar instead of a BNF grammar, when we asked for BNF we were expecting BNF. It is important that you define your grammar using BNF, not only because we ask you to do so (which should be reason enough), but also because the recursive structure of BNF simplifies creating correct semantic specifications using recursive definitions.
As for the grammar you have provided... you are incorrectly duplicating semicolons in your definition of L. That definition of L may be correct for languages like the UNIX Shell, where statements look like "make" or "make clean; make" (note that semicolons separate, rather than terminate, commands in that language), but is incorrect for this particular language (i.e. don't blindly copy from your notes). Also, unless you intend to modify the provided parser, you should allow, for example, "define C;" in your grammar and treat it as semantically equivalent to "define C inherits none;". To answer your initial question... you are correct, you do not need to define "id", "c", "pw", and "cap"; you can simply leave these as terminal symbols in your grammar.
You are most certainly _*/NOT/*_ (even more emphasis than how you wrote it), supposed to:
- Compile the language into Java, or
- Dynamically define honest-to-goodness Java classes, using the ClassLoader.defineClass() API
Java's class mechanism follows different rules than the class mechanism used by the project's language, so it would not make any sense to implement the interpreter by delegating to Java's built-in class mechanism. Familiarizing students with the specifics of Java's ClassLoader.defineClass() function is not a goal of this assignment; teaching students how a class-like mechanism in an interpreted language might be implemented is. Use your own data structures to keep track of the state of the system and to support the language's class mechanism. These data structures comprise the "SecurityConfiguration".
Q4
In the phrase "If you use any non-standard algorithms or non-standard data structures,.....", what does the term 'non-standard' mean i.e. which algorithms/data structures are considered standard and which are non-standard?
A4
As a general rule of thumb, if the algorithm has a name and you can google it or look it up in Wikipedia or if it is provided by the Java API, then it is a standard algorithm. For example, if you construct a Directed Acyclic Graph (also known as a Tree) and perform Depth-First Search or Breadth-First Search on the Tree, ... the Tree data structure is well-known and well-defined, as are the DFS and BFS algorithms. If you create a data structure or algorithm of your own (e.g. a data structure which maintains consistency between several different data structures), then we want you to explain how it works.
Q5
Please correct me if I am wrong. I think we should use a data structure to keep track all classes along with their attributes (i.e. password and capabilities) and another data structure to keep track of all objects along with their attributes (i.e. passwords, capabilities). We can use any data structure as long as it is efficient, meaning that invoking statement 'check u' will efficiently retrieve the attributes of object u. About the algorithms, I guess we should explain the algorithms for constructing, inserting, retrieving, or deleting from the used data structures.
A5
See the answer to the previous question.
Q6
About drawing diagram or visual representation, does it mean to show the underlying data structures with their contents at different points of execution of the program?
A6
Let me try to answer this question by using a LinkedList as an example. Since a linked list is a standard data structure, you do not need to draw diagrams of linked lists; however, suppose for the sake of illustration that a linked list were a non-standard container or that you were not aware that linked lists were standard containers. In that case, a diagram of a linked list might consist of a series of cells, with an arrow (representing a pointer) going from one cell to the next (and possibly also from each cell to the previous cell), with the last arrow pointing to null. Basically, we want something which will help us to visualize how your data structure works. As the saying goes, a picture is worth a thousand words; we want something which will accompany and supplement your English description of how your data structure works.
Q7
I'm having trouble finding in the Java code where the "none" token is handled. The assignment says this is a valid identifier, but I fail to see where the parser handles it. When the parser hits this and creates a DefineStatement object, will it just make the parents list empty or will it put "none" on there (I hope not)?
A7
As far as the parser is concerned, "none" is just another identifier. You can choose to interpret "none" as a special keyword and prohibit definitions of a class named "none"; however, you may also choose to leave "none" as a predefined, but otherwise ordinary, security class. The choice is ultimately up to you. Since the parser treats "none" as an identifier, the parent list will include "none". Note that since we require that your interpreter treat undefined classes as if they were simply empty, the latter route requires no special handling while the former simply requires that you treat "define none ... " as an error (i.e. emitting an error message and then either ignoring the define statement -- which might be nice for the sake of interacting with the interpreter -- or aborting -- which might be nice from a correctness standpoint).
Q8
The professor mentioned during class that the solution should be elegant and efficient. It seems to me that, for denotational semantics, one can put the details of the semantics in the state or in the semantic functions.
That is, we can save most of the info. we need in the environment and use simple queries to process the semantic functions. OR we can make the environment small and make the queries in the semantic function more complex.
If we're trying to strike a balance between these two ideas in the spirit of elegance and efficiency, what should we be looking at? On most runtime systems, state space is fast and efficient, so saving most of the info. in the environment may be more efficient but not as elegant. On the other hand, making the functions more complex reduces state space, but by definition is more complex.
Any thoughts?
A8
In your formal semantic specification, try to be as elegant as possible; in your actual implementation, try to be as efficient as possible. Your implementation must, at least superficially, behave as described by your specification; below the surface, pretty much anything is fair game. By separating specification from implementation, both elegance and efficiency are achievable.
Q9
Yes, that makes sense. I guess what I'm really getting at is the denotational semantics part. Forget the implementation for a moment.
When I write semantic functions, it basically transitions the environment from one state to the next until it's processed the whole program. Then, the environment is in the final (hopefully) correct state.
When we write these functions, the semantic function itself just shows which part(s) of the environment changes and which do not for that function. However, we still have to write some "helper" functions that actually modify part of the environment when the semantic function is processed.
With this being said, we now have two places to do the denotational semantics. We could put a lot of information in the environment and make the "helper" functions simpler, or we could put less in the environment and add complexity to the "helpers".
In terms of the denotational semantics, does it even matter which approach we choose as long as the correct final environment state is reached? You said in the last email that the implementation will superficially represent the denotational semantics. That is, if we start with one environment we will end up with the environment as shown through the semantic functions. But, the underlying implementation can be anything as long as it's reasonably efficient.
So, my real question is: In denotational semantics, does it matter where we put the "guts" of the semantics: in the environment itself or in the "helper" functions?
A9
> "When I write semantic functions, it basically transitions the environment from one state to the next until it's processed the whole program. Then, the environment is in the final (hopefully) correct state."
It appears that you are confusing the operational and denotational semantic models. There is more of a difference between operational and denotational semantics than just using different types of brackets. The most important distinction is that, whereas the operational semantic model describes "execution" of a program, using a series of side-effecting operations, the denotational semantic model describes "evaluation" of a program, by recursively applying non-sideeffecting functions. If you are familiar with the differences between imperative programming languages (e.g. C++, Java, etc.), functional programming languages (e.g. Scheme, LISP, Haskell, etc.), and declarative languages (e.g. Prolog), it may help you to conceptualize the three different types of semantic models as roughly corresponding to each of these three different programming paradigms. Writing a specification in denotational semantics is in many ways similar to implementing the language using a functional programming language.
I bring this up because you write that a semantic function "transitions the environment"; however, in denotational semantics, side effects are strictly prohibited. You can construct a new "environment", based on the previous "environment"; however, you cannot modify or make changes to the previous "environment" -- as is implied by the term "transitions." It may also help you to get a better feel for this if you abandon the term "environment." A denotation function is made aware of previous computations or system state through its parameters. The result of evaluating the program is a mathematical object representing the "final state".
> "When we write these functions, the semantic function itself just shows which part(s) of the environment changes and which do not for that function. However, we still have to write some 'helper' functions that actually modify part of the environment when the semantic function is processed."
As stated above, "the environment changes" is not a valid statement. The result of evaluating a semantic function with a particular state as input might be a new state; however, the results of evaluating a semantic function do not necessarily have to be a world state. However, I agree that -- unless you want your function definition to be big and scary -- it may be necessary to define them in terms of smaller functions.
> "In terms of the denotational semantics, does it even matter which approach we choose as long as the correct final environment state is reached?"
Yes, it does, because I will have to read your solution, and it will be far more readable if you break your solution down into digestable chunks.
> "In denotational semantics, does it matter where we put the 'guts' of the semantics: in the environment itself or in the 'helper' functions?"
Regardless of where you "put the 'guts'", you should still break your solution down into small, manageable, and readable pieces. Maybe, at first -- while you focus on getting the higher-level aspects of your formal specification correct -- , you define your helper functions in such a way that they perform really expensive computations to extract certain information from the environment, and maybe, as you get to dealing with implementation and efficiency, you augment your environment and redefine these helpers to perform this extraction more efficiently by simply looking up the needed information directly from the environment. This would be a reasonable approach to take to the problem, although this is by no means the only correct approach to dealing with this problem.
Q10
This one is regarding the define statement.
The define "statement" can take many forms. For example we could have:
define A; define A inherits B; define A inherits B passwords x;
Generally speaking, how does the semantic function handle "optional" statements? Let's say for this example our "sigma" is a simple mapping between the class identifier and a list of passwords it "contains". If all the statements were required, this wouldn't be an issue. We could have another semantic function that just handles the "passwords" statement, but how would that function know which class the passwords go to if it doesn't also handle the define statement. I guess what I'm getting at is that it seems we need a semantic function for each of the combinations for the define statement.
A10
Your BNF grammar should cover all possible forms of the define statement. If you adhere to your BNF grammar in defining your semantic specification, then all of the possible cases will be covered. To simplify computation and prevent reduplication, you may, however, want to generate a generalized, uniform representation of the define statement from each form, and then perform computations only on the general form.
Q11
So basically, the BNF will handle the actual combinations of the define statement. But, for semantics, we can use a define statement that "processes" the optional statements if they appear? And this general form of the define statement is for semantic processing only, not for the BNF, right?
A11
Perhaps this is better explained with an example. Consider a simple language which consists of either the phrase "hello world" or simply "hello", and let the "value" of the language be a 1 if "world" appears and a "0" if "world" does not appear. Now, there are several ways to go about doing this. One possible way to define the BNF grammar would be:
<program> ::= <hello> <world> | <hello> <hello> ::= "hello" <world> ::= "world"
While this is an acceptable solution, doing this for larger grammars does not scale vary well. A better way to define this grammar would be:
<program> ::= <hello> <world-opt> <hello> ::= "hello" <world-opt> ::= <world> | lambda <world> ::= "world"
A possible denotational specification for the language, using the second grammar, might be:
program[[ <hello> <world-opt> ]] = | world-opt[[ <world-opt> ]] |
world-opt[[ <world> ]] = { world[[<world>]] }
world-opt[[ lambda ]] = {}
world[[ "world" ]] = "world"
In other words, the meaning of the optional clause is a set which contains all the elements in the optional clause. And, in this particular language, the meaning of a program is the size of the optional-clause set.
Q12
- I understand that the semantic function takes in an environment as an argument and returns a new environment and that it can't modify the old environment. So, in the helper functions, it would make sense to me that the new environment starts out as a copy of the old one and is modified by the semantic function before returning. Is this a correct assumption?
- How is output represented in the environment? I know it's really an abstract concept; we just need to put our output somewhere in the environment...I'm just having trouble visualizing the output as a relation or function.
A12
Regarding #1,.. perhaps at this point we are, forgive the pun, arguing semantics. If what you are asking is "can I express a function F' as F[x/F'(x)], where F' is identical to F, except that at x, F' has a value F'(x) instead of F(x)?", then the answer is yes. I am still not happy about using the term "modified" here to describe this, though, since this description of F' does not modify F in that F still retains its value and is not destroyed or altered in any way by this expression. Make sense?
Regarding #2,... You don't "put" the output into the environment; rather, the result of evaluating your program should be a mathematical object which contains, possibly among other things, the program's output. To illustrate this, here is an example of a programming language, in which a program consists of a sequence of numbers, and the output of the program is a copy of the sequence, with each number incremented by 1:
BNF Grammar: P ::= L L ::= L Nop | Nop Nop ::= N | lambda
Denotational Semantics: P[[ L ]] = L [[ L ]] L[[ L Nop ]] = L[[ L ]] . Nop[[ Nop ]] L[[ Nop ]] = Nop[[ Nop ]] Nop[[ N ]] = list(N+1) Nop[[ lambda ]] = ∅
In this description, the output of the program is simply the result of evaluating the program. The output could also have been returned in a tuple or in a tuple in a tuple, etc. or in some other mathematical object returned by the program. For this particular example program, though, having the value of a program be its output is probably the most sensible way of doing things.
Q13
In BNF, is there any way to say when defining something that it can't be equal to something else? Basically, I'm trying to figure out how to ensure that the class I'm defining doesn't inherit from itself.
A13
No. That cannot be specified in the BNF. You would have to do that in post-parse semantic checking. Basically, it is a constraint not expressible in your grammar.
Note that even if you could say that two things were unequal, you would get into quite a pickle when trying to prohibit indirect self-inheritance. To prevent such a thing, one would have to remember which classes were defined and how they were defined. In other words, this would require a context-dependent grammar. Although it is possible for computers to understand context-dependent grammars, it is very inefficient for computers to do so, and so the vast majority of programming languages are created using context-free grammars. We have not really discussed context-dependent grammars in this class, and for the purposes of this class, we are assuming that all of our grammars are context-free.
Q14
Yeah. I just figured it'd be nice to ensure what I could within the syntax... so, even if in the hierarchy of classes it eventually does reference itself, I thought maybe I could at least ensure syntactically that I'm not saying "A inherits A, B", even if I couldn't ensure that when I said "A inherits B, C" that B and C don't inherit from A somewhere down the line.
A14
Yeah, but what does that gain you? You would still have to check for indirect self-inheritance, anyway, and you will detect the direct cycles when you go about detecting the indirect cycles. So, really, you're just making things more difficult for yourself.
Q15
Do I need to be able to grant instantiation to multiple objects at once? For example, do I need to allow "grant A to u1, u2;" or "check u1, u2", etc.?
A15
No. If you wanted to be fancy, you could allow it and then modify the parser to also allow it, but doing that is by no means necessary.
Q16
I have a question regarding the build environment. So far, I've been using Eclipse and running the project by running Main... I was wondering:
- Is this ok?
- How would I build from the commandline (I'm using Windows)?
- Where should I put my data-structures?
A16
What you are doing with Eclipse should be fine, so long as you are careful to update the "Makefile" file to reflect any additional files which you add to the project. As for building from the commandline, you can build the project with "make" and run it with "java -jar project2.jar"; however, for Windows, you will probably need to install Cygwin in order to run Make. You might also need to edit your PATH environment variable to make the Java compiler and interpreter accessible from the Windows commandline (I assume you already have the compiler and interpreter, since you are successfully using Eclipse). Alternatively, you could SSH into Grid (grid DOT cec DOT wustl DOT edu) and do all your building/editing from there. As for where to put your data structures, it doesn't matter all that much where you put them. I would recommend that you put them either in the same package as the Interpreter class, or in a new package of your own creation one level below that package. Again, just be sure to update the Makefile to reflect any new source files you add to your project.
**UPDATE**
Sorry, I mispoke. You should put any classes that you create in the "cse425s.hw2.semantics" package or a sub-package of "cse425s.hw2.semantics" (I forgot that I created that empty directory for that purpose). Since I mispoke, I won't hold it against you if you've placed your classes elsewhere. However, if you haven't gotten to the Java implementation yet or you haven't created any of your own classes yet, then I would prefer it if, when you do make your own classes, that you place them there.
Q17
I am a little bit confused about the denotational semantics part. How are we supposed to update the list of defined classes?
A17
When you give your denotational semantic specification, you should specify the structure of both the input and output to each denotation function. For the sake of brevity, I have omitted this from my examples above; however, we expect to see in your paper both a formal specification of this structure as well as English text explaining the format of the input and the format of the output for each denotation function, along with an English explanation of what the denotation function computes. You can remember the previous state of the system by passing it in as parameters to another denotation function. The denotation function can report a structure, based on its input values, which reflect the new state of the system. The recursive composition of such functions will allow the overall output to reflect the final state of the system, after all input has been read. Make sense?
Q18
So I wrote what I believe to be the correct BNF. It is not non-deterministic if I understood the term correctly. Please let me know if I am on the right path. Also, do I need to define the terminal variable further down into letters?
<program> := <expr>
<expr> := <func> <variables> ';'
| <func> <variables> <expr>
<func> := 'define|inherits'
| 'passwords'
| 'capabilities'
| 'grant'
| 'to'
<variables> := variable | variable ',' <vars>
I also started attempting the denotational semantics, but am having trouble figuring out what functions and how to do some of them. I looked through the resources listed on the class page, but I am still having trouble.
A18
The term "non-deterministic" basically means "unpredictable" (i.e. if something is non-deterministic, you might get two different results when executing the same program two different times with the same input sequence); the term "deterministic", on the other hand, means "predictable" (i.e. you will get identical results for identical input sequences). The phrase "not non-deterministic" is a double-negative and is, therefore, not permitted in English (since English frowns upon double negatives). For this assignment, yes, we expect that everything you give us will be deterministic.
I'm sorry to say that you are very far from the right path. (No you do not need to define the terminal "variable" further down into letters -- if you did that, it would no longer be terminal symbol, now would it?) Your grammar --- aside from combining 'define|inherits' into a single terminal symbol --- allows for one to derive illegal inputs. For example, your grammar allows for "to x passwords z capabilities y grant u;". In general a grammar is a correct grammar if and only if:
- All (syntactically) legal programs can be derived by the grammar.
- No (syntactically) illegal programs can be derived by the grammar.
In other words, if you can find one example of a valid program which your grammar cannot derive or if you can find one example of an invalid program which your grammar can derive, then you know that you need to revise your grammar. Once you have nailed down a correct grammar, developing the formal semantics will come far more easily. Also, please do not be sloppy; use <vars> or <variables>, but not both.
Q19
I am a little confused about the semantics of the language. Am I supposed to define the semantic domain, and the semantic functions? I am not very sure what the domain and functions could be. For example, define's domain is i suppose identifier X superclass* X password* X capability*. I dont feel like I understand how to make a domain for something that is not concrete like integers.
A19
You are supposed to define the semantic functions (a.k.a. the denotation functions). These functions, like all other functions, have a domain, a co-domain, and a range. The domain is the set from which the inputs are taken. The co-domain is the set into which the function is permitted to map elements of the domain. The range is a subset of the co-domain into which the function actually maps elements of the domain.
The domain of the denotation functions will likely consist of the cartesian product of some "syntactic domain" (e.g. a set of identifiers) and some "semantic domain" (e.g. the previous system state). We would like you to, both formally and in standard English, explain to us the domain and co-domain of each function in addition to giving the function's definition. Pages 598-601 of the textbook explains what these domains are.
You are on the right track in terms of defining the domains. My only criticism is that you should say "set of identifiers" instead of "identifier*". Good luck. Don't hesitate to send another email if you have any more questions.
Q20
I had a question about the syntactic specification for this project: Should we include additional constraints and an example program as we did for the first homework?
A20
Yes.
Q21
So my domain definitions are turning out like this:
Domain Env: Environment = IDMap X ClassMap Domain IDMap: Identifier Declaration List = Identifier → Class⊥ Domain ClassMap: Class Definition List = Class → Definition⊥ Domain Definition: Class Definition = Set of Classes X Set of Passwords X Set of Capabilities
So I need to define "Set of Capabilities" and so on as:
Domain Set of Capabilities: Set of Capabilities = {How do I
define a list
of capabilities?}
Is a capability just a terminal? How can I define a list of distinct capabilities?
A21
I hope you have a good English explanation for all of that, since that was really confusing to read. Sets are fundamental and require no definition. If you define a capability as a terminal in your grammar, then a capability is just a terminal; if you use some other definition for a capability (e.g. maybe you define a capability as an identifier), then that's what it would be.
Q22
I'm having trouble understanding how to express the denotational semantics of an optional statement. So if the BNF syntax is:
P ::= L L ::= L1 L2 | S S ::= <class_definition> | <class_instantiation> | <type_checking> <class_definition> ::= define C1 inherits CL | define C1 inherits CL passwords PasL | define C1 inherits CL capabilities CapL | define C1 inherits CL passwords PasL capabilities CapL <class_instantiation> ::= grant C to IO <type_checking> ::= check IO
The denotational semantics for a program and statement list I think are fairly straight forward, but when defining the semantics for the individual statements I'm having trouble. (What I have so far is listed below)
- Is there a way to simplify the syntax grammar? I've been looking at A11 on the questions and answer page. It seems that I should be able to use a <opt-part> or something like that to simplify the grammar. Also in this case I need to specifiy that CL can be 'none' or a class-list. Can I do that in the syntax or is that something I need to do in the semantic portion?
- For the semantics...since the <class_definition> can be multiple different formats how do you generalize it?
- Looking at A11, I don't understand the first two lines of the semantics... Can you explain them?
- In your denotational semantics you have "lambda", is that suppose to represent the undefined state?
{NOTE: semantics in question omitted from Q&A}
A22
Before answering those questions (which I will get to in a moment), I just wanted to point out that you are mixing different styles of BNF, and we would prefer that you use one style or another consistently, rather than mixing styles. So, you should either use upper case without angle brackets or use lower case with angle brackets for non-terminal symbols, rather than a random mix.
- Yes, there is a way to simplify the grammar. Replace "inherits CL" with a new non-terminal symbol, and do likewise for "passwords PasL" and "capabilities CapL". Then, define each of these non-terminals so that it either expands to the empty string or to the contents it replaced. You do not need to do anything regarding 'none', unless you want to treat it as a keyword rather than as a predefined class. If you define 'none' as a keyword, then you can handle it syntactically or semantically, so long as you do handle it somewhere.
- The first line of the semantics in A11 says "the value of a program is the cardinality (size) of the set returned by invoking 'world-opt' with the optional world clause", and "the value of the optional world clause, if it is of the syntactic form <world>, is a set containing the value of the <world> form."
- Please see the BNF Resources Page. BNF has at least two special meta-symbols, the dollars sign ($) which represents the end-of-input, and either lambda or epsilon (depending on the variation of BNF), which represents the empty string.
Q23
When defining a semantic domain, such as identifiers as in Q.19, do we have to define the operations allowed on the domain (such as union, etc.) or do we assume that they are already well known (as the book hints at...pg. 596-597 (Semantic Domains))?
A23
If you use well-understood domains with well-known operations, then you do not need to list the operations (unless you use some bizarre notation for these operations, in which case, it would be good to list the operations so that we know how you are representing them from a notational standpoint). If, to facilitate your definition of the semantics, you want to invent new operations for your domains, then we will want you to list those operations, to give a clear English description of what those operations do, and to provide a formal definition of those operations in terms of the other fundamental operations for those types.
Q24
Do we need to define each 'type' of identifier as a separate semantic domain, or does just defining "identifiers" cover it?
A24
Identifiers are not a semantic domain; they are a syntactic domain. Identifier is sufficient.
Q25
Ok. What I was trying to convey is an environment which has 2 maps. 1 maps id → class, the other maps class → definition. A definition is the crossproduct of the classes defined passwords, superclasses, and capabilities. So perhaps this makes it a little clearer? Also, if I define in my grammar something like, say,
<pws-star> ::= <pws-star> pw | ε
To be a set of any number of passwords, may I use this in my definition of the domain of Definition? Like so:
Domain Env: Environment = IDMap X ClassMap
Domain IDMap: Identifier to Class Map = Class → Class⊥
Domain ClassMap: Class to Definition Map = Class → Definition⊥
Domain Definition: Class Definition =
{ <class-star> } X { <pws-star> } X { <priv-star> }
Does this make sense? I am really not sure if this is what you want or not. What can I do to make it simpler?
A25
That is a little clearer, but not as clear as it could be. Your English description should not be just an English rendition of the formal definition; it should contain additional information to help the reader understand not only what something is, but also why. For example, a better description might be "an environment is a 2-tuple, containing: a mapping of identifiers to class names (representing the instantiated variables) and a mapping of class names to their static definition (representing the defined classes)", because it explains how the elements in the environment are to be interpreted and used. The problem with using <pws-star> in your domain is that it is not clear if <pws-star> is supposed to be a list or a set. You may use terminals in your domains, but for higher level constructs, everything should be based on functions, tuples, sets, and lists.
I would recommend, as a general strategy for making the specification more readable, separating the English description from the formal definition (so as to decrease the text per single line), creating a section/subsection for the domains (so that "domain" need not be repeated), aligning equal-signs and colons (to improve readability), using spaces between definitions (so that, for multiline definitions, it is clear where one definition ends and the other begins), and indenting your formal definitions so that they are not in line with ordinary paragraph text. This is not a technical writing course, and so I don't plan to take off points for poor formatting (although I may leave constructive criticisms regarding textual formatting); however, I am reading these, so it would be helpful if things were formatted in an easily readable manner.
Q26
How are errors handled? That is, in the denotational semantics, is there a notion of a "halt" or invalidation that can be performed to signal to the recursion that something bad happened?
A26
That's a very good question. It is kind of up to you. In your result, your output can consist of the concatenation of your old output and an error message; or, if you want to simulate outputting error messages to STDERR instead of to STDOUT, you could have another list to represent STDERR and concatenate the previous value of STDERR with an error message; or, if you want to keep things simple and just abort when there is an error, you can just write something like "ABORT", "ERROR", etc. As long as it is obvious that you are saying the system should just give up. If you use a phrase which might not be obvious like "GEE_I_WASNT_EXPECTING_THIS_INPUT", or the like, then somewhere you should explain that this result corresponds to an abort. (NOTE: we do not recommend using "GEE_I_WASNT_EXPECTING_THIS_INPUT", since that phrase is too informal and unprofessional for a formal paper such as the one for this project.)
Q27
If I have class A that inherits from B and C, and let's say B inherits from D, does A also inherit passwords and capabilities from D or only from its direct ancestors?
A27
Yes, as in other programming languages, items are inherited both directly and indirectly.
UPDATE 28
I just wanted to point out that my answer to question #16 has changed. Please see the update.
Q29
Because "check id" doesn't actually do anything to the environment, is its semantic function just:
S : Statement → Environment → Environment S[[check id]](Env) = (Env)
It does not evaluate to anything or change the environment, only prints out certain things about the environment. So it should just return the Env it entered with?
And another question: in the book, their example defined denotational functions for each grammar atom. (p601) Am I correct in assuming that I cannot define a function for something like <pws-star>? Because it is really only a fancy terminal character?
A29
If I remember correctly, the book does not deal with programs that output in its coverage of denotational semantics. In denotational semantics, a program's output (including that which is sent to the console) is returned in the evaluation of the program. So, you need to have something in your "environment" which represents what has been written to STDOUT/STDERR, and recompute that appropriately.
As for <pws-star>.... you are confusing non-terminal and terminal symbols. Here's how to remember the difference between terminal and non-terminal symbols: a "non-terminal" is a "non-terminal", because it doesn't terminate. For example, if you were drawing a parse-tree from the top-down, you cannot stop with a "non-terminal" symbol, since it can be expanded. A terminal symbol, on the other hand, leads to a halt in the recursive expansion, because terminal symbols cannot be expanded (i.e. no production rule is given for a terminal symbol). Yes, you can give a function for "<pws-star>", and the job of that function would be to percolate-up the value of the list or set in a mathematical object (such as a list or a set). Please see the example given in A11 and in A12.
Q30
So silly question, but how advanced do we need to make our application and how efficient? Will a simple double-linked list work as suggested by Dr. Roman? Also, am I allowed to use global variables (currently just created a file called Global.java and am using that, but not sure if that's permitted.
A30
Dr. Roman was just giving an example of a data structure. You might use doubly-linked lists in your implementation, but you will probably need more than just a doubly-linked list. Your application should not use global variables. Why on earth would you need global variables? Just make them member variables of your Interpreter class. Global variables are no more acceptable than are goto statements. As for efficiency,.. you will need to justify why you think your implementation is "efficient"; that is, you should discuss alternative ways you might have implemented it, what the tradeoffs would have been, and why the way you chose was the most efficient way possible (in terms of asymptotic time complexity). Keep in mind that some optional features (e.g. outputting in alphabetical order) have time tradeoffs, which may or may not be worth it.
Q31
In the assignment you ask for a test case to be run that involves defining a class that inherits from classes that dont exist (yet). Are we supposed to specifically allow this? I was under the assumption that definitions that inherit from a non existent class are incorrect, like in other languages like c++.
A31
Yes, you are to specifically allow this. It is strange, I agree, but it is part of the specification.
Q32
As far as the output resulting from a "check" statement, does it have to be sorted in alphabetical order, or will it suffice that all the output is displayed correctly?
A32
That's a very good question. We didn't really specify that in the assignment. I believe the output we showed was in alphabetical order, but I think the order in which we defined the classes would have resulted in output in that order, anyway. Since we didn't specify it, the choice is up to you. Whichever you chose, be sure to give a good, English justification of your choice.
Q33
When giving parameters to the denotational functions, I need to use multiple parameter lists, right?
A33
No, although I understand the source of your confusion (the very rapid and half-hazard introduction to "currying"). I plan to put up a resources page on functional programming, lambda calculus, and currying, so I'm not going to try to cover the entire subject in this email, only to repeat it again when I post it to the webpage. Instead, suffice it to say that you should just use a single parameter list containing all of your parameters.
Q34
In my semantics, do I need to be doing things like cycling through all of a class's base classes and adding all of their passwords/capabilities to the class's password/capability mappings? Or is this something we save for the implementation and runtime-system section?
A34
Sort of. Your semantics need to completely describe the behavior of the programming language, so it needs to effectively implement everything your language does. However, you can "cheat" a little bit in your denotational semantics by using set-construction notation.. for example: { (x,y) | (x in z) and (x < y) }. Note that the example has nothing to do with the actual project. Anyway, the idea is that you can write some really complex operations (such as multiple iterations over a list) in highly compact form. In other words, we want something akin to pseudo-code that fully expresses the behavior (not necessarily the running time) of your program.
Q35
Should I use Greek symbols for the elements of the environment?
A35
NO!!!! No Greek. I hate Greek. While I will not penalize you for using Greek -- it would be unfair for me to penalize students for a personal preference/prejudice --, I am going to request that you refrain from using Greek or other crazy symbols in your denotational semantics. There is a reason why computer programmers use multi-character variable names, so please use them. I would rather not have my head explode while grading your papers due to having to decipher a mess of Greek. Thank you in advance for accomodating this request.
Q36
May I use third-party libraries in my Java implementation?
A36
Yes, provided that the license of the library allows you to use it and provided that you indicate that you used the third-party library in your README and AUTHORS file. That said, everything that we ask you to do can be easily implemented by yourself.
Q37
I'm still confused about the difference between terminal and non-terminal symbols... could you give another explanation?
A37
Sure. Basically, if it appears on the left-hand side of "::=", then it's a non-terminal. Symbols which appear on the right-hand side but do not also appear somewhere on the left-hand side are terminal symbols. Another way of thinking about it is that, if the grammar includes a rule for expanding the symbol, then it is a non-terminal; if the grammar does not have a rule for expanding the symbol, then it is a terminal symbol. Also, "terminal" is short for "terminal symbol", while "non-terminal" is short for "non-terminal symbol."
Q38
So let me see if I understand this terminals/non-terminals thing correctly. Given the following grammar:
N ::= N D | D D ::= '0' | '1' | '2' | ... | '9'
Am I correct that "N" and "D" are non-terminals and '0' through '9' are terminals?
A38
Correct.
Q39
So I sent you a couple emails, and you responded with answers, but I don't see any of those questions or answers posted here. Did you decide to stop updating the questions and answers?
A39
No. I intend to keep updating the questiong and answers section; I just fell behind a little bit. That said, detailed questions about nearly complete solutions are not going to be posted for obvious reasons (but that wasn't the case for your questions). So, I'll summarize here what I told you...
Many of you have been having difficulty with denotational semantics, especially with how/where to start. Many of you have been immediately delving into defining the domains of the semantic functions and then realizing you don't know what elements the security configuration ought to contain... So, here is some advice for how to go about doing this... At least at first, ignore the domains. Try to define the semantic functions for some of the easier statements (e.g. check and grant). If you need to make use of some variable or other piece of information, then you can conclude that it either has to be a parameter or it has to be extractable/computable from your parameters. This will help you to shape the parameter lists of these functions. Once you have written the definitions for these operations, then you can "document" them (i.e. state the domains) by stating what they take as input and what they produce as output. As you go from the bottom-up, it will become clear what information needs to be preserved at the very top (i.e. what the security configuration needs to be). There are other approaches, but I think this approach is probably the easiest and most straightforward.
Q40
In the denotational semantics... do I need to ensure that there is no circular inheritance in the definition of the define statement? If so, I don't need to check for circular inheritance in my definition of the check statement, right, since it is prevented in the define statement?
A40
This depends on whether you require that a well-formed program not contain circular dependencies. If you state that as a requirement, then a conforming implementation can essentially do whatever it wants if it is given a program which does contain circular dependencies; if you do not state that as a requirement, then your semantics must be capable of handling this case. In either case, if you enforce the invariant that the system state never contains a circular definition (e.g. by rejecting/ignoring such definitions in the define statement), then you don't have to worry about it in your check statement.
Q41
One more question regarding output:
It seems to me that the easiest thing to do here is concatenate output to a string as "check" statements are evaluated. However, in order to "figure out" the capabilities/passwords for a class in my environment, I need to use a "temporary tuple" to store passwords/capabilities as I search through my environment. After I've accumulated the info into my "temp tuple", the semantic function will return a string that has the latest output concatenated to it.
Am I thinking about this right?
A41
You might be thinking about it correctly, but it is also possible that you are not. If you are creating a named temporary and then modifying it, then you are on the wrong track. If, however, you are using expressions possibly involving recursive calls, and the expression evaluates to a tuple, and you are calling this a "temporary", then you are on the right path.
INFO 42
Just so you know, the server on which this website is located has been giving me some difficulties in terms of logging in; the server is rejecting connections from my computer, but seems to be accepting connections from
grid and the other CEC machines (right now, I've managed to SSH into the webserver from my computer by first SSH'ing into grid). I'm trying to get the problem fixed, but in the process my workaround
might no longer work, either. So, just wanted to give all of you a heads up.
Q43
I'm trying to define the output. Dr. Roman said it would be a tuple <obj_id, {pswd_ids}, {cap_ids}>. My question was in regards to the output tuple... is that a set of tuples <obj_id, {pswd_ids}, {cap_ids}>? I don't see the comparison to the other functions used in the environment that were mappings (i.e. class_id --> pswd_ids).
A43
As I'm sure you have already discovered in programming, two people can write programs which exhibit the exact same behavior, and yet the code which accomplishes these shared behaviors are completely different. There are multiple ways of doing things. Each way, though, has to be internally consistent and achieve the desired behaviors. Dr Roman's version, for example, assumes that the tuple contains a set of sets in the second and third positions or it assumes that "pswd_ids" and "cap_ids" are not sets, but rather comma-separated lists (and hence the need to place them in brackets). Also, this solution makes the assumption that the elements in "cap_ids" are pairs, containing a capability identifier and a class identifier (so as to record which class a particular capability came from). As for whether the output should be a single such tuple or a set of such tuples... as was mentioned in class, you may define the output to be the most recently printed item or everything that has been printed. Conceptually... in the former case, we are assuming that some external system is inspecting the values that are returned from each statement and printing the contents of the output after each statement has been evaluated; in the latter case, we are assuming that the system prints all of the output, after it has evaluated the program. In your paper you should make it clear whether the output is the output just for the most recently evaluated statement or whether the output corresponds to all of the program's output. Don't mention any of the conceptual stuff, though, since it is just that (i.e. it is purely conceptual), and also since -- for conceptual purposes -- it delves into the realm of implementation (when that section is about specification, only).
Q44
(Redacted:) I think I may have stumbled upon a bug in the parser... when I type in the following program:
grant A to u; check u; define A passwords z inherits B; check u;
The parser spits out a lot of errors on the define statement, but when "check u" is invoked, it prints out "password z". Is the framework you provided supposed to invoke our interpreter code, even when the statements are malformed? And if so, is this something our interpreter has to detect and handle?
A44
Congratulations, David Kaminsky! You have, in fact, discovered a bug in my framework. I have reposted the framework, with this error corrected (the only file which changed is "cse425s/hw2/syntax/DefaultParser.java"). You can verify that replacing "DefaultParser.java" with the new version of this file has corrected the problem by applying the same input sequence and noting that the output from "check u" does not change.
By detecting an error in my framework, you have demonstrated a high degree of testing. Therefore, I intend to bestow on you some number of bonus points (not sure yet exactly how many) with regard to testing. If anyone else finds errors in my framework, they will also be given bonus points for the testing section. The number of bonus points to be rewarded will be set once the rubric has been developed (yes, we still haven't come up with the rubric); however, I expect the number of bonus points to be something along the lines of 2 to 4. Anyway, good job.
Q45
I am having a little trouble trying to figure out how to express how to find the set of (class->capability) in my define function. I was trying to define a function that that will do this, and takes in the list of superclasses, classname, and capabilities of a certain class, as well as the environment. Then I wanted to construct a set of all possible {class->capability} such that capability is in the list of capabilities, or a list of capabilities in a superclass, AND that there is no {c->cap} in the set such that classname is a parent of c, AND that horizontal ambiguous inheritance is discarded.
I feel like my set theory/notation is much too weak to do this (correctly). What could you suggest that I do? I would need to define a function isParent(classa,classb,environment) or something, but I am not sure.
A45
Suppose you have { x | c1 and c2 and c3 ... and cN }, where c1...cN are some really, really complicated expressions which determine what values "x" will take on. You may find it easier to form this by defining helper functions for each clause ci and by putting each ci on its own line. You can also send me what you have, and I can try to help you improve your notation.
Q46
So, if a capability is defined by multiple classes we're told explicitly what to do... use the one in the defined class if there is one or just ignore it if they're both in base classes.
Are we supposed to do that with passwords as well?
A46
No. With passwords, you print out all of the passwords (without repeating passwords).
Q47
(Continued from previous question...) So, what if we have classes A, B, and C, and A inherits from B and C, and B and C both define password h but A does not, we just print "password h" out once?
A47
Correct.
Q48
It occurred to me that I'm not sure how to declare containers, like a map of classes to sets of classes. Do I just say what it is (i.e. "M = map of class ids to sets of class ids")?
A48
In mathematics, a map is a function. So, you would define it as a function (e.g. "M: classid -> P(classid)", where "P" means "powerset"). You should still include informal, explanatory English text, in addition to the formal mathematical description.
Q49
Are we allowed to grant a class to an object if the class has not been defined? Ie, is grant A to u; valid if A is not defined? I can easily program it either way, but right now I allow this and simply don't print any passwords/capabilities if check u; is then called.
A49
In my answer to question 7, I wrote "we require that your interpreter treat undefined classes as if they were simply empty". So, to be completely consistent, not only may your interperter allow such a thing, it must; however, looking over the assignment sheet again, it appears that my answer to question 7 may not have been as precise as it should have been... you can choose to allow the granting of undefined classes and you can choose to disallow the granting of undefined classes. Be aware, though, that if you disallow the granting of undefined classes, then you will need to explicitly predefine "none" or make "none" an exception to this rule (so that "grant none to u;" will work); whereas, if you allow the granting of undefined classes, then no special coding is required to handle the "none" class. Is that clear?
Q50
I noticed that with the original code base you gave us, error messages will be printed if a semi-colon is missing, but the statement missing the semi-colon will still be interpreted. Would you like us to stop such statements from being interpreted?
A50
Congratulations, Jessica Codr! You discovered an error in my framework. Actually, you discovered the same bug that David Kaminsky discovered. However, based on the timestamp of your email, it is clear that you discovered this before I posted Q44/A44, so you also get bonus points. Good work. (See A44)
Q51
I also noticed that the assignment asks us what happens when keywords are mistyped or when there are other errors. It seems your code already catches these errors and prints out an error message stating that a keyword has been mistyped. When this happens, there is no interpretation done. Did you expect us to do something other than this default behavior? I am trying to check the robustness of my code, but it seems the only thing that was not already caught by your error printing is the cyclical class definitions. Is there something else I need to check for that I am missing?
A51
The question reads that way, because it is possible for students to modify the parser to bring it into line with their grammar. For example, if a student wants to allow the inherits, passwords, and capabilities clauses to appear in any order, then he/she is free to modify the interpreter to allow this. Assuming no modification to the interpreter (and assuming the patched version of the interpeter), all syntax errors should be caught. Whether you need to detect anything other than cyclical class definitions depends on the choices you make about how the implementation should behave. For example, if you treat "none" as a keyword, then you will want to detect definitions of "none" and output an error if "none" is defined. I can think of at least one other condition which you might want to (but do not have to) detect. I'll let you think about that some more.
Q52
Why is there an "init" function in "Interpreter.java"?
A52
The "init" function is there so that you can do your own initialization without modifying the constructors I provided (I didn't want anyone accidentally breaking the output mechanism).
Q53
How "robust" does my interpreter need to be? How are you planning to determine if my implementation is correct?
A53
Let's put it this way... I am going to put your interpreter through a series of tests. Some of the tests are going to be well-formed, with well-defined expected outputs. For these tests, I am going to verify that your interpreter runs without breaking and outputs the correct results. Some of the tests are going to check for implementation-specific behaviors (like whether "none" is a keyword or merely predefined), and I am going to note which behavior is present in your implementation and verify that this agrees with the behavior indicated in your specification. Some of the tests are going to be malformed and will be used to test for robustness. I am going to want to see that your implementation detects that the input was malformed (by printing an error message of some kind) and responds appropriately (either by attempting recovery or by giving up).
Q54
I have a question regarding hw2 about self-inheritance:
Do we need to check this constraint when we redefine parent classes? For example, given:
define A inherits B, C; define B inherits A;
In this case, it should be prohibited, right?
A54
That is correct.
Q55
Can you give me a hint about how to handle/detect self-inheritance in the formal specification.
A55
Sure. In the specification (but not the implementation), you can be as inefficient as you want in detecting self-inheritance. Also, unless you intend for your language to have well-defined error semantics, you can simply list no self-inheritance as a requirement of your specification (however, you will still need to define no self-inheritance in a mathematically precise way).
Q56
Would you be able to tell us approximately how much each of the three sections is worth (Syntactic Spec, Semantic Spec, and Runtime System), or will that be revealed after we turn it in again this time?
A56
I am intending for the sections to receive roughly equal points, and I am also intending to assign points for providing English explanations alongside the formal descriptions. The exact point distribution, however, will not be set until the matter is discussed with Dr. Roman when he returns. So, try to do a good job on all the sections.
Q57
What is the expected behavior of the system if someone defines a class that already exists? I don't think it's specified anywhere.
A57
Please reread the assignment. This is specified. The assignment says that "existing classes may be redefined dynamically." Your system MUST allow this redefinition, and the effect should be that all existing classes and existing objects which reference the redefined class should reflect the new definition.
Q58
What happens if I have a grant a to b and b already exists. The homework states re-assigns existing object to a class. The way I interpret that is that it overwrites it, but I have a feeling that it is supposed to grant the capabilities but keep the old ones...Or is it up to me?
A58
Don't second guess yourself; you interpreted it correctly the first time. If an object is reassigned membership in a class, it takes on the attributes of the class to which it was reassigned and does not preserve any of the behaviors associated with its previous definition. This part of the spec. is not up to you.
Q59
You mentioned in the FAQ that we need to have a robust test program. I am curious if you want the "test output" in the paper to be from your given test in the assignment, or if we should devise our own test suite that is perhaps a little more intense?
A59
Yes, you should devise your own test suite. You will be given some number of points for thoroughly testing your implementation, and to assign these points, we will need some evidence of testing. Indeed, in the README file, there is a section on testing, which you are supposed to fill-out with an explanation of how to use your test suite. I will run both my own tests, as well as the tests which you provide. By thoroughly testing your implementation with its own test suite, before submitting, you will increase the liklihood of it passing the tests which I have devised.
Q60
You have said a couple of times that the specification and the implementation do not need to be the same... does this mean that they have to be different?
A60
I am going to assume that by "same" and "different" you are discussing what they do and not how they are written (since obviously denotational semantics will look different from Java code). No, they may be different but they do not have to be.
Q61
In the example in the assignment pdf you do "define A inherits B, C passwords p,q capabilities d,e; grant A to u; check u;".... When you do the check, it prints "password p", "password q", "capability d from A", and "capability e from A", but has no mention of the parents. Does that mean that the parents do not become parents of u as well?
A61
In that example, the classes "B" and "C" were not yet defined, so they did not have any passwords or capabilities associated with them. If "B" and "C" had passwords and capabilities associated with them, then these would also show up (assuming that the capabilities/passwords of "A", "B", and "C" were disjoint; otherwise, inheritance rules might cause some of the items to disappear). So, to answer your question,... no, the parents are not ignored; follow the inheritance rules described in the assignment.
Q62
After looking over the Q&A on the website, I came across a question that raised concerns about my runtime implementation. In your answer to question 41, you said: "If you are creating a named temporary and then modifying it, then you are on the wrong track. If, however, you are using expressions possibly involving recursive calls, and the expression evaluates to a tuple, and you are calling this a "temporary", then you are on the right path."
Were you referring to defining the semantics or to implementing the run-time system here?
A62
I was referring only to the semantics part. Note that the student's use of the term "semantic function" along with "tuple" and "environment" give pretty good context clues that he/she is discussing the denotational semantics. Since I inferred that the question was in regards to the denotational semantics, I responded specifically about the denotational semantics. I apologize for any confusion this caused.
Q63
Regarding the ambiguities of capability definitions, if we have an ambiguity somewhere up in our inheritance tree, but somewhere lower in the tree there is an unambiguous definition of that capability, should we use that unambiguous definition?
Specifically: Suppose I have:
- class A that inherits from class B and defines capability p
- class B that inherits from classes C and D
- class C and class D both define capability p
Now in class B, there is an ambiguity about which definition of p to use, so p would be "thrown out". However, class A redefines capability p for itself, so it seems reasonable to me that class A would use its own definition of capability p, as would any other class that inherits from A (only) and does not define its own version of p. So even though there is an ambiguity higher up in the hierarchy, it is resolved at a lower level. Is this correct/acceptable?
A63
You have very nearly hit on something very important. Your question hits the nail on the head, but you could have chosen a better example. The problem with the example you selected was that we made it explicit that whether there are ambiguities or not does not matter when overriding takes place. In other words, since A gives its own definition of p, we don't care whether p is defined, undefined, or ambiguous at a higher level. However, consider the following program:
define A inherits L, R; define L capabilities f; define R inherits X, Y; define X capabilities f; define Y capabilities f; grant A to obj; check obj;
Now, here's the ultimate question: does this print "capability f"? One can argue it either way; since "f" is cancelled in R, A only gets an "f" from L and so "f" is not ambiguous in A, or one can argue that A gets "f" from L, X, and Y, and so it is still ambiguous in A. I will be checking that your denotational semantics and your implementation agree on how they handle this case.
Returning to your initial question, A (in your example) should use its own its own definition of "p", because overriding always takes precedence over cancellation due to ambiguities.
Q64
So my program works correctly (I believe). The way I implemented the output however I have it writing:
passwords: a b c
I know in the example it shows:
password a password b password c
Does that matter? Although it's not a huge deal I would have to do some re-writing and some retesting, but if I will get points taken off for this I will reimplement.
A64
Suppose you were part of a company that contracted out another team to implement this interpreter, and your company wrote up the assignment which was given as an informal specification for this team. And then suppose the team came back with the interpreter which they had been hired to write, and the interpreter gave that output... Do you think the company which hired the team would be a little bit surprised?
In the assignment, it says "the statement above...results in the following output". Note that it does not say, "results in output similar to the following" or "might result in the following output". The phrasing of the assignment implies that the format of the output is a hard and fast requirement of the informal specification, and so you should not deviate from what is requested in the assignment.
Q65
Would you like us to include all the code needed to run the project in our submission or only files that we modified or added?
A65
Please submit everything (archive the folder, using ".tar.bz2", ".tar.gz", or ".zip" format, and then email the archive as an attachment).
Q66
I was printing the output like:
Security status of u: password x password y capability a from A capability b from C
Security status of v: password k password y capability s from B capability b from C
Seeing your answer to Question#64, I changed my output to:
password x password y capability a from A capability b from C
password k password y capability s from B capability b from C
But now the question is: If I have a statement, say 'check p', at some point of a program, but object p has no password or capability, should we just print blank line or print something like 'p has no password' or 'p has no capability'?
Right now I am just printing nothing for an object that has no password or capability. But in this case, it is hard to trace which security status is for which object in output screen.
A66
Printing a blank line is good.
No More Q&A
The Q&A section is officially closed.