[프로그래밍 언어론] CH6 Subprograms

Subscript Binding and Array Categories

• static: subscript 범위가 정적으로 바인딩, storage 할당도 정적 (런타임 이전)
  • 장점: 효율성 (동적 할당 없음)
• fixed stack-dynamic: subscript 범위는 정적으로 바인딩, 할당은 선언 시간에 수행
  • 장점: 공간 효율성
• stack-dynamic: subscript 범위가 동적으로 바인딩, storage 할당도 동적 (런타임에 완료)
  • 장점: 유연성 (배열을 사용할 때까지 배열 사이즈 알 필요 없다)
• fixed heap-dynamic: fixed stack-dynamic과 비슷, storage 바인딩은 동적이지만 할당 후 고정됨.
  • ex: 요청시 바인딩이 수행되고 storage는 스택이 아닌 힙에 할당됨
• heap-dynamic: subscript 범위 바인딩과 storage 할당이 동적, 여러번 변경 가능
  • 장점: 유연성 (프로그램 실행 중에 배열 크기 변할 수 있음)

 

- static modifier를 포함하는 C, C++ 배열: static

- static modifier 없는 C, C++ 배열: fixed static-dynamic

- C, C++을 fixed heap-dynamic 배열 제공

- C#은 fixed heap-dynamic을 제공하는 ArrayList 클래스를 포함

- Perl, JavaScript, Python, Ruby: heap-dynamic 지원

 

 

Array Operation

• APL: 단항 연산자, 배열 처리 연산 제공 (ex: 열 요소 반전)
• Ada: 배열 할당, catenation 허용
• Python: 배열 할당은 참조 변경,  catenation, element membership 연산 제공
• Ruby: 배열 catenation 제공
• Fortrau: 배열 요소의 쌍 사이에 있기 때문에 elemental 연산 제공
  • 예: 두 배열 사이의 + 연산자는 두 배열 요소 쌍의 합 배열 제공

 

 

배열 평가와 비교

• 데이터 값의 콜렉션이 heterogeneous인 경우 레코드가 사용됨.
• 배열 요소에 대한 엑세스는 레코드 필드에 대한 엑세스보다 매우 느림
  • subscript는 동적이지만 필드 이름은 정적이기 때문
• 동적 subscript는 레코드 필드 엑세스로 사용될 수 있지만, type checking을 허용하지 않으면 훨씬 느려짐

 

 

Union Types

• 변수 실행 동안에 서로 다른 시간에 다른 형식의 값을 저장할 수 있는 유형
• Discriminated vs Free Unions
  • Fortran, C, C++은 type checking을 위한 언어 지원이 없는 union construct를 지원 -> free union
  • unionㅡ이 type checking은 각 union이 discriminat(판별자)라 하는 type indicator을 가지고 있어야 함.
• union 평가
  • free union은 unsafe (type checking 허용 안 함)
  • Java, C#은 union 지원 안함
  • Ada의 descriminated union은 safe.

 

 

Point

 

Poiner operations

• 기본 연산: 할당, 역참조
• assignment: 포인터 변수의 값을 유용한 주소로 설정
• dereferencing: 포인터 변수가 가리키는 곳에 접근해 값을 가져옴
  • 역참조는 명시적 또는 암시적
  • C++은 *를 통해 명시적 연산을 사용

 

Problems with Pointers

• dangling pointer
  • 포인터는 할당 해제된 heap-dynamic 변수 가리킴
• heap-dynamic 변수 손실
  • garbage: 더 이상 엑세스 할 수 없는 할당된 heap-dynamic 변수
  • memory leakage: heap-dynamci 변수를 잃는 과정

 

Reference Types

• C++: 형식 매개변수에 주로 사용되는 reference type이라 불리는 포인터 타입 포함
  • pass-by-reference, pass-by-value
• Java: C++의 reference 변수 확장, 포인터 완전히 대체
  • reference는 주소가 아닌 객체 참조
• C#: Java의 reference와 C++의 포인터 모두 포함

 

Evaluation of Pointers

• dangling pointer, dangling object는 heap 관리 문제이다.
• 포인터는 goto와 비슷, 변수로 액세스 할 수 있는 셀의 범위 넓음
• 포인터나 레퍼런스는 동적 데이터 구조 필요

 

Dangling Pointer 문제 해결 방법

• tombstone: heap-dynamic 변수를 가리키는 포인터인 추가 heap cell
  • 모든 동적 변수가 특정 셀을 포함하도록 해서
  • heap-dynamic 변수가 할당 해제되면, tombstone은 nil로 설정하고, nil을 가리키는 포인터의 참조를 오류로 검출하는 방법
  • 실제 포인터 변수는 tombstone만 가리킴
  • 시간, 공간 낭비 유발

• locks-and-keys: 포인터 변수는 (key, address) 쌍으로 표시
  • lock 값과 key 값을 비교해 다르면 오류로 취급한다. 
  • heap-dynamic 변수는 정수 lock 값에 대한 셀과 변수로 표시
  • heap-dynamic 변수가 할당되면, lock 값이 생성되어 포인터의 key 셀과 lock 셀에 배치됨.

 

 

 

 

Heap Management

• 매우 복잡한 런타임 프로세스
  • single-size-cell vs variable-size-cell
  • garbage를 회수하는 2가지 방법
    • reference counter (eager approach): 점진적으로 회수
      • 현재 셀을 가리키는 포인터의 수를 저장하는 (모든 셀의) 카운터를 유지
      • 단점: 공간 필요, 실행 시간 필요, 원형으로 연결된 셀이면 복잡함
      • 장점: 본질적으로 점진적이여서 애플리케이션 실행의 상당한 지연을 피할 수 있음
    • mark-sweep (lazy approach): 변수 공간 리스트가 비면 회수 발생
      • 런타임 시스템은 요청에 따라 storage 셀을 할당하고 필요에 따라 셀에서 포인터를 분리. 그 다음 mark-sweep 시작.
        • 모든 heap cell은 컬렉션 알고리즘을 사용되는 추가 bit를 가진다.
        • 모든 cell은 처음에는 garbage로 초기화 된다.
        • 모든 포인터는 heap으로 추적되고, 접근 가능한 셀은 garbage가 아닌 것으로 표시됨
        • 모든 garbage 셀은 이용가능한 셀의 리스트로 반환
        • 단점: 원래 형태에서는 매우 드물게 수행됨. 수행 완료되면 애플리케이션 실행이 상당히 지연된다. 현대의 mark-sweep 알고리즘은 이를 더 자주 수행함으로써 이를 회피한다(-> incremental mark-sweep라고 함)

 

Type checking

• : 연산자의 피연산자가 호환 가능한 타입인지 보장하는 활동
• compatible type: 연산자에 대해 합법적이거나 언어 규칙에 따라 컴파일러에서 생성된 코드에 의해 법적인 유형으로 암묵적으로 변환될 수 있는 유형이다.
• type error: 부적적할 타입의 피연산자에 연산자를 적용하는 것
• 모든 type binding이 정적 -> 모든 type checking이 정적
• 모든 type binding이 동적 -> 모든 type checking이 동적
• type error 발생시 프로그래밍 언어는  strongly typed
• strong type 장점: 타입 오류를 초래하는 변수의 오용을 탐지 가능