[프언] #05. Expressions

이번 글에서는 이때까지 배웠던 지식을 바탕으로 프로그래밍 언어 하나를 설계해보도록 하겠습니다.

Values & Environment

Scala와 유사하게 프로그램을 Expression으로 정의할 것인데요. 편의를 위해 저희가 만드는 프로그래밍 언어에는 딱 2가지 Value, Integer와 Boolean만 존재한다고 생각합시다.

$$v\in \textbf{Val} = \mathbb{Z}+ \mathit{Bool}$$

이제 Value를 정의했으니 이에 대한 연산에 대해 한번 생각해보겠습니다. 예를 들어 x에 10을 더해 그 값을 y에 저장한다고 생각을 해 봅시다. 이 때, 계산한 값을 y에 저장하려면 y는 그 값이 바뀔 수 있는 Variable이여야 하며 이 Variable은 Pre-assigned, 이전에 정의되어 있어야 합니다.

이렇게 Value에 저장된 값을 Variable로 옮겨져있는 이 상황을 "Environment"라고 합니다.

$$\rho \in \textbf{Env}=\textbf{Var} \to \textbf{Val}$$

예를 들어, 아래와 같은 C++ 프로그램이 있다고 가정합시다.

int x = 10
// ...

이런 C++ 프로그램에서, 10이라는 값이 x에 할당되어 있습니다. 이걸 다르게 말하면 ...이라고 되어 있는 부분에 작성한 코드를 작성하게 되면, 이 코드는 x=10인 Environment 위에 놓여있는 것이고, 이 Envirionment 위에서 x를 호출했을 경우, 그 x는 10이라는 값을 가지는 것입니다.

저희는 Environment를 표현하기 위해 아래와 같은 표현을 사용할 겁니다.

• $[\; ]$ : 빈 Environment를 나타냅니다.
• $[ x\mapsto v ]\rho $ : $x$의 값이 $v$의 값에 의존함, 다른 말로 $v$의 값이 $x$에 할당되어 있음을 의미합니다. $\rho$는 이 Environment의 이름입니다.

 

Expression을 표현하기 위해서는 아래와 같은 표현을 사용합니다.

$$ \rho \vdash e\Rightarrow v$$

$\rho$는 주어진 Environment를, $e$는 Expression을, $v$는 Expression을 계산한 값을 의미합니다. 예를 들어, $ [] \vdash 1+1\Rightarrow 2$ 입니다. 위 식에서 $1+1$을 계산하기 위해 요구되는 Environment가 없기 때문에, $\rho$ 자리에 빈 Environment를 넣었고 Expression인 $1+1$을 계산하면 $2$가 됩니다.

그러면 $ [] \vdash x+1\Rightarrow ?$를 계산하면 어떻게 될까요? Expression $x+1$을 계산하기 위해서는 $x$의 값이 필요합니다. 따라서, 위에 주어진 조건만으로 화살표 오른쪽에 들어갈 값을 구할 수는 없습니다. $x$에 값을 할당해주는 Environment가 필요하죠. $ [x\mapsto 1]] \vdash x+1\Rightarrow 2$ 이렇게요.

 

Evaluation Rules

방금까지 Expression과 Environment를 기술하는 방법에 대해 알아보았습니다. 이제 위 방법들과 Inference Rule을 같이 이용하면, 저희가 사용할 언어의 Syntax에 대한 설명을 보다 쉽게 할 수 있습니다.

Evaluation Rule #1

위는 Axiom입니다. $n$이라는 Expression을 계산한 값은 항상 $n$임을 의미합니다. 이렇게 Inference Rule을 이용해 Syntax에 대해 기술한 것을 우리는 Evaluation Rule이라 부를 것입니다.

Evaluataion Rule #2, #3

위 두 Expression Rule은 더하기 기호와 빼기 기호가 어떻게 동작하는지를 나타냅니다. Evaluataion Rule #2는 Expression $E_1$을 계산한 값이 $n_1$이고, $E_2$를 계산한 값이 $n_2$라면 $E_1+E_2$를 계산하면 $n_1+n_2$가 됨을 의미합니다. Evaluation Rule #3은 뺄셈에 대해 같은 정의를 의미합니다.

Evaluation Rule #4, #5

위 두 Expression Rule은 $iszero$가 무엇을 의미하는지를 나타냅니다. $E$의 값이 0일 경우는 $true$가 되고, 0이 아닐 경우에는 $false$가 됩니다.

Evaluation Rule #6, #7

위 두 Expression Rule은 $if\ then\ else$가 어떻게 계산되는지를 나타냅니다. 자세한 설명은 생략하겠습니다.

Evaluation Rule #8

$let$ Expression에 대해서는 설명을 조금 더 하고 넘어가겠습니다. $let\ E_1 \ in \ E_2$는 새로운 변수 $x$를 만들고 그 값을Expression $E_1$로 지정해준다고 생각하시면 됩니다.

Evaluation Rule #9

위 Expression Rule은 괄호가 무엇을 의미하는지를 나타냅니다. 자세한 설명은 생략하겠습니다.

 

