Павловская структурное программирование практикум

Структурированное программирование — это устоявшаяся парадигма. Все популярные языки программирования предоставляют структурированные конструкции потока управления. Существует повторяющаяся проблема. Возникающая при написании реального программного обеспечения. Многие считают. Что любой вид параллелизма изначально сложен. Но мало кто понимает. Что структурированное программирование делает его еще более сложным. Чем это должно быть. Структурированное программирование предназначено для повышения ясности и качества программного обеспечения. И во многих аспектах оно успешно справляется с этой задачей.

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

Откуда и почему появилось структурированное программирование?

Истоки структурированного программирования можно проследить до открытия. Известного как теорема структурированной программы. Вывод этой теоремы заключается в том. Что графики потока управления. Состоящие из подпрограмм. Блоков условий и циклов. Могут вычислять любую вычислимую функцию. Это означает. Что неструктурированный поток управления. Который использовался до структурированного программирования. Не нужен для представления программ.

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

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

Это нечто настолько фундаментальное. Что сегодня мы принимаем это как должное. Поэтому я приведу пример. Чтобы помочь понять. Что это значит. Здесь у нас есть программа. Которая предназначена для перечисления чисел от 5 до 9.

Сначала я представляю его вам без структуры.

A1:  i := 5  goto A2 A2:  enumerate i  increment i by 1  if i = 10  then goto A2  else goto A3 A3:  program completed

(Программа на самом деле не верна. Хотя я обращал на это внимание при написании кода. Я все еще путал метки в блоке условий. Я решил оставить это. Потому что это еще одна вещь . Которую вы обычно меньше ошибаетесь в структурированном программировании.)

Если A1это единственная точка входа. То эта программа верна. Однако если бы это была часть более крупной программы . То вы бы не знали. Будет ли эта программа введена из

A2или A3пропущена A1.

С другой стороны. Если у вас есть следующая программа:

i := 5 do  enumerate i  increment i by 1 until i = 10

Вы сразу же знаете. Что нет никакого способа войти в цикл. Не установив Зная это. Вы можете сделать вывод . Что программа делает то. Для чего она предназначена.

Полемика вокруг точек выхода

Ранее ученые утверждали. Что структурированное программирование должно также позволять быстро определять точки выхода. Язык программирования Pascal следует этой дисциплине.

Оппозиция против нескольких точек выхода обсуждала такие заявления, как

‘break’ останавливает текущий цикл и выпадает из него. ‘return’ останавливает текущую процедуру и немедленно возвращается из нее.

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

Восстановление и возобновление работы после ошибок-важная часть правильно написанного программного обеспечения. Для этого вы должны отслеживать точки выхода в программном обеспечении.

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

Обработка исключений corruption Повреждение данных

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

  1. Вещи, которые идут не так. Продолжают накапливаться по мере того. Как программа продолжает работать.
  2. Необходимость учитывать ошибки приводит к беспорядку в коде.
  3. Значения ошибок имеют тенденцию быть такими же богатыми и информативными. Как и обычные значения. Такая симметрия игнорируется простым возвратом кода ошибки.
  4. Трассировки стека помогают в отладке.

Единственная проблема с обработкой исключений заключается в том. Что при меньшем количестве точек выхода остается меньше мест. Где вы можете восстановить состояние до того. Как подпрограмма была запущена. Обработка исключений предоставляет для этого

Обычно люди пытаются решить такого рода проблемы с помощью неизменности. Они настаивают на том. Что каждое значение должно быть доступно только для чтения. Если оно не должно быть изменяемым. Хотя это помогает. Это не решение проблемы наличия состояния. Которое должно измениться во время оценки программы.

Трассировки стека. Или то. Что должно быть возвращено. Зависит от контекста

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

