범용 의미 그래프
프로그래밍 언어의 구문적 다양성을 초월하여 프로그램의 순수한 의미를 포착하는 언어 무관한 그래프 표현
운용: 리나 코드 플랫폼 적용 • no‑overlay 게이팅(내부) • 문서는 텍스트 기반 구성
형식적 정의
수학적으로 엄밀하게 정의된 USG의 구조와 구성 요소
그래프 구조
USG는 5-튜플로 정의되는 방향 그래프입니다. 각 구성 요소는 프로그램의 핵심 의미 구조를 표현합니다.
G = (N, E_c, E_d, η, ι)
노드 집합 N
대표 원자 모티프의 유한 집합(버전드 카탈로그, 고정 목록 아님)
제어 흐름 E_c
프로그램 실행 순서를 나타내는 방향 간선
데이터 의존성 E_d
값의 정의와 사용 관계를 나타내는 간선
타입 함수 η
각 노드를 의미론적 원자 타입으로 매핑
의미론적 원자
대표 원자 모티프(버전드)로 기본 계산 단위를 표현
주요 원자 카테고리
- 제어 흐름: 순차, 조건, 루프, 호출
- 데이터 조작: 바인딩, 할당, 접근, 리터럴
- 연산: 산술, 논리, 비교, 타입
- 구조: 모듈, 함수, 클래스, 인터페이스
TOPAZ
1// 의미론적 원자 정의 예시
2enum 의미론적원자 {
3 // 제어 흐름
4 순차[노드배열],
5 조건(조건노드, 참노드, 거짓노드?),
6 반복(조건노드, 본문노드),
7 호출(함수노드, 인자배열),
8
9 // 데이터 조작
10 바인딩(식별자, 값노드),
11 할당(대상노드, 값노드),
12 접근(식별자),
13 리터럴(값),
14
15 // 연산
16 이항연산(연산타입, 왼쪽노드, 오른쪽노드),
17 단항연산(연산타입, 피연산자노드),
18
19 // ... 대표 원자 모티프(발췌)
20}
21
22// 사용 예시
23let 노드 = 의미론적원자.조건(
24 조건 = 비교노드,
25 참가지 = 실행노드1,
26 거짓가지 = 실행노드2
27)그래프 특성
USG가 갖는 수학적 특성과 의미론적 보장
완전성
대표 원자군으로 광범위한 패턴을 포착하도록 설계(형식적 완비성 주장 아님)
정규성
동일 의미의 프로그램에 대해 정규화 일관성을 지향(경계 사례 제외)
최소성
불필요한 중복을 제거하여 프로그램의 본질적 의미만을 포함
타입 안전성
타입 힌트/주석의 보존과 활용을 지향(구체 제약 비공개)
효과 라벨 격자
예시 관계: pure ⊑ read ⊑ write ⊑ io ⊑ global (관계만 공개)
생성 과정
소스 코드로부터 USG를 생성하는 체계적인 변환 과정
변환 단계
- 1단계: 언어별 구문 분석 및 AST 생성
- 2단계: 의미론적 분석 및 타입 추론
- 3단계: 의미론적 원자로 변환
- 4단계: 제어/데이터 흐름 그래프 구성
TOPAZ
1// USG 생성 과정 예시
2function USG생성(소스코드: string, 언어: 언어타입) -> Result<USG, Error> {
3 // 1. 언어별 파싱
4 let ast = 언어별파싱(소스코드, 언어)?
5
6 // 2. 의미론적 분석
7 let 의미정보 = 의미분석(ast)?
8
9 // 3. 원자 변환
10 let 원자들 = 원자로변환(의미정보)?
11
12 // 4. 그래프 구성
13 let 제어흐름 = 제어흐름구축(원자들)
14 let 데이터흐름 = 데이터흐름구축(원자들)
15
16 Ok(USG.새로운(원자들, 제어흐름, 데이터흐름))
17}
18
19// 호출 예시
20let 소스 = """
21function 팩토리얼(n: int) -> int {
22 match n {
23 case 0 | 1 => 1
24 case _ => n * 팩토리얼(n - 1)
25 }
26}
27"""
28
29let usg = USG생성(소스, 언어타입.토파즈)?
30출력("USG 노드 수: {usg.노드수()}")활용 분야
USG의 언어 무관한 특성을 활용한 다양한 응용 영역
언어 간 변환
USG를 중간 표현으로 사용하여 프로그래밍 언어 간 정확한 의미 보존 변환
코드 분석
언어에 무관한 정적 분석, 최적화, 버그 탐지 도구 개발
프로그램 검증
형식적 검증 및 정확성 증명을 위한 수학적 기반 제공