논리 프로그램의 병렬 수행을 위한 AND / OR Bipartite 아키텍춰

최광무(Kwang-Moo Choe),황성훈(Seong-Hoon Whang) 한국정보과학회 1987 한국정보과학회 학술발표논문집 Vol.14 No.2

AND/OR 프로세스 모델에서 fact clause의 unification을 nondeterminstic하게 수행할 수 있는 변형된 AND/OR 프로세스 모델을 제안한다. 또한 AND/OR 프로세스 모델을 실제 환경에서 효율적으로 수행하기위한 AND/OR Bipartite 아키텍춰에 대하여 제안한다. AND/OR Bipartite 아키텍춰는 AND/OR 프로세스 모델의 특성인 AND 프로세스와 OR 프로세스가 번갈아 나오는 parent와 children의 관계에 있는 프로세스들 사이에만 메시지를 특성을 충분히 이용한 모델로서, 이 AND/OR Bipartite 아키텍춰에서는 프로세스 할당 정책을 간소화 할 수 있으며, 전체적인 부하 균등(load balance)의 효과를 얻을 수 있다.

확장된 KAIST 파서 생성 시스템의 개발 및 구현

최광무(Choe Kwang-Moo),정민수(Jung Min-Su),김도형(Kim Do-Hyeong),박광순(Park Kwang-Soon),이형효(Lee Hyeong-Hyo),최준식(Choi Jun-Sik) 한국정보과학회 1989 한국정보과학회 학술발표논문집 Vol.16 No.1

파서 생성 시스템은 컴파일러의 반자동적 개발 및 생산성 향상을 위한 중요한 도구로서 많은 연구 및 개발이 이루어지고 있다. 이에 본 연구진은 스탠포드 PGS(Parser Generating System)를 근간으로 KAIST 파서 생성 시스템을 개발한 바 있다. 본 논문은 기존의 KAIST 파서 생성 시스템의 효율적인 LALR(1) lookahead 집합의 계산 ECFG(Extended Context Free Grammar)의 변환 파싱 및 직접 파싱 Table driven 오류 보정, 입력 문법의 LALR(1) 분석에서 conflict에 대한 원인 분석 기능을 추가한 확장된 KAIST 파서 생성 시스템의 개발과 구현에 관하여 서술한다.

Yacc에서의 최소 비용 삽입 스트링을 이용한 오류 보정

최광무(Choe Kwang-Moo),정민수(Jung Min-Su),김도형(Kim Do-Hyeong) 한국정보과학회 1987 한국정보과학회 학술발표논문집 Vol.14 No.2

Fischer[6, 7, 8, 9]등이 제안한 국부적 최소 비용 오류 처리 방식은 컴파일러 설계자에 의해 제공된 모든 터미널 심볼들에 대한 삽입 및 삭제 비용을 가지고서, table-driven 오류 처리 파서를 만들수 있는 바탕을 제공한다. 최근 최광무와 장천현[1, 2, 3, 12]은 LR 파서를 위하여 국부적 최소 비용 삽입 스트링을 효율적으로 구할 수 있는 앨거리듬을 제시한 바 있다. 본 연구에서는 위의 앨거리듬을 UNIX 환경하에서 잘 알려진 파서 생성 시스템인 Yacc에 적용 시켜서 훨씬 효율적인 오류 처리 기능을 제공해주는 새로운 Yacc (Eryacc Error Recovery Yacc)을 구현하고 실제 프로그래밍 언어에 적용하여 그 실용성을 보였다.

LALR(1) 분석에서의 Conflict의 효율적인 추적

박광순(Kwang Soon Park),최광무(Kwang Moo Choe),박우전(Woo Jun Park) 한국정보과학회 1989 정보과학회논문지 Vol.16 No.4

LALR(1) 분석에서 발생하는 conflict의 원인을 찾아 제거하는 일은, 적지않은 LR(0) 상태들을 일일이 따라가고, 또 프로덕션을 검사해야 하는 매우 번거로운 작업이다. DeRemer와 Pennello는 conflict의 원인을 알려주는 정보(추적)를 파서 생성 시스템이 특정한 양식으로 출력하는 방법을 제시하였다. DeRemer와 Pennello의 추적 계산 방법에서는, lookahead 집합의 계산을 위하여 구성한 방향 그래프를 이용하여 추적을 구성하는 일부 요소를 쉽게 계산하지만, 비효율적인 측면을 가지고 있다. 본 논문에서는 박철희등의 새로운 LALR 해석논리에 기초하는 효율적인 새로운 추적 계산 방법을 제시하였다. 제안된 새로운 방법은, lookahead 집합의 계산을 위하여 계산된 넌터미널들 사이의 관계를 효과적으로 이용하여, 보다 효율적으로 추적을 계산한다. 기존의 방법과 제안된 새로운 방법을 KAIST 파서 생성 시스템에 구현하고, 몇개의 문법에 대하여 실험을 하여, 새로운 방법이 기존의 방법보다 효율적임을 보였다. Tracing of conflicts manually is not so easy in LALR(1) analysis; It involves troublesome tracing of LR(0) states and/or examination of productions in the grammar. DeRemer and Penello suggested an automatic tracing method, where information called trace which shows sources of conflicts, is produced in a predefined form. In the original method of computing traces, a relation needed in computing lookahead sets is used to find out the items which make the conflict symbol be included in the lookahead set of a reducible item. In this thesis, the trace computation method is re-examined under new formalism of Park et al., and a more efficient method based on the formalism is proposed. Both the old and new method are Implemented on KAIST Parser Generating System (KPGS), and experimental results for the comparison of the two method are presented.

논리 프로그램의 병렬 수행에서 재초기화 알고리즘의 정확성 증명을 위한 참조 집합 : 직관적 접근

김도형,최광무(Do-Hyung Kim),Kwang-Moo Choe 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.3

논리 프로그램(logic program)의 병렬 수행 시, 중요한 작업 중의 하나인 재초기화(resetting)를 수행하기 위한 알고리즘들의 정확성(correctness) 증명을 위한 기준을 제시한다. 많은 연구자들이 논리 프로그램의 병렬 수행을 위한 수행 모형을 제안한 바 있고, 그것과 관련하여 재초기화를 효율적으로 처리하기 위한 알고리즘들을 제시하였다. 그러나 그 알고리즘들이 올바르게 작동하는 지에 대해서는 분명한 언급이 없는 경우가 많았다. 본 논문에서는 정확성에 대한 판단을 내릴 수 있는 기준을 도출한다. 이 도출 과정은 직관적으로 보아 명백한 사실에 대한 관찰로부터 유도되는 식으로 이루어진다. 도출된 정확성 판단 기준에 근거하여 기존의 재초기화 방법들을 점검하고, 보다 효율적이라고 판단되는 재초기화 방법도 서술한다. A criterion for the correctness proof of resetting algorithms in parallel execution of logic programs is suggested in the paper. Many researchers have proposed various execution models to exploit parallelism in logic programs, thus various algorithms to handle resetting efficiently. It is, however, hardly mentioned whether those algorithms are "really" correct in every case. In this paper, we devise a yardstick which may serve for probing the correctness of resetting algorithms. This criterion is derived from observations that are intuitively clear. According to the derived criteria, we analytically review existing schemes for resetting, and describe another new resetting method which seems to be more efficient than others.

Intelligent Backtracking의 대수학적 모델

이수현(Lee Su-Hyun),최광무(Choe Kwang-Moo) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

Chang의 정적인 자료종속 관계분석(static data dependency analysis)을 기본으로 하는 효율적인 백트랙킹 방법의 대수학적 모델을 제안하였다. 대수학적 모델의 기초로는 Milner의 Calculus of Communicating Systems(CCS)를 사용하였다. 이러한 접근방법을 이용하면 백트랙킹에 대한 수학적이고 정형적(formal)인 접근이 가능하다.

파서생성시스템에서 파싱 충돌의 해결에 관한 연구

이은정(Lee Eun-Jung),최광무(Choe Kwang-Moo) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.1

이 논문의 목적은 기존의 파서생성 시스템에서 쓰고 있는 충돌해결 방식의 의미를 이론적으로 규명하고 주어진 해결규칙에 의해서 변환된 파서에 대응하는 LR(k) 문법을 자동적으로 작성하는 알고리즘을 제시한다.

KAIST CHILL 컴파일러

이동길(Donggill Lee),최광무(Kwang-Moo Choe),전길남(Kilnam Chon) 한국정보과학회 1985 정보과학회논문지 Vol.12 No.2

A compiler for the subset of CHILL (CCITT High Level Language) is designed and implemented, considering the developing environment of ESS (Electronic Switching Systems). The compiler developed provides a basis for developing the production quality CHILL compiler KAIST CHILL compiler is developed using the powerful compiler-compiler tools, such as KAIST Parser Generating System and Amsterdam Compiler Kits. 본 연구에서는 ESS 개발환경을 고려하여 production quality CHILL compiler개발의 환경조성을 위한 CHILL subset compiler를 설계 제작하였다. KAIST Parser Generating System 등을 이용하여 front end를 설계 제작하였으며 Amsterdam Compiler Kit로 부터 back end와 intermediate machine의 환경을 제공받아 CHILL subset을 위한 compiler를 설계 제작하였다.

상향식 추상 해석을 이용한 논리 프로그램의 AND/0R 병렬 수행 모델 개선

창병모(Byeong-Mo Chang),최광무(Kwang-Moo Choe),한태숙(Taisook Han) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.5

본 논문에서는 상향식 추상 해석(bottom-up abstract interpretation)을 이용하여 논리 프로그램의 병렬 수행 모델인 AND/OR 프로세스 모델을 개선한다. 이를 위하여 기존의 상향식 추상 해석을 깊이 k 추상화를 기초로하여 프로그램의 각 절의 성공 패턴(success pattern)에 대한 근사값을 구할 수 있도록 확장하였다. 확장된 추상 해석은 각 절의 성공 패턴에 대한 근사값을 구할 수 있으며 이를 이용하면 어떠한 subgoal은 실행중에 실패할 것이라는 사실을 컴파일 시간에 결정할 수 있다. 본 연구에서는 이러한 성질을 이용하여 AND/OR 프로세스 모델을 개선하며 이 모델에서 AND 프로세스는 자식 OR 프로세스가 실패할 것이 확실한 경우에 자식 OR 프로세스를 생성하지 않는다. 이 방법론은 다른 하향식 (병렬) 수행에도 쉽게 적용 가능하다. This paper improves the AND/OR Process Model, a parallel execution model of logic programs, using a bottom-up abstract interpretation. We first extend a bottom-up abstract interpretation framework so that it can approximate the program's success patterns of program clauses by depth k abstraction. By the ability of the extended framework to approximate possibly non-ground success patterns for clauses, it can be statically determined whether some subgoals will fail during execution. We improve the AND/OR Process Model using this property, in which AND processes do not create child OR processes if it is statically determined that they will fall during execution. This approach can also be easily applied to other top-down (parallel) execution models.

순환 논리 질의 최적화를 위한 정적 필터의 고정점 계산

창병모(Byeong-Mo Chang),최광무(Kwang-Moo Choe),한태숙(Taisook Han) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.9

정적 필터링은 시스템 그래프 수행을 기초로한 순환 논리 질의 최적화 방법이다. 이 방법은 수행하는 동안에 정적 필터를 이용하여 데이터의 흐름을 제한한다. 본 논문은 정적 필터의 계산 과정을 partially ordered set(poset) 위에서 하나의 변환으로 정형화하고 그 변환의 최소고정점을 구함으로써 정적 필터를 구한다. 계산된 정적 필터의 완전성(completeness)은 제시된 정형화를 이용하여 증명한다. 또한 관련 연구에 대해서 간단히 살펴보고 정적 필터링 방법과 비교한다. 본 논문에서는 정적 필터와 그 계산에 대한 정형화된 새로운 관점을 제공한다. Static filtering is a graph-bsed optimization method for recursive logic queries based on the system graph evaluation. It restricts data-flow during evaluation by means of static filers. We formalize the computation of static filters by defining a transformation on a partially ordered set (poset) so that the least fixed point of the transformation can be the static filters. The static filters are computed by computing the least fixed point of the transformation. The completeness of the static filtering with the computed static filters is proved based on the formalism. Moreover, we review some related works in brevity and compare the static filtering with them. The formalism presented in this paper gives a new formal view to static filter and its computation.