이러한 Expression Rule을 사용하면 아무리 복잡한 Expression들이라도 세부적이고 단순한 형태의 Expression으로 분리하여 그 값을 계산할 수 있습니다. 그 예시를 한번 보겠습니다.

Environment가 $[i\mapsto 1, v\mapsto 5, x\mapsto 10]$로 주어졌을 때, Expression $\left( x-3 \right) - \left( v-i \right)$를 계산하는 과정은 아래와 같이 작성할 수 있습니다.

Envirionment가 $[x\mapsto 33, y\mapsto 22]$로 주어졌을 때, Expression $if \ iszero \ \left( x-11\right)\ then \ y-2 \ else\ y-4$를 계산하는 과정은 아래와 같이 작성할 수 있습니다.

빈 Environment에서 Expression $let\ x=5\ in\ x-3$을 계산하는 과정은 아래와 같이 작성할 수 있습니다.

이렇게 $let$ Expression을 사용할 때마다 새로운 변수가 만들어지고, 이 변수의 값은 주어진 Environment에 의존한다고 생각하면 됩니다. 만약 여러개의 변수를 만들어야 할 상황이라면, $let$ Expression 안에 $let$ Expression을 넣어서 사용할 수 있습니다.

let z = 5
in let x = 3
	in let y = x - 1
		in let x = 4
			in x - (x - y)

이렇게요. 위를 계산한 값은 3입니다.

 

언어의 작성

이제 지금까지 저희가 설계했던 Language를 한번 Scala에서 구현해보도록 하겠습니다. 첫 단계는 글 제일 처음에 했던 것 처럼 Environment와 변수들을 정의하는 것입니다.

type Env = HashMap[Var, Val]

sealed trait Val
case class IntVal(n: Int) extends Val
case class BoolVal(b: Boolean) extends Val

그 다음으로는 Program 그 자체를 정의할 것입니다. Program은 여러 Expression의 모임이고, Program 그 자체도 Expression이라고 볼 수 있으므로, 아래와 같이 정의할 수 있습니다.

sealed trait Program
sealed trait Expr extends Program

이제 상수, 변수, 더하기, 빼기, $Iszero$, $If$, $Let$, 괄호 등 여러가지 Expression을 하나하나 추가해줍니다.

sealed trait Program
sealed trait Expr extends Program
case class Const(n: Int) extends Expr
case class Var(s: String) extends Expr
case class Add(l: Expr, r: Expr) extends Expr
case class Sub(l: Expr, r: Expr) extends Expr
case class Iszero(c: Expr) extends Expr
case class Ite(c: Expr, t: Expr, f Expr) extends Expr
case class Let(name: Var, value: Expr, body: Expr) extends Expr
case class Paren(expr: Expr) extends Expr

 

이제 이렇게 Expression과 Environment를 전부 정의했으므로, 텍스트를 받아서 위의 스칼라 코드가 알아들을 수 있는 표현으로 바꿔주는 프로그램이 필요합니다. 예컨데,

let x = 7
in let y = 2
	in x - 7

이런 텍스트를 받아서, 아래와 같은 스칼라 코드로 바꿔주는 프로그램이죠.

Let(Var(x), Const(7),
	Let(Var(y), Const(2), 
		Sub(Var(x), Var(y))))

이런 프로그램을 우리는 Parser라고 부릅니다. 하지만, 이 글에서 Parser에 대한 내용은 다루지 않고 누군가 이미 만들어둔 아주 멋진 Parser가 있다고 가정하고 설명을 계속해보도록 하겠습니다.

 

다음으로 작성해야 할 코드는 바로 Environment와 Expression을 입력받아 이 Expression을 계산하는 함수입니다.

def eval(env: Env, expr: Expr): Val = expr match {
	case Const(n) => IntVal(n)
	case Var(s) =>
		if (env.exists((a: Var, Val)) => a._1 == Var(s))
			env(Var(s))
		else throw new Exception("1")
	
	case Add(a, b) => (eval(env, a), eval(env, b)) match {
		case (x: IntVal, y: IntVal) => IntVal(x.n + y.n)
		case _ => throw new Exception("Type Error")
	}
	
	case Sub(a, b) => (eval(env, a), eval(env, b)) match {
		case (x: IntVal, y: IntVal) => IntVal(x.n = y.n)
		case _ => throw new Exception("Type Error")
	}

	case IsZero(c) => eval(env, c) match {
		case (x: Intval) => BoolVal(x.n == 0)
		case _ => BoolVal(false)
	}

	case Ite(c, t, f) => eval(env, c) match {
		case v: BoolVal => if (v.b) eval(env, t) else eval(env, f)
		case _ => throw new Excpetion("Type Error")
	}

	case Let(name, value, body) => {
		val new env = env + (name -> eval(env, value))
		eval(new_env, body)
	}

	case Paren(expr: Expr) => eval(env, Expr)
}

코드에 대한 자세한 설명은 생략하도록 하겠습니다.

감사합니다.

---

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