OberonCore
https://forum.oberoncore.ru/

Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
https://forum.oberoncore.ru/viewtopic.php?f=27&t=1320		 Страница 7 из 8
Автор:  Info21 [ Понедельник, 02 Февраль, 2009 16:59 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
... если есть возможность прокинуть более жесткий контракт ... то ошибок будет меньше. При условии, конечно, что такое "прокидывание" контракта не ухудшает другие параметры системы. Если такие ухудшения есть, то мне будет интересно их обсудить.
Лично я только за. Где сей чудный способ?
Автор:  Vlad [ Понедельник, 02 Февраль, 2009 17:09 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Info21 писал(а):
Vlad писал(а):
... если есть возможность прокинуть более жесткий контракт ... то ошибок будет меньше. При условии, конечно, что такое "прокидывание" контракта не ухудшает другие параметры системы. Если такие ухудшения есть, то мне будет интересно их обсудить.
Лично я только за. Где сей чудный способ?


Ненулевые ссылки - более жесткий контракт для "производителя", который может диктоваться "потребителем". Компилятор проследит за тем, чтобы этот контракт дошел до производителя через всю систему.
Автор:  Сергей Губанов [ Понедельник, 02 Февраль, 2009 17:32 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
Да, собственно, я тоже ничего нового не придумал. Все уже есть в существующих ЯП (в том или ином виде). И тут выходите вы и заявляете, что это невозможно даже теоретически. Ну не смешно?

Не смешно. Теоретически невозможно. В каком существующем языке это есть?

Vlad писал(а):
Ну и зачем вы поскипали то, что я написал дальше? Тогда еще раз: заводится "ссылка" а-ля ref<T>, требующая явной инициализации и изменяемая как угодно динамически. И ваш пример со списком замечательно переписывается на реальном языке с реальным контролем "ненулевости".

В С++ ссылка инициализируется единожды, после этого её нельзя поменять.
Автор:  slava [ Понедельник, 02 Февраль, 2009 17:43 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
slava писал(а):
Неужели "висячие указатели" или "выход за границы массива" -- это не ошибки в миллиард $ ?
На нулевых указателях любая система надежно падает, а другие ошибки большинство систем просто игнорируют.
Висячие указатели и прочие выходы за границы - проблемы, успешно решенные практически всеми современными ЯП (собственно, кроме C/C++ никого и не осталось с такими проблемами). А вот проблема нулевых ссылок толком еще не решена. И именно ее мы обсуждаем.
Значит те проблемы не стоят денег?
И вообще C++ и C ни где не применяются?

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

Так как должна быть решена эта проблема?
Падение уже обеспечено, хотите, что бы в очевидных случаях (references) компилятор ругался?
Так в не очевидных случаях (common pointers) все будет падать как прежде.

Короче неплохо было бы почитать статью для начала.
Автор:  Илья Ермаков [ Понедельник, 02 Февраль, 2009 17:45 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
Не надо меня пугать сложными случаями, лучше покажите :) Неужели так трудно дать ссылку на какой-нибудь экзотический численный метод где без сложных (но правильных) циклов ну никак?

Да самый простейший пример - двоичный поиск (ну вдруг акромя stl::search придётся руками писать :) ). Попробуйте методом тыка его написать и отладить. Без понятия инварианта.
Проход по последовательности векторов (т.е. значений пары-тройки переменных, меняющихся в цикле), которые отвечают некоторому хитрому соотношению, и от предыдущего к последующему нетривиальный переход.
Конечно, первое, что делают многие, это пишут FOR FOR FOR IF подходит THEN ... Затем начинают думать, как оптимизировать, ибо полный перебор по быстродействию не подходит. Тык-мык паяльником :)
Автор:  Vlad [ Понедельник, 02 Февраль, 2009 17:47 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Сергей Губанов писал(а):
Не смешно. Теоретически невозможно. В каком существующем языке это есть?


Есть что? Контроль за явной инициализацей? C++. Ненулевые ссылки? Haskell.

Сергей Губанов писал(а):
В С++ ссылка инициализируется единожды, после этого её нельзя поменять.


Код:
template <typename T>
class ref
{
public:
    ref(T &r) : p(&r) {}
private:
    T* p;
};

struct Item
{
    int Value;
    ref<Item> next;
};


Еще больше разжевать?
Автор:  Vlad [ Понедельник, 02 Февраль, 2009 17:53 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
slava писал(а):
Значит те проблемы не стоят денег?


Значит вы пытаетесь сменить тему. Проблема висячих указателей и прочих прелестей отсутствия GC уже сто раз обсосана и мне неинтересна.

slava писал(а):
И вообще C++ и C ни где не применяются?


Эта тема мне тоже неинтересна.

slava писал(а):
А как те проблемы решены в большинстве ЯП?


Посмотрите, что-ли... Полезно иметь представление о том, что в мире творится.

slava писал(а):
Так в не очевидных случаях (common pointers) все будет падать как прежде.


Почитайте внимательно ветку.

slava писал(а):
Короче неплохо было бы почитать статью для начала.


Это да.
Автор:  Сергей Губанов [ Понедельник, 02 Февраль, 2009 17:54 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Вот вызывается процедура. Пусть в процедуре есть локальная переменная являющаяся указателем. Под эту переменную резервируется место на стеке. В процессе выполнения кода процедуры это место на стеке заполняется каким-то значением перед тем как к нему происходит обращение, это хорошо. Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти, что отведена под указатель, лежит мусор. Чтобы этого не произошло, не стоит дожидаться когда пользовательский код проинициализирует эту область памяти, компилятор сам должен эту область памяти очистить от мусора (т.е. забить нулями) прежде чем начнёт выполняться пользовательский код процедуры.
Автор:  Сергей Губанов [ Понедельник, 02 Февраль, 2009 18:04 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
Еще больше разжевать?

Да.
Автор:  Vlad [ Понедельник, 02 Февраль, 2009 18:24 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Илья Ермаков писал(а):
Да самый простейший пример - двоичный поиск (ну вдруг акромя stl::search придётся руками писать :) ). Попробуйте методом тыка его написать и отладить. Без понятия инварианта.


Давненько я такой фигней не страдал, но рискну. Вот моя "наивная" реализация (с неправильным циклом):
Код:
template <typename I, typename V>
bool binary_search(I begin, I end, const V &v)
{
    while (begin != end)
    {
    I m = begin + (end - begin) / 2;
    if (*m == v)
        return true;

    if (*m < v)
        begin = ++m;
    else
        end = m;
    }
    return false;
}


Критикуйте.
Автор:  Илья Ермаков [ Понедельник, 02 Февраль, 2009 18:58 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Написали? Работает? :-) Замечательно. Пусть я Вам доверяю.

А вот себе б я не доверял, если бы написал такой цикл. Разбираться, когда он из какого места изволит выпрыгнуть - брр. (там и без break, кстати, достаточно и одного условия begin < end).
Я лично знаю, что процесс линейного поиска - это процесс стягивания границ отрезка, таким образом, что держим внутри искомый элемент или его потенциальное место (значит - это и есть инвариант цикла. Если я проговорил это свойство вслух - значит, я знаю инвариант, независимо от того, формализовал я там его или нет - а то народ сразу в бутылку на этом месте лезет..). Я знаю, что процесс должен начаться, пойти и закончиться, стянув отрезок к элементу или позиции под него. Вот такого рода чисто мат. знание и хочется выражать в цикле - просто формулируя его как проекцию. Тогда я понимаю, как оно себе ведёт, а иначе мне приходится изображать из себя компьютер и думать "как оно будет выполняться".
Автор:  Info21 [ Понедельник, 02 Февраль, 2009 19:08 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
Info21 писал(а):
... Лично я только за. Где сей чудный способ?
Ненулевые ссылки - более жесткий контракт для "производителя", который может диктоваться "потребителем". Компилятор проследит за тем, чтобы этот контракт дошел до производителя через всю систему.
"Компилятор проследит" -- это, в общем, не способ, а пожелание.
Но я согласен: пусть проследит :)
Автор:  Сергей Губанов [ Понедельник, 02 Февраль, 2009 19:15 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Vlad писал(а):
Давненько я такой фигней не страдал, но рискну. Вот моя "наивная" реализация (с неправильным циклом):
Код:
template <typename I, typename V>
bool binary_search(I begin, I end, const V &v)
{
    while (begin != end)
    {
    I m = begin + (end - begin) / 2;
    if (*m == v)
        return true;

    if (*m < v)
        begin = ++m;
    else
        end = m;
    }
    return false;
}

Критикуйте.

Незачёт.
Обнаруженные ошибки:
1) Не учтён случай когда искомый элемент находится в позиции begin = end.
2) Программа выдаёт неправильный ответ если искомый элемент находится в позиции end.
Автор:  Сергей Губанов [ Понедельник, 02 Февраль, 2009 19:28 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Илья Ермаков писал(а):
Разбираться, когда он из какого места изволит выпрыгнуть - брр. (там и без break, кстати, достаточно и одного условия begin < end).

begin может быть равен end и элемент может лежать именно там. Без break/return конечно можно, и лучше писать не процедуру-функцию, а процедуру. Я, например, написал такую: void GetPosition (int[] a, int value, out int position), без бряка цикла.
Автор:  Илья Ермаков [ Понедельник, 02 Февраль, 2009 19:53 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Зависит от того, какая граница отрезка какая (точная граница или нет, "не включая"). В "Алгоритмы и структуры данных", мне помнится, было строго <. У меня сколько помню, всегда, когда вдруг приходилось писать этот алгоритм, были проблемы, потому потом привык, что без строгого обдумывания даже пробовать нечего ))
Автор:  PGR [ Понедельник, 02 Февраль, 2009 19:54 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Если begin = end, то массив пустой. end -- указатель на элемент, следующий за последним элементом массива.
Автор:  Info21 [ Понедельник, 02 Февраль, 2009 22:25 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Илья Ермаков писал(а):
.. всегда, когда вдруг приходилось писать этот алгоритм, были проблемы ...
Там есть тонкость: два идеологически чуть разных варианта алгоритма, но второй похож на оптимизацию первого (примерно так их Вирт и преподносит, что логически не точно), и при рассуждениях наобум они путаются. И чтобы четко написать, нужно, действительно, четко проговорить инвариант, чтобы не сбиваться.

Эта пара версий алгоритма -- очень хороший учебный пример для начинающих по теме инвариант цикла, именно в силу этой тонкости с формулировкой инварианта, отражающейся в реализации (и, кстати, в поведении алгоритма, когда в массиве несколько элементов с искомым значением, где видно, что это разные алгоритмы).
Автор:  Wlad [ Понедельник, 02 Февраль, 2009 23:05 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Сергей Губанов писал(а):
Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти

"Вот-вот-вот!"(с)ММЖ
Помните я носился с библиотекой libao, потом перестал? Таки примерно из-за такой ошибки, тока зеркально отражённой из другого места. Просто потому, что система поддержки времени исполнения на Си++ и современные ОС про сборку мусора и объекты ничего не знают, за то они знают про "потоки" вне контекста каких-либо объектов... А лочить всё на уровне ОСи, на время инициализации локальных указателей, системе, для которой собсна и создавалась libao было ОЧЕНЬ накладно... А про ГолубуюБутылку как-то невнятно всё было у начальства...
Автор:  Vlad [ Вторник, 03 Февраль, 2009 00:23 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Сергей Губанов писал(а):
Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти


Ну и что? Ну пусть компилятор пишет туда нули, если он определит, что GC может запуститься до корректной инициализации. Еще придумаете какие-нибудь "проблемы" реализации?
Автор:  Vlad [ Вторник, 03 Февраль, 2009 01:22 ]
Заголовок сообщения:  Re: Хоар: "Нулевые ссылки -- ошибка стоимостью в миллиард доллар
Сергей Губанов писал(а):
Vlad писал(а):
Еще больше разжевать?

Да.


Код:
template <typename T>
class ref
{
public:
    ref(T &r) : p(&r) {}
private:
    T* p;
};

struct Item
{
    Item(int v) : Value(v), next(*this) {}
    Item(int v, ref<Item> n) : Value(v), next(n) {}

    int Value;
    ref<Item> next;
};

Item *first = NULL;
Item *last = NULL;

void put(int v)
{
    ASSERT(bool(first) == bool(last));
   
    if (!first)
        first = last = new Item(v);       
    else
    {
        last->next = *new Item(v, *first);
        last = last->next;
    }
}
Страница 7 из 8 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/