Что такое ссылочная прозрачность?

Question

Что означает термин ссылочная прозрачность ? Я слышал, что это описывается как «это означает, что вы можете заменить равные равными», но это кажется неадекватным объяснением.

Answer 1

Термин «ссылочная прозрачность» происходит от аналитической философии , ветви философии, которая анализирует конструкции, утверждения и аргументы естественного языка, основанные на методах логики и математики. Другими словами, это самая близкая тема вне компьютерной науки к тому, что мы называем семантика языка программирования . Философ Уиллард Куайн был ответственен за инициирование концепции прозрачности ссылок, но это также подразумевалось в подходах Бертрана Рассела и Альфреда Уайтхеда.

По своей сути «ссылочная прозрачность» - очень простая и понятная идея. Термин «референт» используется в аналитической философии, чтобы говорить о вещи, к которой относится выражение . Это примерно то же самое, что мы подразумеваем под «значением» или «обозначением» в семантике языка программирования. Используя пример Эндрю Биркетта ( сообщение в блоге ), термин "столица Шотландии" относится к городу Эдинбургу. Это простой пример «референта».

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

Шотландский парламент собирается в столице Шотландии.

означает то же, что и

Шотландский парламент собирается в Эдинбурге.

Таким образом, контекст "Шотландский парламент встречается в ..." является ссылочно прозрачным контекстом. Мы можем заменить «столицу Шотландии» на «Эдинбург», не меняя смысла. Другими словами, контекст заботится только о том, к чему относится этот термин, и ничего более. В этом смысле контекст «ссылочно прозрачен».

С другой стороны, в предложении

Эдинбург является столицей Шотландии с 1999 года.

мы не можем сделать такую ​​замену. Если бы мы это сделали, мы бы получили «Эдинбург был Эдинбургом с 1999 года», что является сумасшедшей вещью, и не передает того же значения, что и первоначальное предложение. Таким образом, может показаться, что контекст «Эдинбург был ... с 1999 года» является косвенно непрозрачным (противоположность ссылочно-прозрачным). По-видимому, его волнует нечто большее , чем то, к чему относится этот термин. Что это?

Такие вещи, как "столица Шотландии", называются определенными терминами , и они долго не причиняли головной боли логикам и философам. Рассел и Куайн разобрались с ними, сказав, что они на самом деле не являются «референтными», то есть ошибочно думать, что приведенные выше примеры используются для обозначения сущностей. Правильный способ понять, что «Эдинбург был столицей Шотландии с 1999 года» - это сказать

Столица Шотландии существует с 1999 года, и эта столица - Эдинбург.

Это предложение не может быть преобразовано в сумасшедшее. Задача решена! Суть Куайна состояла в том, чтобы сказать, что естественный язык является грязным или, по крайней мере, сложным, потому что он сделан удобным для практического использования, но философы и логики должны вносить ясность, правильно понимая их. Ссылочная прозрачность - это инструмент, который используется для обеспечения такой ясности значения .

Какое все это имеет отношение к программированию? Не очень, на самом деле. Как мы уже говорили, ссылочная прозрачность - это инструмент, который используется для понимания языка, то есть для назначения , означающего . Кристофер Стрейчи , который основал семантику языка программирования, использовал его в своем исследовании значения. Его основополагающая статья " Основные понятия в языках программирования " доступна в Интернете. Это красивая бумага, и каждый может ее прочитать и понять. Поэтому, пожалуйста, сделайте это. Вы будете очень просветленным. Он вводит термин «ссылочная прозрачность» в этом параграфе:

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

Использование слова «по существу» предполагает, что Стрейчи перефразирует его, чтобы объяснить его простыми словами. Функциональные программисты, кажется, понимают этот абзац по-своему. Есть 9 других случаев "ссылочной прозрачности" в статье, но они, кажется, не беспокоятся ни о каких других. Фактически вся статья Стрейчи посвящена объяснению значения императивных языков программирования . Но сегодня функциональные программисты утверждают, что императивные языки программирования не референтно прозрачны. Стрейчи перевернется в своей могиле.

