로직 프로그래밍과 관련하여 Prolog와 miniKanren의 주요 기술적 차이점은 무엇입니까?

로직 프로그래밍과 관련하여 Prolog와 miniKanren의 주요 기술적 차이점은 무엇입니까? [닫은]

---

논리 프로그래밍에 대해 읽고 싶을 때는 항상 두 가지 "주요"방법을 찾아 넘어 가고 있습니다.

• miniKanren , The Reasoned Schemer에 소개 된 minilanguage 는 현재 core.logic 으로 인해 인기가 있습니다.
• 첫 번째 "큰"논리 프로그래밍 언어 인 Prolog

내가 지금 관심있는 것 : 둘 사이의 주요 기술적 차이점은 무엇입니까? 그것들은 접근 방식과 구현면에서 매우 유사합니까, 아니면 논리 프로그래밍에 대해 완전히 다른 접근 방식을 취합니까? 어떤 수학 분기에서 왔으며 이론적 기초는 무엇입니까?

---

먼저, 귀하의 훌륭한 pw0n1e 아이콘을 칭찬 해 드리겠습니다.

miniKanren과 Prolog의 변종이 너무 많기 때문에 대답하기 까다로운 질문입니다. miniKanren과 Prolog는 실제로 언어의 패밀리이므로 기능을 비교하거나 실제 사용 방식을 비교하기가 어렵습니다. 이 때문에 Prolog가 깊이 우선 검색을 사용한다고 말하면 많은 Prolog 구현이 다른 검색 전략을 지원하며 대체 검색 전략도 메타에서 인코딩 될 수 있다는 점에 유의하십시오. 통역 수준. 그러나 miniKanren과 Prolog는 디자인 철학이 다르며 다른 절충점을 만듭니다.

Prolog는 상징적 인공 지능 프로그래밍을위한 두 가지 고전 언어 중 하나입니다 (다른 고전 언어는 Lisp). Prolog는 선언적 지식이 1 차 논리로 인코딩되는 기호 규칙 기반 시스템을 구현하는 데 탁월합니다. 언어는 이러한 유형의 응용 프로그램에 대한 표현력과 효율성에 최적화되어 있으며 때로는 논리적 순도를 희생합니다. 예를 들어, 기본적으로 Prolog는 통일에서 "발생 확인"을 사용하지 않습니다. 수학 / 논리적 관점에서이 통일 버전이 잘못되었습니다. 그러나 발생 점검은 비용이 많이 들며 대부분의 경우 발생 점검 부족은 문제가되지 않습니다. 이것은 프롤로그가 깊이 우선 검색을 사용하고 컷을 사용하는 것과 같이 매우 실용적인 디자인 결정입니다.!)를 사용하여 역 추적을 제어합니다. 1970 년대의 하드웨어에서 실행할 때 이러한 결정이 절대적으로 필요했다고 확신합니다. 오늘날 큰 문제를 처리하고 거대한 (종종 무한대) 검색 공간을 처리 할 때 매우 유용합니다.

프롤로그는 잘라 내기 assert및 retract,를 사용하여 산술 변수의 투영 등을 포함하여 많은 "외부"또는 "논리"기능을 지원 is합니다. 이러한 많은 기능을 통해 복잡한 제어 흐름을보다 쉽게 ​​표현하고 Prolog의 글로벌 사실 데이터베이스를 조작 할 수 있습니다. Prolog의 매우 흥미로운 기능 중 하나는 Prolog 코드 자체가 전역 사실 데이터베이스에 저장되어 있으며 런타임에 쿼리 할 수 ​​있다는 것입니다. 이것은 해석 하에서 Prolog 코드의 동작을 수정하는 메타 해석기를 작성하는 것이 쉽지 않습니다. 예를 들어, 검색 순서를 변경하는 메타 해석기를 사용하여 Prolog에서 너비 우선 검색을 인코딩 할 수 있습니다. 이것은 프롤로그 세계 외부에서는 잘 알려지지 않은 매우 강력한 기술입니다. '프롤로그 기술'

프롤로그 구현을 개선하기 위해 많은 노력을 기울였으며, 대부분 WAM (Warren Abstract Machine)을 기반으로합니다. WAM은 역 추적시 취소되지 않은 논리 변수에 값이 파괴적으로 할당되는 부작용 모델을 사용합니다. WAM의 지침을 확장하여 많은 기능을 Prolog에 추가 할 수 있습니다. 이 접근법의 한 가지 단점은 WAM에 대한 확실한 이해없이 Prolog 구현 문서를 읽기가 어렵다는 것입니다. 반면, Prolog 구현자는 구현 문제를 논의하기위한 공통 모델을 가지고 있습니다. 병렬 프롤로그에 대한 많은 연구가 있었으며 1990 년대 안도라 프롤로그에서 절정에 이르렀습니다. 이러한 아이디어 중 적어도 일부는 Ciao Prolog에 있습니다. (Ciao Prolog는 흥미로운 아이디어로 가득 차 있으며 많은 아이디어가 Prolog 표준을 훨씬 뛰어 넘습니다.)

프롤로그는 통일 기반의 "패턴 일치"스타일 구문을 사용하여 간결한 프로그램을 만들었습니다. Lispers가 s- 표현식을 좋아하는 것처럼 프롤로 저는 구문을 좋아합니다. Prolog에는 또한 큰 표준 술어 라이브러리가 있습니다. WAM을 빠르게 만드는 데 필요한 모든 엔지니어링으로 인해 매우 유능하고 성숙한 프롤로그 구현이 있습니다. 그 결과 많은 지식 기반 시스템이 전적으로 Prolog로 작성되었습니다.

miniKanren은 작고 이해하기 쉽고 쉽게 해킹 할 수있는 최소 논리 프로그래밍 언어로 설계되었습니다. miniKanren은 원래 Scheme에 내장되어 있으며 지난 10 년 동안 수십 개의 다른 호스트 언어로 이식되었습니다. 가장 인기있는 miniKanren 구현은 Clojure의 'core.logic'으로, 현재 많은 프롤로그 유사 확장 기능과 많은 최적화 기능이 있습니다. 최근 miniKanren 구현의 핵심이 더욱 단순화되어 "microKanren"이라는 작은 "마이크로 커널"이 만들어졌습니다. 그런 다음 miniKanren을이 microKanren 코어 위에 구현할 수 있습니다. microKanren 또는 miniKanren을 새로운 호스트 언어로 이식하는 것은 miniKanren을 배우는 프로그래머에게 표준 연습이되었습니다. 결과적으로

miniKanren 및 microKanren의 표준 구현에는 단일 예외를 제외하고는 돌연변이 나 다른 부작용이 없습니다. 일부 버전의 miniKanren은 논리 변수를 비교하기 위해 포인터 동등성을 사용합니다. 많은 구현에서 구현을 통해 카운터를 전달하여이 효과조차 피할 수 있지만이 방법을 "양성 효과"라고 ​​생각합니다. 글로벌 팩트 데이터베이스도 없습니다. miniKanren의 구현 철학은 함수형 프로그래밍에서 영감을 얻었습니다. 돌연변이와 효과는 피해야하며 모든 언어 구성은 어휘 범위를 존중해야합니다. 구현을주의 깊게 보면 몇 개의 모나드를 발견 할 수도 있습니다. 검색 구현은 돌연변이를 사용하지 않고 지연 스트림을 결합하고 조작하는 것을 기반으로합니다. 이러한 구현 선택은 Prolog와는 매우 다른 절충점을 초래합니다. Prolog에서 변수 조회는 일정한 시간이지만 역 추적을 실행하려면 부작용을 취소해야합니다. miniKanren에서 변수 조회는 더 비싸지 만 역 추적은 "무료"입니다. 실제로, 스트림 처리 방식으로 인해 miniKanren에는 역 추적이 없습니다.

miniKanren 구현의 흥미로운 측면 중 하나는 코드가 본질적으로 스레드로부터 안전하고 이론적으로는 거의 병렬화 가능하다는 것입니다. 물론, 각 스레드 또는 프로세스에 병렬 처리 오버 헤드를 보충 할 수있는 충분한 작업을 제공해야 하기 때문에 코드를 느리게 만들지 않고 병렬화하는 것은 쉽지 않습니다. 아직도, 이것은 miniKanren 구현 영역으로 더 많은 관심과 실험을 받기를 바랍니다.

miniKanren은 통일을 위해 발생 확인을 사용하고 깊이 우선 검색 대신 완전한 인터리빙 검색을 사용합니다. 인터리빙 검색은 깊이 우선 검색보다 더 많은 메모리를 사용하지만 일부 경우 깊이 우선 검색이 영구적으로 분기 / 루프되는 경우에 대한 답을 찾을 수 있습니다. miniKanren는 않는 몇 가지 추가 - 논리 연산자 --- 지원 conda, condu및 project, 예를. conda그리고 condu프롤로그 컷을 시뮬레이션하는 데 사용 될 수 있으며, project논리 변수와 관련된 값을 취득 할 수 있습니다.

