보존 정리
개요
보존 정리(Preservation Theorem), 또는 형식 보존(type preservation), 때때로 진전과 보존(Progress and Preservation)의 일부로 언급되는 개념은 프로그래밍 언어의 형식 시스템(타입 시스템)에서 매우 중요한 성질 중 하나입니다. 이 정리는 "형식이 지정된 프로그램이 한 단계 계산(evaluation)을 거쳐도 여전히 동일한 형식 체계 내에 머문다"는 내용을 담고 있습니다. 즉, 타입이 붙은 프로그램이 실행되면서 타입이 깨지지 않는다는 것을 보장합니다.
보존 정리는 프로그래밍 언어의 신뢰성, 안정성, 그리고 오류 방지 능력을 수학적으로 검증하는 데 핵심적인 역할을 하며, 형식적 의미론 및 프로그래밍 언어 설계 분야에서 널리 연구됩니다.
형식 시스템과 보존 정리의 역할
형식 시스템은 프로그램의 각 구성 요소(변수, 식, 명령문 등)에 형식(type)을 부여하고, 프로그램이 실행되는 동안 형식 규칙을 위반하지 않도록 제약을 두는 체계입니다. 보존 정리는 이 체계가 실제로 안정적인지를 보여주는 정리입니다.
핵심 개념
- 형식 체계(Typing System): 표현식에 형식을 부여하는 규칙 집합.
- 계산(Evaluation): 프로그램이 실행되면서 표현식이 줄어드는 과정 (예:
(3 + 5) → 8).
- 형식 유도(Type Derivation): 주어진 표현식이 특정 형식을 가짐을 증명하는 추론 과정.
보존 정리는 다음과 같은 형태로 기술됩니다:
정리 (보존): 만약 표현식 ( e )가 형식 ( T )을 가지며(즉, ( \Gamma \vdash e : T )), 그리고 ( e )가 ( e' )로 한 단계 계산된다(즉, ( e \rightarrow e' )),
그렇다면 ( \Gamma \vdash e' : T )도 성립한다.
이 정리는 프로그램이 실행되면서도 원래의 형식 구조를 유지함을 의미합니다.
보존 정리의 수학적 기초
보존 정리는 일반적으로 형식 체계의 형식 유도 규칙과 계산 규칙(reduction rules)에 기반하여 귀납법(induction)을 사용해 증명됩니다.
예시: 간단한 산술 표현식의 보존 정리
다음과 같은 최소한의 언어를 생각해 봅시다:
- 형식:
Nat (자연수)
- 표현식: 숫자
n, 덧셈 e₁ + e₂
- 계산 규칙:
- ( n_1 + n_2 \rightarrow n ) (두 자연수의 덧셈 결과)
- ( e_1 + e_2 \rightarrow e_1' + e_2 ) (만약 ( e_1 \rightarrow e_1' ))
형식 유도 규칙:
- ( \vdash n : \text{Nat} )
- ( \vdash e_1 : \text{Nat}, \vdash e_2 : \text{Nat} \Rightarrow \vdash e_1 + e_2 : \text{Nat} )
이제 ( \vdash e : \text{Nat} )이고 ( e \rightarrow e' )이면 ( \vdash e' : \text{Nat} )임을 보여야 합니다.
귀납법을 사용하여 각 표현식 형태에 대해 증명할 수 있습니다.
예를 들어, ( e = 3 + 5 )는 ( \vdash 3 + 5 : \text{Nat} )이며, ( 3 + 5 \rightarrow 8 )이고 ( \vdash 8 : \text{Nat} )이므로 보존이 성립합니다.
보존 정리와 진전 정리의 관계
보존 정리는 보통 진전 정리(Progress Theorem)와 함께 언급됩니다. 두 정리는 프로그램이 런타임 오류(runtime error) 없이 안전하게 실행됨을 보장하는 핵심 성질입니다.
| 정리 |
내용 |
| 보존 정리 |
형식이 있는 표현식이 계산되어도 형식이 유지된다. |
| 진전 정리 |
형식이 있는 표현식은 계산을 멈추지 않거나, 멈춘 상태가 "값"(value)이다 (즉, 오류 상태가 아님). |
이 둘이 함께 성립하면, 형식이 올바른 프로그램은 런타임 타입 오류를 일으키지 않는다는 결론을 도출할 수 있습니다. 이를 형식 안전성(Type Safety)이라 부릅니다.
실용적 의미와 응용
보존 정리는 이론적인 관심을 넘어서 실제 프로그래밍 언어 설계에 중요한 영향을 미칩니다.
1. 컴파일러 신뢰성 강화
- 보존 정리가 성립하면, 컴파일러가 타입 체크를 통과한 코드를 안전하게 변환하거나 최적화할 수 있음.
- 예: Haskell, Rust, ML 계열 언어는 형식 안전성을 엄격히 보장.
2. 정형 검증 및 증명 기반 프로그래밍
- Coq, Agda, Idris 같은 증명 기반 언어는 보존 정리를 통해 프로그램의 정확성을 수학적으로 보장.
- 프로그램 자체가 수학적 증명이 되는 경우, 보존은 추론의 유효성을 유지하는 데 필수적.
3. 런타임 오류 예방
- 타입 오류로 인한 크래시(예:
null pointer, undefined method)를 컴파일 타임에 방지.
- 예: Rust는 소유권 시스템과 함께 보존 정리 수준의 안전성을 제공.
관련 개념
- 형식 안전성(Type Safety): 보존 + 진전 정리로 구성됨.
- 강한 정규화(Strong Normalization): 모든 계산이 유한한 단계 내에 종료됨을 보장.
- 형식 유추(Type Inference): 형식을 명시하지 않아도 시스템이 자동으로 유추.
물리학의 보존 법칙과의 개념적 유사성
보존 정리는 컴퓨터 과학의 영역이지만, 그 근본적인 철학은 물리학의 보존 법칙(Conservation Laws)과 매우 유사합니다. 물리학에서 에너지 보존 법칙이나 운동량 보존 법칙이 시스템의 상태가 변하더라도 특정 물리량이 일정하게 유지됨을 의미하듯, 보존 정리는 프로그램의 상태(표현식)가 계산을 통해 변하더라도 '타입'이라는 성질이 일정하게 유지됨을 의미합니다.
두 분야의 개념적 공통점은 다음과 같습니다.
| 비교 항목 |
물리학의 보존 법칙 (예: 에너지 보존) |
컴퓨터 과학의 보존 정리 (Type Preservation) |
| 대상 |
물리적 시스템 (Physical System) |
형식 시스템 (Formal System) |
| 변화 과정 |
시간 경과 및 상호작용 (Interaction) |
계산 및 리덕션 (Evaluation/Reduction) |
| 보존되는 값 |
에너지, 전하, 운동량 등 |
타입 (Type) |
| 핵심 원리 |
상태가 변해도 총량/성질은 불변함 |
표현식이 변해도 타입은 불변함 |
| 결과적 보장 |
물리적 모순(에너지 생성/소멸) 없음 |
런타임 타입 오류(Type Crash) 없음 |
불변량(Invariant)으로서의 타입
보존 정리에서 타입은 단순한 분류 체계를 넘어, 계산 과정 전체에서 유지되어야 하는 불변량(Invariant)으로 작용합니다. 불변량의 정의에 따르면, 불변량이란 시스템의 상태가 변경되어도 항상 참으로 유지되는 조건을 말합니다.
에너지 보존 법칙에서 '에너지'가 시스템의 불변량인 것처럼, 보존 정리는 "타입 $T$를 가진 표현식은 어떤 계산 단계를 거치더라도 여전히 타입 $T$를 가진다"는 불변성을 수학적으로 증명하는 것입니다. 이는 계산이라는 '에너지 변환 과정' 속에서도 프로그램의 정체성(타입)이 훼손되지 않음을 보장하며, 이를 통해 개발자는 실행 전 단계에서 프로그램의 안전성을 확신할 수 있습니다.
타입 보존의 구체적 예제
다음은 간단한 타입 시스템에서 보존 정리가 어떻게 작동하는지를 보여주는 예제 코드와 분석입니다.
예제: 함수 적용(Function Application)의 보존
함수 타입 $\text{Int} \to \text{Int}$를 가진 함수 $f$에 정수 $n$을 전달하는 상황을 가정합니다.
1. 초기 상태 (Initial State)
- 표현식 $e$: (lambda x: Int. x + 1) 5
- 타입 유도:
- (lambda x: Int. x + 1) $\vdash \text{Int} \to \text{Int}$
- 5 $\vdash \text{Int}$
- 따라서 $e \vdash \text{Int}$ (함수 적용 규칙에 의해 결과 타입은 $\text{Int}$)
2. 계산 단계 (Evaluation Step)
- $\beta$-리덕션 수행: (lambda x: Int. x + 1) 5 $\rightarrow$ 5 + 1
- 여기서 $e \rightarrow e'$ 가 성립하며, $e' = 5 + 1$ 입니다.
3. 보존 확인 (Preservation Check)
- 새로운 표현식 $e'$의 타입 유도:
- 5 $\vdash \text{Int}$
- 1 $\vdash \text{Int}$
- + 연산자는 $\text{Int} \times \text{Int} \to \text{Int}$ 이므로, 5 + 1 $\vdash \text{Int}$
- 결과: $e$의 타입($\text{Int}$)과 $e'$의 타입($\text{Int}$)이 동일하므로 보존 정리가 성립합니다.
만약 계산 결과 $e'$의 타입이 $\text{String}$으로 변하거나 타입을 정의할 수 없게 된다면, 해당 언어의 타입 시스템은 보존 정리를 만족하지 못하며 이는 잠재적인 런타임 오류의 원인이 됩니다.
참고 자료
- Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press.
→ 보존 정리와 진전 정리의 고전적인 설명 제공.
- Harper, Robert (2016). Practical Foundations for Programming Languages. Cambridge University Press.
- 연구 논문: "The Definition of Standard ML" (Milner et al.) – 산업용 언어에서 형식 안전성의 적용 사례.
결론
보존 정리는 프로그래밍 언어의 타입 시스템이 실행 시간 중에도 형식의 일관성을 유지함을 보장하는 핵심 원리입니다. 이는 프로그램의 신뢰성과 안정성을 수학적으로 뒷받침하며, 현대의 안전한 프로그래밍 언어 설계에 없어서는 안 될 기초 이론입니다. 형식 언어 이론을 공부하거나 언어 설계에 관심이 있다면, 보존 정리의 이해는 필수적입니다.
# 보존 정리
## 개요
**보존 정리**(Preservation Theorem), 또는 **형식 보존**(type preservation), 때때로 **진전과 보존**(Progress and Preservation)의 일부로 언급되는 개념은 프로그래밍 언어의 **형식 시스템**(타입 시스템)에서 매우 중요한 성질 중 하나입니다. 이 정리는 "형식이 지정된 프로그램이 한 단계 계산(evaluation)을 거쳐도 여전히 동일한 형식 체계 내에 머문다"는 내용을 담고 있습니다. 즉, 타입이 붙은 프로그램이 실행되면서 타입이 깨지지 않는다는 것을 보장합니다.
보존 정리는 프로그래밍 언어의 **신뢰성**, **안정성**, 그리고 **오류 방지 능력**을 수학적으로 검증하는 데 핵심적인 역할을 하며, 형식적 의미론 및 프로그래밍 언어 설계 분야에서 널리 연구됩니다.
---
## 형식 시스템과 보존 정리의 역할
형식 시스템은 프로그램의 각 구성 요소(변수, 식, 명령문 등)에 **형식**(type)을 부여하고, 프로그램이 실행되는 동안 형식 규칙을 위반하지 않도록 제약을 두는 체계입니다. 보존 정리는 이 체계가 실제로 안정적인지를 보여주는 정리입니다.
### 핵심 개념
- **형식 체계**(Typing System): 표현식에 형식을 부여하는 규칙 집합.
- **계산**(Evaluation): 프로그램이 실행되면서 표현식이 줄어드는 과정 (예: `(3 + 5) → 8`).
- **형식 유도**(Type Derivation): 주어진 표현식이 특정 형식을 가짐을 증명하는 추론 과정.
보존 정리는 다음과 같은 형태로 기술됩니다:
> **정리 (보존)**: 만약 표현식 \( e \)가 형식 \( T \)을 가지며(즉, \( \Gamma \vdash e : T \)), 그리고 \( e \)가 \( e' \)로 한 단계 계산된다(즉, \( e \rightarrow e' \)),
> 그렇다면 \( \Gamma \vdash e' : T \)도 성립한다.
이 정리는 프로그램이 실행되면서도 원래의 형식 구조를 유지함을 의미합니다.
---
## 보존 정리의 수학적 기초
보존 정리는 일반적으로 **형식 체계의 형식 유도 규칙**과 **계산 규칙**(reduction rules)에 기반하여 귀납법(induction)을 사용해 증명됩니다.
### 예시: 간단한 산술 표현식의 보존 정리
다음과 같은 최소한의 언어를 생각해 봅시다:
- 형식: `Nat` (자연수)
- 표현식: 숫자 `n`, 덧셈 `e₁ + e₂`
- 계산 규칙:
- \( n_1 + n_2 \rightarrow n \) (두 자연수의 덧셈 결과)
- \( e_1 + e_2 \rightarrow e_1' + e_2 \) (만약 \( e_1 \rightarrow e_1' \))
형식 유도 규칙:
- \( \vdash n : \text{Nat} \)
- \( \vdash e_1 : \text{Nat}, \vdash e_2 : \text{Nat} \Rightarrow \vdash e_1 + e_2 : \text{Nat} \)
이제 \( \vdash e : \text{Nat} \)이고 \( e \rightarrow e' \)이면 \( \vdash e' : \text{Nat} \)임을 보여야 합니다.
귀납법을 사용하여 각 표현식 형태에 대해 증명할 수 있습니다.
예를 들어, \( e = 3 + 5 \)는 \( \vdash 3 + 5 : \text{Nat} \)이며, \( 3 + 5 \rightarrow 8 \)이고 \( \vdash 8 : \text{Nat} \)이므로 보존이 성립합니다.
---
## 보존 정리와 진전 정리의 관계
보존 정리는 보통 **진전 정리**(Progress Theorem)와 함께 언급됩니다. 두 정리는 프로그램이 **런타임 오류**(runtime error) 없이 안전하게 실행됨을 보장하는 핵심 성질입니다.
| 정리 | 내용 |
|------|------|
| **보존 정리** | 형식이 있는 표현식이 계산되어도 형식이 유지된다. |
| **진전 정리** | 형식이 있는 표현식은 계산을 멈추지 않거나, 멈춘 상태가 "값"(value)이다 (즉, 오류 상태가 아님). |
이 둘이 함께 성립하면, **형식이 올바른 프로그램은 런타임 타입 오류를 일으키지 않는다**는 결론을 도출할 수 있습니다. 이를 **형식 안전성**(Type Safety)이라 부릅니다.
---
## 실용적 의미와 응용
보존 정리는 이론적인 관심을 넘어서 실제 프로그래밍 언어 설계에 중요한 영향을 미칩니다.
### 1. **컴파일러 신뢰성 강화**
- 보존 정리가 성립하면, 컴파일러가 타입 체크를 통과한 코드를 안전하게 변환하거나 최적화할 수 있음.
- 예: Haskell, Rust, ML 계열 언어는 형식 안전성을 엄격히 보장.
### 2. **정형 검증 및 증명 기반 프로그래밍**
- Coq, Agda, Idris 같은 증명 기반 언어는 보존 정리를 통해 프로그램의 정확성을 수학적으로 보장.
- 프로그램 자체가 수학적 증명이 되는 경우, 보존은 추론의 유효성을 유지하는 데 필수적.
### 3. **런타임 오류 예방**
- 타입 오류로 인한 크래시(예: `null pointer`, `undefined method`)를 컴파일 타임에 방지.
- 예: Rust는 소유권 시스템과 함께 보존 정리 수준의 안전성을 제공.
---
## 관련 개념
- **형식 안전성**(Type Safety): 보존 + 진전 정리로 구성됨.
- **강한 정규화**(Strong Normalization): 모든 계산이 유한한 단계 내에 종료됨을 보장.
- **형식 유추**(Type Inference): 형식을 명시하지 않아도 시스템이 자동으로 유추.
---
## 물리학의 보존 법칙과의 개념적 유사성
보존 정리는 컴퓨터 과학의 영역이지만, 그 근본적인 철학은 물리학의 **보존 법칙(Conservation Laws)**과 매우 유사합니다. 물리학에서 에너지 보존 법칙이나 운동량 보존 법칙이 시스템의 상태가 변하더라도 특정 물리량이 일정하게 유지됨을 의미하듯, 보존 정리는 프로그램의 상태(표현식)가 계산을 통해 변하더라도 '타입'이라는 성질이 일정하게 유지됨을 의미합니다.
두 분야의 개념적 공통점은 다음과 같습니다.
| 비교 항목 | 물리학의 보존 법칙 (예: 에너지 보존) | 컴퓨터 과학의 보존 정리 (Type Preservation) |
| :--- | :--- | :--- |
| **대상** | 물리적 시스템 (Physical System) | 형식 시스템 (Formal System) |
| **변화 과정** | 시간 경과 및 상호작용 (Interaction) | 계산 및 리덕션 (Evaluation/Reduction) |
| **보존되는 값** | 에너지, 전하, 운동량 등 | 타입 (Type) |
| **핵심 원리** | 상태가 변해도 총량/성질은 불변함 | 표현식이 변해도 타입은 불변함 |
| **결과적 보장** | 물리적 모순(에너지 생성/소멸) 없음 | 런타임 타입 오류(Type Crash) 없음 |
## 불변량(Invariant)으로서의 타입
보존 정리에서 타입은 단순한 분류 체계를 넘어, 계산 과정 전체에서 유지되어야 하는 **불변량(Invariant)**으로 작용합니다. [불변량의 정의](https://ko.wikipedia.org/wiki/%EB%B6%88%EB%B3%80%EB%96%9C)에 따르면, 불변량이란 시스템의 상태가 변경되어도 항상 참으로 유지되는 조건을 말합니다.
에너지 보존 법칙에서 '에너지'가 시스템의 불변량인 것처럼, 보존 정리는 **"타입 $T$를 가진 표현식은 어떤 계산 단계를 거치더라도 여전히 타입 $T$를 가진다"**는 불변성을 수학적으로 증명하는 것입니다. 이는 계산이라는 '에너지 변환 과정' 속에서도 프로그램의 정체성(타입)이 훼손되지 않음을 보장하며, 이를 통해 개발자는 실행 전 단계에서 프로그램의 안전성을 확신할 수 있습니다.
## 타입 보존의 구체적 예제
다음은 간단한 타입 시스템에서 보존 정리가 어떻게 작동하는지를 보여주는 예제 코드와 분석입니다.
### 예제: 함수 적용(Function Application)의 보존
함수 타입 $\text{Int} \to \text{Int}$를 가진 함수 $f$에 정수 $n$을 전달하는 상황을 가정합니다.
**1. 초기 상태 (Initial State)**
- 표현식 $e$: `(lambda x: Int. x + 1) 5`
- 타입 유도:
- `(lambda x: Int. x + 1)` $\vdash \text{Int} \to \text{Int}$
- `5` $\vdash \text{Int}$
- 따라서 $e \vdash \text{Int}$ (함수 적용 규칙에 의해 결과 타입은 $\text{Int}$)
**2. 계산 단계 (Evaluation Step)**
- $\beta$-리덕션 수행: `(lambda x: Int. x + 1) 5` $\rightarrow$ `5 + 1`
- 여기서 $e \rightarrow e'$ 가 성립하며, $e' = 5 + 1$ 입니다.
**3. 보존 확인 (Preservation Check)**
- 새로운 표현식 $e'$의 타입 유도:
- `5` $\vdash \text{Int}$
- `1` $\vdash \text{Int}$
- `+` 연산자는 $\text{Int} \times \text{Int} \to \text{Int}$ 이므로, `5 + 1` $\vdash \text{Int}$
- **결과**: $e$의 타입($\text{Int}$)과 $e'$의 타입($\text{Int}$)이 동일하므로 **보존 정리가 성립**합니다.
만약 계산 결과 $e'$의 타입이 $\text{String}$으로 변하거나 타입을 정의할 수 없게 된다면, 해당 언어의 타입 시스템은 보존 정리를 만족하지 못하며 이는 잠재적인 런타임 오류의 원인이 됩니다.
## 참고 자료
- Pierce, Benjamin C. (2002). *Types and Programming Languages*. MIT Press.
→ 보존 정리와 진전 정리의 고전적인 설명 제공.
- Harper, Robert (2016). *Practical Foundations for Programming Languages*. Cambridge University Press.
- 연구 논문: "The Definition of Standard ML" (Milner et al.) – 산업용 언어에서 형식 안전성의 적용 사례.
---
## 결론
보존 정리는 프로그래밍 언어의 타입 시스템이 실행 시간 중에도 형식의 일관성을 유지함을 보장하는 핵심 원리입니다. 이는 프로그램의 신뢰성과 안정성을 수학적으로 뒷받침하며, 현대의 안전한 프로그래밍 언어 설계에 없어서는 안 될 기초 이론입니다. 형식 언어 이론을 공부하거나 언어 설계에 관심이 있다면, 보존 정리의 이해는 필수적입니다.