Semantic Analysis — Type System과 Type Checking

📌단원 개요

AST 구성을 마쳤으니, 이제 프로그램의 구조가 아니라 실제 의미(semantics)를 분석한다. 이 단계가 semantic analysis이며 핵심은 type checking이다.

7.1Overview of Type Systems

대부분의 언어는 모든 value(literal, constant, variable)에 type을 부여한다. type은 그 data를 어떻게 해석할지를 나타낸다 — integer, floating point, boolean, string, pointer 등.

이런 atomic type들은 enumeration, structure, variant type 같은 higher-order type으로 결합되어 복잡한 제약을 표현할 수 있다.

type system의 3가지 목적

type system 분류의 3축

/* This is C code */
int i;
int a[10];
for(i=0;i<100;i++) a[i] = i;

/* This is C-sharp code */
a = new int[10];
for(int i=0;i<100;i++) a[i] = i;
// IndexOutOfRangeException 발생

/* This is Java code */
public void sit( Furniture f ) {
   if (f instanceof Chair) {
       System.out.println("Sit up straight!");
   } else if ( f instanceof Couch ) {
       System.out.println("You may slouch.");
   } else {
       System.out.println("You may sit normally.");
   }
}

/* This is C code */
int x = 32.5;          // precision loss

/* This is C code */
int *i;
float *f = i;          // pointer 타입 불일치

/* This is C++11 code */
auto x = 32.5;         // x 는 double 로 추론
cout << x << endl;

7.2Designing a Type System

type system을 기술하려면 atomic type, compound type, 그리고 type 간 assigning·converting rule을 설명해야 한다.

user-defined types

atomic type으로 구현하되 range를 제한해 새 의미를 부여한다.

-- This is Ada code
type Day   is range 1..31;
type Month is range 1..12;

/* This is C code */
typedef int Month;
typedef int Day;

Month m = 10;
Day d = m;   /* 둘 다 int 라 허용됨 */

enumerations

변수가 가질 수 있는 finite set의 symbolic value를 선언하는 user-defined type. 내부적으로는 integer지만 가독성을 높이고 불법 값 할당을 막는다. (C는 enumeration 선언은 되지만 integer와 섞어 쓰는 것을 막지 못함.)

/* This is Rust code */
enum Fuzzy { True, False, Uncertain };

compound types

/* This is Go code */
type coordinates struct {
    latitude  float64
    longitude float64
}

/* This is C code */
union number {
    int i;
    float f;
};

union number n;
n.i = 10;
n.f = 3.14;

/* This is Rust code */
enum Expression {
    ADD{ left: Expression, right: Expression },
    MULTIPLY{ left: Expression, right: Expression },
    INTEGER{ value: i32 },
    NAME{ name: string }
}

unlike type을 함께 쓸 때의 4가지 선택지

integer i를 floating point f에 할당하거나, 함수 인자로 다른 type을 넘길 때 언어가 할 수 있는 일:

@days = ("Monday", "Tuesday", "Wednesday", ... );
@a = @days; # copies the array to array a
$b = @days; # puts the length of the array into b

7.3The B-Minor Type System

B-Minor의 type system은 safe, static, explicit이다. 그래서 기술이 간결하고 구현이 직관적이며 많은 error를 제거한다. 다만 엄격해서 검출해야 할 error가 많다.

array [size] type

function type ( a: type, b: type, ... )

7.4The Symbol Table

symbol table은 프로그램의 모든 declared variable(및 function 같은 named item)에 대해 알아야 할 정보를 기록한다. 각 entry는 struct symbol이다.

struct symbol {
    symbol_t kind;
    struct type *type;
    char *name;
    int which;
};

typedef enum {
    SYMBOL_LOCAL,
    SYMBOL_PARAM,
    SYMBOL_GLOBAL
} symbol_t;

factory function

struct symbol * symbol_create( symbol_t kind,
                               struct type *type,
                               char *name ) {
    struct symbol *s = malloc(sizeof(*s));
    s->kind = kind;
    s->type = type;
    s->name = name;
    return s;
}

같은 이름 x가 세 scope에 등장하는 예

아래 프로그램은 x를 type·storage class를 달리하며 세 번 정의한다. 실행 시 10 hello false를 출력해야 한다.

x: integer = 10;

f: function void ( x: string ) =
{
    print x, "\n";
    {
        x: boolean = false;
        print x, "\n";
    }
}

main: function void () =
{
    print x, "\n";
    f("hello");
}

Symbol Table API (Figure 7.3) — 6개 연산

void scope_enter();
void scope_exit();
int  scope_level();

void scope_bind( const char *name, struct symbol *sym );
struct symbol *scope_lookup( const char *name );
struct symbol *scope_lookup_current( const char *name );

7.5Name Resolution

symbol table이 준비되면, 변수 이름의 각 use를 그에 맞는 definition에 연결한다. 이 과정이 name resolution이다.

선언 resolve (Figure 7.4)

각 decl은 변수 선언이므로 새 symbol을 만들어 현재 scope의 이름에 bind한다. expression 선언(d->value가 not null)이면 그 expression도 resolve하고, function 선언(d->code가 not null)이면 새 scope를 만들어 parameter와 code를 resolve한다.

