1 of 103

Expressions

(식: LET, PROC, LETREC)

Choi, Kwanghoon (최광훈)

Chonnam National University (전남대학교)

2 of 103

Overview

Expressions in PL (식)

- The binding and scoping of variables (변수 이름에 속성을 부여, 그 범위)

2

The EOPL book (이오플 북)	Programming Languages (프로그래밍언어)	Essentials concepts of PLs (PL 주요 특징)
Ch.3 Expression (식)	LET	Expressions (식)
	PROC	Procedures (함수 정의와 호출)
	LETREC	Recursive procedures (재귀함수)

3 of 103

LET: A Simple Language

Examples

3

Constant(상수)

* positive-const : Name

* “11” : Program text

* 11 : Evaluation result

* positive_const.let : File

Arithmetic expr(산술식)

* nested-arith-left : Name

* “-(-(44,33),22)” : Program text

* -11 : Evaluation result

* nested_arith_left.let : File

Variable(변수)

* test-var-1 : Name

* “x” : Program text

* 10 : Evaluation result

* test_var_1.let : File

unbound variables : 정의되지 않는 변수

Refs. https://github.com/mwand/eopl3/blob/master/chapter3/let-lang/tests.scm

4 of 103

LET: A Simple Language

Examples

4

Conditional expression(조건식)

* if … then … else …

Testing if zero(0인지 검사)

* zero?( … )

Refs. https://github.com/mwand/eopl3/blob/master/chapter3/let-lang/tests.scm

5 of 103

LET: A Simple Language

Examples

5

Let expression(조건식)

* let v = … in … v …

Refs. https://github.com/mwand/eopl3/blob/master/chapter3/let-lang/tests.scm

6 of 103

LET: Syntax(구문)

How to define the syntax of a PL(프로그래밍언어 구문을 정의하는 방법)?

Grammar (문법)

- Backus-Naur Form, BNF

- a.k.a. Context-free grammar, CFG (문맥 자유 문법)

(cf. wiki 위키)

6

7 of 103

LET: Syntax(구문)

Elements of a grammar(문법의 구성 요소)

- Symbols(기호) : terminals and nonterminals (단말과 비단말)

- Terminals(단말) : the atomic elements of of a PL’s syntax (구문의 최소 요소)

- Nonterminals(비단말) :

* symbols representing a set of sequences of terminals

(단말 기호 시퀀스들의 집합을 표현하는 기호)

* the structure of the PL’s syntax by means of production rules

(생산 규칙으로 구문 구조를 정의)

7

8 of 103

LET: Syntax(구문)

The grammar for LET(LET 프로그래밍언어의 문법)

8

9 of 103

LET: Syntax(구문)

The grammar for LET(LET 프로그래밍언어의 문법)

- Terminals(단말) :

‘integer_number’, ‘-’, ‘(’, ‘,’, ‘)’, ‘zero?’, ‘if’, ‘then’, ‘else’, ‘identifier’, ‘let’, ‘=’, ‘in’

- Nonterminals(비단말) : Expression

- 7 production rules(7개 생산규칙)

9

‘zero?’ is a terminal, and ‘?’ is not a terminal.

let x = 1 in x

identifier(식별자)

integer_number(숫자)

let

=

in

10 of 103

LET: Syntax(구문)

Definition of terminals by regular expressions (정규식으로 터미널 정의)

- integer_number : [0-9]+

- identifier : [_a-zA-Z][_a-zA-Z0-9]*

- The other terminals are defined as they look (그 외 터미널들은 그대로 정의)

10

Regular expressions (정규식)

let x = 1 in x

identifier(식별자)

integer_number(숫자)

let

=

in

11 of 103

LET: Syntax(구문)

Derivation of an example expression, “let x = 1 in x” (예시 식의 유도 과정)

- Expression by (7)

=> let identifier = Expression in Expression by def. of identifier

=> let x = Expression in Expression by (1)

=> let x = integer_number in Expression by def. of integer_number

=> let x = 1 in Expression by (6)

=> let x = 1 in identifier by def. of identifier

=> let x = 1 in x

11

12 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Up to now, the syntax means a concrete syntax that is textually written in a program(지금까지 고려한 구문은 프로그램 텍스트로 작성된 구문).

Abstract syntax tree (추상 구문 트리)

- Consider syntactically valid programs (구문이 올바른 프로그램만 고려)

- Contains only the essential elements for the meaning of the programs (그러한 프로그램의 의미를 정할때 필요한 요소로만 구성)

=> Input of an interpreter (해석기의 입력)

12

13 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

The datatype for abstract syntax tree of LET (LET언어 추상 구문 트리를 표현하기 위한 자료형)

13

A Scheme datatype for the abstract syntax tree of LET : Figure 3.2 in [EOPL]

[REMIND] Haskell datatype (data)

[REMIND type synonym (type)

14 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Examples

- “11” => Const_Exp 11

- “-(44,33)” =>

Diff_Exp (Const_Exp 44, Const_Exp 33)

- “zero?(0)” => IsZero_Exp (Const_Exp 0)

- “x” => Var_Exp “x”

14

15 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Examples

- “if zero?(1) then 3 else 4”

=> If_Exp

( IsZero_Exp (Const_Exp 1) )

(Const_Exp 3)

(Const_Exp 4)

15

16 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Examples

- “let x = 3 in x”

=> Let_Exp “x” (Const_Exp 3) (Var_Exp “x”)

16

17 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Examples

- “let x = 3 in x”

=> Let_Exp “x” (Const_Exp 3) (Var_Exp “x”)

17

Q. 텍스트 프로그램(String)에서 파란 x와 빨간 x는 추상 구문 트리 (Exp)에서 각각 “x” (Identifier)와 Var_Exp “x” (Exp)로 다르게 표현될까?

A. let [ ] = 3 in [ ]에서 파란 [ ]는 오로지 변수만 작성하는 곳이고, 빨간 [ ]는 변수 뿐만 아니라 나머지 5가지 종류의 식을 모두 작성할 수 있는 곳이기 때문에 그 중에서 Var_Exp 임을 표시해야 어느 종류의 식을 작성하였는지 구분이 가능하기 때문

18 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Parsing(파싱): Turn a program text(a sequence of characters) into an abstract syntax tree (프로그램 텍스트, 문자 나열을 분석해서 추상 구문 트리를 만들기)

18

Parsing(파싱)

19 of 103

LET: Abstract Syntax Tree(추상 구문 트리)

Lab(실습): Parsing of LET (LET 프로그램 예제를 파싱하여 AST 확인)

-

19

20 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- value_of : an interpreter function (해석 함수)

- Exp : an abstract syntax tree (추상구문트리로 표현된 입력 프로그램)

- Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- ExpVal : The semantic value of the program (입력 프로그램의 의미/결과값)

20

21 of 103

LET: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- a mapping of variable names onto values { x1->v1, …, xn ->vn}

- ex) -(x,1) _{{ x -> 1}} ==> 0, -(x,1) _{{ x -> 2}} ==> 1

21

22 of 103

LET: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- a mapping of variable names onto values { x1->v1, …, xn ->vn}

data Env = Empty_Env -- { }

| Extend_Env Identifier ExpVal Env -- env { x->10 }

- empty_env :: Env - extend_env :: Identifier -> ExpVal -> Env -> Env

empty_env = Emtpy_env extend_env = Extend_Env

22

let x = 10

in … x …

23 of 103

LET: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- a mapping of variable names onto values { x1->v1, …, xn ->vn}

data Env = Empty_Env -- { }

| Extend_Env Identifier ExpVal Env -- env { x->10 }

- apply_env :: Env -> Identifier -> ExpVal

apply_env Empty_Env x = error ( “not found: ” ++ x )

apply_env (Extend_env y v env) x = if x==y then v else apply_env env x

23

let x = 10

in … x …

24 of 103

LET: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool

24

value_of (IsZero_Exp (Const_Exp 0)) env

⌈ “zero?(0)” ⌉

= ⌈ True ⌉

value_of (Diff_Exp (Const_Exp 44) (Const_Exp 33)) env

⌈ “-(44,33)” ⌉

= ⌈ 11 ⌉

(*) Discriminated union: S₁ + S₂ = { (1,a) | S₁ ∍ a } ⋃ { (2,b) | S₂ ∍ b }

25 of 103

LET: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool

25

26 of 103

LET: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool

Constructors Deconstructors

- Num_Val :: Int -> ExpVal - expval_num :: ExpVal -> Int

- Bool_Val :: Bool -> ExpVal - expval_bool :: ExpVal -> Bool

26

27 of 103

LET: Semantics (by Interpreter)

The denoted values, DenVal, are the values bound to variables (변수에 담을 수 있는 값, DenVal)

- DenVal = Int + Bool

27

initEnv = Extend_env i 1 (Extend_env b True Empty_env)

- 변수 i의 값 1 (Num_Val 1),

- 변수 b의 값 True (Bool_Val True)

cf. [ (i, 1), (b, True) ]

28 of 103

LET: Semantics (by Interpreter)

The denoted values, DenVal, are the values bound to variables (변수에 담을 수 있는 값, DenVal)

- DenVal = Int + Bool

Note: LET is too simple to have different ExpVal and DenVal (LET은 간단한 PL이므로 ExpVal과 DenVal이 다르지 않음)

28

29 of 103

LET: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

-

- E.g., extend_env “i” (Num_Val 1)

( extend_env “b” (Bool_Val True) empty_env )

==> [ i |-> 1, b |-> True ]

29

- Create an environment with 1 for “i” and True for “b”

(변수 i는 1, b는 True로 매핑하는 환경 만들기)

Abstract data types for environments

- emtpy_env = Empty_env

- extend_env = Extend_env

- apply_env env = …

30 of 103

LET: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

-

- apply_env ( extend_env “i” (Num_Val 1)

(extend_env “b” (Bool_Val True) empty_env) ) “b”

=> Bool_Val True

30

- Lookup the environment for an identifier “b” to find a boolean value True (주어진 환경에서 변수 “b”의 값 True를 찾기)

31 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Constant(상수):

- Variable(변수):

31

apply_env :: Env -> Identifier -> ExpVal

Case analysis on kinds of expression by pattern matching

(패턴 매칭으로 식의 종류에 따라 구분)

32 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Difference(뺄셈):

32

Evaluate exp1 (exp1 계산)

Evaluate exp2 (exp2 계산)

expval_num :: ExpVal -> Int

val1, val2 :: ExpVal

num1, num2 :: Int

Num_Val :: Int -> ExpVal

33 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Testing if it is zero(0인지 검사):

33

Evaluate exp (exp 계산)

expval_num :: ExpVal -> Int

val1 :: ExpVal

num1 :: Int

Bool_Val :: Bool -> ExpVal

Testing if num1 is zero

(num1이 0인지 검사)

34 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- if conditional(if 조건식):

34

Evaluate the conditional expression, exp1 (조건식 exp1 계산)

expval_bool :: ExpVal -> Bool

val1 :: ExpVal

If val1’s bool value is True, evaluate exp3

(val1이 True이면 exp3를 계산)

If val1’s bool value is True, evaluate exp2

(val1이 True이면 exp2를 계산)

35 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Let(지역 변수 선언):

35

Evaluate exp1 (식 exp1 계산)

Evaluate the body expression with an extended environment env with (var, val1)

(Let 몸체 식을 계산하되, Let에서 정의한 변수 var를 val1로 매핑하는 확장된 환경에서)

Q. In “value_of exp1 env”, does the env contains the variable var?

(exp1을 계산할 때 사용하는 환경 env에 선언하고자 하는 변수 var가 포함되어 있는가?)

36 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Let(지역 변수 선언): lexical scope (프로그램 텍스트로 판단하는 변수 범위)

let x = 3 in

let x = 4 in

x

36

cf. dynamic scope (실행하면서 판단하는 변수 범위)

env0

env1

env2

env1 = Extend_env “x” (Num_Val 3) env0

env2 = Extend_env “x” (Num_Val 4) env1

= Extend_env “x” (Num_Val 4)

(Extend_env “x” (Num_Val 3) env0)

apply_env env2 “x”

=> Num_Val 4

cf. value_of (Var “x”) env2

37 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Let(지역 변수 선언): lexical scope (프로그램 텍스트로 판단하는 변수 범위)

let x = 3 in

let x = -(x,1) in

x

37

cf. dynamic scope (실행하면서 판단하는 변수 범위)

env0

env1

env2

env1 = Extend_env “x” (Num_Val 3) env0

env2 = Extend_env “x” (Num_Val 2) env1

= Extend_env “x” (Num_Val 2)

(Extend_env “x” (Num_Val 3) env0)

apply_env env2 “x”

=> Num_Val 2

cf. value_of (Var “x”) env2

38 of 103

LET: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Let(지역 변수 선언): lexical scope (프로그램 텍스트로 판단하는 변수 범위)

let x = 3 in

let x = - ( let x = 5 in

x , 1) in

x

38

cf. dynamic scope (실행하면서 판단하는 변수 범위)

env0

env1

env2

env1 = Extend_env “x” (Num_Val 3) env0

env1_1 = Extend_env “x” (Num_Val 5) env1

= Extend_env “x” (Num_Val 5)

(Extend_env “x” (Num_Val 3) env0)

env2 = Extend_env “x” (Num_Val 4) env1

= Extend_env “x” (Num_Val 4)

(Extend_env “x” (Num_Val 3) env0)

apply_env env2 “x”

=> Num_Val 4

cf. value_of (Var “x”) env2

env1

env1_1

env1

Note. Since env1 can be extended to env1_1 or env2, it is better to implement env1 as immutable.

(env1이 env1_1로 확장되거나 env2로 확장될 수 있으므로 env1을 immutable하게 구현하는게 좋음.)

https://haskell.mooc.fi/part1#a-word-about-immutability-1

39 of 103

LET: Semantics (by Interpreter)

value_of_program :: Exp -> ExpVal

- 프로그램:

39

Evaluate a program expression with the initial environment.

