지금껏 다양한 깃 명령어들을 사용해왔지만, 깃이 정확히 어떻게 동작하는지는 모르고 있었다.

이번에 OSSCA(오픈소스 컨트리뷰션 아카데미)에 참여하게 됐는데, 깃 리포지토리에서 커밋 시 .git 폴더 안의 내용들이 어떻게 변하는지 알아보는 과제를 받았다.

과제 수행 과정에서 알게 된 점들을 기록해두려 한다.

git init

git init은 깃 리포지토리를 초기화(initialize)하는 명령이다

어떻게? .git이란 숨김 폴더를 하나 만든다:

.git/hooks 안에는 여러 깃 훅 예시 파일들이 들어있다

.git/info/exclude 파일은 .gitignore 파일과 동일한 패턴 매칭 문법을 사용해 git에서 특정 파일들을 추적하지 않도록 할 수 있다

.git/refs/heads에는 브랜치 정보가 담기게 되는데, 첫번째 커밋 전에는 브랜치 정보가 없으므로 빈 디렉토리에서 시작한다

.git/config 파일에는 리포지토리 단위의 깃 설정과 remote 정보 같은 내용들이 담기게 된다

이때 전역 git 설정과 리포지토리의 .git/config의 값이 충돌할 경우, 리포지토리의 설정값이 우선순위를 가진다. (user.name, user.email 등이 겹친다면 리포지토리의 설정이 적용된다)

.git/HEAD 파일은 현재 checkout된 위치를 나타내는데, 두 가지 상태를 가질 수 있다:

1. 일반적인 상태 (현재 브랜치를 가리키는 symbolic reference)
2. detatched HEAD

TODO: HEAD 설명 더 채우기

.git/FETCH_HEAD 파일에는 마지막 git fetch 결과가 담기는데, 처음에는 remote가 없기 때문에 빈 파일이다

.git/description 파일은 GitWeb 같은 웹 인터페이스에서 저장소 설명을 보여주기 위한 파일이라고 하는데, GitHub, GitLab, Gitea에서는 사용되지 않는다고 하니 이런게 있다는 것 정도만 알아두면 될 것 같다

git add

간단한 파일을 하나 만들고 git add 명령을 실행하면, git commit 명령을 수행하기 전에도 .git/objects 에 새로운 blob 객체가 생기는 것을 확인할 수 있다:

➜ git ls-files -s

100644 9f4d96d5b00d98959ea9960f069585ce42b1349a 0	hello.md

➜ git cat-file -p 9f4d96d5b00d98959ea9960f069585ce42b1349a

Hello Git

blob 이란 Binary Large OBjects의 약어로, 파일 내용을 zlib 압축 알고리즘으로 압축한 객체다.

압축을 풀고 읽으면 해당 파일의 모든 내용이 담겨있는 것을 확인해볼 수 있다

+ 한 디렉토리 안에 들어있는 파일의 수가 너무 많아지면 파일 시스템의 성능이 저하될 수 있기 때문에, 오브젝트의 해시 값 40자 중 앞 2글자는 디렉토리 이름으로 사용하고 나머지 38글자를 파일명으로 사용한다

git commit

커밋을 하고 나면 .git/objects에 commit, tree 두가지 객체가 더 생성되는 것을 확인할 수 있다

commit은 tree를 가리키고, tree는 파일 이름과 blob을 매핑하는 구조다:

➜  git cat-file -p 6808b6d1928c9f9b5aeac8cc22ff55153fa62a41

tree e11db9408991281fa8fc0b0bd455ecaffbf74cc2
author doorcs <itsdoorcs@gmail.com> 1777275722 +0900
committer doorcs <itsdoorcs@gmail.com> 1777275722 +0900

hello.md 커밋

➜  git cat-file -p e11db9408991281fa8fc0b0bd455ecaffbf74cc2

100644 blob 9f4d96d5b00d98959ea9960f069585ce42b1349a	hello.md

git branch

깃에서 브랜치는 어떻게 관리될까?

브랜치 정보는 .git/refs/heads 안에서 파일로 관리된다.
파일 내용도 별다를 게 없는데, 특정 커밋 해시값이 저장되어 있는 텍스트 파일이다

main 브랜치로부터 develop 브랜치를 새로 만들게 되면 .git/refs/heads 안에 develop이라는 이름의 파일이 생성되는데, main 파일과 동일한 커밋 해시값이 들어있는 것을 확인할 수 있다

blob 중복 관리

빈 파일을 두 개 만들고 git add 명령을 실행하면 blob 객체가 하나만 생성되는 것을 확인할 수 있다.

깃은 git add 명령을 통해 staging area에 올라오는 모든 파일에 대한 blob 파일을 만드는데, 이때 파일에 들어있는 내용을 기준으로 추적하기 때문에 내용이 겹칠 경우 동일한 blob을 재사용한다

빈 파일 두개를 커밋한 다음 commit이 가리키는 tree 의 내용을 살펴보면
empty1.md, empty2.md 두 파일이 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 라는 동일한 blob 과 매핑되어 있는 것을 확인해볼 수 있다:

➜ git cat-file -p 0c04eb9141cec2836a4bb1293abb3db0179fb604

tree 137acbf1803395bc2d236f19af50db56a02a4eca
parent 6808b6d1928c9f9b5aeac8cc22ff55153fa62a41
author doorcs <itsdoorcs@gmail.com> 1777277752 +0900
committer doorcs <itsdoorcs@gmail.com> 1777277752 +0900

empty1, empty2 커밋

➜ git cat-file -p 137acbf1803395bc2d236f19af50db56a02a4eca

100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391	empty1.md
100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391	empty2.md
100644 blob 9f4d96d5b00d98959ea9960f069585ce42b1349a	hello.md

git merge

현재 브랜치별 커밋 상태는 다음과 같다:

• main 브랜치
  • 6808b6d1928c9f9b5aeac8cc22ff55153fa62a41 (hello.md 커밋)
• develop 브랜치
  • 6808b6d1928c9f9b5aeac8cc22ff55153fa62a41 (hello.md 커밋)
  • 0c04eb9141cec2836a4bb1293abb3db0179fb604 (empty1, empty2 커밋)

main 브랜치로 돌아와서 develop 브랜치와 겹치지 않는 새로운 파일을 커밋하게 되면 브랜치와 커밋 히스토리가 갈라지게 된다:

이 경우 두 브랜치의 작업 내용들을 합치려면 merge commit이 필요하다

➜ git checkout main

Switched to branch 'main'

➜ git merge develop

Merge made by the 'ort' strategy.
 empty1.md | 0
 empty2.md | 0
 2 files changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 empty1.md
 create mode 100644 empty2.md

merge commit 이후 git log 명령을 실행하면 커밋이 시간 순서에 맞게 잘 합쳐진것을 확인해볼 수 있다:

일반적인 commit 객체는 parent 커밋을 한 개 가지지만,
merge commit 객체는 parent 커밋을 두 개 이상 가질 수 있다:
(브랜치 세 개를 합치면 parent 커밋이 세 개 존재하기도 함)

➜ git cat-file -p 95ee2c0c402f0a0a4bc81987e812eada0c0fedbf

tree e737137c198438d3f50927bbfdfdfb6951499049
parent cf2e9f4ab0d764c2f94534779eb16a524eecf289
parent 0c04eb9141cec2836a4bb1293abb3db0179fb604
author doorcs <itsdoorcs@gmail.com> 1777280109 +0900
committer doorcs <itsdoorcs@gmail.com> 1777280109 +0900

Merge branch 'develop'

갈라졌던 깃 브랜치가 다시 합쳐지는 과정을 시각화해보면 다음과 같다:

*   95ee2c0 (HEAD -> main) Merge branch 'develop'
|\
| * 0c04eb9 (develop) empty1, empty2 커밋
* | cf2e9f4 newblob 커밋
|/
* 6808b6d hello.md 커밋

정리

깃을 구성하는 핵심 객체들 ( .git/objects )

• COMMIT
  • <Tree> + <Parent> + <Author> + <Committer> + <Message> 구조 (항목 간 줄바꿈)
  • tree 객체를 가리키고 있음
  • parent commit 객체도 가리키고 있음 (최초 1회 커밋은 parent commit이 없다)
  • merge commit 객체의 경우 parent commit 정보를 두 개 이상 가지고 있기도 함
  • + author, committer, commit message 정보도 가지고 있음
    • 이때 author 정보와 committer 정보는 달라질 수도 있다
• TREE
  • <Mode> <Type> <SHA-1 hash> <Name> 구조의 리스트 (여러줄일 수 있다)
  • tree 객체의 줄 수 == 해당 tree 의 직속 하위 요소 수 (디렉토리, 파일 모두 포함)
    • Mode
      • 100644: 일반 파일
      • 100755: 실행 파일 (Executable)
      • 040000: tree (디렉토리 안에 디렉토리가 있는 경우를 표현)
    • Type
      • blob (파일)
      • tree (디렉토리)
    • SHA-1: 해시값
    • Name: 파일명 또는 디렉토리명
• BLOB (Binary Large OBjects)
  • <Header> <Content> 구조 (한 줄)
    • Header
      • 아래 구조 고정:
      • blob <Size>\0
    • Content
      • zlib 압축 알고리즘으로 압축된 파일 원본 데이터
  • git commit 시점이 아닌 git add 시점에 생성된다
  • 파일 내용 전체를 담고 있음
  • 파일명은 내용에 포함되지 않는다
    • file rename commit은 blob 수정이 아니라 tree 수정!!

