본 연구에서는 CoLweb이라 불리는 알고리즘 언어에 해당하는, 새로운 알고리즘의 정의를 제시한다. CoLweb[1]의 장점은 알고리즘 설계를 매우 유연하게 만든다는 데 있다. 즉, 비분산 컴퓨팅과 분산 컴퓨팅 모두에 대해 알고리즘 설계를 고수준의 증명-수반(proof-carrying), 분산형(distributed-style) 접근으로 강제한다. 우리는 이러한 접근이 알고리즘 설계를 단순화한다고 주장한다. 또한 재귀적 논리/함수형 알고리즘, 명령형 알고리즘, 객체지향 명령형 알고리즘, 신경망(neural-nets), 인터랙션 넷(interaction nets), 증명-수반 코드(proof-carrying code) 등 다른 접근들을 통합한다. 응용의 한 예로, 우리는 혼 절(Horn clause) 정의를 두 종류로 정교화한다: 맹목적 전칭-양화(blind-universally-quantified, BUQ) 정의와 병렬 전칭-양화(parallel-universally-quantified, PUQ) 정의이다. BUQ 정의는 지식기반이 $not$ 확장되지 않으며 그 증명 절차가 역방향 체이닝(backward chaining)에 기반하는 Prolog에서의 전통적 정의에 해당한다. 반면 PUQ 정의에서는 지식기반이 $expanding$되고, 그 증명 절차가 순방향 체이닝(forward chaining)과 { it automatic memoization}을 도출한다.

논리 프로그래밍에서 오랫동안 이어져 온 연구 문제 중 하나는 cut 술어를 논리적이고 고수준의 방식으로 취급하는 것이다. 우리는 이러한 문제는 선형 논리와, G0 ⊕ G1 형태의 선택-이항(disjunctive) 목표 공식(choice-disjunctive goal formulas)을 채택함으로써 해결될 수 있음을 주장한다. 여기서 G0, G1는 목표이다. 이러한 목표가 갖는 의도된 의미는 다음과 같다. 참인 이항 Gi를 선택하고, i (= 0 또는 1)인 해당 Gi를 실행하되, 선택하지 않은 이항은 폐기한다. 실행 중에는 오직 하나의 목표만이 살아 있을 수 있음을 주의하라. 이 목표들은 따라서 서로 배타적인 과업을 고수준의 방식으로 명시할 수 있게 해준다. 또한 cut에는 실패에 의해 구동되는 반복 루프에서 벗어나기 위한 사용과, 효율적인 힙(heap) 관리를 위한 사용이라는 또 다른 용도가 있음을 주의하라. 그러나 불행히도 이와 같은 종류의 cut은 선택-이항 목표의 사용으로 대체할 수 없다.

본 연구에서는 CoLweb이라 불리는 알고리즘 언어에 해당하는, 새로운 알고리즘의 정의를 제시한다. CoLweb[1]의 장점은 알고리즘 설계를 매우 유연하게 만든다는 데 있다. 즉, 비분산 컴퓨팅과 분산 컴퓨팅 모두에 대해 알고리즘 설계를 고수준의 증명-수반(proof-carrying), 분산형(distributed-style) 접근으로 강제한다. 우리는 이러한 접근이 알고리즘 설계를 단순화한다고 주장한다. 또한 재귀적 논리/함수형 알고리즘, 명령형 알고리즘, 객체지향 명령형 알고리즘, 신경망(neural-nets), 인터랙션 넷(interaction nets), 증명-수반 코드(proof-carrying code) 등 다른 접근들을 통합한다. 응용의 한 예로, 우리는 혼 절(Horn clause) 정의를 두 종류로 정교화한다: 맹목적 전칭-양화(blind-universally-quantified, BUQ) 정의와 병렬 전칭-양화(parallel-universally-quantified, PUQ) 정의이다. BUQ 정의는 지식기반이 $not$ 확장되지 않으며 그 증명 절차가 역방향 체이닝(backward chaining)에 기반하는 Prolog에서의 전통적 정의에 해당한다. 반면 PUQ 정의에서는 지식기반이 $expanding$되고, 그 증명 절차가 순방향 체이닝(forward chaining)과 { it automatic memoization}을 도출한다.

논리 프로그래밍에서 오랫동안 이어져 온 연구 문제 중 하나는 cut 술어를 논리적이고 고수준의 방식으로 취급하는 것이다. 우리는 이러한 문제는 선형 논리와, G0 ⊕ G1 형태의 선택-이항(disjunctive) 목표 공식(choice-disjunctive goal formulas)을 채택함으로써 해결될 수 있음을 주장한다. 여기서 G0, G1는 목표이다. 이러한 목표가 갖는 의도된 의미는 다음과 같다. 참인 이항 Gi를 선택하고, i (= 0 또는 1)인 해당 Gi를 실행하되, 선택하지 않은 이항은 폐기한다. 실행 중에는 오직 하나의 목표만이 살아 있을 수 있음을 주의하라. 이 목표들은 따라서 서로 배타적인 과업을 고수준의 방식으로 명시할 수 있게 해준다. 또한 cut에는 실패에 의해 구동되는 반복 루프에서 벗어나기 위한 사용과, 효율적인 힙(heap) 관리를 위한 사용이라는 또 다른 용도가 있음을 주의하라. 그러나 불행히도 이와 같은 종류의 cut은 선택-이항 목표의 사용으로 대체할 수 없다.

정리 증명은 탐색 공간을 가지치기(prune)하기 위해 휴리스틱이 요구되는 가장 오래된 응용들 중 하나이다. 가역적인(procedures) 증명 절차는 주요한 도구로 자리해 왔다. 본 논문에서는 가역적 증명 절차의 기저 원리로 볼 수 있는, 새롭고 강력한 휴리스틱인 $nongshim$을 제시한다. 이 휴리스틱을 사용하여, 명제 논리를 위한 선행사(sequent) 계산으로부터 가역적 선행사 계산",

모듈 시스템에서 한정된 이름(qualified names)이라는 개념은 널리 사용되지만, 심각한 합병증을 유발한다. 본 논문에서는 한정된 이름의 대안을 제안한다. 핵심 아이디어는 다른 모듈의 선언들을 사용되기 전에 현재 모듈로 가져오는 것이다. 이와 같이 하면 모든 선언을 로컬에서 접근할 수 있다. 그러나 이러한 접근은 메모리 사용 측면에서 효율적이지 않다. 우리의 기여는 최소한의 부분만을 가져올 수 있게 하는 { module weakening} 방식이다. 이 접근의 한 예로서, 우리는 함수형 언어를 위한 모듈 시스템을 제안한다.

증명(서열 계산, 자연 연역)과 명령형 알고리즘(의사코드)은 잘 알려진 두 가지 공존하는 개념이다. 그렇다면 이들 사이의 관계는 무엇인가? 우리의 답은 \[ imperative\ algorithms\ =\ proofs\ with\ cuts \] 이라는 것이다. 이러한 관찰은 우리가 { \it logical pseudocodes}라고 부르는 의사코드에 대한 일반화로 이어진다. 이는 계산가능성 논리의 자연 연역 증명",

계산가능성 논리(computability logic) \cite{Jap03}에 영감을 받아, 재귀 함수 정의를 두 종류로 정련한다: 맹목적으로 한정(\textit{blindingly-quantified}, BQ)된 것들과 병렬 보편 한정(parallel universally quantified, PUQ)된 것들이다. BQ 정의는 재귀 정의가 $not$ evolving인 전통적인 정의에 해당한다. PUQ 정의는 계산 과정에서 \textit{evolving}되어, 자동 메모이제이션으로 이어진다. 또한 이러한 아이디어를 바탕으로, 새로운 고수준 객체지향 언어를 제안한다.

비록 알고리즘이 핵심 주제 중 하나이지만, 알고리즘이 무엇인지에 대해서는 공통의 이해가 거의 없었다. 예를 들어 Gurevich는 알고리즘을 추상 상태 기계로 보는 반면, 다른 이들은 알고리즘을 재귀자(recursors)로 본다. 우리는 세 번째 관점을 제안한다. 이는 이 두 상반된 관점을 결합한 것이다. 이러한 접근—계산가능성 논리(computability logic)에 기반함—은 알고리즘을 $A(I,O)$로 기술하는데, 여기서 $I$는 입력 서비스들의 집합이고 $O$는 출력 서비스이다. 이는 다음과 같은 현대적 정의로 이어진다: {\ \it 알고리즘 $A$는, $I$를 사용하여 $O$를 제공하기 위한 합법적인 수들의 (트리의) 연속(sequence)이다. } 위에서 $A$는 명령형 언어/추상 상태 기계로 기술되며, $I$와 $O$는 재귀자/논리 명세로 기술된다.