Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 20 янв 2019, 15:11

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




Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
СообщениеДобавлено: 12 окт 2018, 18:00 
Не в сети

Сообщения: 335
О, вот что ещё нашлось в модуле Kernel. Того и гляди - и вариант готовый не нашёлся бы...
Код: "OBERON"
  1.  
  2. PtrType = RECORD v: S.PTR END; (* used for array of pointer *)
  3. Char8Type = RECORD v: SHORTCHAR END;
  4. Char16Type = RECORD v: CHAR END;
  5. Int8Type = RECORD v: BYTE END;
  6. Int16Type = RECORD v: SHORTINT END;
  7. Int32Type = RECORD v: INTEGER END;
  8. Int64Type = RECORD v: LONGINT END;
  9. BoolType = RECORD v: BOOLEAN END;
  10. SetType = RECORD v: SET END;
  11. Real32Type = RECORD v: SHORTREAL END;
  12. Real64Type = RECORD v: REAL END;
  13. ProcType = RECORD v: PROCEDURE END;
  14. UPtrType = RECORD v: INTEGER END;
  15.  


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 07 ноя 2018, 17:58 
Не в сети

Сообщения: 335
Благодаря переводу и осознанию исходников компилятора появился план реализации задуманного.

http://вече.программирование-по-русски.рф/viewtopic.php?f=2&t=27


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 15 ноя 2018, 20:06 
Не в сети

Сообщения: 335
Проект заморожен по экономическим причинам.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 01 дек 2018, 23:37 
Не в сети

Сообщения: 335
Иногда урываю время что-то поделать. Заодно расшифровываю код компилятора и перевожу на русский. Вот цитата из свеженького:
Код: "OBERON"
  1.  
  2. (** РазбериФактическиеПараметры делает следующее:
  3.   - парсит параметры
  4.   - проверяет совместимость типов
  5.   - генерирует код для передачи особых типов (таких, как строка и интерфейс) в виде параметров
  6.  
  7.   См. также ИмитируйРазборФактическихПараметровДля_itemfn
  8.   Параметры:
  9.   VAR фактПараметры = список факт параметров (каждый параметр - это узел в односвязном списке узлов, по полю link )
  10.   мы его строим
  11.   формПараметры - аналогично, список формальных параметров
  12.   VAR pre, lastp - список неявных действий при передаче строк или интерфейсов (он пополняется)
  13.   *)
  14. PROCEDURE РазбериФактическиеПараметры(VAR фактПараметры: НяФс.Node; формПараметры: НяФс.Object; VAR pre, lastp: НяФс.Node); (* <ActualParameters> *)
  15. VAR apar, last, newPar, iidPar, n: НяФс.Node;
  16. BEGIN
  17. фактПараметры := NIL; last := NIL;
  18. IF текЛксм # rparen THEN
  19. newPar := NIL; iidPar := NIL;
  20. LOOP РазбериВыражение(apar);
  21. IF формПараметры # NIL THEN
  22. IF (apar.typ.form = Pointer) & (формПараметры.typ.form = Comp) THEN НяД.ЯвиУзелРазыменованияПеременной(apar) END;
  23. НяД.ОбработайСовместимостьПоПараметрам(apar, формПараметры);
  24. IF (формПараметры.mode = Var) OR (формПараметры.vis = inPar) THEN НяД.СоздайASTНеявныхДействийПриПередачеСтрокиИлиИнтерфейса(apar, NIL, формПараметры, pre, lastp) END;
  25. НяД.ПриклейКСпискуСИзвестнымХвостомЕщёСписокСзади(фактПараметры, last, apar);
  26. IF ODD(формПараметры.sysflag DIV newBit) THEN newPar := apar
  27. ELSIF ODD(формПараметры.sysflag DIV iidBit) THEN iidPar := apar
  28. END;
  29. IF (newPar # NIL) & (iidPar # NIL) THEN НяД.CheckNewParamPair(newPar, iidPar) END;
  30. IF anchorVarPar & (формПараметры.mode = VarPar)
  31. OR (НяМ.allSysVal IN НяМ.options) (* source output: avoid double evaluation *)
  32. & ((формПараметры.mode = VarPar) & (формПараметры.typ.comp = Record) & ~формПараметры.typ.untagged
  33. OR (формПараметры.typ.comp = DynArr) & ~формПараметры.typ.untagged) THEN
  34. n := apar;
  35. WHILE n.class IN {Nfield, Nindex, Nguard} DO n := n.left END;
  36. IF (n.class = Nderef) & (n.subcl = 0) THEN
  37. IF n.left.class = Nguard THEN n := n.left END;
  38. НяД.CheckVarParBuffering(n.left, pre, lastp)
  39. END
  40. END;
  41. формПараметры := формПараметры.link
  42. ELSE Ош(64 (*больше параметров чем требуется*))
  43. END;
  44. IF текЛксм = comma THEN добудьЛксм
  45. ELSIF (lparen <= текЛксм) & (текЛксм <= ident) THEN Ош(comma)
  46. ELSE EXIT
  47. END
  48. END
  49. END;
  50. IF формПараметры # NIL THEN Ош(65 (*меньше параметров чем требуется*)) END
  51. END РазбериФактическиеПараметры;
  52.  

Не удаётся сделать задуманное без достаточно серьёзного дублирования кода, поскольку в компиляторе одна функция делает много вещей сразу.
Но уже многое сделано - завёл заглушку функции, которая будет называться ITEM, проверяю количество и типы формальных параметров, написал код, который
находит реализацию нужного преобразования для ITEM(x) в модуле Meta. Осталось только синтезировать вызов найденной процедуры, но тут утыкаемся в то, что парсинг, синтез дерева и вставка вспомогательного кода происходят одновременно, а у нас уже есть узел AST, представляющий параметр, и никакой парсинг не нужен. Сегодня сидел часа 4-5, но доделать сил и времени не хватило.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 03 дек 2018, 23:48 
Не в сети

Сообщения: 335
Ну, начало получаться. Вот как:
Код: "OBERON"
  1.  
  2. PROCEDURE Печ*(э:Meta.DynamicallyTypedPtr);
  3. BEGIN
  4. CASE э.тип OF
  5. | boolTyp : StdLog.String("Б");
  6. StdLog.Bool(Meta.DynamicallyTypedBOOLEANValue(э))
  7. | intTyp : StdLog.String("Ц");
  8. StdLog.Int(Meta.DynamicallyTypedINTEGERValue(э));
  9. ELSE StdLog.String("НЁХ")
  10. END
  11. END Печ;
  12.  
  13. ...
  14.  
  15. Печ(ITEM(ц)); StdLog.Ln;
  16. Печ(ITEM(б)); StdLog.Ln;
  17.  

Но костылей пришлось нагородить... Ужас!

Всё защищено ассертами и типобезопасно.
Код, который генерирует ITEM, не содержит никакой динамической диспетчеризации - тип выясняется во время компиляции.
Соответственно, если тип, хранимый внутри DynamicallyTyped, нам известен из каких-то высших соображений, то
мы можем напрямую получать его значение через DynamicallyTyped...Value и цена этому будет - один ASSERT.
Выборки метода из таблицы вирт. методов не производится.

Когда мы делали Яр, всё это было макросами и можно было вообще исключить вызов функции (а он стоит достаточно дорого).
Если бы в КП были Inline функции, то и в КП можно было бы добиться такого же результата - весь код преобразования
из конкретного типа в DynamicallyTyped и обратно был бы без единого вызова функции.

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

Код, как обычно, тут: https://gitlab.com/budden/nkp

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


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 04 дек 2018, 00:04 
Не в сети

Сообщения: 335
Соответственно, ITEM - не самоцель. Он нужен для того, чтобы можно было

  • создавать списки, массивы и таблицы с неоднородным содержимым так же изящно, как в лиспе, дельфи или JS
  • напечатать любой объект, отсюда можно делать REPL


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 04 дек 2018, 13:30 
Не в сети

Сообщения: 197
budden писал(а):
Ну, начало получаться. Вот как:
Код: "OBERON"
  1.  
  2. PROCEDURE Печ*(э:Meta.DynamicallyTypedPtr);
  3. BEGIN
  4. CASE э.тип OF
  5. | boolTyp : StdLog.String("Б");
  6. StdLog.Bool(Meta.DynamicallyTypedBOOLEANValue(э))
  7. | intTyp : StdLog.String("Ц");
  8. StdLog.Int(Meta.DynamicallyTypedINTEGERValue(э));
  9. ELSE StdLog.String("НЁХ")
  10. END
  11. END Печ;
  12.  
  13. ...
  14.  
  15. Печ(ITEM(ц)); StdLog.Ln;
  16. Печ(ITEM(б)); StdLog.Ln;
  17.  

Но костылей пришлось нагородить... Ужас!


Ужас-не ужас, но это не ad-hoc полиморфизм (aka перегруженные функции). Это ближе к полиморфизму наследования, только вместо наследования -- перечислимый тип по сути. Короче, это что-то вроде вариантной записи.

ad-hoc полиморфизм был бы, если бы было несколько определений одной и той же функции с разными типами параметров...


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 04 дек 2018, 14:09 
Не в сети

Сообщения: 335
Ну, дело сделано, можно теперь и про терминологию поговорить. Каким определением ad hoc полиморфизма ты пользуешься?


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 05 дек 2018, 07:09 
Не в сети

Сообщения: 197
budden писал(а):
Ну, дело сделано, можно теперь и про терминологию поговорить. Каким определением ad hoc полиморфизма ты пользуешься?
Я не оберонщик, поэтому не придумываю новых расшифровок для старых, давно известных терминов. Вот это определение (точнее, примеры в нём) вполне норм:
Код: "PASCAL"
program Adhoc;
 
function Add( x, y : Integer ) : Integer;
begin
Add := x + y
end;
 
function Add( s, t : String ) : String;
begin
Add := Concat( s, t )
end;
 
begin
Writeln(Add(1, 2));
Writeln(Add('Hello, ', 'World!'));
end.

Вообще, если обращаться к классике программирования, то всё это расписано у Луки Карделли "Cardelli, Luca; Wegner, Peter (December 1985). "On understanding types, data abstraction, and polymorphism"" (русский перевод)
Цитата:
1.3 Виды полиморфизма
Традиционные типизированные языки, например Паскаль, основаны на идее, что функции и процедуры, и, следовательно, их операнды имеют уникальный тип. Такие языки называются мономорфными (monomorphic), в том смысле, что каждая значение и переменная могут интерпретироваться как один и только один тип. Мономорфные языки программирования могут быть противопоставлены полиморфным (polymorphic) языкам, в которых некоторые значения и переменные могут иметь более одного типа. Полиморфные функции – это функции, чьи операнды (фактические параметры) могут иметь более одного типа. Полиморфные типы – это типы, операции над которыми применимы к значениям более чем одного типа.
Изображение
Рисунок 1. Варианты полиморфизма.

Straychey [67] неформально определил два главных типа полиморфизма.

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

Наша классификация полиморфизма (рисунок 1) развивает классификацию Strachey, вводя новую форму полиморфизма, полиморфизм включения (inclusion polymorphism), для моделирования подтипов и наследования. Параметрический полиморфизм и полиморфизм включения классифицированы как две главных подкатегории универсального полиморфизма, который противопоставлен не универсальному полиморфизму (перегрузке). Таким образом, рисунок 1, отражая точку зрения Strachey на полиморфизм, добавляет полиморфизм включения для моделирования объектно-ориентированного программирования.

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

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

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

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

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

3 + 4
3.0 + 4
3 + 4.0
3.0 + 4.0

Здесь перегрузочный полиморфизм оператора + можно объяснить одним из следующих способов:

§ Оператор + имеет 4 перегруженных варианта, по одному для каждой из четырех комбинаций типов аргументов.
§ Оператор + имеет 2 перегруженных варианта, соответствующих сложению целых и действительных чисел. Если один из аргументов – типа «целое число», а другой – типа «действительное», аргумент типа «целое» приводится к типу «действительное».
§ Оператор + определен только для сложения действительных чисел, и целые аргументы всегда будут приводиться к соответствующим значениям действительных чисел. В этом примере одно и то же выражение можно рассматривать как представляющее и перегрузку, и приведение типов, и как оба сразу, в зависимости от реализации.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 05 дек 2018, 08:55 
Не в сети

Сообщения: 197
Почти 30 лет назад для языка Хаскелл придумали теоретически обоснованный способ упорядоченного ad hoc полиморфизма и назвали это классами типов. С помощью классов типов можно реализовывать функции с одним и тем же именем для аргументов разных типов. Эти типы объявляются как принадлежащие некоему классу типов с определёнными для этого класса методами.
Например, числовые типы объединены в класс типов Num с операциями + - * (и ещё некоторыми), при этом целые числа дополнительно сгруппированны в класс Integral с операциями div mod и др., дробные числа -- в класс Fractional с операцией /...
Классы типов позволяют создавать экземпляры для типов, которые были неизвестны на момент создания этих классов, что отличает их от интерфейсов явы.

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

Забавный пример использования классов -- это вычисление чисел фибоначчи алгоритмом Госпера-Саламина (возведение матрицы (1 0) в степень n)

Определяем тип данных, внутри которого два целочисленных элемента:

data GS = GS Integer Integer

Указываем, что этот тип является числом, т. е. экземпляром класса типов Num, реализуем операцию умножения (по хорошему, следует определить все операции, для простоты примера определим только умножение):

instance Num GS where
GS a b * GS c d = GS (a*(c+d) + b*c) (a*c + b*d)

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

(^) :: (Num a, Integral b) => a -> b -> a

то есть она может возвести любое число (экземпляр класса Num) в степень от целого числа (экземпляр класса Integral).

Получаем такую функцию вычисления чисел Фибоначчи:

fib n = res where GS res _ = (GS 1 0) ^ n

PS. Напомню, что наивный рекурсивный алгоритм вычисления чисел Фибоначчи имеет экспоненциальную сложность расчётов, итеративный -- линейную, алгоритм Госпера-Саламина -- логарифмическую. Есть ещё способ вычисления приближённого значения с помощью формулы Бине тоже с логарифмической сложностью (ведь там тоже есть возведения в степень).


Последний раз редактировалось geniepro 07 дек 2018, 11:51, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу Пред.  1, 2, 3  След.

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


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Тех.поддержка phpBB