오토마타 기반 프로그래밍
| 프로그래밍 패러다임 |
|---|
오토마타 기반 프로그래밍(Automata-based programming)은 프로그램 또는 프로그램의 일부가 유한 상태 기계(FSM) 또는 다른 (종종 더 복잡한) 형식 오토마톤의 모델로 생각되는 프로그래밍 패러다임이다. 때로는 잠재적으로 무한한 상태 집합이 도입되기도 하는데, 이러한 집합은 단순히 열거에 그치지 않고 복잡한 구조를 가질 수 있다.
유한 상태 기계 기반 프로그래밍은 일반적으로 동일하지만, 형식적으로는 모든 가능한 변형을 다루지는 않는다. FSM이 유한 상태 기계를 의미하며, 오토마타 기반 프로그래밍이 엄격한 의미에서 FSM을 반드시 사용하는 것은 아니기 때문이다.
다음 속성들은 오토마타 기반 프로그래밍의 핵심 지표이다.
- 프로그램 실행 시간은 오토마톤 단계로 명확하게 분리된다. 각 단계는 단일 진입점을 가진 코드 섹션(모든 단계에 대해 동일)의 효과적인 실행이다. 이 섹션은 다른 상태에 따라 실행되도록 하위 섹션으로 나눌 수 있지만, 이는 필수는 아니다.
- 오토마톤 단계 간의 모든 통신은 오토마톤 상태라고 명시적으로 표시된 변수 집합을 통해서만 가능하다. 두 단계 사이에서 프로그램은 지역 변수 값, 반환 주소, 현재 명령 포인터 등과 같은 상태의 암시적 구성 요소를 가질 수 없다. 즉, 오토마톤 단계에 진입하는 두 순간에 전체 프로그램의 상태는 오토마톤 상태로 간주되는 변수의 값에서만 다를 수 있다.
오토마타 기반 코드의 전체 실행은 오토마톤 단계의 주기이다.
오토마타 기반 프로그래밍의 개념을 사용하는 또 다른 이유는 이 기법에서 프로그램에 대해 생각하는 프로그래머의 사고방식이 튜링 기계, 마르코프 알고리즘 등을 사용하여 수학적 작업을 해결하는 데 사용되는 사고방식과 매우 유사하기 때문이다.
예시
[편집]작업
[편집]표준 입력에서 텍스트를 한 줄씩 읽어 각 줄의 첫 단어를 표준 출력에 쓰는 작업을 고려해 보자. 먼저 선행하는 공백 문자가 있으면 모두 건너뛴다. 그런 다음 첫 단어의 모든 문자를 출력한다. 마지막으로 새줄 문자가 나타날 때까지 후행 문자를 모두 건너뛴다. 스트림의 시작이 아닌 곳에서 새줄 문자 시퀀스가 나타나면 첫 번째만 출력하고 나머지는 건너뛴다. 그렇지 않으면 모두 건너뛴다. 다음으로 다음 줄에서 프로세스를 다시 시작한다. 파일 끝 조건이 발생하면(단계에 관계없이) 중지한다.
전통적인 프로그램
[편집]위 작업을 수행하는 C 언어의 전통적인 프로그램은 다음과 같을 수 있다.
#include <ctype.h>
#include <stdio.h>
int main(void) {
int c;
do {
do {
c = getchar();
} while (isspace(c));
while (!isspace(c) && c != EOF) {
putchar(c);
c = getchar();
}
while (c != '\n' && c != EOF) {
c = getchar();
}
if (c == '\n') {
putchar(c);
}
} while (c != EOF);
return 0;
}
예를 들어, 위 프로그램을 다음 입력으로 컴파일하고 실행하면:
$ clang program.c && (printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out)
다음과 같은 결과가 나온다.
foo
qux
오토마타 기반 프로그램
[편집]절차적
[편집]동일한 작업은 유한 상태 기계 관점에서 생각하여 해결할 수 있다. 한 줄의 파싱은 세 단계로 나뉜다. 선행 공백 문자를 건너뛰는 단계, 첫 번째 단어의 문자를 출력하는 단계, 그리고 후행 문자를 건너뛰는 단계이다. 이 상태들을 BEFORE, INSIDE, AFTER라고 부른다. 오토마타 기반 프로그램 버전은 다음과 같을 수 있다.
#include <ctype.h>
#include <stdio.h>
enum State {BEFORE, INSIDE, AFTER};
int main(void) {
int c;
enum State s = BEFORE;
while ((c = getchar()) != EOF) {
switch (s) {
case BEFORE:
if (!isspace(c)) {
putchar(c);
s = INSIDE;
}
break;
case INSIDE:
if (c == '\n') {
putchar(c);
s = BEFORE;
} else if (isspace(c)) {
s = AFTER;
} else {
putchar(c);
}
break;
case AFTER:
if (c == '\n') {
putchar(c);
s = BEFORE;
}
break;
}
}
return 0;
}
프로그램이 더 길어졌지만, 적어도 한 가지 중요한 장점이 있다. 읽기(즉, getchar 함수 호출) 명령이 하나뿐이다. 게다가 전통적인 버전이 네 개였던 루프 대신 루프가 하나뿐이다. while 루프의 본문은 오토마톤 단계이고, 루프 자체는 오토마톤 단계의 주기이다. 이 프로그램은 상태도에 표시된 유한 상태 기계의 작동을 구현한다.
이 프로그램의 가장 중요한 속성은 오토마톤 단계 코드 섹션이 명확하게 지역화되어 있다는 것이다. 오토마톤 단계를 위한 명시적인 step 함수를 사용하면 이 속성을 더 잘 보여준다.
#include <ctype.h>
#include <stdio.h>
enum State {BEFORE, INSIDE, AFTER};
void step(enum State* const s, int const c) {
switch (*s) {
case BEFORE:
if (!isspace(c)) {
putchar(c);
*s = INSIDE;
}
break;
case INSIDE:
if (c == '\n') {
putchar(c);
*s = BEFORE;
} else if (isspace(c)) {
*s = AFTER;
} else {
putchar(c);
}
break;
case AFTER:
if (c == '\n') {
putchar(c);
*s = BEFORE;
}
break;
}
}
int main(void) {
int c;
enum State s = BEFORE;
while ((c = getchar()) != EOF) {
step(&s, c);
}
return 0;
}
이제 프로그램은 오토마타 기반 코드의 기본 속성을 명확하게 보여준다.
- 오토마톤 단계 실행 시간은 겹치지 않을 수 있다.
- 이전 단계에서 다음 단계로 전달되는 유일한 정보는 명시적으로 지정된 오토마톤 상태이다.
유한 오토마톤은 상태 전이표로 정의될 수 있으며, 행은 현재 상태를 나타내고, 열은 입력을 나타내며, 셀은 다음 상태와 수행할 동작을 나타낸다.
입력 현재 상태
|
새줄 | 공백 | 기타 |
|---|---|---|---|
| 이전 | 이전 | 이전 | 내부/출력 |
| 내부 | 이전/출력 | 이후 | 내부/출력 |
| 이후 | 이전/출력 | 이후 | 이후 |
 |
