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


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


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


А как бы хотелось отдать эти проблемы на откуп компилятору! Чтобы компьютер сам автоматически проверял корректность доступа по ссылкам, в том числе и из разных потоков и чтобы все это делалось во время компиляции приложения без накладных расходов в рантайме!


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


Неявные ссылки


Модель передачи аргументов Python не является ни «передачей по значению», ни «передачей по ссылке», а описывается скорее как «передача по ссылке на объект». И в зависимости от типа объекта, который передается в функцию, переменные-аргументы ведут себя по разному.


Поэтому принято считать, что неизменяемые объекты в Python в качестве аргументов передаются по значению, тогда как изменяемые объекты (списки (list), множества (set) и словари (dict)), всегда передаются по ссылке.


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


А вот в С++ есть и указатели (pointer) и ссылки (reference), причем ссылки можно считать синтаксическим сахаром над указателями, которые упрощают чтение и написание кода. К сожалению, одновременно с этим они так же добавляют и путаницы, т.к. при изменении ссылочной переменной в реальности происходит обращение к объекту, на который эта ссылка указывает, но визуально в тексте программы ссылочная переменная ничем не отличаются от остальных переменных "по значению", ведь для работы с ними не требуется выполнять разименовывание указателя.


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


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


Конкурентный доступ


Еще одна проблема проявляется только во время многопоточного и/или асинхронного выполнения кода. Когда к одной и той же области данных может быть получен доступ из разных потоков приложения. И что в купе с неявным обращением по ссылкам еще больше усугубляет ситуацию. Причем, проблема конкурентного доступа проявляется, в том числе и при работе с обычными ссылками. И хотя разименовывать указатель для доступа к данным необходимо выполнять явным образом, проблему с конкуретным доступом по ссылке из разных потоков все равно приходится решать программисту самостоятельно.


Формализация концепции переменных


Чтобы описать концепцию использования переменных для какого-нибудь нового языка программирования, сперва нужно разделить все переменные по их времени жизни на статические и локальные (автоматические):


  • Статические — это глобальные переменные, функции и типы данных к которым можно обратиться из любого другого участка кода или модуля. Статические переменные (объекты) создаются как правило в куче и сохраняют свое значение при выходе из блока кода, где были определены (т.е. после выхода из текущей области видимости).
  • Автоматические или локальные переменные, это аргументы функций и переменные в выражениях, которые создаются компилятором в автоматическом режиме как правило на стеке. Локальные и автоматические переменные доступные только изнутри того лексического контекста, в котором они были определены, а их значения уничтожаются при выходе из блока кода, где они были созданы.

И определить следующие виды переменных:


  • переменная по значению (variable by value) — данные хранятся непосредственно в самой переменной, а при копировании переменной создается новая копия данных. Ссылки такие переменные запрещены.
  • общая переменная (common variable) — классическая переменная по ссылке. В переменой хранится только указатель на данные (например shared_ptr) который увеличивает счетчик владений данными. При копировании переменной копируется только указатель и увеличивается счетчик владений.
  • разделяемая переменная (shared variable) — тоже переменная по ссылке в которой хранится указатель на данные со счетчиком владений, но копировать саму переменную запрещено (можно сделать только swap — обмен значениями, который необходим для copy-and-swap idiom), но для такой переменной можно получить переменную-ссылку.
  • переменная ссылка — слабый указатель на разделяемую переменную, который не увеличивает счетчик владений (weak_ptr). Перед использованием слабый указатель необходимо преобразовать в сильный или сохранить в общую переменную.

Тогда правилами для работы с такими видами переменных будут следующие:


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

Ссылки и конкурентный доступ

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


Доступ из разных потоков возможен только у разделяемых переменных. Причем совместный доступ реализуется за счет наличия переменных-ссылок, которые разрешено создавать для разделяемых переменных.


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


Типы ссылок с точки зрения разделяемого доступа могут быть:


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

Операторы для ссылок

Так как любая переменная-ссылка является слабой (weak_ptr), перед использовать её требуется преобразовать в сильную ссылку. А с учетом возможного конкурентого доступа из разных потоков, требуется ещё выполнять и захват объект межпотоковой синхронизации (если он используется).


Захват ссылки — это захват объекта синхронизации доступа к переменной (при его наличии) и преобразование слабой ссылки в сильную с инкрементом счетчика владения и сохранением результата в локальную (автоматическую) переменную.


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


В завершении


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


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


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


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

Комментарии (95)


  1. Zenitchik
    08.11.2024 11:19

    Можете пояснить, зачем нужна операция swap, почему нужно запрещать копирование разделяемых ссылок, и что понимается под "использованием ссылки", для которого она непременно должна быть сильной?


    1. rsashka Автор
      08.11.2024 11:19

      Операция swap нужна для реализации copy-and-swap idiom.

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

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


      1. Zenitchik
        08.11.2024 11:19

        Погодите. Допустим, я хочу обратиться к объекту, и прочитать его поле. Мне для этого придётся инкрементировать счётчик владений?


        1. rsashka Автор
          08.11.2024 11:19

          Не вам лично. Если объект является общей переменной (shared_ptr), то его сохранение в локальной переменной будет инкрементировать счетчик владений автоматически.


          1. Zenitchik
            08.11.2024 11:19

            Не вам лично.

            Дураку ясно, что не мне лично! Вы слышали, что про такое слово, как "иносказание"?

            то его сохранение в локальной переменной 

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


            1. rsashka Автор
              08.11.2024 11:19

              Если у вас общая переменная уже содержит shared_ptr, то естественно никакого лишнего инкремента не будет.

              Счетчик владений инкрементируется только при копировании общей переменной в другую переменную или при захвате слабого указателя (преобразовании weak_ptr -> shared_ptr).


  1. ednersky
    08.11.2024 11:19

    Вам надо на ерланг взглянуть, вот где все эти траблемы решены :)


    1. rsashka Автор
      08.11.2024 11:19

      Там и своих проблем хватает.


  1. mayorovp
    08.11.2024 11:19

    Поэтому принято считать, что неизменяемые объекты в Python в качестве аргументов передаются по значению, тогда как изменяемые объекты (списки (list), множества (set) и словари (dict)), всегда передаются по ссылке.

    Чушь. Такой способ передачи параметров называется pass by sharing, русский перевод не устоялся. Он совершенно точно не является передачей по ссылке.


    1. rsashka Автор
      08.11.2024 11:19

      точно не является передачей по ссылке.

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


      1. Zenitchik
        08.11.2024 11:19

        Это передача по значению. Но значением является ссылка.


        1. rsashka Автор
          08.11.2024 11:19

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


          1. Zenitchik
            08.11.2024 11:19

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


            1. rsashka Автор
              08.11.2024 11:19

              Вы совершенно правы с точки зрения классического С/С++!!!

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

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


  1. pawnhearts
    08.11.2024 11:19

    >что с учетом отсутствия в Python строгой типизации

    Python is strongly, dynamically typed.

    • Strong typing means that the type of a value doesn't change in unexpected ways. A string containing only digits doesn't magically become a number, as may happen in Perl. Every change of type requires an explicit conversion.

    • Dynamic typing means that runtime objects (values) have a type, as opposed to static typing where variables have a type.


    1. rsashka Автор
      08.11.2024 11:19

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


  1. Apoheliy
    08.11.2024 11:19

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

    какого-нибудь нового языка программирования

    И это всё наверное будет работать, особенно если все низкоуровневые части раскидать по внешним библиотекам.

    Но если мы говорим про язык уровня С++ (а автор Говорит про C++), то можно вспомнить, что в управлении ресурсов участвует не только сама программа (и компилятор за ней), но и другие субъекты.

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

    Таких тонкостей на "низком" уровне (и с памятью, и с хендлами, и с межпоточкой) - их очень много.

    Хочется всё решить новым языком с новыми концепциями? Пожелаю Вам удачи!


    1. rsashka Автор
      08.11.2024 11:19

      Спасибо за комментарий!

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

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


      1. VoodooCat
        08.11.2024 11:19

        Компилятор - не может помнить про динамически выделяемую память просто потому что во время этого самого динамизма - рыла компилятора в этом празднике - не участвует. Аллокации на куче - помнит куча.

        Выделите массив рандомного размера и верните его из функции, а элементами массива - пусть будут буфера, но выделены тоже рандомного, где-то есть, где-то nullptr. Много компилятор "запомнит"?


  1. Lewigh
    08.11.2024 11:19

    Чтобы описать концепцию использования переменных для какого-нибудь нового языка программирования, сперва нужно разделить все переменные по их времени жизни на статические и локальные (автоматические):

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

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

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


    1. rsashka Автор
      08.11.2024 11:19

      Не важно, где выделяется память под переменную. Важно лишь то, удаляется ли она после выхода их текущего контекста или нет. Если удаляется, то локальная (автоматическая), если же остается, то статическая.


  1. Sly_tom_cat
    08.11.2024 11:19

    Была у меня история с интерпретатором LISP - там подсчет ссылок лег под капот языка как родной. Там все - динамическое, просто язык такой.


    1. funny_falcon
      08.11.2024 11:19

      А как с циклами боролись?


      1. Sly_tom_cat
        08.11.2024 11:19

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

        Там сам код - список из списков и скаляров. Грамматика языка - простая как палка. На столько простая что я ее начал на if-ах делать... три раза переделывал пока до меня не доперло сделать простой автомат синтаксического разбора.


  1. SergeyProkhorenko
    08.11.2024 11:19

    Не хватает графической схемы. Поэтому тяжело понять.


  1. qw1
    08.11.2024 11:19

    Не совсем понял статус этой разработки: идея, или готовая концепция, библиотека, язык программирования, или принцип, которого можно придерживаться в любом ЯП? C++ или Python?


    1. rsashka Автор
      08.11.2024 11:19

      Это прототип концепции (принцип) которого можно придерживаться в некоторых ЯП. Базовые элементы взяты готовые из С++, поэтому на низком уровне все совместимо с уже существующим кодом.

      Но для проверок в compile-time требуется либо препроцессор, либо добавлять поддержку в компиляторе.


  1. qw1
    08.11.2024 11:19

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

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

    Представьте обычный двунаправленный список. Если все ссылки prev/next будут сильные - сразу же образуется цикл. Если все ссылки будут слабыми - список тотчас же уничтожит менеджер памяти, как структуру, на которую нет сильных ссылок.


    1. rsashka Автор
      08.11.2024 11:19

      Такая идея будет работать и в том случае, если компилятор будет за этим следить.

      В вашем примере (в двунаправленном списке) компилятор не даст создать две владеющие ссылки на одном уровне (это будет ошибка компиляции).

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


      1. qw1
        08.11.2024 11:19

        Я считаю, это невыполнимо.
        Опишем одну ноду списка:

        struct Node {
           Node* prev;
           Node* next;
           int data;
        };
        

        Компилятор тут ругается, или ещё нет?

        Опишем функции работы с нодами:

        void setPrev(Node* _this, Node* p) { _this->prev = p; }
        void setNext(Node* _this, Node* n) { _this->next = n; }
        

        Тут компилятор ругается, или пока ещё всё нормально?

        На какой код компилятор должен ругаться?

        Если я размечу ссылки, что от этого меняется?

        struct Node {
           [[weak]] Node* prev;
           [[strong]] Node* next;
           int data;
        };
        


        1. rsashka Автор
          08.11.2024 11:19

          Если я размечу ссылки, что от этого меняется?

          Изменяется то, что компилятор сам будет следить за тем, чтобы в поля prev и next невозможно было сохранить сильный указатель на один и тот же объект.


          1. amishaa
            08.11.2024 11:19

            Так для циклических ссылок не нужен один и тот же объект: достаточно в next одного и prev другого сделать сильную ссылку. И всё, вот утечка памяти.


            1. rsashka Автор
              08.11.2024 11:19

              Так я именно про это и пишу.

              Для компилятора поля prev и next находятся на одному ровне вложенности. Поэтому нельзя создать объект (сильную ссылку) и сохранить её в оба эти поля одновременно.

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


              1. qw1
                08.11.2024 11:19

                Вы на мой вопрос не ответили: код, который я представил, должен компилироваться? Если нет, какая ошибка?


                1. rsashka Автор
                  08.11.2024 11:19

                  Ааааа! Теперь кажется понял. Вопрос не в объявлении, а в том, что присвоение может быть неявным (например через сеттеры) и как это отследить на этапе компиляции?
                  Теперь я правильно понял вопрос?


                  1. qw1
                    08.11.2024 11:19

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


                    1. rsashka Автор
                      08.11.2024 11:19

                      Ваши комментарии самые полезные. Это уже не первый заход с попыткой решения данной проблемы, и один из них пришлось переделывать как раз из-за ваших комментариев.

                      Чему, кстати, я был очень рад, так как проблема вылезла еще на этапе проектирования!


                1. rsashka Автор
                  08.11.2024 11:19

                  Аргументы p и n, это автоматические переменные, которые должны быть удалены после вызова функции, а они неявно возвращаются через _this в полях prev и next.

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

                  void setPrev(Node* _this, Node* p) { _this->prev = p; }
                  void setNext(Node* _this, Node* n) { _this->next = n; }
                  


                  1. qw1
                    08.11.2024 11:19

                    То есть, сеттеры в принципе запрещены, или этот код можно починить?

                    И что значит "возвращаются", как компилятор об этом догадается?
                    Если он видит фунцию

                    void debugPrint(char* message) {
                        printf("%s\n", message);
                    }
                    

                    он не должен её компилировать, потому что "автоматическая переменная" message уходит в какую-то неизвестную функцию printf, которая, кто знает, может сохранит значение ссылки себе куда-нибудь в глобальную переменную.


                    1. rsashka Автор
                      08.11.2024 11:19

                      То есть, сеттеры в принципе запрещены, или этот код можно починить?

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

                      И что значит "возвращаются", как компилятор об этом догадается?

                      Node* _this, это ссылочная переменная, которая передается в качестве аргумента (фактически out Node _this*), поэтому у компилятора не возникнет трудностей об этом догадаться.

                      он не должен её компилировать, потому что "автоматическая переменная" message уходит в какую-то неизвестную функцию printf, которая, кто знает, может сохранит значение ссылки себе куда-нибудь в глобальную переменную.

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

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


                      1. qw1
                        08.11.2024 11:19

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

                        "Эти" - поля в структуре Node?

                        Если обе ссылки (prev, next) сделать weak, структура просто развалится, потому что за неимением сильной ссылки на последующие элементы списка, по правилам работы слабых ссылок, весь хвост списка надо удалить.


                      1. rsashka Автор
                        08.11.2024 11:19

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

                        Но не правы в том, что связанный список не возможен. Просто нужно объявлять структуру так, как у вас было сделано в самом последнем случае (когда одна ссылка владеющая, а слабая только вторая).

                        struct Node {
                           [[weak]] Node* prev;
                           [[strong]] Node* next;
                           int data;
                        };
                        


                      1. qw1
                        08.11.2024 11:19

                        Ха-ха, вы идёте строго по дорожке из крошек, которую я заранее подготовил.

                        А теперь у меня тривиальное бинарное дерево:

                        struct TreeNode {
                           [[strong]] TreeNode* left;
                           [[strong]] TreeNode* right;
                           int data;
                        };
                        

                        Всё, приехали? В вашей парадигме двоичные деревья запрещены?


                      1. rsashka Автор
                        08.11.2024 11:19

                        Всё, приехали? В вашей парадигме двоичные деревья запрещены?

                        Нет, не запрещены. Но запрещено присваивать копию сильной ссылки на одном уровне вложенности. т.е. у вас left и right должны быть разными объектами.


                      1. qw1
                        08.11.2024 11:19

                        И как это защищает от циклических ссылок?

                        TreeNode* root = new TreeNode();
                        TreeNode* child = new TreeNode();
                        root->left = child;
                        child->right = root;
                        

                        Формально,
                        root->left и root->right - разные,
                        child->left и child->right - разные,
                        А цикл есть.


                      1. rsashka Автор
                        08.11.2024 11:19

                        Такая конструкция не допускается, так как root (а поэтому и root->left) и child (child->right) находятся на одном уровне вложенности и сделать копию (root->left = child; и child->right = root;) не получится.

                        Но можно сделать так:

                        root->left = new TreeNode();
                        root->right = new TreeNode();
                        

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


                      1. qw1
                        08.11.2024 11:19

                        В смысле не получится? Сформулируйте правило, которое это запрещает.

                        "Уровень вложенности" - это свойство чего? Локальной переменной, поля класса, стека вызовов функций?


                      1. amishaa
                        08.11.2024 11:19

                        Можно даже не уходить в деревья.
                        Пусть у нас связанный список, у которого сильные ссылки только вперёд.

                        Операция "сконкатинируй два списка (т.е. имея одну ноду у которой нет prev и одну ноду у которой нет next пропиши соответствующие ссылки)" допустимая или нет?


                      1. rsashka Автор
                        08.11.2024 11:19

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

                        Речь идет о вложенности блоков кода лексического контекста.

                        Node* node = new Node();
                        Node* error =  node; // Так нельзя
                          {
                            Node* copy =  node; // Так можно
                          }
                        


                      1. qw1
                        08.11.2024 11:19

                        1. Что делать с сеттерами? Запрещены?
                          Например, мне нужен std::vector или std::map, который владеет объектами.
                          Но я не могу передать ссылку в vector::push_back(obj)

                        2. Как я понимаю, вы хотите, чтобы у каждого объекта была ровно 1 владеющая ссылка, а все остальные - слабые.

                        Тут 2 проблемы:

                        2.1 Слабые ссылки имеют большие накладные расходы. При уничтожении объекта от должен оповестить все известные слабые ссылки на него, чтобы они пометили у себя удаление объекта. То есть, любой [[strong]] Node* ptr должен под капотом держать vector<WeakRef<Node>*> refs

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

                        2.2 Не решается проблема времени жизни. То есть, если в программе есть ошибки, и объект Server был удалён раньше, чем корректно затушены все его клиенты, то клиенты, при попытке постучаеться на сервер по слабой ссылке, получает "недоступен". Но по задумке архитектора, допустим, такого быть не должно. И что делать? Вызывать panic() и это ничем не отличается от SegFault при доступе к недействительной ссылке? Или молча заметать мусор под ковёр, в обход спроектированной логики, теряя данные?

                        1. А что насчёт

                        TreeNode* node = new TreeNode();
                        node->left = new TreeNode();
                        node->left = new TreeNode();
                        

                        Какое-нибудь правило запрещает это?


                      1. rsashka Автор
                        08.11.2024 11:19

                        1. Что делать с сеттерами? Запрещены? ... Но я не могу передать ссылку в vector::push_back(obj)

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

                        1. Как я понимаю, вы хотите, чтобы у каждого объекта была ровно 1 владеющая ссылка, а все остальные - слабые.

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

                        2.1 Слабые ссылки имеют большие накладные расходы.

                        По моему в реализациях shared_ptr и weak_ptr нет никаких оповещений или векторов.

                        2.2 ... если в программе есть ошибки, и объект Server был удалён раньше, чем корректно затушены все его клиенты, то клиенты, при попытке постучаеться на сервер по слабой ссылке, получает "недоступен". Но по задумке архитектора, допустим, такого быть не должно. И что делать?

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


                      1. amishaa
                        08.11.2024 11:19

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

                        Так же получится много сильных ссылок на сервер?

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


                      1. rsashka Автор
                        08.11.2024 11:19

                        Тогда я не понял, кто от кого зависит.

                        Если клиент зависит от сервера и хранит ссылку на него, тогда при создании клиента ему передается объект сервер (сильная ссылка), которая и сохраняется у него до завершения работы клиента. И таких ссылок будет столько, сколько клиентов было создано.


                      1. qw1
                        08.11.2024 11:19

                        Так же получится много сильных ссылок на сервер?
                        И может ли у сервера быть сильная ссылка на клиент в таком сетапе?

                        Тогда я не понял, кто от кого зависит.

                        Вы свели всё к "пишите правильно, неправильно не пишите".

                        Понятно, что если аккуратно всё писать, можно безошибочно реализовать хоть на ассемблере. Но вы нам обещали, что компилятор не позволит писать неправильно.


                      1. rsashka Автор
                        08.11.2024 11:19

                        Вы свели всё к "пишите правильно, неправильно не пишите".

                        Нет, так как за выполнением данных правил должен следить компилятор. Поэтому данный подход не "бест практикс", а именно правила языка программирования, которые контролируются в compile-time.


                      1. qw1
                        08.11.2024 11:19

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


                      1. rsashka Автор
                        08.11.2024 11:19

                        С данным утверждением я полностью согласен.

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


                      1. qw1
                        08.11.2024 11:19

                        С данным утверждением я полностью согласен

                        Тогда бессмысленно критиковать и придумывать контр-примеры. Вы будете постоянно менять правила на ходу.

                        Когда допишете, тогда и приходите )))


                      1. qw1
                        08.11.2024 11:19

                        Что делать с сеттерами? Запрещены?
                        не запрещены. Просто вы приводили пример функции, которая возвращая сильный указатель через out аргумент. Так действительно нельзя, но можно использовать метод, который сохранит аргумент в поле класса. Тогда и не будет возврата сильной ссылки из функции

                        Поле класса... Меняете правила на ходу. Потому что раньше про поля класса не говорилось.

                        Вы похоже прикола не выкупили, почему я параметр назвал _this.

                        Вот так у вас нельзя:

                        void setNext(Node* _this, Node* n) { _this->next = n; }
                        

                        А вот так, внезапно, можно. Хотя под капотом это одно и то же )))

                        struct Node {
                            Node* next;
                            int data;
                            void setNext(Node* n) { next = n; }
                        };
                        

                        По моему в реализациях shared_ptr и weak_ptr нет никаких оповещений или векторов.

                        Ха-ха! А как, по-вашему, weak_ptr узнает, что его target более недействителен?

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

                        Вы постоянно путаетесь между статическим назначением владельца (для которого придумали правило "владеющий указатель" на вершине "синтаксического контекста") и управлением памятью через подсчёт ссылок.

                        Сейчас вы пишете "хоть один живой клиент" - это значит, подсчёт ссылок и нарушение правила единственного владельца. Но тогда возможны циклы ссылок и утечки памяти.


                      1. rsashka Автор
                        08.11.2024 11:19

                        А вот так, внезапно, можно. Хотя под капотом это одно и то же )))

                        Вы правы в том, что "под капотом" одно и тоже. Но не учитываете, что данном случае метод класса, это не только обычная функция "под капотом", но и определенная лексическая единица в AST (как метод объекта).

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

                        Ха-ха! А как, по-вашему, weak_ptr узнает, что его target более недействителен?

                        В момент захвата

                        Вы постоянно путаетесь между статическим назначением владельца (для которого придумали правило "владеющий указатель" на вершине "синтаксического контекста") и управлением памятью через подсчёт ссылок.

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

                        Сейчас вы пишете "хоть один живой клиент" - это значит, подсчёт ссылок и нарушение правила единственного владельца. Но тогда возможны циклы ссылок и утечки памяти.

                        Я не говорил про единственного владельца, я писал, чтобы "... у каждого объекта была 1 владеющая ссылка на самом верхнем лексическом уровне."


                      1. qw1
                        08.11.2024 11:19

                        И в данном случае одна и та же "под капотом" функция сеттера является принципиально разной с точки зрения синтаксического анализа

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

                        В момент захвата

                        Я спросил не "когда", а "как".
                        Как метод lock узнает, что объект был удалён до вызова lock?

                        Классическое решение - shared_ptr ведёт список своих слабых ссылок и уведомляет их в момент разрушения объекта, слабые ссылки переходят в состояние "недействителен".

                        Ваше решение?

                        Я не говорил про единственного владельца, я писал, чтобы

                        Ок, хорошо. У вас все, абсолютно все указатели - либо shared_ptr, либо weak_ptr, верно?


                      1. rsashka Автор
                        08.11.2024 11:19

                        ... а та же самая установка через метод класса позволяет это сделать.

                        Да, все так. Метод класса сохраняет данные в этом самом классе, который в свою очередь должен находится в какой-то переменной, которая в свою очередь подчиняется все тем же лексическим правилам.

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

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

                        Классическое решение - shared_ptr ведёт список своих слабых ссылок и уведомляет их в момент разрушения объекта, слабые ссылки переходят в состояние "недействителен".

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


                      1. qw1
                        08.11.2024 11:19

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

                        И в чём разница?

                        setNext(node, nextNode); // ахтунг, опасность!
                        node->setNext(nextNode); // выдыхаем, безопастно!
                        

                        Вы можете скинуть ссылку на файл с реализацией данных шаблонов

                        Посмотрел, как сейчас делают. Реализация weak, которую я держал в голове, чрезмерно избыточна. Сейчас на каждый shared-объект делают 2 аллокации: сам объект и его control block, связанный с объектом двунаправленными ссылками. Все weak-указатели указывают на control block. При удалении объекта он делает пометку в control block. Control block не удаляется, пока жива хотя бы одна weak-ссылка (выполняется подсчёт ссылок).


                      1. rsashka Автор
                        08.11.2024 11:19

                        И в чём разница?

                        Разница в том, что для функции setNext(node, nextNode); // ахтунг, опасность! аргумент node является выходным и может быть на любом уровне иерархии AST, поэтому nextNode может быть сохранен в переменную выше разрешенного лексического уровня.

                        А вот для кода node->setNext(nextNode); // выдыхаем, безопастно!, максимальный лексический уровень сохранения nextNode ограничен уровнем объекта node, как как nextNode гарантированно создается позже объекта node и не может быть выше его уровня в AST, а это является гарантией от возникновения циклически ссылок (именно этот момент не получается проверить во время компиляции для первого варианта функции).


                      1. qw1
                        08.11.2024 11:19

                        Что можно проверить во время компиляции "безопасного" кода?

                        Node* n1 = new Node();
                        Node* n2 = new Node();
                        n1->setNext(n2);
                        n2->setNext(n1);
                        

                        Чем это отличается от корректного

                        Node* n1 = new Node();
                        Node* n2 = new Node();
                        n1->setNext(n2);
                        n2->setPrev(n1);
                        

                        Если компилятор не видит семантику функций setNext, setPrev - декларации у них полностью одинаковые, а тело может быть в другом юните трансляции.


                      1. rsashka Автор
                        08.11.2024 11:19

                        Если компилятор не видит семантику функций setNext, setPrev - декларации у них полностью одинаковые, а тело может быть в другом юните трансляции.

                        Но ведь он их должен видеть (декларацию, а не реализацию):

                        struct Node {
                           [[weak]] Node* prev;
                           [[strong]] Node* next;
                           int data;
                        void setNext( [[strong]]  Node *);
                        void setPrev( [[weak]]  Node *);
                        };
                        

                        А это значит, компилятор проверяет аргумент метода void setPrev( [[weak]] Node *); которым должна быть слабая ссылка, либо сильная ссылка должна быть преобразована в слабую уже в теле метода при присвоении нового значения полю prev.


                      1. qw1
                        08.11.2024 11:19

                        И какое правило запрещает передавать сильную ссылку во 2-й setNext, но разрешает передавать в 1-й?
                        Сформулируйте так, чтобы его можно было закодить.


                      1. rsashka Автор
                        08.11.2024 11:19

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

                        Я не прав, утверждая в предыдущем комментарии, что "к nextNode гарантированно создается позже объекта node и не может быть выше его уровня в AST". Он может быть создан раньше объекта node.


                      1. amishaa
                        08.11.2024 11:19

                        Более того, свойство "создаётся гарантированно позже" может быть не определено на переменных:

                        var *a = ...;
                        var *b = ...;
                        var *c = ...;
                        var *d = if(rand < 0.5) a else c

                        И всё - переменные b и d могут быть созданы в любом порядке.


                      1. rsashka Автор
                        08.11.2024 11:19

                        Какое-нибудь правило запрещает это?

                        Чувствую, что придумали какое-то каверзное решение :-)

                        Нет не запрещает, так как new TreeNode(); по определению имеет только одну владеющую ссылку и сохранить её можно куда угодно.

                        А так как строка node->left = new TreeNode(); выполняется дважды, то результат первого вызова удалится после перезаписи поля left (ведь в нашем условном примере new должен возвращать shared_ptr).


                      1. mayorovp
                        08.11.2024 11:19

                        Речь идет о вложенности блоков кода лексического контекста.

                        А чем это поможет-то?


                      1. rsashka Автор
                        08.11.2024 11:19

                        При завершении лексического контекста, все локальные переменные автоматически уничтожаются.


                      1. mayorovp
                        08.11.2024 11:19

                        Так в случае с одноуровневыми локальными переменными они тоже автоматически уничтожаются.


                      1. rsashka Автор
                        08.11.2024 11:19

                        "Уровень вложенности" - это свойство чего? Локальной переменной, поля класса, стека вызовов функций?

                        Синтаксического контекста


  1. VoodooCat
    08.11.2024 11:19

    Сборщики мусора нужны для управления сложными и порою непредсказуемыми графами объектов, т.е. когда вы либо сами мозгом не способны понять все (это не укол), либо вы интерпретируете/исполняете код третьей стороны, который априори может не делать все правильно. Типичный пример последнего это JS и DOM - API которых предполагают сборку мусора как таковую.

    Вы же в введении говорите про то что как хорошо бы что б компилятор проверял - но это вообще параллельные проблемы.


    1. rsashka Автор
      08.11.2024 11:19

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

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


      1. Kealon
        08.11.2024 11:19

        Двух связный список сможете описать?

        Это циклическая структура если что


        1. rsashka Автор
          08.11.2024 11:19

          Да, это уже обсуждалось


  1. Anarchist
    08.11.2024 11:19

    Rust не?


    1. rsashka Автор
      08.11.2024 11:19

      Так у Rust нет подсчета ссылок. Там же только контроль перехода владения?


      1. sdramare
        08.11.2024 11:19

        Rc<T>


        1. rsashka Автор
          08.11.2024 11:19

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

          У С++ в STL тоже есть примитивы для контроля владения и подсчета ссылок, но это никак не мешает разработчикам писать программы с ошибками :-)


          1. qw1
            08.11.2024 11:19

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

            Это и хорошо. В rust можно аллоцировать структуру и "одолжить" её вызываемой функции, потом забрать обратно и освободить память. Всё управление zero-cost, compile-time. В вашей же концепции такую структуру надо делать common variable + создавать shared variable для передачи в функцию. На ровном месте ненужный счётчик и недешёвые atomic inc/dec для его обслуживания.

            в STL тоже есть примитивы для контроля владения и подсчета ссылок, но это никак не мешает разработчикам писать программы с ошибками

            А в rust невозможны утечки памяти через циклы Rc
            Значит, проблема в C++ в и STL.


            1. sdramare
              08.11.2024 11:19

              А в rust невозможны утечки памяти через циклы Rc

              Зато возможны через Rc<RefCell<T>> . Всегда можно найти способ выстрелить в ногу.


          1. sdramare
            08.11.2024 11:19

            То, что вы в языке сделаете алиас типа &Τ -> Rc<T> никак не поменяет сути.


          1. sdramare
            08.11.2024 11:19

            Вы так говорите, как-будто автоматическая генерация ref counters на любые графы это что-то хорошее. По-факту у вас получается крайне неэффективный вариант автоматический сборки мусора, зачем это нужно не очень понятно. Тогда уж проще сразу GC поставить с хорошим эскейп анализом, чтобы отбросить generational hypothesis, как это сделали в Го.


            1. rsashka Автор
              08.11.2024 11:19

              В отличие от GC, подсчет ссылок выполняется не рантайме, а во время компиляции.


              1. sdramare
                08.11.2024 11:19

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


                1. rsashka Автор
                  08.11.2024 11:19

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

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


  1. MasterMentor
    08.11.2024 11:19

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

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


    1. rsashka Автор
      08.11.2024 11:19

      Если это не будет сделано на уровне синтаксиса языка (прямо в компиляторе), тогда только и остается использовать как набор best practice. Однако если не следить за их выполнением, тогда это будут только пожелания без каких либо реальных гарантий.


  1. murkin-kot
    08.11.2024 11:19

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

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

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


    1. rsashka Автор
      08.11.2024 11:19

      А почему вы пришли к такому выводу? Почему вы считаете, что не было изучения разных подходов, сравнения различных вариантов реализации и разработки прототипов?

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


      1. sdramare
        08.11.2024 11:19

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


        1. rsashka Автор
          08.11.2024 11:19

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