[프로그래밍 언어론] 의미론(sementics) - 수식의 의미
의미론
언어 S에서 수식의 의미를 알아보기 전, 의미론(sementics)에 대해 알아보자. 의미론이란 예전 포스팅에서 언급한 프로그래밍 언어를 설계할 때 필수적으로 있어야 하는 요소이다. 의미론 / 시멘틱스(sementics)는 작성된 수식, 문장, 혹은 프로그램의 의미를 정하는 것을 말한다. 의미론의 용도는 다음과 같다.
1. 프로그램 의미를 정확히 정의하고 이해하기 위함.
2. 소프트웨어가 하는 일을 정확히 명세.
3. 소프트웨어에 대한 검증 혹은 추론의 기초.
4. 컴파일러 / 해석기 작성의 기초.
프로그램의 의미는 자연어를 이용해 기술하거나 수학적으로 기술 가능하다. 의미의 수학적 기술 방법에는 다음 세 가지가 있다.
1. 작동 의미론: 실행 과정을 기술해 정의하는 정형화된 방법
2. 표시 의미론: 수식, 문장의 의미를 표시(denotation)라 부르는 수학적 함수 형태로 정의
3. 공리 의미론: 시작과 끝 상태를 논리적 선언으로 정의
수식의 의미
어떤 상태에서 수식 E의 의미는 무엇일까? 수식 E의 의미는 바로 수식 E가 나타내는 값에 해당한다. 어떤 상태에서 수식의 의미(값)를 각 수식에 대해 다음과 같은 함수 V 형태로 정의 가능하다. Expr는 모든 가능한 수식의 집합, State는 모든 가능한 상태의 집합, Value는 모든 가능한 값들의 집합이다.
V: (State, Expr) -> Value
이제 여러 수식의 의미, 값에 대해 알아보자.
간단한 수식
E -> true | false | n | str | id
상태 s에서 true의 값은 항상 T, false의 값은 항상 F이다. 추가로 상태 s에서 상수 n의 값은 상태에 관계없이 n이며 스트링 리터럴 str의 값 역시 상태에 관계없이 str이다. 상태 s에서 변수 id의 의미(값)는 상태 s에서 변수 id에 대응된 값이다. 이것을 다음과 같이 표현할 수 있다. V(s, id) = s(id)
산술 연산
E -> E + E | E - E | E * E | E / E
덧셈 연산을 예시로 살펴보자. 상태 s에서 E1 + E2의 값은 V(s, E1 + E2)로 표현하며 이것은 V(s, E1) + V(s, E2)와 같다. 다음의 짧은 예시를 살펴보자.
s = { x |-> 1, y |-> 2 }
V(s, x + y) = V(s, x) + V(s, y) = s(x) + s(y) = 1 + 2 = 3
비교 연산
E -> E > E | E < E | E == E | E != E
== 비교 연산을 예시로 살펴보자. 상태 s에서 E1 == E2의 의미(값)는 E1와 E2의 값이 같으면 T, 그렇지 않으면 F일 것이다. 다음 x와 y의 비교 연산 예시를 확인해보자.
s = { x |-> 1, y |-> 2 }
V(s, x == y) = V(s, x) == V(s, y) = s(x) == s(y) = 1 == 2 = F
연산자 우선순위
수식의 의미, 즉 수식의 값을 계산할 때 고려해야 할 점은 무엇일까? 우리가 사칙연산을 할 때에도 연산자의 우선순위에 맞게 계산을 하는게 당연하듯이 연산자의 우선순위를 고려해야 한다. *, /를 먼저 계산하고 +, -를 나중에 계산하도록 우선순위를 설정하려면 어떻게 해야 할까?
이러한 연산자 우선순위는 구문법으로 표현할 수 있다. 아래 문법을 이용해 a + b * c 수식을 유도해 보면, 곱셈을 포함한 항이 가장 먼저 계산되고 이후에 다른 항을 더하게 된다.
E -> E + T | T
T -> T * F | F
F -> n | id
연산자의 결합성
연산자의 우선순위 말고도 수식에서 고려해야 하는 것이 하나 더 있다. 수식을 계산할 때, 괄호의 범위에 따라 수식의 값이 바뀔 수 있다. 1 - 2 - 3을 (1 - 2) - 3, 1 - (2 - 3)의 두 방식대로 계산하면 값이 다른 것이 그 예시이다. 결합성은 다음 두 가지 규칙이 있다.
1. 좌결합: 왼쪽부터 우선 결합하는 규칙. 왼쪽 -> 오른쪽 방향으로 수행
2. 우결합: 오른쪽부터 우선 결합하는 규칙. 오른쪽의 연산자부터 먼저 수행.
역시 글만 보면 잘 이해가 되지 않으니 예시를 통해 빠르게 이해해보자. 대부분 이항 연산자들은 좌우선 결합 규칙을 가진다. 앞서 보았던 1 - 2 - 3을 우리는 왼쪽 -> 오른쪽 방향으로 계산한다. 대부분의 단항 연산자, 대입 연산자들은 우결합 규칙은 따른다. 해당 예시로 1) !!x, 2) x = y = z가 있다. 2)에서 대입 연산자 =의 계산 순서는 y에 z의 값을 먼저 대입하고, y의 값을 x에 대입하는 것이다. 이렇게 단항 / 대입 연산자는 오른쪽 연산자들을 먼저 계산한다.