(초기 환경을 가지고 프로그램 식을 계산)

extend_env “i” (Num_Val 1)

(extend_env “v” (Num_Val 5)

(extend_env “x” (Num_Val 10)

empty_env))

Initial environment (초기 환경)

40 of 103

LET: Project

-

40

Tokens.hs	Declare tokens (구문의 최소 단위 선언)
Lexer.hs	Turn a text (char seq.) into a token sequences( 텍스트를 토큰으로 분리)
Expr.hs	Declare abstract syntax trees (구문 트리 선언)
Parser.hs	Turn the token seq. into an abstract syntrax tree (토큰들을 구문 트리로)
Env.hs	Declare environments and semantics values (환경과 의미 값 선언)
Interp.hs	An interpreter (해석기)

41 of 103

LET: Project

Lab(실습): Evaluating LET programs (LET 프로그램 예제를 실행)

-

41

26개 예제를 한번에 테스트

stack test ch3:testletlang-test

42 of 103

LET: Project

Lab(실습): Evaluating LET programs (LET 프로그램 예제를 실행)

42

(명령어)

- stack run letlang-exe FILENAME.let

- stack exec -- letlang-exe FILENAME.let

43 of 103

Exercises

[More operators ]

43

44 of 103

Exercises

[More operators ]

44

45 of 103

PROC: A Language with Procedures

Procedure/lambda declaration(함수 정의)

- proc (x) -(x,1) : A lambda function that takes x and returns x - 1

(인자 x를 받아 x-1을 리턴하는 함수 lambda)

Procedure/lambda call(함수 호출)

- ( proc (x) -(x,1) 5 ) : Call the lambda function with the argument 5

=> -(5,1) (실인자 5를 주어 이 함수를 호출)

=> 4 : Replace x with 5 in the procedure body

(프로시저 몸체 안의 x를 5로 대체)

45

46 of 103

PROC: A Language with Procedures

Examples

46

-(5, 6)

( proc (y) -(5,y) 6 )

47 of 103

PROC: A Language with Procedures

Examples

47

Procedure(프로시저)

* Take 5 for the first arg. x,

take 6 for the second arg. y,

and do “-(x,y)”

(첫째 인자 x에 5를 받고

둘째 인자 y에 6을 받아

-(x,y)를 계산)

Procedure(프로시저)

* Define f as a local procedure, and

call f with 5 and 6 as its args.

(지역 프로시저 f를 정의하고

5와 6을 인자로 지정해 호출)

Procedure(프로시저)

* Define a y-combinator, fix, to make a functional into a recursive function

(재귀 함수를 만드는 함수 fix, 닉네임 와이컴비네이터)

Refs. https://github.com/mwand/eopl3/blob/master/chapter3/proc-lang/ds-rep/tests.scm

cf. Fixed-point combinator

48 of 103

PROC: A Language with Procedures

Examples

- Q. Try to simulate the evaluation of “time4 3” (time4 3의 계산 과정을 따라가보세요)

48

49 of 103

PROC: A Language with Procedures

We want to define the syntax and semantics of PROC by extending LET.

(LET을 확장해서 PROC의 구문과 의미 value-of 를 정의)

- New terminals(새로운 터미널)?

- New production rules in the grammar(문법에 추가할 새로운 생산 규칙)? Any changes(그 외의 문법 변경 사항)?

- Procedure values in ExpVal or DenVal? (ExpVal이나 DenVal에 프로시저 추가)

- New semantics rules, i.e. new cases of the value-of function(value-of 함수에 추가할 새로운 추상구문트리 노드 종류)?

49

50 of 103

PROC: Syntax(구문)

The grammar for PROC (PROC 프로그래밍언어의 문법)

- Terminals(단말) : …, ‘proc’

- Nonterminals(비단말) : Expression

- 7+2 production rules(9개 생산규칙)

50

Procedure(함수)

Procedure call

(함수 호출식)

Procedure body expr

(함수 몸체 식)

Procedure argument var (함수 인자)

rator (함수)

rand (인자)

A new keyword (terminal)

51 of 103

PROC: Syntax(구문)

Derivation of an example expression, “proc(x) proc(y) x” (예시 식의 유도 과정)

- Expression

=> proc ( identifier ) Expression by def. of the terminal, identifier

=> proc ( x ) Expression

=> proc(x) proc ( identifier ) Expression by def. of the terminal, identifier

=> proc(x) proc ( y ) Expression

=> proc(x) proc ( y ) identifier by def. of the terminal, identifier

=> proc(x) proc ( y ) x

51

Correct in syntax!

(올바른 구문의 프로그램)

52 of 103

PROC: Abstract Syntax Tree(추상 구문 트리)

The datatype for abstract syntax tree of PROC (PROC 언어의 추상 구문 트리를 표현하기 위한 자료형)

- cf.

52

A Scheme datatype for the abstract syntax tree of PROC: Section 3.3 in [EOPL]

[REMIND] Haskell datatype (data)

[REMIND type synonym (type)

| Var_Exp Identifier

53 of 103

PROC: Abstract Syntax Tree(추상 구문 트리)

Examples

- “((proc (x) proc (y) -(x,y) 5) 6)”

=> Call_Exp

(Call_Exp

(Proc_Exp “x”

(Proc_Exp “y”

( Diff_Exp (Var_Exp “x”) (Var_Exp “y”) )))

(Const_Exp 5))

(Const_Exp 6)

53

rator1

rand1

rand2

rator2

54 of 103

PROC: Abstract Syntax Tree(추상 구문 트리)

Parsing(파싱): Turn a program text(a sequence of characters) into an abstract syntax tree (프로그램 텍스트, 문자 나열을 분석해서 추상 구문 트리를 만들기)

Lab(실습): Parsing of PROC (PROC 프로그램 예제를 파싱하여 AST 확인)

54

55 of 103

PROC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- value_of : an interpreter function (해석 함수)

- Exp : an abstract syntax tree (추상구문트리로 표현된 입력 프로그램)

- Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- ExpVal : The semantic value of the program (입력 프로그램의 의미/결과값)

55

56 of 103

PROC: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool + Proc

56

value of (Proc_Exp “x” (Const_Exp 0)) env

⌈ “proc(x) 0” ⌉

value of (Diff_Exp (Const_Exp 44) (Const_Exp 33)) env

⌈ “-(44,33)” ⌉

value of (IsZero_Exp (Const_Exp 0)) env

⌈ “zero?(0)” ⌉

57 of 103

PROC: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool + Proc

How to represent a procedure?(프로시저를 표현하는 방법)

- Argument(인자 변수), body(몸체) ???

57

58 of 103

PROC: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool + Proc

How to represent a procedure?(프로시저를 표현하는 방법)

- Argument(인자 변수), body(몸체), and environment(환경)

58

env0

env1

env2

env4

env3

env1

“z”, Diff_Exp (Var “z”) (Var “x”), env1

“z”, Diff_Exp (Var “z”) (Var “x”), env3

59 of 103

PROC: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool + Proc

59

In Num_Val and Bool_Val, Haskell primitive types Int and Bool are used while in Proc_Val, Haskell datatype Proc is used.

(Num_Val과 Bool_Val에는 하스켈 기본 타입 Int와 Bool을 사용하고, Proc_Val에는 하스켈 데이터타입 Proc을 새로 정의해 사용)

60 of 103

PROC: Semantics (by Interpreter)

Each procedure carries its environment as well as the bound variable and the body(각 함수는 인자 변수와 함수 몸체 식과 그 식의 환경을 포함).

Note: Closures (클로저) (cf. Lambda in Semantics 시맨틱스에서 람다)

- Code + Environment (코드 var & body + 환경 saved_env)

60

61 of 103

PROC: Semantics (by Interpreter)

Each procedure carries its environment as well as the bound variable and the body(각 함수는 인자 변수와 함수 몸체 식과 그 식의 환경을 포함).

- E.g., The two same-looking procedures produce different results. Why?(동일한 함수 f와 g가 다른 결과를 내는데 그 이유는?)

61

env_f = [ (x, 200) ]

env_g = [ (x, 100), (f, …), (x, 200) ]

62 of 103

PROC: Semantics (by Interpreter)

Each procedure carries its environment as well as the bound variable and the body(각 함수는 인자 변수와 함수 몸체 식과 그 식의 환경을 포함).

- E.g., The two same-looking procedures produce different results. Why?(동일한 함수 f와 g가 다른 결과를 내는데 그 이유는?)

62

env_f = [ (x, 200) ]

env_g = [ (x, 100), (f, …), (x, 200) ]

Static scoping(정적 스코핑: 실행하기 전에 어느 변수를 참조할지 미리 결정)

- When creating functions f or g, it stores each variable environment(함수 f나 g를 만들때 각각의 변수 환경을 저장하고).

- When calling the function f or g, it finds the values of the variables appearing in the body expression through that environment(그 함수 f나 g를 호출할때 그 환경을 통해 몸체 식에 나타난 변수들의 값을 찾는다).

Free variables (자유 변수)

- f에서 x, g에서 x와 같은 변수

- f나 g 바깥에서 선언된 변수

63 of 103

PROC: Semantics (by Interpreter)

-

63

Thanks to 신효원!

64 of 103

PROC: Semantics (by Interpreter)

The expressed values, ExpVal, are the possible values of expressions (식을 계산해서 나올 수 있는 가능한 값, ExpVal)

- ExpVal = Int + Bool + Proc

- Num_Val :: Int -> ExpVal expval_num :: ExpVal -> Int

- Bool_Val :: Bool -> ExpVal expval_bool :: ExpVal -> Bool

- Proc_Val :: Proc -> ExpVal expval_proc :: ExpVal -> Proc

64

65 of 103

PROC: Semantics (by Interpreter)

The denoted values, DenVal, are the values bound to variables (변수에 담을 수 있는 값, DenVal)

- DenVal = Int + Bool + Proc

Note: type Env = [ (Identifier, DenVal) ]

65

env = { i |-> Num_Val 1, b |-> Bool_Val True, f |-> Proc_Val (Procedure “x” (Const_Exp 0) env0) }

66 of 103

PROC: Semantics (by Interpreter)

The denoted values, DenVal, are the values bound to variables (변수에 담을 수 있는 값, DenVal)

- DenVal = Int + Bool + Proc

Note: PROC is also too simple to have different ExpVal and DenVal (PROC도 간단해서 ExpVal과 DenVal이 다르지 않음)

66

67 of 103

PROC: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

-

67

68 of 103

PROC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Creating a procedure(함수 생성):

- Applying a procedure (함수 호출):

68

Case analysis on kinds of expression by pattern matching

(패턴 매칭으로 식의 종류에 따라 구분)

69 of 103

PROC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Creating a procedure(함수 생성):

- cf.

69

Case analysis on kinds of expression by pattern matching

(패턴 매칭으로 식의 종류에 따라 구분)

In Env.hs:

procedure :: Identifier -> Exp -> Env -> Proc

procedure var body env = Procedure var body env

let p = proc (x) -(x,1) in …

70 of 103

PROC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Calling a procedure(함수 호출):

-

70

- apply_procedure unpacks the proc into var, body, and env0.

(apply_procedure는 proc에서 var, body, env0를 꺼냄)

- Then it evaluate the body under the env0 extended with (var, arg).

(그 다음 body 식을 계산하되, 이때 env0를 (var,arg)로 확장한 환경을 사용)

71 of 103

PROC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Calling a procedure(함수 호출):

-

71

72 of 103

PROC: Project

-

72

Tokens.hs	Declare tokens (구문의 최소 단위 선언)
Lexer.hs	Turn a text (char seq.) into a token sequences( 텍스트를 토큰으로 분리)
Expr.hs	Declare abstract syntax trees (구문 트리 선언)
Parser.hs	Turn the token seq. into an abstract syntrax tree (토큰들을 구문 트리로)
Env.hs	Declare environments and semantics values (환경과 의미 값 선언)
Interp.hs	An interpreter (해석기)

73 of 103

PROC: Project

Lab(실습): Evaluating PROC programs (PROC 프로그램 예제를 실행)

73

74 of 103

PROC: Project

Lab(실습): Implementing Interp.hs and then testing with PROC programs (PROC 해석기를 구현하고 예제를 통해 테스팅)

74

(명령어)

- stack run proclang-exe FILENAME.let

- stack exec -- proclang-exe FILENAME.let

75 of 103

Exercises

[Compact environments of closures ]

75

let x = 200 in

let f = proc (z) -(z,x) in

let x = 100 in

let g = proc (z) -(z,x) in

-((f 1), (g 1))

g의 proc에 도달할 때 환경에 x, f, x가 쌓임.

이때, x는 필요하지만, f, x는 필요 없음.

따라서, g의 클로저에 x만 있는 환경을 보관함!

Extend_env x v_x

Extend_env f v_f

Extend_env x v_x

Empty_env

Extend_env x v_x

Empty_env

힌트)

