برنامه‌نویسی مبتنی بر اتوماتا

برنامه‌نویسی مبتنی بر اتوماتا (به انگلیسی: Automata-based programming) یک الگوی برنامه‌نویسی است که در آن کل برنامه یا بخشی از آن به صورت مدلی از ماشین حالات متناهی (FSM) یا دیگر اتوماتاهای قراردادی دیگر (که اغلب پیچیده‌تر هستند) تصور می‌شود (نظریه اتوماتا را ببینید).

برنامه‌نویسی مبتنی بر اتوماتیک

اتوماتای بر اساس برنامه‌نویسی نمونه‌ای از برنامه‌نویسی می‌باشد که برنامه و قسمت‌های مختلف آن سعی بر این دارند تا یک ماشین متناهی را مدل کنند.

برنامه‌نویسی مبتنی بر FSM

برنامه‌نویسی مبتنی بر FSM نیز مانند برنامه‌نویسی مبتنی بر اتوماتیک می‌باشد با این تفاوت که تمامی جنبه‌های ماشین متناهی را پوشش نمی‌دهد.

مشخصه‌های برنامه‌نویسی مبتنی بر اتوماتیک

موارد زیر مشخصه‌های برنامه‌نویسی مبتنی بر اتوماتیک است:

۱-زمان اجرای برنامه به وضوح از مراحل اتوماتا جدا می‌باشد. ۲-ارتباط میان مراحل فقط از طریق رفتن از یک وضعیت به وضعیت دیگر می‌باشد.

تمام مراحل اجرای یک اتومات به‌طور کلی یک چرخهٔ اتوماتا را می‌گویند.

مثال

برنامه‌ای در زبان C را در نظر که یک متن را از ورودی می‌خواند، خط به خط کلمه اول هر خط را چاپ می‌کند.

روش سنتی برنامه‌نویسی C

برنامه زیر می‌تواند مورد بالا را به روش سنتی برنامه‌نویسی C انجام بدهد:

# include <stdio.h>
int main(void)
{
    int c;
    do {
        c = getchar();
        while(c == ' ')
            c = getchar();
        while(c != EOF && c != ' ' && c != '\n') {
            putchar(c);
            c = getchar();
        }
        putchar('\n');
        while(c != EOF && c != '\n')
            c = getchar();
    } while(c != EOF);
    return 0;
}

روش برنامه‌نویسی مبتنی بر اتوماتیک

همان کاری که برنامه قبل انجام میداد را می‌توانیم با ماشین متناهی انجام دهیم.توجه داشته باشید که تجزیه خطوط سه مرحله دارد :

1- عبور کردن از space ها

2- چاپ کردن کلمه

3- گذر از همهٔ حروف کلمه

برنامه به شکل زیر می‌باشد :

      #include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        switch(state) {
            case before:
                if(c == '\n') {
                    putchar('\n');
                } else
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                switch(c) {
                    case ' ':  state = after; break;
                    case '\n':
                        putchar('\n');
                        state = before;
                        break;
                    default:   putchar(c);
                }
                break;
            case after:
                if(c == '\n') {
                    putchar('\n');
                    state = before;
                }
        }
    }
    return 0;
}

اگرچه برنامه طولانی به نظر می‌رسد اما مزیت آن این است که فقط یک دستور خواندن دارد و همچنین تنها یک حلقه در برنامه وجود دارد نه 4 عدد.

کاملاً لازم نیست کد را به گرداننده‌ها ی جدا برای‌ها وضعیت تقسیم کنیم.برنامهٔ زیر همان کار برنامهٔ بالا را انجام می‌دهد با این تفاوت که یک مقدار کوتاه‌تر است.

        #include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        if(c == '\n') {
            putchar('\n');
            state = before;
        } else
        switch(state) {
            case before:
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                if(c == ' ') {
                    state = after;
                } else {
                    putchar(c);
                }
                break;
            case after:
                break;
        }
    }
    return 0;
}

تابعی جدا برای مرحله ی اتوماتیک

مهمترین ویژگی برنامه قبل این است که کد مرحله اتوماتیک به صورت محلی تعریف شده‌است. با یک تابع جدا برای این قسمت ما بهتر می‌توانیم این ویژگی را اثبات کنیم.

#include <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
    if(c == '\n') {
        putchar('\n');
        *state = before;
    } else
    switch(*state) {
        case before:
            if(c != ' ') {
                putchar(c);
                *state = inside;
            }
            break;
        case inside:
            if(c == ' ') {
                *state = after;
            } else {
                putchar(c);
            }
            break;
        case after:
            break;
    }
} 
int main(void)
{
    int c;
    enum states state = before;
    while((c = getchar()) != EOF) {
        step(&state, c);
    }
    return 0;
}

این مثال به‌طور کامل ویژگی کد مبتنی بر اتوماتا را ثابت می‌کند.

جدول انتقال صریح و روشن

