Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Концепция владения в Rust на примерах, часть 3

Время жизни и структуры

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

#[derive(Debug)]
struct Person {
    name: &str // ошибка: ожидается параметр времени жизни
}

fn main() {
    let alice = Person { name: "Alice" };

    println!("alice: {:?}", alice);
}

Здесь компилятор не может исключить случаи, когда удаление имени члена происходит до удаления включающего его экземпляра Person. Мы можем исправить эту проблему, добавив параметр времени жизни 'a. При этом мы уведомляем компилятор, что имя будет жить как минимум столько же, сколько его родительский элемент.

#[derive(Debug)]
struct Person<'a> {
    name: &'a str
}

fn main() {
    let alice = Person { name: "Alice" };

    println!("alice: {:?}", alice);
}

Изменчивость

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

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

В Rust переменные по умолчанию имеют неизменяемые величины. Мы можем изменить это поведение, поставив перед переменной ключевое слово mut.

Например, мы по умолчанию не можем добавлять участников в Vec:

fn main() {
    let numbers = vec![1, 2, 3];

    numbers.push(4); // Ошибка: недьзя заимствовать как мутабельное

    println!("numbers: {:?}", numbers);
}

Если делаем владельца изменяемым, то это решает проблему.

fn main() {
    let mut numbers = vec![1, 2, 3];

    numbers.push(4);  // изменчивый Vec поддерживает push

    println!("numbers: {:?}", numbers);  // numbers: [1, 2, 3, 4]
}

MARSAW (Multiple Active Readers or Single Active Writer): несколько активных читателей или один активный писатель

Изменчивость ограничивает нашу способность заимствовать ссылки. В книге «Программирование на Rust» высокоуровневая концепция — это несколько читателей или один писатель.

Руководство по Rust описывает тот же принцип следующим образом:

... у вас может быть один из этих двух видов заимствований, но не оба одновременно:
• одна или несколько ссылок (&T) на ресурс,
• ровно одна изменяемая ссылка (&mut T).

Однако ни одно из описаний не попадает в цель. Во-первых, правило распространяется как на заимствованные ссылки, так и на владельцев. Во-вторых, правило применяется только тогда, когда в нем участвуют активные читатели и писатели. По существу, было бы более поучительно переделать правило следующим образом: «несколько активных читателей или один активный писатель» (MARSAW).

Термин «активный» заслуживает некоторого пояснения. Пока не используется изменяющий API писателя, он неактивен. После совершения изменения писатель остается активным на протяжении всей своей жизни. Считыватель, заимствованный до активации модуля записи, станет активным при первом использовании неизменяемого API владельца.

Давайте рассмотрим несколько примеров, чтобы конкретизировать эти идеи.

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

fn main() {
    let mut writer = vec![1,2,3];   // неактивно
    let reader = &writer;           // неактивно
}

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

fn main() {
    let mut writer = vec![1,2,3];
    let reader = &writer;

    println!("len: {}", reader.len()); // ошибки нет, но writer не активен
}

Точно так же мы пишем, не вызывая ошибки компилятора:

fn main() {
    let mut writer = vec![1,2,3];
    let reader = &writer;

    writer.push(4);  // ошибки нет, но reader не активен
}

Мы можем пойти дальше с помощью последовательного чтения-записи:

fn main() {
    let mut writer = vec![1,2,3];
    let reader = &writer;

    println!("len: {}", reader.len()); // ошибки нет, но writer не активен

    writer.push(4);                    // ошибки нет, но reader не активен
}

Мы можем использовать неизменяемый API писателя, а затем читать без ошибок:

fn main() {
    let mut writer = vec![1,2,3];
    let reader = &writer;

    writer.len();

    println!("len: {}", reader.len()); // ошибки нет, но reader и writer не активны
}

Что мы не можем сделать, так это активировать writer, а затем использовать reader. Следующий код вызывает ошибку, потому что оператор println! генерирует активный reader, который в паре с активным writer не допускается:

fn main() {
    let mut writer = vec![1,2,3];
    let reader = &writer;

    writer.push(4); // ошибка: невозможно заимствовать `writer` как изменяемый, 
                    // ибо он заимствован как неизменяемый

    println!("len: {}", reader.len());
}

Сообщение об ошибке объясняет ситуацию:

3 |     let reader = &writer;
  |                  ------- здесь происходит неизменяемое заимствование
4 | 
5 |     writer.push(4);         // активный writer, неактивный reader
  |     ^^^^^^^^^^^^^^ здесь происходит изменяемое заимствование
