[프언] #18. Algebraic Data Type

지금까지 저희는 Type을 약식으로 정의해 왔었는데요, 지금부터는 Type을 변수들과 Expression의 계산값이 들어가 있는 집합의 이름으로서 다루겠습니다. 

List를 정의할 때, 보통 빈 리스트와 원소가 하나인 리스트, 그리고 이것들의 합. 이렇게 정의하는게 일반적입니다. 비슷하게 이진트리를 정의할 때도 빈 트리와 Root, 2개의 Child로 구성된 단순한 트리, 그리고 이것들의 합. 이렇게 정의합니다. 이런 식으로 정의되는 Type, 혹은 Set을 Sum Type이라고 합니다.

반면, 프로시져를 정의할 때 저희는 변수 x, expression b, environment e에 대해 (x, b, e)와 같은 식으로 정의를 합니다. 이렇게 정의되는 Type 혹은 Set을 Product Type이라고 합니다.

많은 Type들은 보통 Product Type의 Sum Type으로 구성되어 있습니다. 이렇게 구성된 Type을 Algebraic Data Type, 줄여서 ADT라고 부릅니다.

 

ADT in Scala

스칼라에서는 trait와 class를 통해서 ADT를 만들 수 있습니다.

sealed trait AE
case class Num(n: Int) extends AE
case class Add(a: Int, b: Int) extends AE
case class Sub(a: Int, b: Int) extends AE

여기서 Num은 정수를 나타내는 ADT이며, 비슷하게 Add와 Sub은 덧셈과 뺄셈을 나타냅니다. 예를 들어, Num(5)는 정수 5를 나타내고, Add(1, 4)는 1+4를 나타내는 것이겠죠.

어떤 Expression을 계산하는 함수를 만들 수도 있습니다.

def eval(x: AE): Int = x match {
	Num(n) => n
	Add(a, b) => a + b
}

 

Extending the Language with ADT

이제 이와 비슷한 기능을 저희 언어에 추가해보겠습니다.

아래는 이를 활용한 예시입니다.

type AE = Num @ {n: Int} + Add @ {a: Int, b: Int} in
let eval = proc x: AE (x match Num(n) => n.n, Add(a) => a.a + a.b) in ...

첫 번째 줄은 n이라는 정수를 필드로 가지는 타입인 Num과 a, b라는 두 정수를 필드로 가지는 타입인 Add를 만들고, 이 둘을 묶어서 AE라는 타입을 정의합니다. 두 번째 줄은 AE 타입을 받아 패턴 매칭을 사용해 그 값을 계산하는 프로시져인 eval을 정의하고 있습니다. 위와 같은 코드 내부에서 아래와 같이 새로운 변수들을 정의할 수 있습니다.

(Num, 1)
(Add, {1, 2})
<Add>
<Num>

<와 >로 묶인 것들은 아무것도 없는 변수를 만들었다는 의미로, Constructor라고 불립니다. 이에 대한 Inference Rule들은 아래와 같습니다.

 

 

Type System

Type Environment는 이제 사용자가 정의한 Type에 대해서도 처리할 수 있어야 합니다. 따라서, 아래와 같은 형태가 됩니다.

만약 어떤 Type이 Free Type 없이 정의되었다면 그 Type을 Well-Formed 되었다고 합니다. 다르게 말하면, 이미 Type Environment에 존재하는 Well-Formed Type만으로 정의된 Type이 있다면, 그 Type 역시 Well-Formed입니다.

($\Gamma \vdash t$는 $t$가 $\Gamma$에서 Well-Formed라는 의미입니다.)

 

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.