이색적인 프로그래밍 아이디어: 2부 (항 재작성)
지난주에 이어 이번에는 항 재작성이라는 주제를 다루겠습니다. 항 재작성은 매우 일반적인 계산 모델로, 항(term)이라 불리는 표현식을 다른 항들의 집합으로 변환하는 변환(규칙(rule)이라 부릅니다)을 기술하는 프로그램적 체계로 이루어져 있습니다.
가장 널리 쓰이는 재작성 엔진은 논리 프로그래밍, 증명 보조기, 컴퓨터 대수 시스템에 사용되는 프로그램과 언어의 핵심에 자리 잡고 있는 경우가 많습니다. 그중 가장 대중적인 것 중 하나가 Mathematica와 Wolfram 언어입니다. 이는 Wolfram Research사가 과학 계산 프레임워크의 일부로 제공하는 독점 프로그래밍 언어입니다. 이 시스템의 핵심(Core)에는 수학적 표현식을 나타내는 복합 기호 표현식을 조작할 수 있는 재작성 시스템이 있습니다. Maude, Pure, Aldor 및 일부 Lisp 변종과 같은 다른 언어들도 비슷한 시스템을 구현하지만, 이 글의 예제에서는 보다 일반적인 개념을 보여 주기 위해 Mathematica로 작성한 코드를 사용하겠습니다.
Mathematica는 보통 노트북 환경에서 실행되며, 여기서 In과 Out 표현식은 REPL에 입력된 각 줄마다 단조 증가하는 인덱스로 색인되는 벡터입니다.
Wolfram Language 12.0.1 Engine for Linux x86 (64-bit)
Copyright 1988-2019 Wolfram Research, Inc.
In[1]:= 1+2
Out[1]= 3
In[2]:= 1+2+x
Out[2]= 3 + x
In[3]:= List[x,y,z]
Out[3]= {x, y, z}
이 언어 자체는 정신적으로 표현식을 다루는 Lisp이며, 이 표현식에는 기호 항(위의 x 항과 같은)이 포함될 수 있습니다. 이러한 표현식은 변수가 아니라, 표현식 안에서 변수를 나타내는 더 이상 환원할 수 없는 원자입니다. 합성 표현식은 Lisp의 S-표현식과 비슷하며, 머리(head) 항과 그 표현식의 인수인 중첩된 하위 표현식들의 집합으로 이루어져 있습니다.
F[x,y]
이 경우 F가 머리이고 x와 y가 인수입니다. 이러한 형태의 표기법을 M-표현식이라고 합니다. 핵심적인 표기상의 특징은 모든 언어 구성 요소 자체가 기호 표현식이며, 규칙에 의해 내부를 들여다보고 변환할 수 있다는 점입니다. 예를 들어 Head 함수는 주어진 표현식에서 머리 기호를 추출합니다.
In[4]:= Head[f[a,b,c]]
Out[4]= f
In[5]:= Symbol["x"]
Out[5]= x
In[6]:= Head[x]
Out[6]= Symbol
주어진 M-표현식의 인수는 Level 함수를 사용하여 추출할 수 있는데, 이 함수는 주어진 깊이의 인수들을 벡터(중괄호로 표시됩니다)로 추출합니다. 이 경우 첫 번째 레벨은 인수 a, b, c입니다.
In[7]:= Level[f[a,b,c],1]
Out[7]= {a, b, c}
표현식은 여러 형태로 작성할 수 있으며, 이들은 모두 이 기본 M-표현식 형태로 환원됩니다. 예를 들어 덧셈 연산은 Plus 머리를 가진 표현식에 대한 문법적 설탕일 뿐입니다. FullForm 함수를 사용하면 이 표현식을 내부 정규 형태로 환원할 수 있습니다. 곱셈 역시 일반 대수학에서 쓰이는 관례와 비슷하게, 개별 항을 공백으로 구분하는 중위 표기로 나타냅니다.
In[8]:= FullForm[x+y]
Out[8]//FullForm= Plus[x, y]
In[9]:= FullForm[x y]
Out[9]//FullForm= Times[x, y]
중위 문법적 설탕 외에도 두 연산자 @와 //를 사용하면 각각 전위 또는 후위 형태로 함수를 인수에 적용할 수 있습니다.
In[10]:= Sin[x] (* Full form *)
Out[10]= Sin[x]
In[11]:= Sin @ x (* Prefix sugar *)
Out[11]= Sin[x]
In[12]:= x // Sin (* Postfix sugar *)
Out[12]= Sin[x]
복잡한 수학적 표현식은 단지 항들의 중첩된 조합일 뿐입니다. 예를 들어 간단한 단항식 표현식 은
다음과 같이 나타냅니다:
In[13]:= FullForm[x^3 + (1 + x)^2]
Out[13]//FullForm= Plus[Power[x, 3], Power[Plus[1, x], 2]]
In[14]:= TeXForm[x^3 + (1 + x)^2]
Out[14]//TeXForm= x^3+(x+1)^2
이 표현식 자체는 그래프 구조이며, 그 구현은 하위 표현식을 가리키는 포인터를 가진 노드들의 집합으로 이루어져 있습니다. 대괄호를 사용하는 인덱스 표기법으로 주어진 하위 표현식을 직접 조작할 수 있으며, 하위 표현식은 머리 항부터 시작하여 왼쪽에서 오른쪽으로 번호가 매겨집니다.
In[15]:= f[a,b,c][[0]]
Out[15]= f
In[16]:= f[a,b,c][[1]]
Out[16]= a
In[17]:= f[a,b,c][[2]]
Out[17]= b
표현식의 개별 인자는 인덱스로 슬롯을 참조하여 순서를 바꾸거나 다른 표현식에 대입할 수 있습니다.
In[18]:= F[#3, #1, #2] & [x, y, z]
Out[18]= F[z, x, y]
복잡한 수학 표현식은 표현식의 그래프로 표현할 수 있으며, 그래픽 트리 형태로 렌더링할 수 있습니다. 사실상 이 시스템의 모든 규칙과 함수는 유향 그래프를 다른 유향 그래프 구조로 변환하는 것입니다. 예를 들어 간단한 삼각 급수는 다음과 같이 기호적으로 표현할 수 있습니다.
In[19]:= Series[Cos[x]/x, {x, 0, 10}]
이는 내부적으로 다음과 같은 M-표현식의 그래프 구조로 표현됩니다.
In[20]:= FullForm[Series[Cos[x]/x, {x, 0, 10}]]
Out[20]//FullForm= SeriesData[x, 0, {1, 0, Rational[-1, 2], 0, Rational[1, 24], 0, Rational[-1, 720], 0, Rational[1, 40320], 0, Rational[-1, 3628800], 0, Rational[1, 39916800]}, 0, 11, 1]
이 기호 표현식은 Series 항을 평가하여 개별 항으로 전개할 수 있습니다.
평가 순서
이 언어에서 평가는 축약된 표현식에 더 이상 적용할 규칙이 없을 때까지 항을 축약하는 방식으로 진행됩니다. 이러한 표현식을 정규형(normal form)에 있다고 합니다. 이러한 평가 방식은 메모리를 순차적으로 갱신하고 부수 효과가 있는 문장을 차례로 실행하는 것이 실행 방식인 순차적, 문장 기반 언어와는 다릅니다.
예를 들어 Range 함수는 일련의 값을 리스트로 생성합니다. 이 리스트는 다시 각 원소에 함수를 적용하는 다른 함수에 전달할 수 있으며, 예를 들어 주어진 정수가 소수인지 질의하는 함수를 적용할 수 있습니다.
In[20]:= Range[1,10]
Out[20]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
In[21]:= Map[PrimeQ, Range[1,10]]
Out[21]= {False, True, True, False, True, False, True, False, False, False}
이 불리언 시퀀스가 최종 형태이며, 범위 내에서 더 이상 적용할 수 있는 규칙이 없으므로 최종 표현식이 반환됩니다.
규칙
사용자 정의 로직을 환경에 새로 도입하는 주된 메커니즘은 재작성 규칙을 도입하는 것입니다. 재작성 규칙은 Rule 정의 또는 그 중위 문법 설탕인 ->로 정의합니다. 좌변은 패턴 문법으로 주어지며, 우변에 걸쳐 변수 정의를 바인딩할 수 있습니다.
예를 들어 정수 1의 모든 출현을 2로 재작성하는 규칙은 다음과 같습니다.
In[22]:= Rule[1,2]
Out[22]= 1 -> 2
또는 기호 x의 명시적인 출현을 각각 기호 y로 변환하는 규칙은 다음과 같습니다.
In[23]:= Rule[x,y]
Out[23]= x -> y
하위 표현식과 매칭되어 규칙의 범위 안에서 그것에 이름을 붙이는 패턴 변수를 도입할 수도 있습니다. 이 “구멍(hole)“에 대한 매칭 결과는 규칙의 우변에 걸쳐 변수 이름으로 바인딩됩니다. 예를 들어 임의의 양 x_와 매칭하여 이를 정의 x에 바인딩하는 규칙은 다음과 같습니다.
In[24]:= Rule[x_,x]
Out[24]= x_ -> x
더 유용하게도, 이러한 패턴 변수는 표현식 내부에 나타날 수 있습니다. 예를 들어 사인 함수에 주어진 모든 인자를 코사인 함수로 재작성하고 싶다면 다음과 같은 규칙을 작성할 수 있습니다.
In[25]:= Sin[x_] -> Cos[x]
Out[25]= Sin[x_] -> Cos[x]
규칙은 ReplaceAll 함수나 그 중위 형태인 /.를 사용하여 주어진 표현식에 적용할 수 있으며, 이는 주어진 규칙을 왼쪽의 표현식에 적용합니다.
In[26]:= ReplaceAll[x, Rule[x,y]]
Out[26]= y
In[27]:= x /. Rule[x,y]
Out[27]= y
앞의 삼각함수 예제에서는 표현식 본문 안에 중첩된 삼각함수를 재작성할 수 있습니다.
In[28]:= Sin[a+b] /. Sin[x_] -> Cos[x]
Out[28]= Cos[a + b]
규칙 리스트를 ReplaceAll의 인자로 전달하여 규칙을 결합할 수 있습니다. 예를 들어 다음은 주어진 리스트를 한 번 순회하면서 모든 x를 y로, 모든 y를 z로 재작성합니다.
In[29]:= {x,y,z} /. {x->y, y->z}
Out[29]= {y, z, z}
규칙은 직전 규칙이 만든 중간 표현식에 순서대로 적용되므로, 이것은 리스트 전체를 같은 원소로 변환하지 않습니다. 그러나 ReplaceRepeated 함수는 고정점에 도달하여 항이 직전 축약 결과와 동일해질 때까지 주어진 규칙 집합을 반복해서 적용합니다.
In[30]:= ReplaceRepeated[x, Rule[x,y]]
Out[30]= y
In[31]:= ReplaceRepeated[x, {Rule[x,y], Rule[y,z]}]
Out[31]= z
In[32]:= {x,y,z} /. {x->y, y->z} (* Non-repeated *)
Out[32]= {y, z, z}
In[33]:= {x,y,z} //. {x->y, y->z} (* Repeated *)
Out[33]= {z, z, z}
이 과정이 무한히 반복되기만 하고 수렴하지 않는 규칙 집합을 정의하는 것도 충분히 가능합니다. 이러한 경우에는 정규형이 없으며, 시간(또는 공간)이 폭증하거나 런타임이 포기할 때까지 계속됩니다.
In[34]:= {1,2} //. {1 -> 2, 2 -> 1}
ReplaceRepeated::rrlim: Exiting after {1, 2} scanned 65536 times.
대수적 변환
많은 규칙 집합은 여러 재작성 경로를 허용하며, 이 경로들이 반드시 같은 최종 항에 도달하는 것은 아닙니다. 재작성 순서를 어떻게 선택하든 최종 결과에 차이가 없는 규칙 체계를 합류적(confluent)이라고 합니다. 런타임 내부의 재작성 규칙에서는 평가 순서에 대한 규정이 사용됩니다. 이는 임의적인 선택이지만, Mathematica는 표현식의 헤드를 먼저 평가한 다음 표현식의 각 원소를 평가합니다. 이 원소들은 그 자체로 표현식이며, 동일한 평가 절차가 재귀적으로 적용됩니다.
표준 라이브러리에는 대수적 단순화와 항 재배열을 다루기 위한 이러한 변환 집합이 많이 있습니다. FullSimplify 함수는 가장 범용적인 함수로, 내부에 정의된 방대한 항등식과 관계의 집합에 따라 실숫값 대수 표현식을 정리하고 단순화합니다.
In[35]:= FullSimplify[x^2 x + y x + z + x y]
Out[35]= Plus[Power[x, 3], Times[2, x, y], z]
그러나 이러한 규칙 집합을 우리가 직접 도입하고 확장할 수도 있습니다. 예를 들어 주어진 항등식에 따라 삼각함수를 단순화하는 간단한 규칙 집합을 새로 인코딩하고 싶다면, 다음 수학 항등식에 대한 규칙을 작성할 수 있습니다.
이는 다음과 같은 두 개의 패턴과 재작성으로 인코딩됩니다:
In[36]:= ElemTrigExpand = {
Sin[a_ + b_] -> Sin[a] Cos[b] + Cos[a] Sin[b],
Cos[a_ + b_] -> Cos[a] Cos[b] - Sin[a] Sin[b]
}
그런 다음 이를 선형 인수를 갖는 삼각함수에 반복적으로 적용하여 중첩된 항을 단일 변수로 축약할 수 있습니다.
In[37]:= Sin[a+b+c] //. ElemTrigExpand
Out[37]= Cos[a] (Cos[c] Sin[b] + Cos[b] Sin[c]) Sin[a] (Cos[b] Cos[c] + Sin[b] Sin[c])
속성과 성질
규칙 안에 나타나는 항은 규칙이 디스패치할 수 있는 추가 구조를 가질 수도 있습니다. 기호에는 Attributes를 정의할 수 있으며, 이는 기호를 정규형으로 축약하고 재배열하는 데 활용됩니다. 흔히 결합법칙, 교환법칙, 항등원, 소멸 같은 일반적인 대수적 성질이 이에 해당합니다.
In[38]:= Attributes[f] = {Flat, OneIdentity}
Out[38]= {Flat, OneIdentity}
In[39]:= f[1, f[2, f[3, 4]]] (* Associative *)
Out[39]= f[1, 2, 3, 4]
In[40]:= f[f[1]] (* Idempotent *)
Out[40]= f[1]
함수의 구조적 성질 외에도, 기호에는 그 출처와 정의역 또는 그 기호가 속한 집합에 대한 가정을 덧붙일 수 있습니다. 예를 들어 주어진 수가 0이 아닌지, 정수(적분)인지, 소수인지, 또는 주어진 집합의 원소인지와 같은 것입니다. 이러한 성질은 그 자체로 기호 표현식이므로, 예를 들어 주어진 변수 z가 복소평면에 속한다는 가정을 인코딩하고 싶다면:
다음과 같은 표현식을 작성할 수 있으며, 여기서 Complexes는 를 나타내는 내장 기호입니다.
이러한 가정은 변수 Assumptions로 정의되는 전역 가정 집합에 추가할 수 있습니다.
In[42]:= $Assumptions = {a > 0, b > 1}
Out[42]= a > 0
이러한 대수적 단순화를 재작성할 때는 redex에서 만나는 항의 가정에 따라 디스패치하며, 기호의 성질에 대한 연쇄적인 추론에 근거하여 서로 다른 축약 경로를 택합니다. 예를 들어 제곱의 제곱근이 원래 값으로 축약된다는 항등식은 주어진 기호의 부호에 따라 달라집니다. Refine 함수를 사용하면 전역 가정을 반영하여 단순화기에 어느 분기를 선택할지 알려 줄 수 있습니다.
In[43]:= Refine[Sqrt[a^2 b^2]]
Out[43]= a b
이 함수를 사용하여 기호에 대한 술어의 진릿값을 질의할 수도 있습니다. 그 결과는 True나 False가 되며, 기호에 대한 국소 가정이 없으면 판정할 수 없다는 답이 나옵니다.
In[44]:= Refine[Positive[b]]
Out[44]= True
In[45]:= Refine[Positive[x]]
Out[45]= Positive[x] (* Has no truth value *)
또한 많은 함수가 Assumptions라는 이름의 매개변수를 받으며, 이를 사용하여 함수에 주어진 인수에 대한 국소 가정을 도입할 수 있습니다.
In[46]:= Refine[Sqrt[x^2], Assumptions -> {x < 0}]
Out[46]= -x
가정 시스템은 특정 영역 안에서 기호의 성질을 추론하기 위해 제한적인 1차 논리 도출(resolution)을 수행할 수 있습니다. 예를 들어 x > 1이라는 가정은 x가 0이 아니며 음수가 아니라는 사실을 함의합니다. 또는 정수 y가 y > 2이고 소수라는 가정은 y가 짝수가 아님을 함의합니다.
규칙의 좌변에 있는 패턴은 식의 타입뿐 아니라 패턴 변수의 가정과 속성에 따라서도 분기할 수 있습니다. 예를 들어 좌변 x_Symbol은 모든 기호적 양(숫자는 제외)과 매칭되며, 이를 주어진 상수로 재작성할 수 있습니다. 이것은 List 자체의 헤드와도 매칭되어 그 헤드를 상수로 재작성한다는 점에 유의하십시오.
In[47]:= {1, x, Pi} /. x_Symbol -> 0 (* Matches List, x, Pi *)
Out[47]= 0[1, 0, 0]
_?s 접미사 뒤에 함수를 붙이면 패턴 변수에 술어 함수를 씌울 수 있습니다. 예를 들어 주어진 항이 수치적인 양인지 확인하려면 NumericQ 함수를 사용할 수 있습니다. 이것은 Pi와 1 항에는 매칭되지만 List나 1 항에는 매칭되지 않습니다.
In[48]:= {1, x, Pi} /. x_?NumericQ -> 0 (* Matches 1, Pi *)
Out[48]= {0, x, 0}
특수 함수
표준 라이브러리에는 기호적 양에 대한 가정과 규칙의 라이브러리로 인코딩된 방대한 수학 지식이 담겨 있습니다. 예를 들어 리만 제타 함수에는 수백 가지의 알려진 항등식과 다른 함수를 이용한 표현이 있습니다. 짝수인 정수 값에 대해서는 π와 베르누이 수로 표현되는 간단한 닫힌 형식이 있습니다.
Mathematica는 이러한 항등식을 알고 있으므로 Zeta 함수를 이 축약된 형식으로 자동 변환합니다. 짝수가 아닌 값에 대해서는 (일반적으로) 간단한 닫힌 형식이 없지만, N 함수를 사용하면 원하는 자릿수만큼 계산할 수 있는 급수 근사가 있습니다.
In[49]:= Zeta[2]
Out[49]= Times[Rational[1, 6], Power[Pi, 2]]
In[50]:= Zeta[3]
Out[50]= Zeta[3]
In[51]:= N[Zeta[3], 30]
Out[51]= 1.20205690315959428539973816151
미적분
유명한 XKCD 만화는 어떤 미적분 문제들이 지닌 비대칭성을 보여 줍니다. 이러한 재작성 시스템 안에서 미분과 적분에 대한 단순화를 인코딩하려고 하면 이 만화가 그대로 재현됩니다.
실제로 미분은 앞에서 설명한 기법을 사용하면 거의 자명하게 인코딩할 수 있습니다. 미분 연산자의 선형성, 곱의 법칙, 거듭제곱 법칙, 상수 법칙은 규칙 네 줄로 작성할 수 있습니다. 표준 라이브러리에는 이러한 정의가 더 많이 들어 있지만, 대체로 이 정도로 간결합니다.
{
Diff[f_ g_, x_] -> f Diff[g, x] + g Diff[f, x],
Diff[f_ + g_, x_] -> Diff[f, x] + Diff[g, x],
Diff[Pow[x_,n_Integer], x_] -> n * Pow[x,n-1],
Diff[x_, x_] -> 1
Diff[n_?NumericQ, x_] -> 0
}
그러나 많은 컴퓨터 대수 시스템은 거의 마법 같은 방법으로 부정적분을 계산해 낼 수 있습니다. 예를 들면 다음과 같습니다.
In[52]:= Integrate[Log[1/x], x]
Out[52]= Plus[x, Times[x, Log[Power[x, -1]]]]
Mathematica의 기호 적분 능력은 마법처럼 보일 수 있지만, 실제로는 재작성 기계 장치에 변환 규칙 모음과 1930년대의 몇 가지 해석학적 성과를 결합한 대표적인 예일 뿐입니다. 어떤 적분은 패턴 매칭만으로 바로 계산할 수 있지만, Meijer G-함수 연구에는 여러 종류의 초월 함수를 적분 계산에 편리한 닫힌 형식으로 변환할 수 있게 해 주는 자명하지 않은 결과가 있습니다.
Meijer G-함수는 4개의 벡터 매개변수를 인덱스로 갖는 함수로, L이 에서 까지 이어지는 다음 복소 적분으로 표현됩니다.
이 함수는 잘 연구된 함수이며, 놀랍게도 아주 많은 종류의 특수 함수(삼각 함수, 베셀 함수, 초기하 함수 등)를 G-함수로 표현할 수 있습니다. 따라서 이러한 함수들이 복잡하게 중첩된 식도 G-함수 항을 다루는 일로 단순화할 수 있습니다. 이렇게 축약된 식에 적분 정리를 적용하면 하나 이상의 다른 G-함수 항이 나옵니다. 그런 다음 그 결과를 다시 특수 함수로 전개하면 적분 결과를 얻을 수 있습니다. 이 방법이 모든 경우에 통하는 것은 아니지만, 실제로는 매우 유용할 만큼 충분히 많은 경우에 통합니다.
매우 일반적인 부정적분 정리 중 하나는 피적분 함수를 G-함수 인덱스의 순열로 다시 표현합니다. 좌변에는 적분식이 있고 우변에는 계산된 적분이 있으며, 둘 다 G-함수로 표현됩니다.
적분표 한 권 분량이 항 재작성 로직 몇 줄로 된 G-함수의 간단한 곱셈 및 변환 규칙 집합으로 축약될 수 있습니다.
Mathematica 적분 엔진의 핵심(Core)에는 이 접근법을 활용한 변환과 함께 상당히 잘 작동하는 다양한 휴리스틱이 자리하고 있습니다. 예를 들어 MeijerGReduce 함수를 사용하면 여러 부류의 특수 함수를 그에 대응하는 G-함수로 변환할 수 있으며, 그런 다음 FullSimplify와 기타 항등식을 사용해 이러한 식을 더 간단하게 줄일 수 있습니다.
In[53]:= MeijerGReduce[Sqrt[x] Sqrt[1+x],x]
이 모든 기능이 한데 모여, 대부분의 주류 언어의 의미론과는 크게 다른 방식으로 추상적인 식을 다루는 데 특화된 프로그래밍 환경이 만들어집니다.
이 시스템으로 임의의 로직을 프로그래밍할 수 있는 것은 사실이지만, 제자리 참조와 가변 자료 구조를 다루는 명령형 로직을 코드로 작성하려고 하면 다소 번거로워질 수 있습니다. 그럼에도 이 시스템은 과학 계산 분야에서 매우 강력한 도메인 도구입니다. 언어에서 제공하는 기술 분야 관련 함수의 수는 수십 년에 걸쳐 꼼꼼하게 쌓아 온 전문가들의 도메인 지식을 보여 줍니다.
많은 대학이 이 소프트웨어의 사이트 라이선스를 보유하고 있으므로, 독특한 평가 모델과 의미론을 가진 프로그래밍 언어에 관심이 있다면 이 시스템에 담긴 아이디어를 직접 다뤄 볼 만합니다.