CS298 Proposal
Feasible C++
Yan Yao (ckctyy@hotmail.com)
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
Week 1 (Jan 19- 24) | Prepare CS298 proposal
|
Week 2-3 (Jan 27-Feb 7) | Design data structures and develop a set
of rules to apply necessary restrictions to the assignment and switch
statements.
|
Week 4-5 (Feb 10-21) | Design data structures and develop a set
of rules to apply necessary restrictions to the for loops.
|
Week 6-7 (Feb. 24-Mar 7) | Design data structures and develop a set
of rules to apply necessary restrictions to the while and goto statements.
|
Week 8-9 (Mar 10-21) | Add more restrictions. Complete the
design, and enhance the final coding of the whole project.
|
Week 10-11 (Mar 24-Apr 4) | Write up CS 298 report
|
Week 12-13 (Apr 7-18) | Submit cs298 draft to the committee. Clean
up code.
|
Week 14-15 (Apr 21-May 2) | Prepare final presentation.
|
Week 16 (May 5- 9) | Finalize the report.
|
Week 17 | Oral defense.
|
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.
|