?

Log in

No account? Create an account
мимоходом - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

мимоходом [ноя. 21, 2006|01:20 pm]
Anatoly Vorobey

(только для программистов)

Мой парсер Perl6 понимает теперь любые операторы, включая все виды скобок итд. Следующий шаг - написать макросы для контрольных структур, объявлений переменных, и самое главное макро "{". Откладываю это, потому что понял, что моя схема обработки переменных отлично подходит для динамических переменных, но не работает с лексическими - точнее, парсеру-то в принципе все равно, но (гипотетическому) компилятору мало информации.

Последние пару дней над этим думаю. Мучительно медленно выкристаллизовывается понимание того, как надо воплощать лексические переменные и closures. Особенно с closures красиво получается, загляденье. Но некоторые важные аспекты остаются непонятыми. Если додумаю это до конца, может, мой парсер плавно перетечет в компилятор, в конце концов...

СсылкаОтветить

Comments:
[User Picture]From: mxposed
2006-11-21 12:10 pm
а вы где вообще все это делаете?

я тут просто пишу плагин к idea (jetbrains.com) - для языка - те же в общем задачи про лексер парсер и дальнейшее
(Ответить) (Thread)
[User Picture]From: avva
2006-11-21 02:35 pm
Пока это во внутренней repository, когда оно начнет что-то нетривиальное делать, я его либо вставлю в качестве под-проекта в pugs, либо отдельным проектом выложу для svn-доступа.
(Ответить) (Parent) (Thread)
[User Picture]From: avnik
2006-11-21 12:44 pm
А на чем все это пишется если не секрет?
(Ответить) (Thread)
[User Picture]From: avva
2006-11-21 02:22 pm
На Common Lisp.
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 01:18 pm
> Мучительно медленно выкристаллизовывается понимание того, как надо воплощать лексические переменные и closures.

а что именно вызывает мучения?

(про это всё, в принципе, в книжках разных пишут, да и вообще не бином-ньютон.  вот я и спрашиваю — видимо в Perl 6 приходится делать что-то особенно, мнээ, интересное?).
(Ответить) (Thread)
[User Picture]From: avva
2006-11-21 03:59 pm
Может, это я просто такой тупой.

Есть некоторые осложнения, да, связанные в частности с тем, что в Perl6 я могу в рантайме обращаться напрямую к лексическим переменным конкретного лексического блока, например $MY::foo или $OUTER::bar. Поэтому когда я закрываю блок, создавая из него closure, я не могу просто взять все значения всех лексических переменных, что он видит (кроме его собственных), и поместить их в какую-нибудь хэш-таблицу по имени. Мне нужно сохранить структуру.
Это означает также, что я не могу делать deep binding в обычном смысле этого слова. Shallow binding для лексических переменных делать тоже как-то неудобно получается (для динамических, package-level, он вроде бы вполе подходит тут).

Если назвать pad'ом хэш-таблицу, которая для каждого блока связывает имена его локальных переменных с их значениями, то заход в каждый блок связан с созданием нового pad'а для него. Если блок хочет обратиться к лексической переменной $bar, которая определена в окружающем его лексическом блоке, а не в нем самом, ему нужно как-то найти pad того блока, причем правильный pad - их может быть много (напр. если окружающий блок вызывал себя рекурсивно). Та схема, к которой я пока что пришел, выглядит так: стэк пэдов, который изменяется динамически, но имеет лексическое значение, т.е. каждый следующий уровень в нем соответствует следующему вложенному лексическому блоку, а значение на этом уровне указывает на конкретный пэд этого блока, в котором сейчас происходит execution. Обращение к лексической переменной одного из окружающих блоков записано в коде данного блока (компилятором) как что-то вроде "уровень -3 от моего, имя '$x'", и в рантайме это переводится в реальный пэд согласно стэку, и находится реальное значение. Вход в новый лексический блок (например, как часть выполнения if или for) выглядит как добавление нового пэда в стэк. Рекурсивный вызов функцией самой себя выглядит в этой схеме как временная (на время вызова) замена последнего значения в стэке на новый созданный пэд для того же блока. Создание closure выглядит так: все лексические переменные, которые блок в принципе может запросить, собираются из всех пэдов в стэке, как он сейчас выглядит, их значения клонируются и сохраняются в "фантомном" стэке, который прикрепляется к closure, и который отныне используется для доступа к этим переменным, когда код closure вызывается. Вызов функции, определенной в другом месте, выглядит так: на время откладываем наш стэк полностью в сторону и заменяем его стэком для лексического контекста той функции.

