Автор Тема: [Oberon7] "Man or Boy test" by Donald Knuth  (Прочитано 46900 раз)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #75 : Июль 11, 2013, 09:52:43 am »
Кстати, Свердлов в своей книге упоминает о 16-проходном компиляторе (один из ранних). Неужели там использовалось 16 различных представлений одной и той же программы?  :)  Хотя, нет конечно. Вот там действительно по каждому из представлений делалось по несколько проходов. Памяти не хватало даже на то, чтобы хранить код самого компилятора, загружался и выполнялся по частям.

Вот воспомминания об одном из первых трансляторов расширенного Алгола-60, первого сильно-оптимизирующего транслятора в мире:

"ИСТОРИЯ АЛЬФА-ПРОЕКТА" проф. И. В. Поттосин

Цитировать
Общая структура транслятора состоит из четырех этапов: получение промежуточного представления, превращение его во внутренний язык и оптимизации на внутреннем языке построение машинных команд, экономия памяти и формирование машинной программы. Все эти этапы разбивались на блоки. Разбиение определялось как функциональными действиями, так и необходимостью «вписаться» в малую (4К  45-разрядных слов) память компьютера.

Окончательная структура блоков такова:

 Ввод и первичный синтаксический контроль (блок 1) разработчик и реализатор — Загацкий.
 Обработка описаний (блок 2) — Кожухин.
 Завершение идентификации (блок 3) — Бабецкий.
 Декомпозиция выражений (блоки 4 и 5), разработчик — Кожухин, реализатор — Кожухина.
 Анализ и программирование процедур (блоки б и 7) — Загацкий.
 Перевод из промежуточного представления во внутренний язык (блок 8) — Ершов.
 Обработка геометрических операций над массивами и реализация действий с многомерными массивами (блоки 9, 10) — Волошин.
 Анализ и чистка циклов (блоки 11-13) — Бежанова (при участии в разработке Поттосина).
 Экономия выражений (блок 14) — Поттосин.
 Построение машинных команд (блок 15) — Кожухина (при участии в разработке Бабецкого).
 Программирование индекс-регистров и циклов (блоки 16-18) — разработчик Поттосин, реализатор Кожухина.
 Экономия констант (блок 19) — Змиевская (при участии в разработке Ершова).
 Построение операторной схемы и графа несовместимости (блоки 20, 21) — Мишкович (при участии в разработке Ершова).
 Распределение памяти (блок 22) — Трохан (при участии в разработке Ершова).
 Чистка и компоновка программы (блоки 23, 24) — Трохан, Змиевская.

Потом они портировали этот транслятор с М-20 на БЭСМ-6 и сильно упростили, уменьшив количество проходов в два раза...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

ddn

  • Jr. Member
  • **
  • Сообщений: 59
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #76 : Июль 12, 2013, 05:24:47 am »
Я понимаю там в хаскелле/сишарпе forward declarations не нужны -- весь модуль/класс просматривается при поиске нужной процедуры, переменной или типа , но в обероне...
Жестокое упрощение языка...
Дык лишняя сущность же!

Ну, на самом деле, если ослабить вот это требование: "The scope extends textually from the point of the declaration to the end of the block (procedure or module) to which the declaration belongs and hence to which the object is local." до "whole block (procedure or module)", то получится язык поприятнее для кодописателя (и чуть менее приятный для компилятороклепателя, хотя и тут выигрыш таки в итоге будет, ибо компилятор железно перестает быть однопроходным).
Даже если этого не делать, не следует по крайней мере разрешать видимость в процедуре внешнего к ней идентификатора, до того места где внутри процедуры будет (если будет) объявлен локальный идентификатор с тем же именем. Все идентификаторы внешние к процедуре следует импортировать в процедуру явно, возможно по псевдониму, и объявлений в процедуре идентификаторов с теми же именами/псевдонимами быть не должно. Хотя такой импорт расширяет синтаксис.


Да? А как? Вот у меня процедура Foo, которая использует другую процедуру которая определена где-то далеко внизу. Вопрос - как за один проход такое компилировать?
Никак. Просто потому, что в общем случае нельзя "угадать" сигнатуру - оберон допускает неявные преобразования типов аргументов. Например f('A') может быть как вызовом "PROCEDURE f(c: CHAR)" так и "PROCEDURE f(s: ARRAY OF CHAR)". Кроме того, передача VAR-аргументов тоже влияет на генерируемый код в точке вызова.
Неуверен, что невозможность без заглядывания вперед "угадать" сигнатуру вызываемой процедуры влечет невозможность генерировать готовый код такого вызова. Для ссылочных типов это получается.

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

Начиная с версии 2011 литералы литер (тип CHAR) и строк (тип Srtring) проходят одним нетерминалом и задаются через литерные цепочки только с двойными кавычками либо через число с суффиксом "X". Но неясно, можно ли однолитерные литерные цепочки использовать как литеры.
В версии 07 литералы литер, помимо числа с суффиксом "X", задаются через литерные цепочки с одинарными кавычками (в переводе Бурцева в репорте написано: CharConst = """ character """ | digit {hexDigit} "X", но примеры идут: 'A' '%' 22X), но строковые литералы задаются через литерные цепочки и с двойными кавычками и с одинарными. В версии 1 литералы и литер и строк могут задаваться литерными цепочками только с двойными кавычками (в репорте для литер нет примеров).

Есть и другой пример невозможности угадать сигнатуру без заглядывания вперед, если идентификаторы видны всюду в блоке, а не только впереди от точки своего объявления.
Фактический параметр может быть не только литералом неясного типа, тип которого требуется уточнять типом формального параметра, но и объектом, чей тип объявлен позже чем сделано обращение к объекту. Поскольку, вызов процедуры "f", происходящий когда обработаны еще не все декларативные области модуля (включая локальные), возможен только внутри другой процедуры "h", т.е. локально, и поскольку после такого вызова далее объявляются лишь процедуры (внешние по отношению к "h"), указанный пример возможен, если фактический параметр есть идентификатор некоторой нелокальной процедуры "g" или вычисляется на основе таких процедур.
То есть, если в теле некоторой процедуры "h" идет вызов "f(g)" или например "f(g(0)+g(1))" некоторой процедуры "PROCEDURE f(a: T)", где процедуры "f" и "g" объявлены после точки этого вызова, то в этой точке тоже невозможно угадать сигнатуру "f" без заглядывания вперед.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #77 : Июль 12, 2013, 03:32:51 pm »
Даже если этого не делать, не следует по крайней мере разрешать видимость в процедуре внешнего к ней идентификатора, до того места где внутри процедуры будет (если будет) объявлен локальный идентификатор с тем же именем. Все идентификаторы внешние к процедуре следует импортировать в процедуру явно, возможно по псевдониму, и объявлений в процедуре идентификаторов с теми же именами/псевдонимами быть не должно. Хотя такой импорт расширяет синтаксис.

Это оверкилл. Не пишите процедур на 1000 строк и не заводите кучу глобальных переменных - и будет вам счастье. Хотя если как средство отбить желание заводить глобальные переменные...

Неуверен, что невозможность без заглядывания вперед "угадать" сигнатуру вызываемой процедуры влечет невозможность генерировать готовый код такого вызова. Для ссылочных типов это получается.
...
То есть, если в теле некоторой процедуры "h" идет вызов "f(g)" или например "f(g(0)+g(1))" некоторой процедуры "PROCEDURE f(a: T)", где процедуры "f" и "g" объявлены после точки этого вызова, то в этой точке тоже невозможно угадать сигнатуру "f" без заглядывания вперед.

Взаимоисключающие параграфы детектед.

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