의 존재 conda, condu그리고project--- 검색 전략을 쉽게 수정할 수있는 기능-프로그래머는 miniKanren을 내장 프롤로그와 유사한 언어로 사용할 수 있습니다. 이것은 특히 Prolog와 유사한 확장을 포함하는 Clojure의 'core.logic'사용자에게 해당됩니다. miniKanren의 이러한 "실용적인"사용은 산업에서 miniKanren의 대다수를 차지하는 것으로 보입니다. Clojure 또는 Python 또는 JavaScript로 작성된 기존 응용 프로그램에 지식 기반 추론 시스템을 추가하려는 프로그래머는 일반적으로 Prolog에서 전체 응용 프로그램을 다시 작성하는 데 관심이 없습니다. Clojure 또는 Python에 작은 논리 프로그래밍 언어를 포함시키는 것이 훨씬 매력적입니다. 내장 된 Prolog 구현은 아마도이 목적을 위해서도 잘 작동 할 것입니다.

In addition to the use of miniKanren as a pragmatic embedded logic programming language similar in spirit to Prolog, miniKanren is being used for research in "relational" programming. That is, in writing programs that behave as mathematical relations rather than mathematical functions. For example, in Scheme the append function can append two lists, returning a new list: the function call (append '(a b c) '(d e)) returns the list (a b c d e). We can, however, also treat append as a three-place relation rather than as a two-argument function. The call (appendo '(a b c) '(d e) Z) would then associate the logic variable Z with the list (a b c d e). Of course things get more interesting when we place logic variables in other positions. The call (appendo X '(d e) '(a b c d e)) associates X with (a b c), while the call (appendo X Y '(a b c d e)) associates X and Y with pairs of lists that, when appended, are equal to (a b c d e). For example X = (a b) and Y = (c d e) are one such pair of values. We can also write (appendo X Y Z), which will produce infinitely many triples of lists X, Y, and Z such that appending X to Y produces Z.

This relational version of append can be easily expressed in Prolog, and indeed is shown in many Prolog tutorials. In practice, more complex Prolog programs tend to use at least a few extra-logical features, such as cut, which inhibit the ability to treat the resulting program as a relation. In contrast, miniKanren is explicitly designed to support this style of relational programming. More recent versions of miniKanren have support for symbolic constraint solving (symbolo, numbero, absento, disequality constraints, nominal logic programming) to make it easier to write non-trivial programs as relations. In practice I never use any of the extra-logical features of miniKanren, and I write all of my miniKanren programs as relations. The most interesting relational programs are the relational interpreters for a subset of Scheme. These interpreters have many interesting abilities, such as generating a million Scheme programs that evaluate to the list (I love you), or trivially generating quines (programs that evaluate to themselves).

miniKanren makes a number of trade-offs to enable this relational style of programming, which are very different from the trade-offs Prolog makes. Over time miniKanren has added more symbolic constraints, really becoming a symbolically-oriented Constraint Logic Programming language. In many cases these symbolic constraints make it practical to avoid using extra-logical operators like condu and project. In other cases, these symbolic constraints are not sufficient. Better support for symbolic constraints is one active area of miniKanren research, along with the broader question of how to write larger and more complex programs as relations.

In short, both miniKanren and Prolog have interesting features, implementations, and uses, and I think it is worth learning the ideas from both languages. There are other very interesting logic programming languages as well, such as Mercury, Curry, and Gödel, each of which has its own take on logic programming.

I'll end with a few miniKanren resources:

The main miniKanren website: http://minikanren.org/

An interview I gave on relational programming and miniKanren, including a comparison with Prolog: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

Cheers,

--Will

---

Tentative answer:

AFAIK, "The Reasoned Schemer" introduced basic logic programming in a Scheme-y syntax and functional programming style, adding in particular the constant goals "#u" (fail) and "#s" (suceeed) to the boolean values "#t" and "#f". It used the same approach to logic programming as Prolog: Unification and backtracking search. I will see whether I have some time to retrieve that book from my shelf over the weekend. The branch of mathematics is a restricted form first-order logic, in this case Horn clauses, and the Resolution Unfication. See: Computational Logic: Memories of the Past and Challenges for the Future by John Alan Robinson and The early years of logic programming by Robert Kowalski for a cold start.

참고URL : https://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp