Что означает статическая типизация языка?

Question

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

Моя проблема заключается в следующем:

Предположим, что у нас есть два Тьюринг-полных языка: A и B.Предполагается, что A является «типобезопасным», а «B» — нет.Предположим, мне дана программа L для проверки корректности любой программы, написанной на языке A.Что мне мешает перевести любую программу, написанную на В, на А, применив L.Если P преобразует из A в B, то почему PL не является средством проверки допустимого типа для любой программы, написанной на B?

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

Answer 1

Пусть A будет вашим полным по Тьюрингу языком, который должен быть статически типизирован, и пусть A' будет языком, который вы получите от A, когда вы удалите проверку типов (но не аннотации типов, поскольку они также служат другим целям).Принятые программы А будут подмножеством принятых программ А'.В частности, A' также будет полным по Тьюрингу.

Дан ваш переводчик P из B в A (и наоборот).Что оно должно делать?Он может сделать одно из двух:

1. Во-первых, он мог транслировать любую программу y из B в программу A.В этом случае LPy всегда будет возвращать True, поскольку программы A по определению правильно типизированы.

2. Во-вторых, P мог бы перевести любую программу y из B в программу A'.В этом случае LPy вернет True, если Py является программой A, и False в противном случае.

Поскольку первый случай не дает ничего интересного, давайте остановимся на втором случае, который, вероятно, вы и имеете в виду.Говорит ли нам функция LP, определенная в программах B, что-нибудь интересное о программах B?Я говорю нет, потому что оно не инвариантно при изменении P.Поскольку A является полным по Тьюрингу, даже во втором случае P можно выбрать так, чтобы его образ лежал в A.Тогда LP всегда была бы True.С другой стороны, P можно выбрать так, чтобы некоторые программы отображались в дополнение к A в A'.В этом случае LP выдаст False для некоторых (возможно, всех) программ B.Как видите, вы не получаете ничего, что зависит только от y.

Я могу также выразить это более математически следующим образом:Существует категория C языков программирования, объектами которой являются языки программирования, а морфизмы которых являются трансляторами с одного языка программирования на другой.В частности, если существует морфизм P:X -> Y, Y по крайней мере так же выразителен, как и X.Между каждой парой Тьюринг-полных языков существуют морфизмы в обоих направлениях.Для каждого объекта X из C (т.е.для каждого языка программирования) у нас есть связанный набор, скажем {X} (плохая запись, я знаю) тех частично определенных функций, которые могут быть вычислены программами X.Каждый морфизм P:X -> Y тогда индуцирует включение {X} -> {Y} множеств.Формально обратим все эти морфизмы P:X -> Y, которые индуцируют тождество {X} -> {Y}.Полученную категорию (которая, выражаясь математическим языком, является локализацией С) я назову С'.Теперь включение А -> А' является морфизмом в С'.Однако он не сохраняется при автоморфизмах А', т. е. морфизм А -> А' не является инвариантом А' в С'.Другими словами:с этой абстрактной точки зрения атрибут «статически типизированный» не поддается определению и может быть произвольно прикреплен к языку.

Чтобы прояснить мою точку зрения, вы также можете думать о C' как о категории, скажем, геометрических форм в трехмерном пространстве вместе с евклидовыми движениями как морфизмами.Тогда A' и B — две геометрические фигуры, а P и Q — евклидовы движения, приводящие B к A' и наоборот.Например, A' и B могут быть двумя сферами.Теперь зафиксируем на А' точку, которая будет обозначать подмножество А из А'.Назовем этот момент «статически типизированным».Мы хотим знать, является ли точка B статически типизированной.Итак, мы берем такую ​​точку y, отображаем ее через P на A' и проверяем, является ли это нашей отмеченной точкой на A'.Как легко видеть, это зависит от выбранной карты P или, другими словами:Отмеченная точка на сфере не сохраняется автоморфизмами (то есть евклидовыми движениями, отображающими сферу сама на себя) этой сферы.

Answer 2

Если Вы можете перевести каждый B '(программа, написанная в b) в эквивалентное a' (что правильно, если B 'есть), то язык B пользуется так же столько же «Тип безопасности» как язык A (в теоретическом смысле, конечно ;-) - В основном это будет означать, что B такое, что вы можете сделать идеальный тип выхода. Но это чрезвычайно ограничено на динамичный язык - например, рассмотрим:

if userinput() = 'bah':
    thefun(23)
else:
    thefun('gotcha')

куда thefun (Давайте предположим) - это WhitesAfe для аргумента INT, но не для аргумента CL. Теперь - как вы переводите это на язык A в первую очередь...?

Answer 3

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

• А не может быть сопоставлено с Б
• безопасность типов не является лексическим свойством языка

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

Answer 4

В этом нет ничего "рыбного". ;)

Набор нуринговых языков, которые являются безопасными по отношению к любому нетривиальному [1] Тип системы Т это строгий Подмножество местно-полных языков. Как таковой, в общем случае, ни переводчик п^-1 от Преступность к А. существуют; Поэтому ни один переводчик-сперма-тип-проверка Вспомогательный^-1.

Реакция колена на такого рода претензии может быть: Бред какой то! Оба А. и Преступность Turing-Complete, поэтому я могу выразить Любые Вычислимая функция In либо язык! И, действительно, это правильно - вы могу Выразите любую вычислимую функцию на любом языке; Однако довольно часто вы также можете выразить Довольно больше. Отказ В частности, вы можете построить выражения, денотационные семантики которых не четко определены, такие как те, которые могут с радостью попытаться взять арифметическую сумму строк символов «FOO» и «бар» (это суть Chubsdad. Алекс Мартеллиответ). Эти виды выражений могут быть «в« языке » Преступность, но может просто не быть уверенным на языке А., Потому что обозначающая семантика неопределена, при этом нет разумного способа перевести их.

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

Обратите внимание, что в то время как вышеизложенное является обычным видом примера, приведенного для объяснения достоинств системы статического типа, она, возможно, слишком скромная. В целом, система статического типа не должна быть ограничена просто применением правильности применения параметров, но действительно может выразить Любые Желаемое свойство программы, которая может быть доказана при компиляционном времени. Например, можно построить системы типа, которые обеспечивают ограничение, что один выпускает ручку файловой системы (например в базу данных, файл, сетевой сокет, и т. д.) в рамках того же масштаба, в котором он был приобретен. Очевидно, что это чрезвычайно ценно в таких областях как системы жизнеобеспечения, среди прочего, где доказательство правильность как можно больше параметров системы абсолютно необходима. Если вы удовлетворяете систему статического типа, вы можете получить такие доказательства бесплатно.

[1] Нетривиальным, я имею в виду, что не все возможные выражения хорошо набираются.

Answer 5

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

Answer 6

Позвольте мне ответить на это наоборот:

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

Один «динамически набран», что означает, что у вас есть какая-то оболочка, где вы можете запрограммировать, набрав определения в эту оболочку, подумайте об этом, как Fython White Shell.

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