기말 시험 준비

 

5-2단원

 

요소 타입

• 동형(homogeneous) 구조: array, set
• 이형(heterogeneous) 구조: record, list
• 주의: 동형 리스트만 허용하는 경우도 있음

 

저장공간 관리의 문제점

Garbage(떠돌이 객체)

• 참조 경로를 잃어 버린 객체
• 객체의 deadlocation이 너무 늦음
• dangling object라고도 함
• 위험하진 않지만 공간의 낭비 -> 메모리 누수

Dangling Reference(외로운 참조)

• 이미 해제된 공간을 가리키는 참조 경로
• 객체의 deadlocation이 너무 빠름
• 다른 용도의 공간을 훼손할 수 있음 -> 심각한 위험

 

6단원

 

• Abstraction(추상화): 더 간단하게 만드는 것
• Encapsulation(캡슐화): Data와 Operation을 하나의 묶음(capsule)으로 묶을 수 있는 장치
• Information Hiding(정보은닉)
  • 상세내용을 숨기는 것
  • 인터페이스와 무관한 부분을 숨기는 설계 기법
  • 정보은닉은 어떤 언어에도 구현 가능함
• 추상화, 캡슐화, 정보은닉은 밀접한 연괸이 있음
• 캡슐화와 정보은닉은 통상 같은 의미로 사용하지만 구분하는 경우도 있음

 

Abstract Data Types

Type = Set of Values + Set of operations

Abstract Data Types(ADT)

• ADT도 타입이다.(Value Set + Operation Set)
• 다만 operation의 구현이 드러나지 않음(추상화)
• value의 구현(저장형태 등)도 드러나지 않음
• ADT는 Algebraic data type인 경우가 많음 

 

Subprogram Storage 구현

가장 간단한 구현 방법

• 서브 프로그램을 통째로 복사하여 수행 -> 비효율적
• recursion -> 실행시간에 복사하는 것이 필요할지도 모름

좀 더 나은 구현 방법

• 정적인 부분(static part)과 동적인 부분(dynamic part)을 구별
• 실행시간에는 동적인 부분만 관리

구현

• 정적인 부분: 코드, static data -> static segment
• 동적인 부분: 실인수, local data -> dynamic segment

 

Activation Records

Activation Records

• 서브프로그램과 연관된 동적 데이터를 관리하는 구조체
• 서브프로그램이 실행될 경우에만 생성됨
• 실행 중인 하위 프로그램의 비코드 부분의 형식 또는 레이아웃을 활성화 레코드라고 합니다.
• 활성화 레코드 인스턴스는 활성화 레코드의 구체적인 예입니다(특정 하위 프로그램 활성화를 위한 데이터 수집)

 

지속시간(lifetime)과 가시영역(Scope)

지속시간

• 해당 변수의 storage binding이 지속되는 시간
• 시간 축의 일부분(session)
• static data / dynamic data

가시영역

• 프로그램에서 해당 변수를 볼 수 있는 영역
• 공간의 일부분(section)
• global data / local data

 

할당 방법에 따른 변수의 분류

• static allocation: 프로그램 적재 시 할당
• automatic allocation: 서브프로그램 진입 시 할당
• manual allocation: 명시적 연산자나 함수를 통해 변수 할당

 

Granularity of Typing(타입의 세분성)

Strongly Typed

• 모든 타입 오류를 다 검출해냄
• 즉 타입 오류가 있는데도 불구하고 수행되는 경우는 없음

Weakly Typed

• 타입이라는 개념은 있음
• 하지만 어떤경우에는 타입 오류가 검출되지 않음
• 타입 변환 연산자, variant record 등이 문제의 원인일 수 있음

Typeless

• 어떤 이름은 임의 타입의 객체를 가리킬 수 있음
• 특정 이름에 대한 타입 선언도 별도로 없음

 

Type Cheking Time

Static Type Checking

• 수행 전에 타입 검사를 완료함

Dynamic Type Cheking

• 수행 중에 타입 검사
• 타입 descriptor를 수행 중 관리해야 함

주의점

• Strongly Typed Language라고 해서 반드시 Static Type Cheking을 수행하는 것은 아님

 

 

 

Type Equivalence 종류

