> 1 <

Автор Сообщение

Spirit

Members


Статус

5 сообщений

Где: Bangladesh
Род занятий:
Возраст:

#7463   2014-11-19 19:28 GMT+3 часа(ов)      
Пишу дерево, там есть такое место:
(defstruct node
....
(left nil)
(parent nil))
Ну, понятно, как бы не-указатель на левую ветвь и на предка. Пишем (setf (node-left x) y), (setf (node-parent y) x), получаем висяк, потому что он начинает всё это добро раскрывать. Есть способ вместо явного копирования списка в поле сделать указатель?

P.S. Очень нубский вопрос - пишу простейший однострочный факториал, clisp разрешает глубину рекурсии всего в несколько тысяч. Вопрос: где обещанная tail recursion? (Учу по Sicp'у. в Scheme она видимо сразу зашита)

skelter

Members


Статус

34 сообщений

Где: ---
Род занятий:
Возраст:

#7464   2014-11-19 23:45 GMT+3 часа(ов)      
> Есть способ вместо явного копирования списка в поле сделать указатель?

Во-первых, списков тут и нет, тут структуры. Во-вторых, в лиспе и так одни указатели. На самом деле в вашем примере всё работает нормально, кроме печати. Он же хочет в REPLе ответ напечатать, а ответ циклический, вот и глючит. Чтобы печатал, надо сделать
(setf *print-circle* t)

тогда вывод будет навроде такого:
#1=#S(NODE :LEFT #S(NODE :LEFT NIL :PARENT #1#) :PARENT NIL)


> Вопрос: где обещанная tail recursion?

А вот нету. В стандарте CL нет понятия tail call, потому что оно не сочетается с динамическими переменными, unwind-protect и, наверно, ещё какими-то фичами CL. Оптимизация хвостовой рекурсии присутствует как часть компиляторной магии (и зависит от реализации), в переносимом коде на неё не надо полагаться.

А в схеме - да, эта оптимизация требуется стандартом.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#7466   2014-11-20 01:58 GMT+3 часа(ов)      
> В стандарте CL нет понятия tail call, потому что оно не сочетается с динамическими переменными, unwind-protect и, наверно, ещё какими-то фичами CL.

Тут проблема в обратной совместимости с предыдущими диалектами(реализациями) лиспа. А касательно динамических переменных и unwind-protect, то с ними проблем не должно возникнуть.

skelter

Members


Статус

34 сообщений

Где: ---
Род занятий:
Возраст:

#7467   2014-11-20 03:45 GMT+3 часа(ов)      
Вот умные люди рассуждают насчёт tail position в CL, с примерами:
https://groups.google.com/forum/#!topic/comp.lang.lisp/yqJgSycUo20
Лень вчитываться, но говорят, что динамические переменные и unwind-protect - основные препятствия к формальному определению хвостовой позиции.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#7468   2014-11-20 04:02 GMT+3 часа(ов)      
Там, вроде как, идет речь о создании специального макрокомпилятора. Полноценный же компилятор должен справляться с данными возможностями без особых проблем.

Spirit

Members


Статус

5 сообщений

Где: Bangladesh
Род занятий:
Возраст:

#7469   2014-11-20 05:31 GMT+3 часа(ов)      
Цитата
skelter :
(setf *print-circle* t)

тогда вывод будет навроде такого:
#1=#S(NODE :LEFT #S(NODE :LEFT NIL :PARENT #1#) :PARENT NIL)



Ок, спасибо.
Цитата

А вот нету. В стандарте CL нет понятия tail call, потому что оно не сочетается с динамическими переменными, unwind-protect и, наверно, ещё какими-то фичами CL. Оптимизация хвостовой рекурсии присутствует как часть компиляторной магии (и зависит от реализации), в переносимом коде на неё не надо полагаться.

А в схеме - да, эта оптимизация требуется стандартом.


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

skelter

Members


Статус

34 сообщений

Где: ---
Род занятий:
Возраст:

#7470   2014-11-20 05:52 GMT+3 часа(ов)      
Вот пример из той ветки:

Цитата
Consider this simple case:

(defun foo ()
(let ((some-var 37))
(gorp some-var)
(bar)))


Now if SOME-VAR is a lexical variable [no visible dynamic binding
or declaration], then the call of BAR is truly in tail position.
The stack space consumed by SOME-VAR can be released *before* the
call to BAR, which can thus be converted by the compiler into a jump.

But if SOME-VAR is a *dynamic* variable [e.g., there is a
(defvar some-var 53) somewhere above the (defun foo ...)],
then the compiler can't convert the call to a jump since
it needs to be able to restore the previous value of SOME-VAR
when the call to BAR returns. So in this case the call to
BAR *isn't* actually in tail position at all.

Similar considerations apply if there are UNWIND-PROTECT or
WITHOUT-ERRORS forms wrapped around the call to BAR.


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

В безопасных случаях компилятору под силу оптимизировать хвостовую рекурсию, и иногда они действительно её оптимизируют за счёт отладки. Компиляторная магия.

> Типо функция, допускающая хвостовую рекурсию, может быть переписана в итерационную? Мм, ну ладно, пусть так.

Ну да, люди вовсю используют циклы. Я люблю простой loop.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#7471   2014-11-20 16:51 GMT+3 часа(ов)      
> Насколько понимаю, этот пример опровергает возможность формального определения того, будет ли данный вызов хвостовым, путём пристального изучения этой функции.

Вы ведь сами указываете компилятору какие переменных являются динамическими. Так что проблема классического fluid-let решается очень просто: хвостовой вызов возможен, только если компилятор не обнаружил ни одной динамической переменной. Если вы не можете обойтись без динамической переменной, то лучше тогда явно использовать цикл или вынести его во внешнюю процедуру. Вообще-то, для "вменяемой" поддержки лексических переменных компилятору необходимо где-то хранить всю информацию о локальных переменных, а иначе он не сможет сгенерировать качественный код.

Кстати, в первых лиспах ведь были только динамические переменные (да, и в emacs лексические переменные появились лишь недавно). И при этом им удавалось восстанавливать значения переменных в случае возникновения ошибки. Угадаете каким образом они это делали?

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

skelter

Members


Статус

34 сообщений

Где: ---
Род занятий:
Возраст:

#7472   2014-11-20 18:25 GMT+3 часа(ов)      
> Я ранее ради интереса реализовал экспериментальный интерпретатор лиспа, в котором отсутствует компиляция, нет циклов, все переменные динамические, но с поддержкой хвостовых вызовов и некоторых др. не менее интересных для меня возможностей.

Убедительно.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#7473   2014-11-20 21:29 GMT+3 часа(ов)      
Я реализовал на нем простенький шлюз (cgi-скрипт), который интерпретирует лисп код. Желательно, последнюю строку в левой форме заменить на что-то типа:
(prin1 (time (fib 100.0)))
> 1 <


Онлайн :

0 пользователь(ей), 23 гость(ей) :




Реклама на сайте: