5. 간단한 언어 만들어보기 - 1

Syntax & Semantics

프로그래밍 언어를 설계할 때 가장 중요한 두 가지 요소는 문법(Syntax)과 의미(Semantics)이다.

 

Syntax는 프로그램을 어떻게 작성해야 하는지에 대한 규칙을 정의한다. 프로그램의 구조를 결정하고, 변수, 키워드, 연산자, 구문 등 언어의 요소들이 어떻게 조합되어야 하는지를 명시한다.

 

Semantics는 프로그램이 실제로 어떤 동작을 수행하는지에ㅍ 대한 정의이다.

 

Syntax와 Semantics는 귀납적 정의(Inductive Definitions)로 명시될 수 있다.

 

 

첫 번째 언어 구축

먼저, Let이라는 이름의 간단한 언어를 만들어보자.

Syntax

P → E // 프로그램은 표현식으로 구성된다.

E → n // 표현식은 다음 중 하나일 수 있다.

    | x // 변수 생성 가능

    | E + E // 덧셈 가능

    | E - E // 뺄셈 가능

    | (E) // 괄호 가능

    | iszero E // 간단한 함수 (0인지 확인)

    | if E then E else E // 조건문 가능

    | let x = E in E // 지역 변수에 표현식 할당

    | read // 입력

 

위 문법을 사용하여 다양한 표현식을 작성할 수 있다.

 

Symantics

프로그래밍 언어의 Semantics를 정의하기 위해선 values와 environments가 필요하다.

Values는 프로그래밍 언어에서 데이터의 기본 단위이다. 예를 들어, 1+(2+3)은 6으로 평가되고 iszero 1은 표현식 1이 0인지 검사하고 false로 평가한다.

Environments는 변수와 그에 해당하는 값의 매핑을 나타낸다. 표현식에서 변수를 평가할 때 해당 변수가 가리키는 값을 찾기 위해 환경을 참조한다.

 

values 집합은 정수와 불리언을 포함한다.

v ∈ Val = Z + Bool

 

enviroments는 변수에서 values로의 함수이다.

p ∈ Env = Var → Val

 

[] : 빈 enviroment

[x  v]p : x가 v에 바인딩된 p의 확장

([x ↦ v]p)(y) = if x=y then v else p(y) : y가 x와 같다면 v를 반환하고, 아니라면 p(y)를 반환

[x1 ↦ v1, x2 ↦ v2]p = [x1 ↦ v1]([x2 ↦ v2]p) : 환경 p의 확장 

 

p ⊢ e ⇒ v

환경 p가 주어졌을 때, 표현식 e는 값 v로 평가된다.

 

[] ⊢ 1 ⇒ 1 // 빈 환경 []에서 숫자 1은 그 자체로 1로 평가된다.

[x ↦ 1] ⊢ x+1 ⇒ 2 // 환경에서 x가 1로 매핑될 때, x+1은 2로 평가된다.

[] ⊢ read ⇒ 3 // 입력이 3이라면 read는 3으로 평가된다.  

[x ↦ 1] ⊢ read ⇒ 5 // 환경에서 x=1이더라도, 입력이 5라면 read는 5로 평가된다.

[x ↦ 0] ⊢ let y = 2 in if iszero x then y else x ⇒ 2

// 환경에서 x가 0으로 매핑될 때, let 표현식을 사용해 y를 2로 정의하고,  iszero x는 true로 평가되므로 y의 값은 2로 평가된다.

 

 

Evaluation Rules

이에 대한 평가 규칙(Evaluation Rules)은 다음과 같이 나타난다.

 

추론 규칙(inference rules)은 환경 p, 표현식 e, 값 v의 삼중항 집합 S를 정의한다.

표현식 e가 환경 p에 대해 semantics를 가진다는 것은 값 v에 대해 삼중한 (p, e, v)가 집합 S에 속함을 의미한다.

즉, 표현식 e가 환경 p에 대해 의미를 가지려면, 추론 규칙을 적용하여 p ⊢ e ⇒ v를 어떤 값 v에 대해 도출할 수 있어야 한다.

 

여기서 프로그램 e가 의미를 가진다라고 말하는 경우, 그것은 초기 환경인 []에서 표현식 e를 평가했을 때 어떤 값 v로 평가될 수 있음을 의미한다. 이것은 프로그램이 실행될 때 그 결과가 결정될 수 있다는 것을 뜻한다.

 

 

사칙연산 평가

p = [i ↦ 1, v ↦ 5, x ↦ 10]일 때, p ⊢ (x - 3) - (v - i) ⇒ 3이 평가되는 과정을 알아보자.

p ⊢ x ⇒ 10,  p ⊢ 3 ⇒ 3, p ⊢ v ⇒ 5, p ⊢ i ⇒ 1이므로, x와 3과 v와 i는 각각 10, 3, 5, 1으로 평가된다.