76 of 103

Exercises

[Static/lexical scoping vs. Dynamic scoping ]

76

77 of 103

LETREC: A Language with Recursive Procedures

Examples

77

letrec (keyword token)

a recursive function(재귀 함수)

a recursive call(재귀 함수 호출)

78 of 103

LETREC: A Language with Recursive Procedures

Examples

78

Ref. https://github.com/mwand/eopl3/blob/master/chapter3/letrec-lang/tests.scm

79 of 103

LETREC: A Language with Recursive Procedures

Examples

79

Ref. https://github.com/mwand/eopl3/blob/master/chapter3/letrec-lang/tests.scm

80 of 103

LETREC: A Language with Recursive Procedures

We want to define LETREC by extending PROC. What needs to be changed? (PROC을 확장해 LETREC를 정의하려고 함. 추가 변경할 사항은?)

- New terminals(새로운 터미널)?

- New production rules in the grammar(문법에 추가할 새로운 생산 규칙)? Any changes(그 외의 문법 변경 사항)?

- New values in ExpVal or DenVal? (ExpVal이나 DenVal에 새로 추가?)

- New semantics rules, i.e. new cases of the value-of function(value-of 함수에 추가할 새로운 추상구문트리 노드 종류)?

80

81 of 103

LETREC: Syntax(구문)

