추상 기계

Abstract machine
가상 시스템과 혼동하지 마십시오.

추상 기계는 컴퓨터 시스템이 어떻게 [1]기능하는지에 대한 상세하고 정확한 분석을 가능하게 하는 컴퓨터 과학 이론 모델입니다.이 기능은 입력을 수신하고 사전 정의된 규칙에 따라 출력을 생성한다는 점에서 수학 함수와 유사합니다.추상 시스템은 하드웨어와 [2]독립적으로 올바르게 수행되어야 한다는 점에서 리터럴 시스템과 다릅니다.추상 머신은 프로그램을 단계별로 실행할 수 있기 때문에 "머신"이며, 실제(하드웨어) [3]머신의 많은 측면을 무시하기 때문에 "추상"입니다.전형적인 추상 기계는 입력, 출력 및 전자를 후자로 변환하기 위해 사용되는 일련의 허용 연산에 관한 정의로 구성됩니다.그것들은 이론적인 이유뿐만 아니라 실제 컴퓨터 [2]시스템의 모델에도 사용될 수 있습니다.계산 이론에서, 추상 기계는 계산 가능성과 관련된 사고 실험이나 [3]알고리즘의 복잡성을 분석하기 위해 종종 사용된다.추상 기계의 이러한 사용은 유한 상태 기계, 밀리 기계, 푸시다운 오토마타, 튜링 [4]기계와 같은 계산 복잡성 이론의 분야와 연결되어 있다.


분류

추상 기계는 일반적으로 한 번에 수행할 수 있는 작업의 수에 따라 결정론적 추상 기계와 비결정론적 추상 기계의 [2]두 가지 유형으로 분류됩니다.결정론적 추상 기계는 특정 시작 상태 또는 조건이 항상 동일한 출력을 생성하는 시스템입니다.입력이 [5]출력으로 변환되는 방법에는 랜덤성이나 변동이 없습니다.한편, 비결정론적 추상 기계는 다른 [2]실행에서 동일한 입력에 대해 다양한 출력을 제공할 수 있다.반복 횟수에 관계없이 동일한 입력에 대해 동일한 결과를 제공하는 결정론적 알고리즘과는 대조적으로, 비결정론적 알고리즘은 다른 [6]출력에 도달하기 위해 다양한 경로를 사용합니다.비결정론적 알고리즘은 결정론적 접근방식을 사용하여 정확한 해결책을 도출하는 것이 어렵거나[7] 비용이 많이 드는 경우 대략적인 답을 얻는 데 도움이 된다.

튜링 머신의 동작.

예를 들어 튜링 기계는 컴퓨터 과학에서 [2]가장 기본적인 추상 기계 중 하나이다.임의의 길이의 테이프(기호열)를 조작할 수 있는 기계입니다.이 메뉴얼에는, 기호의 수정과 그 기초가 되는 기호의 변경에 관한 순서가 기재되어 있습니다.기본적인 튜링 컴퓨터의 단일 명령어는 "기호를 1로 변환한 후 오른쪽으로 이동"이며, 이 기계는 [8]1s의 문자열만 생성합니다.이 기본적인 튜링 기계는 결정론적이지만, 동일한 입력이 주어졌을 때 여러 가지 동작을 실행할 수 있는 비결정론적 튜링 기계도 [2]만들어질 수 있다.

추상 머신의 실장

(하드웨어에서의) 물리적인 실장의 경우 추상적인 머신의 실장은 프로그래밍 언어의 명령을 실행하기 위해 물리적인 디바이스(기계적, 전자적 등)를 사용합니다.그러나 추상 머신은 추상 머신과 기초가 되는 물리 [9]디바이스의 중간 레벨에서 소프트웨어 또는 펌웨어로 구현될 수도 있습니다.

  • 소프트웨어를 사용한 시뮬레이션:소프트웨어를 사용하여 추상 머신을 구현하려면 추상 머신에 필요한 데이터 구조 및 알고리즘을 구현하기 위해 다른 언어로 프로그램을 작성해야 합니다.이는 추상적인 기계 구조를 구현하는 프로그램을 쉽게 [9]변경할 수 있기 때문에 최대의 유연성을 제공합니다.소프트웨어 시뮬레이션으로 구현되거나 인터프리터가 존재하는 추상 머신을 가상 [11]머신이라고 합니다.

