Ряд языков программирования заявляют неизменяемость переменных (immutability) как одну из своих главных фич. Среди них семейство ML (OCaml, F#, Standard ML) и Haskell, а также молодые Clojure и Rust. Если вы незнакомы с ними, то наверняка удивлялись: а чем это отличается от const в C и C++? Давайте разберемся.
РЕКОМЕНДУЕМ:
Олимпиады по программированию
Примеры мы будем писать на OCaml и Rust, чтобы продемонстрировать сходство и различия реализации этой идеи в разных языках. Выполнить примеры на OCaml можно в онлайне на сайте try.ocamlpro.com, а примеры на Rust — на play.rust-lang.org.
Краткая история переменных
В самый ранний период компьютерной истории, когда люди писали машинный код, вся организация памяти программы была на совести программиста и все адреса тоже приходилось указывать вручную.
Чуть позже появились ассемблеры, которые позволяли указывать символьные метки вместо числовых адресов. Возьмем пример на условном языке ассемблера и посмотрим, как будет выглядеть вывод строки hello world в бесконечном цикле.
|
1 2 3 4 5 6 7 |
msg: .ascii "hello world" foo: push msg call print jmp foo |
Любой современный ассемблер за нас придумает, как разместить в памяти строку hello world и машинные инструкции, а метку foo в jmp foo заменит реальным адресом инструкции push msg в памяти. Затем компоновщик (linker) подставит вместо названия функции print ее реальный адрес в библиотеке, но это другая история. Это первый уровень абстракции по сравнению с машинным кодом.
Первые версии фортрана и прочих ранних языков были скорее развитыми макроассемблерами, чем компиляторами в современном понимании. Даже С на момент своего появления транслировал каждый оператор языка в одну-две машинные команды PDP-11.
Безопасность памяти в языках ассемблера отсутствует: можно записать любые данные по адресу любой метки, и последствия проявятся только во время выполнения. С тех пор языки развивались в сторону большей абстрактности и выразительности: появилась возможность указать смысл переменных и ограничить их возможные значения с помощью типов.
Неизменным оставалось одно: каждое имя переменной связано с определенным участком памяти или как минимум одними и теми же данными. Присваивание нового значения в императивном программировании всегда затирает старые данные в памяти и заменяет их новыми.
Наибольшие сложности это вызывает, когда компилятор начинает применять к переменным оптимизации. Если содержимое памяти может измениться в любой момент, судить о том, можно ли заинлайнить значение переменной, непросто.
Еще сложнее становятся задачи вроде undo и redo. Если ты пишешь текстовый или графический редактор с возможностью отменить изменения, в языке вроде C есть только два варианта: хранить каждую версию данных либо явно хранить список выполненных операций вроде DeleteLineRange(10,11) и ApplyFilter(Blur, radius=2).
Даже в более простых задачах может оказаться, что функции из библиотеки модифицируют существующие данные, и, если оригинальные данные еще понадобятся, их приходится копировать целиком. Популярность copy.copy() и copy.deepcopy() в коде на Python — яркое тому подтверждение.
Константы
Механизм констант в языках вроде C — первый маленький шаг к неизменяемым переменным. Если мы пишем const int foo = 17, у компилятора есть гарантия, что значение, связанное с именем foo, никогда не изменится во время выполнения. Это позволяет безопасно оптимизировать код таким образом, что ассоциации имени foo или значения 17 с каким-то адресом в памяти там не останется — во всех выражениях вроде bar = foo*2 слово foo будет просто заменено на значение 17. С данными большей сложности и размеров такая наивная оптимизация уже не работает, но простор для оптимизаций все равно больше, чем с изменяемыми переменными.
Остается одно главное ограничение — имена констант связаны с определенными значениями для всей программы или модуля. Именно это ограничение и снимают неизменяемые переменные.
Связывание имен со значениями и области видимости
Возможности языков обычно работают не в изоляции, а вместе. Не делать постоянной связь имен со значениями можно, если создание новых областей видимости (scope) будет простым и «дешевым».
Часто для связывания (binding) имени со значением используют синтаксис вроде let name = value и его вариации. Каждое связывание открывает новую область видимости. Посмотрим пример на OCaml.
|
1 2 3 4 5 6 7 |
(* Scope 0 *) let x = "hello" let () = Printf.printf "%s" x let x = " world" (* Scope 1 *) let () = Printf.printf "%s\n" x |
Или похожий пример на Rust.
|
1 2 3 4 5 6 7 8 9 |
fn main() { // Scope 0 let x = 5; println!("The value of x is: {}", x); let x = x + 1; // Scope 1 println!("The value of x is: {}", x); } |
Это очень простой пример, который отличается от const в C только тем, что нам не пришлось выдумывать новое имя для каждого нового значения. В обоих случаях компилятору понятно, что за пределами области видимости Scope 0 (после второго let) старое значение x никем не используется и выделенную под него память можно безопасно освободить или вовсе не выделять под него память динамически.
Гораздо интереснее случаи, когда имена используются заново, а старые данные остаются жить в памяти.
Замыкания
Области видимости называются лексическими, если значение переменной навсегда определяется местом, где она определена, и не может измениться в будущем. Применение таких областей видимости делает возможными замыкания — функции, которые захватывают переменные из контекста, где были созданы.
Продемонстрировать это можно, если сначала определить переменную и использовать ее в функции, а затем переопределить и использовать в другой функции. Вот пример на OCaml.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(* Scope 0 *) let msg = "hello world" (* Scope 1 *) let greeting () = Printf.printf "%s\n" msg let msg = "bye world" (* Scope 2 *) let farewell () = Printf.printf "%s\n" msg let () = greeting (); farewell () |
Программа выведет сначала hello world, затем bye world. Функции greeting и farewell ссылаются на одно и то же имя переменной msg. Ключевой момент в том, что выражение let msg = "bye world", которое открывает область видимости Scope 2, никак не влияет на предыдущие области видимости.
Для функции greeting переменная msg связана со значением hello world, и это значение останется в памяти программы, хотя уже не связано ни с каким именем.
Синтаксис let greeting () = ... — это синтаксический сахар для связывания анонимной функции с именем, и «подлинная форма» этих выражений была бы let greeting = fun () -> .... Поскольку в OCaml и Haskell все функции являются замыканиями и захватывают значения из своей области видимости, там нет причин использовать более длинную форму.
РЕКОМЕНДУЕМ:
Программирование в консоли
В Rust существуют как лексические области видимости, так и динамические, в которых значение переменных определяется местом вызова функции. Функции, созданные с помощью ключевого слова fn, ведут себя как функции в стиле C, и попытки сослаться на созданную с помощью let переменную вызовут ошибку компиляции (смотри rustc --explain E0434). Замыкания в нем можно создать, явно связав анонимную функцию с именем.
Вот пример синтаксиса анонимных функций в Rust.
|
1 |
[crayon-66233760bc7b0390111911 inline="true" class="language-rust"]<span class="pun">|параметр|</span> <span class="pun">-></span> <span class="pun">тип</span> <span class="pun">{выражение}</span> |
[/crayon]
В качестве типа для функций, которые не возвращают полезных значений, используется тип unit с единственным значением
(). В OCaml, если мы хотим явно указать тип функции, он так и будет называться
unit.
|
1 |
let greeting : unit -> unit = fun () -> print_endline "hello world" |
В Haskell и Rust токен () используется и для названия этого типа. Кроме того, в Rust указывать тип анонимных функций обязательно, поэтому синтаксис анонимной функции без возвращаемого значения будет || -> () { ... }.
Воспользовавшись этими знаниями, напишем аналог нашей программы на Rust.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
fn main() { // Scope 0 let msg = "hello world"; let greeting = || -> () { println!("{}", msg) }; let msg = "bye world"; // Scope 1 let farewell = || -> () { println!("{}", msg) }; greeting(); farewell(); } |
Если ее выполнить, результат будет такой же, как у примера на OCaml.
Замыкания как форма инкапсуляции
Сочетание замыканий с изменяемыми переменными позволяет реализовать инкапсуляцию без необходимости прибегать к средствам ООП и контролю за доступом к полям объекта.
Для следующего примера нам нужно знать, что изменяемую переменную (ссылку) в OCaml можно создать функцией let myrref = ref $value, а получить ее значение — оператором !myref.
Мы напишем функцию, которая создает функцию-счетчик, увеличивающий свое значение при каждом вызове:
|
1 2 3 4 5 6 7 8 9 10 |
let make_counter initial_value = let counter = ref initial_value in fun () -> let () = counter := !counter + 1 in !counter let my_counter = make_counter 0 let () = Printf.printf "%d\n" (my_counter ()); Printf.printf "%d\n" (my_counter ()); Printf.printf "%d\n" (my_counter ()) |
При выполнении программы в выводе мы увидим 1 2 3. Каждый раз, когда мы вызываем make_counter, она создает изменяемую переменную и функцию, которая ее увеличивает и возвращает новое значение. При этом извне той функции counter ничто не может ни изменить значение счетчика, ни прочитать его без увеличения.
Такого же эффекта можно добиться и без изменяемых переменных, если возвращать не одно значение, а кортеж из нового значения и новой функции.
Структуры данных
Пока что мы работали только со значениями примитивных типов, а теперь посмотрим на структуры данных. В OCaml, Haskell и Rust они реализуются с помощью кортежей и типов-сумм (sum type, tagged union) вроде
|
1 |
type cmyk_color = Key | CMY_Color of (int, int, int) |
В качестве примера рассмотрим односвязный список. Связные списки так широко применяются для построения неизменяемых структур данных, что для них OCaml и Haskell предоставляют встроенный синтаксис. Общий смысл: список может быть пустым либо состоять из головы и хвоста — пары из значения и другого списка (возможно, пустого). В условном синтаксисе это будет выглядеть так.
|
1 |
type 'a list = [] | 'a :: 'a list |
В OСaml можно писать let xs = [1; 2; 3], что будет синтаксическим сахаром для 1 :: (2 :: (3 :: [])).
В отличие от списков в Python или Ruby, такая реализация представляет собой именно односвязный список и не позволяет получать произвольный доступ к любому элементу (и уж тем более — их модифицировать). Безопасность памяти — первое очевидное преимущество.
Менее очевидное преимущество в том, что создание нового списка из существующего через добавление нового элемента в его начало безопасно для старых данных. Посмотрим на пример.
|
1 2 3 |
let xs = [2; 3] let ys = 1 :: xs (* ys = [1; 2; 3] *) |
Поскольку никакого способа изменить что-то внутри исходного списка xs = [2;3] не существует, в памяти программы новый список ys будет состоять из значения 1 и указателя на старый список xs. Компилятор знает, что это безопасно, и не выделяет память под новый список.
Если элементы списка сами по себе большие, экономия памяти с таким подходом может получиться весьма значительной. При этом хранение предыдущих версий списка не вызывает никаких сложностей, достаточно сохранять их в отдельных переменных — в памяти программы это опять же будут просто указатели на отдельные части нового большого списка.
Первый очевидный недостаток — в большей алгоритмической сложности типичных операций. Например, получить элемент с номером n можно, только пройдя первые n элементов:
|
1 2 3 4 5 6 |
let rec nth n xs = match xs with | [] -> None | y :: ys -> if n = 0 then y else nth (n - 1) ys |
Второй недостаток в том, что некоторые алгоритмы приведут к неявному копированию всего списка значений в новый участок памяти. К примеру, перевернуть список можно, только создав новый на основе старого.
Насколько эти недостатки значительны, зависит от задачи и от того, с чем сравниваем. Поскольку OCaml, Haskell и Rust компилируются в машинный код и организация памяти для таких типов оказывается куда компактнее, чем для объектов в Python или Ruby, производительность может оказаться выше, несмотря на формально большую сложность алгоритма. Кроме того, если старый список все еще нужен для других целей, память все равно пришлось бы копировать. Здесь это хотя бы не требует нашего явного участия.
Тем не менее при творческом подходе можно улучшить производительность неизменяемых структур данных и привести ее к O(1) для определенных операций. К примеру, отсутствие быстрого произвольного доступа к элементам можно компенсировать с помощью так называемых зипперов. Zipper — это кортеж из двух частей структуры данных и ее элемента, с которым мы в данный момент работаем. Вот пример для списка.
|
1 |
type 'a list_zipper = 'a list * 'a * 'a list |
С помощью зипперов можно реализовать программу вроде текстового редактора или оконного менеджера в чисто функциональном стиле, не сильно жертвуя при этом производительностью. Когда пользователь переходит к другой строке, «окно» зиппера сдвигается, таким образом время доступа к текущей строке в любой момент одинаково.
Заключение
Мы рассмотрели только самые основы, но я надеюсь, что эти знания помогут вам в изучении популярного ныне Rust или классических OCaml и Haskell.
РЕКОМЕНДУЕМ:
Повышение продуктивности программиста
К структурам данных мы только прикоснулись, но, помимо зиппера, существуют и другие способы создавать структуры с постоянным средним временем доступа. Из двух списков можно создать очередь, а массив с доступом по номеру элемента можно сделать из двоичного дерева поиска. За деталями можно обратиться к книге Криса Окасаки Purely Functional Data Structures или его диссертации.
