（计算机软件与理论专业论文）认知容易度驱动的程序理解过程.pdf

u s gc o g n i t i v ee a s i n e ssm e t r i c t od 对v ep r o g ra mc o m p i 冱h e n s i o n ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y nm a n m a n s u p e r v i s e db y p r o f l ib i x i n s c h o o lo fc o m p u t e rs c i e n c ea n de n g i n e e r i n g so u t h e a s tu n i v e r s i t y a p r i l2 0 1 0 2洲8咖5 l67，iiil-y 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 耻日期：2 血扯 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：艘导师签名：拯 日 摘要 摘要 程序理解是软件维护的重要阶段，程序员对程序的理解程度直接影响到维护工作的正确 性和效率。由于在设计程序时，尤其是使用面向对象方法设计时，功能行为相关的代码通常 会被分散在程序中的各个角落，这增加了理解程序的难度，也使得理解者感到无从下手。因 此很多研究人员不断地探索寻找有效的方法辅助程序员理解程序。然而很少有人致力于研究 如何利用已有的知识快速有效地结块抽象出新知识。 本文提出认知容易度概念，表示当前理解阶段程序员理解程序中某个未理解部分的容易 东南大学硕上学位论文 a b s t r a c t p r o g r a mc o m p r e h e n s i o ni s o n eo ft h em o s tc r i t i c a lp h a s e si ns o f t w a r em a i n t e n a n c e 1 1 1 ee x t e n tt o u n d e r s t a n d i n gt h ep r o g r a mi n f l u e n c e st h ee f f i c i e n c ya n dp r e c i s i o no fs o f t w a r em a i n t e n a n c e d u r i n gp r o g r a m d e s i g n i n g ，t h ec o d e sh a v i n gr e l a t e df u n c t i o na n db e h a v i o ra r eo f t e ns c a t t e r e di nd i f f e r e n tp a r t so fp r o g r a m ，w h i c h i n c r e a s e st h ed i f f i c u l t yo fu n d e r s t a n d i n gp r o g r a m ，a n df u r t h e ro b f u s c a t e sp r o g r a m m e r s t h e r e f o r e ，an u m b e ro f r e s e a r c h e r st r yt of i n da ne f f i c i e n tm e t h o dt oa s s i s tp r o g r a m m e r sw i t hp r o g r a mc o m p r e h e n s i o n h o w e v e r , f e w r e s e a r c h e sf o c u so nh o wt ou t i l i z ee x i s t i n gk n o w l e d g et oc h u n ka n da b s t r a c tn e wk n o w l e d g ee f f e c t i v e l ya n d r a p i d l y t h ep a p e rp r o p o s e st h ec o n c e p to fc o g n i t i v ee a s i n e s sd e g r e e ，w h i c hr e p r e s 锄t st h ed e g r e eo fe a s i n e s sa b o u t u n d e r s t a n d i n gt h en o n - u n d e r s t o o dp a r to fp r o g r a mi nt h ec u r r e n tc o m p r e h e n s i o np h a s e t oq u a n t i f yc o g n i t i v e e a s i n e s sd e g r e e ，w et a k ef u n c t i o na sau n i ta n dd i v i d et h ef u n c t i o n si np r o g r a mi n t ot w op a r t s ：u n d e r s t o o dp a r t s ( a l r e a d yu n d e r s t o o db yp r o g r a m m e r s ) a n dn o n u n d e r s t o o dp a r t s ( h a v en o tb e e nu n d e r s t o o db yp r o g r a m m e r sa n d n e e d c o g n i z i n g ) m o r e o v e r , t h ec o a r s e g r a i n e d c a l l g r a p hs l i c i n gt e c h n i q u e a n dt h ei n t r a - p r o c e d u r a l c o a r s e - g r a i n e ds l i c i n gt e c h n i q u ea r ea d o p t e df o ro b t a i n i n gt h er e l a t i o n s h i pa m o n gf u n c t i o n s t h e n ，t h ec o g n i t i v e d e g r e eo fn o n - u n d e r s t o o dp a r ti sc a l c u l a t e dc o m b i n e dw i t hu n d e r s t o o dp a r t u s i n gc o g n i t i v ed e g r e et od r i v ep r o g r a mc o m p r e h e n s i o nc a ng u i d ep r o g r a m m e r st ou n d e r s t a n dp r o g r a m g r a d u a l l y , t om a k es u r et h ec o d eu n d e r s t o o di ne v e r yp h a s ei st h ee a s i e s ti nt h er e m a i n d e rp a r t s m e a n t i m e ，0 1 1 1 a p p r o a c hc a np r o v i d ed i f f e r e n tg u i d a n c ef o rd i f f e r e n tp r o g r a m m e r s t oa s s e s st h ev a l i d i t ya n dp r a c t i c a b i l i t y , w e d e v e l o pat o o lc e p l u n g i nt os u p p o r tp r o g r a mc o m p r e h e n s i o na n dp e r f o r me x p e r i m e n t a la n a l y s i si nt h ee n do ft h e p a p e r k e yw o r d s ：c o g n i t i v ee a s i n e s sm e t r i c ，p r o g r a mc o m p r e h e n s i o n ，p r o g r a ms l i c i n g ，c a l lg r a p hs l i c e i i 第一章绪论 目录 摘要i a b s t r a c t i i e jj i 2 1 第一章绪论1 1 1 研究背景。l 1 2 研究现状l 1 2 1 认知过程的研究2 1 2 2 半自动化工具的研究2 1 3 论文主要工作一3 1 3 1 研究内容3 1 3 2 研究目的与意义3 1 4 论文章节安排4 第二章程序理解和程序切片5 2 1 程序理解认知模型5 2 1 1 自顶向下模型5 2 1 2 自底向上模型6 2 1 3 机会主义模型6 2 1 4 ，j 、结7 2 2 程序切片7 2 2 1 程序切片的分类7 2 2 2 程序切片的计算方法9 2 2 3 调用图切片9 2 2 4 粗粒度程序切片9 2 3 基于程序切片的程序理解认知过程一1 0 第三章认知容易度1 2 3 1 认知容易度概念1 2 3 2 构造理解依赖图1 2 3 2 1 计算调用图粗粒度切片1 3 3 2 2 删除冗余结点1 4 3 2 3 扩充理解依赖图1 5 3 3 计算认知容易度1 5 第四章使用认知容易度驱动程序理解1 7 4 1 动机1 7 4 2 原理与过程1 7 4 3 方法示例1 8 4 3 1 场景描述1 8 4 3 2 过程示例1 9 4 3 3 方法评估2 0 第五章支持程序理解工具的设计与实现2 2 5 1 工具设计2 2 5 1 1 工具简介2 2 5 1 2 框架设计2 2 东南大学硕士学位论文 5 2 上具实现2 3 5 2 1 开发环境2 3 5 2 2 程序分析器的实现2 5 5 2 3 认知容易度计算器的实现2 5 5 2 4 界面显示的实现2 6 第六章实验研究2 9 6 1 案例分析2 9 6 2 参数分析3 0 6 3 工具评估3 2 第七章总结与展望3 3 7 1 主要j ：作总结3 3 7 2 未来工作展望3 3 致谢3 4 参考文献3 5 作者简介3 8 附录a6 2 节中四种不同参数值得到的计算结果3 9 2 第一章绪论 第一章绪论 本章介绍了程序理解的研究背景和研究现状，并在此基础上提出本文的研究内容、研究 目的及意义。 1 1 研究背景 随着软件行业渗透到各个领域，越来越多的软件为了保持其有用性而需要不断地维护、 修改。在维护人员进行软件维护工作前，首先需要理解被维护的程序，以便获得足够的信息 实施维护工作。有研究表明，软件维护的总工作量大约一半被用在理解程序上【l 】。维护人员 对程序的理解程度直接影响到其工作的正确性和效率。因此程序理解是软件维护的重要阶段， 在软件维护和演化过程中起着重要作用。 程序理解的过程是程序员使用现有知识，提取程序中的各种信息，并映射到人脑中，形 成关于程序结构和功能的思维模型的过程 2 , 3 1 。在程序设计阶段，程序员将应用领域中需要完 成的功能映射为程序设计域中可运行的代码。而程序理解正是这个过程的逆过程，通过提取 并分析程序中各种实体之间的关系，形成系统的不同形式和层次的抽象表示，完成程序设计 领域到应用领域的映射。 程序理解的一大特点是高度依赖于人的思维干预，然而理解人员通常并不是程序设计人 员，由于人与人之间思维方式存在差异，个人能力、专业水平也高低不同，导致恢复程序最 初的设计模型并不是件容易的事。而且经常出现程序随着需求变更不断地演化，破坏了最初 设计的结构降低代码质量等情况，更增加了这项工作的难度。尤其是随着软件系统日益复杂， 规模也逐渐增大，程序员在面对庞大的程序时经常感觉无从下手，所以，寻找一些方法来减 轻程序员的理解负担是非常有必要的。 理解程序的主要结构和功能实现是程序理解的主要工作，需要识别程序单元，跟踪控制 流，跟踪数据流，综合程序逻辑【4 j 。程序员在理解程序的过程中，经常通过反复三个活动一 一阅读关于程序的文档，阅读源代码，运行程序【i l 一来捕捉信息。由于经常出现文档不全 或者文档过时等情况，源代码通常是信息的主要来源。程序员在阅读代码时可以通过追踪控 制流和数据流系统地理解函数的全部行为，也可以根据需要选择局部代码进行理解。有研究 表明，系统地理解可以更好地捕捉程序不同部分间的关联交互，而按需理解则很难捕捉这方 面的信息，因此系统地理解整个程序更有助于成功地完成维护工作【5 】。 在源代码中功能相关的代码经常分散在不同的位置，如果程序员仅凭借自身的直觉和经 验来选择浏览代码将会是非常低效的。因此，很多研究人员不断地研究采用什么样的方法系 统地浏览代码对于理解工作更为有效。本文也正是基于这一点展开研究工作的，通过分析程 序中函数问的关系，寻找程序中最容易理解的部分，引导程序员从程序中较容易理解的部分 着手，从而降低工作难度，提高工作效率。 1 2 研究现状 程序理解研究有两个关键难点【6 】：第一是关于程序员在理解程序时所使用的认知过程的 实证研究。第二是聚焦在开发半自动化工具来支持改善程序理解的技术研究。为了解决这两 个难点，近几十年关于程序理解的研究可以划分为两个主要方向：研究程序员是如何理解程 序的和研究支持程序理解的半自动化工具和技术。这两个方向并不是毫不相关、独立进行的， 东南人学硕士学位论文 前者是理论基础，可以为后者提供理论依据和设计指导，但是仅仅了解程序员如何认知程序 是不足够的；后者则是对前者理论的现实应用，并通过实践检验前者的理论，为进一步地探 究认知过程指引方向。 1 2 1 认知过程的研究 通过对程序员理解过程进行实验和观察研究，研究人员提出了很多认知模型来描述程序 员是怎样理解程序，如文献 7 8 】【9 】 1 0 11 1 2 】。这些模型揭示了人在理解过程中的思维方式 和行为动作，并分析可用于形成思维模型的信息结构。在这些研究的基础上，m a d s t o r e y 等人【l3 】从两个不同的层次支持不同的理解策略和减轻维护人员认知负担提出了可以 帮助构造心理模型的1 4 个认知设计元素。这些元素可以用于评估一个工具是否有助于程序理 解，从而指导辅助理解的工具的开发设计。m p r o b i l l a r d 等人【1 4 】通过分析程序观察行为和成 功修改工作的关系，研究程序员在浏览代码时哪些行为是有用的。他们从程序员的实际维护 工作中收集数据，分析有效的程序观察行为的特点，得出在程序观察阶段程序员逐行浏览代 码远远没有有计划地浏览有效率，即系统地采用方法地观察代码比随机的浏览更为有效。 1 2 2 半自动化工具的研究 支持程序理解的半自动化工具研究又可以分为两大类。一类是基于程序结构的可视化工 具。这种工具通过分析程序的结构，抽取其中各种实体，使用图形表示这些实体和他们之问 的关系，可以直观地为程序员提供不同抽象层次上的信息。早期的r a t i o n a lr o s e 工具可以从 源代码中抽象出静态设计模型，并表示为u m l 类图。为了解决图中包含过多的节点和边而 增加理解负担的问题，d a 4 j a v a 工具【l5 j 提供了递增组合图的功能，可以过滤掉不相关的节点 和边简化图形。e x t r a v i s 工具【l6 j 使用大量的顺序视图和环形束视图可视化执行轨迹。它根 据r s f 文件提供的结构信息，基本调用关系和消息调用关系，将系统中实体及其关系可视化 为环状束视图，展示父元素和子元素之间隐含的调用关系；同时大量的顺序视图提供整个执 行轨迹的概况，可以帮助用户识别感兴趣的轨迹。 另一类工具聚焦在帮助程序员导航浏览源代码，为程序员的浏览工作提供着眼点，缩小 程序员需要浏览的代码范围。w i l d e 等人在 1 7 】和 1 8 】提出一种基于分析程序执行来定位特征 的技术，将自然语言下的维护需求映射为实现对应功能的代码。随后，b i g g e r s t a f f 等人【l 州又 引入静态特征定位技术，并且设计了一个使用语法分析，简单的聚合，标识符名和浏览器识 别特征的工具。e i s e n b a r t h 等人【2 0 】结合静态和动态分析，提出一种映射代码模块和测试用例的 半自动化特征定位技术。p o s h y v a n y k 等人【2 1 】结合源代码的潜在语义索引( l s i ) 和基于场景 的概率评价( s p r ) 技术提出了p r o m s e s i r 特征定位技术，这种特征定位的结果优于仅使 用l s i 和s p r 中的任一种技术。 还有一部分研究人员尝试为程序员提取出他们在完成某个维护工作时可能感兴趣的代 码。m p r o b i l l a r d 等人【2 2 】提出一种自动生成潜在关注代码的技术。这种技术通过记录并分析 程序员在执行维护工作浏览过的所有代码，从中提取出与当前维护工作相关的代码，为下一 次执行类似维护工作提供着眼点，节省重复观察代码的时间。m k e r s t e n 等人【2 3 】开发出称为 m y l a r 的工具，这个工具通过监视程序员的行为计算程序元素的感兴趣度( d o i ) ，反映出程 序元素对于某个任务的相关性。随后，m p r o b i l l a r d1 2 4 】又基于程序的结构依赖拓扑，提出一 种自动为程序员在浏览代码提供建议的技术，帮助程序员识别更值得观察的代码。这个技术 可以根据程序员提供的感兴趣的元素集合，输出与这些元素可能相关的建议元素集合，同时 为集合中每个元素的计算一个值表示对于程序员可能感兴趣的程序。 程序切片技术最初是由w e i s e r 提出【2 5 j 用于帮助程序员调试代码的。它可以提取出与关注 2 箜二主堑笙 点有关系的代码，删除无关代码，将一个比较大的程序缩小为一个相对于关注点仍然具有相 同行为的较小程序。基于这种特性，程序员在理解程序时，结合程序切片技术可以屏蔽掉无 关代码，缩小理解范围，将注意力集中到某个更小更紧凑更利于理解的部分代码中，从而减 少工作量提高工作效率。我们将在下一章做详细的介绍。 1 3 论文主要工作 1 3 1 研究内容 在总结国内外现有的对程序理解研究的基础上，本文分析程序理解认知模型和程序切片 在程序理解中的应用，提出认知容易度概念和计算认知容易度的方法，并且将认知容易度应 用到程序理解过程中，使用认知容易度驱动程序理解。同时，根据方法实现支持程序理解工 具展开实验研究。 本文在以下几个方面展开研究： ( 1 ) 程序理解认知模型特点分析 为了帮助程序员理解程序，减轻理解负担，首先必须要搞清楚程序员是如何进行理解程 序的。程序理解认知模型正是对程序员在认知过程中使用的策略和构造思维模型时使用的信 息结构的描述，揭示了人在理解过程中的思维方式和行为动作。通过对这些认知模型的分析、 研究，我们可以找到现有技术的不足，并且提出更好的方法进行改进。 ( 2 ) 使用认知容易度驱动程序理解 为了表示程序员理解程序中某个函数的容易情况，本文提出认知容易度概念。采用调用 图层粗粒度切片技术和过程内粗颗粒切片技术寻找程序中函数之间的关系，通过分析这些关 系量化认知容易度。然后将认知容易度贯穿到整个程序理解过程中，以达到指引程序员每一 步理解方向的目的。 ( 3 ) 工具实现与实验研究 为了验证本文方法的有效性，我们开发了支持程序理解的c e p l u g i n 工具。c e p l u g i n 工具 根据我们提出的方法理论实现了认知容易度的计算。工具以源程序和程序员理解函数作为输 入，解析源代码寻找函数间的调用关系，构造函数的理解依赖图，最终计算出认知容易度值 并显示出来。最后，本文使用c e p l u g i n 工具进行实验研究，分析工具计算结果是否合理性， 同时研究在不同的情况下应该如何设置参数使用工具。 1 3 2 研究目的与意义 理解程序的过程与理解其他事物一样是一个逐步渐进的过程，程序员不是一下子就能理 解整个程序，而是由少到多，由局部到整体的理解。在这个过程中，程序员通过阅读文档、 注释，分析代码可以先理解其中的一部分代码，对代码有初步的认识。我们研究的目的就是 根据程序员已经理解的部分预测当前理解阶段中尚未理解部分的容易程度，从而引导程序员 定位下一步浏览代码的方向先理解容易理解的部分再理解较难理解的部分。随着理解的 不断推进，前期阶段较难理解的部分也会逐步变得容易理解，直到达到成熟条件为程序员所 选择。采用这种理解方式可以做到每次阅读的代码都是程序中剩余部分最容易理解的，有助 于程序员建立较快地更高层抽象，同时减少程序员浪费在盲目浏览无关代码的时问，降低工 作难度，提高工作效率。 3 东南大学硕i ：学位论文 1 4 论文章节安排 本文共分七章，各章的内容简述如下： 第一章绪论：介绍本文的研究背景和研究现状，并在此基础上提出本文的研究内容、研 究目的及意义； 第二章程序理解和程序切片：详细介绍了程序理解认知模型和程序切片，以及基于程序 切片的程序理解认知过程； 第三章认知容易度：基于程序理解认知模型和程序切片在程序理解中的应用，提出认知 容易度概念，和计算认知容易度的方法； 第四章使用认知容易度驱动程序理解：将认知容易度应用到程序理解中，详细阐述了 使用认知容易度驱动程序理解的原理与过程，并且以一个程序源代码作为示例， 展示如何在理解程序的过程中使用认知容易度； 第五章支持程序理解工具的设计与实现：介绍c e p l u g i n 工具的设计思路、主要功能、 工具框架、开发环境以及实现细节； 第六章实验研究：以j h s a 工具作为目标使用c e p l u g i n 工具进行实验研究，并且分析参 数值对计算结果的影响。最后，使用一系列认知设计元素评估工具的有效性。 第七章总结与展望：总结本文的主要工作，指出未来研究方向。 4 第- 二章程序理解和程序切片 第二章程序理解和程序切片 本章详细描述了程序理解的认知模型和程序切片的基础知识，并且将程序切片技术融入 到程序理解活动中，展示了基于程序切片的程序理解认知过程。 2 1 程序理解认知模型 程序理解的过程是一个使用已有知识学习新知识，以达到理解目的的认知过程。认知过 程是人们在心中处理知识的方式，在这个过程中，人们反复地参考已有知识和新知识来构建 大脑中对程序的思维模型。为了理解程序，相应的知识是必不可少的。程序员的知识一般可 以划分为两种类型：通用知识和特定知识【z 引。通用知识是独立于特定软件系统，与当前正在 理解的系统不相关的知识，可以是程序语言的编程知识，基本的算法设计思想等；特定知识 则是与正在理解的软件系统相关的知识，它反映了程序员对该软件系统的理解层次。在程序 理解过程中，程序员需要结合通用知识逐步获取更多的特定知识，与此同时也会产生新的通 用知识。 在认知过程中形成的思维模型是程序的一种抽象表示，是程序员大脑中对当前正在理解 的软件系统的内部的、实时的表达【2 引。它包括文本结构、程序结构块( c h u n k ) 、编程设计、 假设、标志( b e a c o n ) 、交流规则等。在理解过程中，程序员对正在理解的软件系统形成的思 维模型是不断更新的，反映了其对该程序的理解程度。 认知模型用于描述程序员在认知过程中使用的策略和构造思维模型时使用的信息结构， 揭示了人在理解过程中的思维方式和行为动作。在过去的几十年中，研究人员提出了许多描 述程序员如何理解程序的认知模型，主要可以分为三大类：自顶向下，自底向上和机会主义。 2 1 1 自顶向下模型 自顶向下模型是从理解程序的顶层细节开始，以从上到下的方式转向理解下层细节。主 要代表有b r o o k s 模型【，j 和s o l o w a y 模型引。 b r o o k s 模型把要被理解的程序的结构看作是组织成连接问题域和程序设计域的不同表 示。程序理解过程就是重新构造这些域和域之间的关系的知识的过程，这些知识为最初的系 统设计者所掌握。这种重新构造是自顶向下的，从程序做什么，如何运行开始不断地提出假 设，确认假设和细化假设，逐步恢复设计阶段所做的决策，并且通过中间领域重新创建问题 域和程序设计域的映射关系。 程序员首先根据已有知识，在理解代码过程中提出关于某个被分析的代码段的假设，这 些假设可以通过扫描代码寻找标志进行验证。随后，假设反复地被细化，产生更多的新的假 设，再次通过扫描代码进行验证。标志由实现特定数据结构和算法的代码片段组成，是辅助 认知的主要信息，同时也是驱动程序员产生进一步假设的要素。 s o l o w a y 模型适合熟悉的代码和代码类型，采用所拥有的知识公式化假设，把系统分解 成能够在代码中实现的已经知道的子系统，然后轮流分解每个子系统，直到取得实现既定功 能的一个个代码块。用这种方法构造的思维模型由目标和设计格局的层次构成，利用论述规 则把目标分解成设计格局，继而细化成更加底层的设计格局。 设计格局用于描述系统的设计目标和构成，该模型的设计格局可以分为三种类型：战略 性格局，策略性格局，实现性格局。战略性格局描述程序或算法中的整体策略和独立于语言 5 壅堕盔兰堡占堂篁笙苎 的那部分行为；策略性格局是解决某个问题的局部策略，包含与具体语言无关的算法规格说 明；实现性格局依赖具体的语言，主要用于描述策略性格局的具体实现，包括实际的代码片 段。 2 1 2 自底向上模型 自底向上模型是从程序的底层细节入手，由代码中的低层结构迭代的组成更有意义的高 层结构，然后再按照自底向上的方式，组合成更大的结构，直到程序被完全理解。主要代表 有p e n n i n g t o n 模型【9 ，10 1 。 p e n n i n g t o n 模型提出了两个不同的思维表示：程序模型和状态模型。当程序员遇到陌生 的代码时，首先创建控制流程序抽象，这种思维表示属于程序模型，并且通过标志( b e a c o n ) 自底向上的构建，用来标示程序中的代码控制基本块。在程序模型的构建过程中，需要外部 表示和文本结构，其中外部表示包括程序代码、设计文档、用户手册等，而文本结构包括基 本控制结构、程序结构、程序语法、编程惯例、控制顺序知识等。 在程序模型中的控制流抽象被建立后，理解将进入状态模型所描述的领域。状态模型是 数据流功能的抽象，其构建需要现实世界中的领域知识，如理解某个具体的操作系统时，其 应用领域知识包括操作系统的基本组成部分、各个部分的功能以及如何协作等。在状态模型 的构建过程中需要与外部的系统表示进行匹配，通过交叉引用和聚合结块的方式产生新的更 高层的设计推测并能用于指导后续的假设验i i e t 2 6 1 。匹配的信息来源包括程序模型、外部表示、 设计知识和领域知识等。通过交叉引用寻找程序中代码语句之问的相互关系，并构成微观结 构；通过聚合结块操作微观结构被构建成宏观结构，这些宏观结构被保存在长期记忆中，将 应用于后续更大规模的聚合结块操作。 虽然程序模型先于状态模型被构建，但是在构造状态模型的过程中如果发现了程序模型 中的矛盾之处，仍可以返回到程序模型，并对之进行调整。交叉引用映射能够允许程序员从 过程级、语句级抽象直接映射到功能级系统抽象，达到程序模型和状态模型之间的映射。更 高层次的设计计划能够驱动程序员重新考虑程序模型，并对模型做必要的改变或增强【l 列。 2 1 3 机会主义模型 机会主义模型是指程序员在理解过程中既使用自顶向下又使用自底向上，将二者灵活的 结合使用。主要代表有l e t o v s k y 模型】和v o nm a y r h a u s e r 和v a n s 的集成模型【1 2 】。 l e t o v s k y 提出的认知模型中包含一个重要的知识库，所以又把这个模型称为基于知识的 认知模型。他把程序员看作是一个基于知识的理解器，而理解则是理解器通过自上而下或自 下而上的方式去探索标志( b e a s o n s ) 以此来引导理解的过程。l e t o v s k y 模型主要由三个组成部 分构成： ( 1 ) 知识库：包括程序员的专业技能和背景知识，例如程序员的编程经验、问题领域知识、 交流规则、编程计划，和程序目标等知识； ( 2 ) 思维模型：是程序员对程序内容理解的内部表示，可以分为三个层次：规格层、实现 层和注释层。规格层表示程序目标，是程序的最高抽象层次；实现层表示数据结构、 函数等低层实体，是程序的最低抽象层次；注释层负责连接规格层的每一个目标和实 现层的具体实施，是介于规格层和实现层之间的衔接层。然而这种连接可能是不完整 的，存在未知目的单元负责对这种有待解决的连接建模； ( 3 ) 同化过程：描述了思维模型是如何使用知识库，程序源代码和文档进行演化的。这个 过程可以是自顶向下的也可以是自底向上的，取决于程序员在具体理解问题时如何更 有效果的选择。 6 一 笙= 三望堡壁堡堡塑堡堡望竺 v o nm a y r h a u s e r 和v a n s 通过研究发现，在认知过程中理解会在代码、设计和应用领域知 识之间频繁地切换，并行地构建各个抽象层次被，而非单单地逐层构建。因此，他们吸取前 人对认知模型研究的合理部分，组合自顶向下的s o l o w a y 模型和自底向上的p e n n i n g t o n 模型， 形成集成模型。 集成模型有四个主要组成部分：自顶向下模型，状态模型，程序模型和知识库。前三个 反应了理解过程，第四个是构建f j 三个的必要部分，提供与当前理解任务相关的信息，并且 存储新的知识和推断。在理解过程中，三个子模型之间可以在任何时间相互切换。当遇到熟 悉的代码时，可以进入自顶向下模型，而随着理解的推进遇到不熟悉的代码时，可以切换到 程序模型或状态模型。当构建程序模型或状态模型时，程序员识别出了程序代码中某个功能 标志，这可能使程序员产生一个假设，故而会把思维引向自顶向下模型。如此反复，直至完 成理解任务。 2 1 4 小结 在实际的理解过程中，程序员并不会完整的按照某一种认知模型，很可能会充分利用发 现的线索灵活地使用多个不同的理解策略。而且，上述的理解模型中没有考虑使用支持程序 理解的工具会带来的影响。支持程序理解工具的使用可以帮助程序员更快更好的捕捉线索理 解程序，达到事半功倍的效果。 通过对这些认知模型的分析、研究，我们发现不论是哪种理解模型描述的理解过程，都 是一个在现有知识基础上构造待理解程序的新知识，并且不断聚集结块知识的渐进的认知过 程。但是现在很少有人致力于研究如何利用已有的知识快速有效的结块抽象出新知识。同时， 由于理解具有不同程序员，理解的过程和结果也不相同的特点，更加增加了这项工作的难度。 本文针对这一点提出认知容易度概念，和使用认知容易度驱动程序理解过程的方法。这种方 法可以指引程序员下一步理解工作的方向，并且可以针对每个具体不同的程序员提供不同的 认知方向。 2 2 程序切片 程序切片技术是1 9 7 9 年由m w e i s e r 提出的【2 5 1 。它采用分而治之的思想，根据一个关注 点( 切片准则) ，对代码进行语义上的分解，将有关的内容从代码中提取出来，屏蔽掉无关 代码。其目的是删除程序中不影响切片准则的语句，以缩小程序。基于这种特性，程序切片 自提出以来，被广泛应用于程序理解、测试、调试和维护等领域。 程序切片一般是指程序p 中与切片准则s c 相关部分的集合，即关于某个特定的切片准则 的切片。切片准则( s o ) 代表感兴趣的变量，以及该变量的定义位置或使用位置，对于某些 类型的切片还包括某个特定的具体输入。切片准则不同，得到的切片的结果也不相同。 2 2 1 程序切片的分类 1 静态切片和动态切片 静态切片是指利用静态分析产生的切片，包含与某个关注点中的变量( 集合) 相关的所 有语句和控制谓词，计算这种切片时需要考虑程序的所有可能的输入值情况；动态切片则是 在某个特定输入下的程序切片，只包括在特定输入时实际与某个关注点中的变量( 集合) 相 关的所有语句。通常情况下，动态切片是静态切片的子集。如图2 1 所示。 7 东南人学硕 ：学位论文 1 m a i n ( ) 1 m a i n ( ) 2 2 3 熬t 如b ，霉 3 g t a ，6 ，餮 4 s c a n f ( “d ，1 ；秀& 如& 嶙 4 s c a n f ( “屯& 锄嵫 5 蓼( a 嬷 5 篡( a b t 6 6 7 罐 7 仁a ； 8势镌 8 a b ； 9b = t ：9b ：t ： 1 0 ) 1 0 ， 1 1 赫n l 髫眦职筋鹾 1 1 赫n t 髦鸯；筋鹾 1 2 1 2 ， 图2 1 左图为关- j ： 的静态切片，右图为关r 的动态切片 2 后向切片和前向切片 后向切片包含影响某个关注点中的变量( 集合) 的所有语句和控制谓词；前向切片包含 受到某个关注点中的变量( 集合) 影响的所有语句和控制谓词。如图2 2 所示 1 m a i n ( ) 1 m a i n ( ) 2 2 3 m t 蠢b ，甏 3i n ta ，b ，t ； 4 s c a n f ( 哆碡砂& & 鹾 4 s c a n f ( “d ，d ”& a ，& b ) ； 5 劳畛坳 5 i f ( a b ) 6 6 7 静麓 7 t = - a ； 8 爹：魄 8 a _ b ： 9 b - - t ； 9 b = t ； 1 0 ) 1 0 ) 11 p r i n t f ( “d ，d ”，a ，b ) ； 11 餮n n t f e 或矗o d - 。= , 潮 1 2 ， 1 2 ) 图2 2 左图为关于 的后向切片，右图为关丁二 的前向切片 3 过程内切片和过程间切片 过程内切片主要是指只针对一个过程，在其内计算切片，图2 1 和图2 2 中展示的程序 切片的例子实际上都是过程内切片。 随着程序规模越来越大，程序中几乎不可能只包含一个过程，因此出现了针对具有多个 过程的程序进行切片。过程间切片是指当一个程序由多个过程组成时，在这些过程之间计算 切片。计算过程间切片的时候，除了过程内切片的部分，还需要考虑某个过程被调用的上下 文，用以将切片准则扩展到被调函数和施调函数中继续计算切片。如图2 3 所示。 1 m a i n ( ) 8 i n t m a x ( i n t x ，i n ty ) 2 9 3 猛菇西，7 蓬 l o藜t 煮 4 s c a n f ( “也谬& & b 鬟 11 簇( 炉磋 5 够一m a x ( a ，b k 1 2 轳镌 6 p r i n t f ( d ，乞磋 1 3e l s ez = b ： 7 ) 1 4 r e t u r n 渊 1 5 ) 图2 - 3 关于 的过程间静态切片 第二章程序理解和程序切， 2 2 2 程序切片的计算方法 传统程序切片的计算方法主要有两种：一种是m w e i s e r 提出的基于数据流方程的方法 【z 5 j ；一种是基于依赖图的两步遍历图可达性算法【2 7 】【2 8 】。 m w e i s e r 在程序控制流图的基础上建立了数据流方程，提出通过求解数据流方程来获得 相应的程序切片。这种方法首先计算与准则直接相关的变量和语句，然后再不断地迭代计算 问接相关的变量和语句，直到切片结果不再增大。然而由于建立数据流方程是一个非常复杂 的过程，即使是一些很小的错误信息也会使结果受到很大的影响，而且求解方程所消耗的时 间和空间比较多，导致计算的效率并不高。同时，这种方法只能解决简单的包含顺序、选择 和循环结构的程序切片问题，无法解决存在多个过程和过程调用的程序切片问题。随着面向 过程和面向对象编程语言的广泛应用，这种计算方法显得无能为力。 随后，k j o t t e n s t e i n 和l m o t t e n s t e i n 又提出了基于程序依赖图的图可达性算法，解决 了过程内后向切片的问题。s b h o r w i t z ，t w r e p s 和d b i n k l e y 等人又提出了利用系统依赖 图计算过程问程序切片的两步遍历图可达性算法，从而解决了饱含多个过程的程序切片计算 问题。大致过程如下【2 9 】： ( 1 ) 构造某个程序的程序依赖图或者系统依赖图； ( 2 ) 给定某个程序切片准则，在程序