• 이름 동등성(name equivalence): 이름이 같으면 동일
• 구조 동등성(structural equivalence): 구조가 같으면 동일

Inheritance

일반적 의미의 Inheritance

• 한 프로그램 요소의 특징이 다른 프로그램 요소로 전달되는 것
• 감싸고 있는 블록의 변수 이름을 내부 블록에서 볼 수 있는 것도 Inheritance의 일종이라고 보기도 함

ADT 관점의 Inheritance

• 한 ADT를 보다 구체화하여 다른 ADT를 만드는 것
• superclass, subclass 관계를 형성(subtype관계를 형성)
• subclass는 superclass의 모든 속성을 상속받음

Inheritance의 구현 예

• Ada의 tagged record
• C++의 derived class
• Java의 subclass

 

 

8단원

Control 분류

• Sequence Control(Flow Control): 수행 순서 제어
• Data Control: 서브프로그램 사이의 데이터 흐름 제어

 

(-B + SQRT(B**2-4*A*C)) / (2*A)

Tree Representation의 예

<postfix>
연산자를 피연산자의 뒷쪽에 표시하는 방법이다.
Stack을 사용한 컴퓨터의 계산을 위해서 postfix와 prefix가 고안되었다.
변형방법은 괄호로 묶어서 괄호를 하나씩 지우면서 연산자를 뒤로 빼내면 된다.
가장 기본적인 변환방법은 'a + b' > 'a b +' 이다

(a + b) * c / d + e
> (((a + b) * c) / d) + e
> (((a + b) * c) / d) e  +
> ((a + b) * c) d / e  +
> (a + b) c * d / e  +
> a

 

prefix는 반대로 부호를 앞에 붙이면된다.

 

 

Eager Evaluation

• 피연산자의 값을 먼저 구하고 함수를 적용
• eval-apply evaluation model

Lazy Evaluation

• 함수의 정의에 따라 필요한 경우에만 피연산자의 값을 구함
• push-enter evaluation model

인수 전달 방법과의 유사성

• eager evaluation ~= pass by value
• lazy evaluation ~= pass by name

 

 

Structured Program Theorem

• 다음 세 가지 제어 구조는 계산 가능한 기능을 표현하기에 충분하다.
  • Composition(sequence): 놓인 순서대로 수행
  • Alternation(selection): 둘 이상의 문장에 대해 하나만 선택
  • Iteration(repetition): 특정 문장을 0회 이상 반복

 

Goto에 의존하면

• 프로그램 계층 구조를 알아볼 수 없다 -> one-in, one-out 구조 필요
• 문장 순서가 수행 순서와 무관하다 -> 스파게티 코드 유발
• 특정 문장 그룹이 여러 용도로 사용될 수 있다 ->  이해하기 어려움

Structured Programming

• 프로그램 설계를 계층적으로
• structured 제어 구조만 사용(3가지 기본구조)
• 문장 순서가 바로 수행 순서가 되도록
• 어떤 문장 그룹은 하나의 목적으로 사용되도록
• -> goto-less programming

 

 

Dangling Else Problem

• 이 "else"가 누구 else냐?
  if expr1 then tif expr2 then statement1 else statement2
  
  • 해결방법1: 가장 가까운, 앞쪽, 짝없는 if
  • 해결방법 2: end-if을 강제

 

 

Prime Programs

• • 흐름도를 이루는 기본 구성요소: function, decision, join
  • 프로그램 분류: prime program, composite program
  • 우리가 추구해야 할 방향: proper program
   

Proper Programs

Proper program: 제어 흐름이 다음과 같은 프로그램

• 입구가 하나
• 출구가 하나
• 입구로부터 모든 노드로 경로가 있고, 모든 노드에서 출구로 경로가 있음

Prime Program

• 두개 이상의 노드로 이루어진 proper subprogram을 포함하고 있지 않은 proper program 
• 단, function node가 일렬로 늘어선 경우는 하나의 prime으로 취급
• 그 안에서 프라임 서브프로그램을 추출하기 위해 2개의 아크를 자를 수 없다.
• sunprogram을 구분하기 위해선 해당 자리에 function노드를 하나 넣어보면 된다.(입력,출력 부분이 각각 1개여야함)

Composite Program

• prime program이 아닌 proper program

 

 

 

 

 

