Sign In

[프로그래밍 언어] 7. Implementing Subprograms

Y
Yerim
  1. Programming Language

호출과 복귀

호출

•
매개변수 전달 방법을 포함
•
지역 변수가 정적변수가 아닌 경우
◦
지역 변수를 위한 기억 장소 할당 → 지역변수 바인딩 → 실행 상태를 저장
◦
레지스터 값, CPU 상태 비트, 환경 포인터 EP 포함
•
제어를 부프로그램 코드에 전달 → 반환
•
중첩 부프로그램 지원하면 가시적인 비지역변수를 접근할 수 있는 동작 구조를 생성

복귀

•
출력 모드, 입출력 모드 + 복사 매개변수 → 형식 매개변수의 지역 값을 실 매개변수로 옮김
•
기억 장소를 해제 → 실행 상태를 복원 → 제어를 호출 프로그램에 반환

단순 부프로그램

부프로그램의 코드 (고정크기) + 지역변수 (고정크기)
•
중첩될 수 없고 지역변수가 정적
•
호출: 실행 상태 저장 → 매개변수 계산 및 전달 → 복귀 주소 전달 → 제어 전달
•
복귀: 실 매개변수 복사 → 함수 값 이동 → 실행 상태 복원 → 제어 전달
호출 복귀를 위해 저장되어야 하는 정보
•
실행 상태
•
매개변수
•
복귀 주소
•
함수의 반환값
•
임시 기억장소
활성화 레코드
•
활성화 부프로그램: 실행 중인 프로그램
•
활성화 레코드: 부프로그램의 코드를 제외한 부분의 형식 → 정적
•
단순부프로그램에서 저장할 값 → 레코드 형식 구조체 필드 (인스턴스) - 데이터의 모음
단순 부프로그램을 갖는 언어
•
재귀 부프로그램 지원 X → 활성화된 부 프로그램은 오직 하나 → 활성화 레코드 인스턴스도 하나
•
Local variables: 피호출
•
Paramters: 호출 → 피호출
•
Return address: 호출
•
호출자의 실행 상태 생략
•
함수의 반환값이 없는 경우 생략
링커
•
고정 크기 → 정적으로 할당
•
컴파일 시에 참조 리스트 + 기계어 코드
•
운영체제의 링커에 의해 통합
•
파일들을 메모리에 적재 → 호출 목적지 주소 설정 → 동일 작업 수행
•
MAIN → 기계 코드 프로그램 + 활성화 레코드인스턴스 → 메모리 적재
•
A, B, C에 대한 호출, 호출 모적지 주소 패치

스택-동적 지역변수 부프로그램

•
스택 동적 지역변수를 갖는 언어의 부프로그램 연결 구현 → 재귀 부프로그램을 지원

복잡한 활성화 레코드

•
지역변수의 묵지겅니 할당과 해제 코드 생성
•
재귀 부프로그램의 다중 동시 활성화 가능성 → 한 개 이상의 부프로그램 인스턴스가 존재
•
주어진 시점 에 한 개 이상의 부프로그램 인스턴스가 존재 → 메모리 크기에 의해 제한
•
각 활성화는 활성화 레코드 인스턴스 요구 → 컴파일 시간에 크기 및 형식 알려짐
•
피호출: Local variables
•
호출: Paramters, Dynamic link, Return address
◦
return address: 다음 명령어에 대한 포인터
◦
dynamic link: 호출자의 활성화 레코드 인스턴스의 기준점 base 포인터
▪
정적 영역 언어에서 추적 정보 제공 / 동적 영역 언어에서 비지역 변수 접근
◦
paramters: 호출자가 제공하는 값, 주소
◦
local variables: 지역 스칼라 변수 / 데이터 구조 → 힙 등 다른 곳에 할당
•
활성화 레코드 인스턴스 동적 생성 → 실행 시간 스택에 생성
환경 포인터 EP
•
현재 실행 중인 활성화 레코드 인스턴의 기준 주소 (실행 시간 스택에 저장 X)
•
새로운 활성화 사례에 저장 → 새로운 기준 주소를 가리키도록 설정
•
스택 꼭대기top를 재설정pop하고 동적 링크의 값으로 EP를 재설정
•
g()가 실행 중이라면 f(), main은 중단중
활성화 레코드 인스턴스 부프로그램 호출 동작
•
활성화 레코드 인스턴스 생성 → 실행 상태 저장 → 매개변수 계산 및 전달 → 복귀 주소를 피호출 프로그램에 전달 → 제어를 피호출 프로그램에 전달
•
프롤로그 동작: EP를 스택에 저장, 새로운 값 생성 → 지역 변수 할당
•
에필로그 동작: 실 매개변수로 복사 → 함수 값(반환 값) 이동 → 스택 꼭대기 재설정, EP 재설정 → 실행 상태 복원 → 제어를 호출자에게 전달

재귀 없는 부프로그램

void fun1(float r){
    int s, t;
    fun2(s);
}
void fun2(int x){
    int y;
    fun3(s);
}
void fun3(int q){
    ...
}