The grammar for LETREC (LETREC 프로그래밍언어의 문법)

- Terminals(단말) : …, letrec

- Nonterminals(비단말) : Expression

- 9+1 production rules(10개 생산규칙)

81

Procedure argument (함수 인자)

Procedure name

(함수 이름)

A new keyword (terminal)

Procedure body expr

(함수 몸체 식)

82 of 103

LETREC: Abstract Syntax Tree(추상 구문 트리)

The datatype for abstract syntax tree of LETREC (LETREC 언어의 추상 구문 트리를 표현하기 위한 자료형)

- cf.

82

[REMIND] Haskell datatype (data)

[REMIND type synonym (type)

A Scheme datatype for the abstract syntax tree of LETREC: Section 3.4 in [EOPL]

No changes in the Exp for PROC

(PROC에 대한 Exp는 변경 사항 없음)

Letrec_Exp is introduced (Letrec_Exp 추가)

83 of 103

LETREC: Abstract Syntax Tree(추상 구문 트리)

Examples

- “letrec f(x) = -(x,1) in (f 33)”

=> Letrec_Exp “f” “x”

(Diff_Exp

(Var_Exp “x”)

(Const_Exp 1))

(Call_Exp (Var_Exp “f”) (Const_Exp 33))

83

Exp1

Exp2

This is a non-recursive function to make it simpler.

(더 간단한 예제를 들기 위해 비재귀 함수를 사용)

Identifier1

Identifier2

84 of 103

LETREC: Abstract Syntax Tree(추상 구문 트리)

Parsing(파싱): Turn a program text(a sequence of characters) into an abstract syntax tree (프로그램 텍스트, 문자 나열을 분석해서 추상 구문 트리를 만들기)

Lab(실습): Parsing of LETREC (LETREC 프로그램 예제를 파싱하여 AST 확인)

84

85 of 103

LETREC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- value_of : an interpreter function (해석 함수)

- Exp : an abstract syntax tree (추상구문트리로 표현된 입력 프로그램)

- Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- ExpVal : The semantic value of the program (입력 프로그램의 의미/결과값)

85

86 of 103

LETREC: Semantics (by Interpreter)

What is a (recursive) procedure value for double and its environment(double에 대한 재귀 프로시저 값과 환경은 무엇인가)?

- ExpVal = Int + Bool + Proc

86

No change in representing procedure values

(함수 값 표현은 그대로)

We express both recursive and non-recursive functions uniformly as values of type Proc.

(재귀 함수와 비재귀 함수 둘 다 Proc 타입의 값으로 동일하게 표현)

87 of 103

LETREC: Semantics (by Interpreter)

What is a (recursive) procedure value for double and its environment(double에 대한 재귀 프로시저 값과 환경은 무엇인가)?

87

env0

env1

env0

env0 does not include any binding for double.

(env0는 double에 대한 매핑을 포함하지 않음)

88 of 103

LETREC: Semantics (by Interpreter)

What is a (recursive) procedure value for double and its environment(double에 대한 재귀 프로시저 값과 환경은 무엇인가)?

Problem: We are building a procedure value ‘p’ for double to extend env0 with {double |-> p}. But the extended environment env1 must be used to build the p.

(문제점: 우리는 double에 대한 프로시저 값 p를 만들어 env0을 {double |-> p}로 확장하는 중임. 그러나 p를 만들 때 확장된 환경인 env1을 사용해야 함!)

88

env0

env1

env1 must be used here.

(env1을 사용해야함)

89 of 103

LETREC: Semantics

What is a (recursive) procedure value for double and its environment(double에 대한 재귀 프로시저 값과 환경은 무엇인가)?

Mutually recursive references are involved as (상호 참조 필요):

- p1 = Proc_Val ( Procedure “x” ⌈ “if zero?(x) … -((double -(x,1)), -2)” ⌉ env1 )

- env1 = env0 { “double” |-> p1 }

89

env0

env1

env1 must be used here.

(env1을 사용해야함)

90 of 103

LETREC: Semantics (by Interpreter)

Mutually recursive references is involved as(상호 참조):

- p1 = Proc_Val (Procedure “x” ⌈ “if zero?(x) … -((double -(x,1)), -2)” ⌉ env1)

- env1 = [ …, (“double”, p1), … ]

=> It requires a defining PL to have a feature for expressing mutually recursive data structures(구현 언어에서 상호 참조 자료 구조를 표현해야 함-예:C 포인터, Java 레퍼런스, Haskell 지연계산 lazy evaluation).

Could we have an alternative way that does not need the mutual recursive data structure(상호 참조 자료 구조없이 재귀함수의 프로시저 값과 환경을 표현하는 대안은)? => This is a topic in the following slides (다음에서 논의할 주제)

90

91 of 103

LETREC: Semantics (by Interpreter)

Our strategy (전략)

- Procedure values for non-recursive functions are created at the declaration (비재귀 함수를 선언할 때 프로시저 값을 생성).

- Procedure values for recursive functions are created when being referenced (재귀 함수를 참조할 때 프로시저 값을 생성)

- At the declaration of recursive functions, the environment is just extended to retain the information necessary for creating the procedure values later (재귀 함수를 선언할 때, 나중에 프로시저 값 생성할 때 필요한 정보를 환경에 저장).

91

92 of 103

LETREC: Semantics (by Interpreter)

Env : an environment (환경: 이 변수가 어떤 값을 갖고 있는지)

- At the declarationn of recursive functions, the environment is extended to retain the necessary information for creating the procedure values of these functions (재귀 함수를 정의할 때, 해당 함수의 프로시저 값을 생성하기 위해 필요한 정보를 보존하도록 환경을 확장).

92

Example)

