- 영국 여권 신청 절차를 관료적 문서 수집 퍼즐로 보고, 국적 증명에 필요한 문서 조합을 Haskell 논리 탐색으로 계산한 사례임
- HMPO의 문서 요청은 신청자·부모·조부모의 출생지와 출생일, 부모의 국적·정착 상태, 혼인 여부에 따라 가계도 방향으로 재귀될 수 있음
- 해외 출생 아동의 첫 여권 신청에서 증조부의 출생증명서와 혼인증명서까지 요구됐고, 1983년 이전 UK 출생 같은 기저 사례에 닿아야 재귀가 멈춤
- 구현은 Prolog 대신 Haskell의 LogicT와
StateT Claims IO로 가능한 국적 증명Proof를 열거하고, 각 경로에 필요한Set Document를 계산함 - 같은 신청에도 여러 증명 경로가 가능해 단순한 경로가 남아 있어도 실제 요청은 더 길어질 수 있으며, 자동화는 문서 준비와 요청 이유 이해에 도움이 될 수 있음
Passport Application을 문서 수집 게임으로 보기
- UK의 Passport Application은 HMPO가 운영하는 온라인 신청 절차이며, 표준 온라인 버전은 시작 비용이 약 £100임
- 목표는 여러 관료 기관에 흩어진 원본 문서를 모아 “신청자는 British”라는 명제를 증명하는 것임
- 최종 보상은 다시 신청할 수 있는 날짜가 적힌 작은 책자, 즉 여권임
- 종이 기반 신청은 우편에 의존하는 “하드코어” 버전에 가까움
실제 신청에서 이어진 문서 요청
- 사례는 딸을 대신해 온라인으로 “first child passport born abroad” 난이도를 선택한 신청임
- 신청은 “examiner”가 처리하지만, 신청자는 채팅이나 전화의 advice agent를 통해서만 문의할 수 있음
- advice agent의 안내는 공식 결정이 아님
- examiner에게 질문을 전달하면 며칠, 사례상 최대 10일 정도의 대기 시간이 생김
- 초기 문서 요청 중 약 50% 는 채팅 서비스에서 불필요하다고 안내됐고, 이후에도 추가 문서 요청이 이어짐
- 요청 이메일에는 깨진 템플릿처럼 보이는
__APPLICANT_NAME__이 포함됐고, 부모 책임 증명 조건도 명확하지 않았음 - 최종적으로 드문 요청인 부계 증조부의 출생증명서와 혼인증명서가 요구됨
- “applicant's Paternal great grandfather”는 두 명 중 누구인지 모호할 수 있음
- 이를
applicant's father's father's father's birth certificate로 해석함
HMPO 논리를 재귀적 증명 문제로 해석하기
- HMPO의 논리는 문서 기반의 Bureaucratic Logic으로 볼 수 있음
- Constructive Logic처럼 단순한 논리적 가능성만으로는 부족함
- 증명에는 원본 문서라는 “증인”이 필요함
- 배중률
P ∨ ¬P를 그대로 사용할 수 없음- 예를 들어 “부친의 부친이 UK 출생인지 아닌지” 중 하나는 참이라고 말하고 양쪽 시나리오 문서를 모두 내는 방식은 허용되지 않음
- 하나의 대안을 선택하고 그에 맞는 문서를 제출해야 함
- HMPO 안내문에 따르면 1982년 12월 31일 이후 UK 밖에서 태어난 사람은 일반적으로 출생 당시 부모 중 한 명이 “British citizen otherwise than by descent”여야 British citizen이 됨
- HMPO가 자체 여권 기록만으로 Britishness를 증명하지 않기 때문에, 일부 신청에서는 부모·조부모 방향으로 재귀적 문서 요청이 발생함
- 재귀는 Britishness가 부모에 의존하지 않는 조상에서 멈춤
- 예: 귀화한 사람
- 예: 1983년 이전 UK 출생자, 부모와 무관하게 British인 기저 사례
사례의 요청 체인
- HMPO가 최초 문서를 받은 날짜는 6월 7일이며, 신청자의 출생증명서와 신청자 부친의 출생증명서가 포함됨
- 6월 12일 요청:
- 신청자 부친이 1983년 1월 1일 이후 출생했기 때문에, 부친의 British citizenship claim 증거가 필요하다고 안내됨
- 그 결과 부친의 부친 출생증명서가 요구됨
- 6월 26일 요청:
- 신청자의 조부가 해외 출생이므로 British citizenship claim 증거가 필요하다고 안내됨
- 이에 따라 신청자의 부계 증조부 문서가 요구됨
- 필요한 문서는 출생증명서와 혼인증명서임
- 이 재귀는 이메일 요청 형태로 진행됨
Haskell 구현 구조
- 전체 코드는 GitHub에 있음
- 처음에는 Prolog로 규칙을 인코딩하다가 Haskell의
LogicT모나드로 전환함 - 목표는 단일 문서 목록이 아니라 가능한 여러 문서 집합을 찾는 것임
- 국적 주장 방식이 여러 개라서 필요한 문서 집합도 여러 개가 될 수 있음
- 개념적으로
Set (Set Document)가 필요함
- 문서 모델은 신청자와 조상, 증명서 종류를 타입으로 표현함
Parent = Mother | FatherPerson = Applicant | Parent Parent PersonDocument = BirthCertificate Person | MarriageCertificate Person Person | NaturalizationCertificate Person | Passport Person
- 단순 문서 목록만으로는 왜 충분한지 알기 어려워, 문제를 증명 탐색으로 다룸
LogicT로 신청자의 Britishness에 대한 모든Proof를 열거함- 각
Proof에 필요한 문서 집합을 계산함
Proof와 지식 상태
- 증명 타입은 세 가지 형태로 구성됨
ViaParent Person Proof: 부모를 통한 Britishness 파생And Proof Proof: 두 개의 주장 결합Evidence Predicate: 기초 증거
- 필요한 질문은 실행 중에 사용자에게 묻고, 이전 답변은 모든 분기와 백트래킹에서 재사용함
- 이를 위해
IO,State,LogicT를 결합함type Claims = Map Predicate Knowledgetype M a = LogicT (StateT Claims IO) a
Knowledge는SureYes,SureNo,Unsure로 나뉨Predicate는 규칙 판단에 필요한 조건을 나타냄IsBritish PersonSettled PersonBornBefore Int PersonBornInUK PersonBornAfter Int PersonNaturalized PersonYears3LivingInUK PersonIsBritOtbd PersonMarried Person Person
국적 판정 규칙의 핵심
brit함수는 사람이 British인지 판단하는 루트 함수임- 먼저
IsBritish p를 확인함 - 출생에 의한 Britishness와 귀화를 통한 Britishness를 탐색함
- 먼저
- 귀화는 단순한 경로이며, 귀화증명서 하나가 핵심 문서가 됨
- UK 출생자는 크게 두 경우로 나뉨
- 1983년 이전 UK 출생이면 기저 사례로 Britishness를 얻음
- 그 이후 출생이면 부모 중 한 명이 British이거나 당시 정착 상태였는지 확인함
- UK 밖에서 태어난 경우는 더 복잡함
- 부모가 British otherwise than by descent인지 확인함
- 또는 부모가 British이고 UK에서 3년 연속 거주한 증거가 있는지 확인함
- “British otherwise than by descent”는 부모로부터만 Britishness를 받은 사람이 아닌 경우를 가리킴
- 예: 귀화
- 예: UK 출생
- 예: 해외 출생이지만 부모가 “Crown Service” 근무 중이었던 경우
부모를 통한 전파와 2006년 조건
viaParent는 자녀가 부모를 통해 Britishness를 얻는 경우를 표현함- 어머니와 아버지 양쪽 경로를 탐색하되, 아버지 경로에는 추가 조건이 붙음
- 자녀가 2006년 이후 출생이면 아버지 경로를 그대로 사용할 수 있음
- 2006년 이전 출생이면 아버지와 어머니가 출생 당시 혼인 상태였는지 확인함
- 구현에는 “registration”처럼 우회 가능한 경로와 일부 성차별적 역사 조항이 포함되지 않음
- 현재는 적용되지 않는 법도 조상의 Britishness를 판단할 때는 역사적으로 적용될 수 있음
실행 결과와 세 가지 증명 경로
run (brit Applicant)실행은 대화형 질문으로 진행됨- 예: 신청자가 UK 출생인지
- 예: 부친이 British otherwise than by descent인지
- 예: 조부모가 정착 상태였는지
- 사례에서는 총 37개 질문이 이어짐
- 사용자는
dk로 모른다고 답할 수 있고, 그러면 해당 분기를 계속 탐색함 - 결과는 신청자에게 3개의 Britishness proof가 있음을 출력함
- Proof 1:
- 신청자는 2006년 이후 출생
- 부친을 통한 Britishness
- 부친은 UK 출생
- 부친의 어머니가 출생 당시 정착 상태
- 필요한 문서는 신청자 출생증명서, 부친 출생증명서, 부친의 어머니 정착 상태 문서임
- Proof 2:
- 부친의 부친의 어머니가 1983년 이전 UK 출생자인 경로임
- 필요한 문서에는 신청자, 부친, 조부, 조부의 어머니 출생증명서와 조부모 혼인증명서가 포함됨
- Proof 3:
- 부친의 부친의 부친, 즉 부계 증조부가 1983년 이전 UK 출생자인 경로임
- 필요한 문서에는 신청자, 부친, 조부, 부계 증조부 출생증명서와 두 세대의 혼인증명서가 포함됨
- HMPO가 요구한
Birth certificate for Applicant's Father's Father's Father가 이 경로에 나타남
Crown Service와 더 복잡한 경로
- 사례에서 부계 증조부의 Crown Service 상태는 혼란을 만들었지만, 실행 결과상 해당 상태는 필요하지 않았음
- 부친의 British otherwise than by descent 상태는 UK 출생과 조부의 단순 Britishness에서 이미 도출됨
- 다만 조부의 단순 Britishness는 여전히 증명해야 하므로 재귀는 조부 세대로 내려감
- 조부의 “legitimacy”를 증명하기 위해 혼인증명서도 필요함
- HMPO가 선택한 경로는 세 가지 중 가장 길고 복잡한 Proof 3임
- Proof 1은 한 조상의 정착 상태만 증명하면 되는 더 단순한 경로임
- 비British 정착 조상을 통한 시민권은 비재귀적이라 더 단순할 수 있음
- 다만 특정 시점의 정착 상태를 증명하는 일 자체는 어려울 수 있음
구현상의 한계와 자동화 판단
orElse는 첫 번째 분기가 성공하면 두 번째 분기를 탐색하지 않지만,<|>는 양쪽 분기를 모두 탐색함- 일부 규칙에서는
<|>를 쓰면 더 많은 시민권 증명 경로가 나오지만, HMPO가 먼저 특정 경로를 소진하려는 것처럼 보이는 경우가 있음 - 구현은 특정 시점의 조건을 충분히 정밀하게 추적하지 않음
- 예: 혼인 상태나 정착 상태가 특정 인물의 출생 당시 성립해야 하는 경우
- 이는 어렵지 않게 추가할 수 있는 부분으로 봄
- 전체 UK 국적법을 구현한 것이 아니라, 사례와 관련 있거나 흥미로운 부분만 인코딩함
- 전체 구현에는 훨씬 많은 코드와 많은 예외가 필요함
- 이런 소프트웨어가 있었다면 올바른 문서 집합을 더 빠르게 만들고, 요청이 복잡해진 이유를 이해하는 데 유용했을 수 있음
- 완전 자동화에는 위험도 있음
- 프로그램이 false positive를 내면 “컴퓨터가 된다고 했다”는 항의가 생길 수 있음
- 인간 전문성을 대체하는 자동화는 “컴퓨터가 안 된다고 했다”는 이유로 시민권이 거부되는 상황으로 이어질 수 있음
- 현재 신청은 아직 끝나지 않았고, Proof 2와 Proof 3을 동시에 진행하다가 실패하면 Proof 1을 시도할 계획임