커밋, 트리, 블롭은 모두 40자리 해시 값으로 표현된다

이때 한 디렉토리에 너무 많은 파일이 들어가면 파일시스템의 성능에 영향을 줄 수 있기 때문에,
앞 2자리는 디렉토리 이름으로 사용하고 나머지 38자를 파일명으로 사용한다!

• 자바는 숫자 리터럴에 L 접미사를 붙여주지 않으면 int취급!!!

long wrong = 1_000_000_000 * 1_000_000_000;
// 이러면 int*int라 오버플로우 발생!!! (wrong == -1486618624)

long right = 1_000_000_000L * 1_000_000_000;
// 한쪽에 `L`을 붙여서 long 리터럴로 만들어줘야 오버플로우 안 생김

long error = 2_147_483_648;
// int범위를 넘어서는 리터럴을 L 접미사 없이 사용하면 컴파일 에러가 발생한다!!
// error: integer number too large

• 배열 크기, Collection의 인덱스, 크기관련 메서드는 모두 파라미터로 int를 받고 int를 리턴!!

Queue.size()                    // 컬렉션의 size()는 항상 int형을 리턴함
String.length()                 // String의 length()도 마찬가지

long[] arr = new long[(int)3L]  // 배열의 크기는 int형만 가능
// long[] err = new long[3L]

List.get(3)                     // 인덱스는 int형이어야 함
String.charAt(7)                // 인덱스는 int형이어야 함
String.substring(2, 3);         // 인덱스는 int형이어야 함

오버플로우 없는 평균

int a = 2_147_483_647;
int b = 3;

int avg = a + (b-a)/2;

나눗셈 결과 올림 처리

int dividend = 7;
int divisor = 3;

int ceil = (dividend + divisor - 1) / divisor;

에라토스테네스의 체

• 소수 판정이 필요할 때, 범위가 넓다면 거의 무조건 이거 쓰는거

boolean[] sieve = new boolean[N+1]; // 1-based 인덱스 쓰기 위해 크기+1
Arrays.fill(sieve, true);

sieve[1] = false;
for (int i = 2; i*i <= N; i++) {
    if (sieve[i]) { // 현재 수가 소수라면
        for (int j = i*i; j <= N; j+=i) {
            sieve[j] = false; // 그 수의 배수는 모두 소수가 아니다
        }
    }
}

반복문 불변식을 활용한 파라메트릭 서치

int search() {
    int fr = -1; // 조건을 항상 만족하는 지점에서 시작
    int rr = N+1; // 조건을 항상 만족하지 `않는` 지점에서 시작

    while (fr+1 < rr) {
        int mid = fr + (rr-fr)/2;

        if (check(mid)) { // 조건을 만족하는지 확인
            fr = mid;
        } else {
            rr = mid;
        }
    }

    return fr; // 조건을 만족하는 최댓값
    // return rr; // 조건을 만족하지 않기 시작하는 지점
}

이분탐색

int search(int[] arr, int target) {
    int fr = -1;
    int rr = arr.length; // 범위설정 주의! `0`이랑 `length-1`이 아니다

    while (fr+1 < rr) {
        int mid = fr + (rr-fr)/2;

        if (arr[mid] < target) {
            fr = mid;
        } else {
            rr = mid;
        }
    }
    // 반복이 끝나면 rr에 `조건을 만족하지 않기 시작하는 지점`이 담긴다
    // rr == `arr[mid] >= target` 시작되는 지점 == Lower Bound

    if (rr < arr.length && arr[rr] == target) {
        return rr;
    } else {
        return -1; // // rr이 갱신된 적 없거나 타겟과 다르다면 찾지 못한것
    }
}

유니온 파인드 (DSU 구현체)

class DSU {

    int[] parent;
    int[] size;

    DSU(int n) {
        parent = new int[n+1];
        size = new int[n+1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]]; // path halving 기법
            x = parent[x];
        }

        return x; // `x == parent[x]` 의 의미? `루트까지 올라왔다`
    }

    boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return false;

        if (size[pa] < size[pb]) {
            // size[pa]가 size[pb]보다 작다면 pa와 pb의 순서를 바꿔주고 시작
            int tmp = pa;
            pa = pb;
            pb = tmp;
        }
        
        parent[pb] = pa;
        // 작은놈의 부모를 큰 놈으로 바꾼다 == 큰 놈을 작은놈의 부모로 만든다
        size[pa] += size[pb];
        // 부모의 크기를 자식 크기만큼 키운다
        return true;
    }
}

• Control?
  • Sequence Control, Flow Control: 수행 순서 제어
    • implicit
    • explicit
  • Data Control: 데이터 흐름 제어
• Classifying Sequence Controls
  • Expression Level
  • Statement Level
  • Subprogram Level
    • Subprogram Control에서 다룸

Expression Level

Tree Representation

: 표현식을 나타내는 기본적인 방법

• Functional Composition
  • 연산자(operator or function)를 서브트리의 루트에
  • 피연산자를 연산자의 하위 노드에!
• 트리 표기는 계산의 의존성을 나타낼 뿐, 좌측 서브트리와 우측 서브트리의 계산 순서는 명확하지 않다!!!

Expression Syntax

• Infix: 연산자가 피연산자 사이에 위치 (이항 연산에 적합)
  • 계산 순서가 모호할 수 있다
    • infix의 모호함을 해결하는 방법:
      • 매번 괄호를 써 준다
      • 우선순위와 결합방향을 정한다
  • (a + b)
• Prefix: 연산자가 피연산자들의 앞에 위치
  • 일반적인 함수 호출 표기
  • (+ a b), add(a, b)
• Postfix: 연산자가 피연산자들의 뒤에 위치
  • 스택을 활용한 계산에 적합하기 때문에, 가장 많이 사용되는 방식!
  • 컴파일러의 코드 생성에도 유리하다
  • (a b +)

Precedence

• 우선순위
• 인접한 다른 연산자들 사이의 피연산자가 어떤 연산자의 피연산자인지를 결정

Associativity

• 결합 방향
• 인접한 같은 우선순위인 연산자들 사이의 피연산자가 어떤 연산자의 피연산자인지를 결정

"모호함을 어떻게 해결할것인가"는 언어의 선택:

C: 모든 연산자의 우선순위와 결합방향을 사전에 정의
APL: 우선순위가 없음(모두 동일한 우선순위), 항상 right-to-left 결합
Forth: Postfix 방식을 사용

Evaluation Order

Eager Evaluation

• 피연산자의 값을 (무조건) 먼저 구하고 -> 연산자(operator or function)를 적용
• eval-apply evaluation model
• pass by value 인수 전달 방식과 유사성이 있다

Lazy Evaluation

• 연산자(operator or function)의 정의에 따라, 필요할 경우에만 피연산자의 값을 계산함
• push-enter evaluation model
• pass by name 인수 전달 방식(Thunk)과 유사성이 있다

Side Effect

: 실인수(Arguments)를 이용하여 결과값을 계산하는 것 외에 수행하는 다른 연산

• 비지역변수(non-local) 변경
• 입출력(I/O) 연산 - 파일 또는 콘솔I/O에 대한 Assignment!!
• Manual Memory Allocation - malloc, new, ...

int x = 3;
int y = ++x * x++; // 20

• 피연산자를 계산할 때, side effect가 발생한다면 결과값 예측이 어려워진다!
  • sol 1: 피연산자들의 계산 순서를 정확히 정의
  • sol 2: Side Effect를 사용하지 않도록 강제

Short-Circuit Evaluation

• 논리합 or 논리곱 연산자의 경우, 좌측 피연산자의 계산 결과에 따라서 우측 피연산자의 계산 여부를 결정할 수 있다!
• Lazy Evaluation의 특수한 형태로도 볼 수 있다

if (1 || /* */) // 뒤에 오는 Expression과 무관하게 조건을 만족시킴
if (0 && /* */) // 뒤에 오는 Expression과 무관하게 조건을 만족시키지 못함

• Ada의 경우, short-circuit evaluation이 적용되는 연산자와 적용되지 않는 연산자를 모두 제공
  • and then, or else - short circuit eval 버전
  • and, or - 무조건 eager eval 버전

Statement Level

Assignment Statement

• Assignment를 operator로 간주하는 언어도 있다 (C++)
  • -> cascading assignment 가능
  • a = b = 3;
• 언어에 따라 배열, Record와 같은 Aggregation에 대한 assignment를 지원할 수도 있다

I/O Statement

• 파일 또는 콘솔 I/O에 대한 Assignment로 볼 수도 있다!
• 대부분의 경우, 언어 라이브러리를 통해 지원된다

Explicit Sequence Control

• 기계어(Machine Code)로부터 유래됨!
  • goto
  • break, continue

Proper Program Theory

: 프로그램의 실행 흐름을 어떻게 가져가야 할 것인가? 어떤 프로그램이 "제대로 된" 프로그램인가?

Flowchart Nodes

: 어떤 Flowchart도 아래 세 타입의 노드와 간선들(arcs)로 표현될 수 있다

• Function Node
• Decision Node
• Join Node

Proper Program

• 입구가 하나 (1 entry arc)
• 출구도 하나 (1 exit arc)
• 입구로부터 모든 노드로 향하는 경로가 있고, 모든 노드에서 출구로 향하는 경로가 존재

