Advisor: Dr. Chris Pollett

Committee Members: Dr. Araya, Dept. of Computer Science (araya@cs.sjsu.edu)
Dr. Louden, Dept. of Computer Science (louden at cs.sjsu.edu)

Abstract:

In recent years there has been an active research area which tries to give functional characterizations of time-bounded or space bounded complexity classes. An old example of this would be Cobham's [C64] characterization of PTIME using simple base functions on the natural numbers and closure under composition and bounded recursion on notation. Unfortunately, this characterization is restricted to natural numbers and thus makes it somewhat awkward to implement ``naturally'' occurring algorithms over other structures such as trees. Another avenue of research in this area, has been to give characterizations of these complexity classes which do not explicitly mention the resource bound in question. So for example, one would try to give a functional characterization of polynomial time that does not explicitly mention polynomials anywhere. Such characterizations have been given by Bellantoni-Cook [BC92] and Leivant [L93] under the names of safe recursion and tiered recursion. Still, both safe recursion and tiered recursion have disadvantages in that many naturally occurring polynomial time algorithms do not fit into the rather rigid discipline they impose. Recently, Hofmann [H02] gives a characterization of EXPTIME which allows computations over a variety of data structures such as lists or trees besides natural number. It also does not explicitly mention resource bounds. Thus, if a programming language were developed out of this characterization it would give the user the illusion of being able to write code of arbitrary time complexity.

My Master's project is to develop a subset/variant of C++ guaranteed to be polynomial time. The idea is to add a keyword to C++ called ``polynomial'' which one could tag functions or member functions with. The functions/member functions taged with the polynomial keyword promise to run in polynomial time in their input parameters. I would write a translator using Lex and Yacc from our ``feasible C++'' to regular C++ that translates code not contained in such a polynomial block verbatim into our target. For code in a polynomial block, the code will be parsed to make sure it satisfies the constraints of feasible C++ and, if so, the code will be converted to usual C++. If the code does not satisfy the constraints of feasible C++, an error message will be given. The point of this is that if the translator successfully translate such functions without errors, it would then have verified that the algorithm is in fact a polynomial in its input parameters. Otherwise the parsed code is not polynomial in its input parameters.

CS297 Results

• Researched and studied the Turing machine basics, and wrote a program to simulate a Turing machine which can multiply two integers.
• Researched and studied Lex and Yacc, and wrote a program to parse the ShML ( a shape make up language) file.
• Researched and studied the book [Pap94] to understand the properties of computational complexity classes.
• Researched and studied the paper [C99] to understand different computation models and function algebras.
• Researched and studied the book [B93] and defined a set of restrictions which can be applied in C++ to guarantee the polynomial computation.
• Partially implemented a translator to recognize and validate the polynomial key words in C file.

Proposed Schedule

Key Deliverables:

• Software
  • A translator consists of two parts: a lexical scanner and a parser. The lexical scanner identifies blocks of C++ code tagged with keyword .polynomial.. The parser checks the polynomial block against a preset collection of rules to validate if the block of code can be computed in polynomial time. A C++ file consists of preprocessors, variable declarations, function calls, function prototypes, assignments, switch statements, while loops, for loops, etc. The lexical scanner recognizes keywords of those statement using tokens. The tokens are .#., INCLUDE, FOR, WHILE, SWITCH, CASE, INT, FLOAT, DOUBLE, INT, CHAR, STRING, VOID, WHILE, IF, ELSE, .(., .)., .;., .{., .}., .=., etc. The code which is successfully parsed is guaranteed to be polynomial time.
• Report
  • The background information and the motivation behind the study of our research topic.
  • A detailed description of the architecture of the proposed feasible C++, the tokens, and the grammar to validate polynomial C++ functions/member functions.
  • Results of some tests on development time of some programmer using our program. We will choose two teams, one team is going to use our program while another team is not. The results will show us how our program can improve the work efficiency.

Innovations and Challenges

• This project applies ideas which have been previously done for more obscure language to a more commonly used language C++. C++ is frequently used now. So our results will have a greater chance of actually being used.
• Previous work in the area has mainly been done with functional language. As C++ is imperative with many quirky features, our task will be harder.
• Writing such a preprocessor itself is a challenging task.

References:

[B93] Bjarne Stroustrup. The C++ Programming Language. 1993.

[BC92] Stephen Bellantoni and Stephen Cook. New recursion-theoretic characterization of the polytime functions. Computational Complexity, 2:97-110, 1992.

[C99] P.Clote. Computation models and function algebras , Handbook of Computability Theory, ed. E.R. Griffor, Elsevier Science B.V. (1999). pp. 589--681.

[C64] Cobham, A. The intrinsic computational difficulty of functions. PROC. 1964 INTERNAT. CONGR. FOR LOGIC, METH., AND PHILO. OF SCI., North-Holland, Amsterdam, pp. 24--30.

[H02] Martin Hofmann. The strength of non-size increasing computation. Principles of Programming Languages. p. 260--269. ACM press. 2002.

[L93] Daniel Leivant. Stratified Functional Programs and Computational Complexity. In Proc. 20th IEEE Symp. on Principles of Programming Languages, 1993.

[LMB92] lex & yacc. Levine, Mason, and Brown. O'Reilly & Associates, Inc. 1992.

[Pap94] Computational Complexity. C.Papapdimitriou. Addison Wesley. 1994.