9단원

 

 

Local vs Non-local

• 지역변수(local variable): 변수를 참고하는 문장이 포함된 블록과 변수를 선언한 블록이 같은 경우, 해당 변수는 지연변수
• 비지역변수(non-local variable): 참조 문장이 포함된 블록과 선언한 블록이 다를 경우, 해당 변수는 비지역변수

• 정적 범위(특정 범위)를 둘러싸는 것을 static ancestors(정적 조상)이라고 한다; 가장 가까운 정적 조상은 static parent(정적 부모)라고 불린다.

Evaluation of Dynamic Scoping

• 장점: 편리함
• 단점: 가독성 부족
• 범위와 수명은 때때로 밀접한 관련이 있지만, 다른 개념이다!!(C++의 static변수)

 

static_depth

• 그 범위의 중첩 깊이인 정적 범위와 관련된 정수이다.

 

Chain_offset(nesting_depth)

• 비로컬 참조의 chain_offset 또는 nesting_depth는 참조의 static_depth와 그것이 선언된 범위의 차이이다.
• 참조는 쌍으로 나타낼 수 있다: (chain_offset, local_offset) 여기서 local_offset은 참조되는 변수의 활성화 레코드에서 오프셋이다.

 

static link,dynamic link 있고 local offset은 3부터 시작, 파라미터가 있으면 파라미터가 앞으로 그래서 이전그림이에 E(0,5)이다

 

 

Static Chain 방법의 단점

• 참조되는 비지역 변수가 선언된 블록의 중첩깊이와 참조 문장을 포함한 중첩깊이의 차이가 크다면 비지역 변수 참조 시간 부담이 커진다.
• 비지역 변수 참조 시간이 변수에 따라 다름: 수행 시간이 중요한(real-time application)에서 사용하기 힘들다.

Display

• 정적영역규칙을 구현하기 위한 다른 방법
• 정적 링크를 별도의 스택에 관리
• 참조 환경의 모든 변수는 이 스택이 가리키는 활성 레코드 내에 존재

 

 

정적 체인(static chain)과 디스플레이(display) 비교

• locals에 대한 참조: 거의 차이가 없다.
• nonlocal에 대한 참조:
  • 만약 한 단계 떨어져 있다면, 둘은 똑같다.
  • 그 이상 떨어져 있다면, 디스플레이가 더 빠르다.
  • 모든 비로컬 참조 비용이 동일하기 때문에 디스플레이는 시간이 중요한 코드에 더 좋습니다.
• Procedure 호출
  • 하나 또는 두단계의 깊이의 경우 static chain이 더 빠르다.
  • 그 이상은 display가 더 빠르다.
• Procedure 리턴
  • 둘 다 시간이 고정되어 있지만, static chain이 약간 더 빠르다.
• 결론
  • 비지역 변수 참조가 빈번하다면 display가 유리하다.
  • 비지역 변수 참조가 거의 없다면 static chain 방법이 더 유리하다.

 

Dynamic Scope 구현

 

 

인수전달 방법: 실 인수와 형식 매개변수와의 관계를 설정

• Call by name
  • 인수를 받지 않는 함수
  • 각 실인수에 대하여, 실인수로 주어진 수식의 L-value와 R-value를 계산하는 thunk를 만듦
  • 인수를 사용할 경우 해당 thunk 호출
  •  프로그램을 이해하기 힘들다.
• Call by reference
  • 실인수의 I-value를 전달
  • callee에서 실인수의 r-value와 l-value를 모두 참조할 수 있음
  • 즉, 실인수의 내용을 변경할 수도 있음 -> in-out parameter
• Call by value
  • 실인수의 r-value를 전달
  • 실인수의 값을 복사하는 것과 같은 의미 -> call by copy라고도 함
• Call by result (or value-result)
  • all by value처럼 인수의 r-value를 매개변수로 전달
  • 서브프로그램에서 복귀시, 매개변수의 r-value를 다시 실인수에 복사
  • in-out parameter를 구현하는 다른 방법으로서 aliasing이 발생하지 않음
  • aliasing이 발생하지 않는다.
  • 값 복사에 따른 시간 부담이 있다.
  • 복사 순서에 따라 결과가 달라질 수 있다.