Language Theory & Type Systems

1. Overview

언어 설계 및 타입 시스템 기초(Language Design & Type Systems Foundations, LDT)는 컴퓨터가 인간의 추상적이고 모호한 사고를 일관된 규칙으로 해석할 수 있게 만드는 '언어(Language)의 구조와 안전망'을 다룹니다.

프로그래밍 언어는 단순한 문법 표기가 아니라, 연산을 모델링하는 패러다임(명령형, 함수형, 선언형)을 결정짓는 수학적 사고 프레임워크입니다. 학습자는 정규 문법(Regex)과 문맥 자유 문법(CFG)을 바탕으로 언어의 뼈대(Syntax)를 정의하고, 코드가 메모리 상에서 어떻게 실행될지를 규정하는 의미론(Semantics)을 이해합니다. 이어 개발자의 실수로 생길 수 있는 데이터 충돌(예: 정수에 문자열 덧셈)을 컴파일 단계에서 줄이는 강타입(Strong Typing) 기반 '타입 시스템(Type System)'의 논리적 엄밀함을 훈련하여, 언어라는 도구의 한계와 철학을 명확히 파악합니다.

2. Scope & Boundaries

In-Scope

• 문법 구조 (Syntax & Grammar): 어휘(Lexeme)와 토큰(Token), 구상 구문(Concrete Syntax), 추상 구문 트리(AST), BNF(Backus-Naur Form)를 이용한 문맥 자유 문법(CFG) 정의.
• 실행 의미와 바인딩 (Semantics & Binding): 연산 의미론(Operational Semantics), 정적/동적 바인딩의 시점 차이, 환경(Environment) 레코드와 상태(State), 정적 스코프(Lexical Scope)와 클로저(Closure)의 수명 연장 방식.
• 타입 논리망 (Type Theory & Safety): 타입 검사(Type Checking)와 타입 추론(Type Inference - Hindley-Milner 기반), 정적/동적 타이핑(Static vs Dynamic), 타입 안전성(Type Safety)의 증명.
• 다형성과 패러다임 (Polymorphism & Paradigms): 제네릭(Parametric Polymorphism), 서브타이핑(Subtyping), 객체지향의 상속(Inheritance), 함수형 언어의 일급 객체(First-class Citizen) 및 순수 함수(Pure Function) 원칙.

Out-of-Scope

• 컴파일러의 기계어 변환 로직 (Code Generation): 구문 트리를 파싱한 뒤 LLVM IR로 바꾸거나 레지스터를 할당하는 최적화 프로세스 → 05-02. Compiler Design 영역으로 위임.
• 특정 런타임 엔진의 구조 (GC, JIT): V8 엔진의 자바스크립트 가비지 컬렉터 동작 방식이나 JVM의 메모리 힙 구조 → 05-03. Runtime Systems 영역으로 위임.
• 특정 언어 라이브러리 사용법: Java의 Spring Framework나 Python의 Pandas API 활용법 등 → 각 도메인 영역(Web, Data)으로 위임.

Boundaries

• LDT vs. Data Structures (04): Data Structures(04)가 데이터를 메모리에 어떻게 배치하고 접근할지에 초점을 맞춘다면, LDT는 그 데이터를 어떤 이름으로 바인딩하고 어떤 타입(정수/문자)으로 다뤄야 연산 오류를 줄일 수 있는지 다룹니다.

3. Counterexample

• 동적 타입 언어 과신과 타입 안정성의 오해: "JavaScript나 Python은 변수에 타입을 안 써도 되니 편하다"며 정적 타입 체커(TypeScript, MyPy)를 거부하는 태도입니다. 대규모 프로젝트에서 동적 언어가 런타임에 undefined is not a function 같은 오류를 내는 이유(컴파일 타임에 타입 결론(Type Inference)을 확정 짓지 못하고, 함수 호출 순간에 메모리 객체의 프로토타입 체인을 탐색하다 실패함)를 이해하지 못하면 타입 안정성 문제를 놓치기 쉽습니다.
• 스코프(Scope)와 라이프타임(Lifetime)의 혼동: 블록 스코프 변수가 함수 호출 종료와 동시에 스택 메모리에서 소멸(Lifetime 종료)되는 것이 기본 동작임에도, 함수가 '클로저(Closure)'를 통해 반환될 때 해당 자유 변수가 어떻게 힙(Heap) 메모리로 이동해 수명이 연장되는지 모르는 경우입니다. 이 메커니즘을 이해하지 못한 채 콜백 함수를 남발하면 메모리 누수(Memory Leak)를 만들 수 있습니다.

4. Prerequisites

