Форум программистов, компьютерный форум, киберфорум
Наши страницы
CoderHuligan
Войти
Регистрация
Восстановить пароль
Рейтинг: 2.25. Голосов: 4.

Уроки программинга. Урок 3. Язык Си в свете структурной парадигмы.

Запись от CoderHuligan размещена 27.05.2019 в 14:10
Обновил(-а) CoderHuligan 28.05.2019 в 11:15

Очень краткая история.

Язык Си впервые был реализован на компьютере PDP-11 Дэннисом Ритчи в операционной системе UNIX. Да, вы не ослышались, - Юникс создавался первоначально не на Си, а на интерпретируемом языке Би, который вел свои корни от языка BCPL. Первоначально Юникс был всего лишь переработанной и упрощённой версией ОC MULTIX, которая большей частью была реализована на языке PL\1. Но она оказалась монстрообразной, медленной, неудобной, требовала дорогостоящего оборудования. В конце концов разработка была прекращена, и основное внимание было сосредоточено на создании новой системы, которая работала бы на более дешевых компьютерах. Так как новая система оказалась не мобильной, то крепко задумались о создании нового языка, который смог бы оказаться некой универсальной прослойкой между разными процессорными архитектурами, то есть стал бы переносим. Томпсон и Ритчи были бывшими разработчиками MULTIX, поэтому имели богатый опыт работы. Томпсон предложил создать новую UNIX на новом языке. Новый язык и был реализован путём создания его компилятора Деннисом Ритчи. Отсюда и начинается целая эпоха юникс-подобных операционных систем и популярность языка Си. Подробнее с историей создания юникс можно ознакомиться в книге Криса Касперски "Техника сетевых атак".
Итак, Си создавался практически специально для написания операционной системы, хотя изначально замысливался как универсальный инструмент. Поэтому его специфические особенности лежат в этой плоскости. Он очень компактен. В нём отсутствуют средства, которые теперь обычны в других языках высокого уровня, такие как списки, динамические строки и т.п. Однако их можно легко реализовать и на Си. Из-за его небольшого размера его легко освоить. По сути это своеобразный мега-ассемблер - надстройка над ассемблером. Так сделано специально, чтобы иметь возможность напрямую работать с памятью машины. Создатели этого языка писали, что "Си не является языком "слишком высокого уровня", также как не является он и "большим" языком.... Однако отсутствие в нём каких-либо ограничений, и его универсализм, делают его более эффективным и удобным средством, чем даже языки более высокого уровня."
Есть у него и некоторые недостатки, которые признавали и сами его создатели. По ходу мы поговорим и про них.
Классическим руководством по языку Си является конечно же книга от самих его авторов-создателей: Брайан Керниган, Деннис Ритчи "Язык программирования Си" (Brian W. Kernighan, Dennis M. Ritchie. The C Programming Language ). Также существуют десятки других учебников. Но мы будем пользоваться вот этой книгой, и ещё одной книгой, Тондо, Гимпел. "Книга ответов", в которой собраны ответы на упражнения в первой книге. Первую книгу мы будем называть сокращённо КР (КерниганРитчи), а вторую ТГ (ТонгоГимпел). Прошу это учесть.
Код некоторых упражнений мы будем полностью переписывать. Сделано это потому, что эти примеры создавались в чисто структурном стиле и малоэффективны.
Мы в частности попытаемся "утереть носик" отцам основателям, и научимся писать так как надо с прицелом на создание своего собственного языка.

Структурное программирование наступает.

При всём глубоком уважении к Кернигану и Ритчи я не могу согласится с их подходом. Язык Си, как и многие языки того времени, создавались в то время, когда происходила так называемая "структурная революция". Когда отбрасывали "устаревшие" способы кодирования, которые заменялись другими, так называемыми "структурными" конструкциями.
В то время многие известные программисты, один из которых Дейкстра, начали писать о "вреде" оператора goto, который широко использовался в таких языках, как Fortran и Basic. В эти благословенные времена, программирование считалось очень лёгким делом. Каждый "чайник" мог ему научится и создавать свои собственные программы. Причиной этой лёгкости была в не зашорености мозгов, в то время. Программы писали так, как требовала сама задача, и полагал её программист. Оператор goto использовался для структуризации кода. О каких-либо "парадигмах" ещё и слыхом не слыхивали. Постепенно программирование всё больше стало коммерциализироваться. Появилась сильная конкуренция между программистами за рабочие места.
В это время и стали возникать так называемые "парадигмы".. По всей видимости решили выкинуть за борт всех "чайников"..
Вирт, Хоор, Дейкстра и др. менее известные программисты-теоретики стали призывать полностью отказаться от применения операторов перехода. И даже не только от него, но и указатели оказались вредными, глобальные переменные и пр. Этот оператор называли слишком опасным и мощным средством, которое так запутывает программу, что её сложно становится понимать и отлаживать. Просто собрались некие люди, и решили за всех сразу что им вредно, а что нет. Интересно, что спорность этих утверждений начали оспаривать уже тогда. Дейкстра признавался в письме к Дональду Кнуту, что получал мешки писем, в которых осуждались его революционные идеи.
Спусковым механизмом, который привёл в движение процесс самоуничтожения искусства программирования, как такового, послужила статья Эдгара Дейкстры, которую он послал в один и журналов по программированию. Редактор этого журнала недолго думая самостоятельно придумал такой заголовок "Оператор goto признан вредным". Сам Дейкстра к этому заголовку не имел никакого отношения. "Признан" вредным он оказался видимо только самим Дейкстрой (на то время). После этой статьи-бомбы, его признали вредным и многие другие.
Однако сам Дейкстра по поводу этого бума писал:
"Пожалуйста, не попадите в ловушку, уверовав в то, что я ужасно догматичен [по поводу оператора goto]. У меня есть стойкое чувство дискомфорта по поводу того, что люди делают из этого религию, полагая, что все концептуальные проблемы программирования могут быть решены лишь одним единственным трюком, или простейшей формой дисциплины кодирования."
Видимо, всё же он был умнее многих своих последователей..
Что же предложили революционеры от программирования?
Они предложили строить программу всего из трёх основных конструкций:
1) Следование;
2) Развилка;
3) Цикл;



Одним из условий было полный или частичный отказ от применения оператора goto.

"Следование" - это простая последовательность операторов или любых других конструкций, блоков, которые следуют один за другим и реализуют так называемый "линейный алгоритм". Следование это один блок с одной точкой входа и с одной точкой выхода.

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

"Цикл" - это конструкция, которая позволяет повторять некоторую последовательность операций определённое или неопределённое количество раз. Есть две основные разновидности структурных циклов. Обе они также являются блоками с одним входом и с одним выходом со всеми вышеприведёнными замечаниями по этому поводу. Первый это цикл "до", а второй это цикл "пока". Подробнее поговорим об этом в следующих уроках.

Это дело назвали структурным подходом к программированию. Вот из таких блоков-кирпичиков структурное программирование и предлагает строить свои программы. Почему таким образом очень сложно, а иногда просто невозможно построить правильный алгоритм позже. Пока мы просто расставляем вешки.
Революционеры пытались доказать, что любой алгоритм может быть реализован применением вот этих трёх конструкций. Листинг такой программы, как предполагалось, можно читать сверху вниз не прыгая туда-сюда по переходам. И вроде бы ничего плохого в этом и нет, однако теперь приходится удерживать в памяти все возможные условия и т.п. с тем, чтобы не возвращаться к началу программы или какому-либо участку её кода. К тому же возникают и другие проблемы.
Дональд Кнут, математик-программист, который написал трёх-томный классический труд по программированию, по поводу которого основатель и владелец компании Майкрософт Билл Гейтс говорил: "Я без разговоров дам работу любому программисту, который осилил этот труд", откликнулся по поводу этого несколькими статьями. В первой статье - [Knuth Donald E., and Floyd Robert W., "Notes on avoiding 'goto' statements", Information Processing Letters l, 1 (February 1971), 23-31, 177.], которая была написана в соавторстве с Флойдом, чисто математическими методами доказывалось, что не все алгоритмы могут быть реализованы подобным образом. Нужны дополнительные вычисления, введение булевых переменных (флагов) чтобы реализовать алгоритм. Эффективность подобных программ не слишком высока. Вторая статья -"Структурное программирование с оператором goto" - "Stractured programming with goto statements" была написана более объёмной на несколько десятков страниц, в которой он приводил историю борьбы с оператором перехода, историей введения структурного программирования, и опять призывал не отказываться в некоторых случаях от данного оператора. Я приступил к её переводу на русский язык. К сожалению, эти работы известны лишь специалистам. Ссылки на эти работы старались замалчивать, ведь они полностью разбивают стройность их собственной парадигмы.. Теперь все языки в той или иной степени поддерживают структурность их грамматики.
Когда Кнут впервые познакомился с этим подходом, то, как он пишет, совершенно не мог понять поначалу каким образом кодировать программы в этом стиле. Ему даже пришлось приходить в офис к Роберту Флойду, с которым они экспериментировали в этой области. И не он один оказался в тупике.
Итак программисты не-математики получили строгую отповедь от программистов-математиков. К слову сказать, в своих работах Дейкстра с Виртом вообще не упоминали математическую теорию конечных автоматов, которая к тому времени была уже совершенно оформлена.. Хорошо известно, что так называемая "Машина Тьюринга" была создана именно математиком, Тьюрингом, и сейчас считается эталоном применимости того или иного языка программирования. В теории конечных автоматов есть такое понятие как "состояние" обьекта управления, которое начисто отсутствует в структурном программировании. В последнем состояния скрыты в листинге программы и не имеют своих собственных имён. То есть состояния там неявны. Понимание же алгоритма без явного выделения состояний невозможно или очень сложно. Дейкстра, кстати предлагал для верификации программ, ввести единственную переменную, которая бы отслеживала все состояния программы в каждый единичный момент её выполнения. Дейкстра всё же был очень умным человеком, в отличие от многих.. К машине Тьюринга мы ещё вернёмся. Функциональная парадигма пошла ещё дальше структурной: она вообще предложила упразднить такое понятие как состояние программы. Но, это уже тяжёлая патология, и тема для другого разговора..
Так вот, язык Си, вслед за Паскалем, Алголом, PL\2, и др. языками того времени, тоже последовал магии структурной парадигмы, и ввёл все эти структурные конструкции. Позже мы их все рассмотрим более подробно. Разберём их, так сказать "по косточкам"..
Продолжение следует..
Размещено в Без категории
Просмотров 275 Комментарии 13
Всего комментариев 13
Комментарии
  1. Старый комментарий
    Аватар для liv
    Ну и где "вложения"? Хотя их содержимое не вызывает вопросов, но их нет! Выдается:
    Цитата:
    Вложение не существует или не указан идентификатор (номер)
    Все эти проблемы и баталии вполне известны... Ждем разбора "по косточкам"
    Т.к. догадываюсь, что одним из Ваших пунктов есть использование goto... Ждем доказательств, что без goto невозможно обойтись...
    А "состояние" объекта управления вполне даже полезный инструмент. Я постоянно его использую, когда это необходимо
    Запись от liv размещена 27.05.2019 в 18:47 liv вне форума
  2. Старый комментарий
    Аватар для liv
    Вложение появилось...
    Запись от liv размещена 27.05.2019 в 19:21 liv вне форума
  3. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от liv Просмотреть комментарий
    Ну и где "вложения"?
    У вас такой тон, как буд-то я специально спрятал от вас вложения.. Прямо-таки монстр в ваших глазах.)) Вложил, и спрятал..))
    У меня кстати показывает в другой вкладке. Но раз уж форум не может показать те рисунки, которые я сделал, то изменил на рисунок из сети.
    Цитата:
    Сообщение от liv Просмотреть комментарий
    Все эти проблемы и баталии вполне известны...
    Кому известны? Всем? Думаю далеко не всем. Очень далеко.. Кто читал статьи Кнута по этому вопросу? Вы читали? Если да, то вы продвинутый малый, но только не надо судить по себе..
    Цитата:
    Сообщение от liv Просмотреть комментарий
    Т.к. догадываюсь, что одним из Ваших пунктов есть использование goto... Ждем доказательств, что без goto невозможно обойтись...
    Дело не в goto как таковом, а в способе переходов из одного состояния алгоритма в другое. Просто при помощи именно goto это легко и просто реализуется. Существующие методики (свитч-технология, система "Дракон") позволяют опять скрыть этот оператор, вводя понятие состояние, но думается, что наиболее прямые методы наиболее и эффективны же.. Дракон система и свитч-технология будут обсуждаться в других уроках.

    Цитата:
    Сообщение от liv Просмотреть комментарий
    А "состояние" объекта управления вполне даже полезный инструмент. Я постоянно его использую, когда это необходимо
    Оно необходимо всегда, где присутствует сложное поведение обьекта управления. А как показывает практика сложное поведение наблюдается даже у наиболее простых обьектов.
    Запись от CoderHuligan размещена 27.05.2019 в 19:24 CoderHuligan на форуме
    Обновил(-а) CoderHuligan 27.05.2019 в 19:25
  4. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от liv Просмотреть комментарий
    Ждем доказательств, что без goto невозможно обойтись...
    Доказательства имеются.
    Запись от CoderHuligan размещена 27.05.2019 в 19:35 CoderHuligan на форуме
  5. Старый комментарий
    Аватар для bedvit
    Ух.. инфа интересная! С нетерпением жду крутого замеса следующей части. Готовлю попкорн компилятор.
    Запись от bedvit размещена 27.05.2019 в 20:15 bedvit на форуме
  6. Старый комментарий
    Аватар для Croessmah
    Кому интересно об истории C:
    Dennis M. Ritchie - The Development of the C Language
    Запись от Croessmah размещена 27.05.2019 в 21:19 Croessmah на форуме
  7. Старый комментарий
    История с оператором GOTO напоминает нечто подобное в математике...
    Известно, что любое вычисление можно свести к сложению и вычитанию, НО
    люди поняли, что неплохо бы использовать Умножение и функции...
    Запись от нтч размещена 28.05.2019 в 07:11 нтч вне форума
  8. Старый комментарий
    Аватар для bedvit
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Кому интересно об истории C:
    Dennis M. Ritchie - The Development of the C Language
    С удовольствием почитал. Благодарю.
    Запись от bedvit размещена 28.05.2019 в 10:12 bedvit на форуме
  9. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от нтч Просмотреть комментарий
    История с оператором GOTO напоминает нечто подобное в математике...
    Известно, что любое вычисление можно свести к сложению и вычитанию, НО
    люди поняли, что неплохо бы использовать Умножение и функции...
    То-то и оно что эти вещи не сводимы..
    Запись от CoderHuligan размещена 28.05.2019 в 10:59 CoderHuligan на форуме
  10. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Кому интересно об истории C:
    Dennis M. Ritchie - The Development of the C Language
    Спасибо!
    Запись от CoderHuligan размещена 28.05.2019 в 11:09 CoderHuligan на форуме
  11. Старый комментарий
    Они предложили строить программу всего из трёх основных конструкций:
    1) Следование;
    2) Развилка;
    3) Цикл;
    .........
    Это понятно. А куда относятся такие вещи как Процедура (функция)? В особенности Рекурсивная процедура (функция)? На рекурсию смотрят даже хуже, чем на Goto. От неё просто так не отделаешься. Рекурсия - краеугольный камень в построении Искусственного Интеллекта!!
    Запись от нтч размещена 28.05.2019 в 17:52 нтч вне форума
  12. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от нтч Просмотреть комментарий
    От неё просто так не отделаешься. Рекурсия - краеугольный камень в построении Искусственного Интеллекта!!
    К сожалению, рекурсия ограничена глубиной системного стека, который обычно не слишком глубок. Даже быстрая сортировка пасует перед его глубиной если массив слишком велик.
    Запись от CoderHuligan размещена 28.05.2019 в 19:02 CoderHuligan на форуме
  13. Старый комментарий
    Аватар для liv
    Ко всему надо подходить с умом. Включая и к рекурсии. Нет универсальных методов. Каждый хорош в своих пределах.
    Запись от liv размещена 29.05.2019 в 15:41 liv вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru