함수형 언어 인터프리터 (C++)

ML 스타일 함수형 언어 인터프리터의 C++ 구현으로, 컴파일러 front-end 개념(e.g., AST, Environment), 함수형 프로그래밍 의미론, 그리고 Modern C++ 사용법에 대한 이해를 보이고자 하였습니다.

개요

고려대학교 COSE212 수업의 OCaml 기반 인터프리터를 C++로 포팅한 프로젝트입니다.

구현 내용

• AST (Abstract Syntax Tree): 언어가 지원하는 문법 요소(Syntactic feature) 정의
• Environment 기반 평가: 모든 스코프마다 별도의 환경이 존재하고, 해당 환경을 통해 평가
• Persistent 자료구조: Structural sharing을 통한 불변 자료구조

지원 언어 기능

• 렉시컬 스코핑을 가진 일급 함수
• 재귀 및 상호 재귀 프로시저
• Let 바인딩 및 조건 표현식

주요 설계 결정

1. Smart Pointer 전략

using PgmPtr = std::unique_ptr<Exp>;  // 단일 소유권
using ExpPtr = std::shared_ptr<Exp>;  // 공유 가능 (AST 노드)
using ValPtr = std::shared_ptr<Val>;  // 공유 가능 (런타임 값)

이유: AST와 Value는 여러 곳에서 참조될 수 있으므로 shared_ptr 사용. 자동 메모리 관리(RAII)로 누수 방지.

2. Persistent Environment (불변 환경)

EnvData Env::clone(EnvData &e) {
    return e;  // vector는 복사, 내부 shared_ptr는 공유
}

의도: OCaml의 불변 리스트 구조를 모방. Vector는 복사되지만 내부 Value 객체들은 shared_ptr로 공유되어 structural sharing 구현. 메모리 효율적이면서 각 스코프가 독립적인 환경을 유지.

3. Virtual operator== with Exception

class Procedure : public Val
{
public:
    bool operator==(Val& other) const {
        throw NotAllowedEqCheck("Procedure"); 
    }
};

이유: 함수는 문법을 통해 동일성을 결정할 수 없음.

4. Immutable Semantics 구현

ValPtr eval(ExpPtr exp, EnvData env);  // pass by value

설계: Environment를 값으로 전달하여 OCaml의 불변 의미론 구현. 각 재귀 호출이 독립적인 환경을 가져 상위 스코프에 영향을 주지 않음.

기술 스택

• 언어: C++17
• 메모리 관리: Smart pointers (unique_ptr, shared_ptr)
• 다형성: Virtual functions, dynamic_cast
• 예외 처리: Custom exception classes

설치 및 실행

Setup

./setup.sh

Build

cd build
cmake ..
make

Test

./test_pl

프로젝트 구조

pl_base/
├── include/
│   ├── ast.hpp           # AST 노드 정의
│   ├── environment.hpp   # Value 타입 및 환경 관리
│   ├── error.hpp         # 예외 정의
│   └── evaluator.hpp     # 인터프리터
└── src/
    ├── ast.cpp
    ├── environment.cpp
    ├── evaluator.cpp
    └── test.cpp

학습 포인트

1. 함수형 개념의 Imperative 구현

   • OCaml의 불변 자료구조를 vector의 shallow copy를 이용한 ructural sharing으로 구현
   • Closure를 environment capture로 구현

2. Modern C++ 활용

   • Move semantics (std::move)
   • Smart pointers를 통한 자동 메모리 관리
   • Virtual functions / Smart pointer를 통한 다형성 확보

3. 컴파일러 Front-end 이해

   • AST 설계 및 traversal
   • Environment 기반 evaluation