프로그래밍 언어 구현

"기계"라는 용어는 컴퓨터가 "이해할" 정도로 충분히 공식화된 알고리즘을 실행하는 물리적 기계인 컴퓨팅 기계를 말합니다.추상 기계는 직관적으로 물리적 [13]컴퓨터의 개념을 추상화한 것에 지나지 않습니다.실제 실행을 위해서는 프로그래밍 언어가 제공하는 구성을 사용하여 알고리즘을 적절하게 공식화해야 합니다.이는 실행할 알고리즘이 프로그래밍 언어 [3]명령을 사용하여 표현되어야 함을 의미합니다.프로그래밍 언어의 구문은 명령으로 알려진 유한한 구성 집합을 사용하여 프로그램을 구성할 수 있도록 합니다.대부분의 추상 기계는 프로그램 스토어와 상태를 공유하며, 여기에는 종종 스택과 [9][14]레지스터가 포함됩니다.디지털 컴퓨터에서 스택은 단순히 (초기 값이 로드된 후) 양의 정수만 셀 수 있는 주소 레지스터가 있는 메모리 장치입니다.스택의 주소 레지스터는 값이 항상 [15]스택의 상위 항목을 참조하기 때문에 스택 포인터라고 불립니다.이 프로그램은 일련의 명령으로 구성되며, 스택 포인터는 수행할 다음 명령을 나타냅니다.명령이 완료되면 스택 포인터가 진행됩니다.추상 머신의 이 기본적인 제어 메커니즘은 실행 [3]루프라고도 합니다.따라서 프로그래밍 언어를 위한 추상 기계는 프로그래밍 언어로 작성된 프로그램을 저장하고 실행할 수 있는 데이터 구조 및 알고리즘의 집합입니다.컴파일을 위한 중간 언어 단계를 제공함으로써 프로그래밍 언어의 높은 수준과 실제 기계의 낮은 수준 사이의 갭을 메운다.추상기계의 명령은 특정 소스 언어 또는 소스 [9]언어 집합의 연산을 구현하기 위해 필요한 고유한 연산에 맞게 조정됩니다.

명령형 프로그래밍 언어

1950년대 후반, 컴퓨터 기계 협회(ACM)와 다른 제휴 조직들은 Conway의 기계와 같은 Universal Computer Oriented Language(UNCOL)에 대한 많은 제안서를 개발했습니다.UNCOL 개념은 좋지만 생성된 코드의 성능이 좋지 않아 널리 사용되지 않습니다.컴퓨팅의 많은 분야에서 1990년대 [16]후반 Java Virtual Machine의 개발에도 불구하고 그 성능은 계속 문제가 될 것입니다.Algol Object Code(1964), P4-machine(1976), UCSD P-machine(1977) 및 Forth(1970)는 이러한 종류의 [3]성공한 추상 머신입니다.

객체 지향 프로그래밍 언어

객체 지향 프로그래밍 언어용 추상 머신은 스택 기반이며 객체 필드 및 메서드에 대한 특별한 액세스 명령이 있습니다.이러한 머신에서는, 메모리 관리는, 가비지 콜렉터에 의해서 암묵적으로 행해집니다(메모리 리커버리 기능은 프로그래밍 [17]언어에 짜넣어져 있습니다).이 구현의 예는 Smalltalk-80(1980), Self(1989), Java([3]1994)입니다.

문자열 처리 언어

문자열 처리 언어는 숫자보다는 문자열 처리에 초점을 맞춘 컴퓨터 언어입니다.수십 [18]년 동안 명령 셸, 프로그래밍 도구, 매크로 프로세서 및 스크립트 언어의 형태로 문자열 처리 언어가 존재해 왔습니다.적절한 추상 머신을 사용하면 실행 속도 향상과 휴대성 향상이라는 두 가지 이점이 있습니다.Snobol4와 ML/I는 추상 머신을 사용하여 머신의 [3]독립성을 얻는 초기 문자열 처리 언어의 두 가지 주목할 만한 인스턴스입니다.

기능 프로그래밍 언어

Krivine 머신의 그림 표현.

SECD 머신(1964)과 Cardelli의 Functional Abstract Machine(1983)을 포함한 기능언어의 초기 추상기계는 엄격한 평가를 정의했습니다.이러한 평가에서는 호출 전에 함수 인수를 정확하게 1회 평가하기도 합니다.[3]최근 몇 년 동안 대부분의 연구는 G-기계(1984년), Krivine 기계(1985년), Three Instruction Machine(1986년)와 같은 게으른([19]또는 요구에 의한 콜) 평가에 관한 것이었다.이러한 평가에서는 함수 인수는 필요한 경우에만 그리고 최대 한 번에 평가된다.한 가지 이유는 엄격한 평가의 효과적인 실시가 현재 잘 이해되고 있기 때문에 추상적인 기계의 필요성이 [3]줄어들었기 때문이다.

로직 프로그래밍 언어

술어 미적분(일차 논리)은 논리 프로그래밍 언어의 기초입니다.가장 잘 알려진 논리 프로그래밍 언어는 프롤로그입니다.프롤로그의 규칙은 보편적으로 수량화된 '호른 조항'으로 알려진 통일된 형식으로 작성되며, 이는 목표의 증거를 발견하기 위한 계산을 시작하는 것을 의미합니다.프롤로그 프로그램 편집에서 사실상의 표준이 된 Warren [3]Abstract Machine WAM(1983)은 대부분의 연구에 초점이 맞춰져 왔다.데이터 통합 지침 및 흐름 제어 지침과 같은 특수 목적 지침을 제공하여 역추적(검색 알고리즘)[20]을 지원합니다.

추상 기계의 구조

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

추상 기계의 구조

통역자는 통역하는 언어에 고유한 작업을 수행해야 합니다.그러나 언어의 다양성을 고려할 때, 모든 통역자가 공유하는 "실행 메커니즘"과 운영 범주를 식별할 수 있다.통역사의 운영과 그에 수반되는 데이터 구조는 다음과 같은 [9][21]범주로 분류된다.

  1. 원시 데이터 처리 작업:
  2. 작업 실행 순서를 제어하기 위한 작업 및 데이터 구조
  3. 데이터 전송을 제어하기 위한 운영 및 데이터 구조
  4. 메모리 관리를 위한 작업 및 데이터 구조.

원시 데이터 처리 작업

추상 머신도 알고리즘을 실행함으로써 동작하기 때문에 문자열이나 [9]정수 등의 원시 데이터 타입을 조작하기 위한 연산을 포함해야 합니다.예를 들어 정수(정수 또는 실수)는 물리 추상 머신과 많은 프로그래밍 언어에 사용되는 추상 머신 모두에 대해 거의 보편적으로 기본 데이터로 간주됩니다.기계는 필요한 다른 산술 연산(더하기, 곱하기 등)[22]을 즉시 수행합니다.

시퀀스 제어를 위한 운영 및 데이터 구조

"시퀀스 제어"를 위한 조작과 구조를 통해 프로그램 명령의 실행 흐름을 제어할 수 있습니다.특정 조건이 충족되면 프로그램의 [9]일반적인 순차 실행을 변경해야 합니다.따라서 인터프리터는 데이터 구조(다음 실행 명령의 주소를 저장하기 위해 사용되는 것 등)를 채용하고 있습니다.데이터 구조(예를 들어 다음 실행 [23]명령의 주소를 갱신하기 위한 조작)는 데이터 조작에 사용되는 것과 다릅니다.

데이터 전송을 제어하기 위한 운영 및 데이터 구조

데이터 전송 연산은 오퍼랜드와 데이터가 메모리에서 인터프리터로 전송되는 방법을 제어하기 위해 사용됩니다.이러한 작업은 스토어 [9]및 스토어에서 오퍼랜드의 검색 순서를 처리합니다.

