추상 기계

컴퓨터 과학에서 추상 기계(抽象機械, abstract machine)는 컴퓨터 시스템이 어떻게 작동하는지에 대한 상세하고 정밀한 분석을 가능하게 하는 이론적 모델이다. 이는 미리 정의된 규칙에 따라 입력을 받고 출력을 생성한다는 점에서 수학적 함수와 유사하다. 추상 기계는 하드웨어와 독립적으로 올바르게 작동할 것으로 예상된다는 점에서 실제 기계와 다르다. 추상 기계는 프로그램의 단계별 실행을 허용하므로 "기계"이며, 실제 (하드웨어) 기계의 많은 측면을 무시하므로 "추상적"이다. 일반적인 추상 기계는 입력, 출력, 그리고 전자를 후자로 바꾸는 데 사용되는 허용된 연산의 집합에 대한 정의로 구성된다. 이들은 순전히 이론적인 이유뿐만 아니라 실제 컴퓨터 시스템의 모델로도 사용될 수 있다. 계산 이론에서 추상 기계는 종종 계산 가능성에 대한 사고 실험에 사용되거나 알고리즘의 복잡성을 분석하는 데 사용된다. 이러한 추상 기계의 사용은 유한 상태 기계, 밀리 기계, 푸시다운 자동 기계, 튜링 기계와 같은 계산 복잡도 이론 분야의 근본이다.

 분류 
추상 기계는 일반적으로 주어진 순간에 동시에 실행할 수 있는 연산의 양에 따라 두 가지 유형으로 분류된다: 결정론적 추상 기계와 비결정적 추상 기계. 결정론적 추상 기계는 특정 시작 상태 또는 조건이 항상 동일한 출력을 산출하는 시스템이다. 입력이 출력으로 변환되는 방식에는 무작위성이나 변동이 없다. 대조적으로, 비결정적 추상 기계는 다른 실행에서 동일한 입력에 대해 다양한 출력을 제공할 수 있다. 반복 횟수에 관계없이 동일한 입력에 대해 동일한 결과를 제공하는 결정론적 알고리즘과 달리, 비결정적 알고리즘은 다양한 경로를 통해 다른 출력에 도달한다. 비결정적 알고리즘은 결정론적 접근 방식을 사용하여 정확한 해법을 도출하기 어렵거나 비용이 많이 들 때 근사치를 얻는 데 유용하다.

섬네일|튜링 기계 실행
예를 들어, 튜링 기계는 컴퓨터 과학에서 가장 근본적인 추상 기계 중 하나이다. 이 기계는 임의 길이의 테이프(기호 문자열)에서 연산을 수행한다. 이들의 명령어는 기호를 수정하고 기계의 포인터가 현재 있는 기호를 변경하는 것을 모두 제공한다. 예를 들어, 기본적인 튜링 기계는 "기호를 1로 변환한 다음 오른쪽으로 이동"이라는 단일 명령을 가질 수 있으며, 이 기계는 1로 구성된 문자열만 생성할 것이다. 이 기본 튜링 기계는 결정론적이다. 그러나 동일한 입력에 대해 여러 작업을 실행할 수 있는 비결정론적 튜링 기계도 구축할 수 있다.

 구현 
추상 기계의 물리적 구현 (하드웨어)의 경우 어떤 구현이든 프로그래밍 언어의 명령을 실행하기 위해 어떤 종류의 물리적 장치 (기계적 또는 전자적)를 사용한다. 그러나 추상 기계는 추상 기계와 기본 물리적 장치 사이의 수준에서 소프트웨어 또는 펌웨어로도 구현될 수 있다.

 하드웨어 구현: 하드웨어에서 추상 기계를 직접 구현하는 것은 메모리 셀, 산술 및 논리 회로, 버스 등과 같은 물리적 장치를 사용하여 프로그래밍 언어와 기계어가 일치하는 물리적 기계를 구현하는 것이다. 일단 구축되면 그러한 기계를 변경하는 것은 사실상 어렵다. CPU는 추상 기계, 특히 프로세서 설계의 구체적인 하드웨어 구현으로 간주될 수 있다.

 소프트웨어 시뮬레이션: 소프트웨어로 추상 기계를 구현하는 것은 추상 기계가 필요로 하는 자료 구조와 알고리즘을 구현하기 위해 다른 프로그래밍 언어로 프로그램을 작성하는 것을 포함한다. 추상 기계 구성을 구현하는 프로그램을 쉽게 변경할 수 있으므로 가장 큰 유연성을 제공한다. 소프트웨어 시뮬레이션으로 구현되거나 인터프리터가 존재하는 추상 기계를 가상 머신이라고 한다.

 펌웨어 에뮬레이션: 펌웨어 구현은 하드웨어와 소프트웨어 구현 사이에 있다. 이는 추상 기계의 자료 구조와 알고리즘에 대한 마이크로코드 시뮬레이션으로 구성된다. 마이크로코드는 컴퓨터 프로그래머가 전자 회로를 제작할 필요 없이 기계 명령어를 작성할 수 있게 한다.

 프로그래밍 언어 구현 
추상 기계는 직관적으로 물리적 컴퓨터의 아이디어에 대한 추상화일 뿐이다. 실제 실행을 위해서는 알고리즘이 프로그래밍 언어가 제공하는 구성 요소를 사용하여 적절하게 형식화되어야 한다. 이는 실행할 알고리즘이 프로그래밍 언어 명령어를 사용하여 표현되어야 함을 의미한다. 프로그래밍 언어의 구문은 명령어라고 하는 유한한 구성 요소 집합을 사용하여 프로그램을 구성할 수 있게 한다. 대부분의 추상 기계는 프로그램 저장소와 상태를 공유하며, 이는 종종 스택과 레지스터를 포함한다. 디지털 컴퓨터에서 스택은 단순히 양의 정수만 셀 수 있는 주소 레지스터가 있는 메모리 셀이다 (초기 값이 로드된 후). 스택의 주소 레지스터는 항상 스택의 최상위 항목을 참조하기 때문에 스택 포인터라고 알려져 있다. 프로그램은 일련의 명령어로 구성되며, 스택 포인터는 다음에 수행할 명령어를 나타낸다. 명령어가 완료되면 스택 포인터가 증가한다. 추상 기계의 이러한 기본적인 제어 메커니즘은 실행 루프라고도 한다. 따라서 프로그래밍 언어를 위한 추상 기계는 프로그래밍 언어로 작성된 프로그램을 저장하고 실행할 수 있는 자료 구조와 알고리즘의 모든 컬렉션이다. 이는 컴파일을 위한 중간 언어 단계를 제공함으로써 고급 프로그래밍 언어와 실제 기계의 저급 사이의 간극을 메운다. 추상 기계의 명령어는 특정 소스 언어 또는 소스 언어 집합의 연산을 구현하는 데 필요한 고유한 연산에 맞게 조정된다.

 명령형 언어 
1950년대 후반 미국 컴퓨터 학회(ACM)와 기타 관련 단체는 콘웨이의 기계와 같은 범용 컴퓨터 지향 언어(UNCOL)에 대한 많은 제안을 개발했다. UNCOL 개념은 훌륭하지만, 생성된 코드의 성능이 좋지 않아 널리 사용되지 못했다. 1990년대 후반 자바 가상 머신이 개발되었음에도 불구하고, 컴퓨터 분야의 많은 영역에서 그 성능은 계속 문제가 될 것이다. 알골 객체 코드 (1964), P4-기계 (1976), UCSD P-기계 (1977), 포스 (1970)는 이러한 종류의 성공적인 추상 기계 중 일부이다.

 객체 지향 언어 
