416 Journal of Software 4(3) 2003,1. Java, Java, Java : ; ; ;Java : TP311 : A (binding time analysis ), (partial evaluation)., [1~3]., C Java, Java.,.

Size: px

Start display at page:

Download "416 Journal of Software 4(3) 2003,1. Java, Java, Java : ; ; ;Java : TP311 : A (binding time analysis ), (partial evaluation)., [1~3]., C Java, Java.,."

钻奄云
5 years ago
Views:

1 /2003/14(03) Journal of Software Vol.14, No.3 +,, (, ) A Technology of Binding Time Analysis for Object-Oriented Programming Languages LIAO Hu-Sheng +, TONG Zhao-Feng, WANG Zhong (College of Computer Science, Beijing Polytechnic University, Beijing , China) + Corresponding author: Phn: ; , Fax: , liaohs@bjpu.edu.cn Received ; Accepted Liao HS, Tong ZF, Wang Z. A technology of binding time analysis for object-oriented programming languages. Journal of Software, 2003,14(3):415~421. Abstract: A technology of binding time analysis for implementing partial evaluation of object-oriented programming languages is proposed in this paper. By tracing context-sensitivity of reference variables and pointer variables, the new approach can deal with elements of partly static data structure, such as attributes of each object and elements of each array. The new approach uses a two-level environment to hold states for static variables and local variables. The objects created at different program points are represented by a kind of specific handle. The state of a reference variable is represented by a set of such handles. The algorithm of a forward analysis and backward analysis are presented. They are used to annotate source program, with environment to trace binding time of various kind of variables including identifier of array, object and reference. The binding time analysis has been implemented for Java. It is able to analyse most single thread Java programs and support partial evaluation for Java with higher performance. Key words: binding time analysis; partial evaluation; object-oriented programming language; Java language :,.,,.,,., Supported by the National Natural Science Foundation of China under Grant No ( ) ; the Natural Science Foundation of Beijing City of China under Grant No ( ); the Assisting Project of Ministry of Education of China for Backbone Teachers of University and College (. : (1954 ),,,,, 转载

2 416 Journal of Software 4(3) 2003,1. Java, Java, Java : ; ; ;Java : TP311 : A (binding time analysis ), (partial evaluation)., [1~3]., C Java, Java.,., (context sensitivity),,. Java, Java. 1,,, ( ), ( ) (residual program)., 1 x,y,, Table 1 Case on binding time analysis 1 void fun (int x, int y) void fun (int x S,int y D ) MyObj o; MyObj o SD ; o=new MyObj( ); o SD = SD new SD MyObj( ); o.a=x; o.a SD = SD x S ; while (x>10) while S (x S > S 10 S ) o.a=o.a+x; o.a D = D o.a D + D x S ; o.a=o.a*y; o.a D = D o.a D * D y D ; x=x 2; x S = S x S S 2 S ; S, D, SD.,,,,., a 4~6, SD,S D.,. C,,,,.,.. 2,,: [4,5]

3 : 417 (1),.. ;. (2),,,.,,. (3) ( ),.,.,,.,, : (1), ;,,. ( ),. (2), ( ) ( ) ;. (3). 1,,.,,. (4) 2.,,,., 2. 1,, ; 2,, 1 o 4, 4. 2, SD Table 2 Results of two parse phases in binding time analysis 2 void fun (int x S,int y D ) MyObj o; o 4 = 4 new MyObj( ); o.a= S x S ; while S (x S > S 3 S ) o.a= D o.a D + D x S ; o.a= D o.a D * D y D ; x= S x S S 2 S ; void fun (int x S,int y D ) MyObj o SD ; o SD = SD new SD MyObj( ); o.a SD = SD x S ; while S (x S > S 10 S ) o.a D = D o.a D + D x S ; o.a D = D o.a D * D y D ; x S = S x S S 2 S ;. 1,,,S D D;,.,,.

4 418 Journal of Software 4(3) 2003,1 2,., SD.,, SD;,,. 3 3 Java,. 4, ( 1 ) ( 2 ). 4 ; v,,. State : Bta. Java, Table 3 Subset of Java language 3 Java Syntax domain: stmt Stmt statement expr Expr expression Id Iden identifier const Const constant Abstract syntax: stmt Id=expr; stmt Id 1=New Id 2[expr]; array (including object array) stmt Id 1=New Id 2(expr 1,,expr n); object construction stmt Id 1.Id 2=expr; object s member stmt Id[expr 1]=expr 2; stmt Id(expr 1,,expr n); method invocation for this class stmt Id 1.Id 2(expr 1,,expr n); method invocation stmt If (expr) stmt 1 Else stmt 2 condition statement stmt While (expr) stmt loop statement stmt stmt 1 stmt n compound statement stmt Type Id; declaration statement expr const constant expr Id expr Id 1.Id 2 object s member expr Id [expr] element of array expr UnOp expr unary operation (including cast) expr expr 1 BinOp expr 2 binary operation expr (expr), ;.,.,,,.,.,,. 5 1.,,.

5 : 419 Table 4 Annotation for an expression in binding time analysis 4 Representation for value: State=Bta+Iden * state bt Bta annotation bt::=s D SD Key Iden+Iden.Iden+Iden[Expr] v Env=Key State environment evaluation rules for expression: EB [Expr] Env Bta EB [const] v =S EB [Id] v =v [Id] variable EB [Id 1.Id 2] v =v [Id 1.Id 2] object s member EB [Id [expr]] v =v [Id[expr]] element of array EB [UnOp expr] v =EB [expr] v EB [expr 1 BinOp expr 2] v =EB [expr 1] v EB[expr 2] v EB [(expr)] v =EB [expr] v Comment: Initialization: The initial value of v is a two -level environment for the current method Function: bt 1 bt 2 evaluation of the least-upper boundary of the two states Table 5 Forward analysis algorithm for a statement in binding time analysis 5 Representation of value: in Env Premise environment for analyzing the current statement out Env Post environment for analyzing the current statement Forward analysis rules for statement: SFB [Stmt] Env Env SFB [Id=expr;] in=in++ id bt where bt=eb[expr]in SFB [Id 1=New Id 2 [expr];] in=in++ id 1 bt where bt=in[new.where] SFB [Id 1=New Id 2 (e 1,,e n);] in out.getoutenv(id 2,Id 2) where out=in++ id 1 in[new.where] SFB [Id 1.Id 2=expr;] in in++ Id 1.Id 2 bt where bt=eb [expr] in SFB [Id [expr 1]=expr 2;] in in++ Id[expr] bt where bt=eb[expr 1] in EB [expr 2] in SFB [Id(e 1,,e n);] in in.getoutenv(this,id) SFB [Id 1.Id 2(e 1,,e n);] in in.getoutenv(id 1,Id 2) SFB [If (expr) stmt 1 Else stmt 2] in if bt==s then out else out.setdyn(stmt 1, stmt 2) where bt=eb [expr] in out=sfb[stmt 1] in SFB[stmt 2] in SFB [While (expr) stmt] in if bt==s then out n else out n setdyn(stmt) where bt=eb[expr] out n; in 1=in out i=sfb [stmt] in i for i=1,,n and in n=out n SFB [s 1 s n] in=out n where out i=sfb [s i] out i 1 for i=1,,n out 0=in SFB [Type Id;] in in++ Id null Comment Initialization: the initial value of in is a two-level environment for the current method with each parameter s state, which is set in analysis for method. Auxiliary function: in++ id bt to update environment by assigning id s state with bt. env.getoutenv(class,method) to get the post environment for the method class.method.env.setdyn (stmt) to assign dynamic states of the variables those are assigned in the statement stmt.bt 1 bt 2 evaluation of the least-upper boundary of the two states.in 1 in 2 union of the two states. Attribute: New.where to representation the position of the statement in program s text.

6 420 Journal of Software 4(3) 2003,1,, ;,,,.,.,.,.,,.,.,,., 1 7 o.a, 8,,.,,, ;,..,., :(1) ;(2). n, m k., 3.,,, O(n+m*k).,.,,.. 4 Java Java. Java. 1, Java Java 3.,,,.,,., Java. Program transformation Java source Java subset source for methods Requirement for PE Forward analysis PE pattern for methods Java program with state Backward analysis Java program with annotation Fig.1 Binding time analysis system for Java 1 Java

7 : 421 5,,,, References: [1] Anderson LO. Program analysis and specialization for the C programming language [Ph.D. Thesis]. Copenhagen: Department of Computer Science, University of Copenhagen, [2] Consel C, Noel F. A general approach for run-time specialization and its application to C. In: Proceedings of the Conference Record of the 23rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. St. Petersburg Beach, FL: ACM Press, ~156. [3] Grant B, Mock M, Philipose M, Chambers C, Eggers SJ. Annotation-Directed run-time specialization in C. In: ACM SIGPLAN Symposium on Partial Evaluation and Semantice-Based Program Manipulation. Amsterdam: ACM Press, ~178. [4] Hornof L, Noye J, Consel C. Effective specialization of realistic programs via use sensitivity. Lecture Notes in Computer Science, 1997,1302:293~314. [5] Hornof L, Noye J. Accurate binding time analysis for imperative languages: flow, context and return sensitivity. In: ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 97). Amsterdam: ACM Press, ~ ChinaCrypt ~ 7 EI Word/PDF Tel: Tel: lixiang@gzu.edu.cn kfchen@mail.sjtu.edu.cn

中文模板

中文模板 1000-9825/2003/14(03)0415 2003 Journal of Software 软件学报 Vol.14, No.3 面向对象程序设计语言的绑定时间分析技术廖湖声 +, 童兆丰, 王众 ( 北京工业大学计算机学院, 北京 100022) A Technology of Binding Time Analysis