В функциональных языках, как понятие неизменности применяется к адресам в памяти?

Question

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

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

Может кто-нибудь объяснить, как функциональный язык имеет дело с местными сортами? Идея быть «на месте» отброшена и заменена структурой данных, которая поддерживает структурный обмен?

Я действительно пытаюсь понять, как неизменность соответствует адресам в памяти (подумайте о указателях). Например, данные на месте сортировки не уничтожаются, а перемещаются по новым адресам. Это считается мутацией? Я думаю, что ответ - да. Но тогда как вы можете делать такие вещи, как вращение, чтобы сбалансировать бинарное дерево? Как функциональные программисты думают об указателях?

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

Answer 1

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

Как происходит распределение памяти на вашем любимом языке для сбора мусора (Python, Java, Ruby и т. Д.)? Вы не знаете Эта деталь оставлена ​​на усмотрение компилятора и / или среды выполнения. Вы путаете семантику языка программирования с подробностью реализации для компилятора этого языка. Я допускаю, что C / C ++ значительно размывает различия, но это размытие, вероятно, является наиболее существенной особенностью этих языков на данный момент.

Рассмотрим общую ассоциативную структуру данных, структуру C:

struct address 
{ 
   char number[10]; 
   char street[100]; 
   char city[50]; 
   char state[15]; 
};

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

public class Record {
  public int number;
  public String street;
  public String city;
  public String state;
}

Как дела с макетом в памяти? Вы не знаете Даже если вы замените строки на символьные буферы, вы не узнаете * * * * * Очевидно, Javac делает это возможным. С постоянными структурами данных в функциональных языках ничем не отличается: место, куда вещи помещаются в память, зависит от компилятора , который не связан семантикой языка, который он компилирует.

Answer 2

1. Просто чтобы убрать это с пути:

   Например, данные сортировки на месте не уничтожаются, а перемещаются на новые адреса.

   Это не имеет никакого смысла. Если данные «перемещаются по новым адресам», алгоритм по определению больше не работает «на месте».

2. Существует давняя традиция функциональных языков программирования, которые не настаивают на 100% чистоте. Начиная с Lisp, через ML, затем OCaml, Scala или Clojure - все эти языки имеют изменяемые структуры данных. В «мультипарадигмальных» языках, имеющих аспекты функционального программирования, таких как JavaScript, Python и даже Java, у вас также есть изменяемые структуры данных. Haskell скорее исключение в своей настойчивости в отношении чистоты.

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

4. Даже если вы настаиваете на чистоте, вы все равно можете обращаться с изменяемой памятью вашего компьютера так же, как с другой частью изменяемого «внешнего мира» - как если бы это был какой-то пользовательский ввод-вывод, системные часы , сетевая связь или генератор случайных чисел. То есть, чтобы иметь дело с изменяемой памятью чисто функциональным способом, вам понадобятся два компонента: во-первых, вам понадобится способ описать что нужно сделать с изменяемой памятью путем построения «плана» - который неизменен; и тогда вам понадобится переводчик, который сможет принять этот неизменный план и применить его к фактическому изменяемому фрагменту памяти. То есть интерпретатор, который мутирует память, становится чем-то внешним по отношению к ядру языка и рассматривается как любая другая часть «внешнего изменяемого мира».

5. В языках, которые не настаивают на чистоте, вы можете реализовать и небольшой предметно-ориентированный язык для построения неизменяемых планов, а также интерпретатор, который фактически изменяет память, тем самым разделяя чистые части от нечистых побочных эффектов изменчивых частей. Например, Кьюзано и Бьярнасон в своей книге «Функциональное программирование в Scala» имеют главу 14.2.5 буквально под названием «Чисто функциональная быстрая сортировка на месте» .

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