Трассировки стека записывают каждый вызов подпрограммы. Который произошел между точкой. Где произошла ошибка. И подпрограммой. Которая ответила на ошибку. Обычно это массив числовых значений. Записанных при размотке стека вызовов в ответ на ошибку. Таким образом. Трассировка показывает каждую точку входа. Которая была необходима для воспроизведения ошибки. И является неоценимой помощью в выяснении причины сбоя программы.

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

Если мы представляем ошибки как возвращаемые значения. Люди обычно думают. Что это означает. Что мы не получаем никаких обратных следов ошибок. Но должны ли обратные следы вообще быть связаны с обработкой ошибок? Единственная причина. По которой они не всегда записываются. — это производительность.

Проблема в том. Что при запуске программы мы не знаем. Требуется ли трассировка стека или нет. Но трассировка должна быть собрана во время работы программы.

Был бы способ включить трассировку стека. Когда это необходимо. Вы можете сделать некоторые выводы относительно контекста. Чтобы решить. Вычислять ли трассировку стека или нет. Как в вы можете вычислить его. Когда что-то ожидает его. Вы даже можете вывести условия. Необходимые для чтения трассировки стека.

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

Структурированная обработка ошибок

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

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

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

data BrewingError:  CleaningDue  GrindingUnitBroken  HeaterBroken  NoWater  OutOfBeans  ReplaceClockBattery  ThermistorDisconnected

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

Монады в императивном программировании

Но если вы передаете ошибки как возвращаемые значения. Будет ли это означать. Что вы в конечном итоге имеете его. Как у языка программирования Go? Обработка ошибок в изобилии рассыпалась вокруг кода. Как маленькие гранулы. Программирование хомячьего колеса в лучшем виде.

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

Монады вводят две функции. Которые мы можем закрыть в интерфейс:

Monad M  unit : a → M a  bind : M a → (a → M b) → M b

Символы стрелки здесь следует понимать как функции. unit это функция. Принимающая некоторое значение и производящая монаду. bind это функция. Которая принимает монаду, и функция. Которая производит монаду. А затем производит другую монаду.

bind это псевдоним >>=для удобства. Чтобы структура была монадой. Грубо говоря. Это означает. Что Математически вы можете описать эти правила следующим образом:

left identity: (unit x >>= f) = f x  right identity: (a >>= unit) = a  associativity: ( a >>= x ↦ f x >>= g)  = ((a >>= f) >>= g)

Эти структуры позволяют варьировать значение. Содержащееся в процедуре. Это означает. Что вы можете построить свою собственную конвенцию о том. Как должна работать процедура. Все еще можно испортить его. Норайней мере. Теперь у языка нет систематически ошибочного способа выполнения задачи обработки ошибок.

Например, следующая реализация позволит вам присоединить процедуру обработки ошибок:

data Either a b:  Left a  Right b  Monad (Either e):  unit = Right  bind (Right x) f = f x  bind (Left y) f = Left y

Эта процедура будет работать до тех пор. Пока не будет обнаружен какой-то недостаток. Вы можете использовать этот тип. Чтобы определить. Какое соглашение использует процедура.

isOperational : Either BrewingError SystemParameters procedure isOperational()  checkMaintentanceLog;  testGrindingUnit;  testMoisture;  etc... end procedure

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

case isOperational() of  Left error:  reportError error  Right parameters:  runMenu parameters

Поддерживать монады в языке довольно просто. Особенно если вы придерживаетесь того. Чтобы иметь конструкции потока управления. Которые обеспечивают беспрепятственный принцип одного входа/одного выхода. Процедура рассматривается как одно большое уравнение. И последовательность формируется путем ее построения из операций

Двоюродный брат структурированного программирования

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

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

Хорхе представляет презентацию программы на основе рога как способ анализа и преобразования программ. Представление делает многие формы ошибок очень очевидными.

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

Циклы заменяются вызовами подпрограмм. Блоки условий заменяются на пункты guard. Предложения Guard совпадают таким образом. Что программа полностью определена.

Рассмотрим структурированное программирование fizz buzz:

fizz_buzz(count):  i := 1;  while i  by_3 := (i % 3 == 0);  by_5 := (i % 5 == 0);  if by_3 and by_5 then  print "fizz buzz"  else if by_3 then  print "fizz"  else if by_5 then  print "buzz"  else  print "%s" i;  i := i + 1

Низкоуровневое представление. Основанное на предложении хорна. Для этого будет следующим:

fizz_buzz(count):  fizz_buzz(1, count).  fizz_buzz(index. Count):  index  i % 3 = 0;  i % 5 = 0;  print "fizz buzz";  fizz_buzz(index+1, count)  fizz_buzz(index. Count):  index  i % 3 = 0;  i % 5 ≠ 0;  print "fizz";  fizz_buzz(index+1, count)  fizz_buzz(index. Count):  index  i % 3 ≠ 0;  i % 5 = 0;  print "buzz";  fizz_buzz(index+1, count)  fizz_buzz(index. Count):  index  i % 3 ≠ 0;  i % 5 ≠ 0;  print "%s" index;  fizz_buzz(index+1, count)  fizz_buzz(index. Count):  ! index 

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

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

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

Счетчик программ — это деталь реализации

Секвенирование-сложная вещь для эмуляции. Если аппаратное обеспечение не совсем соответствует тому. Что стремится обеспечить среда программирования.

Это начинает стоять на пути написания программного обеспечения. Например, графическое оборудование сегодня достаточно отличается. Чтобы оно не запускало javascript или webassembly. И вам нужен какой-то небольшой вариант языка для их программирования. Такие языки. Как Rust или Javascript. Просто слишком много предполагают о платформе. Чтобы работать на видеокарте.

Я думаю, что это счетчик программ и предположения о состоянии программы. Которые здесь догоняют.

Async/Sync не должен подвергаться воздействию программиста

Структурированное программирование плохо подходит для моделирования программного обеспечения с расходящимися обязанностями.

Давайте рассмотрим программу. Которая ждет секунду. А затем пишет сообщение. На этот раз написанное на Javascript:

setTimeout(function(){ console.log("hello") }, 1000)

Это асинхронный способ заставить программу подождать секунду . Прежде чем она выполнит действие. Это достигается путем запуска eventloop. Который вводится при выходе из сценария.

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

#include  #include   int main(void) {  sleep(1);  printf("hello\n");  return 0; }

Как дизайнер интерфейсов для структурированного языка программирования. Вы должны решить. Следует ли предоставлять синхронный или асинхронный ввод-вывод. JS выбрал асинхронный ввод-вывод. Потому что его легче реализовать таким образом . Чтобы он работал для написания интерактивных программ.

Ни тот, ни другой выбор не был удовлетворительным. И вы, возможно. Наткнулись на проблемы. Возникающие из-за того. Что какой-то интерфейс приложения прибегает к синхронному поведению. А другой интерфейс пытается быть асинхронным.

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

Как насчет того. Чтобы игнорировать всю проблему асинхронности/синхронизации. Как мы делали с несколькими точками выхода? Хорошо.. Тогда я мог бы рассказать вам о сообщениях. Семафорах, мьютексах. Блокировках. Барьерах записи и чтения. Процессе нереста и разветвления. Однопрограммном множестве данных. Когда мы начинаем различать программы по порядку оценки. Который применяется к ним. Мы получаем все эти детали. И все они очень специфичны для системы.

Если мы рассматриваем структурированное программирование как монаду. Аннотируем побочные эффекты в типы. А затем исследуем сигнатуры интуитивных типов. То увидим следующее различие между функциями синхронизации и асинхронности:

timeout : Integer → IO () → IO () sleep : Integer → IO ()

Здесь важен второй аргумент в пользу тайм-аута . И мы не можем его упустить. Это означало бы. Что разница между асинхронностью и синхронизацией не может быть абстрагирована.

Но мы можем изменить нашу логику. Мы можем переписать сигнатуры типов в линейной логике а затем сравнить их:

timeout : Integer ⊸ (1 ⊸ 1) ⊸ 1 sleep : Integer ⊸ 1

timeout : ~Integer ⅋ (~1 ⊗ 1) ⅋ 1 sleep : ~Integer ⅋ 1

В линейной логике 1-единица⊗. А ~1-единица ⅋ . Это было бы описано так:

unit_conj : 1 ⊗ a = a unit_disj : ~1 ⅋ a = a

Применяя эти правила. Мы можем переписать timeoutsleepи наоборот. Это означает. Что они эквивалентны по линейной логике.

Однако это невозможно сделать. Если мы придерживаемся структурированного программирования. Он не может абстрагироваться от асинхронности без потери свойств.

Моделирование поведения с помощью линейной логики

Разработчики программного обеспечения не заботятся о последовательности большую часть времени. Они заботятся о том. Как ведет себя их программа.

Например, рассмотрим веб-сервер. Реализующий чат. Мы хотели бы. Чтобы все происходило, когда:

  1. Есть запрос на настройку сервера.
  2. Есть запрос на прослушивание в порту.
  3. Запрос на подключение делается к порту. Который затем должен быть либо отклонен. Либо принят. И тогда мы получаем соединение. С которым мы должны что-то сделать.
  4. Сообщение принимается через соединение.
  5. Соединение разрывается.
  6. Есть запрос на отключение сервера.

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

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

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

Все это поведение можно моделировать в линейной логике. В такой логике вы можете быть обязаны обратиться.

Например, запрос на отключение клиента может быть представлен таким типом. Как Connection client ⊸ 1. Вы не можете отбросить это значение иначе. Как применив его к соединению. Которое соответствует определенному клиенту. Другими словами. Программа не вводит проверку типа. Если она не отключает клиента по требованию.

Если вам интересно. Вот некоторые другие потенциальные модели для концепций. Которые могут появиться в программе чата:

start : 1 ⊸ Server s listen : Server s ⊸ Server s ⊗ Listen port s connection : Listen port s  ⊸ Listen port s  ⊗ Request k  ⊗ (Reject k & Accept k ⊗ Connection k s) receive : Connection k s ⊸ Connection k s ⊗ Message k disconnect : Connection k s ⊸ 1 stop : Server s ⊸ 1

Это не моделирование взаимодействия между событиями. Это достаточно выразительно. Чтобы сделать это.

Чтобы управлять списком подключений и обрабатывать логику программы чата. Мы могли бы смоделировать его со списком подключений. Который потребляет сообщения:

List (∃k. Connection k s) ⊗ Message j  ⊸ List (∃k. Connection k s)

При отключении он будет потреблять запрос на отключение:

(Connection j s ⊸ 1)  ⊸ List (∃k. Connection k s)  ⊸ List (∃k. Connection k s)

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

Линейная логика образует исчисление. Немного похожее на те. Которые используются в качестве основы для ML. Haskell или Idris. Он также предоставляет шаг нормализации. Который может быть использован для его оценки. Это не единственная форма логики. Способная моделировать взаимодействия. Но в то же время она может эффективно представлять такого рода идеи.

Небольшой ускоренный курс линейной логики

Предположим. Что у вас есть список значений. Каждое из которых помечено своим типом. Это может быть знакомая настройка. Если вы изучали типизированное лямбда-исчисление. Мы бы отображали их так и называли контекстами:

⊢ a,b,c...

Например, у вас может быть контекст с двумя числами и строкой:

⊢ int, int, string

Теперь эта система, кажется. Становится способной моделировать взаимодействия. Если мы требуем. Чтобы вы не могли просто добавлять и удалять значения из контекста. Например , если вы хотите перейти к⊢ int, string, вы должны явно сказать. Что вы можете стереть целые числа и сказать. Какое целое число вы стерли.

Можно выполнить сопряжение элементов в контексте с помощью дизъюнктивной операции:

⊢ a, b  ⊢ a ⅋ b

Если у вас есть два разных контекста. Вы можете объединить их с помощью конъюнктивной операции:

⊢ a ⊢ b  ⊢ a ⊗ b

Если вы будете следить за тем. Что вы объединили и как. Вы можете избежать или. По крайней мере. Изолировать сценарии. Которые приведут к тупикам. Это, в свою очередь, означает. Что ценности и требования к ценностям могут рассматриваться одинаково.

Теперь очевидно. Что есть некоторые ценности. Которые вы всегда можете уничтожить или создать. Целые числа и строки были бы такими. Если вы создаете пустой контекст и можете создать значение оттуда. То вы всегда можете создать такое значение. И поэтому вам разрешено копировать его. То, что значение может быть создано из пустого контекста. Можно обозначить восклицательным знаком.

⊢ !a

Вы можете стирать и дублировать такие значения бесплатно. Есть дуал для этой концепции. Отмеченный ?a. Который работает в обратном направлении. Если значение может быть уменьшено в контекст с только ~1 в нем. То он может быть отмечен знаком вопроса:

⊢ ?a

Эти правила формируют классическую линейную логику. Первые правила являются мультипликативными операторами. А последующие-экспоненциальными операторами. Я все равно буду вводить вам добавки.

Теперь, как и в типизированном лямбда-исчислении. Здесь есть тип sum. Его можно использовать для того чтобы два разных контекста выглядели одинаково:

⊢ a ⊢ b ⊢ a ⊕ b ⊢ a ⊕ b

Точно так же мы можем объединить два контекста. Когда они что-то разделяют.

⊢ a,c ⊢ b,c ⊢ a&b, c

Чтобы показать. Что это образует логику. Я представляю вам. Как это может быть использовано для опровержения предложения.

Небольшой пример

Допустим, у нас есть строка. Состоящая из пар двух разных букв. Я утверждаю. Что такая строка не может быть палиндромом. Мы бы это опровергли:

⊢ (a ≠ b) ⊗ paired s a b ⊗ palindrome s

Что такое палиндром?

palindrome "" palindrome s ⊸ palindrome (char a ++ s ++ char a)

Мы определяем пустую строку как палиндром. И тогда любая строка палиндрома. В которой мы добавляем символ . Также является палиндромом. Например:

Мы пропускаем палиндромы с нечетным числом букв в них. Хотя 🙂 Я пропустил это. Не раскрывая. Что означает это выражение. Эта недостающая база не меняет вывода и добавляет еще один случай. Так что я не исправляю его здесь. Хотя наше определение

Вы можете задаться вопросом. Как формальная логика справляется с такого рода ошибками? Одно дело-устно объяснить. Что ты имеешь в виду. Как это сделал я. Вы, вероятно. Замечаете такие ошибки. Когда пытаетесь доказать свойства палиндромов и работаете с определением. Было бы важно исправить это. Если бы мы делали это.

ОК. Палиндромы определены. Как насчет нашей парной строки?

paired (char a ++ char b) a b paired s a b ⊸ paired (s ++ char a ++ char b)

Точно так же мы берем базовый случай. Который представляет собой две буквы вместе. А затем рассматриваем любую парную строку с парными символами также как парную строку. Например, здесь есть парные струны. Однако пустая строка не рассматривается как парная строка.

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

⊢ (a ≠ b) ⊗ ((s = "") ⊕ ∃q.(s = q ++ char a ++ char b) ⊗ paired q) ⊗ ((s = "") ⊕ ∃q.(∃a. s = char a ++ q ++ char a) ⊗ palindrome q)

Этот символ означает Мы можем разбить это на следующие части:

⊢ (a ≠ b) ⊗ (s = char a ++ char b) ⊗ (s = "") ⊢ (a ≠ b) ⊗ (s = char a ++ char b) ⊗ ∃q.(∃a. s = char a ++ q ++ char a) ⊗ palindrome q ⊢ (a ≠ b) ⊗ (∃q.(s = q ++ char a ++ char b) ⊗ paired q) ⊗ (s = "") ⊢ (a ≠ b) ⊗ (s = q ++ char a ++ char b) ⊗ paired q ⊗ ∃q.(∃a. s = char a ++ q ++ char a) ⊗ palindrome q

Как только мы опровергаем каждое из этих выражений. Мы доказываем. Что предложение не имеет доказательства.

Первое выражение тут же опровергается:

⊢ (a ≠ b) ⊗ 0 ─────────────

Разверните палиндром во втором выражении. И мы узнаем. Что q должен быть Это долгий шаг. Но вы знаете. Что это можно сделать.

⊢ (a ≠ b) ⊗ (s = char a ++ char b) ⊗ (∃a. s = char a ++ char a)

Отсюда мы можем сделать вывод:

⊢ (a ≠ b) ⊗ char a = char a ⊗ char b = char a

Char является инъективным. Что означает именно то . Что char a = char bприводит к a = bтому. Что мы можем заключить и опровергнуть второе выражение.

⊢ (a ≠ b) ⊗ a = a ⊗ (b = a) ─────────────────────────── ⊢ 1 ⊗ ~1 ────────

Третье выражение опять же немедленно опровергается:

⊢ (a ≠ b) ⊗ ∃q.paired q ⊗ 0 ───────────────────────────

Мы можем использовать правило. Что длина ‘s’ ненулевая. Если она построена путем объединения непустых строк.

Четвертое выражение требует чего-то другого. Мы должны расширить определение палиндрома.

⊢ (a ≠ b) ⊗ (∃q.(s = q ++ char a ++ char b) ⊗ paired q) ⊗ (s = char a ++ char a)  ⊢ (a ≠ b) ⊗ (∃q.(s = q ++ char a ++ char b) ⊗ paired q) ⊗ ∃q.(∃a,b. s = char a ++ char b ++ q ++ char b ++ char a) ⊗ palindrome q

К обоим из них мы можем применить теорему о том. Что если мы знаем суффикс строки. То мы знаем. Что такое последний символ. Мы можем заключить. Что это должно быть так (char b = char a). Мы можем снова использовать инъективность char для вывода b = a.

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

В классической линейной логике каждое предложение имеет двойственность. Мы можем перевернуть предложение и заявить. Что было доказано следующее:

⊢ (a = b) ⅋ ~paired s a b ⅋ ~palindrome s

Это примерно означает то же самое. Что и все они вместе взятые:

⊢ (a ≠ b) ⊸ paired s a b ⊸ ~palindrome s ⊢ (a ≠ b) ⊸ palindrome s ⊸ ~paired s a b ⊢ paired s a b ⊸ palindrome s ⊸ (a = b)

Можно было бы сделать такое опровержение и с теорией типов. И это не слишком отличалось бы от этого.

Вывод

Здесь я попытался воспроизвести мысли. Которые пережил полтора года назад. Когда перестал работать над своим собственным языком программирования. Постепенно до меня дошло. Что у структурированного программирования есть этот недостаток. Я хотел представить эти идеи, думая. Что они могут повлиять на людей, например. Дать Идрису попробовать.

В последнее время я программирую в Идрисе. Но не уверен. Что буду придерживаться его. Тем не менее на этом языке вы можете построить доказательства. Подобные тому доказательству о палиндроме.

Однако, чтобы работать на вас. Нужно изменить точку зрения. В Idris вы не можете думать о типах как об аппаратных представлениях для значений или макетов памяти. Даже если вы строите натуральное число как (S (S (S (S Z)))), это не предназначенное представление памяти этого значения. А математическое представление для натурального числа. Вы работаете с этими математическими представлениями. А не с компьютерными числами.