맨위로가기

추상 기계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

추상 기계는 특정 시점에 수행할 수 있는 작업량에 따라 결정적 추상 기계와 비결정적 추상 기계로 분류되며, 컴퓨터 과학에서 튜링 기계가 대표적인 예시이다. 추상 기계는 하드웨어, 소프트웨어, 펌웨어로 구현될 수 있으며, 프로그래밍 언어를 실행하기 위해 필요한 자료 구조와 알고리즘을 포함한다. 프로그래밍 언어 구현 방식에 따라 명령형, 객체 지향, 문자열 처리, 함수형, 논리형 언어에 맞는 추상 기계가 존재하며, 메모리와 인터프리터로 구성된다. 추상 기계는 계층 구조를 이루어 하드웨어에서부터 운영체제, 가상 머신, 고급 프로그래밍 언어, 애플리케이션에 이르기까지 다양한 수준에서 구현될 수 있다.

더 읽어볼만한 페이지

  • 추상 기계 - 튜링 기계
    튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
  • 추상 기계 - MMIX
    MMIX는 256개의 64비트 범용 레지스터와 32개의 특수 목적 레지스터를 갖춘 RISC 아키텍처이며, 64비트 가상 주소 공간과 고정 길이 32비트 명령어를 사용한다.
  • 이산수학 - 고속 푸리에 변환
    고속 푸리에 변환(FFT)은 이산 푸리에 변환(DFT)을 효율적으로 계산하는 알고리즘으로, 연산 횟수를 줄여 디지털 신호 처리, 이미지 처리, 음향 분석 등 다양한 분야에 활용되며 쿨리-튜키 알고리즘 등이 대표적이다.
  • 이산수학 - 조합론
    조합론은 이산적인 대상의 개수를 세거나 조건을 만족하는 대상을 구성, 분류하는 수학 분야로, 순열, 조합에서 시작해 그래프 이론, 설계 이론 등 다양한 조합적 구조와 관련된 문제를 연구하며 여러 학문 분야에 응용된다.
  • 계산 이론 - 튜링 완전
    튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다.
  • 계산 이론 - 디지털 물리학
    디지털 물리학은 우주를 거대한 디지털 컴퓨터로 보고 정보 이론, 통계 역학, 양자역학 등을 융합하여 우주의 작동 방식을 디지털 계산 과정으로 설명하려는 이론적 관점이다.
추상 기계
개요
유형계산 모델
설명계산 과정을 추상적으로 정의한 가상 기계
상세 내용
특징실제 컴퓨터 아키텍처의 세부 사항을 숨김
프로그래밍 언어 의미론 정의 및 구현에 사용
예시튜링 기계
람다 계산법
페트리 네트
추상 구문 트리
상태 기계
활용
사용 목적프로그래밍 언어 구현
컴파일러 설계
프로그램 검증
관련 분야형식 검증
프로그램 분석
컴퓨터 과학

2. 분류

추상 기계는 특정 시점에 동시에 실행할 수 있는 작업량에 따라 일반적으로 결정적 추상 기계와 비결정적 추상 기계 두 가지 유형으로 분류된다.[2] 결정적 추상 기계는 특정 시작 상태나 조건이 항상 동일한 출력을 생성하는 시스템으로, 입력이 출력으로 변환되는 과정에 무작위성이나 변동이 없다.[5] 반면 비결정적 추상 기계는 동일한 입력에 대해 서로 다른 실행에서 다양한 출력을 제공할 수 있다.[2] 결정적 알고리즘은 반복 횟수에 관계없이 동일한 입력에 대해 동일한 결과를 제공하지만, 비결정적 알고리즘은 서로 다른 출력에 도달하기 위해 다양한 경로를 거친다.[6] 비결정적 알고리즘은 결정적 접근 방식으로는 정확한 솔루션을 도출하기 어렵거나 비용이 많이 드는 경우 근사적인 답을 얻는 데 유용하다.[7]

튜링 기계의 실행


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

일부 추상 기계는 계층적으로 분류할 수 있다. 여기서는 튜링 완전성을 가진 기계만을 대상으로 하며, 다음은 모든 것을 포함하는 것은 아니고, 이러한 분류 방식이 유일한 것도 아니다.

  • 직렬 계산 기계
  • 병렬 계산 기계


다음은 직렬 계산 기계만 해당한다.

  • 테이프 기반 - 튜링 기계의 변형 등
  • 단일 테이프, 다중 테이프 튜링 기계, 결정적 튜링 기계, 비결정적 튜링 기계, Wang B-머신, 포스트 튜링 머신, 오라클 머신, 보편 튜링 기계
  • 레지스터 기반 - 레지스터 머신
  • 카운터 머신, RAM (Random-Access Machine), RASP (Random-Access Stored-Program machine), 포인터 머신


레지스터 기반 각각에 대한 자세한 내용은 다음과 같다.

  • 카운터 머신
  • 주판 머신, Lambek 머신, Melzak 모델, 민스키 머신, Shepherdson-Sturgis 머신, 프로그램 머신
  • RAM (Random-Access Machine)
  • RASP (Random-Access Stored-Program machine)
  • 폰 노이만 머신
  • 포인터 머신
  • Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton
  • 범주적 추상 기계
  • 유한 오토마타
  • 프롤로그용 추상 기계
  • * 워렌 추상 기계
  • SECD 머신
  • [Ten15]
  • * [TenDRA 배포 형식]

3. 구현

추상 기계의 구현은 물리적 구현, 소프트웨어 및 펌웨어를 사용한 구현으로 나눌 수 있다.[9]


  • 하드웨어 구현: 하드웨어에서 추상 기계를 직접 구현하는 것은 메모리, 산술 및 논리 회로, 버스 등과 같은 물리적 장치를 사용하여 프로그래밍 언어와 일치하는 기계어를 가진 물리적 기계를 구현하는 것이다.[9] CPU는 특히 프로세서의 설계와 관련하여 추상 기계의 구체적인 하드웨어 구현으로 간주될 수 있다.[10]


SECD 머신과 같이, 보다 실용을 목적으로 한 추상 기계도 있다. 다른 예로는, OCaml의 기반인 Caml은 원래 categorical abstract machine(:en:Categorical abstract machine)이라는 추상 기계를 기반으로 한 구현이었기 때문에 그 이름이 붙었다.

4. 프로그래밍 언어 구현

추상 기계는 물리적 컴퓨터의 아이디어를 추상화한 것이다.[13] 실제 실행을 위해 알고리즘은 프로그래밍 언어가 제공하는 구성 요소를 사용하여 형식화되어야 한다. 프로그래밍 언어의 구문은 명령어 집합으로 프로그램을 구성한다. 대부분의 추상 기계는 프로그램 저장소와 상태를 공유하며, 스택과 레지스터를 포함한다.[9][14] 디지털 컴퓨터에서 스택은 양의 정수만 계산할 수 있는 주소 레지스터가 있는 메모리 장치이다. 스택 주소 레지스터는 스택 포인터라고 하며, 프로그램은 명령어 나열로 구성된다.[15] 스택 포인터는 다음 명령어를 나타내고, 명령 완료 후 증가한다. 이러한 제어 메커니즘은 실행 루프라고 한다.[3]

프로그래밍 언어 추상 기계는 프로그래밍 언어 프로그램을 저장, 실행하는 자료 구조 및 알고리즘 집합이다. 고급 언어와 저급 기계 사이를 컴파일 중간 언어로 연결한다. 추상 기계 명령어는 특정 소스 언어나 집합 연산 구현에 필요한 고유 연산에 맞춰져 있다.[9]

4. 1. 명령형 언어

1950년대 후반, 계산기학회(ACM)와 다른 관련 단체들은 범용 컴퓨터 지향 언어(UNCOL)에 대한 많은 제안을 개발했으며, 여기에는 콘웨이의 기계가 포함되었다. UNCOL 개념은 좋았지만 생성된 코드의 성능 저하로 인해 널리 사용되지 않았다. 컴퓨팅의 많은 분야에서 1990년대 후반 자바 가상 머신의 개발에도 불구하고 성능 문제는 계속될 것이다. Algol 객체 코드 (1964), P4-머신 (1976), UCSD P-머신 (1977) 및 포스 (1970)는 이러한 종류의 성공적인 추상 기계의 예이다.[3]

4. 2. 객체 지향 언어

객체 지향 프로그래밍 언어를 위한 추상 기계는 스택 기반 메모리 할당 방식을 사용하는 경우가 많으며, 객체 필드 및 메서드에 대한 특별한 접근 명령어를 갖는다. 이러한 기계에서 메모리 관리는 프로그래밍 언어에 내장된 메모리 회수 기능인 가비지 컬렉션에 의해 암묵적으로 수행되는 경우가 많다.[16] 스몰토크-80, 셀프(1989), 자바(1994)는 이러한 구현의 예시이다.[3]