void main(){
    float p;
    fun1(p);
}
•
함수가 시작되면 ARI 추가, 종료되면 ARI 삭제
•
동적 체인 또는 호출 체인 → 동적 링크이 집합
•
지역 오프셋: 지역 변수의 참조는 지역 영역의 오프셋 → 지역 오프셋을 EP에 더하면 찾을 수 있음

재귀 부프로그램

int factorial(int n){
    // 지점 <1>
    if (n<=1) return 1;
    else      return (n*factorial(n-1));
    //지점 <2>
}
void main(){
    int value;
    value = factorial(3);
    // 지점 <3>
}
•
첫 번쨰 ARI는 호출자 main의 복귀 주소를 가지고 있음
•
함수 값: 1 → 2 → 6

중첩 부프로그램

•
Python, JavaScript, Ruby, Lua, Ada 등 → 정적 영역, 스택 동적, 부프로그램의 중첩 허용
중첩 부프로그램 정적 영역 언어에서 비지역 변수 참조
•
비지역적으로 접근 가능한 비정적 변수 → 활성화 레코드 인스턴스 중 하나에 존재
•
활성화 인스턴스를 찾구 → 지역 오프셋으로 변수에 접근
정적 조상 영역의 변수에 접근
•
자신이 정적 조상 영역에서 선언된 변수만 가시적으로 접근
•
모든 정적 조상의 활성화 레코드 인스턴스 → 스택에 항상 존재
•
모든 정적 조상 부프로그램이 활성화 → 부프로그램을 호출 가능
•
정적 조상이 활성화 상태가 아니라면 접근이 무의미

활성화 레코드 인스턴스 검색

비지역 참조
•
정확한 선언 = 첫 번째 발견된 선언
•
정적 체인을 통해 활성화 레코드 인스턴스를 찾을 수 있음
정적 체인
•
중첩 부프로그램을 허용하는 언어에서 정적 영역 구현
•
정적 링크 → 정적 영역 포인터 → 정적 부모의 활성화 레코드 인스턴스의 시작 주소 가리킴
•
정적 체인은 모든 정적 조상을 연결 (비지역변수를 모두 찾을 수 있음)
단순한 방법
•
정적 체인을 따라감
•
컴파일러는 비지역변수 참조 + 필요한 정적 체인의 길이도 알고 있음
•
정적 깊이: 중첩되지 않은 정적 깊이는 0, A가 B 내부에 중첩되었으면 1
•
실제 참조: (A정적 깊이 - B 정적 깊이)
•
<1> (체인 오프셋, 지역 오프셋) = (0, 3) → 지역 변수
•
<2> (2, 3) → 비지역변수 (bigsub의 변수 a)
•
<3> (1, 3) → 비지역변수 (bigsub의 변수 a)

블록

{
    int temp;
    temp = list[upper];
    list[upper] = list[lower];
    list[lower] = temp;
}
•
사용자-지정 지역 영역 제공
•
다른 곳에서 선언된 같은 이름을 갖는 변수에 의해 방해 받지 않음
•
블록은 프로그램의 같은 장소에서 항상 호출되는 매개변수가 없는 부프로그램을 처리
•
오프셋을 정적으로 계산하면서 블록 변수를 지역변수 인 것처럼 처리

동적-영역 규칙 구현

심층 접근

•
동적 영역 언어에서 지역변수가 스택 동적이고 활성화 레코드의 일부
→ 비지역변수의 참조는 가장 최근에 활성화된 부프로그램부터 시작, 인스턴스를 탐색
•
정적 체인 대신 동적 체인을 사용 → 동적 체인은 활성화된 역순으로 활성화 레코드 인스턴스 연결
•
스택 심층부에 대한 탐색 → 심층 접근
•
정적 체인과의 차이점
◦
탐색할 체인의 길이를 결정하는 방법이 없음 → 첫 번째 인스턴스가 발견될 때까지 탐색
◦
동적영역 활성화 레코드는 변수 이름을 정해야함 → 정적 영역 언어에서는 값만 요구
•
main은 sub1 호출
•
sub1은 sub2 호출
•
sub2는 sub3 호출
•
변수 u 참조
•
4개의 동적 링크
→ 10개의 변수 이름 조사
•
2개의 동적 링크
→ 6개의 변수 이름 조사

피상 접근

•
심층 접근과 같은 목적을 달성하기 위한 다른 구현
•
활성화 레코드에 저장되지 않음
•
각 변수에 대해 별도의 스택을 만듦
•
새로운 변수가 최상위에 한 개의 셀을 할당
•
이름의 참조는 스택 꼭대기에 있는 변수 → 가장 나중에 들어간 변수(가장 최근에 생성된 변수)
•
존속시간이 끝나고 스택에서 한 항목이 제거
•
장점: 빠른참조 허용
•
단점: 유지보수 비용 높아짐
Yerim-DevNote
Subscribe to 'Yerim-DevNote'
Subscribe to my site to be the first to receive notifications and emails about the latest updates, including new posts.
Join Slashpage and subscribe to 'Yerim-DevNote'!
Subscribe
👍
Open channel