Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки 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

ОценитеОценки посетителей
   █████████████████████ 3 (50%)
   ███████ 1 (16.6%)
   ███████ 1 (16.6%)
   ███████ 1 (16.6%)

Отзывы

✅  2021/01/08 10:16, MihalNik          #0 

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

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

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

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

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

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

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

✅  2021/01/10 15:33, MihalNik          #2 

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

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

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

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

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

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

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

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

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

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

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

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

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

✅  2021/01/10 17:32, MihalNik          #4 

не следит?

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

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

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

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


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

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

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

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

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

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

Я, например, не видел никакой сложности 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          #7 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MihalNik

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

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

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

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

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

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

✅  2021/01/12 12:43, MihalNik          #9 

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

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

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

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

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

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

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

✅  2021/01/12 16:53, MihalNik          #10 

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

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

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

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

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

✅  2021/01/13 06:41, MihalNik          #12 

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

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

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

MihalNik

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

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

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

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

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

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


Маздайщик

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

Автор сайта

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

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

Автор сайта

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

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

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

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

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

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

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

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

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

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

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

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

Во-первых, конструкция 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 Маздайщик          #15 

Довольно интересен язык программирования 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, Автор сайта          #16 

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

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

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

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

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

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

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

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

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

Вообще, язык симпатичный, писать на нём хочется. Основные концепции языка просты для понимания сишного программиста (в отличие от 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          #18 

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/).

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

Если этот код некорректный, покажите, какую синтаксическую ошибку выдаёт компилятор ;-). При очевидной реализации Point мой пример кода будет работать. Чтобы он стал неработоспособным, нужно приложить специальные усилия (но тогда реализация Point будет немного странной, не идиоматичной).

Я специально подбирал код, который будет дословно эквивалентен рассмотренному коду на Rust. Тот вариант, который предлагаете Вы, он более идиоматичный (с этим всецело согласен), но не эквивалентный коду на Rust.

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

Да, Вы правы. Код некорректный. Я имел ввиду следующий код:
auto b = std::make_shared<Point>(Point(0.0, 0.0));

✅  2021/01/23 00:34, Автор сайта          #21 

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

О фиктивном типе. Тип данных, упрощенно говоря, — это формат хранения данных; он определяет правила работы с данными. Но данные и типы этих данных — это пассивная сущность. Данные не могут активировать изменение себя или других данных. А побочный эффект — это активное явление.

И вот видится противоречие: один элемент кортежа — значение, полученное чистым способом, а второй — тоже какие-то данные (объект фиктивного типа), пассивные по своей сущности, но непонятно почему вызывающие побочный эффект.

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

Так зависимости по побочному эффекту превращаются в зависимости по данным.

Получается, что если хотим получить побочный эффект, то надо получить объект описанного типа.

В Википедии он назван исследовательским языком

Я принял Ваши слова об «экспериментальном языке», как относящиеся к Rust, а не Cyclone. Недоразумение.

Вызывается конструктор умного указателя. Он выделяет в куче память размером с объект и перемещает значение объекта в кучу.

А как он выделяет память? С помощью malloc() или new? Тогда это ручное управление памятью. Если оно же, только спрятанное под капот, в машинные коды — тогда наверное может называться автоматическим управлением памятью. Впрочем, если ручное выделение/уничтожение памяти существует только внутри конструкторов/деструкторов, то такое управление уже может не считаться ручным.

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

И вот видится противоречие: один элемент кортежа — значение, полученное чистым способом, а второй — тоже какие-то данные (объект фиктивного типа), пассивные по своей сущности, но непонятно почему вызывающие побочный эффект.

Побочный эффект/недетерминизм (то, что делает язык «грязным») в языках программирования имеет две причины:
  • изменяемые переменные и
  • примитивные операции ввода-вывода (в широком смысле, включая любое взаимодействие с ОС и оборудованием).

И если стоит задача обеспечить чистоту языка, нужно побороть обе причины. В чистом языке порядок вычислений ограничен только зависимостью по данным. В композиции f(g(x)) функция g должна быть вычислена раньше f. (Случай ленивых вычислений рассматривать не буду, т.к. он отвлечёт нас от предмета разговора. Но там по сути ничего не меняется.)

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

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

Т.е. каждая «грязная» функция должна принимать некоторый «токен» и «токен» возвращать. Тогда цепочка операций ввода/вывода будет записана как цепочка вызовов функций, где первая получает токен извне, вторая — токен, возвращённый предыдущим вызовом и т.д. Сам этот токен никакой информации внутри себя не несёт (примерный аналог в Си: структура без полей), он нужен только для превращения неявной зависимости по побочному эффекту в явную зависимость по данным.

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

(Автор сайта знает про уникальные типы, я пишу подробно для других читателей нашего обсуждения.)

Уникальный тип — это тип, значение которого нельзя ни копировать, ни терять. Это означает, что если мы присваиваем объект уникального типа другой переменной, то после этого присваивания старой переменной пользоваться уже нельзя — объект перемещён. Если передаём уникальный тип в вызов функции, то точно также, после этой точки обращения к переменной становятся синтаксически неверными. Если функция возвращает значение уникального типа, его обязательно нужно или сохранить в переменную, или передать в другую функцию. Если в теле функции есть «живые» переменные уникальных типов, то их обязательно нужно вернуть return’ом по завершении, иначе тоже будет ошибка.

(Отвлекусь: уникальные типы можно применять для контроля ресурсов. Если выделенный ресурс (открытый файл или сетевое соединение, выделенная память) хранится в объекте уникального типа, то ни утечка, ни двойное освобождение в синтаксически корректной программе будут невозможны. Функция создания ресурса создаёт объект уникального типа, функция освобождения принимает параметром, остальные или принимают, а потом снова возвращают, или заимствуют, как в Rust.)

Очевидно, упомянутые «токены» ввода-вывода должны иметь уникальный тип. Тогда все операции ввода-вывода будут неизбежно связаны в цепочки, а функция main (или её аналог) будет иметь токен в качестве одного из параметров и должна будет его вернуть. Примитивные операции ввода/вывода предоставляются стандартной библиотекой языка, все они в сигнатуре имеют токены, и у программиста нет другой возможности осуществлять ввод-вывод, кроме как связывать эти функции в цепочки.

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

Вызывается конструктор умного указателя. Он выделяет в куче память размером с объект и перемещает значение объекта в кучу.

А как он выделяет память? С помощью malloc() или new? Тогда это ручное управление памятью.

Да, это ручное управление памятью, спрятанное внутри библиотеки.

К слову, некоторые умные указатели (в частности, Box) в Rust это и есть (почти) уникальные типы. Копировать их нельзя, но вот терять можно (поэтому «почти»). Если объект, реализующий типаж Drop, выходит из области видимости, то для него неявно вызывается метод drop (как деструктор в C++). У умного указателя Box метод drop освобождает память.

✅  2021/01/25 11:10, Автор сайта          #23 

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

Любопытно заметить, что в языке D внутри чистых функций (они помечены ключевым словом «pure») запрета на изменение значений переменных нет. И циклы разрешены внутри чистых функций D. То есть изменяемость переменных не является препятствием к чистоте функций. Александреску, один из авторов языка, так и пишет: «Чист тот, кто чисто поступает». В этом есть определённая логика: если функция играет роль герметичного чёрного ящика, то наличие или отсутствие внутренних состояний — это личное дело самой функции. Всё равно эти локальные состояния не имеют возможности стать глобальными. Получается, что отсутствие побочных эффектов и недетерминированности вполне достаточно для чистоты функций языка D.

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

Цитата из статьи «Типы, гарантирующие уникальность»:

Если x имеет гарантированную уникальность, то при вычислении
x' = f(x)
компилятор гарантирует, что на х больше нигде нет ссылок. Значит в этом месте х использован последний раз, занимаемую им память можно после вычисления f(x) освободить. Если x' и x имеют один тип и размер, то вместо объявления х мусором и выделения памяти для x' можно разместить x' там, где ранее был x. Таким образом получается изменение по месту без нарушения чистоты.

Мне видится, что гарантия отсутствия внешних ссылок тоже гарантирует уникальность, поскольку внутренние ссылки умрут по окончании функции. Главное, чтобы функция гарантировала герметичность — возможно через объявление её определённым ключевым словом, а не через систему типов.

цепочка операций ввода/вывода будет записана как цепочка вызовов функций, где первая получает токен извне, вторая — токен, возвращённый предыдущим вызовом и т. д.

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

Понятно, таким образом мы выстраиваем императивную цепочку вызовов «f(g(x))» в строгой очерёдности: «y=g(x); f(y)». И помогает в этом эстафетная палочка, которая передаётся от одного к другому. Ведь для функций «f» и «g» с побочными эффектами важен порядок оказания этого эффекта. Но факт того, что последовательность побочных эффектов правильная, не привносит чистоту в функцию, внутри которой есть «f(g(x))». Она тоже заражается «нечистотой» «f» и «g».

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

К слову, некоторые умные указатели (в частности, Box) в Rust это и есть (почти) уникальные типы. Копировать их нельзя, но вот терять можно (поэтому «почти»). Если объект, реализующий типаж Drop, выходит из области видимости, то для него неявно вызывается метод drop (как деструктор в C++).

Да, это интересный вопрос. То ли main должна вернуть эстафетную палочку, то ли её можно потерять по дороге. Первое, вероятно, гарантирует отсутствие конкурирующего ввода/вывода. С другой стороны, как быть при выходе из области видимости?

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

И помогает в этом эстафетная палочка, которая передаётся от одного к другому.

Эстафетная палочка! Очень точная и красивая метафора. Я до неё не додумался, спасибо!

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

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

Но факт того, что последовательность побочных эффектов правильная, не привносит чистоту в функцию, внутри которой есть «f(g(x))». Она тоже заражается «нечистотой» «f» и «g».

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

Функция, заражённая «нечистотой», видна по своему типу: в аргументах и результате есть эстафетная палочка.

Да, это интересный вопрос. То ли main должна вернуть эстафетную палочку, то ли её можно потерять по дороге. Первое, вероятно, гарантирует отсутствие конкурирующего ввода/вывода. С другой стороны, как быть при выходе из области видимости?

Эстафетная палочка ввода-вывода используется в языках, где ввод-вывод сделан через уникальные типы. Там она не может потеряться по дороге — компилятор не даст.

В языке Rust значения могут теряться по дороге, и если тип реализует типаж Drop, то при потере автоматически вызовется метод drop() (аналог деструктора в C++). Если тип сам не реализует типаж Drop, но содержит объекты типов, его реализующие (например, это структура, некоторые из полей которых являются векторами или умными указателями), то drop’ы вызовутся только для соответствующих полей.

А в остальном действительно, к значениям в Rust применима метафора эстафетной палочки. Исключение: если тип реализует типаж Copy, то при присваивании он неявно копируется. Как написано в статье, типаж Copy реализован для простых типов данных (числа, ссылки) и кортежей этих типов данных.

✅  2021/02/11 23:35, Автор сайта          #25 

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

Выходит, что более сложным ограничением является то, что внутри чистой функции (в языке D — с ключевым словом pure) необходимо употреблять только такие же чистые функции. То есть и вызывающая, и вызываемая функции не могут делать запись по указателю.

Но у чистых функций есть «узкое горлышко». Они должны отдать наружу только возвращаемый результат. Или в регистре (по традиции — в регистре-аккумуляторе типа EAX), или записью в кортеж/контейнер/структуру в ОП. Последний вариант не столь выгоден с точки зрения процессора. Интересно, есть ли компиляторы, возвращающие результат в нескольких регистрах, а не через ОП?

Ну ладно, допустим наши функции умеют возвращать кортеж/контейнер/структуру, а операция присвоения может иметь несколько операндов слева:
a, b, c = fn (x, y, z);		// x, y, z доступны только для чтения
Тогда у нас вообще отпадает необходимость что-то записывать по указателю! Всё делается через присвоение, которое получило право быть деструктивным.

Про эстафетную палочку. Коль она — фиктивный параметр, то и является «бестелесной», существует только во время компиляции. При исполнении она уже не нужна, поскольку вычисления уже выстроены в цепочку. Тем не менее, «нечистая» функция должна вроде как вернуть кортеж. Как-то противоречиво…

С другой стороны, в императивных языках выражения выстраиваются в чепочку через точку с запятой:
<выражение 1>; <выражение 2>;
Точка с запятой обеспечивает, что за выражением 1 следует выражение 2. То есть это тоже эстафетная палочка. В однопоточном коде гарантированно одно следует за другим. Осталось только определиться со способом, каким образом обеспечить гарантию однопоточности и вытекающую из неё автоматическую эстафету. И, как видится, к этому не обязательно привлекать типизацию аргументов и результата. Можно ввести язык помимо ключевого слова «функция» ключевое слово «однопоточная функция». Правда, это решить часть проблем, но не все. За бортом останутся многопоточные. Можно, конечно, многопоточность рассматривать как набор однопоточных функций. Но вопросы всё равно останутся.

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

Похоже, ради таких преобразований всё и делается.

Вот только тут возникает, как говорится, когнитивный диссонанс, связанный с противоречивостью утверждений о чистоте функций, языка, побочных эффектах и недерминированности. С одной стороны, утверждается, что те же Haskell и Clean — чистые языки программирования. Но почему же они допускают побочные эффекты? Как можно утверждать о чистоте функций, производящих побочный эффект, даже если они обёрнуты монадой IO? Цитирую Википедию:

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

Я вижу в монадах механизм изоляции функций разных типов друг от друга. Но монада IO не превращает функцию в чистую. Её по-прежнему нельзя сделать ленивой, распараллелить или выполнить в произвольном порядке. То есть замечательные свойства чистых функций им по-прежнему недоступны.

отсутствия изменяемых переменных

К слову, о терминологии. К сожалению, нет адекватного термина, соответствующего «неизменяемой переменной». Ибо слово «переменная» само собой подразумевает изменяемость. А слово «константа» не всегда соответствует объекту в программе, который неизменяем. Английское «value» подразумевает, что оно может быть как изменяемым, так и неизменяемым. А чем заменить его в русском? В этой статье, которую мы обсуждаем, заменял «value» словом «значение» и получил замечание за некачественный перевод. В английской Википедии есть статья «value», а в русской ей соответствует статья «значение», но эта — замена не ахти…

уникальные типы используются

И опять о терминологии. Когда переводил статью английской Википедии «Uniqueness type», то не понравились размытость и нечёткость формулировки, буквального перевода «уникальный тип». Взять, к примеру, тип int. Он уникальный и неповторимый, он просто однажды «зашит» в язык и его больше нельзя переопределить. А вот объекты уникального типа int могут быть не уникальны. Говоря же «уникальный тип», имеют в виду несколько иное. Уникальный не сам тип, а объекты этого типа. Он обеспечивает не собственную уникальность, а уникальность объектов своего типа. Вот поэтому при переводе статьи я посоветовался на форуме, приводил такие аргументы:

Разница между «уникальными типами» и «типами уникальности» вполне ощущается, её можно почувствовать:

неисправный индикатор — индикатор неисправности
правильный критерий — критерий правильности
надёжный признак — признак надёжности
уникальное объявление — объявление уникальности

После этого и родился такой перевод: «тип, гарантирующий уникальность».

✅  2021/02/12 12:24, Александр Коновалов aka Маздайщик          #26 

При исполнении она уже не нужна, поскольку вычисления уже выстроены в цепочку. Тем не менее, „нечистая“ функция должна вроде как вернуть кортеж. Как-то противоречиво…

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

Вот только тут возникает, как говорится, когнитивный диссонанс, связанный с противоречивостью утверждений о чистоте функций, языка, побочных эффектах и недерминированности. С одной стороны, утверждается, что те же Haskell и Clean — чистые языки программирования. Но почему же они допускают побочные эффекты? Как можно утверждать о чистоте функций, производящих побочный эффект, даже если они обёрнуты монадой IO?

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

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

А монады и типы, гарантирующие уникальность, — это средства моделирования ввода-вывода в языке с чистой семантикой. Библиотека не входит в ядро языка.

А вообще монада IO на самом деле чистая. Только это сложно объяснить человеку, не знающему Хаскель. Рассмотрим такую упрощённую модель: у нас есть две операции ввода-вывода: чтение одного Char’а и запись одного Char’а. Монада IO позволяет построить объект типа IOTerm, который представляет собой размеченное объединение трёх значений:
  • пара из Char’а и IOTerm’а,
  • функция, принимающая Char и возвращающая IOTerm,
  • признак остановки вычислений, без полей.
Программа на Хаскеле вычисляет этот IOTerm. Отдельно от программы на Хаскеле есть интерпретатор IOTerm’а. Когда интерпретатор видит первый член объединения, он печатает этот Char и в цикле интерпретирует второй компонент пары. Когда он видит второй член объединения, он считывает Char и вызывает с ним функцию. Функция возвращает новый IOTerm, который интерпретируется снова. Когда видит третий член — завершает свою работу.

Этот подход обобщается на вызов любых других нечистых функций.

Интерпретатор IOTerm’а грязный. Программа, его вычисляющая — чистая. У меня где-то был исходник на Хаскеле, который демонстрирует реализацию монады IO, формирующей этот IOTerm.

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

f :: A -> B -> IO()
f a b = do putStrLn (g a)
putStrLn (h b)
Функция f чистая. Вызовы g a и h b могут выполняться лениво, параллельно и в произвольном порядке.

Пример на типы, гарантирующие уникальность (псевдокод):
IO f(IO a) {
x, a1 = get_string(a)
y, a2 = get_string(a1)
a3 = put_string(compile(x), a2)
a4 = put_string(calculate(y), a3)
return a4
}
Вызовы compile и calculate по данным друг от друга не зависят, поэтому могут вычисляться параллельно или в произвольном порядке. Лениво, в общем-то тоже могут, только их вычисления тогда будут форсированы внутри put_string.

Спасибо за пояснения по терминологии.

✅  2021/02/15 23:19, Автор сайта          #27 

f :: A -> B -> IO()
f a b = do putStrLn (g a)
putStrLn (h b)

Функция f чистая. Вызовы g a и h b могут выполняться лениво, параллельно и в произвольном порядке.

Не ясно, откуда взялись g и h, они не передавались в функцию в качестве аргументов. Хотя, возможно, это вызовы функций. Но согласимся, что с вызовами g, a и h, b так и обстоит. Но чисты ли putStrLn? По-видимому нет, иначе как объяснить появление do, которая обеспечивает последовательное выполнение putStrLn, первой и второй? Ведь putStrLn должны выполняться не в произвольном, а в строгом порядке, а это один из признаков отсутствия чистоты. Да и сама функция f не может быть применена без do, только внутри этого блока.

Возьмём пример книги «О Haskell по-человечески» Дениса Шевченко (стр.115):
obtain_user_text :: String -> IO String
obtain_user_text prompt = do
putStrLn prompt -- Выведи приглашение ввести строку
getLine -- Получи от пользователя некую строку
main :: IO ()
main = do
first_text <- obtain_user_text "Enter your text, please: "
second_text <- obtain_user_text "One more, please: "
putStrLn $ "You said '" ++ first_text ++ "' and '" ++ second_text ++ "'"
Можно ли считать чистой функцию obtain_user_text несмотря на строгое выполнение putStrLn и getLine внутри do? Можно ли считать чистой функцию main, несмотря на строгое выполнение obtain_user_text и putStrLn внутри do? Вот в чём вопрос.

это сложно объяснить человеку, не знающему Хаскель

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

Отдельно от программы на Хаскеле есть интерпретатор IOTerm’а… Интерпретатор IOTerm’а грязный

Я так и знал, что в раю есть провайдеры услуг ада! Агнцы отделены от козлищ, но между ними — незадокументированный интерфейс взаимодействия. Раздумывая, как устроены эти неочевидные вещи, сделал предположение, что монадические IO-функции возвращают, помимо результата, указатель на функцию ввода-вывода. Таким образом сохраняя чистоту, но поручая нечистые деяния тёмному миру. Но как происходит это взаимодействие — сам пока не додумался, а где почитать чужие мысли — не нашёл.

У меня где-то был исходник на Хаскеле, который демонстрирует реализацию монады IO, формирующей этот IOTerm

Если Вас не затруднит, поделитесь. Было бы здорово найти где-то переложение этой системы на Си. Не сам ввод/вывод (в нём то секрета нет), а взаимодействие чистоты и нечистоты.

Спасибо за Ваши ответы. Надо будет ещё осмыслить, поискать информацию.

✅  2021/02/16 19:47, Александр Коновалов aka Маздайщик          #28 

Не ясно, откуда взялись g и h, они не передавались в функцию в качестве аргументов. Хотя, возможно, это вызовы функций.

Я имел ввиду, что это вызовы каких-то функций.

Но чисты ли putStrLn?

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

По-видимому нет, иначе как объяснить появление do, которая обеспечивает последовательное выполнение putStrLn, первой и второй?

Ключевое слово do ничего не обеспечивает. Это синтаксический сахар для вызова методов класса Monad.

Выражение
do x <- f1
f2
эквивалентно
f1 >>= (\x -> f2)
Выражение
do f1
f2
эквивалентно
f1 >>= (\_ -> f2)
Для примера раскрою синтаксический сахар в примере кода, который Вы процитировали выше. Исходный текст (добавил отступы для читаемости):
obtain_user_text :: String -> IO String
obtain_user_text prompt = do
putStrLn prompt -- Выведи приглашение ввести строку
getLine -- Получи от пользователя некую строку

main :: IO ()
main = do
first_text <- obtain_user_text "Enter your text, please: "
second_text <- obtain_user_text "One more, please: "
putStrLn $ "You said '" ++ first_text ++ "' and '" ++ second_text ++ "'"
Убрал комментарии и раскрыл синтаксический сахар:
obtain_user_text :: String -> IO String
obtain_user_text prompt = putStrLn prompt >>= (\_ -> getLine)

main :: IO ()
main = obtain_user_text "Enter your text, please: "
>>= (\first_text -> obtain_user_text "One more, please: "
>>= (\second_text -> putStrLn $ "You said '" ++ first_text ++ "' and '" ++ second_text ++ "'"))

IO-функции возвращают, помимо результата, указатель на функцию ввода-вывода.

В некотором смысле это верно.

Маздайщик: У меня где-то был исходник на Хаскеле, который демонстрирует реализацию монады IO, формирующей этот IOTerm

Автор сайта: Если Вас не затруднит, поделитесь.

Этот текст возник, когда я объяснял студентам устройство монады IO. Начинал с простого, а потом развивал, пока не получится полноценная монада.
data IOTerm = PutChar Char IOTerm
| GetChar (Char->IOTerm)
| Exit

newtype MyIO x = MyIO { runMyIO :: ((x -> IOTerm) -> IOTerm) }

instance Monad MyIO where
m >>= f = MyIO $ \k -> (runMyIO m) (\x -> runMyIO (f x) k)
return x = MyIO $ \k -> k x

instance Functor MyIO where
fmap = undefined

instance Applicative MyIO where
pure = undefined
(<*>) = undefined


myMain :: MyIO ()
myMain = do
xs <- myGetStr
myPutStr ("Hello, " ++ xs ++ "!")


myPutChar :: Char -> MyIO ()
myPutChar ch = MyIO $ \k -> PutChar ch (k ())

myPutStr :: [Char] -> MyIO ()
myPutStr (x:xs) = do { myPutChar x; myPutStr xs }
myPutStr [] = myPutChar '\n'

myGetChar :: MyIO Char
myGetChar = MyIO GetChar

myGetStr :: MyIO [Char]
myGetStr = myGetChar >>= read []
where read res '\n' = return res
read res ch = myGetChar >>= read (res ++ [ch])



runIOTerm :: IOTerm -> IO ()

runIOTerm (PutChar ch cont) = do
putChar ch
runIOTerm cont

runIOTerm (GetChar fn) = do
c <- getChar
runIOTerm (fn c)

runIOTerm Exit = return ()


main = do
runIOTerm (runMyIO myMain $ \_ -> Exit)
В примере выше функция myMain чистая, хотя в ней есть do, myGetStr и myPutStr, которые осуществляют «ввод» и «вывод».

«Грязным» является интерпретатор runIOTerm, который, используя уже встроенную монаду IO, осуществляет чтение с консоли и запись на консоль. Но впрочем, он не грязнее функций myGetStr и myPutStr, поскольку в Хаскеле все функции чистые (ну, кроме unsafePerformIO и каких-то других, наверное).

Если интересно, могу подробно объяснить каждую функции в листинге выше.

Было бы здорово найти где-то переложение этой системы на Си.

Не очень понял. Можно считать, что в примере выше функции runIOTerm и main являются частью интерпретатора Хаскеля и написаны на Си, а на Хаскеле пишется только myMain. И тогда на Хаскеле весь код будет чистым.

Про типы, гарантирующие уникальность, вопросов нет?

✅  2021/02/16 20:16, Александр Коновалов aka Маздайщик          #29 

Маздайщик: это сложно объяснить человеку, не знающему Хаскель

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

Прошу прощения, пропустил эту реплику при ответе на вопрос.

Прекрасно Вас понимаю! Сам когда-то не понимал, как на самом деле реализована монада IO и почему она чистая. И поэтому у меня тоже был некоторый затык с пониманием монад: в чём же фокус в монаде IO? Но нашёл статью, которая фокус частично раскрывает. Прочитал её (больше примеры кода, чем сам текст), идея стала очевидна, даже для полноты понимания написал монаду IO на Рефале. Т.е. можно красиво изобразить чистую монаду IO, которая описывает порядок вычислений. Код из предыдущего комментариях вдохновлён этой статьёй Люка Палмера. Могу пример кода подробно объяснить, но это уже будет целая статья. Может, это лучше разместить отдельной статьёй?

Когда готовил этот комментарий, нашёл другой материал. Здесь написано, как реализована IO в компиляторе GHC. Реализована она иначе. Не так элегантно, как по ссылке выше, но в некоторой красоте ей не откажешь. Хотя есть и что-то от грязного хака.

✅  2021/02/19 23:07, Автор сайта          #30 

Если интересно, могу подробно объяснить каждую функции в листинге выше.

Не просто интересно, а очень интересно!

«Грязным» является интерпретатор runIOTerm

И вправду интерпретатор — в противоположность компилятору?

И всё-таки хочется переложить вашу реализацию монады IO с Haskell на Си. Во-первых, самому привычнее. А во-вторых, Си — это латынь или эсперанто, поэтому для многих читателей это упростит чтение. А пока что разбираюсь с Вашим кодом.

С каррированием я, к примеру, разобрался самостоятельно. Изучил технику каррирования применительно к Си. Выявил его недостатки. Хотя преимущества для меня не столь очевидны. Может, и с монадой IO получится разобраться. Тогда можно и за монаду State взяться.

Про типы, гарантирующие уникальность, вопросов нет?

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

А вот что пишет Миран Липовача, стр. 208:

язык Haskell чётко разделяет чистую и «грязную» части кода. Функция getLine — не чистая функция, потому что её результат может быть неодинаковым при последовательных вызовах

Читая «О Haskell по-человечески», не видел утверждения, что в Haskell — исключительно чистые функции. Более того, на стр. 115 пишется:

Мы можем использовать do-нотацию в любой функции с побочными эффектами.

Любая функция — имеется в виду функции в Haskell. И эти функции в Haskell — с побочными эффектами! Даже авторы книг противоречат друг другу. А Липовача сам себе в рамках одной книги! А ещё авторы книг о других языках высказывались о Haskell негативно.

Спасибо за ссылки, будет чем заняться :)

✅  2021/02/21 13:05, Александр Коновалов aka Маздайщик          #31 

Не просто интересно, а очень интересно!

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

И вправду интерпретатор — в противоположность компилятору?

Интерпретатор — это часть рантайма языка. В модели, которую я описал в комментарии #28, чистая программа на Хаскеле, вычисляющая IOTerm, взаимодействует с интерпретатором этого IOTerm’а, который и осуществляет побочный эффект.

И всё-таки хочется переложить вашу реализацию монады IO с Haskell на Си. Во-первых, самому привычнее. А во-вторых, Си — это латынь или эсперанто, поэтому для многих читателей это упростит чтение. А пока что разбираюсь с Вашим кодом.

С каррированием я, к примеру, разобрался самостоятельно. Изучил технику каррирования применительно к Си. Выявил его недостатки. Хотя преимущества для меня не столь очевидны. Может, и с монадой IO получится разобраться. Тогда можно и за монаду State взяться.

Монада State даже проще монады IO и в ней существенно используется каррирование.

А что Вы читали про каррирование применительно к Си?

Модель, описанная в комментарии #28, существенно использует функции высшего порядка: возврат безымянных функций, захватывающих контекст, каррирование, получение функции в качестве аргумента. Всех этих понятий в языке Си просто нет. Я не знаю, как такое наглядно перевести на Си. Это даже сложнее, чем переводить на Си паттерны объектно-ориентированного программирования.

(Офтопик. ООП на Си возможно, но для этого придётся вручную моделировать то, что делает компилятор ОО-языков. В частности, нужно будет объявлять структуры, содержащие указатели на функции — это будут таблицы виртуальных функций. Объявлять структуры, первым полем которых будет указатель на виртуальную таблицу — это будут объекты. Вызов виртуальной функции будет выглядеть как (obj.vtable->func)(&obj, param1, param2) вместо obj.func(param1, param2). При объяснении монад Хаскеля на Си придётся точно также изобретать функции высших порядков (их вызов, лямбды, каррирование) и параметрический полиморфизм поверх void*.)

Как эсперанто в статьях часто используют нотацию языка ML. Язык ML немного более читабелен, чем язык Haskell.

Могу переписать пример с монадами на Python или JavaScript — в них есть поддержка функций высшего порядка.

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

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

В рамках данного определения языки Clean и Haskell чистые, не смотря на возможность писать на них программы с побочными эффектами. Функции с побочными эффектами оформлены в них таким образом, чтобы зависимость по побочному эффекту выражалась искусственным образом через зависимость по данным. В случае языка Clean функции передают уникальную эстафетную палочку, в случае Хаскеля используется концепция монад.

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

✅  2021/02/24 11:12, Автор сайта          #32 

Думаю, стоит написать статью для Вашего сайта.

Да, это хорошая идея.

Интерпретатор — это часть рантайма языка. В модели, которую я описал в комментарии #28, чистая программа на Хаскеле, вычисляющая IOTerm, взаимодействует с интерпретатором этого IOTerm’а, который и осуществляет побочный эффект.

Интерпретатор читает, анализирует и выполняет программу построчно. Или компилирует в байт-код, который потом выполняется. Именно так работает интерпретатор IOTerm’а?

Монада State даже проще монады IO и в ней существенно используется каррирование.

Да, конечно проще. Просто она другая, тем и интересна.

А что Вы читали про каррирование применительно к Си?

Модель, описанная в комментарии #28, существенно использует функции высшего порядка: возврат безымянных функций, захватывающих контекст, каррирование, получение функции в качестве аргумента. Всех этих понятий в языке Си просто нет. Я не знаю, как такое наглядно перевести на Си. Это даже сложнее, чем переводить на Си паттерны объектно-ориентированного программирования.

Ничего не читал. Просто вооружился фактами и логикой и написал небольшой эскиз:
#include <stdio.h>  
int global_var;
typedef void (*f_1)(int);
typedef f_1 (*f_2)(int);
typedef f_2 (*f_3)(int);
typedef f_3 (*f_4)(int);
typedef f_4 (*f_5)(int);
// ---------------------------------------------------------------------------
int f5 (int a1, int a2, int a3, int a4, int a5) {
printf ("function f5 (%i, %i, %i, %i, %i) returns ", a1, a2, a3, a4, a5);
int ret = a1*10000 + a2*1000 + a3*100 + a4*10 + a5;
printf("%i\n", ret); return ret;
}
// ---------------------------------------------------------------------------
void F1 (int a) {
global_var += a*10000; printf (" (%i) returns %i", a, global_var);
}
f_1 F2 (int a) {
global_var += a*1000; printf (" (%i)", a); return F1;
}
f_2 F3 (int a) {
global_var += a*100; printf (" (%i)", a); return F2;
}
f_3 F4 (int a) {
global_var += a*10; printf (" (%i)", a); return F3;
}
f_4 F5 (int a) {
global_var = a; printf ("F5 (%i)", a); return F4;
}
// ---------------------------------------------------------------------------
main() {
f5 (5, 4, 3, 2, 1);
F5 (1) (2) (3) (4) (5);
}
На консоль выдаётся:
function f5 (5, 4, 3, 2, 1) returns 54321
F5 (1) (2) (3) (4) (5) returns 54321
Посмотрел, какой код генерируется на выходе. Мне было интересно, насколько падает эффективность кода от каррирования, когда вызов одной функции с пятью аргументами заменён пятью вызовами функций с одним аргументом. С точки зрения математики это эквивалентно, с точки зрения эффективности кода — нет.

Много лет назад спорил со своим коллегой: «Знаешь, в языке XYZ есть такая фишка, а в ассемблере её нет». На это он возражал: «Раз программа на XYZ транслируется в машинный код, то это можно написать на ассемблере. Нет ничего, чего нельзя написать на ассемблере». По своему он прав. Только вместо ассемблера почти всегда можно использовать Си.

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

на Си возможно, но для этого придётся вручную моделировать… При объяснении монад Хаскеля на Си придётся точно также изобретать функции высших порядков (их вызов, лямбды, каррирование) и параметрический полиморфизм поверх void*

Мне кажется, трудности преодолимы.

Как эсперанто в статьях часто используют нотацию языка ML

Может, в академических кругах так и обстоит. Но среди практикующих программистов синтаксису Си-подобных языков нет равных. Взять, к примеру, свежий рейтинг TIOBE: в первой десятке — шесть Си-подобных языков. Си во многих вузах — первый язык.

Но самую большую прозрачность обеспечит ассемблерный код :) Недаром Дональд Кнут комментировал теорию в своих трудах псевдоассемблером.

Могу переписать пример с монадами на Python или JavaScript — в них есть поддержка функций высшего порядка.

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

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

Мне кажется, такая формулировка отдаляет от понимания сути. Хотя, конечно, я субъективен. Я всё ещё не развеял туман вокруг функции main, определённой как
main :: String -> IO ()
Ведь если она чистая, то значит она ленивая. Как она вдруг заработает, если она ленивая?

А пока разбираюсь с Вашей реализацией монады IO.

✅  2021/02/27 20:36, Александр Коновалов aka Маздайщик          #33 

Интерпретатор читает, анализирует и выполняет программу построчно. Или компилирует в байт-код, который потом выполняется. Именно так работает интерпретатор IOTerm’а?

Интерпретатор может быть частью большей программы: принимать на входе синтаксическое дерево и вычислять его. Более того, это синтаксическое дерево может динамически генерироваться в процессе работы. На интерпретатор IOTerm’а нужно смотреть в этом ключе.

Если интерпретатор видит, что значением является PutChar ch term, то он запишет ch на stdout и продолжит интерпретировать терм term. Если он увидит GetChar func, то он прочитает символ ch с stdin, вызовет func ch, вызов вернёт новый терм — интерпретатор приступит к интерпретации его. Если увидит Exit, закончит интерпретацию.

Псевдокодом смеси Хаскеля и Си интерпретатор можно изобразить так (присваивание обозначено := для большей наглядности):
term := main(λx.Exit); /* колдунство */

while (term != Exit) {
switch (term) {
case PutChar(ch, term′):
putc(ch, stdout);
term := term′;
continue;

case GetChar(func):
ch := getc(stdin);
term := func(ch); /* вызов чистой функции */
continue;
}
}
Колдунство я пока пояснять не буду, для этого нужно писать целую статью, которую я сейчас писать не готов. Отмечу лишь, что вызов main, помеченный как «колдунство» и вызов func(ch) — чистые. Весь «грязный» код сосредоточен в цикле.

С вопросом «как» применительно к каррированию можно считать разобрался.

На мой взгляд, Вы разобрались отчасти. Каррирование формирует новую функцию, которую можно положить в переменную, а затем вызывать. Связав первый аргумент с разными значениями, можно получить несколько разных функций, которые потом можно вызывать независимо (псевдокод):
func mult(a, b) {
return a * b;
}

twice := mult(2);
triple := mult(3);
print(twice(10)); // 20
print(triple(100)); // 300
print(twice(7)); // 14
print(triple(6)); // 18
Рассмотренный Вами код такого фокуса не допускает по очевидным причинам. А ведь за это каррирование и любят.

Мне кажется, трудности преодолимы.

Трудности преодолимы, но существенно снижается наглядность изложения.

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

Проблема в том, что функций (и, соответственно, указателей на них) в программе конечное количество. А в функциональных языках можно порождать бесконечное количество функций:
twice := mult(2);
triple := mult(3);
ten_times := mult(10);
...
На Си для этого придётся написать структуру, содержащую указатель на функцию + указатель на некоторый контекст (скорее всего, void *). И вызывать с явной передачей контекста. Но такое представление начисто скроет основную идею.

Я всё ещё не развеял туман вокруг функции main, определённой как…

Ведь если она чистая, то значит она ленивая. Как она вдруг заработает, если она ленивая?

Возвращаемся к интерпретатору:
term := main(λx.Exit); /* колдунство */

while (true) {
switch (term) {
case PutChar(ch, term′):
putc(ch, stdout);
term := term′;
continue;

case GetChar(func):
ch := getc(stdin);
term := func(ch); /* вызов чистой функции */
continue;

case Exit:
exit();
}
}
Для наглядности дальнейшего изложения я немного изменил программу.

Переменная term хранит ленивое значение — оно всегда вычисляется ровно на столько, на сколько его просят. В примере терм вычисляется до тех пор, пока не обретёт форму вида Exit, PutChar(c, t) или GetChar(f), т.е. до т.н. слабой головной нормальной формы (далее, СГНФ). И вычисляется оно в операторе switch, когда сопоставляется с образцами.

Допустим, он вычислился в PutChar(c, t) и сопоставился в первой ветке case. Значения переменных ch и term′ тоже будут ленивыми. Переменная ch полностью вычислится во время вызова putc(ch, stdout), переменная term′ будет вычислена до СГНФ на следующем витке цикла, когда будет сопоставляться с образцами в switch.

Значение func в GetChar(func) тоже будет ленивым, вызов func(ch) ничего не вычислит, т.к. лень. Ленивый результат будет присвоен переменной term, и уже вычислится до СГНФ на следующем витке цикла.

✅  2021/03/02 00:31, Автор сайта          #34 

На мой взгляд, Вы разобрались отчасти.

Я вдохновлялся примером из Википедии (свежая версия статьи о каррировании уже не содержит примеров, но старых версиях можно найти):
class curry {
private:
int m_x;
public:
curry(int x): m_x(x) {}
int operator() (int y) { return m_x + y; }
};
int a = curry(4)(5); // 9
Согласен, что мой пример не предусматривает частичного применения, но по факту один вызов функции от нескольких аргументов заменён несколькими вызовами функций от одного аргумента. Что является каррированием, хоть и не с такими возможностями, как в Haskell. Просто хотел увидеть машинный код и убедиться, что эквивалентные с точки зрения математики преобразования не приводят эквивалентным преобразованиям в машинном коде. Напротив, каррирование удлиняет код программы и замедляет его.

Связав первый аргумент с разными значениями...

twice := mult(2);
triple := mult(3);
А каков тип twice и triple? Чему равен результат связывания? Вероятно, следующий текст всё объясняет?

На Си для этого придётся написать структуру, содержащую указатель на функцию + указатель на некоторый контекст (скорее всего, void *). И вызывать с явной передачей контекста. Но такое представление начисто скроет основную идею.

Это кому как. Мне бы наоборот открыло. С другой стороны, есть отличная альтернатива. Ещё в школе учили: «Если что-то кажется сложным, попробуй схематично нарисовать условие задачи». Иногда графическое представление объясняет лучше, чем текст. Дональд Кнут, один из классиков программирования, охотно прибегал к такому приёму. Даже как-то посчитал, что «схема данных» встречается в его трудах на порядок чаще, чем «схема программы», то есть блок-схема. Если Вы решите прокомментировать свои мысли каким-нибудь рисунком — присылайте любой, хоть от руки рисунок — я его «подрихтую».

Кстати, в моей коллекции книг по Haskell я что-то не помню ни одной иллюстрации к объясняемому материалу. Но ведь есть иллюстрировать! А откроешь Кнута — вот тебе рисунки с деревьями, графами, списками.

Переменная term хранит ленивое значение — оно всегда вычисляется ровно на столько, на сколько его просят.

Вероятно, это надо понимать так: «Переменная term содержит указатель на ленивую функцию, которая выдаст значение, если её вызовут». Это чтобы не запутаться, где данные, а где указатели на функции.

✅  2021/03/02 12:49, MihalNik          #35 

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

Это неверно и зависит от того, как именно сделано в языке, в каком алгоритме и на каких данных. Кастрирование функции — это сужение. Если перенести это в простые языки, то можно выполнить больше вычислений до запуска программы. Например, обычный параметр по умолчанию в Сях — это частный случай. Если есть вычисления над нам вроде квадрата, то, очевидно, можно сделать отдельную реализацию, которая выполняется быстрее на 1 операцию. Или можно сократить лишнюю передачу параметров, сделав отдельную специализацию одним вызовом.
С другой стороны, можно в динамике автоматически собрать статистику обращений к функции и выполнить оптимизацию, например, запоминать и брать готовые значения или генерировать оптимизированный код под конкретную специализацию. Именно этого в Сях нет, т.е. придется реализовывать.

Специализация функций во время компиляции — это шаблоны С++.

✅  2021/03/02 17:56, Автор сайта          #36 

Ну в Си много чего нет. С другой стороны, Си имеет очень эффективную реализацию — в отличие от языков, в которых «много чего есть». Да, частичное применение можно имитировать шаблонными функциями. А вот как имитировать чистоту функций с побочными эффектами — это вопрос.

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

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

Авторизация

Регистрация

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

Карта сайта


Содержание

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

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

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

Компилятор

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

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

●  О превращении кибернетики в шаманство

●  Про лебедей, раков и щук

●  О замысле и воплощении

●  О русском ассемблере

●  Арифметика синтаксиса-3

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

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

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

●  Суть побочных эффектов в чисто функциональных языках

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

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

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

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

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

●●  Джоэл Спольски о функциональном программировании

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

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

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

●  Десятка худших фич C#

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

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

●  ЕС ЭВМ — это измена, трусость и обман?

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

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

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

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

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

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

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

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

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

●●  Опыт самостоятельного развития средства программирования в РКК «Энергия»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

●●  К вопросу о парадигмах

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

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

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

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

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

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

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

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




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

2024/12/07 20:54 ••• Клихальт
Переключатель

2024/12/06 18:44 ••• Анкнав
Русский язык и программирование

2024/12/01 00:00 ••• alextretyak
Продолжение цикла и выход из него

2024/11/29 23:08 ••• Вежливый Лис
О русском ассемблере

2024/11/26 23:53 ••• Бурановский дедушка
ЕС ЭВМ — это измена, трусость и обман?

2024/11/25 18:31 ••• Деньги на WWWетер
Ресурсы, посвящённые созданию языков программирования и компиляторов

2024/11/12 20:24 ••• Вежливый Лис
Правила языка: строки, комментарии

2024/11/12 13:10 ••• Вежливый Лис
Новости и прочее

2024/11/12 00:32 ••• Автор сайта
Оценка надёжности функции с несколькими реализациями

2024/11/06 02:50 ••• Иван
Энтузиасты-разработчики компиляторов и их проекты

2024/11/05 23:51 ••• Борис К.
Изменение приоритетов операций

2024/11/05 23:38 ••• Борис К.
Шестнадцатиричные и двоичные константы

2024/11/01 12:11 ••• ИванАс
Русской операционной системой должна стать ReactOS