递归程序设计方法的分析探讨

递归是设计程序的一种重要方法,文中对递归的定义及递归的基本条件进行了分析,给出了递归程序设计的基本方法,并结合数据结构中二叉树遍历和单链表结点输出的实例进行了验证,最后对递归程序进行了深度分析,说明了递归是一种有效的程序设计方法。     

一种包含异常传播的类间数据依赖分析方法

类间数据依赖分析是类间数据流测试的基础。本文通过分析类簇级测试中的异常传播对程序数据依赖的影响,提出一种包括异常结构在内的类间C++程序数据依赖分析方法,根据类间关系增量式地构造类间数据依赖图,并给出类间数据依赖图的构造算法。最后,在程序切片中应用了该数据依赖分析方法。结果证明,该方法通过分析异常传播对数据依赖的影响能够带来切片精度的提高。     

一种Java程序Chopping方法

程序Chopping对于程序理解、分析、调试、测试等具有重要的意义。已有的Chopping方法主要基于相互连接的系统依赖图(SDG),对于大程序这种SDG描述通常非常复杂,易导致程序Chopping结果不准确。针对这一问题,基于带标签的Java程序描述方法,提出一种Java程序Chopping方法。该方法利用这种描述附带的程序依赖信息,分析参数依赖关系,并在此基础上给出Chopping算法。此程序Chopping方法能把Java程序方法间的程序Chopping问题转换到Java程序方法内进行分析,程序依赖图具有结点少、可重用、可并发构造等优点。最后通过实例和实验给出程序Chopping方法的实施过程及有效性。     

适用于分布式静态检测的Java代码依赖性分析技术

为满足Java静态分布式检测系统对Java程序源代码解耦分包的需求,解决代码检测单节点单进程运行耗时过长问题,实现分布式检测系统单任务多节点并行运行的目的,本文提出了Java源代码文件间依赖性分析方法.该方法以生成源代码文件抽象语法树的方式抽取文件文本信息,遍历分析抽象语法树,获取文件与其他源代码文件类依赖关系,再通过定位类所在的文件方式得到文件与文件之间依赖关系.同时,以无入边顶点的带环有向图表示文件间依赖关系图,本文提出的方法基于该图进行了文件间解耦的分析.最后,通过对示例程序逐步剖析的实验以及对数个开源工具源代码解耦拆分的实验,验证了本文提出的文件间依赖性分析方法的可行性.     

递归程序变换及其实验

递归程序变换是软件自动化研究中程序变换途径的一种方法。本文介绍了递归程序等价变换的一系列模式以及根据递归程序变换基本思想而构造的人-机交互实验系统XDPTS的梗概。     

自动分析递归数据结构的归纳性质

本文提出了一种对递归数据结构的归纳性质进行自动化分析的框架.工作分为三个主要部分.首先,它将递归数据结构的归纳性质分为两个主要类别,并提出对应的处理模式,从而帮助简化对于程序中的递归数据结构上的相关性质的分析.其次,提出了一种称为分割与拼接的技术来发现和描述递归数据结构是如何被程序修改的：递归数据结构首先被分割为若干个互不相交的片段,然后这些片段以新的方式重新拼接在一起,形成一个新的数据结构.这个技术的重点在于如何将程序原有的性质保留下来,从而为后面的分析过程所使用.最后,提出了一种调用上下文敏感的程序摘要过程间分析方法.案例分析和实验结果表明我们的分析框架可以有效地分析递归数据结构的归纳性质,并生成对程序证明过程有用的断言.     

单线程程序到多线程程序的自动转换

给出了一种将单线程程序自动变为多线程程序的一种方法.该方法基于依赖性分析,将依赖性分析的结果用有向无环图表示出来,然后将有向无环图分解成多个存在依赖关系的集合,同一集合内的元素却不存在依赖关系,它们之间是可以并行执行的,集合间是有执行先后顺序的.然后将各个集合看作各个并行域,并行域内部的程序并行执行,处理并行域的时候,可以用各种模型,如:Thread and Lock,OPENMP等,最后生成相应的并行程序.     

形式推导支持的递归程序向非递归程序的转换

本文提出一种递归消除的方法,适于一类基于递归数据结构的程序。该方法将递归程序作为初始规约,以求解过程的状态变迁序列作迭代模式;通过数据展开和变换实现初始规约向基于序列描述规约的变换,继而用PAR形式推导出序列规约的递推关系,并以之为核心近乎机械地构造出非递归算法。树和图的两个算法实例说明了本方法的有效性。     

