понедельник, 18 июня 2012 г.

Сказочные quote/unquote

Сколько инет не перерыла, сколько в своих мозгах не рылась, а алгоритм правильного написания quasiquote/unquote/unquote-splicing.. -- так и не нашла/не поняла. Смысл в том, что нужно написать не в стиле макросов/компилятора, а в стиле простого интерпретатора, применяя функции, написанные с помощью окружений, фреймов и еще какого-то безобразия)
В процессе изучения было уяснено 3 умные мысли:



1) Как только мы видим quasiquote -- применяем некоторую функцию, которая будет выполнять действия в зависимости от встретившихся нам quasiquote, unquote, unquote-splicing, и хранить глубину вложенности. При этом все бы было не так страшно, если бы не обработка списков вида: `(1 2 3 (5 6 (7 8 ,@(cdr '(100 1001 1002)))345 67889) 67) ну и т.д, т.е. сильно-вложенные.
Мысль 1: Проблема из-за вложенности, и поэтому нельзя просто пройтись по данному нам списку с помощью cdr & car, выясняя встретившиеся "квоты"
2) Используя map, можно решить 1ю проблему. Однако возникает 2я -- unquote-splicing. При этом, в источнике "Quasiquotation in Lisp" by Alan Bawden сразу очевидно, что quasiquote аналогичен list, a unquote-splicing -- append. Но append можно вставлять только в изначальный список (т.е. в тот список, который на уровень выше того, к которому мы сейчас применяем map).
Мысль 2: Вся проблема в unquote-splicing -- его нужно рассматривать отдельно.
Отдельное рассмотрение привесло к следующему ужасно-неэффективному алгоритму:
1. берем наш список
2. ищем в нем unquote-splicing
3. выполняем его и запоминаем в качетстве отдельного аргумента
4. берем начальный список и заменяем всю скобку с ,@ на полученное выражение, при этом нужно учитывать позицию и вставлять append'ом.
5. радуемся выполненным неисвзращенным тестам (к извращенным относится *** ,@(cdr `(1 2 3 '(4 5 6))) ***
Этот ужасно-неэффективный алгоритм почти наверное не работает из-за потери опыта программирования в Лиспе (месяц не прогала -- все забыла).
3) Последнее, что стало ясно -- что я совсем ничего не понимаю, а особенно то, как можно "квоты" реализовать с помощью окружений и фреймов.
Мысль 3: спросить у "первоисточника". поиск в гугле не помог. в яндексе (некоторые считают, что он лучше гугла) -- тоже)

Интересны некоторые версии, приведенные в инете:
1. https://github.com/evanrmurphy/SweetScript/blob/master/arc3.1/ac.scm -- аля компилятора
2. http://www.cs.utah.edu/plt/mailarch/plt-scheme-2002/msg00494.html -- аля непонятно ничего
3. http://arclanguage.org/item?id=9373 -- стр 9 -- аля компилятора
ничего лучше не нашла

p.s.: Этот пост был написан, т.к. пожаловаться некому. Нормальные люди не хотят, чтобы им выносили мозг. Анормальные одногрупники послали меня в русского Сипсера (ну или как там его).
p.s.s: В любом случае мне это нужно написать. Вот заодно и посмеюсь над тем, что не понимала и не могла сделать (скорее всего там все просто).

1 комментарий:

  1. угу)) было все просто:
    blah-blah...
    ...
    ...
    (def (eval-qq depth x env)
    (se (null? x) nil
    (= depth 0) (eval x env)
    (or
    (and (application? x)
    (unquote? x))
    (and (application? x)
    (unquote-splicing? x)
    (= depth 1))) (eval-qq (- depth 1) (cadr x) env)
    (and (application? x)
    (quasiquote? x)) (eval-qq (+ depth 1) (cadr x) env)
    (list? (car x)) (if (next-splicing? x)
    (append (eval-qq depth (car x) env) (eval-qq depth (cdr x) env))
    (cons (eval-qq depth (car x) env) (eval-qq depth (cdr x) env)))
    (cons (car x) (eval-qq depth (cdr x) env))))

    а уж если проставить все табуляции, то станет все и совсем понятно)

    ОтветитьУдалить