- Picat의
planner모듈은 값 할당을 찾는 논리 프로그래밍에서 한 단계 나아가, 목표 상태까지 가는 상태 변경 시퀀스를 문제로 표현함 - 시작 상태
Start, 전이 규칙action(From, To, Action, Cost), 종료 조건final(S)를 정의하면best_plan(Start, Plan)이 최종 상태까지의 최소 비용 계획을 찾아줌 - 격자 경로 예제에서는 이동, 경계 제한, 장애물 회피, 여러 목표 방문을
action과final변경만으로 다루며 목표 방문 순서도 고정하거나 자유롭게 바꿀 수 있음 - 계획 기능은 제약 해결과 결합되어, partition problem에서 원소를 제거해 같은 합으로 나눌 수 있는 가장 큰 부분 리스트를 찾는 식의 문제도 표현 가능함
- Picat은 연구 언어라 문서와 오류 메시지가 부족하지만, 특정 계산 문제를 빠르게 풀기 위한 도구형 언어로는 일반 언어보다 간결한 해법을 줄 수 있음
Picat과 플래너 프로그래밍의 기본 아이디어
- Picat은 논리 프로그래밍, 명령형 프로그래밍, 제약 해결을 결합하려는 연구 언어임
- 일반적인 명령형·함수형 프로그래밍은 입력에서 출력을 만드는 알고리듬을 작성하지만, 논리 프로그래밍과 제약 해결은 관계를 만족하는 값 할당을 찾음
- Picat에서 소문자로 시작하는 비함수 식별자는
a,b,c같은 atom이고, 대문자로 시작하는 식별자는 변수임 - 아직 정의되지 않은 변수
Y가 들어간member(Y, Arr)같은 식에서도 Picat은 식을 참으로 만드는 값을 찾아 할당할 수 있음Arr = [a, b, c, a]이면Y는a,b,c중 하나가 될 수 있음- 이어서
X != Y같은 조건을 넣으면 가능한 값이 더 좁아짐 member(a, Z)처럼 리스트 자체를 아직 모르는 상태에서도Z를 리스트로 인스턴스화할 수 있음
계획은 값 할당이 아니라 상태 변경을 찾음
- 계획(planning)은 방정식을 만족하는 변수 값을 찾는 대신, 특정 종료 상태에 도달하는 변수 변경 시퀀스를 찾음
- Picat의 계획 문제에는 세 가지 요소가 필요함
- 시작 상태
Start - 상태 전이를 나타내는
action함수들 - 상태가 종료 상태인지 판단하는
final(S)
- 시작 상태
- Picat의
action함수는 모두 이름이action이어야 하며, 네 매개변수를 받음- 현재 상태
- 다음 상태
- 액션 이름
- 비용
best_plan(Start, Plan)은 종료 상태까지 필요한 최단 단계 또는 최소 비용 계획을Plan에 할당함- 비용을 모두
1로 두면 계획의 비용은 총 이동 단계 수가 됨 - 어떤 길이든 상관없이 아무 계획만 필요하면
plan(Start, Plan)을 사용할 수 있음
- 비용을 모두
격자 경로 찾기 예제
- 예제 문제는 격자 위 마커가 원점
(0, 0)에서 출발해 목표 좌표에 도달하는 것임- 각 단계마다 상하좌우 한 칸씩 이동 가능함
- 격자 경계 밖으로는 나갈 수 없음
- 목표 좌표에 도착하면 성공함
- 시작 상태는
{Origin, Goal}처럼 현재 위치와 목표를 함께 담음- Picat의
{a, b}는 배열 문법이며 사실상 튜플처럼 사용됨
- Picat의
final({Pos, Goal}) => Pos = Goal.처럼 패턴 매칭으로 종료 조건을 표현할 수 있음- 같은 내용을 패턴 매칭 없이 쓰려면 상태를 먼저
{Pos, Goal}로 분해해야 함 final조건이 여러 개 있으면 그중 하나라도 참일 때 계획이 성공함
- 같은 내용을 패턴 매칭 없이 쓰려면 상태를 먼저
- 이동 액션은 네 방향
{-1,0},{1,0},{0,-1},{0,1}중 하나를 선택하고, 새 좌표가0..10범위에 있는지 검사함member({Dx, Dy}, Dir)는 가능한 방향 값을 찾는 데 사용됨member(Tx, 0..10)과member(Ty, 0..10)은 좌표가 경계 안에 있는지 검사하는 데 쓰임- 값을 할당하지 않는 검사 전용 predicate로는
membchk도 있음
- 결과 계획은
{move,{1,0}},{move,{2,0}}처럼 이동 액션과 새 좌표의 목록으로 출력됨- Raku 스크립트로 경로를 시각화할 수 있음
{Tx, Ty} != {2, 1}같은 조건을 추가하면 특정 좌표를 피하는 장애물 회피도 가능함
여러 목표와 비용 최소화
- 여러 목표를 방문하려면
Goal을 단일 좌표가 아니라[{2, 2}, {3, 4}]같은 목표 큐로 바꿈 - 목표에 도착했을 때 목표 목록에서 해당 항목을 제거하는 새
action을 추가함[Head|Tail]은 리스트를 첫 원소와 나머지로 나눔Goal = [Pos|Rest]는 현재 위치Pos가 목표 목록의 첫 항목과 같을 때만 참이 됨- 새 상태를
{Pos, Rest}로 두면 도달한 목표가 제거됨
- 목표를 모두 방문했는지는
final({Pos, Goal}) => Goal = [].로 판단함- 현재 위치가 특정 목표와 같은지가 아니라, 목표 목록이 비었는지가 종료 조건이 됨
- 목표를 정해진 순서대로 방문하는 방식이 항상 전체 최단 경로를 만들지는 않음
- 목표 순서를 무시하고 전체 경로를 최소화하려면
mark액션을 바꿈Goal = [Pos|Rest]대신member(Pos, Goal)로 현재 위치가 목표 목록 어디든 포함되는지 검사함To = {Pos, delete(Goal, Pos)}로 방문한 목표를 목록에서 제거함- 이 방식에서는 Picat이 다음에 갈 목표를 선택해 전체 경로 길이를 최소화할 수 있음
계획과 제약 해결의 결합
- Picat의 계획 기능은 다른 Picat 기능과 통합되며, 계획과 제약 해결을 함께 사용할 수 있음
- 예제로 다룬 partition problem은 숫자 리스트를 합이 같은 두 그룹으로 나누는 NP-complete 문제임
- 이 프로그램은 숫자 리스트에서 원소를 제거해, 같은 합으로 나눌 수 있는 가장 큰 부분 리스트를 찾음
- 입력 숫자 목록에서 원소를 제거하는 것을 계획 액션으로 둠
final(Numbers)는 해당 숫자 목록에 유효한 partition 해가 있는지 검사함cp모듈의 제약으로 각 원소가 왼쪽 또는 오른쪽 그룹에 들어가는지를0..1변수로 표현함- 전체 합이 한쪽 그룹 합의 두 배가 되도록 제약을 둠
- 예제 출력에서는
[5,17]을 제거한 뒤 남은 리스트를 두 그룹으로 나눠 각각 합1108을 만들 수 있음32+99+977=1108122+77+86+59+47+154+141+172+49+62+109+30=1108
- 이 방식은 유효한 제약을 직접 푸는 데서 그치지 않고, 유효한 제약 상태에 도달하기 위한 변경까지 계획으로 표현함
Picat을 쓸 때의 한계와 적합한 용도
- Picat은 연구 언어라 프로덕션 사용에는 권장되지 않음
- 편의 기능이 많지 않고, 좋은 문서나 명확한 오류 메시지도 부족함
- 해결 가능한 계획이 없을 때 오류는
*** error(failed,main/0)처럼 출력됨
- 해결 가능한 계획이 없을 때 오류는
- Windows에서 실행 가능하다는 점은 많은 연구 언어보다 낫다고 평가됨
- Picat은 유지보수하거나 공유할 코드를 작성하는 언어라기보다, 특정 종류의 계산 문제를 풀기 위한 툴킷 언어에 가까움
- 일반 프로그래밍 언어와 제약 해결기로 처리하기 어려웠던 일부 문제를 Picat으로는 꽤 우아하게 풀 수 있음