Есть еще всякие сложности, связанные с тем, что я не до конца понимаю все тонкости этих операций, а кроме того, не очень понимаю, что делать в случае, когда вызывается функция, находящаяся где-то лексически глубоко внутри, без того, чтобы окружающие ее лексические блоки вообще когда-либо создавали свои пэды. Например:
sub foo() { my $x=5; sub bar() { $x; } }
bar()
Ясно, что bar() не может увидеть 5 как значение своего обращения к $x, но непонятно, как (в моей схеме) она вообще может это обращение как-либо разрешить, у нее нет никакой информации о пэдах окружающего ее блока.
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 04:18 pm
гхм, ну да, тут явно никуда не денешься от необходимости подвязывать весь стэк local lexical environments (стандартное название для того что ты называешь "pad", только длинное) к каждому замыканию.  молодцы ребята, way to preclude optimizations.

а вот тут я не уловил:
sub foo() { my $x=5; sub bar() { $x; } }
bar()

а как ты вообще видишь bar, если ты не внутри foo?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 04:27 pm
Насчет оптимизации: мне кажется, оптимизация эта конкретная грошовая, а у возможности посмотреть на лексические переменные выше тебя explicitly есть есть свои достоинства.

Насчет bar. sub bar - то же, что our sub bar, т.е. имя функции является переменной package-level, но лексически видима она действительно только внутри блока. Однако вызов функции с неизвестным науке именем компилируется как provisional call, который может разрешиться в конце процесса компиляции данного файла. Это позволяет например из func1() вызвать func2() до определения func2().

Короче говоря, в момент компиляции bar() компилятор не знает, что это за функция bar(), но позволяет, а после того как весь файл окончен, он для всех таких provisional вызовов проверяет,есть ли такая фунцкия, и в случае bar находит ее on package level.

Если бы я написал my sub bar() {...}, оно бы действительно было невидимо. Или если бы я написал &bar(), то это было бы обращение к лексически видимой переменной &bar (а не специальный случай bareword function call), и не скомпилировалось бы, потому что лексически видимой переменной &bar в этом месте нет. Если бы я написал &Main::bar, то наоборот бы сработало, потому что доступ к динамической переменной package'a, которая таки есть.
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 04:40 pm
> оптимизация эта конкретная грошовая

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

> Если бы я написал my sub bar() {...}, оно бы действительно было невидимо.

ага, вспомнил, спасибо.  то есть, в твоём примере bar — это примерный аналог такой вот фигни на CL:
(defun foo ()
  (let ((x 5))
    (defun bar ()
      x)))

до первого вызова foo вызов bar работать в принципе не может, а потом это нормальненькое такое замыкание.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 05:32 pm
Дело в том, что другие средства языка и так мешают пользоваться для хранения лексических переменных нормальным стэком, т.е. забыть про их имена. В частности, у функций есть named parameters, и аргументы, к ним подходящие, можно создавать в рантайме в качестве пар или из хэша. Например:

sub foo ($arg1, $arg2, :$something) {...}

foo(3, 5, something => $value);
foo(:something($value), 3, 5); 
foo 3, 5, :something($value) ;

my %hash; my $name = "something"; %hash{$name} = $value;
foo 3, 5, |%hash;