Мы можем спасти ситуацию. Мы сказали, что естественный язык «грязный или, по крайней мере, сложный», потому что он сделан удобным для практического использования. Языки программирования одинаковы. Они «грязные или, по крайней мере, сложные», потому что они сделаны так, чтобы их было удобно использовать на практике. Это не значит, что они должны нас смущать. Они просто должны быть поняты правильно, используя мета-язык, который является ссылочно прозрачным, чтобы у нас была ясность смысла. В статье, которую я цитировал, Стрейчи делает именно это. Он объясняет значение императивных языков программирования, разбивая их на элементарные понятия, нигде не теряя ясности. Важной частью его анализа является указание на то, что выражения в языках программирования имеют два вида «значений», называемых l-значениями и r-значениями . До статьи Стрейчи это не было понято, и воцарилась путаница. Сегодня определение C упоминает об этом регулярно, и каждый программист C понимает это различие. (Понятно ли это понимают программисты на других языках).

И Куайн, и Стрейчи были обеспокоены значением языковых конструкций, которые включают некоторую форму зависимости от контекста. Например, наш пример «Эдинбург является столицей Шотландии с 1999 года» означает тот факт, что «столица Шотландии» зависит от времени, в которое она рассматривается. Такая зависимость от контекста является реальностью, как на естественных языках, так и на языках программирования. Даже в функциональном программировании свободные и связанные переменные должны интерпретироваться с учетом контекста, в котором они появляются. Зависимость от контекста любого вида так или иначе блокирует ссылочную прозрачность. Если вы попытаетесь понять значение терминов без учета контекста, от которого они зависят, вы снова получите путаницу. Куайна интересовало значение модальной логики. Он считал, что модальная логика была непрозрачной по ссылкам, и ее следует очистить, переведя ее в ссылочно-прозрачную структуру (например, рассматривая необходимость как доказуемость). Он в значительной степени проиграл эту дискуссию. Логики и философы одинаково находили возможную мировую семантику Крипке совершенно адекватной. Подобная ситуация также царит с императивным программированием. Зависимость от состояния, объясняемая Стрейчи, и зависимость от запаса, объясняемая Рейнольдсом (аналогично возможной мировой семантике Крипке), вполне адекватны. Функциональные программисты мало знают об этом исследовании. Их идеи относительно ссылочной прозрачности должны быть приняты с большим количеством соли.

[Дополнительное примечание: Приведенные выше примеры иллюстрируют, что простая фраза, такая как «столица Шотландии», имеет несколько уровней значения. На одном уровне мы можем говорить о столице в настоящее время. На другом уровне мы могли бы говорить о всех возможных столицах, которые Шотландия могла иметь с течением времени. Мы можем «увеличить» конкретный контекст и «уменьшить», чтобы довольно легко охватить все контексты в обычной практике. Эффективность естественного языка использует нашу способность сделать это. Императивные языки программирования эффективны практически так же. Мы можем использовать переменную x справа от присваивания ( r-значение ), чтобы говорить о ее значении в определенном состоянии. Или мы можем говорить о его l-значении , которое охватывает все состояния. Людей редко смущают такие вещи. Однако они могут или не могут точно объяснить все слои значения, присущие языковым конструкциям. Все такие слои значения не обязательно являются «очевидными», и это вопрос науки, чтобы изучить их должным образом. Однако неспособность простых людей объяснять такие многоуровневые значения не означает, что они смущены ими.]

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

Answer 2

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

Вот пример ссылочной прозрачной функции:

int plusOne(int x)
{
  return x+1;
}

С помощью ссылочной прозрачной функции, с учетом ввода и функции, вы можете заменить ее значением вместо вызова функции. Поэтому вместо вызова plusOne с параметром 5 мы можем просто заменить его на 6.

Другой хороший пример - математика в целом. В математике с заданной функцией и входным значением она всегда будет отображаться на одно и то же выходное значение. f (x) = x + 1. Поэтому функции в математике являются ссылочно прозрачными.

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

Ссылочная прозрачность всегда используется в функциональных языках, таких как Haskell.

-

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

//global G
int G = 10;

int plusG(int x)
{//G can be modified externally returning different values.
  return x + G;
}

Другим примером является функция-член в объектно-ориентированном языке программирования. Функции-члены обычно работают с переменными-членами и, следовательно, будут непрозрачными для ссылок. Хотя функции-члены, конечно, могут быть прозрачными по ссылкам.

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

Answer 3

Ссылочно-прозрачная функция - это функция, которая зависит только от ее ввода.

Answer 4

[Это постскриптум к моему ответу от 25 марта, чтобы приблизить обсуждение к проблемам функционального / императивного программирования.]

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

• В то время как философы / логики используют такие термины, как «ссылка», «обозначение», «designatum» и « bedeutung » (немецкий термин Фреге), функциональные программисты используют термин «значение». (Это не совсем их работа. Я замечаю, что Лэндин, Стрейчи и их потомки также использовали термин «ценность», чтобы говорить об упоминании / обозначении. Это может быть просто терминологическое упрощение, которое представили Ландин и Стрейчи, но похоже, что большая разница при наивном использовании.)

• Функциональные программисты, кажется, полагают, что эти "значения" существуют внутри языка программирования, а не снаружи. При этом они отличаются как от философов, так и от семантистов языка программирования.

• Кажется, они считают, что эти "значения" должны быть получены путем оценки.

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

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

Это полностью противоречит тому, что говорят философы / логики. Они говорят, что контекст является ссылочным или прозрачным по ссылкам, если выражение в этом контексте можно заменить другим выражением , которое ссылается на то же самое (выражение coreferential ). Кто эти философы / логики? Среди них Фреге , Рассел , Уайтхед , Карнап , Куайн , Церковь и бесчисленное множество других. Каждый из них - высокая фигура. Объединенная интеллектуальная сила этих логиков поразительна, если не сказать больше. Все они единодушны в том положении, что ссылки / обозначения существуют вне формального языка, и выражения в языке могут говорить только о их. Таким образом, все, что можно сделать в языке, - это заменить одно выражение другим выражением, относящимся к той же сущности. Сами ссылки / обозначения не существуют в языке. Почему функциональные программисты отклоняются от этой устоявшейся традиции?

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

Ландин

(а) каждое выражение имеет вложенная структура подвыражения, (b) каждое подвыражение обозначает что-то (обычно число, значение истинности или числовая функция) , (c) вещь, которую обозначает выражение, то есть его «ценность» зависит только от значений его выражения, а не о других их свойствах. [Добавлен акцент]

Стой

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

Птица и вадлер :

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

Таким образом, в ретроспективе, попытки Ландина и Стрейчи упростить терминологию путем замены «ссылки» / «обозначения» на «значения» могли быть необоснованными. Как только кто-то слышит о «ценности», возникает соблазн подумать о процессе оценки, который ведет к нему. Не менее заманчиво думать о том, что оценка производит, как о «ценности», хотя может быть совершенно ясно, что это не обозначение. Это то, что я понимаю, что произошло с понятием «ссылочной прозрачности» в глазах функциональных программистов. Но «ценность», о которой говорили ранние семантики, - , а не - результат оценки или вывода функции или любой подобной вещи. Это обозначение термина.

Как только мы понимаем так называемую «ценность» выражения («ссылка» или «обозначение» в дискурсе классических философов) как сложный математический / концептуальный объект, открываются все виды возможностей.

• Strachey интерпретировал переменные в императивных языках программирования как L-значения , как упоминалось в моем ответе от 25 марта, который является сложным концептуальным объектом, который не имеет прямого представления в синтаксисе языка программирования.
• Он также интерпретировал команды на таких языках как функции состояния к состоянию, еще один пример сложного математического объекта, который не является «значением» в синтаксисе.
• Даже вызов функции с побочным эффектом в C имеет четко определенное «значение» в качестве преобразователя состояний, который отображает состояния в пары состояний и значений (так называемая «монада» в терминологии функциональных программистов).

Нежелание функциональных программистов называть такие языки «ссылочно-прозрачными» просто подразумевает, что они не хотят признавать такие сложные математические / концептуальные объекты как «значения». С другой стороны, они, похоже, совершенно готовы назвать преобразователь состояния «значением», когда он помещен в их собственный любимый синтаксис и наделен модным словом типа «монада». Я должен сказать, что они совершенно непоследовательны, даже если мы дадим им понять, что их идея «ссылочной прозрачности» имеет некоторую последовательность.

