GN⁺: 고대 세계에서의 서브루틴 호출: 컴퓨터가 스택이나 힙을 갖기 전

컴퓨터에 스택과 힙이 없던 고대의 서브루틴 호출

• 현대 컴퓨팅에서는 스택과 힙을 당연하게 여기지만, 컴퓨팅의 초기 시절에는 스택이나 힙 없이 컴퓨터가 작동함.
• 동적 메모리 할당 없이 컴퓨팅을 상상하는 것은 어렵지 않음. 모든 것에 고정 크기의 메모리 버퍼를 사용해야 함.
• 가변 크기 데이터를 처리해야 할 경우, 예상 가능한 데이터를 수용할 수 있는 충분히 큰 고정 크기 버퍼를 예약함.
• 컴파일 시간 설정을 제공하여 클라이언트가 최대 용량을 조정할 수 있도록 하거나, 고정 크기 버퍼에서 메모리를 "할당"하고 "해제"할 수 있는 사용자 정의 할당자를 작성함.

스택 없이 함수 호출하기

• 컴파일러는 각 함수의 인바운드 매개변수, 반환 주소, 로컬 변수에 대해 비밀 글로벌 변수를 정의함.
• 함수 호출을 생성하기 위해 컴파일러는 매개변수 값을 해당 비밀 글로벌 변수에 할당하고, 반환 주소를 함수의 비밀 "반환 주소 변수"에 할당한 다음 함수의 시작 부분으로 점프함.
• 함수는 매개변수를 비밀 글로벌 변수에서 읽고, 논리적으로 로컬 변수에 해당하는 사전 정의된 비밀 글로벌 변수를 사용함.
• 함수가 끝나면, 함수의 비밀 "반환 주소 변수"에 있는 주소로 점프함.

ABI 최적화

• ABI를 최적화하기 위해 일부 값을 글로벌 변수 대신 레지스터에 전달함.
• 대부분의 프로세서는 "링크" 레지스터와 "링크와 함께 분기" 명령어를 가지고 있어, 자동으로 링크 레지스터를 "링크와 함께 분기" 명령어 다음의 주소로 설정함.
• 첫 두 매개변수를 레지스터로 전달하는 호출 규약을 최적화함.

재귀 호출의 불가능성

• 재귀 호출은 작동하지 않음. 재귀 호출은 반환 주소 변수를 재귀 호출의 반환 주소로 덮어쓰기 때문에 외부 호출이 완료될 때 잘못된 위치로 점프함.
• 당시의 프로그래밍 언어는 재귀를 지원하지 않음을 선언하여 이 문제를 해결함.

보너스 대화

• 일부 컴파일러는 자기 수정 코드를 사용하여 더 교묘하게 작동함: 특별한 반환 주소 변수는 실제로 함수 끝의 점프 명령어의 주소 필드임.
• 프로세서가 간접 점프를 지원하지 않는 경우에는 이 방법이 실용적인 필요성으로 사용됨.
• 서브루틴의 실용적 가치가 인식된 후, 많은 프로세서는 서브루틴 호출 명령어를 추가하여 서브루틴의 첫 번째 단어에 반환 주소를 저장하고, 서브루틴의 두 번째 단어에서 실행을 시작함.
• 서브루틴에서 반환하기 위해 서브루틴 시작 레이블을 통한 간접 점프를 실행함.

GN⁺의 의견

• 이 기사는 초기 컴퓨팅 시대에 스택과 힙이 없었을 때의 프로그래밍 방식을 설명함으로써, 현대 소프트웨어 개발에 사용되는 메모리 관리 기법의 발전을 이해하는 데 도움을 줌.
• 스택과 힙이 없었던 시절의 프로그래밍 방식은 현대 개발자들에게는 매우 생소하고 비효율적으로 보일 수 있으나, 컴퓨팅의 역사를 통해 기술이 어떻게 발전해왔는지를 이해하는 데 중요한 배경 지식을 제공함.
• 재귀 호출이 불가능했던 시절의 프로그래밍 제약은 오늘날 재귀적 알고리즘을 사용하는 개발자들에게 흥미로운 역사적 사실을 제공함.
• 비판적인 시각에서 볼 때, 이러한 초기 프로그래밍 방식은 현대의 복잡하고 다양한 요구 사항을 충족시키기에는 매우 제한적이었음을 보여줌.

[neo]

Hacker News 의견