env1 = Extend_env_rec

“double”

“x”

body expression

env0

env1

We do not create any procedure value at the declaration. We just extend the current environment to retain the necessary information for the creation.

(선언 시점에는 어떤 프로시저 값도 생성하지 않고, 단지 프로시저 생성에 필요한 정보를 보존하기 위해 현재 환경을 확장할 뿐.)

93 of 103

LETREC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Letrec(재귀함수 정의):

- At the declaration of recursive functions, the environment is extended to retain the necessary information for creating the procedure values of these functions (재귀 함수를 정의할 때, 해당 함수의 프로시저 값을 생성하기 위해 필요한 정보를 보존하도록 환경을 확장).

- cf.

93

94 of 103

LETREC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Var(변수):

94

This is where a recursive procedure is referenced, and apply_env is called.

(변수 식의 경우에서 재귀 함수를 참조되고, apply_env가 호출됨)

95 of 103

LETREC: Semantics (by Interpreter)

value_of :: Exp -> Env -> ExpVal

- Var(변수):

- Procedure values for recursive functions are created when they are referenced through variables

(재귀 함수는 변수를 통한 참조 시점에 프로시저 값이 생성).

95

[Env.hs]

The environment, saved_env, changes to (Extend_env_rec p_name b_var p_body saved_env).

(재귀함수 프로시저 값을 포함하지 않은 환경 saved_env를 그 값을 표현하도록 확장된 환경으로 변경)

96 of 103

LETREC: Semantics (by Interpreter)

Note: apply_env for Extend_env and Extend_env_rec

96

We refer to a procedure value previously added to the environment.

(이전에 생성되어 환경에 추가된 프로시저 값을 참조)

When referring to it, we create a new procedure value.

(참조할 프로시저 값을 지금 생성)

97 of 103

LETREC: Semantics (by Interpreter)

In summary, the LETREC language supports recursive functions by adding only the necessary information to the environment when evaluating a letrec expression, and by creating the procedure value anew in apply_env when a var expression is evaluated.

(요약하자면, letrec 식을 실행할 때는 환경에 필요한 정보만 추가하고, var 식을 실행할 때 apply_env에서 프로시저 값을 새로 생성함으로써 LETREC 언어는 재귀 함수를 지원.)

97

98 of 103

LETREC: Semantics (by Interpreter)

Q. value_of “let p = proc(x) -(x,1) in (p 1)” env0 vs.

value_of “letrec p(x) -(x,1) in (p 1)” env0

A. The meaning remains the same while the steps to set up the environment are different. (환경을 다루는 과정은 다르지만, 결과 값/의미는 동일)

98

99 of 103

LETREC: Project

-

99

Tokens.hs	Declare tokens (구문의 최소 단위 선언)
Lexer.hs	Turn a text (char seq.) into a token sequences( 텍스트를 토큰으로 분리)
Expr.hs	Declare abstract syntax trees (구문 트리 선언)
Parser.hs	Turn the token seq. into an abstract syntrax tree (토큰들을 구문 트리로)
Env.hs	Declare environments and semantics values (환경과 의미 값 선언)
Interp.hs	An interpreter (해석기)

100 of 103

LETREC: Project

Lab(실습): Evaluating LETREC programs (LETREC 프로그램 예제를 실행)

100

101 of 103

LETREC: Project

Lab(실습): Evaluating LETREC programs (LETREC 프로그램 예제를 실행)

101

102 of 103

Exercises

[An alternative implementation of the circular structure ] (1/2)

102

103 of 103

Exercises

[An alternative implementation of the circular structure ] (2/2)

103