일반적으로 오토마타 기반 프로그램은 이 접근 방식을 자연스럽게 사용할 수 있다. 상태 전이표를 위한 명시적인 2차원 배열 transitions를 사용하면 프로그램은 이 접근 방식을 사용한다.
#include <ctype.h>
#include <stdio.h>
enum State {BEFORE, INSIDE, AFTER};
void nop(int const c) {}
void print(int const c) {
putchar(c);
}
struct Branch {
enum State const next_state;
void (*action)(int);
};
struct Branch const transitions[3][3] = {
// newline whitespace other Inputs/States
{{BEFORE, &nop}, {BEFORE, &nop}, {INSIDE, &print}}, // before
{{BEFORE, &print}, {AFTER, &nop}, {INSIDE, &print}}, // inside
{{BEFORE, &print}, {AFTER, &nop}, {AFTER, &nop}} // after
};
void step(enum State* const s, int const c) {
int const row = (*s == BEFORE) ? 0 : (*s == INSIDE) ? 1 : 2;
int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
struct Branch const* const b = &transitions[row][column];
*s = b->next_state;
b->action(c);
}
int main(void) {
int c;
enum State s = BEFORE;
while ((c = getchar()) != EOF) {
step(&s, c);
}
return 0;
}
객체 지향
[편집]구현 언어가 객체 지향 프로그래밍을 지원한다면, 프로그램의 간단한 리팩토링은 오토마톤을 객체로 캡슐화하여 구현 세부 사항을 숨기는 것이다. 객체 지향 스타일을 사용하는 C++ 프로그램은 다음과 같을 수 있다.
#include <ctype.h>
#include <stdio.h>
enum State {BEFORE, INSIDE, AFTER};
struct Branch {
enum State const next_state;
void (*action)(int);
};
class StateMachine {
public:
StateMachine();
void feedChar(int);
protected:
static void nop(int);
static void print(int);
private:
enum State _state;
static struct Branch const _transitions[3][3];
};
StateMachine::StateMachine(): _state(BEFORE) {}
void StateMachine::feedChar(int const c) {
int const row = (_state == BEFORE) ? 0 : (_state == INSIDE) ? 1 : 2;
int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
struct Branch const* const b = &_transitions[row][column];
_state = b->next_state;
b->action(c);
}
void StateMachine::nop(int const c) {}
void StateMachine::print(int const c) {
putchar(c);
}
struct Branch const StateMachine::_transitions[3][3] = {
// newline whitespace other Inputs/States
{{BEFORE, &nop}, {BEFORE, &nop}, {INSIDE, &print}}, // before
{{BEFORE, &print}, {AFTER, &nop}, {INSIDE, &print}}, // inside
{{BEFORE, &print}, {AFTER, &nop}, {AFTER, &nop}} // after
};
int main() {
int c;
StateMachine m;
while ((c = getchar()) != EOF) {
m.feedChar(c);
}
return 0;
}
문서의 주제와 직접적으로 관련 없는 변경 사항을 최소화하기 위해 C 표준 라이브러리의 입출력 getchar 및 putchar 함수가 사용되고 있다.
상태 디자인 패턴은 객체가 대규모 조건문이나 테이블 검색에 의존하지 않고 가상 함수 호출 덕분에 내부 상태에 따라 런타임에 동작을 변경하는 방법이다. 대규모 조건문을 사용하는 코드에 비해 주요 장점은 상태별 코드가 단일 블록에 집중되지 않고 여러 객체에 분산되어 유지보수성이 향상된다는 것이다. 상태 전이표를 사용하는 코드에 비해 주요 장점은 가상 함수 호출이 테이블 검색보다 효율적인 경우가 많고, 상태 전이 기준이 표 형식보다 더 명시적이며, 상태 전이에 수반되는 동작을 추가하기가 더 쉽다는 것이다. 그러나 새로운 문제가 발생한다. 클래스 수가 코드의 압축성을 다른 접근 방식보다 떨어뜨린다. 상태 디자인 패턴을 사용하는 프로그램은 다음과 같을 수 있다.
#include <ctype.h>
#include <stdio.h>
class StateMachine;
class State {
public:
virtual void feedChar(StateMachine*, int) const = 0;
};
class Before: public State {
public:
static State const* instantiate();
virtual void feedChar(StateMachine*, int) const override;
protected:
Before() = default;
private:
static State const* _instance;
};
class Inside: public State {
public:
static State const* instantiate();
virtual void feedChar(StateMachine*, int) const override;
protected:
Inside() = default;
private:
static State const* _instance;
};
class After: public State {
public:
static State const* instantiate();
virtual void feedChar(StateMachine*, int) const override;
protected:
After() = default;
private:
static State const* _instance;
};
class StateMachine {
public:
StateMachine();
void feedChar(int);
protected:
void setState(State const*);
private:
State const* _state;
friend class Before;
friend class Inside;
friend class After;
};
State const* Before::instantiate() {
if (!_instance) {
_instance = new Before;
}
return _instance;
}
void Before::feedChar(StateMachine* const m, int const c) const {
if (!isspace(c)) {
putchar(c);
m->setState(Inside::instantiate());
}
}
State const* Before::_instance = nullptr;
State const* Inside::instantiate() {
if (!_instance) {
_instance = new Inside;
}
return _instance;
}
void Inside::feedChar(StateMachine* const m, int const c) const {
if (c == '\n') {
putchar(c);
m->setState(Before::instantiate());
} else if (isspace(c)) {
m->setState(After::instantiate());
} else {
putchar(c);
}
}
State const* Inside::_instance = nullptr;
State const* After::instantiate() {
if (!_instance) {
_instance = new After;
}
return _instance;
}
void After::feedChar(StateMachine* const m, int const c) const {
if (c == '\n') {
putchar(c);
m->setState(Before::instantiate());
}
}
State const* After::_instance = nullptr;
StateMachine::StateMachine(): _state(Before::instantiate()) {}
void StateMachine::feedChar(int const c) {
_state->feedChar(this, c);
}
void StateMachine::setState(State const* const s) {
_state = s;
}
int main() {
int c;
StateMachine m;
while ((c = getchar()) != EOF) {
m.feedChar(c);
}
return 0;
}
자동화와 오토마타
[편집]오토마타 기반 프로그래밍은 실제로 자동화 분야에서 발견되는 프로그래밍 요구 사항과 밀접하게 일치한다.
생산 주기는 일반적으로 다음과 같이 모델링된다.
- 입력 데이터(캡처 장치에서)에 따라 단계를 밟는 일련의 단계
- 현재 단계에 따라 수행되는 일련의 동작
다양한 전용 프로그래밍 언어는 이러한 모델을 다소 정교한 방식으로 표현할 수 있도록 한다.
자동화 프로그램
[편집]위에 제시된 예시는 다음 의사코드와 같이 이 관점에 따라 표현될 수 있다 ('set'은 논리 변수를 활성화하고, 'reset'은 논리 변수를 비활성화하며, ':'는 변수를 할당하고, '='는 동등성을 테스트한다).
newline: '\n'
whitespace: ('\t', '\n', '\v', '\f', '\r', ' ')
states: (before, inside, after)
setState(c) {
if before and (c != newline and c not in whitespace) then set inside
if inside then (if c in whitespace then set after else if c = newline then set before)
if after and c = newline then set before
}
doAction(c) {
if before and (c != newline and c not in whitespace) then write(c)
if inside and c not in whitespace then write(c)
if after and c = newline then write(c)
}
cycle {
set before
loop until (c: readCharacter) = EOL {
setState(c)
doAction(c)
}
}
사이클 진행을 표현하는 루틴과 실제 동작(입력 및 출력 일치)을 표현하는 루틴을 분리하면 더 명확하고 간단한 코드를 얻을 수 있다.
이벤트
[편집]자동화 분야에서는 단계별 진행이 기계 자체에서 오는 입력 데이터에 따라 달라진다. 이는 프로그램에서 텍스트에서 문자를 읽는 것으로 표현된다. 실제로는 이러한 데이터가 기계의 주요 요소의 위치, 속도, 온도 등을 알려준다.
GUI 프로그래밍에서와 마찬가지로, 기계 상태의 변경은 최종 상태에 도달할 때까지 한 상태에서 다른 상태로의 전환을 유발하는 이벤트로 간주될 수 있다. 가능한 상태의 조합은 다양한 이벤트를 생성하여 더 복잡한 생산 주기를 정의한다. 결과적으로 주기는 일반적으로 단순한 선형 시퀀스와는 거리가 멀다. 일반적으로 동시에 실행되는 병렬 분기와 다양한 이벤트에 따라 선택되는 대안이 있으며, 이는 아래에 개략적으로 표시되어 있다.
s:단계 c:조건
s1 | |-c2 | s2 | ---------- | | |-c31 |-c32 | | s31 s32 | | |-c41 |-c42 | | ---------- | s4
응용 분야
[편집]오토마타 기반 프로그래밍은 어휘 및 구문 분석에서 널리 사용된다.[1]
그 외에도 오토마타 관점에서 생각하는 것(즉, 실행 프로세스를 오토마톤 단계로 분해하고 명시적인 오토마톤 상태를 통해 단계별로 정보를 전달하는 것)은 병렬 프로세스나 스레드를 사용하는 유일한 대안으로서 사건 기반 프로그래밍에 필요하다.
상태 및 상태 기계의 개념은 형식 명세 분야에서 자주 사용된다. 예를 들어, UML 기반 소프트웨어 아키텍처 개발은 프로그램의 동작을 지정하기 위해 상태도를 사용한다. 또한 다양한 통신 프로토콜도 종종 명시적인 상태 개념을 사용하여 지정된다(예: RFC 793).
오토마타 관점(단계 및 상태)에서 생각하는 것은 일부 프로그래밍 언어의 의미를 설명하는 데에도 사용될 수 있다. 예를 들어, 레팔 언어로 작성된 프로그램의 실행은 소위 추상 레팔 기계의 단계 시퀀스로 설명된다. 기계의 상태는 뷰(변수 없는 임의의 레팔 표현식)이다.
스킴 언어의 연속은 스킴 자체가 오토마타와 전혀 관련이 없지만(재귀적이다) 단계와 상태의 관점에서 생각하는 것을 요구한다. call/cc 기능이 작동하도록 하려면 구현이 실행 중인 프로그램의 전체 상태를 포착할 수 있어야 하며, 이는 상태에 암시적인 부분이 없을 때만 가능하다. 이러한 포착된 상태가 바로 연속이라고 불리는 것이며, 이는 (상대적으로 복잡한) 오토마톤의 상태로 간주될 수 있다. 오토마톤 단계는 이전 연속에서 다음 연속을 추론하는 것이고, 실행 프로세스는 이러한 단계의 주기이다.
알렉산더 올롱그렌(Alexander Ollongren)은 그의 저서[2]에서 형식 오토마타에 전적으로 기반을 둔 프로그래밍 언어 의미론 기술의 소위 비엔나 방법을 설명한다.
STAT 시스템 [1]은 오토마타 기반 접근 방식을 사용하는 좋은 예시이다. 이 시스템은 다른 기능 외에도 순전히 오토마타 지향적인 STATL이라는 임베디드 언어를 포함한다.
역사
[편집]오토마타 기반 기술은 형식 언어 분석과 같은 오토마타 이론에 기반을 둔 알고리즘이 있는 영역에서 널리 사용되었다.[1]
이 분야의 초기 논문 중 하나는 존슨(Johnson) 외 공저, 1968년이다.[3]
오토마타 기반 프로그래밍이 일반적인 기술로 언급된 가장 초기의 사례 중 하나는 페테르 나우르의 1963년 논문에서 찾아볼 수 있다.[4] 저자는 이 기술을 튜링 기계 접근법이라고 부르지만, 논문에는 실제 튜링 기계가 주어지지 않았다. 대신 단계와 상태에 기반한 기술이 설명되어 있다.
명령형 및 절차적 프로그래밍과의 비교
[편집]상태의 개념은 오토마타 기반 프로그래밍만의 고유한 속성이 아니다.[5] 일반적으로 말해, 컴퓨터 프로그램의 실행 중에 변경될 수 있는 모든 정보의 조합으로서 상태(또는 프로그램 상태)가 나타난다. 예를 들어, 전통적인 명령형 프로그래밍 프로그램의 상태는 다음으로 구성된다.
이들은 명시적 부분(변수에 저장된 값 등)과 암시적 부분(반환 주소 및 명령어 포인터)으로 나눌 수 있다.
이러한 점을 고려할 때, 오토마타 기반 프로그램은 상태의 암시적 부분이 최소화된 명령형 프로그램의 특별한 경우로 간주될 수 있다. 단계 코드 섹션에 진입하는 두 개의 다른 순간에 취한 전체 프로그램의 상태는 오토마톤 상태에서만 다를 수 있다. 이는 프로그램 분석을 단순화한다.
객체 지향 프로그래밍 관계
[편집]객체 지향 프로그래밍 이론에서 객체는 내부 상태를 가지며 메시지를 수신하고, 응답하며, 다른 객체에 메시지를 보내고, 메시지 처리 중 내부 상태를 변경할 수 있다고 한다. 보다 실용적인 용어로, 객체의 메서드를 호출하는 것은 객체에 메시지를 보내는 것과 동일하게 간주된다.
따라서 한편으로 객체 지향 프로그래밍의 객체는 상태가 private 필드의 조합이고 하나 이상의 메서드가 단계로 간주되는 오토마타(또는 오토마타 모델)로 간주될 수 있다. 이러한 메서드는 직접 또는 간접적으로 서로 또는 자신을 호출해서는 안 된다. 그렇지 않으면 객체가 오토마타 기반 방식으로 구현된 것으로 간주될 수 없다.
다른 한편으로, 객체는 오토마톤 모델을 구현하는 데 적합하다. 오토마타 기반 접근 방식이 객체 지향 언어 내에서 사용될 때, 오토마톤 모델은 일반적으로 클래스로 구현되고, 상태는 클래스의 private 필드로 표현되며, 단계는 메서드로 구현된다. 이러한 메서드는 일반적으로 클래스의 유일한 비상수 공개 메서드이다(생성자 및 소멸자 제외). 다른 공개 메서드는 상태를 쿼리할 수 있지만 변경하지는 않는다. 모든 보조 메서드(특정 상태 핸들러 등)는 일반적으로 클래스의 private 부분 내에 숨겨진다.
같이 보기
[편집]각주
[편집]- ↑ 가 나 Aho, Alfred V.; Ullman, Jeffrey D. (1973). 《The theory of parsing, translation and compiling》 1. Englewood Cliffs, N. J.: Prentice-Hall. ISBN 0-13-914564-8.
- ↑ Ollongren, Alexander (1974). 《Definition of programming languages by interpreting automata》. London: Academic Press. ISBN 0-12-525750-3.
- ↑ Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (1968). 《Automatic generation of efficient lexical processors using finite state techniques》. 《Comm ACM》 11. 805–813쪽. doi:10.1145/364175.364185. S2CID 17253809.
- ↑ Naur, Peter (September 1963). 《The design of the GIER ALGOL compiler Part II》. 《BIT Numerical Mathematics》 3. 145–166쪽. doi:10.1007/BF01939983. S2CID 189785656.
- ↑ 《Automata-based programming》 (PDF). 《Scientific and Technical Journal of Information Technologies, Mechanics and Optics》. 2008.
외부 링크
[편집]- J. V. Noble. «Finite State Machines in Forth» — 포스 언어의 오토마타 기반 프로그래밍
- Harel, David (1987). 《Statecharts: A Visual Formalism for Complex Systems》 (PDF). 《Sci. Comput. Programming》 8. 231–274쪽. doi:10.1016/0167-6423(87)90035-9.
- Harel, David; Drusinsky, D. (1989). 《Using Statecharts for Hardware Description and Synthesis》. 《IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems》 8. 798–807쪽. doi:10.1109/43.31537. S2CID 8754800.
- Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus)
- ITMO 대학교, "프로그래밍 기술" 학과