Институт №8 МАИ

13 день. Критика фон Неймана, Pascal, рекурсия

d10. Нотация Дейкстры <–> d11. Типы данных <–> d12. Файлы, блоки <–> d13. Критика фон Неймана, рекурсия
d1. Раскладки клавиатур, кодировки <–> d6. Системы программирования <–> d9. Железки (1-12) <–> d14. Железки (13-35) <–> d15. Железки (36-74)

Словарик программиста (надо знать!):

Концептуальный — сущностный, содержательный.
Рекурсия — это углубляющееся многократное самоприменение.
Рекурсивная программа — композиция из множества операторов, не содержащих самой программы.

3.4.4 Побочные эффекты

При использовании глобальных объектов в подпрограмме их значение может измениться после выполнения.

Подпрограмма, вычисляющая функцию, в результате должна получать новое значение. Но изменение при этом глобальных переменных не являлось целью, поэтому и называется побочным эффектом.

Это проявляется и в изменении значений параметров функции, если способ их передачи был нежелателен.

3.4.5 Критика алгоритмической модели фон Неймана

Модель фон Неймана — развитие модели Тьюринга, математически точной и полезной, наделённой памятью и чувствительностью к предыстории.

МТ работает на частой смене простых состояний, поэтому программы неясные и концептуально бесполезные. Построением диаграмм, схем, а также программ на языке ОСТ мы улучшили эту модель, но недостатки сохранились.

Только концепция модели фон Неймана оказалась полезной на практике. К ней относят как компьютеры, так и ЯП. Они математически сложны и громоздки, существенно используют память и чувствительны к предыстории, как и МТ.

Модель фон Неймана основана на переходах между более сложными (в сравнении с МТ) состояниями. При этом ясность программ и концептуальная польза оказывается выше в сравнении с Тьюрингом.

Компьютер фон-Неймана состоит из процессора, памяти и соединяющей их шины, передающей между ними одно слово за такт. Это слово либо единица данных, либо команда, либо адрес.

Джон Бэкус называет шину «бутылочным горлышком» этой архитектуры и вот почему:

Программа меняет содержимое памяти процессором посредством перекачки данных через шину из памяти и обратно. Но большую часть этого потока составляют команды и адреса, а не полезные данные.

Перед отправлением слова через шину его адрес появляется на процессоре. И появляется он там либо через шину, либо генерируется на процессоре. Если адрес взят из памяти, то и его адрес посылается из памяти либо вырабатывается на процессоре.

Шина не только сужает место для потока команд и данных, но и ограничивает в мышлении: программируем «слово за словом» вместо работы с крупными понятиями решаемой задачи.

ЯП — более сложные версии компьютера фон Неймана:

Переменные имитируют ячейки памяти;
операторы управления выражают команды управления и проверки;
операторы присваивания имитируют загрузку содержимого ячейки и вычисления, запоминанают результат.

Узкое место ЯП — оператор присваивания.

Он разделяет программирование на левый и правый миры:

Левый — неупорядоченный мир операторов, существующих ради главного из них — оператора присваивания, выполняющего вычисления.
Правый — мир полезных алгебраических вычислений (не учитывая их нарушения побочными эффектами).

Отсутствие иных стилей программирования сделало другие концепции неэкономичными, ограничив их развитие.

Джон Бэкус предлагает функциональный стиль программирования, основанный на рекурсивных построениях.

3.5 Критика языка Паскаль

© Профессионализм в том, чтобы 
- критиковать вещи,
- которые сделаны хорошо.

Автор Паскаля, профессор Вирт, был удостоен Тьюринговской премии. С этим ЯП связан ряд достижений систем программирования.

Это и бутстрепинг — постепенное написание компилятора для системного программирования, и реализация интерпретатора p-кода, реализуемого за неделю на любом ЯП на новом компьютере.

Недостатки этого замечательного языка являются продолжением его достоинств.

Паскаль представляет собой программно-компилируемую реализацию машины фон Неймана и к нему можно отнести всю критику этой алгоритмической модели.

1) Скалярный оператор присваивания заставляет программиста постоянно заботиться о рациональном его использовании и отвлекает от решения самой задачи.

2) Паскаль является строго типированным языком, а значит меньше вероятность написать плохую программу. При этом он прост: всё описание программы в начале, но объекты программы употребляются в строгом соответствии с описаниями, что неудобно в системном программировании.

3) В своей строгости Паскаль непоследователен. Например, записи с вариантными частями образуют брешь в системе типизации.

Паскаль эффективно компилируется на аппаратуру. Но это превращается в недостаток, т.к. многие типы данных (строки и массивы переменной длины) либо не реализованы, либо их реализация наталкивается на ряд проблем.

Поэтому едим 3 ножами и 5 вилками.

На Си блочная структура, реализуемая через процедуры.
При этом язык Си не так дуракоустойчив, как Pascal.
Си — аскетичный язык. Он даёт небогатую среду в сравнение с диванным программированием на Python.

Паскаль проигрывает Си не только в выризительной силе и лаконичности. Идеальная модель Паскаля далека от реальности:

Отсутствие модульности и внешних процедур закрывает путь в товарное программирование
Да и сама библиотека языка Си — мощный интерпретируемый компонент.

5.8 Рекурсия (переход на с.258)

А этот глист страдал глистами
- что мучились глистами сами!

Понятие рекурсии. Рекурсия и итерации

Рекурсивное описание процессов и функций — описание их через самих себя.

Наглядный жизненный пример получим, если встанем между 2 зеркалами — увидим бесконечную последовательность отражений.

Мощь рекурсии состоит в конструктивном определении бесконечного множества объектов малым набором правил.

Более сложная классификация рекурсий:

линейная
повторная (концевая, хвостовая)
каскадная
удалённая
взаимная

Рекурсия — это углубляющееся многократное самоприменение.
Итерация — повторяющаяся многократная обработка данных, которая не приводит к рекурсивным вызовам программы.

Разница между рекурсией и итерацией

Мы прибегаем к рекурсии для автоматического упрощения задачи, которая, как и цикл, должна завершиться по выполнении.

Внутри рекурсивного тела Р должно находиться условие завершения В, которое станет истинным. Схему рекурсивных алгоритмов можно представить в одной из следующих форм:

Следует добиваться конечной и малой повторяемости рекурсивных вычислений, иначе мы не получим выигрыш от красивого программирования.

Функция Аккермана — пример удалённо-рекурсивной функции. Она захлёбывается в рекурсии, но не сводится к итерации. В цикл её не перепишешь. Эта функция завершима: все её аргументы уменьшаются, а она сама терминируется нулём.

Рекурсивный вызов процедур

Программы, как и функции, могут быть вызваны рекурсивно.

Рекурсивная программа — композиция из множества операторов, не содержащих самой программы.

Виды рекурсий:

Прямая рекурсия — вызов подпрограммой самой себя по имени, а косвенная — вызов одной через другую программу.

Рекурсивные вызовы процедур производятся аналогично вызову одной процедуры из другой. Просто в них все вызываемые процедуры одинаковы.

Каждая рекурсивная активация блока порождает новую локальную переменную, а предыдущие одноименные откладываются в стек и экранируются.