Последствия невозможности добавить натуральные числа в C

Question

В Системе F я могу определить подлинную функцию общего сложения, используя церковные цифры.

В Haskell я не могу определить эту функцию из-за нижнего значения. Например, в haskell, если x + y = x, тогда я не могу сказать, что y равен нулю - если x - это дно, x + y = x для любого y. Таким образом, сложение не является истинным дополнением, а приближением к нему.

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

Итак, имеем:

В Системе F можно определить дополнение, но невозможно получить полную реализацию (поскольку нет бесконечного оборудования).

В Haskell невозможно определить дополнение (из-за дна), и невозможно получить полную реализацию.

В C невозможно определить функцию полного сложения (поскольку семантика всего ограничена), но возможны совместимые реализации.

Таким образом, все 3 формальные системы (Haskell, System F и C), похоже, имеют разные компромиссные решения.

Так каковы последствия выбора одного над другим?

Answer 1

Haskell

Это странная проблема, потому что вы работаете со смутным представлением =._|_ = _|_ только «держит» (и даже тогда вы действительно должны использовать ⊑) на семантическом уровне домена.Если мы различаем информацию, доступную на семантическом уровне предметной области, и равенство в самом языке, то совершенно правильно сказать, что True ⊑ x + y == x -> True ⊑ y == 0.

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

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

C

Вы утверждаете, что C требует всего (включая адресное пространство)иметь конечный размер, и, следовательно, семантика C "накладывает ограничение" на размер представимых натуральных чисел.На самом деле, нет.Стандарт C99 гласит следующее: «Любой тип указателя может быть преобразован в целочисленный тип. За исключением указанного ранее, результат определяется реализацией. Если результат не может быть представлен в целочисленном типе, поведениене определено. Результат не обязательно должен находиться в диапазоне значений любого целочисленного типа. "В обосновании документа далее подчеркивается, что «C теперь реализован на широком спектре архитектур. Хотя некоторые из этих архитектур имеют унифицированные указатели, которые имеют размер некоторого целочисленного типа, максимально переносимый код не может принимать какого-либо необходимого соответствия между различными типами указателей ицелочисленные типы. В некоторых реализациях указатели могут быть даже шире, чем любой целочисленный тип. "

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

Answer 2

У вас есть набор теорий в качестве основы для рассуждений; конечная реальность, семантика Хаскелла, система F - лишь некоторые из них.

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

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

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

Answer 3

Я уверен, что вы слышали афоризм, что «в теории нет разницы между теорией и практикой, но на практике есть».

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

РЕДАКТИРОВАТЬ:

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

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

В лямбда-исчислении вы можете представить список как функцию, которая возвращает функцию, которая вызывается с истинным значением, возвращает бит 1, а вызываемая с ложным возвращает функцию, которая делает то же самое.для бита 2 и т. д.

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

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

Что касается простоты учета крайних случаев, C очень мало вам поможет.Вы можете возвращать специальные значения для представления переполнения / недополнения и даже пытаться сделать их заразными (например, IEEE-754 NaN), но вы не получите жалоб во время компиляции, если не проверите.Вы можете попытаться перегрузить сигнал SIGFPE или что-то похожее на проблемы с ловушками.

Я не могу сказать, что у равен нулю - если х - низ, х + у = х для любого у.

Если вы хотите сделать символьные манипуляции, Matlab и Mathematica реализованы на языках C и C, подобных.Тем не менее, Python имеет хорошо оптимизированную реализацию bigint, которая используется для всех целочисленных типов.Это, вероятно, не подходит для представления действительно очень больших чисел.