User Tools

Site Tools


study:algorithms:functional_logic_programming

함수 논리형 프로그래밍

함수형 패러다임과 논리형 패러다임이 함께 구현된 프로그래밍 언어를 말하는데, 처음에 λProlog에 의해 시작되었으면, 현대적 언어로는 CurryMurcury가 있다.

논리형 프로그래밍

논리형 프로그래밍은 주요 4개 프로그래밍 패러다임1)중 하나로, 판단문 계산방식(predicate calculus)에 기반한, 선언적 프로그래밍 방식이다. 이것은 문제에 대한 답을 찾는 절차적인 단계들에 주목하는 것이 아니라, 그 답이 가져야 하는 속성들에 주목하는 프로그래밍 방식이다. 가장 널리 사용되는 언어로는 프롤로그(Prolog)가 있으며 최근의 언어로는 머큐리(Murcury)오즈(Oz), Datalog2)가 있다.

선언형 프로그래밍

“명령형 언어와 함수 언어에서의 프로그래밍은 기본적으로 절차적 (procedural) 이다. 그것은 프로그래머가 프로그램에 의해 무엇이 성취되는지를 알고 계산이 정확하게 어떻게 수행되는지를 컴퓨터에게 지시하는 것을 의미한다. 다시 말하면, 컴퓨터는 명령을 따르는 간단한 장치로서 취급된다. 계산되는 모든 것은 계산의 모든 세부 사항이 상세히 설명되어야 한다. 어떤 사람은 이런 것이 컴퓨터 프로그래밍을 어렵게 하는 핵심이라고 믿는다.

어떤 비명령형 언어에서의 프로그래밍, 특히 논리 프로그래밍 언어에서의 프로그래밍은 비절차적이다. 이러한 언어에서의 프로그램은 결과가 계산되는 방법을 정확하게 서술하지 않고 결과의 형식을 서술한다. 차이점은 우리가 컴퓨터 시스템이 어쨌든 결과가 얻어지는 방식을 결정한다고 가정하는 것이다. 논리 프로그래밍 언어에 이 능력을 제공하기 위해 필요한 것은 적당한 정보와 원하는 계산 결과를 추론하는 방법을 컴퓨터에게 제공하는 간결한 수단이다. 수렁 해석학은 컴퓨터에 대한 기본 통신 형식을 제공하고, Robinson 에 의해 첫번째로 개발된 증명 방법은 추론 기법을 제공한다.” –논리 프로그래밍에서

제약형 프로그래밍

참고 3)

변수 간의 관계를 제약하는 형태로 프로그래밍을 기술하는 패러다임이다. 제약형 프로그래밍에서는 문제를 제약 만족 문제로 풀어버린다. 즉 어떤 변수들이 특정 도메인 영역속에서 있는데, 이 도메인(혹은 변수들)을 제약하는 제약(이것은 논리적 관계로 표현된다)의 집합이 있을 때, 이 제약을 만족하는 변수들을 찾는 것이다. 4)

제약형 프로그래밍은 가장 선언적인 프로그래밍이다.5)

명제, 논리, 관계

수학이나 철학의 명제는 참이거나 거짓이 될 수 있는 논리적인 문장으로, 객체와 객체 상호간의 관계로 구성된다. (명제과 논리에 대한 자료 더 필요함)

순수 함수

  1. 결정론적 : 함수는 항상 하나의 값을 갖는다.
  2. 입력과 출력에 대해 단지 하나의 패턴으로만 동작한다.

하지만 함수는 다른 경우도 있다.

  1. 4의 제곱근은 +2와 -2이다 : sqrt(4) ⇒ +2, -2
  2. 0으로 나누면 결과값이 없다. : divideByZero(n) ⇒ no result!

관계는 함수를 좀 더 일반화 한 것이다

  1. 비결정적 : 결과는 0개 이상이다.
  2. 입력과 출력에 대한 패턴이 매 호출마다 다를 수 있다.
  3. 실행 전략이 유연하다.
  4. 탐색으로 구현된다.

함수를 관계로 바꾸기

  1. 관계는 그 관계가 참일 때 참을 리턴하고, 거짓일 때 거짓을 리턴한다.
  2. 리턴값을 인수로 바꾼다.
(cons 1 [2])
;=> (1 2)
(conso 1 [2] [1 2])
;=> true

