Oberon space
General Category => Общий раздел => Тема начата: vlad от Май 21, 2013, 05:27:22 am
-
Согласно репорту указатели можно сравнивать только на равенство. На больше/меньше - нельзя. В чем глубокий смысл такого ограничения? Недостаток вполне очевиден - указатели нельзя использовать в качестве ключа поиска.
-
В чем глубокий смысл такого ограничения?
Причем даже в ББ такая фигня.
-
Согласно репорту указатели можно сравнивать только на равенство. На больше/меньше - нельзя. В чем глубокий смысл такого ограничения? Недостаток вполне очевиден - указатели нельзя использовать в качестве ключа поиска.
А какой смысл использовать указатели в качестве ключей для поиска? :o
-
http://oberspace.dyndns.org/index.php/topic,214.0.html
-
С точки зрения Оберона, сравнение указателей совершенно бессмысленное занятие.
-
Согласно репорту указатели можно сравнивать только на равенство. На больше/меньше - нельзя. В чем глубокий смысл такого ограничения? Недостаток вполне очевиден - указатели нельзя использовать в качестве ключа поиска.
дело в том, что Оберон на уровне языка не определяет структуру адресного пространства (то есть в качестве указателя (значения) может использоваться обьект произвольной сложности (структуры)), в отличии от более низкоуровневых яву (например, язык си постулирует линейное адресное пространство с ячейками размером в байт которое можно представить в виде ленты начинающейся с 0 ячейки ... в ней адрес некоторой переменной (содержимое переменной указателя) - есть номер ячейки с которой начинается переменная в этом пространстве, в этой модели имеют смысл расширенные операции сравнения).
-
.... по ссылке ниже С. Губанов приводит возможные проблемы которые можно огрести развлекаясь с ручными преобразованиями ЗНАЧЕНИЙ указателей
http://oberspace.dyndns.org/index.php/topic,214.0.html
... эти проблемы
1. Предполагается, что адреса можно упорядочить в некотором линейным пространстве
2. Сборщик мусоре НЕ МЕНЯЕТ эти адреса (во время сборки мусора и выделения памяти под обьекты)..
-
.... по ссылке ниже С. Губанов приводит возможные проблемы которые можно огрести развлекаясь с ручными преобразованиями ЗНАЧЕНИЙ указателей
http://oberspace.dyndns.org/index.php/topic,214.0.html
... эти проблемы
1. Предполагается, что адреса можно упорядочить в некотором линейным пространстве
2. Сборщик мусоре НЕ МЕНЯЕТ эти адреса (во время сборки мусора и выделения памяти под обьекты)..
Вообще говоря, сборщик мусора может перемещать объекты (то есть менять адреса) и не собирая мусор (то есть не имея целью освобождение памяти). Компактификация/дефрагментация памяти.
-
А какой смысл использовать указатели в качестве ключей для поиска? :o
А что в этом такого странного? Как еще задать связь между существующим объектом и еще чем-то (неинтрузивно)?
P.S. Перемещающий GC (пусть даже и теоретический применительно к оберонам) все объясняет, всем спасибо :)
-
P.S. Перемещающий GC (пусть даже и теоретический применительно к оберонам) все объясняет, всем спасибо :)
нет (это только пример) (заметьте, что в Паскале аналогично определена только часть операций).. второй пример... возможная реализация виртуального адресного пространства (пусть даже линейного) на нескольких физически различных хранилищах... т.е. когда с точки зрения программиста память выделяется под переменные а и b как обычно но сами эти ячейки расположены в физически различных пространствах (например , на разных машинах) - здесь, возможна такая ситуация, что адреса этих переменных ОДИНАКОВЫ (разумеется в своих адресных пространствах) - как следствие универсальный указатель НЕЛЬЗЯ задать одним лишь адресом ( но можно задать парой (номером виртуального пространства и адресом в нем)) - в этом случае над указателем имеют смысл только операции идентификации (т.е. совпадения - равно , не равно).
-
нет (это только пример) (заметьте, что в Паскале аналогично определена только часть операций).. второй пример... возможная реализация виртуального адресного пространства (пусть даже линейного) на нескольких физически различных хранилищах...
Это что-то сильно экзотическое. А мы тут про квинтэссенцию императивного программирования говорим :)
-
А какой смысл использовать указатели в качестве ключей для поиска? :o
А что в этом такого странного? Как еще задать связь между существующим объектом и еще чем-то (неинтрузивно)?
Хеш-код, конечно же.
-
нет (это только пример) (заметьте, что в Паскале аналогично определена только часть операций).. второй пример... возможная реализация виртуального адресного пространства (пусть даже линейного) на нескольких физически различных хранилищах...
Это что-то сильно экзотическое. А мы тут про квинтэссенцию императивного программирования говорим :)
так она (в том числе) в этом и заключается ( в абстракции от "внутренней структуры" переменных).
-
... из которой следует независимость от реализации.
-
...
2. Сборщик мусоре НЕ МЕНЯЕТ эти адреса (во время сборки мусора и выделения памяти под обьекты)..
Вообще говоря, сборщик мусора может перемещать объекты (то есть менять адреса) и не собирая мусор (то есть не имея целью освобождение памяти). Компактификация/дефрагментация памяти.
Достаточно, чтобы сборщик мусора не менял адреса динамических объектов или вообще не вызывался лишь во время работы процедуры поиска. Возможно, что GC вообще не вызывается во время вызова процедур и загрузки-выгрузки модулей, как в КП.
Такую низкоуровневую процедуру можно реализовать в отдельном модуле через импорт SYSTEM, а внешний пользователь пусть видит только результат поиска.
Я так понимаю, если поиск идет в массиве ссылок типа "T", то процедура поиска будет эквивалентна чему-то такому:
PROCEDURE SearchPointerT* (IN a: ARRAY OF POINTER TO T; p: POINTER TO T; k: INTEGER; b: BOOLEAN): INTEGER;
BEGIN
ASSERT(k >= 0);
WHILE (k < LEN(a)) & ((a[k] = p) # b) DO
INC(k)
END
;RETURN
k (* (k = LEN(a)) OR ((a[k] = p) = b) *)
END SearchPointerT;
При "b = FALSE" - поиск первой ссылки несовпадающей с "p", начиная с "k"-ой;
при "b = TRUE" - поиск первой совпадающей с "p" ссылки, начиная с "k"-ой.
Для ссылок на списки в КП возможна общая процедура:
PROCEDURE SearchPointerRecord (IN a: ARRAY OF ANYPTR; p: ANYPTR; k: INTEGER; b: BOOLEAN): INTEGER;
-
...
как следствие универсальный указатель НЕЛЬЗЯ задать одним лишь адресом ( но можно задать парой (номером виртуального пространства и адресом в нем)) - в этом случае над указателем имеют смысл только операции идентификации (т.е. совпадения - равно , не равно).
Если виртуальные пространства упорядочены, то и указатели в них можно сравнивать (лексикографически), причем в каждом модуле может быть свое упорядочение в.п., которым пользуются процедуры быстрого поиска.
Явное упорядочение универсальных указателей недопустимо при высокоуровневой многозадачности и паралельных вычислениях, результаты таких "независимо" выполненных работ могут зависеть от реального порядка их выполнения.
-
Нужно написать системный модуль с процедурой: PtrToInt. Для любой конечной платформы понадобится изменить только её.
-
Если виртуальные пространства упорядочены, то и указатели в них можно сравнивать (лексикографически), причем в каждом модуле может быть свое упорядочение в.п., которым пользуются процедуры быстрого поиска.
...
на уровне яву(вроде оберона) нельзя - он не определяет такие пространства -с его точки зрения места в которых расположены переменные а и b равнозначны. Соответственно некоторые задачи , которые формулируются в терминах в несводящихся к базовым понятиям ЯВУ невозможно решить естественным образом... как пример... задача программирования примитивного "псевдоблера" рассматриваемая Алексеем на соседней ветке... обратите внимание на уродливые преобразования типов которые ему понадобилось делать для кодирования значений цветовых каналов.. и ему еще "свезло" что необходимое преобразование могло быть выражено через базовые типы и функции... Реально эта задача требует опуститься на уровень ниже (на уровень системо-платформенно- реализационной зависимости от модуля SYSTEM).
-
Хеш-код, конечно же.
Ага. Только для этого надо, чтобы он был у объекта ;)
P.S. Да, я знаю, что во всех мегафрэймворках этот хеш засунут в базовый Object. Что ж еще делать, если сравнивать указатели нельзя... ;)
-
Хеш-код, конечно же.
Ага. Только для этого надо, чтобы он был у объекта ;)
P.S. Да, я знаю, что во всех мегафрэймворках этот хеш засунут в базовый Object. Что ж еще делать, если сравнивать указатели нельзя... ;)
Оно обычно даже не во вреймворке а прямо в языке (во всех этих, так называемых "управляемых" языках - жаба, шарпик и так далее).
-
Нужно написать системный модуль с процедурой: PtrToInt. Для любой конечной платформы понадобится изменить только её.
Можно конечно сунуть все в один модуль, однако такой системный модуль все равно будет зависеть не только от платформы, но и от набора пользовательских модулей, он должен импортировать все сслычные типы, которым требуется процедура упорядочения. Для каждого сслычного типа, процедура PtrToInt все равно будет своя, иначе как же статическая типизация?
PtrToInt дает много лишней информации, в пользовательских модулях лучше пользоваться только результатами быстрого поиска, без возможности запомнить ссылку в виде числа.
-
Если виртуальные пространства упорядочены, то и указатели в них можно сравнивать (лексикографически), причем в каждом модуле может быть свое упорядочение в.п., которым пользуются процедуры быстрого поиска.
...
на уровне яву (вроде оберона) нельзя - он не определяет такие пространства - с его точки зрения места в которых расположены переменные а и b равнозначны.
Так даже упорядочение указателей из одного пространства требует низкоуровневых средств (модуля SYSTEM), так что я о низкоуровневых средствах и говорю, просто результаты для пользовательских модулей не должны зависеть от низкоуровневых деталей.
Можно было бы ввести на уровне языка составной тип вида "SET OF POINTER..." (динамического размера), как в Паскале и Модуле-2, но не только от ординальных типов, но и от ссылочных (они тоже элементарные). Проверка принадлежности элемента такому множеству и будет быстрым поиском объекта в коллекции по его ссылке. Тогда явной низкоуровневости не будет.
-
Так даже упорядочение указателей из одного пространства требует низкоуровневых средств (модуля SYSTEM), так что я о низкоуровневых средствах и говорю, просто результаты для пользовательских модулей не должны зависеть от низкоуровневых деталей.
если так рассуждать то можно дойти до написания своего сборщика мусора.. который при каждом создании переменной будет заносить хеш- значение в упорядоченную таблицу и отслеживать все изменения в ней автоматически...
Можно было бы ввести на уровне языка составной тип вида "SET OF POINTER..." (динамического размера), как в Паскале и Модуле-2, но не только от ординальных типов, но и от ссылочных (они тоже элементарные). Проверка принадлежности элемента такому множеству и будет быстрым поиском объекта в коллекции по его ссылке. Тогда явной низкоуровневости не будет.
можно ... но что то не уверен я ... насчет Паскаля там максимальный размер множества (количество элементов) фиксирован... как и в Модуле2... но главное - ради чего это делать? ради изолированной задачи которая находится вне области оптимального использования языка?
-
если так рассуждать то можно дойти до написания своего сборщика мусора.. который при каждом создании переменной будет заносить хеш- значение в упорядоченную таблицу и отслеживать все изменения в ней автоматически...
Не уверен, что понял замысел. Зачем так сложно?
Если у нас стоит задача быстро проверить наличие данного ссылочного значения (а не значения объекта по ссылке) в некотором списке ссылок на объекты, или быстро определить место ссылочного значения в этом списке (как в моем примере с SearchPointerT), то совсем не нужно возиться с хеш-значениями от значений объектов и упорядочивать по ним данный список. Раз уж мы обращаемся к низкоуровневым средствам, то нужно пользоваться адресами объектов (их числовыми значениями) и список упорядочивать по ним. Ведь модуль SYSTEM в Оберонах есть, это средство языка!
В такой список заносятся ссылки не на все создаваемые объекты, а только на объекты, указанные пользователем. Тип такого списка должен быть определен в системном модуле, структура такого списка не должна быть видна вне системного модуля - ведь список упорядочен по адресам, внешний модуль может только включать и удалять ссылочные значения в/из него и осуществлять в нем поиск, да создавать и удалять сами списки. Переделывать сборщик мусора и среду исполнения не придется.
Или может мы говорим о разных задачах?
можно ... но что то не уверен я ... насчет Паскаля там максимальный размер множества (количество элементов) фиксирован... как и в Модуле2...
Да, фиксирован у каждого конкретного SET-типа, как и размер памяти под значение, независимо от фактического числа элементов. Я имел ввиду: как в Паскале и Модуле-2, только динамического размера.
но главное - ради чего это делать? ради изолированной задачи которая находится вне области оптимального использования языка?
Как альтернативу модулю SYSTEM, если наличие оного противоречит чьим-либо возвышенным представлениям о высокоуровневом языке. И может быть кто-то посчитает, что универсальный высокоуровневый язык обязан обеспечивать оптимальное решение в любой области задач (с точностью до постоянного множителя, или по крайней мере до логарифмического).
-
Ведь модуль SYSTEM в Оберонах есть, это средство языка!
В обсуждаемом языке (см. топик) SYSTEM является опциональным, не обязательным. В конкретной реализации его может и не быть.
-
Ведь модуль SYSTEM в Оберонах есть, это средство языка!
В обсуждаемом языке (см. топик) SYSTEM является опциональным, не обязательным. В конкретной реализации его может и не быть.
Тогда, без модуля SYSTEM, упорядочение ссылок в O7/O11 невозможно, если только пользователь не контролирует исходный код и каждое размещение соответствующих динамических объектов.
Если контролирует, ему нужно добавить к типу объекта числовое поле, хранящее персональный номер объекта данного типа (скажем 128-битный, чтобы исключить переполнение), который дается объекту (по счетчику) сразу после его размещения процедурой NEW и в дальнейшем не меняется. А счетчик после каждого размещения увеличивается на единицу. Выданные номера однозначно соответствуют адресам объектов, для доступных объектов и адресов это соответствие взаимно-однозначно - это упорядочение адресов. По этим номерам можно проводить быстрый поиск в списке или упорядоченном массиве ссылок. Хэш-значения здесь не нужны.
Если пользователь не контролирует исходный код объектов, то он не может дать путь от объекта к его персональному номеру, хэш-значению, или непосредственно номеру в списке(-ах) поиска. Даже если он контролирует каждое изменение этих объектов на месте обновляя их хэш-значения (что само по себе м.б. очень затратно), приязать к объекту он эти хэш-значения не сможет (хэш-значения для объектов из списка поиска придется хранить в самом списке). Значит, как тут заметили, ему придется сначала перевычислять хэш-значения всех объектов из списка поиска перед (в общем случае) каждым "быстрым" поиском объекта в списке, а это уже полный перебор списка (а после поиска еще перебирать объекты с одинаковым значением).
Только если поиск ведется много раз подряд, пока объекты из списка не изменяются, то использование упорядочения объектов по их значению (либо хэш-значению) дает в среднем увеличение скорости поиска. В противном случае, хэш-функции здесь бесполезны и быстый (логарифмический) поиск ссылки в списке невозможен.
-
Как альтернативу модулю SYSTEM, если наличие оного противоречит чьим-либо возвышенным представлениям о высокоуровневом языке. И может быть кто-то посчитает, что универсальный высокоуровневый язык обязан обеспечивать оптимальное решение в любой области задач (с точностью до постоянного множителя, или по крайней мере до логарифмического).
фичивание языка on demand? - проходили.. (object pascal, js, php).
-
Тогда, без модуля SYSTEM, упорядочение ссылок в O7/O11 невозможно, если только пользователь не контролирует исходный код и каждое размещение соответствующих динамических объектов....
пришли к началу....
-
фичивание языка on demand? - проходили.. (object pascal, js, php).
Зачем "по требованию"? Введения динамических множеств (динамических упорядоченных массивов) от ссылок будет достаточно для ассимптотической оптимальности (в сравнении с машкодами) таких расширенных Паскаля-Модулы-Оберонов на любых задачах. Причем на любых данных, а не только специально сконструированных. Не представляю, какие могут быть задачи, скорость которых можно качественно увеличить новыми фичами языка.
Тогда, без модуля SYSTEM, упорядочение ссылок в O7/O11 невозможно, если только пользователь не контролирует исходный код и каждое размещение соответствующих динамических объектов....
пришли к началу....
Вопрос в том, нужен ли вообще такой язык, чтобы он оптимально работал на любых данных? Или пользователю можно позволить создавать данные неоптимальные для некоторых задач?
Например, в Аде можно создать (?) статический перечислимый тип без отношений порядка, массивы и списки из данных такого типа будут принципиально неупорядочиваемы, и по ним принципиально невозможно будет проводить быстрый поиск. Нужно запретить такой тип данных?
Хэш-функцию тоже не всегда можно вычислять от объектов даже в Паскале-Модуле-Оберонах, например если объект имеет только ссылочные поля, и его "значение" задается только его местом в топологической ссылочной сети (вычисление которого крайне неэффективно). Нужно запретить такие объекты либо разрешить упорядочение ссылок?
Упорядоченные ссылки, это по сути обычный перечислимый тип только с динамически изменяемым диапазоном значений и без встроенных функций succ, prev, ord, а совокупность объектов этого типа есть неявный динамический массив от всех значений этого типа (ссылки редуцируются к индексам массива). С ними всегда можно организовать быстрый поиск объектов. Допустим/обязателен такой тип ссылок?
Инкапсуляция данных вообще вредит эффективности работы с ними внешним пользователям. Инкапсуляция недопустима?
Каким должен быть правильный язык?
Если обеспечивать оптимальность только для специально сконструированных данных, то здесь исходных Паскаля-Модулы-Оберонов уже достаточно для любых задач. Ссылки можно упорядочить с помощью поля персонального номера объекта, для тех типов ссылок, где такой номер есть. Допустимо такое ограничение оптимальности для правильного языка?
-
Зачем "по требованию"? Введения динамических множеств (динамических упорядоченных массивов) от ссылок будет достаточно для ассимптотической оптимальности (в сравнении с машкодами) таких расширенных Паскаля-Модулы-Оберонов на любых задачах. Причем на любых данных, а не только специально сконструированных. Не представляю, какие могут быть задачи, скорость которых можно качественно увеличить новыми фичами языка.
это нарицательное название такого рода включений - когда предлагается фичивать язык в угоду решения одной задачи...
Вопрос в том, нужен ли вообще такой язык, чтобы он оптимально работал на любых данных? Или пользователю можно позволить создавать данные неоптимальные для некоторых задач?
ошибаетесь - вопрос был другой.. посмотрите топик... касаемо второй части псевдовопроса.. пользователю разрешено ровно то , что не запрещено - и он этим пользуется с различной степенью эффективности (наглядности) на свою задницу.