Все эти примеры передают функции foo одно и то же, и внутри foo значение именного аргумента видно как переменная $something. Последний пример показывает, что при компиляции foo невозможно выбросить слово 'something' в обращении $something, заменив его смещением стэка.

В принципе есть еще и доступ низкого уровня прямо к моему пэду как к перловскому хэшу: ::{'$anyname'}, но этим можно было бы еще пожертвовать, а именные аргументы оказались важными.

Твоя аналогия из Лиспа почти верна, потому что в моем примере sub bar работает во время компиляции (sub - макро, парсирующее и определяющее функцию), поэтому не нужно ни одного вызова к foo(), чтобы иметь возможность начать вызывать bar().
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 06:47 pm
> в моем примере sub bar работает во время компиляции (sub - макро, парсирующее и определяющее функцию), поэтому не нужно ни одного вызова к foo(), чтобы иметь возможность начать вызывать bar().

так что тогда bar видит?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 06:53 pm
В моей новой схеме - прото-пэд foo, в котором у $x нет значения (потому что инициализация происходит в рантайме), т.е. undef.
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 07:15 pm
это так по спецификации надо, или просто тебе удобно?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 07:30 pm
Спецификация is vague on this point. Я не вижу реальной возможности для bar увидеть значение, которое назначается $x в рантаймном куске, который никогда не выполнялся! Проблема для меня была не в том, будет это 5 или undef - я не могу себе представить, как это может быть 5 - а в том, как вообще bar может хоть что-то увидеть на месте $x, если не выполнялся блок, который создает пэд для x. Наличие прото-пэдов, созданных во время компиляции, эту проблему, видимо, решает.
(Ответить) (Parent) (Thread)
[User Picture]From: cmm
2006-11-21 07:41 pm

Re: Reply to your comment...

уточню вопрос: согласно спецификации, определение bar является статическим и обязано быть произведено во время компиляции, или необязательно?

(я таки совершенно забыл Перл, извини если вопрос идиоцкий.)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 07:44 pm

Re: Reply to your comment...

Теперь понял. Определение bar обязано быть произведено во время компиляции, да.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2006-11-21 05:25 pm
Не скомпилируется - конфликт во время определения второй bar(). Она на самом деле функция уровня package-or-file, тот факт, что она определяется внутри блока foo только ограничивает ее распознаваемость парсером, когда она написана как &bar() или bar(). Но если бы оба определения были my sub bar..., то обе функции действительно были бы вложены в блок foo, и попытка вызова снаружи провалилась бы.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 06:01 pm
На самом деле, сидя сейчас в кресле зубного врача, я понял внезапно, что моя схема все равно неверна. Я не могу просто скопировать стэк пэдов в качестве фантомного сохраненного стэка для closure, и все. Я не подумал о том, что при последующих вызовах closure может внутри себя делать сколь угодно сложные вещи, в том числе заходить в новые внутренние блоки, делать в них новые closures итд. - все те операции, которые у меня в "обычнном" варианте происходят с глобальным рантаймным стэком пэдов, но в этом случае должны происходить с ним только до уровня N, а дальше переключаться на фантомную сохраненную версию.

Поэтому вот новая версия. Нет глобального рантаймного стэка, просто каждый пэд держит рантаймную ссылку на окружающий его лексически и верный динамически пэд, ссылка называется ::OUTER. Предположим, блок хочет обратиться к лексической переменной $foo, про которую компилятор написал "на -3 лексическом уровне от меня". Значит, он три раза прыгает сквозь ::OUTER, и в полученном пэде ищет '$foo'. (eventually это можно соптимизировать в массив пэдов, который строится на входе в блок, с доступом О(1); сейчас это было бы явной premature optimisation).
Далее, при входе во внутренний блок в процессе обычной работы (как часть for, скажем), происходит создание нового пэда для внутреннего блока, установление в нем ::OUTER на пэд текущего блока, и смена текущего блока. При рекурсивном вызове foo() самой себя происходит создание нового пэда для foo с копированием для него ::OUTER из ::OUTER текущего пэда. При создании closure происходит создание фантомных пэдов для всех уровней над блоком, туда клонируются значения всех переменных, к которым в принципе когда-либо обращается текущий блок, и ::OUTER текущего блока переставляется в фантомный пэд окружающего блока.

С вызовом функции откуда-то из другого места, причем это место находится не на нулевом лексическом уровне, дела обстоят сложно, но пока я придумал вот что. У каждого блока есть прото-пэд, который строится во время компиляции. Туда, в частности, идут те значения переменных, которые известны во время компиляции. Например, если я напишу my $x; print $x; BEGIN { $x = 5; }, то оно должно в рантайме напечатать 5 - по сути дела в пэде должно стоять 5 как значение ключа '$x' уже при входе в блок. Во время компиляции ::OUTER прото-пэда указывает на прото-пэд окружающего блока.

Если я вызываю функцию откуда-то издалека, например из другого модуля, то при создании ее пэда ::OUTER просто не меняется, и продолжает указывать на цепочку прото-пэдов верхних от нее уровней. Функционально это такие же пэды, как обычные, их можно копировать для создания closure итд., но значения в них есть только те, что известны во время компиляции. Это позволяет работать, скажем,
package Foo;

my $x = 100;
sub foo() { $x+5; }

use Foo;
foo();

потому что use весь происходит в compile-time, и $x=1 войдет в прото-пэд над foo.

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

my $x=5;
sub bar() {
...
}

sub foo() {
  ...
  if 1 {
    if 1 {
      if 1 {
        something {
           something {
                sub baz { ...}
           }
        }
        if 1 {
          bar();
          baz();
        }
}}}}}

Когда внутри foo() происходит вызовы bar() и baz(), видят ли эти функции значение $x==1 в том пэде, который находится выше всех этих функций и foo? Если они должны его видеть, совершенно непонятно, как это устроить.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: cmm
2006-11-21 07:14 pm
> в лиспе, кстати, именно так и делается (там нет стека).

в очень древних реализациях очень древних спецификаций.

как-то последнее время (лет двадцать) народ более или менее утвердился во мнении, что линейный стэк — это есть хорошо.  и для реализации проще, и мусора меньше по ходу исполнения программы производится, и процессоры современные линейный стэк и завязанные на него него пары инструкций типа call/return страсть как уважают...
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: cmm
2006-11-21 10:35 pm

Re: Reply to your comment...

я думал, Вы говорите о реализации языка как такового и лексического привязывания в частности.
понятно, что для замыканий надобно копировать нужные куски состояния.
я недопонял, видимо, извините.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-11-21 07:21 pm
Это примерно то, что я написал. Но вы, кажется, путаете два вида "parent" - динамический и лексический. При вызове функции ее динамический предок, та функция, что ее вызвала, не имеет отношения к правилам видимости лексических переменных для вызванной функции.
(Ответить) (Parent) (Thread)
[User Picture]From: madfire
2006-11-22 12:36 pm
Про OUTER напомнило вот это.

Довольно интересный язык получается, тока компилятора к нему нет похоже.
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2006-11-21 01:26 pm
А что такое лексические переменные? dynamic binding?
(Ответить) (Thread)
[User Picture]From: avva
2006-11-21 02:27 pm
В Перле: my $x;
в Лиспе: (let (varname) ... )

Переменные, которые:

1) Видны только в лексическом после своего определения (и если не закрыты более внутренним определением с тем же именем)
2) Создают новую копию каждый раз при входе в блок, в котором они определены;
3) В случае, когда более внутренний блок закрывается для дальнейшего использования в качестве объекта (в том числе вызова когда-то в будущем), этот внутренний блок получает их копии в момент своего закрытия, и впоследствии использует скопированные значения.
(Ответить) (Parent) (Thread)
[User Picture]From: lance10t
2006-11-21 11:12 pm

можент быть вас спрашивали уже,

а зачем вы это делаете? =).
(Ответить) (Thread)