cons는 입력값으로 1과 [2]를 받아 (1 2)리턴하는 함수이다. conso는 1과 [2]의 cons 관계의 결과가 [1 2]임을 판단하는 판단문이다. (관계는 원래의 함수 이름에 'o'을 붙이는 것이 관례이다)

판단문으로서의 conso

conso는 모든 인수가 값이라면 판단문이 된다.

(conso 1 [2] [1 2])
;=> true
 
(conso 1 [] [1 2])
;=> false

발생기로서의 conso

인수중 하나가 변수이면 conso는 발생기로 사용된다.

(run* [x]
  (conso 1 [2] x))
;=> ((1 2))
 
(run* [x]
  (conso 1 x [1 2]))
;=> ((1))
 
(run* [x]
  (sqrto 4 x))
;=> (2 -2)

여기서 x는 논리 변수라고 한다.

core.logic

클로져 논리 프로그래밍 라이브러리

  • 클로져와 클로져스크립트를 위한 논리형 프로그래밍
  • 프롤로그 유형의 관계형 제약 프로그래밍(Relational Constraints Programming)
  • miniKanren을 구현한 것임. 또한 cKanren , aKanren등의 확장 포함.
    • KANREN : a declarative logic programming system with first-class relations, embedded in a pure functional subset of Scheme
    • miniKANREN : a simplified KANREN without many bells, whistles, and optimizations of the full system. an embedded Domain Specific Language for logic programming

함수를 관계로 전환하기

  1. 논리형 프로그래밍의 개념은 결국 관계이다.
  2. 함수 논리형 프로그래밍에서의 관계는 리턴값이 목표(Goal)인 함수이다.
  3. 목표(Goal)이란 성공(succeed)하거나 실패(fail)할 수 있다.
  4. 모든 관계는 목표(Goal)을 리턴한다.
  5. 상수처럼 사용되는 특수 목표가 있다.
    1. clojure.core.logic.minikanren/succeed 는 성공 목표를 나타낸다.
    2. clojure.core.logic.minikanren/fail 은 실패 목표를 나타낸다.

사용하기

참고6)

  (defproject logicfun "1.0.0-SNAPSHOT"
    :dependencies [[org.clojure/clojure "1.5.1"]
                   [org.clojure/core.logic "0.8.3"]])
