Monthly Archives: Квітень 2016

Проста схема перетворення інтерактивної процедурної програми з goto в функціональну рекурсивну

Власне вся передмова помістилась в заголовок. Хоча може для цього “паттерну” є коротша назва.

Існує клас інтерактивних програм які очікують вводу користувача, потім залежно від того вводу щось роблять, потім знову очікують вводу і так далі. Наприклад якась така програма “вгадай число”:

import random

def game():
    print('Як тебе звуть?')
    user = input()

    print('Привіт,', user)
    print('Давай пограємо гру відгадай число?')

    while True:
        number = random.randint(1, 10)
        print('Я загадав число від 1 до 10.')
        print('Спробуєш вгадати?')

        while True:
            print('Вводь свій варіант:')
            guess = input()
            if guess == number:
                print('Ого, так швидко вгадав. Грати ще раз?')
                while True:
                    answer = input()
                    if answer in ('так', 'ні'):
                        break
                    print('Ну то так чи ні?');

                if (answer == 'ні'):
                    print('Ну тоді бувай!')
                    return
                if (answer == 'так'):
                    break
            else:
                print('Ні, моє число ' +
                    ('більше' if (scope.guess < scope.number) else 'менше')
                    + ', пробуй ще'
                )
game()

JavaScript має з такими програмами проблему, бо він ніколи не зупиняється очікуючи на ввід користувача (якщо не рахувати функції alert() та компанії, він викликає функції які обробляють події, як от подію вводу. Щоб написати подібну програму для браузера, ми повинні реалізувати в ньому щось на зразок “консолі”:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" />
</head>
<body>
    <pre id="console"></pre>
    <input type="text" id="input" />

<script>
(function() {
    var input = document.getElementById('input');
    var output = document.getElementById('console');

    var write = function(text) {
        // Write text to console
        output.innerHTML += text;
    };
    var writeln = function(text) {
        // Write line to console
        write(text + 'n');
    };
    
    // Register default callback of echoing input
    var input_callbacks = [function(input) {
        writeln('> ' + input);
    }];

    var on_input = function(callback) {
        // Register input callback

        input_callbacks[1] = callback;
    }

    input.onkeyup = function(e) {
        // Call all callbacks on input
        if (e.keyCode == 13) { // Enter pressed
            for(var i=0; i < input_callbacks.length; i++) {
                input_callbacks[i](input.value);
            }
            input.value = '';
        }
    };

    // Module exports:
    window.CLI = {
        write: write,
        writeln: writeln,
        on_input: on_input
    };
}());
</script>

<script>
// Ну а тут буде наша програма для "консолі". 
</script>
</body>
</html>

Ми маємо модуль CLI, який містить три функції. write та writeln дописують до елемента “консоль” переданий їм текст, а функція передана в on_input, буде викликатись отримуючи вміст елемента input коли в ньому натиснуть Enter. Проблема якраз в тому що буде викликатись окрема функція, якій передадуть ввід, і нема функції яка б той ввід просто повернула. Як написати для такої консолі інтерактивну гру “вгадай число”?

Тут на допомогу може прийти цікаве визначення алгоритму, яке я знайшов в книжці “Мистецтво програмування” Дональда Кнута (ні, я її не осилив, не зміг запам’ятати набір інструкцій MIX, хоча може варто пошукати якийсь емулятор цієї машини, щоб та книжка веселіше проходилась).

Так от, Кнут пише що будь-яку програму можна задати фунцією P(step, scope), яка приймає набір аргументів scope (що може бути одним аргументом – словником). Таким чином ми уникаємо зміни стану і оператора присвоєння, викликаючи функцію рекурсивно з новини аргументами.

Тому наприклад таку програму написану на бейсікоподібному псевдокоді:

    i = 0
1:  writeln i
    i = i + 1
    goto 1

Можна переписати на JavaScript рекурсивно так:

    function exec(step, scope) {
        CLI.writeln(scope.i);
        exec(step, {i: scope.i+1});
    }

    exec(1, {x: 0});

Варто також зауважити що JavaScript не має оптимізації хвостової рекурсії, тому така програма в Firefox зупиняється вивівши число 11085, і пожалівшись в консоль повідомленням “too much recursion”.

Тобто правило таке – як тільки ми хочемо змінити стан – ми викликаємо нашу функцію яка задає програму передавши їй цей новий стан. Ми також можемо робити умовні і безумовні переходи, викликаючи нашу функцію з різними значеннями параметра step. Подивимось як ми зможемо переписати програму гри “вгадай число”, яку описали вище на JavaScript. Але для цього спершу перепишемо її на наш діалект BASIC:

1:  writeln 'Як тебе звуть?'
    input user
2:  writeln 'Привіт,' + user
    writeln 'Давай пограємо гру "Відгадай число"?'
3:  writeln 'Я загадав число від 1 до 10.'
    number = randint(1, 10)
    writeln 'Спробуєш вгадати?'
4:  writeln 'Вводь свій варіант:'
    input guess
5:  if guess == number then 9
6:  if guess < number then 8
7:  writeln 'Ні, моє число менше, пробуй ще' 
    goto 4
8:  writeln 'Ні, моє число більше, пробуй ще'
    goto 4
9:  writeln 'Ого, так швидко вгадав. Грати ще раз?')
    input answer
10: if anwser == 'так' then 3
11: if answer == 'ні' then 13
12: writeln 'Ну то так чи ні?'
    input answer
    goto 10
13: writeln 'Ну тоді бувай!'

Тепер переписуємо цю програму на JavaScript за такими правилами:

  1. Кожен набір операторів що починається міткою ми записуємо в блок:
    if (step == 1 /*мітка*/) {
        // Код сюди
        return;
    };
    
  2. Кожне присвоєння відбувається в scope:
    if (...) {
        scope.number = Math.floor(Math.random() * 10) + 1;
        ...
        return;
    };
    
  3. Кожен блок що закінчується goto закінчується викликом exec:
    if (...) {
        // Код сюди
        exec(4 /* куди послало goto */, scope);
        return;
    };
    
  4. Кожен блок що закінчується if then:
    if (...) {
        // Код сюди
        if (...) {
            exec(3 /* куди послав then */, scope);
        } else {
            exec(11 /* перехід до наступного блоку */, scope);
        }
        return;
    };
    
  5. Кожен блок що закінчується input закінчується викликом exec для наступного кроку в callback:
    if (...) {
        // код сюди
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    }
    
  6. Програма починається без змінних і з першого кроку:
    exec(1, {});
    

Таким чином з “бейсіка” на JavaScript програму можна переписати так:

function exec(step, scope) {
    // 1:  writeln 'Як тебе звуть?'
    //     input user
    if (step == 1) {
        CLI.writeln('Як тебе звуть?');
        CLI.on_input(function(input) {
            scope.user = input;
            exec(2, scope);
        });
        return;
    };
    // 2:  writeln 'Привіт,' + user
    //     writeln 'Давай пограємо гру "Відгадай число"?'
    if (step == 2) {
        CLI.writeln('Привіт, ' + scope.user);
        CLI.writeln('Давай пограємо гру "Відгадай число"?');
        exec(3, scope);
        return;
    };
    // 3:  writeln 'Я загадав число від 1 до 10.'
    //     number = randint(1, 10)
    //     writeln 'Спробуєш вгадати?'
    if (step == 3) {
        CLI.writeln('Я загадав число від 1 до 10.');
        scope.number = Math.floor(Math.random() * 10) + 1;
        CLI.writeln('Спробуєш вгадати?');
        exec(4, scope);
        return;
    };
    // 4:  writeln 'Вводь свій варіант:'
    //     input guess
    if (step == 4) {
        CLI.writeln('Вводь свій варіант:');
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    };
    // 5:  if guess == number then 9
    if (step == 5) {
        if (scope.guess == scope.number) {
            exec(9, scope)
        } else {
            exec(6, scope)
        };
        return;
    };

    // 6:  if guess < number then 8
    if (step == 6) {
        if (scope.guess < scope.number) {
            exec(8, scope)
        } else {
            exec(7, scope)
        };

        return;
    };

    // 7:  writeln 'Ні, моє число менше, пробуй ще' 
    //     goto 4
    if (step == 7) {
        CLI.writeln('Ні, моє число менше, пробуй ще');
        exec(4, scope)
        return;
    };

    // 8:  writeln 'Ні, моє число більше, пробуй ще'
    //     goto 4
    if (step == 8) {
        CLI.writeln('Ні, моє число більше, пробуй ще');
        exec(4, scope)
        return;
    };

    // 9:  writeln 'Ого, так швидко вгадав. Грати ще раз?')
    //     input answer
    if (step == 9) {
        CLI.writeln('Ого, так швидко вгадав. Грати ще раз?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(10, scope);
        });
        return;
    };

    // 10: if anwser == 'так' then 3
    if (step == 10) {
        if (scope.answer == 'так') {
            exec(3, scope)
        } else {
            exec(11, scope)
        };

        return;
    };

    // 11: if answer == 'ні' then 13
    if (step == 11) {
        if (scope.answer == 'ні') {
            exec(13, scope)
        } else {
            exec(12, scope)
        };
        return;
    };

    // 12: writeln 'Ну то так чи ні?'
    //     input answer
    //     goto 10
    if (step == 12) {
        CLI.writeln('Ну то так чи ні?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(10, scope);
        });
        return;
    };

    // 13: writeln 'Ну тоді бувай!'
    if (step == 13) {
        CLI.writeln('Ну тоді бувай!');
        CLI.on_input(function() {}); 
        return;
    };
}

exec(1, {});

Можна звісно коротше, якщо робити умовний оператор без переходів в інший блок:

function exec(step, scope) { 
    console.log(step, scope);
    if (step == 1) {
        CLI.writeln('Як тебе звуть?');
        CLI.on_input(function(input) {
            scope.user = input;
            exec(2, scope);
        });
        return;
    }
    if (step == 2) {
        CLI.writeln('Привіт,' + scope.user);
        CLI.writeln('Давай пограємо гру відгадай число?');
        exec(3, scope);
        return;
    }
    if (step == 3) {
        CLI.writeln('Я загадав число від 1 до 10.');
        scope.number = Math.floor(Math.random() * 10) + 1;
        CLI.writeln('Спробуєш вгадати?');
        exec(4, scope);
        return;
    }
    if (step == 4) {
        CLI.writeln('Вводь свій варіант:');
        CLI.on_input(function(input) {
            scope.guess = input;
            exec(5, scope);
        });
        return;
    }
    if (step == 5) {
        if (scope.guess == scope.number) {
            CLI.writeln('Ого, так швидко вгадав. Грати ще раз?')
            CLI.on_input(function(input) {
                scope.answer = input;
                exec(6, scope);
            });
            return;
        }
        CLI.writeln('Ні, моє число ' +
            (scope.guess < scope.number ? 'більше': 'менше')
            + ', пробуй ще');
        exec(4, scope);
        return;
    }
    if (step == 6) {
        if (scope.answer == 'так') {
            exec(3, scope);
            return;
        }
        if (scope.answer == 'ні') {
            CLI.writeln('Ну тоді бувай!');
            CLI.on_input(function(){});
            return;
        }
        CLI.writeln('Ну то так чи ні?');
        CLI.on_input(function(input) {
            scope.answer = input;
            exec(6, scope);
        });
        return;
    }

};

exec(1, {});

Які з цього висновки? Ми можемо уникнути зайвих вкладень якщо нам треба зробити ланцюзок колбеків – запит, обробка відповіді, новий запит що залежить від результатів, обробка відповіді і т.д. Головне, аби це не був ланцюжок з тисяч колбеків, бо нарвемось на переповнення стеку. Тоді доведеться писати власну оптимізацію хвостової рекурсії.


Filed under: Кодерство Tagged: книжки, JavaScript, розробка, Python