OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 24 Июль, 2019 08:11

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 154 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.
Автор Сообщение
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 16:59 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8169
Откуда: Троицк, Москва
Vlad писал(а):
... если есть возможность прокинуть более жесткий контракт ... то ошибок будет меньше. При условии, конечно, что такое "прокидывание" контракта не ухудшает другие параметры системы. Если такие ухудшения есть, то мне будет интересно их обсудить.
Лично я только за. Где сей чудный способ?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:09 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Info21 писал(а):
Vlad писал(а):
... если есть возможность прокинуть более жесткий контракт ... то ошибок будет меньше. При условии, конечно, что такое "прокидывание" контракта не ухудшает другие параметры системы. Если такие ухудшения есть, то мне будет интересно их обсудить.
Лично я только за. Где сей чудный способ?


Ненулевые ссылки - более жесткий контракт для "производителя", который может диктоваться "потребителем". Компилятор проследит за тем, чтобы этот контракт дошел до производителя через всю систему.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:32 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Vlad писал(а):
Да, собственно, я тоже ничего нового не придумал. Все уже есть в существующих ЯП (в том или ином виде). И тут выходите вы и заявляете, что это невозможно даже теоретически. Ну не смешно?

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:43 

Зарегистрирован: Понедельник, 19 Март, 2007 09:40
Сообщения: 142
Откуда: USA, Israel, Belarus
Vlad писал(а):
slava писал(а):
Неужели "висячие указатели" или "выход за границы массива" -- это не ошибки в миллиард $ ?
На нулевых указателях любая система надежно падает, а другие ошибки большинство систем просто игнорируют.
Висячие указатели и прочие выходы за границы - проблемы, успешно решенные практически всеми современными ЯП (собственно, кроме C/C++ никого и не осталось с такими проблемами). А вот проблема нулевых ссылок толком еще не решена. И именно ее мы обсуждаем.
Значит те проблемы не стоят денег?
И вообще C++ и C ни где не применяются?

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:45 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9127
Откуда: Россия, Орёл
Vlad писал(а):
Не надо меня пугать сложными случаями, лучше покажите :) Неужели так трудно дать ссылку на какой-нибудь экзотический численный метод где без сложных (но правильных) циклов ну никак?

Да самый простейший пример - двоичный поиск (ну вдруг акромя stl::search придётся руками писать :) ). Попробуйте методом тыка его написать и отладить. Без понятия инварианта.
Проход по последовательности векторов (т.е. значений пары-тройки переменных, меняющихся в цикле), которые отвечают некоторому хитрому соотношению, и от предыдущего к последующему нетривиальный переход.
Конечно, первое, что делают многие, это пишут FOR FOR FOR IF подходит THEN ... Затем начинают думать, как оптимизировать, ибо полный перебор по быстродействию не подходит. Тык-мык паяльником :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:47 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Сергей Губанов писал(а):
Не смешно. Теоретически невозможно. В каком существующем языке это есть?


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

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


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

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


Еще больше разжевать?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:53 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
slava писал(а):
Значит те проблемы не стоят денег?


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

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


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

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


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

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


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

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


Это да.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 17:54 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Вот вызывается процедура. Пусть в процедуре есть локальная переменная являющаяся указателем. Под эту переменную резервируется место на стеке. В процессе выполнения кода процедуры это место на стеке заполняется каким-то значением перед тем как к нему происходит обращение, это хорошо. Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти, что отведена под указатель, лежит мусор. Чтобы этого не произошло, не стоит дожидаться когда пользовательский код проинициализирует эту область памяти, компилятор сам должен эту область памяти очистить от мусора (т.е. забить нулями) прежде чем начнёт выполняться пользовательский код процедуры.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 18:04 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Vlad писал(а):
Еще больше разжевать?

Да.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 18:24 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Илья Ермаков писал(а):
Да самый простейший пример - двоичный поиск (ну вдруг акромя 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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9127
Откуда: Россия, Орёл
Написали? Работает? :-) Замечательно. Пусть я Вам доверяю.

А вот себе б я не доверял, если бы написал такой цикл. Разбираться, когда он из какого места изволит выпрыгнуть - брр. (там и без break, кстати, достаточно и одного условия begin < end).
Я лично знаю, что процесс линейного поиска - это процесс стягивания границ отрезка, таким образом, что держим внутри искомый элемент или его потенциальное место (значит - это и есть инвариант цикла. Если я проговорил это свойство вслух - значит, я знаю инвариант, независимо от того, формализовал я там его или нет - а то народ сразу в бутылку на этом месте лезет..). Я знаю, что процесс должен начаться, пойти и закончиться, стянув отрезок к элементу или позиции под него. Вот такого рода чисто мат. знание и хочется выражать в цикле - просто формулируя его как проекцию. Тогда я понимаю, как оно себе ведёт, а иначе мне приходится изображать из себя компьютер и думать "как оно будет выполняться".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 19:08 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8169
Откуда: Троицк, Москва
Vlad писал(а):
Info21 писал(а):
... Лично я только за. Где сей чудный способ?
Ненулевые ссылки - более жесткий контракт для "производителя", который может диктоваться "потребителем". Компилятор проследит за тем, чтобы этот контракт дошел до производителя через всю систему.
"Компилятор проследит" -- это, в общем, не способ, а пожелание.
Но я согласен: пусть проследит :)


Последний раз редактировалось Info21 Понедельник, 02 Февраль, 2009 22:09, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 19:15 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Илья Ермаков писал(а):
Разбираться, когда он из какого места изволит выпрыгнуть - брр. (там и без break, кстати, достаточно и одного условия begin < end).

begin может быть равен end и элемент может лежать именно там. Без break/return конечно можно, и лучше писать не процедуру-функцию, а процедуру. Я, например, написал такую: void GetPosition (int[] a, int value, out int position), без бряка цикла.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 19:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9127
Откуда: Россия, Орёл
Зависит от того, какая граница отрезка какая (точная граница или нет, "не включая"). В "Алгоритмы и структуры данных", мне помнится, было строго <. У меня сколько помню, всегда, когда вдруг приходилось писать этот алгоритм, были проблемы, потому потом привык, что без строгого обдумывания даже пробовать нечего ))


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 19:54 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Если begin = end, то массив пустой. end -- указатель на элемент, следующий за последним элементом массива.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 22:25 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8169
Откуда: Троицк, Москва
Илья Ермаков писал(а):
.. всегда, когда вдруг приходилось писать этот алгоритм, были проблемы ...
Там есть тонкость: два идеологически чуть разных варианта алгоритма, но второй похож на оптимизацию первого (примерно так их Вирт и преподносит, что логически не точно), и при рассуждениях наобум они путаются. И чтобы четко написать, нужно, действительно, четко проговорить инвариант, чтобы не сбиваться.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 02 Февраль, 2009 23:05 

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1378
Сергей Губанов писал(а):
Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Февраль, 2009 00:23 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Сергей Губанов писал(а):
Однако, если между моментом старта процедуры и моментом когда локальная указательная переменная будет проинициализирована запустится сборщик мусора, то он обрушит систему так как в той памяти


Ну и что? Ну пусть компилятор пишет туда нули, если он определит, что GC может запуститься до корректной инициализации. Еще придумаете какие-нибудь "проблемы" реализации?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Февраль, 2009 01:22 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Сергей Губанов писал(а):
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;
    }
}


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 154 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB