Философия программирования

filosofiya programmirovaniya?v=1656604701

от Хаосяня Чена

Логическое мышление === хорошее программное обеспечение

EZF4VCe2rJHLZDPrYv-sUBYvAxsRACQj6kV5
Фото Джаммарко Боскаро на Unsplash

Программирование – это новая грамотность. Но как мы пишем хорошие программы? Вот регулярные вопросы, которые мы должны решить:

  • Как мы находим алгоритмические решения проблемы?
  • В то время как мы знаем, что решение действительно работает?
  • Даже если мы уверены, что это работает, как мы указываем компьютеру выполнить его?

Интересный факт — если вам трудно разобрать любой из этих вопросов, вы занимаетесь философией.

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

Первый принцип: нужно хорошо подумать.

Компьютеры не делают ничего умнее, чем мы – разница в том, что они делают это быстрее.

Но они не могут решить актуальную проблему типа «как мне добраться до офиса из дома?»

Эффективный метод (в принципе) может быть осуществлен человеком без какой-либо техники, кроме бумаги и карандаша.

— Тезис Черча-Тюринга

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

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

Поток рассуждений программиста

Теперь мы смотрим на описание проблемы. Сначала мы можем искать мелкие примеры ввода-вывода, чтобы понять проблему:

Индукция. Нам требуется алгоритм, который может обрабатывать следующие примеры. Сейчас вы делаете индукцию: обобщаете принципы опыта.

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

Онтология. Мы должны хранить данные в памяти компьютера. Цель – сделать их эффективными для обработки компьютеров. Если говорить по порядку, какая структура данных может лучше всего отразить динамический поток моей информации?

Снова индукция. Затем наступает последний этап: отладка. Мы побуждаем ошибочную часть программы анализировать неожиданные результаты.

Пример

Теперь давайте рассмотрим вышеупомянутый процесс, следуя этому реальному примеру: находим кратчайший путь от вершины A до вершины E.

Bs3KoOWL2idTBigI0y630wh78nK9Sdwtvdck
Просто карта. Цифры обозначают расстояние до предела.

Для маленьких заморочек мы можем решить их инстинктами. Мол, нам очень легко распознать решение ACE, просто посмотрев.

Но как насчет более сложных топологий? А как насчет разного веса края?

Нам необходима помощь компьютеров. Однако указывать компьютеру, что ему делать непросто. Есть разрыв между тем, как люди думают, и тем, как работает компьютер.

Процесс

1. Обобщение принципов по опыту: алгоритмы

Чтобы сказать компьютеру, что делать, нам сначала нужно придумать алгоритмическую процедуру.

Жадные стратегии – это естественный способ продолжить. То есть, начиная с исходной вершины A и продолжая весь путь по известному кратчайшему пути. Продолжайте исследовать новые вершины, пока не достигнем пункта назначения E. И действительно, этот подход удовлетворяет наш пример.

Интуиция состоит в том, что вдоль кратчайшего пути к пункту назначения каждый промежуточный узел также посещается по кратчайшему пути. (Конечно, эта интуиция предполагает, что все ребра имеют положительные весы. Это может не соответствовать действительности в зависимости от приложений. Мы обсудим это подробнее позже).

Итак, вот алгоритмическая процедура:

OMYtQquoo-Owxbdgr0s8D270PknR9Ez-Zge5
Анимация алгоритма Дейкстры, автор Шию Джи из Википедии
  1. Некоторые настройки: (1) вести бухгалтерский учет вершин, которые мы посетили: набор (visited), (2) запомнить известные кратчайшие расстояния до каждой вершины, что использовать только найденные вершины: другой набор distance(u). Расстояние до каждой вершины сначала равно бесконечности, за исключением исходной вершины 0.
  2. Теперь начинаем исследовать: сначала мы посетить вершина, которая имеет известный кратчайший путь, скажем, что это u. (Сначала это была бы начальная вершина).
  3. Когда стоит на вершине u, обозреваем выходные края. Каждый край, скажем(u,v)дает нам путь к вершине v использующий вершину u как последний, но только один шаг. Если любой из них действительно является более коротким путем v или первый путь, к которому мы нашли vура, мы можем обновить наш набор кратчайших путей. Иначе игнорируйте и продолжайте.
  4. Мы закончили с верхом uпоэтому мы добавляем его к нашему visited набор.
  5. Вернитесь к шагу 2, продолжайте исследовать, пока мы не посетим все вершины.

distance теперь может указать глобальные кратчайшие расстояния, поскольку он используется для сохранения кратчайших расстояний, используя только посещаемые узлы. И все вершины посещаются, когда алгоритм заканчивается.

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

2. Подтвердить общие принципы путем дедукции

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

Как и априорное утверждение в философии, правильность алгоритма не зависит от его выполнения. Другими словами, тестирование не может гарантировать корректность алгоритмов. Нам нужно это доказать.

Вот основной поток доказательства:

1. Для всех посещенных вершин находим кратчайшие пути.

2. Место назначения посещено.

3. Итак, находим кратчайший путь к пункту назначения.

Не кажутся ли они знакомыми? Нравится это:

1. Все люди смертны.

2. Сократ – мужчина.

3. Итак, Сократ смертен.

На самом деле это силлогизм, классическая форма дедуктивного размышления. Это почти то, что делают логики.

Еще один любопытный исторический факт: формальная концепция вычислений была впервые придумана логиками в 1930-х годах. Им нужно было знать, есть ли логические проблемы вообще разрешимыми (т.е. они могли не тратить свое время на решение чего-то неразрешимого). Чтоб ответить на это, они выдумали понятие вычисляемости.

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

Правильность вывода зависит от первых двух посылок. В нашем подтверждении вторая посылка тривиальна, так как наш метод практически посещает все узлы. Однако доведение первой предпосылки, что мы находим кратчайший путь к моменту посещения узла, требует определенной работы.

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

Общий поток смотрится следующим образом. Во-первых, если алгоритм работает на входе 0а во-вторых, если дело в том, что он работает на вход n означает, что он работает на входе n+1 также, тогда он работает для всех входных данных, больших или равных 0. На этом этапе можно гарантировать правильность своего алгоритма.

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

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

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

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

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

3. Проблема онтологии: структура данных

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

Следующий вопрос: как мы предоставляем информацию в компьютере? Людям нравится визуализированная информация, например графики или гистограммы. Но современные компьютеры имеют дело только с двоичными битами.

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

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

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

Что ж, мы можем избавиться от списка. Оказывается, для того чтобы собрать кратчайший путь, промежуточным шагом является определение следующего шага, который вам нужно пройти. Все, что нам нужно, чтобы получить кратчайший путь от источника A до любого целевого узла, это только сам график и кратчайшее расстояние от A до каждого узла.

EVYvfP6tEU3yBZanFV-m8doAre-P8wWDbBeB
Информация для получения кратчайшего пути от A до любого узла. (Числа внутри вершин обозначают расстояние от A.)

Зрительное представление показано на изображении выше. Это представление эффективно для памяти. Это также более эффективно для обработки программы.

Вот как он строит кратчайший путь, используя только вектор расстояния. Начните с вершины назначения и пустого пути. Ищите промежуточные вершины через входные ребра. Выберите тот, который имеет наименьшее значение distance. Добавьте его в начало пути. Повторяем, пока не дойдем до источника. Этот трюк действительно имеет формальное обозначение, которое называется обратным отслеживанием.

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

4. Апостериорное предложение: отладка

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

К примеру, ошибки сегментации в программах на C часто вызываются нулевыми ссылками на указатель. Я узнал это после того, как столкнулся с множеством ошибок сегментации C/C++. Конечно, есть более тонкие случаи, касающиеся личных привычек программирования.

Следующий пример – синтаксическая ошибка, допущенная программистом. Условие if должно быть is_float==1 но программист ошибочно принял логический оператор равенства == как оператор оценивания =. Это все равно пройдет проверку компилятора, поскольку оба из них правильны.

if (is_float = 1) {  // do something}

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

Вот где ценность практики. Независимо от того, какие методы вы изучаете, необходимо собрать достаточно практических данных. Иначе у вас не будет достаточно опыта для проведения индукции.

Вы должны следить за повторяющимися шаблонами в кодах ошибок. Когда вы обнаружили ошибку, исправить ее недостаточно. Вам необходим дополнительный причинно-следственный анализ вашей собственной практики программирования. Спросите себя: особенно ли эта часть моих привычек программирования уязвима к таким ошибкам?

Так почему это имеет значение?

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

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

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

Ссылки

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *