In building program tutoring system, problem description about program task is inevitable to analyze students' buggy programs. Problem descripiton is provided an instructor to the system and should include enough information to deal with various students' programs. However, it is very hard for an instructor to write a problem description in system understandable form. The simplest way for an instructor to describe a problem may be to write a sample program of given problem, which cannot provide enough information to analyze various programs. In this dissertation, implemented is GOES(Goal Extraction System) which analyzes sample programs and generates problem descriptions. When analyzing sample programs, GOES proposes "Label-based Plan Recognition" to recognize programs more efficiently and control the search space which grows explosively as the size of the program and the knowledge base become larger.
GOES is a bottom-up program understanding system which analyzes sample programs with no advanced information about the programs, and generates high-level descriptions. There are two issues in bottom-up program understanding. First issue is how to represent programming plans which are the basic semantic blocks in programming understanding. In GOES, plans are represented as code-base form which provides the understandability and extensibility of knowledge base. The drawback of code-based representation is that it has difficulty in coping with syntactic variability. GEOS solves this problem by removing syntactic variations during parsing and preprocessing.
Second issue is how to control the explosively growing search space efficiently. GOES uses the "Label" which denotes the functionality of each program statement as a beacon of plan extraction. The label is used to check the necessary condition of a plan to a program line, and the sufficient condition of a plan to the program. Variables of each program statement is used to group the noncontiguous plan fragments. We call this approach to plan extraction as "Label-based Plan Recognition".
For the experiment, GOES was tested with 41 problems including 37 examples and exercises of the text book of introductory C language course of KAIST, Average problem, Rainfall problem, Sort problem, and Rainfall + Sort problem. As the sample programs of examples, used are the programs in the textbook. The sample programs of exercises and other problems are gathered from 12 teaching assistants of KAIST. In the experiment, GOES that shows it can deal with every difficulties of plan-based program understanding. Label-based Plan Recognition controls the search space efficiently. In average, among 80 plans in the knowledge base, only 11.7 plans satisfy the necessary condition per a program line, and 2.0 plans among them satisfy the sufficient condition. The exact code matching is applied only to the plans which satisfy the necessary and the sufficient conditions. Therefore, computational effort is reduced significantly.
본 논문에서는 지식시반형 프로그램 교사 시스템의 구현시 반드시 필요한 문제정의를 교사의 예시 프로그램으로부터 자동으로 추출하는 시스템인 GOES(GOal Extraction System)을 구현하였다. 또한, 이 시스템이 주어진 프로그램을 인식하는 과정에서 탐색 영역을 효과적으로 제한하여 시스템의 성능을 높이며 보다 실용적인 시스템으로 사용될 수 있도록 하는 Label-based Plan Recognition 방식을 제안하였으며, 실험을 통해 이 방식이 실제로 프로그램을 효율적으로 인식할 수 있음을 보였다.
간단한 문제에 대한 프로그램이라 할 지라도 그 변형의 가지수가 무한대에 이를 수 있는 학생의 프로그램을 분석하기 위해서는 학생이 어떠한 문제를 풀었는가에 대한 정보, 즉 문제 정의가 필요하다. 문제 정의의 형식은 제공하는 교사와 이를 활용하는 시스템이 각각 다르게 요구한다. GOES에서 택한 예시 프로그램으로부터 추상화된 프로그램의 정보를 추출하여 시스템에 Formal Language 형태로 제공해 주는 방법은 교사와 시스템의 상반된 요구 사항을 적절히 조화시킨 방법이다.
GOES는 주어진 예시 프로그램을 분석하여 High-level description을 생성하는 일종의 프로그램 인식 시스템이다. 이와같이 인식하고자 하는 프로그램에 대해 아무런 정보도 없이 프로그램을 인식해 내는 과제에는 다음과 같은 두가지의 이슈가 있다.
첫째, 프로그램을 이루는 가장 기본적인 의미 단위인 플랜을 어떻게 표현할 것인가 하는 점이다. GOES는 이 플랜을 이해와 확장이 비교적 쉬운 코드 기반으로 표현하였으 코드 기반의 단점인 문법적 변형에 대응하기 어렵다는 점을 극복하기 위해 입력 프로그램을 파싱과 전처리를 통해 추상화 시킴으로써 문법적 변형을 제거하였다.
둘째, 주어진 프로그램으로부터 사용된 플랜을 찾아내는 일은 방대한 지식베이스에 대한 탐색을 요한다. 이 탐색 영역은 인식하고자 하는 프로그램의 크기가 커질수록, 또 사용하는 지식 베이스의 크기가 커질수록 기하급수적으로 증가하게 된다. 따라서 이 탐색 영역을 어떻게 효과적으로 제어하는가가 시스템이 실용적이 될 수 있는가의 관건이 되며, 시스템 전체의 효율에도 큰 영향을 미치게 된다. GOES에서 제안한 Label-based Plan Recognition방식은 각 프로그램 코드의 역할을 나타내는 Label과 비연속적으로 산재한 플랜의 코드를 효과적으로 결합하여주는 프로그램 변수를 쌍으로 하여 주어진 프로그램 라인에 플랜이 부합되기 위한 최소 필요 조건과 플랜이 프로그램 내에 존재하는가를 보는 충분 조건을 검사한다. 이러한 필요/충분 조건의 검사는 플랜을 인식해 내는 과정에 필요한 탐색 영역을 효과적으로 줄이는 한편, 실제 코드 매칭을 제한된 플랜에 한하여 수행하도록 함으로써 계산 효율을 높이고 있다.
GOES에 의해 최종 생성되는 문제 정의에는 프로그램에 구현되어 있는 고울 뿐만 아니라 프로그램 코드에 대한 정의도 포함되어 있다. 대개 프로그램 문제는 해당 문제에서만 사용되는 문제 고유의 부분을 포함하고 있는데, GOES가 생성하는 문제 정의에서는 이 부분을 추상화된 코드로 나타낸다.
GOES의 프로그램 인식 능력을 평가하기 위해, 실험 대상으로 KAIST의 기초 C언어 강좌에서 사용하는 교재인 "알기쉬운 C 언어"의 1장부터 7장까지의 예제 및 연습문제와, 기존의 프로그램 인식 시스템에서 종종 비교 대상으로 거론되었던 Average, Rainfall, Sort문제, 그리고 복잡한 문제를 해결할 수 있는지를 보기 위해 Rainfall과 Sort 문제가 하나로 복합되어 있는 Rainfall+Sort문제 등 총 41개의 문제를 대상으로 실험을 실시하였다. 예시 프로그램으로는 예제의 경우는 책에 나와있는 모범 답안을 그대로 사용 하였으며, 연습 문제 및 기타 문제의 예시 프로그램은 C 언어 조교를 역임한 12명의 대학원생으로부터 얻어내었다. 실험 결과 GOES는 다양한 난이도의 여러 문제들을 모두 분석할 수 있었으며, 동일한 문제를 여러 알고리즘을 사용하여 프로그램한 경우에도 동일한 문제 정의를 생성할 수 있었다.
Label-based Plan Recognition은 주어진 프로그램으로부터 플랜의 인식을 매우 효과적으로 수행하여 주는 방법임이 확인되었다. 총 80개의 플랜 중 임의의 프로그램 문장에 대해 필요조건을 만족하는 플랜의 수는 평균 11.7개에 불과하였으며, 이 중 충분 조건까지 만족하는 플랜의 수는 평균 2.0개에 불과하였다. 따라서 플랜을 인식해 내는데 필요한 탐색의 영역이 대폭 줄어들었을 뿐 아니라, 필요/충분 조건을 만족하는 플랜에 대해서만 코드 매칭을 수행하므로 계산 효율도 크게 높일 수 있었다. 또한 Label-based Plan Recognition은 실제로 프로그램에서 사용하고 있는 플랜을 놓치지 않고 후보 플랜으로 선발 함으로써, 주어진 문제에 대한 한 efficiency를 위해 completeness를 희생하지 않음도 보여주었다.