• 이산 구조 및 모델링 (Basic): BNF 문법 작성과 타입 추론 증명 과정에서 집합론과 명제 논리의 기초 수학 지식이 필요합니다. (01-01. Discrete Structures)
• 자료 구조 (Basic): 소스 코드가 추상 구문 트리(AST)로 파싱되는 과정을 이해하기 위해 트리의 순회(Traversal) 논리가 요구됩니다. (04-02. CDS)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 언어의 뼈대, 구문론 (Syntax & AST)

• Why to Learn: 컴파일러 에러 메시지가 '어떤 문법 규칙'을 위반했는지 명확하게 알려주는 원리를 파악해, 코드 작성의 문법적 오류를 스스로 교정하기 위함입니다.
• What to Learn:
  • Concepts: 어휘 분석(Lexical Analysis, Regex 활용), 구문 분석(Syntax Analysis, CFG 활용), 토큰(Token), 식별자(Identifier).
  • Skills: 배커스-나우르 표기법(BNF/EBNF) 작성, 구상 구문 트리(Parse Tree)와 괄호/세미콜론 등 불필요한 장식이 제거된 추상 구문 트리(AST) 분리 식별.
  • Tools: AST 변환 시각화 도구(AST Explorer).
  • Trade-offs: 사람이 읽기 쉬운 다채로운 문법(Syntactic Sugar) 지원 vs 컴파일러가 트리를 만들 때 감당해야 하는 파싱 오버헤드와 모호성(Ambiguity) 충돌.
• How to Learn:
  • 1단계: $3 + 4 \times 5$ 라는 수식을 BNF 문법(Expr $\rightarrow$ Term + Expr | Term)으로 정의하고, 파스 트리를 그려 연산자 우선순위(곱셈이 먼저 계산됨)가 문법 규칙에서 어떻게 강제되는지 관측합니다.
  • 2단계: 복잡한 if-else 블록이 AST로 치환될 때, Condition, ThenBranch, ElseBranch의 3개 자식을 가진 노드로 단순화되는 과정을 이해합니다.
• Implement: 직접 간단한 JSON 혹은 사칙연산 계산기의 정규 문법(BNF)을 정의하고 재귀 하향 파서(Recursive Descent Parser)의 뼈대 구조를 스케치해 보기.

Recommended

Core Topic 02: 실행 환경과 바인딩 역학 (Semantics & Binding)

• Why to Learn: 프로그램이 구동될 때 어떤 변수가 언제 스택/힙 메모리에 묶이고(Binding) 언제 해제되는지를 정확히 예측하여 메모리 누수를 막기 위해서입니다.
• What to Learn:
  • Concepts: 정적 바인딩(컴파일 타임) vs 동적 바인딩(런타임), 환경(Environment 레코드), 정적 스코프(Lexical Scope) 체인.
  • Skills: 상태(State)와 부수 효과(Side-effect) 분석, 클로저(Closure)가 캡처(Capture)한 자유 변수(Free Variable)의 수명 추적.
  • Tools: 언어 명세서(Specification), 스코프 체인 디버깅.
  • Trade-offs: 정적 바인딩을 통한 실행 전 철저한 검증과 빠른 실행 속도 vs 객체의 실제 타입에 따라 메서드 실행이 런타임에 늦게 결정(Late Binding)되는 가상 메서드(Virtual Method)의 유연성.
• How to Learn:
  • 1단계: 렉시컬 스코프(대부분의 언어) 환경에서 함수가 '선언된 위치'를 기준으로 상위 변수 환경을 기록하는 메커니즘을 환경 트리(Environment Tree) 구조로 그립니다.
  • 2단계: 외부 함수가 종료되어 로컬 스택 프레임이 파괴되었음에도 불구하고, 내부 함수가 반환될 때 그 렉시컬 환경 전체가 힙(Heap)으로 복사되어 생존하는(Closure) 과정을 메모리 다이어그램으로 시뮬레이션합니다.
• Implement: 단순 딕셔너리(해시 맵)를 중첩시켜 로컬 스코프와 글로벌 스코프를 모사한 커스텀 환경 레코드(Environment Record) 객체 시뮬레이터.

Practical

Core Topic 03: 타입 시스템과 안전성 방어망 (Type Theory)

• Why to Learn: 변수 간의 논리적 모순을 사전에 차단해, 대규모 엔터프라이즈 코드가 런타임 오류에 취약해지는 것을 줄이기 위해서입니다.
• What to Learn:
  • Concepts: 강타입(Strong)/약타입(Weak), 정적(Static)/동적(Dynamic) 타입 시스템, 명목적 타이핑(Nominal) vs 구조적 타이핑(Structural, Duck Typing).
  • Skills: 다형성(Polymorphism) 구현 방식(제네릭 템플릿의 컴파일 타임 코드 확장 vs 업캐스팅을 통한 서브타이핑 다형성), 타입 추론(Type Inference) 트리의 유니피케이션(Unification) 과정.
  • Tools: TypeScript, 정적 분석기.
  • Trade-offs: C++나 Java처럼 이름(클래스명) 기반으로 엄격하게 타입을 일치시키는 명목적 타이핑의 안전성 보장 vs 구조(멤버 변수/메서드)만 같으면 다 통과시키는 TypeScript식 구조적 타이핑이 주는 유연한 생산성.