user=> (use 'clojure.core.logic)
;>> WARNING: == already refers to: #'clojure.core/== in namespace:
;>>  user, being replaced by: #'clojure.core.logic/==

심볼 '=='이 이미 이름공간 #'clojure.core에서 정의되어 있는데, #'clojure.core/logic에서는 심볼 '=='을 unification을 재사용하고 있기 때문에 발생하는 경고인데, 무시해도 된다.

run 매크로

모든 core.logic 프로그램의 실행은 run 매크로로 이루어진다.

(run number-of-results [variable] & goals)

run 매크로는 논리 엔진에 goals를 성공으로 만족시키는 variable의 가능한 값들을 문의한다. 만약 값들이 number-of-results개가 되면 멈춘다.

run*는 number-of-results가 없는데, goals를 만족하는 가능한 모든 해를 구한다. 이 해는 무한 집합이 될 수 있어서 run*이 무한루프를 돌 수 있다.

논리 프로그램의 결과는 항상 리스트이다. 리스트는 empty일 수도 있고, 특정값이 아닌 _.0과 _.1이 될 수 있다.

() : goals가 실패
(_.0) : anything
(_.1) : 
(run 1 [q])
;=> (_.0)

'run 1 [q]'는 하나의 가능한 q값을 물어보는 것이다. 여기서 목표(goal)이 전혀 없기 때문에 q는 어떤 값이 와도 된다. 그래서 해는 (_.0) 이다.

(run 1 [q] (== 4 q))
;=> (4)

여기서 목표(goal)인 '(== 4 q)'를 만족시키는 가능한 하나의 q 값을 문의하는 것이다. 해는 (4)가 된다.

(run 1 [q] (== 4 q) (== 5 q))
;=> ()

여기서 목표(goal)인 '(== 4 q)' 와 (== 5 q) 를 동시에 만족시키는 가능한 하나의 q 값을 문의하는 것이다. 이것을 만족시키는 값은 없다. 해는 빈 리스트인 () 이다.

conde 매크로

conde는 목표들간에 OR를 가능하게 한다.

(run 1 [q] 
  (conde [(== 4 q)]
         [(== 5 q)]))
;=> (4)

여기서는 목표인 '(== 4 q)' OR '(== 5 q)'을 만족하는 변수 q의 값 하나를 구하는 것이다. 따라서 해는 (4)이다.

(run 1 [q] 
  (conde [(== 4 q)]
         [(== 5 q)]))
;=> (4)

여기서는 목표인 '(== 4 q)' OR '(== 5 q)'을 만족하는 변수 q의 값 둘을 구하는 것이다. 따라서 해는 (4 5)이다.

conde는 모든 목표를 다 시험해 본다. conde의 'e'는 everything이다.

(run 2 [q]
  (conde [(== 4 q) (== 7 q)]
         [(== 5 q)]))
;=> (5)

여기서는 AND와 OR를 같이 사용할 수 있음을 보여준다.

fresh 매크로

fresh 매크로는 새로운 변수를 도입한다. 로컬 변수를 도입하는 let과 비슷한데, 초기값 설정이 없다는 점이 다르다.

(run 1 [q]
  (fresh [a b]
    (== a 4)
    (== b 5)
    (== q [a b])))
;=> ([4 5])

여기서는 새로운 변수 a, b를 도입하고, 각각에 제약을 한후(즉 '(== a4)' 와 '(== b 5)'), 질의 변수(query variable) q가 a와 b로 된 벡터가 된다.

논리 프로그래밍은 순서에 상관없다. 다음은 위와 완전히 같다.

(run 1 [q]
  (fresh [a b]
    (== 4 a)
    (== 5 b)
    (== [a b] q)))
;=> ([4 5])

membero 매크로

membero 매크로는 컬렉션의 멤버임을 확인하는 관계를 나타낸다.

(run* [q]
  (membero q [1 2 3]))
;=> (1 2 3)
(run* [q]
  (membero q [1 2 3])
  (membero q [3 4 5]))
;=> (3)
(run* [q]
  (fresh [a]
    (membero a [1 2 3])
    (membero q [3 4 5])
    (== a q)))
;=> (3)

사용자 관계 (Custom Relation)

defrel은 사용자가 직접 관계를 만들도록 한다.

(defrel relation-name parameters)

다음은 부모 관계를 나타내는 사용자 관계이다.

(defrel parent Parent Child)

여기서 parent는 새로 만들어진 '관계'이고, Parent와 Child는 parent 관계에 입력되는 인수이다. '관계'가 만들어지면, fact/facts로 '사실'을 추가할 수 있다.

(facts parent [['father 'son]
               ['grandfather 'father]])

위에서 만든 parent 관계에 사실을 추가한다. facts는 복수의 사실을 벡터 형태로 추가한다.

(defn grandparent [gparent child]
  (fresh [p]
    (parent gparent p)
    (parent p child)))
 
(run* [q]
  (grandparent 'grandfather q))
;=> (son)
 
(run* [q]
  (grandparent q 'son))
;=> (grandfather)

Out of Tarpit

함수 논리형 프로그래밍은 프로그래밍의 성배(Holy Grail)으로 회자되고 있다.7)

리치 히키 또한 논리형 프로그래밍을 클로져에 도입하기 위해 core.logic을 받아들였지만, 주 작성자인 David Nolen이 core.logic을 주로 miniKanren에 기반하였기 때문에 상대적으로 한계가 있는 것으로 보인다.

아직까지는 Out of Tarpit의 성배 수준까지는 도달하지 못한 듯!

2)
Cascalog : a Clojure library for querying data stored on Hadoop clusters
7)
Constraint Programming: In Pursuit of the Holy Grail 1996. 프로그래밍 성배는 Gene Freuder에 의해 만들어진 단어로 '인간이여 문제를 기술하라, 그리하면 컴퓨터가 알아서 풀것이다!'를 지향한다. 특히 제약 프로그래밍에 대한 응용은 다음을 보라. Constraint Programming. 제약 프로그래밍에 대한 간단한 소개는 다음을 보라. Overview of CP
study/algorithms/functional_logic_programming.txt · Last modified: 2019/02/04 14:26 (external edit)