Prime Program

• Proper Program이면서, 두개 이상의 노드를 가지는 Proper Subprogram을 분리해낼 수 없는 프로그램
  • A proper program which has no embedded proper subprogram of greater than 1 node
  • cannot cut 2 arcs to extract a prime subprogram in it

Composite Program

• Proper Program이지만 Prime Program은 아닌 프로그램
  • 즉, Proper Subprogram을 분리해낼 수 있는 Proper Program

Prime Decomposition

• 모든 Proper Program은 Prime Program들의 계층으로 분해될 수 있으며, 각각의 분해는 유일(Unique)하다
  • Every proper program can be decomposed into a hierarchical set of prime subprograms
  • This decomposition is unique, except for special case of linear sequence of functional nodes
  • 예외: function node 여러개가 이어져 있는 경우는 분해가 유일하지 않을 수 있다
• 4개 이하의 노드로 표현될 수 있는 가장 기본적인 Prime Program들은 일반적으로 프로그래밍 언어에서 사용되는 제어 구조와 일치함
  • The Prime Decomposition shows that primes up to 4 nodes are the useful programming language control structures.

Issue: Does this limit what programs can be written?

• Proper Program이 좋은 건 알겠는데, 작성 가능한 프로그램의 범위를 제한하는건 아닐까 하는 우려가 있었음
• -> 구조적 프로그램 정리가 해결

Structured Program Theorem

: 순차, 선택, 반복 세 가지 구조만으로 "모든" 계산 가능한 함수를 작성할 수 있다!

이론적으로, 계산 가능한 모든 종류의 프로그램을 작성할 수 있음이 증명됨
: Böhm-Jacopini Theorem (1966) | 구조적 프로그램 정리

• 프로그램: 튜링 머신으로 계산 가능한 함수
• 함수가 계산 가능하다:
  • 그 함수에 대응하는 알고리즘이 존재하며,
  • 그 알고리즘이 유한한 시간 내에 그 함수의 값을 계산할 수 있다

Structured Programming

: 3가지 기본 제어구조(순차, 선택, 반복)만을 사용해 프로그램을 설계!

• 프로그램 설계를 계층적으로
• 문장 순서가 곧 수행 순서가 되도록
  • GOTO에 의존하게 되면:
    • 프로그램 계층 구조를 알아보기 힘들어진다
    • 문장 순서가 수행 순서와 무관해진다
      • spaghetti code를 유발함
        ( 제어 구조가 스파게티처럼 꼬여있어서 이해하기 어려운 코드 )
• 특정 문장 그룹이 여러 용도로 사용될 수 있다
  • 이해하기 어려워짐
• GOTO-less programming

Sequence | Composition | 순차

: 문장(Statement)들이 놓인 순서대로 수행

• 복합문(Compound Statement): 여러 문장을 한 문장처럼 취급
  • begin, end
  • 블럭(Block)
    • 복합문의 일종
    • { stmt1; stmt2; ... }

Selection | Alternation | 선택

: 둘 이상의 문장들 중, 하나만 선택하여 수행

• Single Branch: if expr then stmt1
• Double Branch: if expr then stmt1 else stmt2
• Multiple Selection
  • case statement
    • switch - case
    • case - when
  • Jump Table을 통해 효율적으로 구현할 수 있다!
• Dangling Else Problem
  • else의 짝이 어떤 if인지가 모호해질 수 있다
    • sol 1: 가장 가까운, 짝 없는 if
    • sol 2: endif 구문을 강제

Repetition | Iteration | 반복

: 특정 문장을 0회 이상 반복해서 수행

• Simple Repetition
  • perform stmt K times
• Counter-Controlled Repetition
  • control variable을 활용 (counter)
  • for I := 1 step 2 until 30 do body
• Sentinel-Controlled Repetition
  • 임의의 조건을 검사
  • while condition do body
  • repeat body until condition
• Data-Based Repetition
  • foreach X in container do body
• Infinite Repetition
  • loop body
    • body에서 end loop같은 별도의 탈출 문장을 사용해야함

some notes

• 순차, 선택, 반복 세 가지 제어구조만으로 모든 프로그램을 표현할 수 있다는 것 뿐, 그렇게 표현하는 것이 최선이라는 것은 아님
  • 이론적인 가능성의 증명일 뿐이지, 변환 방법론은 아니다
  • 어떻게 지저분한 코드를 논리적으로 재해석하고 재설계할것인가 하는 문제를 해결해주는 것은 아님
• 또한, 스파게티 코드를 구조적 코드로 바꿀 경우 원래의 코드보다 비효율적이고 이해하기 어려운 코드가 될 수도 있다
• 주어진 상황에 맞는 최고의 알고리즘을 선택하는 것은 결국 프로그래머의 몫이다!

추상화: Hiding the details. 관심 있는 것에 집중!

Abstraction

• Making it Simpler

Encapsulation

• Making them into one Unit

Information Hiding

• Hiding the details

Encapsulation is a language facility,
whereas information hiding is a design principle.

Encapsulation refers to the bundling of data with the methods
that operate on that data.

The primary criteria for system modularization should concern
the hiding of critical design decisions.

ADT

: 추상 자료형(Abstract Data Types)

• Type: Set of Values + Set of Operations
• ADT도 타입이다! 즉, Value Set + Operation Set
  • 하지만 Operation의 구현이 드러나지 않으며,
  • Value의 구현(저장 형태 등)도 드러나지 않는다 (abstract)
• 중요! 데이터 타입을 캡슐화:
  정의된 Operation Set을 제외한 다른 방법으로는 객체를 다룰 수 없도록!!!!!
• ADT 예시:
  • SetName: name * student -> student
  • GetName: student -> name
  • SetCourse: course * student -> student
  • GetCourse: student -> course
  • GetCredits: student -> integer
  • ...
  • 여기서 name, course는 정의되지 않은 또 다른 ADT다!

Information Hiding

• 인터페이스와 무관한 부분은 숨기는 설계 기법
• 위 ADT의 예시에서, student 객체가 어떻게 저장되어야 하는지는 알 수도 없으며, 알 필요도 없다
  • 중요한 것은 연산(Operation)들의 동작 형태(Behavior)다!!
• 정보 은닉은 어떤 언어에서든 구현 가능하다
  • C언어 예시:

typedef struct {
  char *name,
  int salary,
  ...
} Employee;

char *getName(Employee e);
void promotion(Employee e);
...

Algebraic Data Type?

• 해당 데이터타입에 적용 가능한 연산자들 사이에, 특정 대수적 법칙이 만족됨!
• POP(newstack) = newstack
• TOP(newstack) = undefined
• POP( PUSH(S, I) ) = S
  • 원래 상태가 그대로 유지됨 (push 직후 pop)
• TOP( PUSH(S, I) ) = I
  • push 직후 top의 결과는 반드시 방금 push한 element
• ...

Polymorphism

Ad-hoc Polymorphism

: 실제로는 같은 코드지만, 다른 이름으로 사용

• Overloading

Parametric Polymorphism

: 여러 타입에 동일하게 적용될 코드를 타입 인수를 통해 처리

• Generic Programming

Subtype Polymorphism

: Is - A 관계에서, Supertype에 적용 가능한 코드는 Subtype에도 적용 가능하도록

• Inheritance
  • Is - A
  • Has - A

Generic Data Type

• Generic Type?
  • "타입"을 인수로 받는 "타입"
  • 뒤쪽의 타입은, 앞쪽의 타입을 통해 생성된 타입
  • 타입 인수(argument, parameter)를 통해 Parametric Polymorphism을 형성
• Instantiation of Generic Type
  • Generic Type에 타입 인수를 전달함으로써 새로운 타입을 만드는 것
• 구현?
  • 타입 인수(파라미터)는 컴파일 타임에 결정된다
  • 따라서, 컴파일 타임에 일반 타입과 동일하게 구현할 수 있다
    • ex: Instantiation of a class template

Inheritance

• 일반적인 의미의 Inheritance?
  • 한 프로그램 요소의 특징이 다른 프로그램 요소로 전달되는 것
  • nested block에서, 감싸고 있는 블럭의 변수를 내부 블럭에서 볼 수 있는것도 inheritance의 일종이라고 보는 시각도 있다
• ADT 관점의 Inheritance
  • 한 ADT를 보다 구체화하여 새로운 ADT를 만드는 것
  • Superclass - Subclass 관계를 형성함 (Subtype 관계)
  • Subclass는 Superclass의 모든 속성을 상속받음!!
• 구현 예시
  • Ada의 tagged class, C++의 derived class, Java의 subclass

Inheritance Implementation Issues

• 다중 상속(Multiple Inheritance)
  • 여러 Superclass를 가질 수 있나?
  • 다이아몬드 상속(Diamond Inheritance) 문제
    • 다이아몬드 상속 구조에서는, 동일한 Base Class를 여럿 가지게 되는 문제가 발생할 수 있다
    • -> virtual class를 사용(Pure Interface)
• 런타임 메서드 바인딩 (Dynamic Invocation of Methods)
  • 메서드는 객체에 따라 호출되어야 한다!
  • 메시지를 수신하는 실제 객체의 종류에 따라 메서드가 달라져야 함
  • -> C++의 경우, virtual function을 활용 (vtable, vptr)

프로그램이란?

: 프로그램 == 알고리즘(Algorithms) + 자료구조(Data Structures)