4. 3. 문자열 처리 언어

문자열 처리 언어는 숫자가 아닌 문자열 처리에 중점을 둔 컴퓨터 언어이다. 명령 셸, 프로그래밍 도구, 범용 매크로 프로세서, 스크립트 언어 등 다양한 형태로 수십 년 동안 존재해 왔다.[17] 적절한 추상 기계를 사용하면 실행 속도 증가와 이식성 향상이라는 두 가지 이점을 얻을 수 있다. 스노볼4와 ML/I는 추상 기계를 사용하여 기계 독립성을 확보한 초기 문자열 처리 언어의 대표적인 예이다.[3]

4. 4. 함수형 언어

크리빈 기계의 그림 표현


함수형 프로그래밍 언어를 위한 초기 추상 기계에는 SECD 기계(1964)와 카델리의 함수형 추상 기계(Functional Abstract Machine, 1983)가 있으며, 이들은 엄격한 평가(strict evaluation)를 정의했다. 이는 평가 전략에서 조급 또는 값 호출(call-by-value) 평가로도 알려져 있다.[3] 이는 함수 인자가 호출 전에 정확히 한 번 평가되는 방식이다. 최근 연구는 주로 느긋한(또는 필요에 의한 호출, call-by-need) 평가에 집중되어 왔으며,[18] G-machine(1984), 크리빈 기계(1985), Three Instruction Machine(1986) 등이 있다. 이들 기계에서는 함수 인자가 필요할 때만, 그리고 최대 한 번 평가된다. 그 이유는 엄격한 평가의 효과적인 구현이 현재 잘 이해되어 있어 추상 기계의 필요성이 줄어들었기 때문이다.[3]

4. 5. 논리형 언어

술어 논리(일차 논리)는 논리 프로그래밍 언어의 기초이다. 가장 잘 알려진 논리 프로그래밍 언어는 프롤로그이다. 프롤로그의 규칙은 보편적으로 정량화된 '혼 절'이라고 알려진 통일된 형식으로 작성되며, 이는 목표의 증명을 발견하려는 계산을 시작하는 것을 의미한다. 워렌 추상 기계(WAM) (1983년)[3]는 프롤로그 프로그램 컴파일의 사실상의 표준이 되었으며, 대부분 연구의 초점이었다. 이는 백트래킹(검색 알고리즘)을 지원하기 위해 데이터 통합 지침 및 제어 흐름 지침과 같은 특수 목적 지침을 제공한다.[19]

5. 구조

일반적인 추상 기계는 메모리와 인터프리터로 구성된다. 메모리는 데이터와 프로그램을 저장하는 데 사용되며, 인터프리터는 프로그램에 포함된 명령을 실행하는 구성 요소이다.[9]

추상 기계의 구조


인터프리터는 인터프리팅하는 프로그래밍 언어 고유의 연산을 수행해야 한다. 그러나 다양한 언어를 고려할 때, 모든 인터프리터가 공유하는 연산 범주와 "실행 메커니즘"을 식별하는 것이 가능하다. 인터프리터의 연산과 관련 데이터 구조는 다음 범주로 나뉜다:[9][20]

# 기본 데이터 처리를 위한 연산

# 연산의 실행 순서를 제어하기 위한 연산 및 데이터 구조

# 데이터 전송을 제어하기 위한 연산 및 데이터 구조

# 메모리 관리를 위한 연산 및 데이터 구조

6. 계층 구조

추상 기계의 계층 구조


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

7. 기타



이론 컴퓨터 과학 혹은 주로 계산 이론이 이와 관련된 주요 분야이지만, 실제 컴퓨터에의 응용 등도 있다. 다른 "기계 같지 않은" 계산 모델도 포함하는 일반적인 논의는 그쪽을 참조하라.

튜링 머신의 제안과 같이, 계산 가능성 이론에서도 사용되지만, 레지스터 머신의 기사에 있는 것과 같이, 실제 컴퓨터에 비교적 가까운 추상 기계는 계산 복잡성 이론이나, 또는 보다 현실적인 실제 컴퓨터에서의 계산량 논의에 사용하기 쉽다는 특징이 있다.

한 예로, 튜링 머신에서의 테이프는 읽고 쓰고 싶은 목적지까지 한 칸씩 이동시켜야 하며, 조금이라도 복잡한 것을 하면 필요한 단계 수가 방대해진다. 따라서 실제 컴퓨터에서 사용하는 알고리즘의 계산량 검토에는 튜링 머신은 적합하지 않다. 이에 비해, 예를 들어 random-access machine의 머리글자를 딴 "RAM"이라는 추상 기계는 이름 그대로 메모리에 임의 접근, 즉 메모리의 어느 곳이든 일정 단계로 읽고 쓸 수 있다.

캐시 메모리 등, 기억의 계층의 단계가 증가하고 있는 최근에는 빠른 메모리를 최대한 사용하는 것이 고속화의 열쇠가 되고 있으며, 계산량에 대한 논의도 그것을 고려해야 할 필요가 있는 경우도 있다. 그것을 고려한 추상 기계의 필요성도 있을 수 있다.

SECD 머신과 같이, 보다 실용을 목적으로 한 추상 기계도 있다. 다른 예로는, OCaml의 기반인 Caml은, 원래 categorical abstract machine이라는 추상 기계를 기반으로 한 구현이었기 때문에 그 이름이 붙었다(후에 다른 추상 기계를 기반으로 대폭 개조되었다). 그러한 추상 기계와 "가상 머신"이라는 단어가 가리키는 것과의 차이는 어느 정도 불분명하다. 명확하게 구분하는 것은 불가능하지만, 추상보다는 구체에 가까운 쪽이 가상 머신이라고 할 수 있을 것이다(역사적인 이유로, 가상 머신(virtual machine)이라는 단어는 전혀 무관하지는 않지만 서로 다른 두 종류의 것을 가리키게 되었다. 영어판 virtual machine에서 system virtual machine이 아닌 process virtual machine으로 하고 있는 쪽이, 여기서 논의하고 있는 쪽이다).

참조

[1] 웹사이트 Abstract Machine https://mathworld.wo[...] 2022-05-16
[2] 웹사이트 What is an Abstract Machine? http://www.easytechj[...] 2022-05-16
[3] 논문 Abstract machines for programming language implementation https://linkinghub.e[...] 2000-05
[4] 웹사이트 9.1.1: Finite-State Machine Overview https://eng.libretex[...] 2021-04-29
[5] 웹사이트 What is Deterministic System? - Definition from Techopedia http://www.techopedi[...] 2019-08-29
[6] 논문 Deterministic versus nondeterministic time and lower bound problems http://dx.doi.org/10[...] 2003-01
[7] 논문 Non-determinism: An abstract concept in computer science studies http://dx.doi.org/10[...] 2007-12
[8] 논문 Computational Complexity of Probabilistic Turing Machines http://epubs.siam.or[...] 1977-12
[9] 간행물 Abstract Machines http://link.springer[...] Springer London 2022-05-16
[10] 보고서 Hardware Evaluation: Abstract Machine Models and Proxy Architectures for Exascale Computing http://dx.doi.org/10[...] U.S. Department of Energy Office of Scientific and Technical Information 2018-02-01
[11] 웹사이트 abstract machine from FOLDOC http://foldoc.org/Ab[...] 2021-08-07
[12] 서적 Proceedings of the 19th annual workshop on Microprogramming ACM Press 1986
[13] 웹사이트 abstract machine https://www.oxfordre[...] 2022-05-16
[14] Conference Proceedings of Pattern Languages of Programs '99 1999-08-15
[15] 웹사이트 Computer Organization and Architecture (Stack Organization) - UPSC FEVER http://upscfever.com[...] 2022-05-31
[16] 웹사이트 What is Object-Oriented Programming (OOP)? https://www.techtarg[...] 2022-05-31
[17] 간행물 Design considerations for string processing languages http://dx.doi.org/10[...] Springer Berlin Heidelberg 2022-05-31
[18] 논문 Call-by-need is clairvoyant call-by-value 2019-07-26
[19] 웹사이트 Prolog {{!}} An Introduction https://www.geeksfor[...] 2022-05-31
[20] 논문 Distilling abstract machines https://dl.acm.org/d[...] 2014-11-26
[21] 웹사이트 Introduction to Java Primitives {{!}} Baeldung https://www.baeldung[...] 2022-05-31
[22] 간행물 Interpreter Auerbach Publications 2004


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com