• "컴퓨터 프로그래밍의 예술" 책에 대한 긍정적인 평가

  • 이 책은 오래되어 보이지만, 힙(heap)이나 스택(stack) 이전의 다양한 동적 배열이나 데이터 구조를 변경하는 알고리즘을 다룸.
  • 책은 가비지 컬렉션과 Lisp 리스트 구현에 대해서도 설명하며, Knuth가 기대하게 만드는 백과사전 같은 지식을 제공함.

• 두 개의 배열이 하나의 공간을 동적으로 공유하는 방법에 대한 설명

  • 하나의 배열은 위치 #0에서 정상적으로 성장하고, 다른 하나는 위치 #End에서 거꾸로 성장하게 함으로써, 두 배열이 정적으로 할당된 공간을 효율적으로 공유함.
  • 이 방법은 여러 배열에 대해서 확장될 수 있지만, 그 지점에서는 Malloc과 Realloc을 사용하는 것이 더 나을 수 있음.

• ALGOL 언어에 재귀 함수를 도입하는 것이 논란의 여지가 있었던 재미있는 이야기 링크 제공

  • 재귀가 프로그래밍 언어에 어떻게 도입되었는지에 대한 흥미로운 역사를 담은 이야기를 링크를 통해 공유함.

• SUBLEQ 머신과 비트-직렬 머신을 위한 Forth 인터프리터 작성 경험 공유

  • 이 두 머신은 Forth의 필수 요소인 함수 호출 스택을 가지고 있지 않음.
  • SUBLEQ는 간접 로딩과 저장을 허용하지 않으며, 비일상적인 작업을 수행하기 위해 자기 수정 코드가 필요함.
  • 가상 머신을 구축하여 이러한 기능을 수행하고, 협력적 멀티스레딩을 지원함.
  • 필요한 경우 힙은 Forth로 작성되며, 소프트웨어 함수로 구현된 부동 소수점 연산도 포함됨.

• PDP-8 프로세서의 서브루틴 호출과 관련된 기술적 진화에 대한 설명

  • 초기에는 JMS 명령어가 함수의 첫 번째 단어에 반환 주소를 저장함.
  • 후에는 자동 증가 위치를 사용하여 간단한 스택을 만들고, 함수 프롤로그/에필로그가 이 스택을 수동으로 관리하여 완전한 재귀를 가능하게 함.
  • 나중에는 하드웨어 스택이 마이크로프로세서 구현에 추가되어 성능을 향상시킴.

• 함수형 프로그래밍 경험을 오랫동안 한 사용자의 재귀에 대한 선호도 공유

  • 재귀 알고리즘을 반복 알고리즘으로 변환하는 방법을 알고 있지만, 재귀를 선호함.
  • 대부분의 경우 재귀가 충분히 빠르며, 컴파일러가 꼬리 재귀를 지원하면 더욱 그러함.
  • 커먼도어 64 게임을 해킹하면서 과거에 어떻게 프로그래밍이 이루어졌는지 배우려고 노력함.

• 1991년경 RS232 시리얼 멀티플렉서 설계 경험 공유

  • Z80 프로세서, EPROM, Z80-SIO 시리얼 장치를 사용한 하드웨어 설계.
  • 스택이 없어서 함수 호출을 위해 레지스터 쌍에 반환 주소를 사전 로드하는 방식을 사용함.

• 힙이 확장 가능하기 전 프로그래머들이 입력의 가능한 분포를 고려하고 중간 저장소의 크기를 적절히 설정해야 했던 과거 상황에 대한 언급

  • 이로 인해 "버그와 한계"가 발생했음.

• 재귀를 사용할 수 없었던 시절, 꼬리 재귀는 가능했던 점에 대한 설명

  • 초기 호출에 사용된 branch_with_link 이외에는 일반 분기를 사용해야 했음.

• Enhanced GNU Awk에서 함수 외부에 있는 @let 블록에 대해 컴파일러가 비밀 글로벌 변수를 할당하는 방식 설명

  • 이러한 변수들은 가능한 한 많이 재사용됨.

• "Goto considered harmful" 논문의 세계를 묘사하는 포스트에 대한 언급

  • 대부분의 사람들은 제목만 알고 있으며, 논문은 서브루틴에 단일 진입점을 제공하는 것에 대해 주장함.
  • 때때로 어셈블리 코드를 다른 서브루틴으로 넘어가게 작성하지만, 모든 어셈블리 코드가 그렇게 되길 원하지는 않음.