Немного истории может пролить свет на то, как возникли эти заблуждения. Период между 1962 и 1967 годами был очень интенсивным для Кристофера Стрейчи. В период с 1962 по 1965 год он работал неполный рабочий день в качестве помощника исследователя в Морисе Уилксе для разработки и реализации языка программирования, который стал известен как CPL. Это был императивный язык программирования, но он должен был также иметь мощные функциональные возможности языка программирования. Ландин, который был сотрудником Strachey в своей консалтинговой компании, оказал огромное влияние на взгляд Strachey на языки программирования. В знаковой статье 1965 года « Next 700 языков программирования » Ландин безоговорочно продвигает функциональные языки программирования (называя их денотативными языками) и описывает императивные языки программирования как их «антитезу». В последующем обсуждении мы видим, что Стрейчи вызывает сомнения в сильной позиции Лэндина.

... Форма DLs подмножество всех языков. Они интересное подмножество, но один который неудобно использовать, если вы не привыкли к нему. Нам нужно их, потому что на данный момент мы не знаем, как построить доказательства с языками, которые включают императивы и прыжки. [Добавлен акцент]

В 1965 году Стрейчи занял должность читателя в Оксфорде и, похоже, работал практически полный рабочий день над разработкой теории императивов и прыжков. К 1967 году он был готов с теорией, которую он преподавал в своем курсе « Основные понятия в языках программирования » в копенгагенской летней школе. Лекционные заметки должны были быть опубликованы, но, к сожалению, из-за редактирование, производство никогда не материализовалось; лайкбольшая часть работы Стрейчи в Оксфорде, однако, газета имела влиятельный частный тираж. "( Мартин Кэмпбелл-Келли )

Сложность получения работ Стрейчи могла привести к распространению путаницы, когда люди полагались на вторичные источники и слухи. Но теперь, когда « Фундаментальные понятия » легко доступны в Интернете, нет необходимости прибегать к угадыванию работы. Мы должны прочитать это и решить, что имел в виду Стрейчи. В частности:

• В разделе 3.2 он имеет дело с "выражениями", где он говорит о "ссылочной прозрачности R-значения".
• Его раздел 3.3 посвящен «командам», где он говорит о «ссылочной прозрачности L-значения».
• В разделе 3.4.5 он говорит о «функциях и процедурах» и заявляет, что «любое отклонение ссылочной прозрачности R-значения в контексте R-значения должно либо устранить, разложив выражение на несколько команд и проще выражения, или, если это окажется трудным, предмет комментария. "

Любые разговоры о «ссылочной прозрачности» без понимания различия между L-значениями, R-значениями и другими сложными объектами, населяющими концептуальный универсум императивного программиста, в корне ошибочны.

Answer 5

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

Answer 6

Ссылочно-прозрачная функция - это функция, которая действует как математическая функция; при одинаковых входах он всегда будет давать одинаковые выходы. Это означает, что переданное состояние не изменяется и что у функции нет собственного состояния.

Answer 7

Для тех, кто нуждается в кратком объяснении, я рискну один (но прочитайте раскрытие ниже).

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

f x = x + x,

легкость, с которой вы можете (безопасно) заменить f (foo) на foo + foo в рамках этого определения, не имея слишком много ограничений на то, где вы можете выполнить это сокращение, является хорошим показателем того, насколько ссылочная прозрачность Ваш язык программирования имеет.

Например, если бы foo был x ++ в смысле программирования на C, то вы не могли бы выполнить это сокращение безопасно (то есть, если бы вы выполняли это сокращение, вы не получили бы ту же программу, с которой начали) .

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

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

Answer 8

Если вы интересуетесь этимологией (то есть, почему у этой концепции есть именно это имя), взгляните на мой пост в блоге на эту тему. Терминология исходит от философа / логика Куайна.

Answer 9

1. Denotational-семантика основана на языках моделирования путем создания доменов, которые составляют денотируемые значения .
2. Функциональные программисты используют термин значение для описания сходимости вычислений, основанных на правилах переписывания языка, т.е. его операционная семантика.

В 1 есть ясность двух рассматриваемых языков:

• моделируемый объектный язык
• язык моделирования, метаязык

Во 2, благодаря близости объекта и метаязыка, их можно спутать.

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

Итак, профессор Редди, перефразирую вас так: -)

В контексте функционального программирования и семантики термин Ссылочный Прозрачность не является ссылочной прозрачностью.

Answer 10

Следующий ответ, который, я надеюсь, добавляет и квалифицирует спорный 1-й и 3-й ответы.

