Языки и методы программирования - лекция-4: вычислитель, принимающий решения: ветвление программы

Лекция курса "Языки и методы программирования"
Лекция-4: вычислитель, принимающий решения: ветвление программы
- Эпоха механических автоматов: механические калькуляторы, программируемые шарманки
- Как машина может сделать выбор?
- Ответ Чарльза Бэббиджа
- Механизмы ветвления и принятия решений на современных архитектурах на примере MIPS32
- Последовательное выполнение программы инструкция за инструкцией: счетчик программы Program Counter
- Ветвление программы: команда j (jump — прыжок)
- Принятие решений: команда beq (branch if equal — ответвиться, если равно)
- Пример программы: игра «угадай сумму»
- Запуск примера в среде MARS MIPS

Transcript

1. Вычислитель, принимающий решения: ветвление программы
2. • К первой половине XIX века люди научились делать не только прототипы механических вычислителей, • но и начали выпускать их массовые коммерческие варианты • Они умели складывать и вычитать • Некоторые: умножать и делить (при помощи дополнительных приставок)
5. • Серьезный недостаток таких устройств — они выполняли только одну операцию за «подход» • Для того, чтобы сначала сложить два числа, а потом вычесть из 3-го числа результат, оператор должен быть вручную перенастроить аппарат • Если бы кто-то придумал способ, как сделать так, чтобы автомат умел выполнять произвольную заранее определенную последовательность математических операций, это было бы серьезным повышением производительности вычислительного труда
7. • Вариант для следующего шага: соединить программируемую «автоматику шарманок» и вычислительную механику арифмометров • Но была проблема поинтереснее
8. Как машина может сделать выбор? Один из видных итальянских математиков того времени, профессор Мосотти обратился к Бэббиджу во время его пребывания в Италии по поводу следующего затруднения. «Он заметил, что теперь вполне готов поверить в способность механизма овладеть арифметическими и даже алгебраическими соотношениями в любой нужной степени. Но он добавил что не может понять, как машина может сделать выбор, который часто необходим при аналитическом исследовании (то есть в процессе вычислений), когда представляются два или более путей, особенно в том случае, когда правильный путь, как это часто бывает, неизвестен до тех пор, пока не проделаны предшествующие вычисления». («От абака до компьютера»)
9. Например: квадратное уравнение • a*x^2 + b*x + c = 0, • Дискриминант D = b^2 - 4*a*c • Если дискриминант D > 0 => 2 корня • Если дискриминант D == 0 => корень 1 • Если меньше нуля D < 0 => корней нет
16. • Неживой камень летит по траектории, которую легко посчитать по уравнениям из курса школьной физики • Траекторию движения живого существа так легко не посчитать
17. • И вот мы получаем кусок мертвой материи (вычислитель), который ведет себя во внешней среде совсем не тривиальным образом: принимает решения в зависимости от внешних обстоятельств, т. е. «на глаз» ведет себя совсем как живое существо
19. Для некоторых мыслителей это повод • Поднять статус машины до статуса человека а для других • Опустить уровень человека до уровня неживого автомата (в очередной раз)
24. Пока что • Технические попытки сделать машины, повторяющие решения людей, • например, в области генерации речи • пока еще не очень впечатляют (updt-2023: ладно, генерация речи уже вполне впечатляет) • (см. электронные «помощники» на сайтах), • (GPT-3 заливает текст «водой», следуя по «опорным точкам» смысла, предоставленным человеком или результатами поиска во внутренней базе) • Границы принятия решений любого автомата — границы математической логики • Ключевые слова: детерминизм, проблема свободы воли, бихевиоризм, математические вселенные, диалектический материализм и т. п.
25. Как машина может сделать выбор? В ответ на это Бэббидж показал, что решение вопроса о выборе одного из двух возможных путей зависит от того, какой знак (плюс или минус) имеет некоторая вычисляемая величина. Если она отрицательна, то это значит, что из меньшего числа вычитается большее. Процесс переноса приведет в этом случае к тому, что на всех местах слева от «существенных» цифр появятся девятки. Движение механизма переноса, который заставил бы девятку появиться левее самого левого из существующих в машине разрядов, можно использовать для пуска любой требуемой цепи действий. («От абака до компьютера»)
26. • В механическом вычислителе механизм принятия решения может быть реализован поворотом некоторой шестеренки, которая при определенных обстоятельствах переключит какой- нибудь рычаг и автомат перейдет в новое состояние, при котором в его работе будут задействованы другие участки его большого механизма • В электронных вычислителях физический базис переключения другой, но общий смысл тот же: в тех или иных обстоятельствах будут задействованы те или иные участки электрической цепи
27. • Далее в эти вопросы мы сегодня углубляться не будем, а посмотрим, каким образом механизм принятия решений выглядит со стороны разработчика программного обеспечения • Т. е. каким образом вы, как разработчики компьютерной программы, можете научить вычислитель принимать такие решения, которые нужно вам
36. • На первоначальном шаге (при включении вычислителя): pc = 100 (в нашем примере, конечно) • На каждый такт (clk — clock): машинный код инструкции загружается из памяти по адресу «pc» в память процессора «текущая инструкция» («сurrent instr») • Далее выполняется команда в соответствии с её машинным кодом • В конце каждой команды: pc += 4 (pc = pc + 4)
37. Команда j (jump — прыжок) • осуществляет безусловный переход — перевод счетчика программы pc в указанное место
39. Короткий прыжок
40. Длинный прыжок
41. Команда beq (branch if equal — ответвиться, если равно) • условный переход — перевод счетчика программы в указанное место при выполнении условия
47. Игра: «угадай сумму» • На входе два числа, записаны в памяти (ячейки по адресам «0» и «4») • Если сумма этих чисел равна «68», мы выиграли — награда 100 очков • Если сумма этих чисел не равна «68», мы проиграли — награда 1 очко • Награда записывается в память по адресу «8»
78. MARS MIPS • MARS (MIPS Assembler and Runtime Simulator) • courses.missouristate.edu/KenVollmar/MARS/ • > download • java -jar Mars4_5.jar
84. Задание самостоятельно • Запустить код из лекции в среде MARS MIPS, выполнить по шагам • Написать программу, умножающую два целых числа последовательностью сложений, запустить в MARS MIPS