따라서 p ⊢x - 3 ⇒ 7, p ⊢ v - i ⇒ 4 로 평가되고,

이어서 p ⊢ (x - 3) - (v - i) ⇒ 3 으로 평가된다.

 

이를 derivation tree로 나타내면 위와 같다.

 

 

조건문 평가

다음은 p = [ x ↦ 33, y ↦ 22 ]일 때, p ⊢ if iszero (x - 11) then y - 2 else y - 4 ⇒ 18 이 평가되는 과정을 알아보자.

p ⊢ x ⇒ 33, p ⊢ 11 ⇒ 11, p ⊢ x - 11 ⇒ 22, p ⊢ iszero(x - 11) ⇒ false로 평가되어 else문으로 넘어간다.

p ⊢ y ⇒ 22, p ⊢ 4 ⇒ 4, p ⊢ y - 4 ⇒ 18이므로, 18로 평가된다.

 

 

이를 derivation tree로 나타내면 위와 같다.

 

 

Let 표현식 평가

[] ⊢ let x = 5 in x - 3 ⇒ 2 가 평가되는 과정을 알아보자.

먼저, [] ⊢ 5 ⇒ 5 이고, 환경은 [x ↦ 5] 가 된다.

[x ↦ 5] ⊢ x ⇒ 5 이고, [x ↦ 5] ⊢ 3 ⇒ 3 이므로, [x ↦ 5] ⊢ x - 3 ⇒ 2 로 평가된다.

이를 derivation tree로 나타내면 위와 같다.

 

 

OCaml에서 구현?

Syntax

type program = exp
and exp =
       | CONST of int
       | VAR of var
       | ADD of exp * exp
       | SUB of exp * exp
       | READ
       | ISZERO of exp
       | IF of exp * exp * exp
       | LET of var * exp * exp
and var = string

신텍스는 위와 같이 나타낼 수 있다. 

let x = 7
  in let y = 2
    in let y = let x = x - 1
      in x - y
    in (x-8)-y

예를 들어, OCaml의 이런 코드가 있다고 하자.

 

LET ("x", CONST 7,
  LET ("y", CONST 2,
    LET ("y", LET ("x", SUB(VAR "x", CONST 1),
      SUB(VAR "x", VAR "y")),
    SUB (SUB (VAR "x", CONST 8), VAR "y"))))

우리 언어의 신텍스로는 위와 같이 표현된다.

 

 

Symantics

(* Values *)
type value = Int of int | Bool of bool

(* Environments *)
type env = (var * value) list
let empty_env = []
let extend_env (x,v) e = (x,v)::e
let rec apply_env x e =
  match e with
  | [] -> raise (Failure ("variable " ^ x ^ " not found"))
  | (y,v)::tl -> if x = y then v else apply_env x tl

values와 environments를 OCaml 코드로 구현한 것이다.

values에는 int와 bool이 있으므로 둘을 추가해준다.

환경은 (변수이름, 값) 꼴의 튜플 리스트이다.

extend_env는 (x,v)를 e에 추가한다.

apply_env는 e에서 x를 찾아 반환한다. 없으면 에러를 낸다.

 

 

Evaluation Rules

let rec eval : exp -> env -> value = fun exp env ->
  match exp with
  | CONST n -> Int n 
  | VAR x -> apply_env x env
  | ADD (e1, e2) ->
    let v1 = eval e1 env in
    let v2 = eval e2 env in
      (match v1, v2 with
      | Int n1, Int n2 -> Int (n1 + n2)
      | _ -> raise (Failure "Type Error: non-numeric values")
      )
  | SUB (e1, e2) ->
    let v1 = eval e1 env in
    let v2 = eval e2 env in
      (match v1, v2 with
      | Int n1, Int n2 -> Int (n1 - n2)
      | _ -> raise (Failure "Type Error: non-numeric values")
      )
  | READ -> Int (read_int())
  | ISZERO e ->
    (match eval e env with
    | Int n when n = 0 -> Bool true
    | _ -> Bool false
    )
  | IF (e1, e2, e3) ->
    (match eval e1 env with
    | Bool true -> eval e2 env
    | Bool false -> eval e3 env
    | _ -> raise (Failure "Type Error: condition must be Bool type")
    )
  | LET (x, e1, e2) ->
    let v1 = eval e1 env in
      eval e2 (extend_env (x, v1) env)

평가 규칙에서는 각 표현식을 평가한다. 각 분기에 따라 적절한 평가를 수행한다.

 

 

Interpreter

let run : program -> value
  = fun pgm -> eval pgm empty_env

let e1 = LET ("x", CONST 1, ADD (VAR "x", CONST 2));;
let res = (run e1);;

run 함수는 program을 받아 value를 반환한다.

아래 두 줄은 호출 예시이다. res는 Int 3이 된다.