Власне вся передмова помістилась в заголовок. Хоча може для цього “паттерну” є коротша назва.
Існує клас інтерактивних програм які очікують вводу користувача, потім залежно від того вводу щось роблять, потім знову очікують вводу і так далі. Наприклад якась така програма “вгадай число”:
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 за такими правилами:
- Кожен набір операторів що починається міткою ми записуємо в блок:
if (step == 1 /*мітка*/) {
// Код сюди
return;
};
- Кожне присвоєння відбувається в
scope:
if (...) {
scope.number = Math.floor(Math.random() * 10) + 1;
...
return;
};
- Кожен блок що закінчується
goto закінчується викликом exec:
if (...) {
// Код сюди
exec(4 /* куди послало goto */, scope);
return;
};
- Кожен блок що закінчується
if then:
if (...) {
// Код сюди
if (...) {
exec(3 /* куди послав then */, scope);
} else {
exec(11 /* перехід до наступного блоку */, scope);
}
return;
};
- Кожен блок що закінчується
input закінчується викликом exec для наступного кроку в callback:
if (...) {
// код сюди
CLI.on_input(function(input) {
scope.guess = input;
exec(5, scope);
});
return;
}
- Програма починається без змінних і з першого кроку:
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 
). Подивитись чи тести проходяться. Якщо не проходяться – значить ви неправильно зрозуміли як повинна працювати програма (і добре що ви це дізнались раніше поки ще є час зрозуміти її правильно), або вона працює неправильно (Співчуваю ви знайшли баг. Якщо ще не впевнені що зможете пофіксити – додайте в багтрекер.)