객체 지향 프로그래밍 언어를 위한 추상 기계는 종종 스택 기반이며 객체 필드 및 메서드에 대한 특별한 접근 명령어를 가지고 있다. 이 기계에서는 메모리 관리가 종종 쓰레기 수집기 (프로그래밍 언어에 내장된 메모리 회수 기능)에 의해 암묵적으로 수행된다. 스몰토크-80 (1980), 셀프 (1989), 자바 (1994)가 이러한 구현의 예시이다.

 문자열 처리 언어 
문자열 처리 언어는 숫자보다는 문자열 처리에 중점을 둔 컴퓨터 언어이다. 셸, 프로그래밍 도구, 일반 목적 매크로 프로세서, 스크립트 언어의 형태로 수십 년 동안 문자열 처리 언어가 존재해 왔다. 적절한 추상 기계를 사용하면 실행 속도 향상과 이식성 강화라는 두 가지 이점이 있다. 스노볼4와 ML/I는 기계 독립성을 얻기 위해 추상 기계를 사용하는 초기 문자열 처리 언어의 두 가지 주목할 만한 사례이다.

 함수형 프로그래밍 언어 
섬네일|크리빈 기계의 그림 표현
함수형 언어를 위한 초기 추상 기계는 SECD 머신 (1964)과 카델리의 함수형 추상 기계 (1983)를 포함하며, 엄격한 평가를 정의했는데, 이는 탐욕적 평가(eager evaluation) 또는 값에 의한 호출 평가로도 알려져 있다. 이 방식에서는 함수 인수가 호출 전에 정확히 한 번 평가된다. 최근에는 G-기계 (1984), 크리빈 기계 (1985), 세 명령어 기계 (1986)와 같이 함수 인수가 필요한 경우에만 최대 한 번 평가되는 느긋한 (또는 필요에 의한 호출) 평가에 대한 연구가 주로 이루어지고 있다. 한 가지 이유는 엄격한 평가의 효과적인 구현이 이제 잘 이해되어 추상 기계의 필요성이 줄어들었기 때문이다.

 논리형 언어 
술어 논리(1차 논리)는 논리형 프로그래밍 언어의 기초이다. 가장 잘 알려진 논리형 프로그래밍 언어는 프롤로그이다. 프롤로그의 규칙은 보편적으로 양화된 '혼 절(Horn clauses)'이라는 통일된 형식으로 작성되며, 이는 목표에 대한 증명을 찾으려는 계산을 시작하는 것을 의미한다. 프롤로그 프로그램 컴파일의 사실상 표준이 된 워렌 추상 기계 WAM (1983)이 대부분의 연구의 초점이었다. 이는 데이터 통합 명령어와 백트래킹(탐색 알고리즘)을 지원하는 제어 흐름 명령어와 같은 특수 목적 명령어를 제공한다.

 구조 
일반적인 추상 기계는 메모리와 인터프리터로 구성된다. 메모리는 데이터와 프로그램을 저장하는 데 사용되며, 인터프리터는 프로그램에 포함된 명령어를 실행하는 구성 요소이다.
섬네일|추상 기계의 구조
인터프리터는 해석하는 언어에 고유한 연산을 수행해야 한다. 그러나 다양한 언어를 고려할 때, 연산 범주와 모든 인터프리터가 공유하는 "실행 메커니즘"을 식별하는 것이 가능하다. 인터프리터의 연산과 관련 자료 구조는 다음 범주로 나뉜다.

 원시 데이터 처리를 위한 연산:
 연산의 실행 순서를 제어하기 위한 연산 및 자료 구조;
 데이터 전송을 제어하기 위한 연산 및 자료 구조;
 메모리 관리를 위한 연산 및 자료 구조.

 원시 데이터 처리 
추상 기계는 문자열 및 정수와 같은 원시 데이터 유형을 조작하기 위한 연산을 포함해야 한다. 예를 들어, 정수는 물리적 추상 기계와 많은 프로그래밍 언어에서 사용되는 추상 기계 모두에서 거의 보편적으로 기본 데이터 유형으로 간주된다. 기계는 덧셈과 곱셈과 같은 필요한 산술 연산을 단일 시간 단계 내에서 수행한다.

 순서 제어 
"순서 제어"를 위한 연산과 구조는 프로그램 명령어의 실행 흐름을 제어할 수 있게 한다. 특정 조건이 충족될 때 프로그램의 일반적인 순차적 실행을 변경해야 한다. 따라서 인터프리터는 데이터 조작에 사용되는 연산과 다른 연산(예: 다음에 실행할 명령어의 주소를 업데이트하는 연산)에 의해 수정되는 자료 구조(예: 다음에 실행할 명령어의 주소를 저장하는 데 사용되는 자료 구조)를 사용한다.

 데이터 전송 제어 
데이터 전송 연산은 피연산자와 데이터가 메모리에서 인터프리터로, 또는 그 반대로 어떻게 전송되는지를 제어하는 데 사용된다. 이러한 연산은 저장소 및 저장소에서 피연산자의 검색 순서를 다룬다.

 메모리 관리 
메모리 관리는 데이터와 애플리케이션을 할당하기 위해 메모리에서 수행되는 연산과 관련이 있다. 추상 기계에서는 데이터와 프로그램을 무기한으로 보유할 수 있거나, 프로그래밍 언어의 경우 더 복잡한 메커니즘을 사용하여 메모리를 할당하거나 해제할 수 있다.

 계층 

섬네일|추상 기계 계층 구조
추상 기계 계층 구조는 종종 사용되며, 각 기계는 바로 아래 수준의 기능을 사용하고 바로 위 수준을 충족하기 위해 자체적인 추가 기능을 추가한다. 하드웨어 컴퓨터는 물리적 전자 장치로 구성되며 가장 기본적인 수준에 추가될 수 있다. 이 수준 위에는 추상 마이크로 프로그램 기계 수준이 도입될 수 있다. 운영체제가 제공하는 추상 기계는 기계어로 작성된 프로그램에 의해 구현되며, 바로 위(펌웨어 수준이 없다면 하드웨어 바로 위)에 위치한다. 한편, 운영체제는 물리적 기계에는 없는 더 높은 수준의 원시 연산(예: 파일에 작용하는 원시 연산)을 제공함으로써 물리적 기계의 기능을 확장한다. 호스트 기계는 운영체제가 제공하는 추상 기계로 형성되며, 이 위에 자바 가상 머신과 그 바이트 코드 언어와 같은 중개 기계를 사용하여 고급 프로그래밍 언어가 구현된다. 고급 프로그래밍 언어를 위한 추상 기계가 제공하는 수준(예: 자바)은 일반적으로 계층 구조의 최종 수준이 아니다. 이 시점에서 하나 이상의 추가 서비스를 제공하는 애플리케이션이 함께 도입될 수 있다. 예를 들어, 웹 통신(통신 프로토콜 또는 HTML 코드 표현)을 처리하는 데 필요한 기능을 구현하기 위해 "웹 기계" 수준을 추가할 수 있다. "웹 서비스" 수준은 이 위에 위치하며, 상호 작용 프로토콜과 관련된 프로세스의 동작 측면 모두에서 웹 서비스가 통신하는 데 필요한 기능을 제공한다. 이 수준에서는 웹 서비스를 기반으로 소위 "비즈니스 프로세스"의 동작을 지정하는 완전히 새로운 언어가 개발될 수 있다(예시는 비즈니스 프로세스 실행 언어이다). 마지막으로, 가장 높은 수준에는 매우 구체적이고 제한된 기능을 가진 특화된 애플리케이션(예: 전자 상거래)이 있다.

 같이 보기 
 추상화 (컴퓨터 과학)
 이산시간
 상태공간

 각주 

 
분류:이산수학
분류:계산 이론
분류:계산 모형