6 |     
7 |     println!("len: {}", reader.len()); // ошибка: нельзя заимствовать `writer`
  |     как изменяемый, т.к. он также заимствован как неизменяемый
  |                         ------ неизменяемое заимствование, 
  |                                которое затем здесь использовано 

Мы можем устранить ошибку перемещением заимствование вниз, после вызова push.

fn main() {
    let mut writer = vec![1,2,3];

    writer.push(4); 

    let reader = &writer;

    println!("len: {}", reader.len()); // ошибки нет, reader не активен, т.к. он был
                                       // заимствован после последней мутации  writer
}

Даже если переменная может быть объявлена как mut, её все же можно использовать для чтения. Обратите внимание, что writer.iter вызывает неявное неизменяемое заимствование. Однако это не нарушает MARSAW, поскольку заимствование происходит после последней мутации.

fn main() {
    let mut writer = vec![1,2,3];

    writer.push(4);

    for number in writer.iter() {
        println!("number: {}", number); // ошибок нет, неявное заимствование 
                                        // происходит после мутации  writer
    }
}

Тем не менее неявное заимствование может привести к нарушению MARSAW, если оно связано с записью. Следующий код не компилируется, потому что метод iter неявно заимствует неизменяемую ссылку, создавая одновременно активных читателей и писателей:

fn main() {
    let mut writer = vec![1,2,3];

    for number in writer.iter() {
        writer.push(number + 2); // ОШИБКА: нельзя заимствовать `writer` как изменяемый, 
			         // т.к. он заимствован как неизменяемый
    }
}

Ошибка (ниже) сообщает нам, где происходит заимствование. Используя вместе с принципом MARSAW, мы можем увидеть, что источником проблемы являются активные читатели и писатели, работающие одновременно.

4 |     for number in writer.iter() {
  |                   -------------
  |                   |
  |                   здесь делается неизменяемое заимствование
  |                   неизменяемое заимствование, которое позже здесь использовано 
5 |         writer.push(number + 2); // ОШИБКА: нельзя заимствовать `writer` как изменяемый,
  |                                  // т.к. он также заимствован как неизменяемый
  |         ^^^^^^^^^^^^^^^^^^^^^^^ здесь происходит изменямое заимствование

Заключение

Владение пронизывает Rust, поэтому очень важно понять его на раннем этапе изучения языка. Это руководство предлагает несколько простых примеров, иллюстрирующих, как работает право собственности. Ключевые моменты можно резюмировать следующим образом:

  1. Присваивание всегда привязывает значение к переменной, которая становится единственным владельцем значения.
  2. Передача и возврат по значению считаются присвоением.
  3. Значение всегда будет удалено к тому моменту, когда его владелец выйдет из области видимости.
  4. Переназначение величины приводит к перемещению или смене владельца.
  5. После перемещения бывший владелец больше не может быть использован.
  6. Ссылку можно заимствовать путем переназначения, указав перед её владельцем символ амперсанда (&).
  7. Заимствованная ссылка не может жить дольше, чем изначальная величина.

Послесловие переводчика

Где просто — там сто ангелов,
а где мудрёно — там ни одного.
Амвросий Оптинский

Стимулом к переводу оригинальной работы было желание разобраться с интересной концепцией. Перевод разместился на 15 страницах формата А4. Что можно сказать по этому поводу? Попробуем провести параллели с языком Си и классикой — учебником Кернигана и Ритчи по этому языку. Чтобы изложить суть любой концепции Си, достаточно одной-двух-трёх страниц учебника. Больше и не надо, ибо всё просто.

Однако с концепцией владения в Rust дела обстоят не так. Поначалу выглядит несложным, но через некоторое время обнаруживается, что за деревьями не видно леса. Теряется ощущение целостности, как будто бродишь с фонариком по тёмной комнате: отдельные предметы хорошо видны, но в целую картину это не складывается. Почему для реализации альтернативного способа управления памятью потребовалась именно такая реализация и как она это делает? Вот в чём вопрос.

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



Здесь — начало, а здесь - часть 2.

Опубликовано: 2021.01.07, последняя правка: 2021.01.08    13:59

Оцените

Отзывы

     2021/01/08 10:16, MihalNik          # 

Статья откровенно плохая, с постоянной путаницей в определениях (возможно, что-то добавилось в ходе перевода, но очевидно, что косяки изначально) и маркетинговой подменой понятий. Что было написано в заголовке? Автор не эксперт в Rust. Поэтому судить о концепции по данной статье никак нельзя. Либо надо искать более авторитетные источники, возможно лучше русскоязычные, если Вы сразу не заметили низкое качество изложения, либо смотреть альтернативные языки с концепцией владения. Я, например, не видел никакой сложности c этим в AL-IV: для того чтобы концепция работала достаточно отсутствия циклов в графе (цепочек взаимного владения), а удаление ветви дерева достаточно простой алгоритм.
Возможно разработчики Rust'a что-то перемудрили в самом языке, а возможно — только в концепции и терминологии, которая в принципе не нужна.

     2021/01/09 14:28, Автор сайта          # 

А что Вы называете маргетинговой подменой понятий? Поискал «маркетинг». Может к нему можно отнести слова о том, что в Rust управление памятью и не ручное, и без сборки мусора? Ну так это перечисление фактов. Типобезопасный язык? У меня нет возражений простив этих слов, а у Вас?

с постоянной путаницей в определениях

Лучше бы Вы указали на конкретные случаи этой путаницы.

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

Поискал информацию о концепции владения на сайте AL-IV с чувством надежды. Но только в разделе «Важные семантические особенности» — лишь несколько строк об этом. Это поспорит с лаконичностью спартанцев в ответном послании царю Филиппу. Можно было бы вздохнуть и забыть («Автор языка не позаботился о внятной документации»), но вспомнилось, что Вы на каком-то форуме называете себя «евангелистом» этого языка. А раз так, то я смотрю на Вас с надеждой, что Вы где-то опишите, для чего была задумана и как реализована в AL-IV концепция владения. А может это уже описано, да мы просто плохо гуглим, — тогда давайте ссылку.

     2021/01/10 15:33, MihalNik          # 

вспомнилось, что Вы на каком-то форуме называете себя «евангелистом» этого языка

Это просто Лисоярлык.

Но только в разделе «Важные семантические особенности» — лишь несколько строк об этом.

Где-то пара страниц на сайте со спецификацией. Содержание со ссылками там внизу.

опишите, для чего была задумана и как реализована в AL-IV концепция владения.

Каким образом я по-Вашему могу описать чужие задумки? Так-то я давно выкладывал то, что накопал в веб-архиве по ранним наработкам автора. По реализации — исходники там открыты, может как-то и найду время покопаться в подробностях.

     2021/01/10 16:35, Автор сайта          # 

Это просто Лисоярлык.

Он что, вообще за базаром не следит?

пара страниц на сайте

Спасибо, почитаю, но вопросы уже после беглого просмотра.

Каким образом я по-Вашему могу описать чужие задумки?

Я ж и вправду думал, что Вы — евангелист. Что напрямую советуетесь с Владимиром Кладовым. Видимо, канал общения отсутствует или весьма узок.

     2021/01/10 17:32, MihalNik          # 

не следит?

Ну, это просто статус пользователя, присвоенный мне им как администратором. Меня такие фантазии не беспокоят.
Там может права какие-то с этим связаны, может редактирование в разделе про AL-IV или ещё чего, не знаю.

Я ж и вправду думал, что Вы — евангелист. Что напрямую советуетесь с Владимиром Кладовым. Видимо, канал общения отсутствует или весьма узок.

Я знаю, что он читал какие-то наши обсуждения и даже что-то добавлял в язык.

вопросы уже после беглого просмотра.


Вопросы пишите, у меня так-то тоже есть, но может даже отвечу на какие-то.

     2021/01/11 03:56, Александр Коновалов aka Маздайщик          # 

Прочитал про AL-IV по ссылке выше. Для управления памятью используются встроенные в язык счётчики ссылок.

У счётчиков ссылок есть известный недостаток: они не позволяют освобождать память в закольцованных структурах данных. В AL-IV для решения этой проблемы введены слабые ссылки (которые не осуществляют владения) + реализован запрет на циклические связи на уровне типов. Когда на объект не остаётся ни одной сильной ссылки, он удаляется, при этом все слабые ссылки «обнуляются» — начинают ссылаться на NONE. Запрет на циклические связи на уровне типов означает, объект не может содержать прямо или косвенно сильные ссылки на себя. Например, написать дерево, связанный или двухсвязный список, использующий сильные ссылки, на нём невозможно, т.к. сильные ссылки внутри звеньев будут указывать на себя.

Для снятия последнего ограничения придуманы «владельцы». Если объект создаётся с модификатором OWNED BY, то он будет удалён одновременно с владеющим объектом. Т.е. для создания, например, односвязного списка нужно создать фиктивный объект-владелец, узлы списка создавать с модификатором OWNED BY (указывая этот фиктивный объект), в самих узлах использовать только слабые ссылки. Когда фиктивный объект-владелец будет удалён, будут удалены и все узлы списка. Довольно оригинальное решение, такое я в первый раз вижу.

     2021/01/11 18:15, Александр Коновалов aka Маздайщик          # 

Я, например, не видел никакой сложности c этим в AL-IV: для того чтобы концепция работала достаточно отсутствия циклов в графе (цепочек взаимного владения), а удаление ветви дерева достаточно простой алгоритм.

Владение в Rust и владение в AL-IV — разные вещи.

В Rust концепция владения означает, что (а) оператор присваивания не копирует значение, а перемещает¹, (б) ссылки не могут жить дольше, чем ссылаемые объекты, (в) отсутствие мутабельных псевдонимов — объект можно менять через единственную переменную.

¹ Для объектов, реализующих типаж Copy, оператор присваивания копирует значение.

В AL-IV владение — это способ управления памятью при помощи счётчиков ссылок + довольно красивый статический контроль отсутствия циклических сильных ссылок (больше нигде такого нет). Счётчики ссылок, как сильные, так и слабые, есть во многих языках: C++11, Rust, Umka… но они не гарантируют отсутствия циклических связей.

Владение в Rust имеет нулевые издержки времени выполнения (если явно не используются библиотечные контейнеры std::Cell<T> и std::RefCell<T>).

Владение в AL-IV имеет издержки, характерные для счётчиков ссылок, а именно инкременты и декременты на каждое присваивание (включая и слабые ссылки).

(Надо сказать, что AL-IV может компилироваться в текст на Паскале (Delphi), C++ и C#, в первых двух случаях счётчики ссылок используются, а во втором используется сборка мусора языка C# (.NET).)

     2021/01/11 20:12, MihalNik          # 

Владение в Rust и владение в AL-IV — разные вещи.

Да, но переводчик-то посетовал на отсутствие альтернативы сборке мусора и ручного управления памятью. Статья начинается с чрезмерно преувеличенных эпитетов, а содержимое про то, как ходить по неожиданным синтаксическим граблям, которых не было в С/++. Ее можно сократить раз в 10, объединив примеры, отличающиеся одной-двумя строками и закомментировав некорректные варианты с пояснениями. Да, код в примерах можно понять, но что написано русским языком? Например:

Значение всегда будет удалено к тому моменту, когда его владелец выйдет из области видимости.

Читается как затирание в памяти, а вовсе не то, о чём идет речь.

Владение в Rust имеет нулевые издержки времени выполнения (если явно не используются библиотечные контейнеры std::Cell<T> и std::RefCell<T>).

Звучит как "наше растительное масло без холестерина (если в него не кладут кусок жирной свинины)".
Речь-то про время жизни и доступ — Rust обрубает всё по максимуму. Типа задействовали переменную и забудьте. Как только потребуются множественные связи или нетривиальное время жизни — издержки появятся. Но вот требует ли оптимизация тривиального целых "концепций"? Это называется маркетингом.

     2021/01/11 22:32, Автор сайта          # 

Александр Коновалов aka Маздайщик

У счётчиков ссылок есть известный недостаток: они не позволяют освобождать память в закольцованных структурах данных.

От этого недостатка могло бы избавить хранение всех пар «откуда ссылка» — «куда ссылка». Тогда бы кольца выявлялись достаточно легко. Но этот способ относительно расточителен.

слабые ссылки (которые не осуществляют владения)

Внутриконтейнерные ссылки напрашиваются на то, чтобы их сделать не владеющими. Можно пойти ещё дальше: хранить в них не абсолютный адрес, а относительный. Тогда они станут совершенно не самостоятельны. А контейнер будет легко подвернуть сериализации/десериализации.

для создания, например, односвязного списка нужно создать фиктивный объект-владелец, узлы списка создавать с модификатором OWNED BY (указывая этот фиктивный объект), в самих узлах использовать только слабые ссылки. Когда фиктивный объект-владелец будет удалён, будут удалены и все узлы списка.

Получается, что узел (элемент?) списка имеет (содержит в себе) не только ссылку на соседа, но и ссылку на владельца. Т.е. все узлы списка указывают на своего владельца (раз они создаются с указанием владельца!), из-за чего список для своего хранения дополнительно потребует байтов_в_адресе * количество_узлов_в_списке? Или я неправильно понял?

Интересен ещё момент. Допустим, к созданному в AL-IV списку необходимо добавить новый элемент. Как будет запрашиваться новый кусок памяти? Фунrцией malloc()? Или new? Или alloca()? В каком месте разместится новый элемент? Когда перестают существовать объекты типа NONE и превращаются в доступную для использования память? Документация как-то туманна, евангелист и вправду бы пригодился.

MihalNik

Значение всегда будет удалено к тому моменту, когда его владелец выйдет из области видимости.

Признаю, перевод неудачен. В оригинале «value» — величина, значение, остальные варианты ещё дальше от темы. Надо будет доработать.

Статья начинается с чрезмерно преувеличенных эпитетов

Ой, я Вас умоляю… Ну пройдите мимо, если можете…

Как только потребуются множественные связи или нетривиальное время жизни — издержки появятся

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

     2021/01/12 12:43, MihalNik          # 

Т.е. для создания, например, односвязного списка нужно создать фиктивный объект-владелец, узлы списка создавать с модификатором OWNED BY (указывая этот фиктивный объект), в самих узлах использовать только слабые ссылки. Когда фиктивный объект-владелец будет удалён, будут удалены и все узлы списка.

Не вижу чтобы OWNED BY требовал типизации. Т.е. по идеи он позволяет создавать в динамике деревья владения из объектов любого класса с единственной целью — удалять их все целиком. А это совсем не то, что типизированные контейнеры, которые один раз отлаживаются и применяются многократно, в реальности не имея особых проблем с утечкой памяти.

Можно пойти ещё дальше: хранить в них не абсолютный адрес, а относительный. Тогда они станут совершенно не самостоятельны. А контейнер будет легко подвернуть сериализации/десериализации.

Именно так я сразу и предложил:
http://remdev.mybb.ru/viewtopic.php?id=188#p1447

Список делается просто: размещение дин. массивом с элементами (или ссылками на них), в которых есть пара чисел — номер пред. и след.

Более того, ранее к автору обращались:

Автор АЛФОРа написал примерно то же самое: не нужны списки, когда есть массивы.

     2021/01/12 16:53, MihalNik          # 

Получается, что узел (элемент?) списка имеет (содержит в себе) не только ссылку на соседа, но и ссылку на владельца. Т.е. все узлы списка указывают на своего владельца (раз они создаются с указанием владельца!), из-за чего список для своего хранения дополнительно потребует байтов_в_адресе * количество_узлов_в_списке? Или я неправильно понял?

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

     2021/01/12 22:59, Автор сайта          # 

Идея Владимира Кладова мне стала более-менее ясна. Но не скажу, что она меня очаровала. Так что тему владения и управления памятью придётся копать дальше и глубже.

Вашего предложения по ссылке не увидел. Ну да бог с ним. Вопрос не по теме: почему заглох этот форум и кто на нём хозяин?

     2021/01/13 06:41, MihalNik          # 

Почему заглох?
Площадок слишком много, а народа мало. Поэтому он в основном там, где более всего активны сами хозяева.
Т.е. каждый создает темы (в т.ч. ответные) прежде всего у себя с необходимыми ссылками.
Также это решило проблему цензуры.

Оператор OWNED BY в AL_IV уж очень кратко описан и примеров не видно — так что, думаю, я его неправильно всё-таки прочитал, и там присвоение типизированной ссылке, т.к. существование без ссылок бессмысленно.

     2021/01/13 18:36, Александр Коновалов aka Маздайщик          # 

MihalNik

…а содержимое про то, как ходить по неожиданным синтаксическим граблям, которых не было в С/++.

А в C/C++ не было концепции владения, которая гарантирует отсутствие висячих указателей. В Rust ссылки всегда указывают на «живой» объект, иначе программа не скомпилируется.

Но вот требует ли оптимизация тривиального целых „концепций“?

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

Это называется маркетингом.

Да, вокруг новых языков, особенно, Rust и Go, много маркетинговой болтовни. И это раздражает.


Маздайщик

У счётчиков ссылок есть известный недостаток: они не позволяют освобождать память в закольцованных структурах данных.

Автор сайта

От этого недостатка могло бы избавить хранение всех пар «откуда ссылка» — «куда ссылка». Тогда бы кольца выявлялись достаточно легко. Но этот способ относительно расточителен.

Фактически это будет сборка мусора.

Автор сайта

Внутриконтейнерные ссылки напрашиваются на то, чтобы их сделать не владеющими. Можно пойти ещё дальше: хранить в них не абсолютный адрес, а относительный. Тогда они станут совершенно не самостоятельны. А контейнер будет легко подвернуть сериализации/десериализации.

Тут надо правильно понимать, что такое «слабые ссылки». Слабые ссылки — это указатели, которые используются совместно с указателями со счётчиком ссылок, но объектом не владеют. Когда объект удаляется (пропадает последняя сильная ссылка на него), слабая ссылка начинает ссылаться на null, none, nil и т.д. — гарантируется, что или она указывает на валидный объект, либо на специальный нулевой указатель, висячей быть не может. Затраты времени выполнения на слабые ссылки даже больше, чем на сильные: присваивания и выход из области видимости также требуют работы со счётчиком ссылок (слабых ссылок), а разыменования требуют ещё и дополнительной проверки, что счётчик сильных ссылок не нулевой.

По поводу внутриконтейнерных ссылок — это смотря какой контейнер. Дерево и двухсвязный список — тоже контейнеры.

Получается, что узел (элемент?) списка имеет (содержит в себе) не только ссылку на соседа, но и ссылку на владельца. Т.е. все узлы списка указывают на своего владельца (раз они создаются с указанием владельца!), из-за чего список для своего хранения дополнительно потребует байтов_в_адресе * количество_узлов_в_списке? Или я неправильно понял?

Скорее наоборот — объект-владелец имеет ссылки на принадлежащие ему объекты, а значит, какие-то затраты памяти будут. Как это устроено в рантайме — я не знаю.

Список делается просто: размещение дин. массивом с элементами (или ссылками на них), в которых есть пара чисел — номер пред. и след.

Если всё адресное пространство рассматривать как массив, то указатель — это и есть номер элемента. И наоборот, массив + обращение по номеру элемента это эмуляция памяти и разыменование указателей. Т.е. из-за ограничений языка мы вынуждены эмулировать аппаратные концепции.

Впрочем, на Rust’е тоже есть сложности с двухсвязными списками. Их нужно реализовывать или с использованием небезопасного кода (блоки unsafe, в которых снимаются некоторые ограничения языка), или парой умных указателей: назад — сильная ссылка, вперёд — слабая. Но последний вариант имеет ряд недостатков.

Автор АЛФОРа написал примерно то же самое: не нужны списки, когда есть массивы.

Не нужна вилка, если есть ложка. Но есть блюда, которые удобнее есть вилкой, чем ложкой, например, спагетти.

     2021/01/13 18:53, Александр Коновалов aka Маздайщик          # 

В комментарии выше ↑↑↑ я ответил на реплики коллег, здесь напишу некоторые новые соображения об АЛФОРе.

Во-первых, конструкция OWNED BY напоминает использование регионов («арен») для управления памятью: Википедия, управление памятью на основе регионов. Идея этого подхода в следующем. Если есть группа взаимосвязанных объектов, то вместо независимых аллокаций и удалений каждого из них, можно эти объекты выделять в некотором «регионе», а после использования этих объектов сразу весь регион удалить. Например, в компиляторе может быть проход преобразования синтаксического дерева в промежуточный код (например, постфиксный код или SSE-представление). После этого прохода синтаксическое дерево уже не нужно. Поэтому узлы синтаксического дерева можно выделять в отдельном регионе, а потом весь этот регион удалить целиком.

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

Во-вторых, по-видимому, работа с памятью в АЛФОРе всё-таки допускает утечки на циклических ссылках. Как-то так (за корректность синтаксиса не ручаюсь):
x!_owner_temp = {X}
y!_reference_temp = {Y}, OWNED BY x
y.x = x
Объект x владеет объектом y, поэтому объект y будет удалён, когда будет удалён x. Объект y содержит ссылку на x, поэтому x будет удалён, когда будет удалён y.

Это зацикливание напрямую следует из описания языка. Так что или описание неправильное, или действительно в языке возможны утечки. Впрочем, если добавить одно ограничение на тип ссылки после OWNED BY, отсутствие утечек можно будет гарантировать.

     2021/01/14 00:35, Александр Коновалов aka Маздайщик          # 

Довольно интересен язык программирования Cyclone. Это исследовательский язык (создан был как эксперимент), сейчас уже не поддерживается, позиционировался как безопасная разновидность Си. С языком Си не совместим, хоть на него и очень похож. На cyclone.thelanguage.org можно прочитать про особенности языка и его отличие от Си.

В контексте обсуждения он интересен своим подходом к работе с памятью. Общее впечатление: переходное звено между Си и Растом. С одной стороны он внешне похож на Си и является достаточно консервативным его расширением. С другой — контроль времени жизни указателей почти такой же, как и в Rust, вплоть до синтаксиса. Указатель может параметризоваться меткой времени жизни (обозначается `r в Cyclone и 'r в Rust), метка указывается для параметров функций-указателей и возвращаемых значений-указателей. Метка гарантирует, что указателю невозможно будет присвоить адрес с меньшим временем жизни, чем у самого указателя, а значит, он не будет висячим.

Впрочем, в точности переходным звеном назвать его нельзя, поскольку в языке есть масса особенностей, которых и в Си не было, и в Rust они тоже не вошли. Указателям можно назначить кучу атрибутов: @nullable, @notnull, @zeroterm, @fat, @thin, @numelts и др. Проверки корректности указателей делаются во время выполнения программы. Например, если присвоить нулевой указатель указателю с атрибутом @notnull, вылетит исключение (в языке есть исключения в духе ML).

Указатели могут указывать на локальные переменные, на объекты, выделенные в глобальной куче (метка региона `H, malloc, new) и объекты, выделенные в локальном регионе (rmalloc, rnew). Объекты из глобальной кучи подчищаются консервативным сборщиком мусора. Объекты, выделенные в регионе, подчищаются, когда заканчивается время жизни региона.

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

Указатели со счётчиком ссылок тоже копировать присваиванием (создавать псевдонимы) просто так нельзя. Для копирования указателя нужно вызвать специальную функцию, увеличивающую счётчик. Для уничтожения псевдонима тоже нужно использовать специальную функцию.

В общем, как-то мудрёно сделаны оба этих вида указателя. Но, с другой стороны, язык-то экспериментальный.

Ссылку из второго комментария прочитать, тем не менее, рекомендую. Идеи, похожие на идеи Rust’а (т.к. Rust их и заимствовал ;-)), но в целом всё проще и понятнее, чем в Rust.

     2021/01/19 23:32, Автор сайта          # 

В общем, как-то мудрёно сделаны оба этих вида указателя

В Rust мне осталось неясным, как принимается решение о местонахождении объектов при их создании (стек? «куча»?). А пока для себя сделал вывод, что концепция типов, гарантирующие уникальность, будет посимпатичнее. Но и там неясность: непонятно, как эта концепция обеспечивает чистоту функций при работе с вводом/выводом, т. е. с побочными эффектами. Напоминает манипуляции фокусников: по каждая по отдельности манипуляция понятна, но почему получается такой итог — ясности нет.

Но, с другой стороны, язык-то экспериментальный.

Ничего себе экспериментальный! Сколько проектов на нём написано, во всяких рейтингах далеко не последний.

     2021/01/20 12:11, Александр Коновалов aka Маздайщик          # 

Но и там неясность: непонятно, как эта концепция обеспечивает чистоту функций при работе с вводом/выводом, т. е. с побочными эффектами. Напоминает манипуляции фокусников: по каждая по отдельности манипуляция понятна, но почему получается такой итог — ясности нет.

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

Ничего себе экспериментальный! Сколько проектов на нём написано, во всяких рейтингах далеко не последний.

В Википедии он назван исследовательским языком и написано, что автор прекратил разработку с мотивацией «исследовательские цели достигнуты». Так что, наверное, я ошибся, назвав его экспериментальным. Он исследовательский.

Вообще, язык симпатичный, писать на нём хочется. Основные концепции языка просты для понимания сишного программиста (в отличие от Rust’а).

Хотя, есть и недостатки, простительные для исследовательского языка. Во-первых, синтаксис атрибутов указателей, на мой взгляд, громоздкий и неэстетичный (хотя есть синтаксический сахар вроде @ и `r). Во-вторых, есть и неочевидные вещи. Например, алгебраические типы данных занимают одно машинное слово, хотя внутри них могут быть значения из нескольких слов. Значит, они, скорее всего реализованы указателями на реальные значения. Только непонятно: где эти значения аллоцируются и когда их память очищается.

А вообще, я написал комментарий про Cyclone, потому что захотел поделиться весьма вкусной пищей для размышления. На той неделе я решил почитать руководство по Cyclone и мне язык понравился.

В Rust мне осталось неясным, как принимается решение о местонахождении объектов при их создании (стек? «куча»?).

На сколько я понимаю, пользователь новые объекты может создать только в стеке, во всяком случае в безопасном подмножестве. Если пользователь инициализирует умный указатель некоторым объектом, то вызываются два конструктора.
let b = Box::new(Point { x: 0.0, y: 0.0 })
  • Выделяется память на стеке под умный указатель.
  • Выделяется память на стеке под объект.
  • Вызывается конструктор объекта и инициализирует эту память.
  • Вызывается конструктор умного указателя. Он выделяет в куче память размером с объект и перемещает значение объекта в кучу.
  • Т.к. объект, выделенный на стеке, был перемещён, память на стеке под него освобождается.

На стеке остаётся только умный указатель, ссылающийся на объект в куче.

Примерно тоже самое будет происходить в C++ в таком вызове std::make_shared:
auto b = std::make_shared(Point(0.0, 0.0));

     2021/01/21 00:00, alextretyak          # 

auto b = std::make_shared(Point(0.0, 0.0));
Это некорректный код. Правильно так:
auto b = std::make_shared<Point>(0.0, 0.0);
Или так:
auto b = std::shared_ptr<Point>(new Point(0.0, 0.0));
[Замечу, что оба этих способа создания shared_ptr имеют ‘право на жизнь’/‘свои плюсы и минусы’ (см. статью[https://habr.com/ru/post/509004/]).]

Добавить свой отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

●  Концепция владения в Rust на примерах

●●  Концепция владения в Rust на примерах, часть 2

●●  Концепция владения в Rust на примерах, часть 3

●  О неулучшаемой архитектуре процессоров

●  Двадцать тысяч строк кода, которые потрясут мир?

●  Почему владение/заимствование в Rust такое сложное?

●  Масштабируемые архитектуры программ

●  О создании языков

●  Почему Хаскелл так мало используется в отрасли?

●  Программирование исчезнет. Будет дрессировка нейронных сетей

●  Бесплатный софт в мышеловке

●  Исповедь правового нигилиста

●  Русской операционной системой должна стать ReactOS

●  Почему обречён язык Форт

●  Программирование без программистов — это медицина без врачей

●  Электроника без электронщиков

●  Программисты-профессионалы и программирующие инженеры

●  Статьи Дмитрия Караваева

●●  Идеальный транслятор

●●  В защиту PL/1

●●  К вопросу о совершенствовании языка программирования

●●  О реализации метода оптимизации при компиляции

●●  О реализации метода распределения регистров при компиляции

●●  О распределении памяти при выполнении теста Кнута

●●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●●  О размещении переменных в стеке

●●  Сколько проходов должно быть у транслятора?

●●  Чтение лексем

●●  Экстракоды при синтезе программ

●●  Об исключенных командах или за что «списали» инструкцию INTO?

●●  Типы в инженерных задачах

●●  Непрерывное компилирование

●●  Об одной реализации специализированных операторов ввода-вывода

●●  Особенности реализации структурной обработки исключений в Win64

●●  О русском языке в программировании

●●  Формула расчета точности для умножения

●●  Права доступа к переменным

●●  Заметки о выходе из функции без значения и зеркальности get и put

●●  Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

●●  Ошибка при отсутствии выполняемых действий

●●  О PL/1 и почему в нём не зарезервированы ключевые слова

●●  Не поминайте всуе PL/1

●●  Скорость в попугаях

●●  Крах операции «Инкогнито»

●●  Предопределённый результат

●●  Поддержка профилирования кода программы на низком уровне

●  Следующие 7000 языков программирования

●●  Что нового с 1966 года?

●●  Наблюдаемая эволюция языка программирования

●●  Ряд важных языков в 2017 году

●●  Слоны в комнате

●●  Следующие 7000 языков программирования: заключение

Компьютерный юмор

Новости и прочее




Последние отзывы

2021/01/21 00:00 ••• alextretyak
Концепция владения в Rust на примерах, часть 3

2021/01/21 00:00 ••• alextretyak
Выбор кодировки для компилятора

2021/01/20 00:10 ••• Автор сайта
Признаки устаревшего языка

2021/01/17 23:15 ••• Бурановский дедушка
Изменение длины объекта в стеке во время исполнения

2021/01/16 22:47 ••• Автор сайта
Предложения и замечания

2021/01/11 17:51 ••• Автор сайта
Утилита транслитерации русского C/C++ в стандартный

2021/01/09 18:08 ••• kt
Типы в инженерных задачах

2021/01/06 15:34 ••• Автор сайта
О неулучшаемой архитектуре процессоров

2020/12/18 16:04 ••• Автор сайта
Не поминайте всуе PL/1

2020/10/30 15:33 ••• Бурановский дедушка
Указатели и ссылки в C++

2020/10/29 15:02 ••• kt
Экстракоды при синтезе программ

2020/10/08 23:00 ••• Автор сайта
Короткие комментарии

2020/10/07 17:34 ••• NuShaman
Энтузиасты-разработчики компиляторов и их проекты

2020/10/05 23:19 ••• Неслучайный читатель
Обработка ошибок