一种C++程序的分层切片方法

该文介绍了一种C++程序的分层切片方法。通过构造系统程序层依赖图、类层依赖图、方法层依赖图和语句层依赖图,对C++程序进行分层切片,有效地表示了C++中的单重继承、多重继承、多态和动态绑定,该方法比其它C++切片技术更清晰地描述了C++程序中类之间的各种关系和消息传递机制。     

FORTRAN语言递归调用的一种方法

为了能在IBM PC的FORTRAN语言中实现递归算法,本文详细分析了在IBM PC上,FORTRAN语言调用子程序的全过程,并在此基础上提出了一种用FORTRAN语言作递归调用的方法。附录中给出了有关的实例。     

一种并发程序依赖性分析方法

并发程序的依赖性分析是并发程序分析，理解，调试，测试和维护的重要手段，由于并发程序执行的不确定性，目前，尚有很多难点有待解决，针对Ada任务机制，首先提出了一种简洁，有效的并发程序表示方法－并发程序流图，然后讨论了由任务间同步引起的同步依赖和由访问共享变量引起的任务数据依赖，建立了并发程序依赖图，并在此基础上给出了一种有效的并发程序依赖性分析算法，得到一个比较精确的依赖性，较好地解决了并发程序依赖关系不可传递性问题。     

软件流水领域多维数组数据相关性的测试

体差不等式测试为适用于软件流水领域的高维数组数据相关性分析算法,通过使用更严格的限制条件,该算法可以获得比传统数据相关性分析方法更精确的结果。文章展开该算法的实验研究。实验表明,虽然体差不等式测试算法只能针对实可行解域进行数据相关性分析,但所得到的结果仍然与实际情况相吻合。对于科学计算循环中出现的大多数数据相关性判定问题,使用体差不等式测试算法可以获得很好的效果。     

Optimization of program recursive function calls analysis method

Static analysis can be classified into intra-procedural analysis and inter-procedural analysis-by-analysis objects. Inter-procedural analysis need to analyze the whole program adopting bottom-up parsing algorithms. Inter-procedural analysis can be converted to intra-procedural analysis by logging the context of follower’s function call in bottom-up analysis. However, the existence of recursive function calls in program increases the difficulty of inter-procedural analysis, which affects the detection accuracy of static analysis to some extent. An optimal method for analyzing the recursive function calls of program is presented in this paper. This method can lift the recursive function calls in function call graph of the program to be analyzed on the premise that vital function calls will be preserved. In this way, the false negative rate and false positive rate of program static analysis can be reduced and the accuracy of program security check can be improved.     

State dependency probabilistic model for fault localization

ContextFault localization is an important and expensive activity in software debugging. Previous studies indicated that statistically-based fault-localization techniques are effective in prioritizing the possible faulty statements with relatively low computational complexity, but prior works on statistical analysis have not fully investigated the behavior state information of each program element.ObjectiveThe objective of this paper is to propose an effective fault-localization approach based on the analysis of state dependence information between program elements.MethodIn this paper, state dependency is proposed to describe the control flow dependence between statements with particular states. A state dependency probabilistic model uses path profiles to analyze the state dependency information. Then, a fault-localization approach is proposed to locate faults by differentiating the state dependencies in passed and failed test cases.ResultsWe evaluated the fault-localization effectiveness of our approach based on the experiments on Siemens programs and four UNIX programs. Furthermore, we compared our approach with current state-of-art fault-localization methods such as SOBER, Tarantula, and CP. The experimental results show that, our approach can locate more faults than the other methods in every range on Siemens programs, and the overall efficiency of our approach in the range of 10–30% of analyzed source code is higher than the other methods on UNIX programs.ConclusionOur studies show that our approach consistently outperforms the other evaluated techniques in terms of effectiveness in fault localization on Siemens programs. Moreover, our approach is highly effective in fault localization even when very few test cases are available.     

基于近似函数依赖的关系数据属性权重评估方法

在现实应用中,一些关系数据的规范化程度不高,往往存在数据冗余和不一致现象。为了有效评估此类数据 中的属性重要程度,提出了一种基于近似函数依赖的属性权重评估方法。该方法基于一致集的概念导出最大集,生成 最小非平凡函数依赖集,从而找出属性之间的近似函数依赖关系,进而求出近似候选码和近似关键字,在此基础上根 据属性支持度计算属性权重。实验结果和分析表明,提出的属性权重评估方法能够合理地获取关系数据中的属性重 要程度,算法具有较好的稳定性和较高的执行效率。     

Supra-RPC: Subprogram parameters in remote procedure calls

Remote-procedure calls (RPCs) allow distributed, high-level language programs to communicate and synchronize in the usual manner via subprogram calls. One of the great challenges in RPC research is to preserve the traditiional call semantics despite the distribution and heterogeneity of the new environment. The main contribution of SUPRA-RPC is in addressing the passing of subprograms as RPC parameters. In doing so, SUPRA overcomes a number of technical difficulties, stemming from scoping, side-effects and other sources. Since supporting subprogram RPC parameters is harder than supporting non-subprogram RPC parameters, the three (of six) components of the SUPRA architecture extend in novel ways the traditional functionality found in their counterparts in other RPC systems. The SUPRA stub generator extracts information not only from remote entry interfaces, but from any scope potentially referenced by a subprogram passed as an RPC parameter. In addition to the usual call- and accept-stubs and the marshaling and unmarshaling routines, the generator constructs out-of-scope access stubs, callback' and callback-handling-stubs, and modified parameter subprograms and others. The SUPRA run-time support manages a run-time symbol table to keep track of referencing environments and out-of-scope objects. When an out-of-scope object is unavailable for access or execution on the server, the object is reached by a synchronous, ‘under-the-covers’ callback. The SUPRA process management supports servers with independent threads of control, manages (possibly nested) callbacks and pools of callback handler threads, and maintains correct identification of thread-initiated calls or callbacks. A SUPRA prototype has been implemented on Sun Unix workstations. The prototype supports C, C++ and CommonLisp programs. A prototype graphical demonstration has been implemented as well, that represents RPC concepts in terms of common life objects and situations.     

Computer Networks

Computer networks have the ability to bring the power of large machines to work on a single problem and to provide reliable computer services to large populations. They also may become an unmanageable structure that can cripple itself in a fashion akin to the great Northeast power failure in 1965. Imagine the following sequence: computer X does not have the sine subprogram but relies on computer Y for it; computer Y on the other hand solves the sine subprogram using the cosine subprogram which it doesn't have; computer Y therefore calls X for a cosine; X solves for cosine using sine which it asks Y for.& Of course, you say, no computer network would be so simplistic. But would you guarantee it could never happen for any set of computer resources among N computers-and that the network might not head for the buried recursive disaster like a lemming for a cliff?     

基于符号运算的归纳变量识别与约化

针对归纳变量的识别及归约问题提出一种基于符号运算的新算法。通过初始变量替换赋值语句中的右值,用以表达变量间的迭代与依赖关系,由此建立有向依赖图用于识别归纳变量。为归纳变量构建递归方程组并利用符号运算进行求解,获得独立的仅依赖于迭代次数的数学形式。实验结果表明,该方法适用于各种复杂的归纳变量,能够解决现有算法无法处理的一些问题。     

基于EFSM模型的等价类测试

等价类测试是有效减少测试用例而又较小地影响测试效果的一种高效的测试方法，但是对于测试者来说，寻找一种等价类测试的划分方法十分重要，本文提出了一种基于EFSM（Extended Finite State Machine）模型的等价类测试划分的方法，通过对EFSM模型数据依赖和控制依赖分析，给出了等价类测试划分的具体方法和算法，并给出了等价类划分方法的完备性和无冗余性证明。     

C程序单元级依赖性分析

程序依赖性分析是软件分析的一个基本内容，目前的相关工作大多集中在语句级的分析方面。人们同样需要单元级的依赖信息来考察单元间的信息流向及整个程序的构架。本文针对C程序中函数间的调用依赖、参数传递依赖、全局数据依赖以及文件间的包含依赖和外部变量定义依赖进行了分析，并提出单元依赖图表达这些关系。基于此图，本文采用基于信息论的方法度量了单元间的耦合性。单元依赖图中保留的函数调用间的互斥关系提高了度量的准确性。相关的分析思想和技术适用于分析使用其它高级程序设计语言编写的软件。