Program understanding is an important part of the domain expertise required for programming language tutoring systems. However, understanding of student programs by computer is extremely difficult because of the tremendous variability in student solutions for nontrivial tasks. This dissertation aims to handle such variability and improve understanding performance by a integrated approach based on two complementary methods of graph-parsing and expectation-driven analysis.
The graph parsing method by Wills is utilized to recognize the programming plans in the code. At the same time, a new expectation-driven analysis is devised to generate expectations about the program design by using such knowledges as the programming goals, plans, and information about the problem task. The analysis guides the plan recognition process through confirming, amending, or rejecting the expectations by checking them against the given code.
Analysis by expectation on plan (plan-driven expectation analysis) handles the near-miss plan. The matching with the smallest cost to modify the partial recognition is selected for further analysis. Plan-driven expectation analysis can find errors that can be explained as a variation of a plan. This identification is achieved without separate buggy plan library, and it can be debugged automatically.
Analysis by expectation on goal (goal-driven expectation analysis) is used for understanding programs which contain unseen plans not existing in the plan library. Also, it finds unknown goal-implementing plans by generating candidate subgraphs and checks them with test data. Automatically acquiring the new programming plan can be obtained for a specific goal by using simple initial goal specifications. It would widen the range of applicability of program understanding, especially for novice programs.
The system presented in this thesis was implemented as a major component of the Intelligent Tutoring System for C programming tutoring for novice programmers. Experiments have been conducted to evaluate the proposed techniques and the results have proven that the techniques are practically useful and effective in student program understanding for programming tutoring.
본 논문에서 다루는 문제는 학생이 작성한 프로그램을 이해하는 것이다. 시스템은 학생이 작성한 프로그램과 학생이 풀어야 할 문제에 대한 정보를 문제 정의(problem description)의 형태로 입력받고, 시스탬내에 있는 영역지식(domain knowledge)을 이용하여 분석하여, 학생 프로그램이 무엇을 어떻게 구현했는가를, 영역지식내에 있는 "무엇"에 해당하는 고울(goal)과 "어떻게"에 해당하는 플랜(plan)의 설계트리(design tree)의 형태로 출력하게 된다. 이때 학생 프로그램내에 오류가 있는 경우에는 그것을 발견하고, 자동적으로 정정하는 기능도 포함한다.
컴퓨터가 프로그램을 이해하는것은 프로그램 자체가 많은 변형을 포함하고 있어서 상당히 어려운 문제이다. 또한 대상 프로그램이 학생이 작성한 프로그램일 경우에는 프로그램내에 많은 오류가 있을수 있고, 오류가 없다고 하더라도 시스템이 가지고 있는 영역지식만으로는 분석할수 없는 패턴이 포함될수 있다. 이러한 변형의 수는 거의 무한에 가까우므로, 이것을 극복하고 프로그램을 이해하는것은 상당히 어려운 문제라고 할수 있다.
본 논문에서는 이러한 프로그램 이해의 어려움을 극복하며, 보다 효율적으로 학생 프로그램을 이해하기 위하여, 그래프 파싱 (graph parsing) 방법과 기대기반 분석(expectation-driven analysis)의 혼합방법(hybrid approach)을 기반으로 한 프로그램 이해 방법론을 제안하였다.
그래프 파싱 방법은 Bottom-up 방법에 의해서 시스템이 가지고 있는 영역지식 (domain knowledge)로 프로그램을 인식하는데, 이것은 프로그램이 포함하고 있는 여러 변형들을 쉽게 극복한다는 장점이 있다. 하지만, 이 방법은 순수한 bottom-up 방법이기 때문에, 프로그램 인식 도중에 중간 단계의 파싱이 실패하게 되면, 프로그램 전체를 이해하지 못하고, 부분인식으로 끝난다는 문제가 있다. 또한, 문제 자체에 대한 정보를 이용하지 않으므로, 학생 프로그램에 오류나 해석할수 없는 패턴이 포함되어 있어 부분인식으로 끝난 경우에, 학생이 그 문제를 해결하기 위해 필요한 도움말을 생성할수 없다는 문제점이 있다.
이러한 문제점을 극복하기 위하여, 본 논문에서는 기대기반 분석을 새롭게 제안하였다. 기대기반분석 방법은 프로그램 이해도중에 생성되는 기대(expectation)을 기반으로 프로그램을 분석하는 방법이다. 프로그램 이해도중에 생성되는 기대란, 분석 대상 프로그램에 무엇인가a}L} 구현되어 있을것이라고 짐작하는 것이다. 이러한 기대는 두가지 종류가 있는데, 우선 하나는 특정 플랜(plan)이 프로그램상에 구현되어 있을거라는 기대이다. 즉, 프로그램 이해도중에 알고있는 플랜과 비슷한 패턴이 나타나면, 그 패턴이 그 플랜이라고 가정하는 것이다. 또 문제정의로 부터 학생 프로그램이 무엇을 구현했는지 알 수 있으므로, 그 특정 고울(goal)이 프로그램상에 구현되어 있을거라 기대할수 있다. 우리는 이러한 기대분석방법을 각각 "플랜에 의한 기대분석"(Plan-driven Expectation Analysis, PEA)와 "고울에 의한 기대분석"(Goal-driven Expectation Analysis, GEA)라고 부른다.
이러한 기대기반 분석방법은 그래프 파싱의 실패가 되는 원인을 찾아내고, 그것을 정정한 후에, 그래프 파싱이 계속해서 상위단계의 추상화과정을 계속할 수 있도록 해준다. 이 과정에서 PEA는 특정 플랜의 변형으로 해석되는 오류를 찾아내고, 자동적으로 정정할수 있도록 해준다. 그리고, GEA는 학생 프로그램내에 있는 새로운 구현패턴을 찾아내게 하며, 새로운 프로그래밍 플랜을 자동적으로 획득할수 있도록 하는 기능을 제공한다.
본 논문에서는 실제로 학생이 작성한 프로그램을 대상으로 실험하였는데, 그 결과, 프로그램내의 특정 고울의 구현사항을 이해하는데에, 그래프 파싱방법 하나만을 이용한 방법보다 주목할만한 인식률의 향상을 얻었다. 특히 오류와 시스템이 가지고 있는 플랜지식으로 해석할수 없는 패턴을 포함한 프로그램을 인식하는데에 좋은 성능을 보였다. 따라서 본 논문에서 제안한 그래프 파싱 방법과 기대기반 분석방법의 혼합형 프로그램 이해 방법론은 학생에게 프로그래밍을 지도하는 지능형 프로그래밍 교육시스템에 효과적으로 이용될수 있음을 보였다.