메모리 관리를 위한 운영 및 데이터 구조

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

추상 머신의 계층

추상 머신의 계층

추상 머신 계층은 종종 채용됩니다.각 머신은 바로 아래 레벨의 기능을 사용하고,[9] 바로 위의 레벨을 만족시키기 위해서 독자적인 기능을 추가합니다.물리적 전자 장치로 구성된 하드웨어 컴퓨터는 가장 기본적인 수준에서 추가할 수 있습니다.이 레벨 이상으로, 추상적인 마이크로 프로그래밍 머신 레벨이 도입될 수 있습니다.운영체제에서 제공하는 추상기계는 기계어로 작성된 프로그램으로 구현되며, 바로 위(또는 펌웨어 레벨이 [9][24]없는 경우 하드웨어 바로 위)에 있습니다.한편, operating system은, 물리 머신에서는 사용할 수 없는 상위 레벨의 프리미티브(예를 들면, 파일에 동작하는 프리미티브)를 제공해, 물리 머신의 기능을 확장합니다.호스트 머신은 운영체제가 제공하는 추상 머신에 의해 형성되며, Java Virtual 머신과 그 바이트 코드 [16][25]언어와 같은 중간 머신을 사용하여 고급 프로그래밍 언어가 구현됩니다.고급 언어(예: Java)에 대해 추상 머신에 의해 주어진 수준은 일반적으로 계층의 최종 수준이 아닙니다.이 시점에서 추가 서비스를 함께 제공하는 응용 프로그램이 하나 이상 도입될 수 있습니다.예를 들어, 웹 통신(통신 프로토콜 또는 HTML 코드 표시)을 처리하는 데 필요한 기능을 구현하기 위해 "웹 머신" 수준을 추가할 수 있습니다."웹 서비스" 레벨은 이 위에 위치하며, 상호 작용 프로토콜 [26]및 관련된 프로세스의 동작 측면에서 웹 서비스를 통신시키는 데 필요한 기능을 제공합니다.이 레벨에서는, Web 서비스에 근거하는 이른바 「비즈니스 프로세스」의 동작을 지정하는 완전히 새로운 언어가 개발될 가능성이 있습니다(예를 들면, 비즈니스 프로세스 실행 언어).마지막으로, 특수 애플리케이션은 매우 [9]구체적이고 제한된 기능을 가진 최고 수준(예: 전자상거래)에서 찾을 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Weisstein, Eric W. "Abstract Machine". mathworld.wolfram.com. Retrieved 2022-05-16.
  2. ^ a b c d e f "What is an Abstract Machine?". EasyTechJunkie. Retrieved 2022-05-16.
  3. ^ a b c d e f g h i j Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (May 2000). "Abstract machines for programming language implementation". Future Generation Computer Systems. 16 (7): 739–751. doi:10.1016/S0167-739X(99)00088-6.
  4. ^ "9.1.1: Finite-State Machine Overview". Engineering LibreTexts. 2021-04-29. Retrieved 2022-05-31.
  5. ^ "What is Deterministic System? - Definition from Techopedia". Techopedia.com. Retrieved 2022-05-30.
  6. ^ Stearns, Richard E. (January 2003). "Deterministic versus nondeterministic time and lower bound problems". Journal of the ACM. 50 (1): 91–95. doi:10.1145/602382.602409. ISSN 0004-5411. S2CID 2194820.
  7. ^ Armoni, Michal; Gal-Ezer, Judith (December 2007). "Non-determinism: An abstract concept in computer science studies". Computer Science Education. 17 (4): 243–262. Bibcode:2007CSEd...17..243A. doi:10.1080/08993400701442885. ISSN 0899-3408. S2CID 41928460.
  8. ^ Gill, John (December 1977). "Computational Complexity of Probabilistic Turing Machines". SIAM Journal on Computing. 6 (4): 675–695. doi:10.1137/0206049. ISSN 0097-5397.
  9. ^ a b c d e f g h i j k l m n o Gabbrielli, Maurizio; Martini, Simone (2010), "Abstract Machines", Programming Languages: Principles and Paradigms, London: Springer London, pp. 1–25, doi:10.1007/978-1-84882-914-5_1, ISBN 978-1-84882-913-8, retrieved 2022-05-16
  10. ^ Bair, Ray; Chien, Andrew; Cook, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, John; Vetter, Jeff (2018-02-01). "Hardware Evaluation: Abstract Machine Models and Proxy Architectures for Exascale Computing". doi:10.2172/1733300. OSTI 1733300. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  11. ^ "abstract machine from FOLDOC". foldoc.org. Retrieved 2021-08-07.
  12. ^ Gee, J.; Melvin, S. W.; Patt, Y. N. (1986). "The implementation of Prolog via VAX 8600 microcode". Proceedings of the 19th Annual Workshop on Microprogramming - MICRO 19. New York, New York, USA: ACM Press: 68–74. doi:10.1145/19551.19538. ISBN 081860736X. S2CID 3846072.
  13. ^ "abstract machine". Oxford Reference. Retrieved 2022-05-16.
  14. ^ García-Martín, Julio Manuel; Sutil-Martin, Miguel (1999-08-15). "A Pattern for Designing Abstract Machines". doi:10.13140/RG.2.1.3680.5203. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  15. ^ upscfever.com (2017-01-25). "Computer Organization and Architecture (Stack Organization) - UPSC FEVER". upscfever.com. Retrieved 2022-05-31.
  16. ^ a b Tyson, Matthew (2020-01-17). "What is the JVM? Introducing the Java Virtual Machine". InfoWorld. Retrieved 2022-05-31.
  17. ^ "What is Object-Oriented Programming (OOP)?". SearchAppArchitecture. Retrieved 2022-05-31.
  18. ^ "Design considerations for string processing languages", A Study in String Processing Languages, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 205, pp. 17–37, 1985, doi:10.1007/3-540-16041-8_2, ISBN 978-3-540-16041-0, retrieved 2022-05-31
  19. ^ Hackett, Jennifer; Hutton, Graham (2019-07-26). "Call-by-need is clairvoyant call-by-value". Proceedings of the ACM on Programming Languages. 3 (ICFP): 1–23. doi:10.1145/3341718. ISSN 2475-1421. S2CID 195782686.
  20. ^ "Prolog An Introduction". GeeksforGeeks. 2018-05-26. Retrieved 2022-05-31.
  21. ^ Accattoli, Beniamino; Barenbaum, Pablo; Mazza, Damiano (2014-11-26). "Distilling abstract machines". ACM SIGPLAN Notices. 49 (9): 363–376. doi:10.1145/2692915.2628154. ISSN 0362-1340. S2CID 234775413.
  22. ^ baeldung (2018-01-11). "Introduction to Java Primitives Baeldung". www.baeldung.com. Retrieved 2022-05-31.
  23. ^ "Interpreter", Software Architecture Design Patterns in Java, Auerbach Publications, 2004-04-27, doi:10.1201/9780203496213.ch34, ISBN 978-0-8493-2142-9, retrieved 2022-05-31
  24. ^ "Hardware vs Software vs Firmware: What's the Difference?". Lifewire. Retrieved 2022-05-31.
  25. ^ Accattoli, Beniamino; Barras, Bruno (2017-10-09). "Environments and the complexity of abstract machines". Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming. Namur Belgium: ACM: 4–16. doi:10.1145/3131851.3131855. ISBN 978-1-4503-5291-8. S2CID 11953081.
  26. ^ "Web Services". reference.wolfram.com. Retrieved 2022-05-31.
  27. ^ D. B. Skillicorn (2005). Foundations of Parallel Programming. Cambridge University Press. p. 18. ISBN 978-0-521-01856-2.

추가 정보

  • Peter van Emde Boas, 기계 모델 및 시뮬레이션 페이지 3-66에 나오는 내용:
얀 반 리우웬, ed. "이론 컴퓨터 과학 핸드북"A권: 알고리즘과 복잡성, MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2(볼륨 A). QA 76.H279 1990