Del3: Ideas for Restrictions

For this deliverable I began to consider a set of restrictions on C++ functions/member functions to guarantee those functions are polynomial computability.

1. For loop: for (for-init statement condition; expression) statement

   The for-statement is intended to express fairly regular loops. A for loop usually consists of loop variable, the termination condition, and the expression that updates the loop variable. We are considering the following things to restrict and to watch out for to guarantee the for loop can be performed in polynomial time.

   The case where the initializing statement can be empty. If the condition is empty, the for-statement will loop forever unless it exits by a break, return, goto. A bad example:

   for ( ; ;  )
   {
   
   expressions
   
   }
   

   If the expression is omitted, we must make sure if the loop variable is updated in the body of the loop. For example:

   for (i = 0; i <= 10; )
   {
   
   i++;
   
   }
   

   If the loop variable is updated in the expression, it shouldn't be updated again in the body of the loop. An obvious mistake can be made as this example:

   for (i = 0; i <= 10; i++)
   
   {
   
   i--;
   
   }
   

   If the comparison operator in the condition is `>=' or `>', then the loop variable should be incremented. If the comparison operator is `<=' or `<', then the loop variable should be decremented.

   Loop variables are not allowed to be assigned to a pointer. And, pointers are not allowed to be used as loop variables.

2. While loop: while (condition) statement

   Do statement while (expression)

   A while-statement simply executes its controlled statement until its condition becomes false. In this case, we set a loop counter to limit the loops. Once the loop counter exceeds a fixed value, the loop will be terminated regardless of the value of the condition.

3. Switch

   The switch-statement tests the value of its condition, which is supplied in parentheses after the switch keyword. The break-statement is used to exit the switch statement. The constants following the case labels must be distinct. break is the most common way terminates a case. A continue statement can also be used to go to the very end of a loop statement. Each case and the default in a switch must be test to see it satisfies the polynomial condition.

4. Goto : goto identifier;

   Identifier: statement

   First, recall how goto works. The scope of an Identifier is the function it is in. You can use goto to jump to a given identifier and jump both into and out of blocks. The only restriction is that you cannot jump past an initializer or into an exception. In my project we disallowed goto.

5. Recursion: undecided, but will try to handle with function call case.

6. Function calls

   Functions, which are called in a polynomial block, should also be checked to see if they have polynomial tags. We should label the function with polynomial tag.

7. Side-Effects

   For now, we assume input/ouput functions in the standard library to be polynomial time.

8. Function Prototypes

   If the function prototype is labeled with polynomial time, we should also check the function to make sure if it is polynomial time. If the function is not defined.