Lecture 3: Semantics & Transformations

목차

 

Learning Objectives

- Write interpreters for simple languages
- Explain differences, advantages and disadvantages between compilers and interpreters
- Know which different types of semantics exist
- Apply big-step semantics rules to reduce expressions to values
- Explain what desugaring is, and why it is useful
- Implement a simple desugarer

 

 

Semantics (의미)

Semantics is the meaning of program phrase.

Semantics: Phrase → Meaning

 

 

Dynamic Semantics 

Operational Semantics: The meaning of a phrase is given by an algorithm for reducing the phrase to a value.

프로그램 작성 언어의 의미를 기술하는 방법.

얘가 Definitional Interpreters.

 

 

Denotational Semantics: The meaning of a phrase is this translation to an underlying mathematical domain.

 

Axiomatic Semantics: The meaning of a phrase is this set of axioms defining how it affects assertions about the program state.

 

 

Static Semantics vs. Dynamic Semantics

Static Semantics: (Context-sensitive) restriction of the set of valid program phrases; e.g. type systems

Dynamic Semantics: Run-time behavior of a program

 

 

Interpretation and Compilation

Interpreter: Directly performs the actions in the high level program

 

Compiler: Converts program to something executable by the platform.

 

 

Big Step Semantics

Big Step Semantics: One method of providing operational semantics. The meaning of program phrases is given by a set of rules which together form an algorithm for reducing programs to their meaning.

 

Simplified Rules

 

Ex) plus

만약에 e1 + e2 같은 게 있으면 e1과 e2에 각각 n1, n2를 부여하고 n = n1 + n2 한 값.

 

Example 1)

e1과 e2에 각각 3과 2를 대입. 그리고 위에 있는 num rule를 사용해서 n1, n2의 값에 배정.

 

 

Example 2)

Num = axiomatic interpretation

 

 

In Big Step Semantics, reduction of an expression happens through repeated reductions of its subexpressions. 

→ Semantic rules are defined recursively.

 

 

Conditional Expressions

Extending the Grammar

 

Extending the Abstract Syntax (ADTs)

 

Extending the Semantics

 

 

Extending the interpreter

 

 

Examples)

1. ( if  0  1  2)  →  Error

 

2. ( if  true  false  2 )  → False 

 

3. ( if  ( if  false  0  true )  1  2 )  →  ( if  true  1  2 )  →  1

 

 

Multi-armed Conditionals

A chain of if-else-if statements.

 

 

두 번째 예시: both conditions do not satisfy. 이때 else 없으면 Exception (if none of the conditions hold)

 

Syntax

2. Extra set of paranthesis. (괄호 하나 더 있어서 안 됨 → no longer matches the grammar)

3. Need one or more branches before the else.

6. Need one or more branches for cond.

 

A multi-armed conditional, or a cond expression, consist of a list of (condition expression) pairs, where both condition and expression are expressions. If the condition of the pair evaluates to true, then the result of the multi-armed conditional expression is the result of evaluating expression. Otherwise, if the condition of a pair evaluates to false, the next pair is tried. 

 

If each pair's condition evaluates to false and the condition of the last pair is not an else expression, a InterpException should be raised. 

 

1. False (첫번째 condition false여서 else로 감)

2. 3 (0이 3보다 작으니까 true되서 3)

3. 1 (false여서 다음 condition인 (true 1). 이거는 true니까 1

4. 5 (condition 1, 2 둘다 false 여서 3번째 condition으로 이동).

5. Interp Exception (False 밖에 없는데 else 없음) 

6. Interp Exception (5 6) 비교할 수 없음. Condition이 아님.

 

 

Semantics

 

 

Desugaring

Desugaring between parsing and interpretation

An elaboration of one program phrase into a different one

Typically, a desugaring reduces the number of syntactic forms in the core language

 

Distinction between a core language and a surface language.

The surface language may have various conveniences, but these get translated into the core language, whose constructs are all handled directly. 

The program that translates the surface language into the core language: Desugarer.

 

 

Why Desugar?

Small Language

- Easier to interp/compile/transform

- Less chances for mistakes

- Less code duplication 

 

Syntactic sugar

- Easy for programmers to read and write programs

- Good abstraction

 

 

 

 

 

 

Textbook

Two kinds of evaluators: Interpreters and compilers.

- An interpreter consumes a program and simulates its execution. 

- A compiler consumes a program and produces another program. That output program must then be further evaluated.

 

 

 

 

 

 

The variables in the function header are formal parameters and the expression in the function call are the actual parameters.

So in f, x is the formal parameter, while 9 is an actual parameter. 

 

 

 

The formal choice is the eager evaluation (eagerly reducing the actual parameter to a value before starting the function call). The latter choice is the lazy evaluation (not rushing to perform the evaluation).