• How to Learn:
  • 1단계: 동적 타입 언어에서 A = "5" + 3이 어떤 언어에서는 "53"으로 묵시적 강제 형변환(Coercion)이 일어나고, 어떤 언어에서는 타입 에러를 뿜는 현상을 의미론(Semantics) 설계 철학 관점에서 비교합니다.
  • 2단계: 변수에 타입을 적지 않아도 컴파일러가 AST를 순회하며 x = 5;에서 x를 정수형으로, y = x + 3.14에서 y를 실수형으로 연쇄적으로 유추(Hindley-Milner)해 나가는 방정식을 풉니다.
• Implement: 노드 두 개를 더하는 AST가 들어왔을 때 양쪽의 자식 노드 타입을 확인하고 합이 유효한지(정수+정수 O, 정수+문자열 X) 판별하는 간단한 타입 체커 패스(Type Checker Pass).

Advanced

Core Topic 04: 언어 패러다임의 융합과 고차 추상화 (Advanced Paradigms)

• Why to Learn: 상태(State)를 변경해 나가는 고전적 명령형 언어의 한계를 이해하고, 다중 스레드 환경에서 데이터 경합을 줄이는 함수형 프로그래밍 등 고수준 문제 해결 방식을 익히기 위해서입니다.
• What to Learn:
  • Concepts: 명령형(Imperative) vs 선언형(Declarative), 순수 함수(Pure Function)와 참조 투명성(Referential Transparency).
  • Skills: 일급 객체(First-class Function)로서의 함수 취급(변수 할당, 인자 전달), 상태 불변성(Immutability)을 유지하기 위한 영속 자료구조(Persistent Data Structure) 얕은 복사 원리.
  • Tools: 메타프로그래밍(매크로), 언어 확장을 위한 DSL(Domain Specific Language) 디자인.
  • Trade-offs: 부수 효과(Side-effect)를 전면 허용해 단일 메모리 주소를 덮어쓰는 C 방식의 빠른 실행 속도 vs 상태 변경을 금지해 새 객체를 더 많이 만들지만 동시성(Concurrency) 문제를 줄이는 함수형 패러다임.
• How to Learn:
  • 1단계: "배열의 각 요소를 2배로 만든다"는 문제를 for문(명령형)과 map 함수(선언형)로 작성해 보고, map 방식이 내부 반복 처리를 추상화하여 상태 변화(인덱스 증가)를 완전히 숨긴 것을 관측합니다.
  • 2단계: 순수 함수가 아니게 되는 사례(외부 글로벌 변수 수정, 파일 I/O)를 나열하고, 이것이 병렬 스레드 실행 시 가져오는 데이터 경합(Race Condition) 시나리오를 설계합니다.
• Implement: 인자로 넘어온 함수(로직)의 실행 속도를 측정하고 결과를 원래 그대로 반환하는 데코레이터(Decorator) 형태의 고차 함수(Higher-order Function) 작성.

7. Terminology

8. References

Primary

• [P1] CS2023 - PL/Foundations & Design — Language theory and structure.
• [P2] SWEBOK - Computing Foundations — Programming language selection and theory.

Secondary

• [Concepts of Programming Languages] Robert W. Sebesta — Comprehensive design focus.
• [Types and Programming Languages (TAPL)] Benjamin C. Pierce — The type theory Bible.

Industry

• [TypeScript Deep Dive] — Practical type system implementation in JS.
• [ECMAScript Specification] — Real-world semantics and grammar standard.

9. Final Checklist

Primary

• 정적 타입 언어와 동적 타입 언어의 차이를 '메모리 할당 시점'과 '오류 감지 시점' 관점에서 설명 가능한가? (P1)
• 간단한 수식(예: $1 + 2 \times 3$)에 대한 AST 구조를 명확히 그려낼 수 있는가? (P1)

Secondary

• 정적 스코프(Static Scope) 환경에서 자유 변수(Free Variable)의 값이 어떤 순서로 검색되는지 이해하는가?
• 타입 추론(Type Inference)이 개발자의 편의성과 컴파일러의 엄격함 사이에서 어떤 역할을 하는지 인지하는가?

Industry

• 실무 코딩 중 만나는 Type Mismatch 에러를 언어 명세(Specification) 관점에서 분석하고 해결 가능한가? (SFIA)
• 대규모 프로젝트에서 강한 타입 시스템을 적용했을 때의 유지보수 비용 절감 효과를 정량적으로 논할 수 있는가?