bong-u/til

🏠 home 🐈 repository

프로그래밍언어개론

수정일 : 2024-06-13

Ocaml

Functional Programming

함수형 프로그래밍은 함수를 값처럼 다루는 프로그래밍 패러다임

  • 특징
    1. Immutable

    변수의 값이 변하지 않는다

    1. First-class function
    2. Higher-order function
    3. Referential transparency

    동일한 인자에 대해 항상 동일한 결과를 반환한다

    1. Lazy evaluation (지연 계산)

    필요할 때만 계산을 수행

Primitive Types

  • unit
  • int
  • float
    • int_of_float : float->int
    • float_of_int : int->float
  • bool : true/false
    • x = y : x equals y (structural equality)
    • x <> y : x not equals y (structural equality)
    • x == y : x equals y (physical equality)
    • x != y : x not equals y (physical equality)
  • char
  • string
    • ^ : string concatenation
    • .[n] : n-th character
    • .length : length of string
    • .sub n m : substring from n to m

Statement와 Expression

  • Statement

    프로그램의 상태전이(메모리 상태를 변경하는 행위)를 수행하는 언어의 구성 요소

  • Expression

    실행 시 값으로 계산외는 언어의 구성요소

  • Statement는 값을 반환하지 않는다

  • Expression은 값을 반환한다

  • 순수 함수형 언어는 Expression만을 가지고 있다

Tuple

1let x = (1, 2, 3)

Function

  • first-class object (1급 객체)
  1. 할당의 대상이 될 수 있다
  2. 함수의 인자로 사용할 수 있다
  3. 함수의 반화값으로 사용할 수 있다
  4. 비교연산을 적용할 수 있다
  • Higher Order Function (고차함수)

함수를 인자로 받거나 함수를 반환하는 함수

  • 재귀함수인 경우 rec 키워드를 사용해야 한다

Conditional branch

1if [expression1] then [expression2] else [expression3]

Pattern Matching

  • binding occurrence
  • Ocaml 컴파일러는 expression의 타입을 기반으로 패턴매칭의 완전성을 검사

Lists

  • :: : 리스트 앞에 원소를 삽입
  • @ : 리스트를 연결

Type definition

Disjoint union : 구분되는 식별자를 사용하여 여러 타입을 묶은 타입

  • Varient records라고도 부름 type [type_name] = [constructor] (of [type])? (| [name] (of [type])?)*
1type number =
2    | Int of int
3    | Float of float

Tail Call Optimization

재귀함수의 호출이 함수의 마지막 행위일 때, 스택을 사용하지 않고 반복문으로 최적화

Syntax and Semantics

Compilation

프로그래밍 언어로 작성된 프로그램을 다른 언어로 번역하는 행위

  • 적합한 프로젝트
    • 큰 규모의 소프트웨어 프로젝트 : 검증을 통해 오류를 사전에 탐지
    • 고성능 소프트웨어 : 최적화를 통한 성능 향상
    • 저수준 소프트웨어 : 기계어로 변환
  • 단점
    • 학습 곡선이 높다
    • Compilation 과정이 비싸고 복잡

Interpretation

프로그래밍 언어로 작성된 프로그램을 해석하여 실행하는 행위

  • 적합한 프로젝트

    • 높은 언어의 자유도를 활용한 소프트웨어 prototyping : 검증 절차의 부재로 인한 다양한 동적 특성 존재
    • 쉽고 직관적인 구조로 프로그래밍 교육 : 구문 구조가 단순
    • 실행환경에 영향을 받지 않는 cross-platform 소프트웨어 : platform 별로 구현된 interpreter를 통해 실행

  • 단점

    • 성능 이슈가 존재
    • 검증 절차의 부재로 인한 결함 탐지 및 수정의 어려움

Syntax (구문 구조)

프로그래밍 언어의 “형태”

  • 구문 구조의 종류
    • Concrete syntax : 프로그래밍 언어의 구문을 텍스트로 표현
    • Abstract syntax : Concrete syntax를 트리 구조로 표현

Semantics (의미)

프로그래밍 언어 구문의 “실행동작”

Unspecified Behaviors

특정조건에서 구문의 정의하지 않은 동작

Undefined Behaviors

특정조건에서 구문의 정의되지 않은 동작

Programming Language Syntax and Parsing

  • 언어 : L(G)

The Chomsky Hierarchy

  1. Regular Language : Finite-State Automation
  2. Context-Free Language : Pushdown Automation
  3. Context-Sensitive Language : Linear-Bounded Automation
  4. Recursively Enumerable Language : Turing Machine

AST (Abstract Syntax Tree)

프로그램의 추상구조를 나타내는 트리형태의 자료구조

CFG (Context-Free Grammar)

문맥을 고려하지 않고 항상 동일한 문자열을 표현하는 문법

  • G = ($\sum$, N, P, S)
    • $\sum$ : terminal의 유한집합
    • N : non-terminal 유한집합
    • P : production의 집합
    • S : 시작 nonterminal

BNF (Backus-Naur Form)

CFG의 표현 방법

  • 예시
1S ::= aAc
2A ::= aA
3| b
4| 𝜖

Derivation

문법의 규칙을 적용하여 문자열을 생성하는 과정

  • Leftmost derivation
  • Rightmost derivatio

Parse

Derivation의 역과정
Source code –lexing–> Token –parsing–> AST

  • leftmost derivation
  • rightmost derivation
  • ambiguous grammer

    leftmost derivation과 rightmost derivation이 다른 결과를 반환하는 문법

AE (Arithmetic Expression) Language

Syntax 정의

  • Concrete syntax (syntax 형태)
  • Abstract syntax (tree 형태)

Semantics 정의

  • e⇓n : e는 n으로 계산됨

Inference rule (추론 규칙)

전제로부터 결론을 이끌어내는 규칙 $$\frac{H_1 H_2 H_3 … H_n}{P}$$

  • $H_1, H_2, H_3, …, H_n$ : 전제
  • P : 결론
  • 전제가 모두 참이면 결론도 참

Bigstep operational semantics

  • Big-step : 프로그램의 계산이 하나의 큰 단계에 의해 수행
  • Small-step : 프로그램의 계산이 한 스텝 계산들의 연속에 의해 수행
  • Operational : 프로그램의 계산을 가상 기계의 동작(계산)에 기반하여 기술

Proof tree

Inference rule을 이용하여 결론을 증명하는 과정을 나타내는 tree형태의 자료구조

Syntactic Sugar and Identifier

Syntactic Sugar

사용자 편의를 위해 제공되는 구문

  • 주로 concrete syntax의 확장을 통해 제공

Desugaring

~(e) => 0 - e

Sugaring

0 - e => ~(e)

Identifier

프로그램의 어떤 요소와 연관된 이름

Identifier 등장

  • binding occurence : 정의를 위해 등장
  • bound ocurrence : 사용을 위해 등장
  • free identifier : 위 두가지에 해당하지 않는 등장 (정의되지 않은 변수 접근)

Identifier Scope

  • Identifier는 scope(범위)내에서 binding-bound 관계가 성립

  • Scope : binding ocurrence identifier가 bound 될 수 있는 범위

  • Scope를 벗어난 접근 : free identifier

  • Shadowing : 동일한 이름의 identifier가 중첩된 scope에서 binding되는 경우, 바깥쪽 scope의 identifier를 가리키는 것

Abstract Memory

  • $\sigma$(x) : 추상메모리 $\sigma$에서 x의 값을 반환
  • $\sigma$[x↦n](x') : 추상메모리 $\sigma$에서 x를 n으로 업데이트한 후 새로운 추상메모리를 반환
  • ↦ (mapsto) : 왼쪽 값을 오른쪽 값을 매핑한다

First Order Function (F1VAE)

F1VAE

VAE에 first-order function을 추가한 언어

First-order function

변수와 다르게 특별 취급하는 함수

Higher-order function

함수를 인자로 받거나 함수를 반환하는 함수

Concrete syntax

 1// single function
 2prog ::= decl expr
 3// multiple functions
 4prog ::= decl_list expr
 5decl_list ::= decl decl_list | decl
 6// single parameter
 7decl ::= def var var = expr endef
 8// multiple parameters
 9decl ::= def var var_list = expr endef | def var = expr endef
10var_list ::= var var_list | var
11expr_list ::= expr, expr_list | expr
12
13// 공통
14expr ::= let var = expr in expr
15       | var(expr)
16       | expr + expr
17       | expr - expr
18       | (expr)
19       | number
20       | ~ (expr)
21       | var

Abstract syntax

추상메모리 사용을 위한 보조함수

  • Λ(x) : 함수 추상메모리 Λ에서 함수이름 x의 값을 찾아 반환
  • Λ[x1 ↦→ (x2, e)] : 함수 추상메모리 Λ에 함수이름 x1의 값을 (x2, e)로 업데이트한 새로운 함수 추상메모리를 반환

Multiple parameters

$$ p ::= \overline{d}\ e \ d ::= def\ x\ \overline{x} = e \ e ::= n\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ x(\overline{e}) \ n \in Z\ x \in Var $$

Semantics

e[n/x]

함수 호출 시, 함수 몸체의 파라미터 변수를 전달된 이자로 치환한 후 계산

Lexical scope vs dynamic scope

  • Lexical scope : identifier의 scope가 컴파일시점에 저의
  • Dynamic scope : identifier의 scope가 실행시점에 결정

First Class Function (FVAE)

First-class function

함수를 값처럼 다루는 프로그래밍 언어의 특성

Concrete syntax

1expr ::= let var = expr in expr
2       | (fun var -> expr) // 추가된 것 : 함수 정의
3       | expr expr         // 추가된 것 : 함수 호출
4       | expr + expr
5       | expr - expr
6       | (expr)
7       | number
8       | ~ (expr)
9       | var

function applications

함수형 프로그래밍에서는 함수 호출 대신 함수 적용

Abstract syntax

$\lambda x.e$

$$ e ::= n\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ \lambda x.e\ |\ e\ e \ n \in Z\ x \in Var $$

  • $\lambda x.e$ : 함수 정의 (x는 파라미터, e는 함수 몸체)
    • x는 binding occurence
    • x의 scope는 e
  • $e\ e$ : 함수 적용
    • e1 : 함수로 계산되는 expression
    • e2 : 인자

Closure

Closure = Var X Expr X Store

  • FVAE에서는 함수도 “값"이므로 “값"의 확장이 요구된다

Multiple parameters

  • Concrete syntax
 1expr ::= let var = expr in expr
 2       | let var var = expr in expr
 3       | (fun var_list -> expr) // 추가된 것 : 함수 정의
 4       | expr expr
 5       | expr + expr
 6       | expr - expr
 7       | (expr)
 8       | number
 9       | ~ (expr)
10       | var
11var_list ::= var var_list | var // 추가된 것 : 파라미터 리스트

Conditional Branch (CFVAE)

Concrete syntax

 1expr ::= let var = expr in expr
 2       | (fun var_list -> expr)
 3       | if expr then expr else expr // 추가된 것 : 조건문
 4       | expr expr
 5       | expr + expr
 6       | expr - expr
 7       | expr < expr // 추가된 것 : 비교연산
 8       | (expr)
 9       | number
10       | bool
11       | ~ (expr)
12       | var
  • if-then-else가 다른 expression에 비해 우선순위가 낮다고 가정

Abstract syntax

$$ e ::= n\ |\ b\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ \lambda x.e\ |\ e\ e\ |\ e?e\ : e\ |\ e\ <\ e \ n \in Z\ b \in {true, false } x \in Var $$

  • Boolean support as syntatics sugar
    1. true와 false를 정수로 표현
    2. true와 false를 closure로 표현

Option 1. C style

$$ e ::= n\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ \lambda x.e\ |\ e\ e\ |\ e\ ?\ e\ :\ e\ |\ e\ <\ e\ n \in Z\ x \in Var $$

Option 2. Church boolean

$$ e ::= n\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ \lambda x.e\ |\ e\ e\ |\ e\ <\ e\ n \in Z\ b \in {true, false }\ x \in Var $$

Recursion (RCFVAE)

Concrete syntax

 1expr ::= let var = expr in expr
 2       | let rec var = expr in expr // 추가된 것 : 재귀함수
 3       | (fun var -> expr)
 4       | if expr then expr else expr
 5       | expr expr
 6       | expr + expr
 7       | expr - expr
 8       | expr < expr
 9       | (expr)
10       | number
11       | bool
12       | ~ (expr)
13       | var

Abstract syntax

$$ e ::= n\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ let\ x\ =\ e\ in\ e\ |\ let\ rec\ x\ =\ e\ in\ e |\ \lambda x.e\ |\ e\ e\ |\ e\ <\ e \ n \in Z\ x \in Var $$

minic 1

Imperative language (명령형 언어)

연속된 command(명령)을 통해 프로그램의 의미를 수행

Concrete syntax

 1prog ::= stmts
 2stmts ::= stmt | stmt stmts
 3stmt ::= var = expr;
 4       | if expr {stmts}
 5       | if expr {stmts} else {stmts}
 6expr ::= number
 7       | var
 8       | true
 9       | false
10       | (expr)
11       | expr + expr
12       | expr - expr
13       | expr < expr
14       | expr > expr
15       | expr == expr
16       | expr && expr
17       | expr || expr

Abstract syntax

$$ p ::= \overline{s} \ s ::= x = e\ |\ e?\ \overline{s} : \overline{s} \ e ::= n\ |\ x\ |\ b\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ e\ <\ e\ |\ e\ >\ e\ |\ e\ ==\ e\ |\ e\ &&\ e\ |\ e\ ||\ e \ n \in Z\ b \in {true, false}\ x \in Var $$

Semantics

  • p : MiniC program

Prog -> Store

  • s : MiniC statement

Store X Stmt -> Store

  • e : MiniC expression

Store X Expr -> Value

Short circuit evaluation

논리식 연산에 있어 결과가 정해진 경우 남은 expression 계산

minic 2

  • &x: reference
  • *e: dereference

Concrete syntax

 1prog ::= stmts
 2stmts ::= stmt | stmt stmts
 3stmt ::= def var;
 4       | var = expr;
 5       | *expr = expr;
 6       | if expr {stmts}
 7       | if expr {stmts} else {stmts}
 8       | while expr {stmts}
 9expr ::= number
10       | var
11       | true
12       | false
13       | &var
14       | *expr
15       | (expr)
16       | expr + expr
17       | expr - expr
18       | expr < expr
19       | expr > expr
20       | expr == expr
21       | expr && expr
22       | expr || expr

Abstract syntax

$$ p ::= \overline{s} \ s ::= def\ x\ |\ x = e\ |\ *e = e\ |\ e?\ \overline{s} : \overline{s}\ |\ while\ e\ \overline{s} \ e ::= n\ |\ x\ |\ b\ |\ x\ |\ e\ +\ e\ |\ e\ -\ e\ |\ e\ <\ e\ |\ e\ >\ e\ |\ e\ ==\ e\ |\ e\ &&\ e\ |\ e\ ||\ e\ |\ &x\ |\ *e \ b \in {true, false}\ n \in Z\ x \in Var $$

Semantics