Допустим, что выражение обозначает или относится к какой-то референт. Однако вопрос заключается в том, можно ли эти ссылки изоморфно кодировать как часть самих выражений, называя такие выражения «значениями». Например, значения литеральных чисел являются подмножеством набора арифметических выражений, значения истинности являются подмножеством набора логических выражений и т. Д. Идея состоит в том, чтобы оценить выражение по его значению (если оно есть). Таким образом, слово «значение» может относиться к обозначению или к выделенному элементу набора выражений. Но если между референтом и значением есть изоморфизм (биекция) Можно сказать, что это одно и то же. (Это сказал, нужно быть осторожным, чтобы определить референты и изоморфизм, как доказано в области денотации семантика. Чтобы привести пример, упомянутый в ответах на 3-й ответ, определение алгебраического типа данных data Nat = Zero | Suc Nat не соответствуют ожидаемому набору натуральных чисел.)

Давайте напишем E[·] для выражения с дырой, также известного в некоторых кругах как «контекст». Два примера контекста для C-подобных выражений: [·]+1 и [·]++.

Давайте напишем [[·]] для функции, которая принимает выражение (без отверстия) и передает его значение (референт, обозначение и т. д.) в некоторых вселенная, обеспечивающая смысл. (Я заимствую запись с поля денотационной семантики.)

Давайте адаптируем определение Куайна несколько формально следующим образом: контекст E[·] является ссылочно прозрачным, если заданы любые два выражения E1 и E2 (без дырок) там), что [[E1]] = [[E2]] (т.е. выражения обозначают / относятся к тот же референт), тогда это тот случай, когда [[E[E1]]] = [[E[E2]]] (т.е. заполнение отверстие с E1 или E2 приводит к выражениям, которые также обозначают референт).

Правило Лейбница о замене равных на равные обычно выражается как «если E1 = E2 затем E[E1] = E[E2] ', что говорит о том, что E[·] является функцией. Функция (или в этом отношении программа, вычисляющая функцию) является отображением источник к цели, так что существует не более одного целевого элемента для каждого источника элемент. Недетерминированные функции являются неправильными, они либо отношения, функции, доставляющие множества и т. д. Если в правлении Лейбница равенство = денотационные то двойные скобки просто принимаются как должное и опущены. Таким образом, ссылочно-прозрачный контекст - это функция. И правило Лейбница является основным компонентом эквалайзерного мышления, поэтому эквалайзерное мышление определенно связано с прозрачностью ссылок.

Хотя [[·]] - это функция от выражений до обозначений, она может быть функция от выражений до «значений», понимаемых как ограниченное подмножество выражения и [[·]] можно понимать как оценку.

Теперь, если E1 - это выражение, а E2 - это значение, которое мы понимаем большинством людей при определении ссылочной прозрачности в терминах выражений, значений и оценки. Но, как показано в 1-м и 3-м ответах на этой странице, это неточное определение.

Проблема с контекстами, такими как [·]++, заключается не в побочном эффекте, а в том, что его значение не определено в C изоморфно его значению. Функции не значения (ну, указатели на функции есть), тогда как в функциональных языках программирования они есть. Приземлиться, Стрейчи и пионеры денотационной семантики были довольно умны в использование функциональных миров для придания смысла.

Для императивных C-подобных языков мы можем (примерно) предоставить семантику выражения с использованием функции [[·]] : Expression -> (State -> State x Value).

Value является подмножеством Expression. State содержит пары (Идентификатор, значение). Семантическая функция принимает выражение и поставляет как это означает функцию из текущего состояния в пару с обновленным состояние и значение. Например, [[x]] - функция из текущего состоянияк паре, первый компонент которой является текущим состоянием, а второй Компонент является значением х. Напротив, [[x++]] является функцией от текущее состояние для пары, первый компонент которой является состоянием, в котором значение х увеличивается, и чей второй компонент является именно этим значением. В этом в этом смысле контекст [·]++ является ссылочно прозрачным, если он удовлетворяет определение дано выше.

Я думаю, что функциональные программисты имеют право использовать ссылочную прозрачность в ощущение, что они естественным образом восстанавливают [[·]] как функцию от выражений к значениям. Функции являются первоклассными значениями, и состояние также может быть значением, а не денотат. Государственная монада является (частично) чистым механизмом прохождения (или нить) состояние.