프로그래밍?

1. 내가 해결할 문제의 해결 방법이 해당 언어에서 제공된다면, 그걸로 충분하다 (잘 활용하기)
2. 그렇지 않다면 뭔가 만들어야 함

• Encapsulation: Data와 Operation을 하나의 묶음(Capsule)으로 묶을 수 있는 장치, 방법

Four Basic Mechanisms

• Structured Data: 복합 데이터를 만들 수 있는 기능
• Subprograms: 새로운 연산을 정의할 수 있는 기능(함수 또한 연산으로 볼 수 있다)
• Type Declarations: 특정 부류의 데이터와, 이와 관련된 연산을 하나로 묶어 새로운 데이터 타입을 저으이할 수 있는 기능
• Inheritance: 기존 데이터타입의 기능을 모두 포함하며 더욱 확장된 데이터 타입을 생성할 수 있는 기능

Structured Data + Subprogram 은 필수 기능,
Type Declaration + Inheritance 는 고급 기능으로 본다 (optional)

Data Structure(Structured Data)

• 다른 데이터 객체를 원소(Elements)나 요소(Components)로 가지는 데이터 객체
• 배열(Array), 레코드(Record or Structure), 스택(Stack), 리스트(List) 등

Specification of Data Structure Types

• 원소의 개수
  • 고정 크기(Fixed Size): Array, Record
  • 가변 크기(Variable Size): List, Set, Tables, Files
    • 언어에 따라 가변 크기 배열(Array)이 가능할 수 있음
• 원소의 타입
  • 동형 구조(Homogeneous Structure): Array, Set
  • 이형 구조(Heterogeneous Structure): Record, List
    • 언어에 따라 List의 원소를 동형으로 제한하기도 함
• 원소 선택 방법
  • 임의 선택(Random Selection): 임의의 순서로 선택
  • 순차 선택(Sequential Selection): 정해진 순서에 따라 선택
• 최대 원소 개수
  • 가변 크기 구조의 경우에도, 최대 원소 개수가 지정될 수 있음

Operations on Data Structures

• 원소 선택(Component Selection): 임의 선택, 순차 선택
• 전체 구조에 대한 연산(Whole-Structure Operation)
  • Assignments, Union of Sets, Transpose of a Matrix, ...
• 원소의 삽입 및 삭제(Insertion and Deletion of Components)
• 데이터 구조의 생성 및 소멸(Construction and Destruction of Data Structures)

Implementation of Data Structures

• 저장공간의 형태(Storage Representation)
  • 연속된 형태(Sequential Representation, Continuous Block)
  • 연결된 형태(Linked Representation)
• 연산의 구현(Implementations of Operations)
  • 연속된 형태일 경우 Selection: Base Address + Offset
  • 연결된 형태일 경우 Selection: Head Address + Following Links
• 저장공간 관리
  • 객체의 지속시간(Lifetime) 관리
  • Lifetime: Storage Binding이 유지되는 시간.
    즉, 해당 객체의 공간이 존재하는 시간

Problems in Storage Management

• Garbage Object
  • 참조 경로(Access Path)를 잃어버린 객체
  • 객체의 할당 해제(Deallocation)가 너무 늦음
  • Dangling Object라고도 부름
  • 위험하지는 않지만, 공간이 낭비됨 <- 메모리 누수(Memory Leak)
• Dangling Reference
  • 이미 할당이 해제된 객체를 가리키는 참조 경로
  • 객체의 할당 해제가 너무 빠름
  • 굉장히 위험하다!!! <- 다른 용도의 공간을 훼손할 수 있음

Type Checking for Data Structures

• C언어 선언문 예시:
  float a[20];
  • 배열이군
  • 1차원 배열
  • 요소의 개수는 20개
  • 인덱스는 0번부터 19번까지 사용 가능
  • 각각의 원소들의 타입은 float
• Structured Type의 타입 검사를 복잡하게 하는 요인?
  • Selector를 통해 선택한 원소가 실제로 존재하는지를 검사해야 함
    • 배열의 경우, 첨자 범위에 대한 검사 필요
  • 선택된 원소의 타입도 다시 고려해야 함 (?)

Array (배열)

: 같은 타입의 유한한 개체들이 일렬로 나열된 것, Homogeneous Aggregation

• Attributes of a Array:
  • 원소의 개수(Number of Components)
  • 원소의 타입(Type of Each Components)
  • 첨자(Subscript): 통상적으로 자연수이지만, 임의의 enumeration일 수 있다
    • Pascal: V: array [-5 .. 5] of real;
    • type class = (Fresh, Soph, Junior, Senior)
    • var ClassAverage: array [class] of real;
• Array Operations
  • 원소 선택(Selector): 일반적으로 첨자 연산[]으로 처리
  • 원소 갱신(Modifier): 역시 일반적으로 첨자 연산으로 처리
  • 원소 삽입 및 삭제: Variable Size Array일 경우에만 허용됨
• Whole Array Operations
  • 크기(Size)
  • 배열 대입(Array Assignment)
  • 내적(Inner Product)
  • 외적(Outer Product)
• Whole Array Operations의 문제점?
  : 중간 결과(Array일 수 있음)를 저장할 별도의 공간이 필요
• Array Implementation
  • 일차원 배열의 경우:
  • 참조 공식(Accessing Formula)
    • 배열에 할당된 첫 번째 원소의 주소가 a, 원소의 크기가 E일 때
    • i번째 원소의 주소(lvalue) A[i]
    • = a + (I-LB) * E
    • = (a - LB * E) + I * E
    • = VO + I * E
  • VO(Virtual Origin)은 컴파일 타임에 정적으로(statically) 결정될 수 있다
  • + 참조가 올바른지를 검사하기 위해서는, 배열의 UB(Upper Bound)도 알아야 한다!
  • Dope Vector
    • (VO, LB, UB, E) 정보를 가지고 있음 - E는 각각의 원소가 차지하는 메모리 크기
    • 이녀석 덕분에 배열 접근이 빠르게 이루어질 수 있는 것
• Two-Dimensional Array
  • Row-Major: 행들의 1차원 배열
  • Column-Major: 열들의 1차원 배열
  • 일반적으로 2차원 배열의 경우 row-major 방식으로 구현하지만, FORTRAN은 column-major 방식으로 구현됨
  • C언어에는 2차원 배열이 없음! 배열의 배열로 다차원 배열을 지원함
  • 이차원 배열의 참조 공식(Accessing Formula):
    • 배열에 할당된 첫 번째 원소의 주소가 a, 원소의 크기가 E, 한 행의 크기가 S일 때
    • [i][j]번째 원소의 주소(lvalue) A[i][j]
    • = a + (I-LB1) * S + (J-LB2) * E
    • = (a - LB1 * S - LB2 * E) + I * S + J * E
    • = VO + I * S + J * E
      결국 Virtual Origin + (해당 인덱스 이전 원소의 개수 * 원소의 메모리 크기)
• Slice
  • 그 자체가 또다른 배열이 되는 배열의 하위 구조(substructure)

1 2 3
4 5 6
7 8 9

---

(1:4, 2) -> [2, 5, 8, 11]
(3, 1:3) -> [7, 8, 9]

Associative Array

: 연관 배열, 이름을 첨자로 사용하는 배열

• (key, value)로 이루어진 참조 표로 볼 수도 있다
• lookup table 또는 dictionary 라고도 부른다
• 연산들:
  • 첨가(Add): 새로운 (key, value)를 추가
  • 변경(Reassign): 기존 key의 value를 변경
  • 삭제(Remove): 기존 (key, value)를 삭제
  • 참조(lookup): 특정 key의 value를 참조

Record

: (일반적으로) 서로 다른 타입의 원소들을 하나로 묶은 것

• Heterogeneous Aggregation
• 속성:
  • 원소의 개수(Number of Components)
  • 원소의 타입(Type of Each Component)
  • 원소 선택자(Selector for Each Component)
• 연산:
  • Move Corresponding
  • ex) MOVE CORRESPONDING INPUTSEC TO EMPLOYEE
• C언어에서는 Structure (via struct)
  • 필드명이 Selector
  • Tag와 Type을 구분함

typedef struct _A { // 이 `_A`는 Tag
  int x;
  int y;
} A; // 이 `A`는 Type (typedef를 통해 `struct _A`에 대한 별칭을 만들어준것)

Variant Record

: 여러 다른 타입 중 하나가 올 수 있지만, 한 번에 하나의 타입만을 가지는 구조

• 모든 필드가 동일한 주소(L-value)를 공유함
  • 즉, 한 번에 하나의 값만을 저장할 수 있다
• 단순히 공간(메모리) 효율성을 위해 존재하는 타입!
• 속성 및 연산은 Record와 동일하다
• 타입 검사를 어렵게 만든다
  • 동적으로 타입 검사를 수행하거나
  • 타입을 아예 검사하지 않기도 한다
• 구분자(Discriminator) 존재 유무에 따라 구분됨:
  • free-union (non-discriminated variant record)
  • discriminated-union (discriminated variant record)
• C언어에서는 Union

typedef union {
  int x;
  float y;
  char Z[4];
} U;

U.x = 142;
printf("%d\n", U.Z[3]); // 컴파일 타임에 타입 검사를 할 수 없다는 문제점이 있다!

List

: 순차 목록(Ordered Sequence of Elements)

