Меня интересует, почему натуральные числа так любимы авторами книг по теории языков программирования и теории типов (например, Дж. Митчелл, Основы языков программирования и Б. Пирс, Типы и языки программирования). Описание простейшего лямбда-исчисления и, в частности, языка программирования PCF обычно основано на принципах Ната и Була. Для людей, использующих и обучающих промышленным PL общего назначения, гораздо более естественно рассматривать целые числа, а не натуральные. Можете ли вы назвать несколько веских причин, почему теоретик ЛП предпочитает нац? Кроме того, это немного менее сложно. Есть ли фундаментальные причины или это просто честь традиции?
UPD Для всех этих комментариев об «фундаментальности» натуралов: я хорошо осведомлен обо всех этих классных вещах, но я бы предпочел увидеть пример, когда действительно важно иметь эти свойства в теории типов теории PL. Например, широко упоминается индукция. Когда у нас есть какая-либо логика (которая просто типизирована как LC), как и базовая логика первого порядка, мы действительно используем индукцию - но индукцию по дереву деривации (которое мы также имеем в лямбде)
Мой вопрос в основном исходит от людей из промышленности, которые хотят получить фундаментальную теорию языков программирования. Раньше у них были целые числа в своих программах, и без конкретных аргументов и приложений к изучаемой теории (в нашем случае, к теории типов), почему для изучения языков только с натами они чувствуют себя довольно разочарованными.
источник
Ответы:
Краткий ответ: натуральные числа - это первые предельные порядковые числа. Следовательно, они играют центральную роль в аксиоматической теории множеств (например, аксиома бесконечности - это утверждение, что они существуют) и в логике, и теоретики PL имеют тенденцию делиться фундаментальными заботами с логиками. Мы хотим иметь доступ к принципу индукции, чтобы доказать полную правильность, завершение и подобные свойства, и натуральные вещества - это естественный выбор порядка.
Я не хочу подразумевать, что двоичные целые числа конечной ширины - все же менее интересные объекты. Они являются представлениями p-adics и позволяют нам использовать методы степенных рядов в теории чисел и комбинаторике. Это означает, что их значение становится более заметным в алгоритмах, чем в PL, поскольку именно тогда мы начинаем больше заботиться о сложности, а не об окончании.
источник
Naturals - гораздо более фундаментальная концепция, чем целые числа.
Индукция происходит над натуральными числами, а целые числа могут быть получены из натуральных чисел с простым добавлением унарного обратного оператора.
Я бы на самом деле хотел задать обратный вопрос: почему ранние разработчики языка программирования (и регистрации машин) закрепляли целые числа в качестве основного типа данных, когда они настолько вторичны и так легко получены из натуральных чисел?
Я подозреваю, что это только потому, что были некоторые классные двоичные кодировки, которые могли элегантно обрабатывать целые числа. ;-)
Подумайте, как часто вы хотите игнорировать отрицательный диапазон целочисленного значения в программе, и учтите, что импульс имеет целочисленный тип без знака для восстановления потерянного бита.
источник
источник
Еще одна причина (связанная с уже приведенными, но этот ответ добавляет новую информацию) заключается в том, что существует очень простая конструкция без натуральных факторов, которая сопровождается хорошим принципом индукции [как уже было сказано] , Что не было расширено, так это то, как трудно придумать конструкцию целых чисел без фактора.
Чем больше я занимаюсь программированием там, где мне нужна высокая степень уверенности, тем больше мне нужны натуралы, и я считаю, что иметь только целые числа, заранее определенные для меня, настоящая боль.
источник
Есть ли веские причины, по которым теоретики PL предпочитают натуральные числа вместо целых? Есть некоторые, но в учебнике по семантике языка программирования, я думаю, нет технической причины, по которой они нужны. Я не могу думать ни о каком другом месте, кроме систем зависимого типа, где индукция данных важна в теории PL. Другие учебники Майка Гордона , Дэвида Шмидта , Боба Теннента и Джона Рейнольдса этого не делают. (И эти книги, вероятно, были бы намного более подходящими для обучения людей, которые заботятся о промышленных PL общего назначения!)
Итак, у вас есть доказательство того, что в этом нет необходимости. Фактически, я бы сказал, что хороший учебник по теории PL должен быть параметрическим в примитивных типах языка программирования, и было бы неверно предлагать иное.
источник
Природные и логические выражения и операции над ними могут быть прямо и просто закодированы в чистом лямбда-исчислении, как так называемые церковные цифры (и, я полагаю, церковные числа). Не ясно, как можно красиво кодировать целые числа, хотя это, очевидно, можно сделать.
источник