ddn

  • Jr. Member
  • **
  • Сообщений: 59
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #78 : Июль 12, 2013, 06:44:26 pm »
Это оверкилл. Не пишите процедур на 1000 строк и не заводите кучу глобальных переменных - и будет вам счастье.
Если во всех вызовах параметр-переменная ссылается на один и тот же объект/подобъект и даже обязана ссылаться по логике задачи, что плохого если она импортируется один раз при декларации процедуры, а не много раз как фактический параметр.
Что значит кучу, больше 10, больше 100? Если запрещать в процедурах внешние переменные (не как параметры), то совсем.
Хотя если как средство отбить желание заводить глобальные переменные...
Это средство запретить использовать разные объекты под одним именем в одном блоке (за вычетом подблоков), область видимости блока должна быть однородной. Поэтому оператор FOR тоже нужно запретить, он тоже делает область видимости блока неоднородной, можно оформить FOR как спецконструктор процедур со своими областями видимости.

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


Неуверен, что невозможность без заглядывания вперед "угадать" сигнатуру вызываемой процедуры влечет невозможность генерировать готовый код такого вызова. Для ссылочных типов это получается.
...
То есть, если в теле некоторой процедуры "h" идет вызов "f(g)" или например "f(g(0)+g(1))" некоторой процедуры "PROCEDURE f(a: T)", где процедуры "f" и "g" объявлены после точки этого вызова, то в этой точке тоже невозможно угадать сигнатуру "f" без заглядывания вперед.
Взаимоисключающие параграфы детектед.
Во втором процитированном предложении я утверждаю, что если локальные идентификаторы процедуры/модуля видимы в ней всюду (в декларативной и операторной области) т.е. их можно использовать до точки объявления, то без заглядывания вперед будет невозможно в общем случае угадать сигнатуру вызываемой процедуры.
В первом предложении я лишь высказываю сомнение в том, что "если невозможно угадать сигнатуру вызываемой процедуры, то из этого следует невозможность сгенерировать готовый код такого вызова".
Что здесь взаимоисключающего?

То есть, я высказал сомнение в том что из видимости локальных идентификаторов всюду в процедуре/модуле следует в общем случае невозможность сгенерировать готовый код вызова процедур без заглядывания вперед (невозможность однопроходного компилятора). Однопроходность скорее свойство компилятора чем языка. Конечно, при видимости идентификаторов до точки объявления однопроходный компилятор будет сложнее, а генерируемый им код неоптимальнее, но компилятор будет.
« Последнее редактирование: Июль 12, 2013, 06:46:46 pm от ddn »

maliya

  • Newbie
  • *
  • Сообщений: 12
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #79 : Июль 24, 2013, 06:52:48 pm »
hi,I have done some work to make bb can work with this example.

so far, I don't think the closure is useful in bb programing, just do a half work only.

does we need this feature to built  in compiler?

 



   

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #80 : Июль 24, 2013, 07:49:23 pm »
hi,I have done some work to make bb can work with this example.

Wow! SYSTEM and a little bit of machine codes :) Still it traps on my BB 1.6-rc6...

so far, I don't think the closure is useful in bb programing, just do a half work only.

does we need this feature to built  in compiler?

Do you know how to do it (with GC awareness and so on)?

P.S. Yes, I think a modern general purpose language with GC must have a feature like full fledged closures.

maliya

  • Newbie
  • *
  • Сообщений: 12
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #81 : Июль 25, 2013, 02:28:33 am »
Цитировать
Still IT traps on My BB 1.6-rc6 ...

it needs to make some changes of compiler, I say  it's half work,only a draft.
if it needed, can continue change compiler to let original example compiled and work without any change.
It is only a local procedure be packed as a normal procedure, not a true closure.

for my little knownledge of closure reason,I dont known what syntax should be add to cp if we want it.

closure reference, example and suggestion is welcome!

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #82 : Июль 25, 2013, 06:57:32 am »
Про синтаксис я не понял -- у замыканий синтаксис такой же как у обычной процедуры. Может быть maliya имел в виду лямбды?
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

DddIzer

  • Гость
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #83 : Июль 25, 2013, 07:56:32 am »
Про синтаксис я не понял -- у замыканий синтаксис такой же как у обычной процедуры. Может быть maliya имел в виду лямбды?
да нет, как вы поймете по существующему синтаксису в каком случае нужно сохранять локальный контент процедуры, в  каком нет?

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #84 : Июль 25, 2013, 09:41:21 am »
Про синтаксис я не понял -- у замыканий синтаксис такой же как у обычной процедуры. Может быть maliya имел в виду лямбды?
да нет, как вы поймете по существующему синтаксису в каком случае нужно сохранять локальный контент процедуры, в  каком нет?
Так его сохранять нужно в любом случае. Если Вы передадите куда-то процедуру, имеющую доступ к какому-то внешнему для неё контексту, то что случится, если этот контекст не будет сохранён? Crash boom bang -- вот что случится...

Если обращается процедура к внешним переменным -- значит эти переменные должны быть сохранены в её контексте. И синтаксис тут ни при чём...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #85 : Июль 25, 2013, 09:55:47 am »
Про синтаксис я не понял -- у замыканий синтаксис такой же как у обычной процедуры. Может быть maliya имел в виду лямбды?
При чем тут синтаксис? Имелась ввиду естественно семантика замыкания контекста. Лямбды тут вообще не в тему.
Y = λf.(λx.f (x x)) (λx.f (x x))

DddIzer

  • Гость
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #86 : Июль 25, 2013, 10:17:06 am »
Про синтаксис я не понял -- у замыканий синтаксис такой же как у обычной процедуры. Может быть maliya имел в виду лямбды?
да нет, как вы поймете по существующему синтаксису в каком случае нужно сохранять локальный контент процедуры, в  каком нет?
Так его сохранять нужно в любом случае. Если Вы передадите куда-то процедуру, имеющую доступ к какому-то внешнему для неё контексту, то что случится, если этот контекст не будет сохранён? Crash boom bang -- вот что случится...

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

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #87 : Июль 25, 2013, 11:32:50 am »
смотрите внимательно - я говорил о  сохранении локального контента (на который она замыкается) между вызовами.

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

Для замыканий не нужны статические переменные процедур:
http://ru.wikipedia.org/wiki/Замыкание_(программирование)
Цитировать
Замыкание (англ. closure) в программировании — функция, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции и не в качестве её параметров (а в окружающем коде). Говоря другим языком, замыкание — функция, которая ссылается на свободные переменные в своём контексте.
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

DddIzer

  • Гость
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #88 : Июль 25, 2013, 11:52:46 am »
А какой такой локальный контент, сохраняемый между вызовами, может быть у процедуры в обероне? Статические переменные как в сях? Так их же не было никогда в паскалях...
тот  который я  хочу сохранить (по каким причинам, для простоты, неважно) - в самом простом случае я хочу сохранить переменную (ее содержимое) лексически связанную с функцией. Почти как в сях (есть нюансы). Ну и что , в делфях есть.
Цитировать
Для замыканий не нужны статические переменные процедур:
....
давайте договоримся какого эффекта мы хотим добиться их введением(как минимум, как максимум- для чего) а уж с помощью чего добиваться этого дело пятое-десятое.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: [Oberon7] "Man or Boy test" by Donald Knuth
« Ответ #89 : Июль 25, 2013, 04:32:49 pm »
It is only a local procedure be packed as a normal procedure, not a true closure.

I don't think it worth efforts to do it in this way. I'd like to have true closures, not something I can use only with SYSTEM. This particular task can be resolved without closures supported by language (see my solution for O7).

No special syntax needed for CP to support closures. It just semantic change - you can pass and return a local function and this local function can refer to outer variables (including outer function variables).
But compiler will definitely demand some work - procedure variable cannot be just "address" any more, it became "address + pointer to context".

closure reference, example and suggestion is welcome!

You can see how closures work in JavaScript (there was example in this topic for discussed task).