void decl_resolve( struct decl *d )
{
    if(!d) return;

    symbol_t kind = scope_level() > 1 ?
                    SYMBOL_LOCAL : SYMBOL_GLOBAL;

    d->symbol = symbol_create(kind,d->type,d->name);

    expr_resolve(d->value);
    scope_bind(d->name,d->symbol);

    if(d->code) {
        scope_enter();
        param_list_resolve(d->type->params);
        stmt_resolve(d->code);
        scope_exit();
    }

    decl_resolve(d->next);
}

표현식 resolve (Figure 7.5)

EXPR_NAME이면 symbol table에서 lookup해 연결하고, 그 외엔 left·right 자식을 재귀적으로 resolve한다.

void expr_resolve( struct expr *e )
{
    if(!e) return;

    if( e->kind==EXPR_NAME ) {
        e->symbol = scope_lookup(e->name);
    } else {
        expr_resolve( e->left );
        expr_resolve( e->right );
    }
}

7.6Implementing Type Checking

expression을 검사하기 전에 type structure를 다루는 helper 함수가 필요하다: equality·copy·delete.

type helper 함수들 (pseudo-code)

boolean type_equals(
    struct type *a, struct type *b )
{
  if( a->kind == b->kind ) {
    if( a and b are atomic types ){
       Return true
    } else if ( both are array ) {
       Return true if subtype is
              recursively equal
    } else if ( both are function ) {
       Return true if both subtype
       and params are recursively equal
    }
  } else {
    Return false
  }
}

struct type * type_copy( struct type *t )
{
    Return a duplicate copy of t,
    making sure to duplicate subtype
    and params recursively.
}

void type_delete( struct type *t )
{
    Free all the elements of t
    recursively.
}

기본 구조

struct type * expr_typecheck( struct expr *e )
{
    if(!e) return 0;

    struct type *lt = expr_typecheck(e->left);
    struct type *rt = expr_typecheck(e->right);

    struct type *result;

    switch(e->kind) {
        case EXPR_INTEGER_LITERAL:
            result = type_create(TYPE_INTEGER,0,0);
            break;
        case EXPR_STRING_LITERAL:
            result = type_create(TYPE_STRING,0,0);
            break;

        /* more cases here */

    }

    type_delete(lt);
    type_delete(rt);

    return result;
}

operator별 case 예시

case EXPR_ADD:
    if( lt->kind!=TYPE_INTEGER ||
        rt->kind!=TYPE_INTEGER ) {
        /* display an error */
    }
    result = type_create(TYPE_INTEGER,0,0);
    break;

case EXPR_EQ:
case EXPR_NE:
    if(!type_equals(lt,rt)) {
        /* display an error */
    }
    if(lt->kind==TYPE_VOID ||
       lt->kind==TYPE_ARRAY ||
       lt->kind==TYPE_FUNCTION) {
        /* display an error */
    }
    result = type_create(TYPE_BOOLEAN,0,0);
    break;

case EXPR_DEREF:
    if(lt->kind==TYPE_ARRAY) {
        if(rt->kind!=TYPE_INTEGER) {
             /* error: index not an integer */
        }
        result = type_copy(lt->subtype);
    } else {
        /* error: not an array */
        /* but we need to return a valid type */
        result = type_copy(lt);
    }
    break;

declaration / statement typecheck

대부분의 작업은 expr_typecheck에서 일어나지만, declaration·statement 등 다른 AST 요소도 typecheck해야 한다. 이들은 AST를 순회하며 expression type을 계산해 declaration이나 제약과 비교한다.

void decl_typecheck( struct decl *d )
{
    if(d->value) {
        struct type *t;
        t = expr_typecheck(d->value);
        if(!type_equals(t,d->symbol->type)) {
            /* display an error */
        }
    }
    if(d->code) {
        stmt_typecheck(d->code);
    }
}

void stmt_typecheck( struct stmt *s )
{
    struct type *t;
    switch(s->kind) {
        case STMT_EXPR:
            t = expr_typecheck(s->expr);
            type_delete(t);
            break;
        case STMT_IF_THEN:
            t = expr_typecheck(s->expr);
            if(t->kind!=TYPE_BOOLEAN) {
                /* display an error */
            }
            type_delete(t);
            stmt_typecheck(s->body);
            stmt_typecheck(s->else_body);
            break;
        /* more cases here */
    }
}

7.7Error Messages

compiler는 형편없는 error message로 악명 높다. 하지만 지금까지 만든 구조 덕분에, 어떤 type이 발견됐고 무엇이 문제인지 정확히 설명하는 message를 쉽게 출력할 수 있다.

s: string  = "hello";
b: boolean = false;
i: integer = s + (b<5);

error: type compatibility in expression

error: cannot compare a boolean (b)
       to an integer (5)
error: cannot add a boolean (b<5)
       to a string (s)

문제 발견 시 관련된 expression과 type을 정성껏 출력하면 된다.

printf("error: cannot add a ");
type_print(lt);
printf(" (");
expr_print(e->left);
printf(") to a ");
type_print(rt);
printf(" (");
expr_print(e->right);
printf(")\n");

7.8Exercises (연습문제)

myprintf(
    "error: cannot add a %T (%E) to a %T (%E)\n",
    lt,e->left,rt,e->right
);

7.9Further Reading

⭐핵심 정리 / 시험 포인트

📋한눈에 보기 — Cheat Sheet