• 배열과의 차이점:
  • 고정 길이가 아니다
  • 동형 원소가 아닐 수 있다 (하지만 언어에 따라 동형 원소로 제한하기도 함)
  • 암시적 선언을 사용하는 경우가 많다. 별도의 선언 없이 리스트를 생성(?)
• 연산:
  • nil: 빈 리스트 생성
  • cons: 리스트에 특정 원소를 덧붙임
  • head: 리스트의 첫 번째 원소 (LISP의 CAR)
  • tail: 리스트의 첫 번째 요소를 제외한 나머지 원소 (LISP의 CDR)
• 리스트의 원소로 다른 리스트를 포함할 수 있는 리스트를 Generalized List라 부른다
  • 사실상 Tree인 셈!
• Stack, Queue, Tree, Property List(원소의 개수가 가변인 레코드) 등은 List의 변형

Set

: 서로 다른 값들의 모음 (Unordered Collection of Distinct Elements)

• 연산:
  • 원소 검사(Membership)
  • 원소 추가(Insertion), 원소 삭제(Deletion)
• 합집합(Union), 교집합(Intersection), 차집합(Difference)
• 구현 방식:
  • Bitmap of Enumerations
    • 집합의 크기가 제한됨
  • Hashing
    • 충돌(Collision) 해결이 필요함
      • Rehashing
      • Sequential Scan
      • Bucketing

Executable Data Object

: 데이터로 표현된 부프로그램

• 프로그램을 데이터 객체로 나타냄
  • 일반적으로 프로그램과 데이터는 구분하지만, 구별하지 않는 언어도 있다
• 함수형 언어에서는 자연스럽다!
• scheme

(define (double1 x) (+ x x))
(define double2 (lambda (x) (+ x x)))
;; lambda 부프로그램 객체를 double2 변수에 대입

• haskell

addOne = \x -> x + 1

Data

• 처리 대상
• 숫자, 문자, 복합 데이터, 메타 데이터(ex: 포인터)

Data Object

OOP에서의 객체(Object)와는 다른 개념이다!

• 데이터 값을 포함하는 container 또는 memory location
• 일반적으로 변수(Variable)라 부름
• 6가지 기본 속성을 가짐
  • type, name, value(R-value), address(L-value), lifetime, scope
  • 다른 Data Object를 가리키는 pointer value를 특별히 Component라 부르기도 한다
    (value, 즉 R-value 속성의 일종)

Constants

• 상수(Constant)도 변수의 일종
• 하지만 반드시 초기화(value binding)되어야 함
• 또한, 한번 초기화 된 다음에는 값이 변경될 수 없음
• 상수의 종류:
  • literal: 생긴 것 자체가 이름이자 값
  • named constant: 값 외에 별도의 이름이 존재하는 상수
    • manifest constant: 컴파일 타임에 정적으로 값이 바인딩되는 named constant

Data Value

• 특정한 값을 나타내는 비트 패턴
• int a = 3;
  -> 메모리에 저장되는 비트패턴은 00000000000000000000000000000011

Type

• 데이터를 분류해둔 것
• 타입(Type) : 값(Value)의 집합 + 연산(Operation)의 집합
  • The value that data objects of that type may have (값 집합)
  • The operations that define the possible manipulations of data objects of that type (연산의 집합)
• -> ADT

Data Type Specification

• 이상적으로는, 모든 데이터 타입에 대해 명확한 명세(specification)가 주어져야 한다
  • 허용 가능한 값의 범위 + 적용 가능한 연산의 목록
  • 사용자 정의 타입(User-defined Type)도 마찬가지!!
• 타입의 연산 정의를 어렵게 만드는 요인들:
  • 특정 입력에 대해서는 정의되지 않을 수 있음(UB, Undefined Behavior)
    • ex: array out-of bounds
  • 기본적으로, 암시적으로 주어지는 인수(Implicit Arguments)가 있을 수 있음
  • 부작용(Side Effect)
  • 자기 수정(Self-Modification)

Subtype

• 어떤 타입의 값 집합의 일부를 취하는 새로운 타입
• A is subtype of B if every value of A is a value of B
• 반대로, B는 A의 supertype 이라 부른다!
• Subtype 개념이 클래스로 확장된 경우를 상속(Inheritance)이라 부른다!!

Declaration

• 선언문이란?
  • 언어 처리기(컴파일러 또는 인터프리터)에 데이터 객체의 이름과 타입 정보를 전달하는 문장(Statement)
  • 선언문은 수행된다고 하지 않고, Elaboration된다고 부름!!
  • 선언문의 위치와 종류에 따라, 데이터 객체의 영역(Scope)과 지속시간(Lifetime)이 결정됨!
• 선언문의 종류
  • 대부분의 언어에서는 명시적 선언문을 사용
  • 일부 고전 언어에서는 암시적 선언문을 사용
    • FORTRAN에서 { I, J, K, L, M, N } 으로 시작하는 변수는 암시적으로 정수형
    • Perl의 경우: $(스칼라), @(배열), %(연관 배열, dictionary)
• 변수 대신, 함수를 선언할 수도 있다!
  • ex: C언어의 function prototype
    • float sub(int x, float y);
• 선언문의 역할:
  • 저장 형태 결정(Choice of Storage Representations)
  • 메모리 관리(Storage Management)
  • 타입검사(Type Checking)
  • 다형 연산 지원(Polymorphic Operations)

타입, 타입 검사, 타입 추론, 타입 변환(explicit, implicit), 할당, Lvalue, Rvalue, scala assignment(value copy), pointer assignment(pointer copy)

+ lifetime, scope, scope hole(shadowing), allocation 분류(static, dynamic{automatic allocation, manual allocation}, 타입 안전성(타입, 타입 검사 사이에 쓰기), granularity of typing{strongly typed, weakly typed, typeless}, type checking time{static type checking, dynamic type checking} - strongly typed라고 반드시 static type checking을 하는 것은 아님, Equality{data equality, type equivalence}, name equivalence, parameterized type(type을 parameter로 허용)

• 6-2 강의자료, 필기 참고해서 정리하기

scala data, composite data, Numeric data, Integer, Floating-point Real Number(IEEE 754), Fixed-point Real Number, Enmueration, Boolean, Character, // Character String(composite data), // Pointer // File, I/O(Psudo-file, input stream, output stream, error stream)

촘스키 계층 (Chomsky Hierarchy)

• 형식 언어를 분류하는 4계층으로 나뉨. Type 0이 가장 복잡한 언어, Type 3가 가장 간단한 언어

Type 3 - 정규 문법 (Regular Grammar)

: 가장 간단한 언어. 아주 기본적인 패턴만을 표현할 수 있다

• FSA (Finite State Automata)로 인식 가능
• 예시: 0과 1로 구성됐는데, 1로 끝나는 문자열을 생성할 수 있다. transition의 끝이 1인지만 확인하면 되므로, 메모리가 없는 FSA만으로 인식 가능

Type 2 - 문맥 자유 문법 (Context-Free Grammar)

: 문맥을 신경쓰지 않는 간단한 규칙으로 만든 언어. 프로그래밍 언어의 문법을 정의할 때 많이 사용된다

• PDA (Pushdown Automata)로 인식 가능 (스택 == pushdown list)
• 예시: 괄호가 잘 닫혀 있는 문자열을 생성할 수 있다. 스택만으로 처리할 수 있으므로, 주변 문맥에 대한 정보가 없어도 PDA로 인식 가능

Type 1 - 문맥 민감 문법 (Context-sensitive Grammar)

: 문장에서 단어를 바꿀 때, 앞에 뭐가 있는지를 따지는 언어. 문맥에 따라 규칙이 달라진다

• LBA (Linear Bounded Automata)로 인식 가능
• 예시: a가 3개, b가 3개, c가 3개 있는 문자열을 생성할 수 있다.

Type 0 - 무제한 문법 (Unrestricted Grammar)

: 어떤 문자열이든 만들어 낼 수 있음. 문법 인식을 위해 튜링 머신 필요

Types of Automata

Finite-State Automaton

• 단방향 읽기만 가능

Pushdown Automaton

• 별도의 Pushdown List (Stack)을 가지고 있음

Linear-Bounded Automaton

• Read/Write Head를 가지고 있음

Turing Machine

• 읽고 쓸 수 있는 무한 길이의 테이프와 유한 제어로 구성된 형식 모델
• 인간의 계산을 흉내낸 기계

Church's Thesis

: 정리(Theorem)가 아니라 추론(Conjunction)이다!

• Any Computable Function can be computed by a Turing Machine
• 튜링 완전(Turing-Complete):
  • A가 튜링 완전하다는 말은, A의 계산 능력이 튜링 머신과 같다는 뜻
  • 컴퓨터로 계산이 가능하다는 의미로 받아들여짐

Decidability

• Undecidable Problem?
  • 튜링 머신으로 일반해(General Algorithm)를 찾을 수 없는 문제
  • 시간 제한 및 공간 제한은 없음(?)
• Halting Problem
  • Undecidable Problem의 대표적인 예
  • 주어진 튜링 머신과 입력에 대해, 해당 튜링 머신이 멈출 것인가를 결정하는 문제

Language Semantics

Grammatical Model

• 속성 문법(Attribute Grammar): 문법의 각 기호에 속성을 부여하고, 속성 값을 구하는 것으로 의미를 표현
  • Grammar + Evaluation Rules
  • 문법 기호(Grammar Symbol : terminal 또는 non-terminal)에 속성을 부여
  • 속성을 부여하는 규칙을 문법과 함께 제시

Operational Model

• 기능적 의미론(Operational Semantics): 가상 기계 상에서 프로그램의 동작을 보임
• 실제 컴퓨터와 유사한 가상기계의 동작을 통해 프로그램 의미를 표현
• 가상 기계?
  • State: memory, register, I/O device에 대한 추상화
  • State Transition Mechanism: processor에 대한 추상화

Applicative Model

• 표기적 의미론(Denotational Semantics): 각 프로그램이 나타내는 함수(Denotation)가 해당 프로그램의 의미라고 파악
• 의미 함수(Semantic Function)
  • 의미 영역(Semantic Domain)의 값을 다루는 함수
  • 표기적 의미론은 구문에 해당하는 의미영역의 값을 반환하는 의미함수들로 구성됨

Axiomatic Model

• 공리적 의미론(Axiomatic Semantics): 프로그램 수행 전과 수행 후의 술어 변화가 프로그램 명세와 일치하는지를 증명(Verification)
• 프로그램 요소에 대한 사전 조건(Precondition)과 사후 조건(Postcondition)을 통해 프로그램의 의미를 파악
  • {P} program {Q}
    • P: 프로그램 수행 전의 조건(Assertion)
    • Q: 프로그램 수행 후의 조건
    • 사전조건은 input specification으로, 사후조건은 output specification으로 간주할 수 있다!

Specification Model

• 어떤 데이터에 대한 여러 함수의 관계를 입증하고(Specification), 구현 내용이 이것과 동일함을 입증(Algebraic Data Type)

Axiomatic System for Program Verification

• 공리(Axiom):
  • 조건 없이 참이라고 전제된 어떤 명제
  • The assertions that are considered to be correct
  • 가정과 결론의 형태를 갖는 axiom을 특별히 rule이라 부르기도 함
• Axiomatic System
  • 정리를 유도할 수 있는 임의의 공리 집합
  • Any set of axioms from which some theorems may be derived

Weakest Precondition

• 주어진 사후조건에 대해, 가장 제약이 덜 한 사전조건
  • 만약 Weakest precondition이 프로그램의 input spec.으로부터 추론되고,
    프로그램의 사후조건이 원하는 output의 spec.이라면:
  • 올바른 프로그램이며, 프로그램이 의도대로 잘 동작한다는 의미!
• wp(P, Q) : 프로그램 P를 수행한 후, Q 조건을 만족하기 위한 weakest precondition
  • {wp(P, Q)} program {Q}

Assignment Axiom

{Q[E/x]} x := E {Q}

• Q[E/x]: Q에서 자유변수 x를 모두 E로 치환한 것
• 적용 예시:
  • {P} a := b/2 – 1 {a < 10}
  • wp(a := b/2 – 1, a < 10)
  • = (a < 10)[(b/2 – 1) / a]
  • = (b/2-1) < 10
  • = b/2 < 11
  • = b < 22

The Rule of Consequence

• Weakening the Postcondition
  • {P} S {Q}, Q ⇒ R
  • 사후조건을 약화할 수 있다: {P} S {R}
• Strengthen the Precondition
  • R ⇒ P, {P} S {Q}
  • 사전조건을 강화할 수 있다: {R} S {Q}

The Rule of Composition

{P} S1 {Q}, {Q} S2 {R} 일 때, {P} S1 ; S2 {R}

• 명제의 사후조건과 다른 명제의 사전조건이 겹칠 경우, 합칠 수 있다
• 적용 예시:
  • {P} y := 3 * x + 1 , x := y + 3 {x < 10}
  • 두번째 명제의 wp(x := y + 3, x < 10)를 Q라 하면
  • P = wp(y := 3 * x + 1, Q)

The Rule of Selection

{P ∧ B} S1 {Q}, {P ∧ ￢B} S2 {Q} 와 {P} if B then S1 else S2 {Q} 는 동등

• 적용 예시:
  • {P} if (x > 0) then y := y – 1 else y := y + 1 {y > 0}
  • wp(y := y – 1, y > 0) = y > 1
  • wp(y := y + 1, y > 0) = y > -1
  • (y > 1) ∧ (x > 0) ⇒ (y > 1)
  • (y > -1) ∧ (x ≤ 0) ⇒ (y > -1) ⇒ (y > 1)
  • 따라서, P = (y > 1)
  • (y > 1 ∧ x > 0) y = y – 1 (y > 0)
  • (y > 1 ∧ x ≤ 0) y = y + 1 (y > 2) ⇒ (y > 0)

The Rule of Iteration

{I ∧ B} S {I} 와 {I} while B do S {I ∧ ￢B} 는 동등

• 이때 I는 Loop Invariant!
  • 반복문 수행 전에 True
  • 반복문 수행 중에도 True
  • 반복문 수행 후에도 True
• 반복문의 WP를 찾기 위해서는 I(Loop Invariant)를 먼저 찾아야 한다
  • 어떻게? 추측 (Guess the Loop Invariant)
  • ...

• Program Verification 과정은 언어 설계에도 영향을 줌!!
  • aliasing처럼 프로그램의 증명을 어렵게 만드는 기능을 자제
  • assertion 기능의 필요성: 프로그램 중간에 만족해야 할 조건을 검사

서론

자바/스프링 공부를 하면서 IntelliJ IDEA 를 자주 사용하다 보니 편리한 단축키를 많이 익혔다. 그중 Shift Shift 단축키가 특히 마음에 들었는데, 유용함도 유용함이지만 같은 키를 두 번 누르는 단축키가 재밌어서 자주 사용하다 보니 금방 익숙해질 수 있었다.

단축키 인식을 못해요

VS Code에서도 검색에 같은 단축키를 쓰고 싶다는 생각이 들어 키보드 단축키 목록을 열어봤는데, 아쉽게도 Intellij처럼 파일명과 파일 내부 코드를 동시에 검색할 수 있는 방법은 아직 없는 것 같았다. 다양한 검색 관련 기능들 중 내가 찾던 기능은 다음과 같다:

• 디렉토리 내 모든 파일 내부를 검색하고, 해당 라인으로 이동: Search: Find in Files
• 디렉토리 내 파일명을 검색하고, 해당 파일로 이동: Go to File...

첫번째 기능인 Find in Files의 경우 기본적으로 Shift + Command + F에 바인딩 되어 있다. 여기서 Shift가 빠진 Command + F 단축키는 현재 화면, 즉 현재 열려있는 에디터에서 검색하도록 동작하는 것이 직관적이므로 디렉토리 내 모든 파일에서 검색하려면 Shift를 같이 눌러준다고 기억하면 될 것 같다.

그래서 첫번째 기능의 단축키는 그대로 두고 Command + P라는 근본 없는 단축키에 바인딩돼있는 Go to File... 기능의 단축키를 Shift Shift로 변경하려 했더니, Shift Shift와 같이 동일한 키를 두 번 누르는 단축키는 누르는 속도와 상관 없이 인식하지 못하는 것만 같았다..

분명 나랑 비슷한 생각을 했던 사람이 있을 것 같아 인터넷에 검색을 해 보니 10년도 넘은 스택 오버플로우 질문글을 찾을 수 있었고, 2021년에 릴리즈된 VS Code 1.54.0 버전부터 Shift Shift같은 단축키를 사용할 수 있게 됐다는 답변을 봤다. 하지만 4년이 지난 지금까지도 UI에서는 동일한 키를 반복 입력하는 단축키를 적용할 수 없어서, 약간의 수고로움을 감수해야 했다.

Shift Shift 검색 단축키 적용 방법

키보드 단축키 설정 화면에서 Open Keyboard Shortcuts (JSON)을 클릭하면 keybindings.json 파일을 직접 수정할 수 있다.

이 파일은 key, command, when 형식으로 구성된 JSON 파일이며 다음과 같은 Element 구조를 가진다:

• key : 단축키가 들어간다. UI에서는 설정이 불가능하던 Shift Shift 같은 단축키도 매핑시켜줄 수 있다.
• command : 단축키를 통해 실행할 명령이 들어간다. 새로운 단축키를 추가하려면 그냥 작성하고, 기존 단축키를 제거하려면 value 앞에 -를 붙여준다.
• when (optional) : 단축키를 인식하기 위한 상황, 조건이 들어간다.

기존 단축키인 Command + P를 삭제하고, Go to File 기능을 Shift Shift 단축키에 매핑시켜 주기 위해 keybindings.json 파일 하단에 아래 두 Elements를 추가해주면 된다:

    {
      "key": "shift shift",
      "command": "workbench.action.quickOpen"
    },
    {
      "key": "cmd+p",
      "command": "-workbench.action.quickOpen"
    },

파일을 저장한 다음 다시 단축키 패널을 열어보니 키바인딩이 Shift Shift로 변경되어 있으며, 정상적으로 동작하는 것을 확인할 수 있었다:

다른 단축키 수정

단축키 수정하는 방법을 알아본 김에, 다른 단축키들도 취향에 맞게 변경해봤다.

명령 패널

Control Control 단축키로 명령 패널을 열기 위해, keybindings.json 파일 하단에 아래 두 Elements를 추가해주면 된다:

    {
      "key": "ctrl ctrl",
      "command": "workbench.action.showCommands"
    },
    {
      "key": "f1",
      "command": "-workbench.action.showCommands"
    },

탭 전환 단축키 정상화

VS Code에서는 Control + Tab, Control + Shift + Tab 두 단축키가 뭔가 불편한 느낌이 들 때가 있어서 탭이 여러 개 열려있을땐 마우스/트랙패드를 통해 탭을 전환하곤 했다. 두 단축키가 브라우저처럼 한 칸씩 이동하는게 아니라 최근에 사용한 순서 대로 이동하기 때문이었다는 것을 알게 됐고, 이 또한 같이 수정해줬다:

• Control + Tab을 누르면 오른쪽 탭으로 한 칸 이동하도록 수정
• Control + Shift + Tab을 누르면 왼쪽 탭으로 한 칸 이동하도록 수정
• 기존 Control + Tab 단축키의 기능을 Command + E에 매핑
• 기존 Control + Shift + Tab 단축키의 기능을 Command + Shift + E에 매핑

    {
      "key": "cmd+e",
      "command": "-actions.findWithSelection"
    },
    {
      "key": "ctrl+tab",
      "command": "-workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup",
      "when": "!activeEditorGroupEmpty"
    },
    {
      "key": "ctrl+tab",
      "command": "-workbench.action.quickOpenNavigateNextInEditorPicker",
      "when": "inEditorsPicker && inQuickOpen"
    },
    {
      "key": "cmd+e",
      "command": "workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup",
      "when": "!activeEditorGroupEmpty"
    },
    {
      "key": "cmd+e",
      "command": "workbench.action.quickOpenNavigateNextInEditorPicker",
      "when": "inEditorsPicker && inQuickOpen"
    },
    {
      "key": "ctrl+shift+tab",
      "command": "-workbench.action.quickOpenNavigatePreviousInEditorPicker",
      "when": "inEditorsPicker && inQuickOpen"
    },
    {
      "key": "ctrl+shift+tab",
      "command": "-workbench.action.quickOpenLeastRecentlyUsedEditorInGroup",
      "when": "!activeEditorGroupEmpty"
    },
    {
      "key": "shift+cmd+e",
      "command": "workbench.action.quickOpenLeastRecentlyUsedEditorInGroup",
      "when": "!activeEditorGroupEmpty"
    },
    {
      "key": "shift+cmd+e",
      "command": "workbench.action.quickOpenNavigatePreviousInEditorPicker",
      "when": "inEditorsPicker && inQuickOpen"
    },
    {
        "key": "ctrl+tab",
        "command": "workbench.action.nextEditorInGroup"
    },
    {
        "key": "ctrl+shift+tab",
        "command": "workbench.action.previousEditorInGroup"
    },

Explorer 토글

Command + 1 단축키로 파일 익스플로러를 열고 닫을 수 있는 설정이다. 전부터 사용하던 단축키 설정인데, 함께 기록해두려 한다:

• 사이드바가 닫힌 상태에서 Command + 1을 누르면 사이드바의 익스플로러가 열림
• 사이드바가 열려 있으며 익스플로러가 아닌 다른 탭일 경우 Command + 1을 누르면 익스플로러로 이동
• 사이드바가 열려 있으며 익스플로러 탭일 경우, Command + 1을 누르면 사이드바를 닫음 (토글)

    {
      "key": "shift+cmd+e",
      "command": "-workbench.view.explorer",
      "when": "viewContainer.workbench.view.explorer.enabled"
    },
    {
        "key": "cmd+1",
        "command": "-workbench.action.focusFirstEditorGroup"
    },
    {
        "key": "cmd+1",
        "command": "workbench.view.explorer",
        "when": "viewContainer.workbench.view.explorer.enabled"
    },
    {
        "key": "cmd+1",
        "command": "workbench.action.closeSidebar",
        "when": "filesExplorerFocus"
    },

keybindings.json 전체 코드

// Place your key bindings in this file to override the defaultsauto[]
[
  {
    "key": "shift+cmd+e",
    "command": "-workbench.view.explorer",
    "when": "viewContainer.workbench.view.explorer.enabled"
  },
  {
    "key": "cmd+1",
    "command": "-workbench.action.focusFirstEditorGroup"
  },
  {
    "key": "cmd+1",
    "command": "workbench.view.explorer",
    "when": "viewContainer.workbench.view.explorer.enabled"
  },
  {
    "key": "cmd+1",
    "command": "workbench.action.closeSidebar",
    "when": "filesExplorerFocus"
  }, // `Command + 1`로 Explorer 윈도우 토글
  {
    "key": "ctrl+alt+n",
    "command": "-code-runner.run"
  },
  {
    "key": "ctrl+r",
    "command": "-workbench.action.openRecent"
  },
  {
    "key": "ctrl+r",
    "command": "code-runner.run"
  }, // `Control + R`로 Code Runner 익스텐션 실행 (Run Code)
  {
    "key": "escape",
    "command": "search.action.clearSearchResults",
    "when": "searchViewletFocus"
  }, // `Command + Shift + F` 검색 콘솔에서 `ESC`를 통해 검색 창 입력 초기화
  {
    "key": "cmd+p",
    "command": "-workbench.action.quickOpen"
  },
  {
    "key": "shift shift",
    "command": "workbench.action.quickOpen"
  }, // `Shift Shift`로 검색 창 열기
  {
    "key": "ctrl ctrl",
    "command": "workbench.action.showCommands"
  }, // `Control Control`로도 명령 창을 열 수 있도록 단축키 오버로딩 (기본값은 F1)
  {
    "key": "ctrl+tab",
    "command": "-workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup",
    "when": "!activeEditorGroupEmpty"
  },
  {
    "key": "ctrl+tab",
    "command": "-workbench.action.quickOpenNavigateNextInEditorPicker",
    "when": "inEditorsPicker && inQuickOpen"
  },
  {
    "key": "ctrl+tab",
    "command": "workbench.action.nextEditorInGroup"
  }, // `Control + Tab`이 브라우저처럼 동작하도록 변경 (다음 탭으로 이동)
  {
    "key": "ctrl+shift+tab",
    "command": "-workbench.action.quickOpenNavigatePreviousInEditorPicker",
    "when": "inEditorsPicker && inQuickOpen"
  },
  {
    "key": "ctrl+shift+tab",
    "command": "-workbench.action.quickOpenLeastRecentlyUsedEditorInGroup",
    "when": "!activeEditorGroupEmpty"
  },
  {
    "key": "ctrl+shift+tab",
    "command": "workbench.action.previousEditorInGroup"
  }, // `Control + Shift + Tab`이 브라우저처럼 동작하도록 변경 (이전 탭으로 이동)
  {
    "key": "cmd+e",
    "command": "-actions.findWithSelection"
  },
  {
    "key": "cmd+e",
    "command": "workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup",
    "when": "!activeEditorGroupEmpty"
  },
  {
    "key": "cmd+e",
    "command": "workbench.action.quickOpenNavigateNextInEditorPicker",
    "when": "inEditorsPicker && inQuickOpen"
  }, // 기존 `Control + Tab` 기능을 `Command + E`로 이동 (최근 탭으로 이동)
  {
    "key": "shift+cmd+e",
    "command": "workbench.action.quickOpenLeastRecentlyUsedEditorInGroup",
    "when": "!activeEditorGroupEmpty"
  },
  {
    "key": "shift+cmd+e",
    "command": "workbench.action.quickOpenNavigatePreviousInEditorPicker",
    "when": "inEditorsPicker && inQuickOpen"
  }, // 기존 `Control + Shift + Tab` 기능을 `Command + Shift + E`로 이동 (최근 탭 역순으로 이동)
  {
    "key": "ctrl+[Backquote]",
    "command": "workbench.action.terminal.toggleTerminal",
    "when": "terminal.active"
  }, // 한글 키보드일 때도 터미널 토글 단축키가 동작할 수 있도록 단축키 오버로딩 (기본값은 Control + `)
  // 250617
]

• Better late than never
• There's no silver bullet
• Comparison is the thief of joy

인용구 - Quotes

• Where there's a will, there's a way
  • George Herbert ( To him that will, ways are not wanting )
• The only constant in life is change
  • Heraclitus ( There is nothing constant, except change )
• Time flies, but you're the pilot
  • Michael Altshuler ( The bad news is time flies. The good news is you’re the pilot )
• Eternal vigilance is the price of liberty
  • Wendell Phillips
• The future is already here, it's just not very evenly distributed yet
  • William Gibson
• There is no such thing as tomorrow
  There never will be, because time is always now
  • Alan Watts
• There is nothing noble in being superior to your fellow men
  True nobility lies in being superior to your former self
  • Ernest Hemingway
• Anything worth having is worth fighting for
  • Susan Elizabeth Phillips
• To get what you want, you have to deserve what you want
  • Charles Munger
• People think that computer science is the art of geniuses
  but the actual reality is the opposite,
  just many people doing things that build on each other,
  like a wall of mini stones
  • Donald Knuth
• Life begins at the end of your comfort zone
  • Neale Donald Walsch
• The only true test of intelligence is if you get what you want out of life
  • Naval Ravikant

가사 - Lyrics

• The greats weren't great because at birth they could paint
  The greats were great because they paint a lot
• A life lived for art is never a life wasted

etc.

• Procrastination is often rooted in fear of failure

서론

키보드 왼쪽 중앙에는 사용 빈도와 필요성에 비해 지나치게 좋은 위치를 차지하고 있는 Caps Lock 키가 있다. 그래서인지 키보드 입력 언어(Input Source)를 여러 개 사용할 경우, 맥OS에서는 기본적으로 이 Caps Lock 키를 통해 언어 전환이 가능하도록 설정되어 있다.

문제는 이 Caps Lock을 통한 키보드 언어 전환이 꽤 불편하다. 전환에 약간의 딜레이가 있을 뿐 아니라, 심지어는 한번씩 입력이 씹혀서 전환이 안될 때도 있다.

해결 방법

키보드의 Caps Lock에 일반적으로 사용되지 않는 키(F18, F19, ...)를 매핑해두고, 설정의 키보드 단축키에서 Select next source in Input Menu에 대한 단축키를 해당 키로 바꿔주면 된다.

Caps Lock 키에 매핑을 변경하기 위해 karabiner라는 프로그램을 활용하는 방법도 있지만, 개인적으로 키 하나 때문에 별도의 프로그램을 설치하고 싶지는 않아서 맥OS 내장 프로그램인 hidutil을 사용하고 있다.

언젠가 한번쯤은 "그때 그거 어떻게 했더라?" 싶을 때가 생길 것 같아서, 적용 과정을 기록해두려 한다:

1. 먼저 Caps Lock 키에 F19를 매핑시키기 위한 스크립트를 작성해야 한다.
   아래 코드를 그대로 복사해서 사용해도 되고, hidutil generator 사이트에서 원하는 키를 선택해 스크립트를 생성해도 된다.

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
    <key>Label</key>
    <string>com.local.KeyRemapping</string>
    <key>ProgramArguments</key>
    <array>
        <string>/usr/bin/hidutil</string>
        <string>property</string>
        <string>--set</string>
        <string>{"UserKeyMapping":[
            {
              "HIDKeyboardModifierMappingSrc": 0x700000039,
              "HIDKeyboardModifierMappingDst": 0x70000006E
            }
        ]}</string>
    </array>
    <key>RunAtLoad</key>
    <true/>
</dict>
</plist>

2. com.local.KeyRemapping.plist 파일을 ~/Library/LaunchAgents 경로로 옮긴다.
   처음부터 해당 경로에 파일을 생성해도 무방하다.
3. 재부팅 없이 변경사항을 바로 적용해주기 위해 터미널에서 launchctl load ~/Library/LaunchAgents/com.local.KeyRemapping.plist를 실행한다.
4. 마지막으로 설정 -> 키보드 단축키 -> Input Sources에 가서 Select next source in Input Menu 의 기본 단축키인 control + option + space를 더블클릭한 다음 Caps Lock 키를 입력하면, 단축키가 F19로 변경되는 것을 확인할 수 있다.

Select the previous input source는 약간의 딜레이가 있기 때문에,
아래쪽에 있는 Select next source in Input menu 사용!

요약

1. com.local.KeyRemapping.plist 파일 만들기

• hidutil generator

2. ~/Library/LaunchAgents 경로에 저장하기 (재부팅 시에도 적용될 수 있도록)
3. launchctl load ~/Library/LaunchAgents/com.local.KeyRemapping.plist 실행하기
   (로그인 아이템 등록)

로그인 아이템 등록을 해제하려면:
launchctl unload ~/Library/LaunchAgents/com.local.KeyRemapping.plist

마무리

키씹힘 없이, 한영전환 아주 빠르게 잘 된다!

aㅁaㅁaㅁaㅁaㅁaㅁaㅁaㅁaㅁaㅁ

작성중

서론

웬만하면 기본 애플리케이션, 순정을 쓰려고 하는 편이다.

영상 편집을 할 것도 아니고, ...

놀랍게도 macOS 기본 미디어 플레이어인 QuickTime Player에서는 .mp4 영상을 열 수 없다..?

해결 과정

결론

• macOS의 기본 영상 플레이어인 QuickTime Player는 사실 .mp4 확장자를 지원함!
• 하지만 호환성 문제가 발생할 여지가 있음 (오래된 코덱을 사용하는 영상?)
• 깔끔하고 무료에다가 오픈 소스인 IINA 씁시다

바꾸는 김에, 사용 경험의 일관성을 위해 .mov 확장자의 영상도 IINA를 기본값으로 설정했다.

프로그래밍 언어 정의

: 구문(Syntax) + 의미(Semantics)

구문 (Syntax)

: 어떻게 생긴 것이 제대로 생긴 프로그램인가에 대한 것

의미 (Semantics)

: 제대로 된 프로그램은 어떤 동작을 하는지에 대한 것

구문 표기법

BNF (Backus-Naur Form)

: Type 2 문법(Context free grammar)을 표현

• 비 단말 기호 (Nonterminal)
  • 아직 완성되지 않은 부분
  • 다른 형태로 치환 가능한 기호(변수)들의 유한 집합
  • 꺾은 괄호(angle bracket)로 감싸서 나타냄
    • <sentence> | <subject> | <predicate> | <verb> | <article> | <noun> | ...
• 단말 기호 (Terminal)
  • 문법에 의해 실제로 나타나는 글자나 단어
  • 더 이상 치환할 수 없는 기호(상수)들의 유한 집합
  • 그냥 쓰거나 따옴표로 감싸서 나타냄
    • the, boy, girl, ate, cake, ...
• 시작 기호 (Start Symbol)
  • 특별히 정의된 하나의 비단말 기호
    • <sentence> | <S>
• 생성 규칙 (Productions, rewriting rules)
  • 각 비단말기호를 어떻게 바꿔 쓸 수 있는지에 대한 유한 개의 규칙
    • <sentence> ::= <subject> <predicate>
    • <subject> ::= <article> <noun>
    • <predicate> ::= <verb> <article> <noun>
    • <verb> ::= ate | ran
    • <article> ::= the
    • <noun> ::= boy | girl | cake
• 치환 연산 (Replacement Operation)
  • 비단말기호를 생성규칙에 따라 바꿔 쓰는 것
  • => 기호로 나타냄
    • <article> <noun> <predicate> => the <noun> <predicate>

Syntax doesn't imply correct semantics
문법적으로 올바르다고 해서 반드시 의미가 통하는 것은 아니다

EBNF (Extended BNF)

: 기존 BNF의 ::=, | 기호 외에도 [], ( | ), { }*가 추가(확장)된 문법

• [] - 있어도 되고 없어도 됨 (0회 또는 1회)
• ( | ) - 안쪽 or 기호들 사이에서 선택 (반드시 하나 선택)
• { }* - 0번 이상 반복 (0, 1, 2, ...). []와 비슷하지만 반복도 가능

CFG (Context Free Grammar)

: 어떤 nonterminal이 들어와도, 그에 대한 생성규칙이 존재하는 문법

• BNF보다 짧고 간결하게 표현 가능
  • BNF: <A> ::= <B><C>
  • CFG: A -> BC

BNF, EBNF, CFG의 표현력(표현 가능한 범위)은 같다!

• Static Semantics
  • CFG로 나타낼 수 없는 범위의 구문을 규정함
  • Attribute Grammar로 표현됨
  • 경우에 따라 Semantics의 범주에 포함시키기도 함

의미 표기법

Denotational Semantics

: 프로그램의 의미를 semantic function을 통한 evaluation으로 해석

Operational Semantics

: 프로그램의 의미를 state transformer로 해석 - 이때 state는 machine state를 나타냄

Axiomatic Semantics

: 프로그램의 의미를 predicate transformer로 해석

의미론은 살짝 난해한 분야임..!

번역 과정

1. 어휘 분석 (Lexical Analysis, scanning)

• 프로그램을 단어로 나눔
• 주석 제거
• x := a * 2 + b * (x * 3)
  -> id<x> assign id<a> times int<2> plus id<b> times lparen id<x> times int<3> rparen
• paren = parenthesis

2. 구문 분석 (Syntax Analysis, parsing)

• 구문 구조를 tree로 표현
  == parse tree 생성

3. 의미 분석 (Semantic Analysis)

• 정적(Static) 의미 분석
• 타입 검사는 여기서 수행
• 변수들이 사용되기 전에 정의되었는지도 검사

4. 중간 코드 생성 (Intermediate Code Generation)

• parse tree로부터 수행 가능한 코드를 생성

r1 <- load M[fp+x]
r2 <- loadi 3
r3 <- mul r1, r2
r4 <- load M[fp+b]
r5 <- mul r3, r4
r6 <- load M[fp+a]
r7 <- sll r6, r5
r8 <- add r6, r5

store M[fp+x] <- r8

5. 최적화 (Optimization)

• 코드의 동작을 유지하는 선에서, 각종 성능을 개선
  • code size
  • registers
  • speed
  • power

6. [기계어] 코드 생성 (Code Generation)

모호성 (Ambiguity)

: 어떤 문법에서는 같은 문자열에 대해서 두 개 이상의 파스트리가 얻어질 수 있다.
== 파스트리가 유일하지 않다 == 문법이 모호하다

• 모호성을 제거하려면?
  • 문법 자체의 모호성 제거함
  • 파서에서 특정 파스트리만을 선택하도록 함

문법적 모호성 제거하기

S -> SS | (S) | () 는 S -> SS 부분에서 모호성이 생길 수 있다.

예를 들어, ()()()를 생성할 때 S => SS => SSS로 가는 과정에서 두 가지 파스트리가 생길 수 있다.