یک اتوماتای متناهی می‌تواند به‌طور صریح و روشن توسط جدول انتقال بیان شود. در برنامه زیر جدولی وجود دارد که برای هر ترکیب جدول شامل یک وضعیت جدید و یک پرچم می‌باشد.

#include <stdio.h>
enum states { before = 0, inside = 1, after = 2 };
struct branch {
    unsigned char new_state:2;
    unsigned char should_putchar:1;
};
struct branch the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
void step(enum states *state, int c)
{
    int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
    struct branch *b = & the_table[*state][idx2];
    *state = (enum states)(b->new_state);
    if(b->should_putchar) putchar(c);
}

اتوماتا و اتوماسیون برنامه‌نویسی مبتنی بر متن نشان دهندهٔ مطابقت میان برنامه‌نویسی و اتوماسیون می‌باشد.

یک چرخهٔ تولید به‌طور کلی به صورت زیر مدل می‌شود.

1.مجموعه‌ای از مراحل که با ورودی مطابقت دارد.

2.مجموعه‌ای از کارها که با حالت کنونی مطابقت دارد.

برنامه ی نمونه

برنامه‌ای که در بالا ارائه شد از این دیدگاه به صورت زیر بیان می‌شود.

SPC : ' '
EOL : '\n'
 
states : (before, inside, after, end)
 
setState(c) {
    if c=EOF then set end
    if before and (c!=SPC and c!=EOL) then set inside
    if inside and (c=SPC or c=EOL) then set after
    if after and c=EOL then set before
}
 
doAction(c) {
    if inside then write(c)
    else if c=EOL then write(c)
}
 
cycle {
    set before
    loop {
        c : readCharacter
        setState(c)
        doAction(c)
    }
    until end
}

اوتوماسیون و رویدادها

در رشتهٔ اوتوماسیون از یک مرحله به مرحلهٔ دیگر رفتن به این بستگی دارد که چه حروفی به دستگاه وارد می‌شود. این می‌تواند این‌گونه ارائه شود که حروف از یک فایل متنی خوانده شود و به ترتیب وارد دستگاه شود. در واقع این اطلاعات در مورد مکان، سرعت، دما و دیگر عناصر حیاطی دستگاه می‌باشد.

مانند یک برنامه‌نویسی گرافیکی شاخه‌هایی وجود دارند که با یکدیگر اجرا می‌شوند که به صورت زیر می‌توان آن‌ها را نشان داد.

s:stage   c:condition
  
  s1
  |
  |-c2
  |
  s2
  |
  ----
  |        |
  |-c31    |-c32
  |        |
 s31       s32
  |        |
  |-c41    |-c42
  |        |
  ----
  |
  s4

استفاده از ویژگی‌های شی گرا

اگر زبان برنامه‌نویسی از ویژگی‌های شی گرایی استفاده کند می‌توان اوتومات‌ها را به صورت یک شی در نظر گرفت. با این کار چگونگی پیاده‌سازی آن و جزئیات آن پنهان می‌شود.

به عنوان مثال یک نسخه از برنامه‌ای که در بالا گفته شد با استفاده از ویژگی‌های شی گرایی به صورت زیر نوشته می‌شود.

#include <stdio.h>
class StateMachine {
    enum states { before = 0, inside = 1, after = 2 } state;
    struct branch {
        enum states new_state:2;
        int should_putchar:1;
    };
    static struct branch the_table[3][3];
public:
    StateMachine() : state(before) {}
    void FeedChar(int c) {
        int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
        struct branch *b = & the_table[state][idx2];
        state = b->new_state;
        if(b->should_putchar) putchar(c);
    }
};
struct StateMachine::branch StateMachine::the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
int main(void)
{
    int c;
    StateMachine machine;
    while((c = getchar()) != EOF)
        machine.FeedChar(c);
    return 0;
}

کاربردها

اوتوماتای مبتنی بر برنامه‌نویسی به صورت گسترده‌ای در تحلیل لغوی و گرامری استفاده می‌شود.

در نظریهٔ اوتوماتیک فکر نیز می‌تواند مورد استفاده قرار بگیرد.

اوتومات‌های مبتنی بر برنامه‌نویسی برای توصیف معانی بعضی از زبان‌های برنامه‌نویسی مورد استفاده قرار میگیرد.

تاریخجه

تکنیک مبتنی بر اوتومات‌ها به صورت گسترده‌ای در الکوریتم‌ها و نظریهٔ اوتوماتیک استفاده می‌شود. مثل تحلیل زبان‌های با قاعده.

یکی از ابتدایی‌ترین مقاله‌ها در این زمینه در سال 1968 چاپ شد.

اولین جایی که از اوتومات‌های مبتنی در برنامه‌نویسی به عنوان یک تکنیک عمومی نام برده شده‌است در سال 1963 توسط پیتر نور بود که نویسنده آن را تکنیک تورینگ ماشین نام‌گذاری کرده بود.

بیشتر بخوانید

Nondeterministic programming

State pattern

Esterel

Umple

منابع

• ویکی‌پدیای انگلیسی