Предыдущая страница Следующая страница [1] [2] [3] [4] > 5 < [6]

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

misha

Moderators


Статус

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

#4562   2011-07-17 23:14 GMT+3 часа(ов)      
Цитата
Не знаю, какая структура у fasl, а у байткода-таки списочная.

Как вы это определили?
Цитата
имена глобальных символов заменяются абракадаброй

Вставляется код (2 байта) загружающий их значение из environment. Или типа того
Цитата
имена локальных - позицией в стеке.

Какой вы имеете в виду стек?
Цитата
Все примитивы (типа begin, lambda, define, let etc.) в байткоде сохраняются.

Что вы имели в виду? Я увидел только байты
Цитата
а она на структуру байткода и не влияет

На структуру, конечно, не влияет, но не вы ли это писали: "Собственно, можно сделать на любой модуль decompile и посмотреть - вот то что получится, это и есть байткод, с точностью до обозначений"

Kergan

Members


Статус

300 сообщений

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

#4563   2011-07-18 00:24 GMT+3 часа(ов)      
Цитата
На структуру, конечно, не влияет, но не вы ли это писали: "Собственно, можно сделать на любой модуль decompile и посмотреть - вот то что получится, это и есть байткод, с точностью до обозначений"


Ну да, так и есть. А где тут противоречие?

Цитата
Что вы имели в виду? Я увидел только байты

Ну естественно, обозначения закодированы

Цитата
Какой вы имеете в виду стек?


Стек виртуальной машины. vm Racket - стековая.

Цитата
Как вы это определили?

http://plt.eecs.northwestern.edu/racket-machine/

misha

Moderators


Статус

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

#4564   2011-07-18 01:20 GMT+3 часа(ов)      
Цитата
Ну да, так и есть. А где тут противоречие?

Оптимизация удаляет лишнее.
Цитата
>имена локальных - позицией в стеке.
>Стек виртуальной машины. vm Racket - стековая.

У лиспа для хранения значений локальных переменных используется environment. Использовать стек можно лишь в примитивных случаях.
Цитата
http://plt.eecs.northwestern.edu/racket-machine/

Там говорится о том, что байткод имитирует структуру лиспа. Но на деле это больше похоже на Форт наоборот (можете сами проверить)

Кстати, ранее вы писали "он имеет списочную структуру (то есть выражения в виде head/rest)", так вот никаких head/rest там нет.

отредактировал(а) misha: 2011-07-18 01:35 GMT+3 часа(ов)

misha

Moderators


Статус

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

#4565   2011-07-18 02:03 GMT+3 часа(ов)      
Цитата
http://plt.eecs.northwestern.edu/racket-machine/

В работе описана (и реализована) довольно интересная модель VM. Единственно, что настораживает так это использование вложенных стеков и прочие заморочки. К сожалению, данную модель невозможно эффективно реализовать для .net и java платформ.

Kergan

Members


Статус

300 сообщений

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

#4566   2011-07-20 00:18 GMT+3 часа(ов)      
Цитата
Оптимизация удаляет лишнее.

Ну да. После decompile все это лишнее будет удалено. Там еще control-flow как-то непонятно меняется (например при разворачивании рекурсии лифтятся новые функции и как-то переставляются условные ветки).

Цитата
У лиспа для хранения значений локальных переменных используется environment. Использовать стек можно лишь в примитивных случаях.

спагетти-стек - как раз классический вариант реализации схем.

Цитата
Там говорится о том, что байткод имитирует структуру лиспа. Но на деле это больше похоже на Форт наоборот

Ну естественно! Ведь лисп - это _и есть_ форт наоборот. Из кода на лиспе получается код на форте просто переворачиванием сэкспров и убиранием скобочек

Цитата
Кстати, ранее вы писали "он имеет списочную структуру (то есть выражения в виде head/rest)", так вот никаких head/rest там нет.

есть, конечно, просто это не списки.

Цитата
В работе описана (и реализована) довольно интересная модель VM. Единственно, что настораживает так это использование вложенных стеков и прочие заморочки.

ну, главное, что работает

Цитата
К сожалению, данную модель невозможно эффективно реализовать для .net и java платформ.

А зачем? Есть же прекрасная платформа Racket.

misha

Moderators


Статус

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

#4567   2011-07-22 22:06 GMT+3 часа(ов)      
Цитата
Там еще control-flow как-то непонятно меняется (например при разворачивании рекурсии лифтятся новые функции и как-то переставляются условные ветки).

Там описывается работа их VM.
Цитата
спагетти-стек - как раз классический вариант реализации схем.

Впервые слышу
Цитата
Из кода на лиспе получается код на форте просто переворачиванием сэкспров и убиранием скобочек

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

Что есть?
Цитата
А зачем? Есть же прекрасная платформа Racket.

А мне бы хотелось использовать Racket на этих платформах.

Kergan

Members


Статус

300 сообщений

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

#4568   2011-07-23 00:15 GMT+3 часа(ов)      
Цитата
Там описывается работа их VM.

Я говорю про оптимизация при генерации байткода.

Цитата
Они могли с самого начала использовать модель форта

на самом деле не могли, там с фортом одно кардинальное различие - семантика аппликации.

Цитата
А мне бы хотелось использовать Racket на этих платформах.

А зачем реализовывать одну виртуальную машину из-под другой? Под VM .net Racket вообще говоря реализовать можно. Вот с джавой не выйдет, это да, там даже оптимизации хвостовых вызовов нельзя сделать.

misha

Moderators


Статус

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

#4569   2011-07-23 01:37 GMT+3 часа(ов)      
Цитата
Я говорю про оптимизация при генерации байткода.

Тогда об этом подробнее.
Цитата
на самом деле не могли, там с фортом одно кардинальное различие - семантика аппликации.

Вы Racket-байткод анализировали?
Цитата
А зачем реализовывать одну виртуальную машину из-под другой?

Что вы имели в виду?
Цитата
Под VM .net Racket вообще говоря реализовать можно.

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

Хороший компилятор должен уметь преобразовывать хвостовую рекурсию в итерацию. Вообще на Racket также можно наложить ограничения, либо придумать новый диалект.

Kergan

Members


Статус

300 сообщений

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

#4570   2011-07-24 05:02 GMT+3 часа(ов)      
Цитата
Тогда об этом подробнее.

Ну как подробнее? Напишите обычный факториал с вложенной ф-ей и сделайте compile/decompile.

Цитата
Вы Racket-байткод анализировали?

У вас спецификация его подмножества перед глазами. Там доступ к переменной в стеке по смещению - атомарная операция, как вы себе представляете это в форте?

Цитата
Что вы имели в виду?

То и имею. Зачем реализовывать одну виртуальную машину поверх другой (в данном случае racket поверх джавы или .net)?

Цитата
А как продолжения будут реализованы?

Ну продолжения всегда можно реализовать при помощи cps-преобразования, другое дело, что в racket вместо продолжений prompt'ы, но я не думаю, что это проблема. Да и вообще реализаций продолжений много - вопрос в том, насколько они могут быть эффективны. Естественно, на vm заточенной под такие вещи продолжения можно реализовать более эффективно. Вообще есть же IronScheme - видимо, как-то эту задачу решили там, хоть и, скорее всего, и не полностью.

Цитата
Хороший компилятор должен уметь преобразовывать хвостовую рекурсию в итерацию.

Я про рекурсию не говорил, я говорил про оптимизацию хвостовых вызовов.

misha

Moderators


Статус

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

#4571   2011-07-24 12:54 GMT+3 часа(ов)      
Цитата
Ну как подробнее? Напишите обычный факториал с вложенной ф-ей и сделайте compile/decompile.

Ничего подобного: "Там еще control-flow как-то непонятно меняется (например при разворачивании рекурсии лифтятся новые функции и как-то переставляются условные ветки)", я не увидел.
Цитата
У вас спецификация его подмножества перед глазами.

Вот именно, подмножества
Цитата
Там доступ к переменной в стеке по смещению - атомарная операция, как вы себе представляете это в форте?

Точно также
Я ранее писал о том, что выражение
(list 1 (list 2 3) 4)
можно представить как в стиле лиспа
call/3 [let-proc list] [let 1] 
call/2 [let-proc list] [let 2] [let 3]
[let 4]
так и в стиле форта
[let-proc list] [let 1] 
[let-proc list] [let 2] [let 3] call/2
[let 4] call/3

Цитата
То и имею. Зачем реализовывать одну виртуальную машину поверх другой (в данном случае racket поверх джавы или .net)?

А зачем поверх другой? Можно создать специальные диалекты учитывающие ограничения этих платформ.
Цитата
Ну продолжения всегда можно реализовать при помощи cps-преобразования

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

Как раз они должны быть эффективны, т.к. изначально подразумевалось, что они являются альтернативой операции вызова функции.
Цитата
Вообще есть же IronScheme - видимо, как-то эту задачу решили там, хоть и, скорее всего, и не полностью.

По мне так вообще не решили.
Цитата
Я про рекурсию не говорил, я говорил про оптимизацию хвостовых вызовов.

Ну, это не так сложно.

Kergan

Members


Статус

300 сообщений

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

#4572   2011-07-25 03:39 GMT+3 часа(ов)      
Цитата
я не увидел.

Посмотрел - действительно, на факториалах ничего не лифтится
Я, если честно, не помню того самого примера, для которого байткод смотрел, помню только, что там было несколько вложенных лупов с cond-ами.

Цитата
Вот именно, подмножества

Вы считаете, что может быть так, что основное подмножество - имеет списочную структуру, а добавка- нет?

Цитата
Точно также

Как точно так же? В форте у вас нету никакой абсолютно возможности обратиться не к вершине стека а к тому, что лежит под ней.

Цитата
Можно создать специальные диалекты учитывающие ограничения этих платформ.

Но зачем лепить огрызки?

Цитата
Если бы это было бы так, то CL уже давно бы ими обзавелся.

А, ну тут проблема в следующем - для полной поддержки продолжений с помощью cps у вас должен быть ВЕСЬ код преобразован в cps, то есть все библиотеки и все примитивные ФВП в том числе. Естественно, для CL это неприемлемо, но если вы реализуете диалект, в котором компиляция всегда идет через cps, то здесь нету никаких сложностей. Здесь конечно, возникает другая проблема - совместимость с другим джава/.net софтом.

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

Кому должны? Почему должны? стандарт никаких ограничений на эффективность не накладывает.

Цитата
Ну, это не так сложно.

Ну сложнее реализации хвостовой рекурсии, явно
По крайней мере jvm ее не поддерживает.

misha

Moderators


Статус

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

#4573   2011-07-25 12:03 GMT+3 часа(ов)      
Цитата
Вы считаете, что может быть так, что основное подмножество - имеет списочную структуру, а добавка- нет?

А это вы к чему?
Цитата
Как точно так же? В форте у вас нету никакой абсолютно возможности обратиться не к вершине стека а к тому, что лежит под ней.

Кто вам это сказал? Существует же PICK, вообще в большинстве реализаций оговорено, где хранится значение указателя на вершину стека.
Цитата
Но зачем лепить огрызки?

Новая платформа новые правила.
Цитата
А, ну тут проблема в следующем - для полной поддержки продолжений с помощью cps у вас должен быть ВЕСЬ код преобразован в cps, то есть все библиотеки и все примитивные ФВП в том числе.

Примитивы обычно не подвергаются cps преобразованию. Тут проблема скорее в необходимости эффективной реализации. А если конкретно, то необходимы: специальный массив для хранения параметров текущей операции; специальные регистры (глобальные переменные) для хранения переходов, передачи параметров функции.
Цитата

Кому должны? Почему должны? стандарт никаких ограничений на эффективность не накладывает.

Какой такой стандарт? Кому нужны неэффективные продолжения?
Цитата
Ну сложнее реализации хвостовой рекурсии, явно
По крайней мере jvm ее не поддерживает.

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

отредактировал(а) misha: 2011-07-25 12:14 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

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

#4574   2011-07-26 06:18 GMT+3 часа(ов)      
Цитата
А это вы к чему?

Это я к:
Цитата
Вот именно, подмножества


Цитата
Существует же PICK

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

Цитата
Примитивы обычно не подвергаются cps преобразованию.

Не все. Если примитив - ф-я первого порядка, то, действительно, cps-преобразование проводить не надо, потому что мы не можем захватить продолжение у него изнутри. С другой стороны, тот же map обязан быть в cps.

Цитата
Новая платформа новые правила.

Но зачем?

Цитата
Тут проблема скорее в необходимости эффективной реализации.

Вообще говоря - реализация продолжений при помощи cps-преобразования наиболее эффективна из всех. На порядки более эффективна

Цитата
А если конкретно, то необходимы: специальный массив для хранения параметров текущей операции; специальные регистры (глобальные переменные) для хранения переходов, передачи параметров функции.


Зачем?

Цитата
Какой такой стандарт? Кому нужны неэффективные продолжения?

А где они эффективны?
На практике перед каждым вызовом продолжения надо сделать его захват, а захват в не-cps реализациях ОЧЕНЬ долгая операция. В том же racket в итоге захват-вызов продолжения эдак раз в 1000 медленнее обычного вызова ф-и (это если отключить инлайнинг ), и это еще эффективная реализация - в racket пытались оптимизировать работу продолжений даже в ущерб другим аспектам.

Цитата
Пусть компилятор сам вставляет подобную проверку для вызова функций находящихся в "хвосте".

Не все так просто. Во-первых, это все должно быть согласовано в работе с оптимизациями (ну например - положили вы аргумент в регистр, что теперь делать?), во-вторых - тут дело не в компиляторы, вызовы вшиты в jvm, то есть надо переписывать jvm.

Kergan

Members


Статус

300 сообщений

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

#4575   2011-07-26 06:20 GMT+3 часа(ов)      
Цитата
Сравнивая идентификаторы объектов можно определить принадлежность хвостовой это вызов или нет.

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

misha

Moderators


Статус

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

#4576   2011-07-26 11:44 GMT+3 часа(ов)      
Цитата
применение которого считается неправильным стилем.

Ну, так ведь для ламеров пишут
Цитата
Вообще не важно - суть-то в чем, байткод в отличии от форта вы не сможете записать конкантенативно, потому что при вызове ф-и в байткоде переданные аргументы кладутся на стек

И где тут противоречие?
Цитата
там даже, по-моему, не специфицируется порядок вычисления аргументов, хотя уже не помню, могу ошибаться

В зависимости от реализации либо слева направо, либо наоборот.
Цитата
В форте - не кладутся, считается, что положить их должен программист, руками. То есть ключевой особенности форта тут не сохраняется.

В лиспе это делает за вас компилятор, а мы ведем речь о представлении байткода виртуальной машины.
Цитата
Цитата
Новая платформа новые правила.
Но зачем?

Мне так нужно
Цитата
Во-первых, это все должно быть согласовано в работе с оптимизациями (ну например - положили вы аргумент в регистр, что теперь делать?), во-вторых - тут дело не в компиляторы, вызовы вшиты в jvm, то есть надо переписывать jvm.

Из хороших java-компиляторов я знаю только ABCL.
Цитата
Цитата
А если конкретно, то необходимы: специальный массив для хранения параметров текущей операции; специальные регистры (глобальные переменные) для хранения переходов, передачи параметров функции.
Но зачем?

cps-преобразования хороши для Си-компиляторов, но даже там возникают проблемы при написании многопоточных приложений.
Цитата
Вообще говоря - реализация продолжений при помощи cps-преобразования наиболее эффективна из всех. На порядки более эффективна

Смотря с чем сравнивать
Цитата
А где они эффективны?

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

Я отвечал на последний вопрос: "По крайней мере jvm ее не поддерживает.", а там, как я понял, речь шла о хвостовой рекурсии.

Kergan

Members


Статус

300 сообщений

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

#4577   2011-07-26 16:36 GMT+3 часа(ов)      
Цитата
И где тут противоречие?

Противоречие в том, что в этом случае конкантенативно записать программу нельзя.

Цитата
В лиспе это делает за вас компилятор, а мы ведем речь о представлении байткода виртуальной машины.

ну да
форт - конкантенативный, байткод - неконкантенативный
вот и весь разговор?

Цитата
Мне так нужно

Ну тут дело-то вот в чем, виртуальная машина Racket по сравнению с jvm - это как истребитель 5 поколения по сравнению с довоенным кукурузником. А Racket (как язык) сильно заточен под Racket vm (или, скорее, наоборот ). В результате при реализации куда ни ткните - попадете в ограничения jvm. Вот например - систему модулей Racket вы на базе jvm не организуете (то есть на самом деле можно, но по сути вы получите кусок vm Racket, реализованный поверх jvm), а макросы без нее работать не станут и вообще вся синтаксическая модель на модулях завязана. Или, например, - в байткоде может храниться информация о syntax objects. Как это реализовать в джаве? Опять же, специфичные для тредов/custodians вещи и прочая прочая прочая.

Цитата
Из хороших java-компиляторов я знаю только ABCL.

Ну это CL - он старый и простой, его и jvm потянет

Цитата
cps-преобразования хороши для Си-компиляторов

как можно сделать cps преобразование в языке без лямбд? Сможете написать для си cps преобразование факториала?

Цитата
Смотря с чем сравнивать

как с чем? с другими реализациями. с cps-преобразованием захват продолжения и его вызов - это просто вызовы ф-и. Все остальные реализации медленнее.

Цитата
В теории конечно

Ах, ок. но быстрее, чем cps - у вас все равно не получится

Цитата
Я отвечал на последний вопрос: "По крайней мере jvm ее не поддерживает.", а там, как я понял, речь шла о хвостовой рекурсии.

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

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 27

#4578   2011-07-27 02:53 GMT+3 часа(ов)      
> как можно сделать cps преобразование в языке без лямбд?
http://home.pipeline.com/~hbaker1/CheneyMTA.html

Kergan

Members


Статус

300 сообщений

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

#4579   2011-07-27 08:28 GMT+3 часа(ов)      
Ну там же cps-преобразование делается на схемке, а потом просто этот код компилируется в сишку, причем в сишке приходится лифтить все лямбды и велосипедить руками замыкания.

misha

Moderators


Статус

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

#4580   2011-07-28 19:06 GMT+3 часа(ов)      
Цитата
Противоречие в том, что в этом случае конкантенативно записать программу нельзя.

Цитата
форт - конкантенативный, байткод - неконкантенативный
вот и весь разговор?

Вы хотите сказать, что байткод лиспа не может иметь конкатенативный вид?
Цитата
Ну тут дело-то вот в чем, виртуальная машина Racket по сравнению с jvm - это как истребитель 5 поколения по сравнению с довоенным кукурузником. А Racket (как язык) сильно заточен под Racket vm (или, скорее, наоборот ). В результате при реализации куда ни ткните - попадете в ограничения jvm. Вот например - систему модулей Racket вы на базе jvm не организуете (то есть на самом деле можно, но по сути вы получите кусок vm Racket, реализованный поверх jvm), а макросы без нее работать не станут и вообще вся синтаксическая модель на модулях завязана. Или, например, - в байткоде может храниться информация о syntax objects. Как это реализовать в джаве? Опять же, специфичные для тредов/custodians вещи и прочая прочая прочая.

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

Я надеюсь, что это была шутка
Цитата
как можно сделать cps преобразование в языке без лямбд? Сможете написать для си cps преобразование факториала?

Я писал о трансляторах Scheme->C.
Цитата
как с чем? с другими реализациями. с cps-преобразованием захват продолжения и его вызов - это просто вызовы ф-и. Все остальные реализации медленнее.

Даже у этого метода есть свои ограничения.
(define c #f)
(define (factorial n)
(if (zero? n)
(call/cc (lambda(r) (set! c r) 1))
(* n (factorial (sub1 n)))))
> (factorial 10)
3628800
> (c 1)
3628800

Цитата
Ах, ок. но быстрее, чем cps - у вас все равно не получится

А это еще почему?
Цитата
Я как раз за пост до этого указал, что рекурсия это одно, но нужна то оптимизация всех вызовов, а не только рекурсии.

Что вы подразумеваете под оптимизацией всех вызовов?

отредактировал(а) misha: 2011-07-28 19:16 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

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

#4581   2011-07-29 06:46 GMT+3 часа(ов)      
Цитата
Вы хотите сказать, что байткод лиспа не может иметь конкатенативный вид?

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

Цитата
Новый диалект должен быть заточен под выбранную платформу.

Ну получится обычная схема.

Цитата
Я надеюсь, что это была шутка

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

Цитата
Даже у этого метода есть свои ограничения.

Не понял, какие ограничения имеются в виду?

Цитата
А это еще почему?

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

Цитата
Что вы подразумеваете под оптимизацией всех вызовов?

оптимизацию всех хвостовых вызовов. Как в схеме.

misha

Moderators


Статус

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

#4583   2011-07-29 18:59 GMT+3 часа(ов)      
Цитата
Если при вызове функции происходит автоматическая передача аргументов на стек, то конкантенативная запись невозможна.


Да, но сначала необходимо вычислить все параметры, включая предполагаемую функцию.
Решил реинкарнировать свой ToyLisp (аргументы вычисляются справа на лева):
> (setq x (lambda() (list 1 (list 2 3) 4)))
#<procedure id:1>
> (x)
(1 (2 3) 4)
> (disassemble x)
(#<procedure id:1>
(CHECK-ZERO-ARGUMENTS)
(PUSH 4)
(PUSH 3)
(PUSH 2)
(LOAD-GLOBAL-VARIABLE 44)
(CALL2)
(PUSH 1)
(LOAD-GLOBAL-VARIABLE 44)
(CALL3-TAIL)
(RET))
 
#<void>

Цитата
Ну получится обычная схема.

А мне и этого хватит
Цитата
У CL достаточно примитивная семанткика в этом плане.

Как раз семантика чуть более сложная (Lisp-2 ведь).
Цитата
Все-таки, требования совместимости накладывают свой отпечаток - тех же фаз компиляции во времена написания стандарта еще не было, а теперь их уже и не введешь.
Языку без модулей фазы ни к чему. Кстати, фазы существуют только во время загрузки модуля.
Цитата
Не понял, какие ограничения имеются в виду?

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

Например, в ToyLisp-е я обошелся без cps:
(setq c #f)
(setq factorial
(lambda (n)
(if (zero? n)
(call/cc (lambda(r) (setq c r) 1))
(* n (factorial (- n 1))))))
> (factorial 20)
2432902008176640000
> (c 1)
2432902008176640000
При создании продолжения приходится копировать стеки, а при вызове их восстанавливать. Т.к. стек и его копия являются массивами, то я просто присваиваю переменной новое значение. Поэтому у меня вызов продолжения быстрее вызова функции.
Цитата
оптимизацию всех хвостовых вызовов. Как в схеме.

В r5rs требует чтобы хвостовая рекурсия не расходовала стек.

Kergan

Members


Статус

300 сообщений

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

#4584   2011-07-31 11:31 GMT+3 часа(ов)      
Цитата
Да

О чем и речь.

Цитата
Как раз семантика чуть более сложная (Lisp-2 ведь).

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

Цитата
Языку без модулей фазы ни к чему.

Ну вообще фазы решают несколько иную задачу - они позволяют корректно проконтролировать факт и время исполнения кода. То, что без фаз невозможно реализовать систему модулей - это другой разговор, но именно из-за того, что в CL нету фаз, там никогда не будет раздельной компиляции. И не потому что "не нужно" - а потому что невозможно реализовать

Цитата
Кстати, фазы существуют только во время загрузки модуля.

они всегда существуют, потому что есть конструкции вида (require (for-meta phase-number ...)), именно из-за этого после компиляции модуля к коду 0-фазы добавляется и код 1-фазы, хотя для рантайма он совершенно не нужен.

Цитата
Одним преобразованием дело не заканчивается.

как раз заканчивается

Цитата
Необходимо еще реализация специального стека для хранения состояний, либо придумать какие-нибудь другие механизмы.

конечно, не нужно
cps-преобразование решает все эти проблемы, продолжение - это просто обычное замыкание.

Цитата
Поэтому у меня вызов продолжения быстрее вызова функции.

Как же это он у вас быстрее?
У вас вызов продолжения - это вызов функции + присваивание нового значения переменной. А вызов функции будет всегда быстрее, чем вызов функции + любая операция, о чем я и говорил.

Цитата
В r5rs требует чтобы хвостовая рекурсия не расходовала стек.

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

misha

Moderators


Статус

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

#4585   2011-07-31 14:20 GMT+3 часа(ов)      
Цитата
Цитата
А вот наличие модулей с поддержкой фаз - очень сильно. Фактически, тут имеются сразу два рантайма, которые могут при работе пересекаться весьма нетривиальным способом.

Цитата
Ну вообще фазы решают несколько иную задачу - они позволяют корректно проконтролировать факт и время исполнения кода. То, что без фаз невозможно реализовать систему модулей - это другой разговор, но именно из-за того, что в CL нету фаз, там никогда не будет раздельной компиляции. И не потому что "не нужно" - а потому что невозможно реализовать

Как раз наличие фаз почти не влияет на семантику, т.к. фазы влияют лишь на экспанд модуля. Двух рантаймов также не существует. Фазы надо рассматривать как многопроходный экспанд (с раздельными пространствами имен), кстати, вы в этом сами можете убедиться. Для реализации фаз у CL есть все необходимое(пространства имен, eval-when, compile). Стоит еще добавить, что defun можно рассматривать многофазный макрос.
(macroexpand '(defun x() 5))
 
(PROGN
(EVAL-WHEN (:COMPILE-TOPLEVEL) (SB-C:%COMPILER-DEFUN 'X 'NIL T))
(EVAL-WHEN (:LOAD-TOPLEVEL :EXECUTE)
(SB-IMPL::%DEFUN 'X
(SB-INT:NAMED-LAMBDA X
NIL
(BLOCK X 5))
NIL 'NIL (SB-C:SOURCE-LOCATION))))
T

Цитата
они всегда существуют, потому что есть конструкции вида (require (for-meta phase-number ...)), именно из-за этого после компиляции модуля к коду 0-фазы добавляется и код 1-фазы, хотя для рантайма он совершенно не нужен.
У рантайма нет фаз.
Цитата
Цитата
как раз заканчивается
Цитата
конечно, не нужно
cps-преобразование решает все эти проблемы, продолжение - это просто обычное замыкание.

CPS (без расширений) позволяет организовать лишь ограниченную поддержку продолжений. Например, как в IronScheme
> (define c #f)
> (define (factorial n)
. (if (zero? n)
. (call/cc (lambda(r) (set! c r) 1))
. (* n (factorial (- n 1)))))
> (factorial 20)
2432902008176640000
> (c 1)
Unhandled exception during evaluation:
&assertion
&who: "call/cc"
&message: "not supported, continuation called outside dynamic extent"
&irritants: ()

misha

Moderators


Статус

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

#4586   2011-07-31 14:45 GMT+3 часа(ов)      
Цитата
Как же это он у вас быстрее?
У вас вызов продолжения - это вызов функции + присваивание нового значения переменной. А вызов функции будет всегда быстрее, чем вызов функции + любая операция, о чем я и говорил.
Перед вызовом функции необходимо создать environment (конечно, кроме хвостовой рекурсии), а для вызова продолжения этого делать не нужно.
Цитата
Нет, ни в r5rs ни вообще в любой схеме ничего про рекурсию не говорится, стек не должны расходовать хвостовые вызовы, а не рекурсия.

Чтобы все хвостовые вызовы не расходовали стек, необходимо считывать со стека все аргументы в environment (как раз это и реализовано в ToyLisp-е), а иначе придется реализовывать "костыли" для освобождения аргументов со стека.

Kergan

Members


Статус

300 сообщений

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

#4587   2011-07-31 20:06 GMT+3 часа(ов)      
Цитата
Как раз наличие фаз почти не влияет на семантику, т.к. фазы влияют лишь на экспанд модуля.

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

Цитата
Для реализации фаз у CL есть все необходимое(пространства имен, eval-when, compile).

Это все мелочи, даже если бы их не было - можно было бы легко все эти вещи сделать. Фазы в CL сделать нельзя, потому что в CL нету главного - поддерживаемого на уровне рантайма способа разделить код. С точки зрения CL после компиляции макросов не существует - другими словами, после того, как компиляция завершена, никакой информации о первой фазе в скомпилированном коде нет (то есть например в нем нету информации о том, что "вот тут у нас была форма (eval-when ...)"). И нету способа ее туда протащить. А вот в Racket вся эта информация остается - потому что то, что было в 1 фазе в одном модуле, потом может оказаться нулевой фазой. Вы когда написали модуль, то не можете сказать, в какой фазе потом он будет импортирован.

Цитата
У рантайма нет фаз.
Ну конечно же есть.

Цитата
CPS (без расширений) позволяет организовать лишь ограниченную поддержку продолжений. Например, как в IronScheme

Ну ничего подобного, ваш пример будет прекрасно работать в реализации через cps. То, что он не работает в ironscheme - это как бы уже особенности конкретной реализации ironscheme.

Цитата
Перед вызовом функции необходимо создать environment

"создать environment" - это значит "передать аргументы."

Цитата
а для вызова продолжения этого делать не нужно.

Ну если вы аргументы в продолжение передаете - нужно. Если не передаете - не нужно, да. Все в точности так, как при вызове функции.

Цитата
Чтобы все хвостовые вызовы не расходовали стек, необходимо считывать со стека все аргументы в environment

1. с чего вы взяли?
2. даже если так - как это отменяет тот факт, что во всех схемах таки все хвостовые вызовы не расходуют стек?

misha

Moderators


Статус

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

#4588   2011-08-01 00:07 GMT+3 часа(ов)      
Цитата
Цитата
Конечно же, нет. Фазы это совсем не многопроходной экспанд. Вы вообще когда модуль скомпилировали - то любое вычисление внутри этого модуля может потом оказаться в любой фазе.
Цитата
Это все мелочи, даже если бы их не было - можно было бы легко все эти вещи сделать. Фазы в CL сделать нельзя, потому что в CL нету главного - поддерживаемого на уровне рантайма способа разделить код. С точки зрения CL после компиляции макросов не существует - другими словами, после того, как компиляция завершена, никакой информации о первой фазе в скомпилированном коде нет (то есть например в нем нету информации о том, что "вот тут у нас была форма (eval-when ...)"). И нету способа ее туда протащить. А вот в Racket вся эта информация остается - потому что то, что было в 1 фазе в одном модуле, потом может оказаться нулевой фазой. Вы когда написали модуль, то не можете сказать, в какой фазе потом он будет импортирован.
Цитата
Ну конечно же есть.

Вы слишком неубедительно аргументируете. Где доказательства?

misha

Moderators


Статус

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

#4589   2011-08-01 00:56 GMT+3 часа(ов)      
Цитата
Ну ничего подобного, ваш пример будет прекрасно работать в реализации через cps. То, что он не работает в ironscheme - это как бы уже особенности конкретной реализации ironscheme.
У cps есть одна проблема - где лучше хранить остаточные вычисления. Самый примитивный подход подразумевает использование замыканий. Вы его имели в виду?
Давайте сравним его производительность с моим подходом.
(setq halt (lambda(r) r))
 
(setq $* (lambda (cont a b) (cont (* a b))))
(setq $+ (lambda (cont a b) (cont (+ a b))))
(setq $- (lambda (cont a b) (cont (- a b))))
(setq $zero? (lambda (cont a) (cont (zero? a))))
 
(setq $factorial
(lambda (cont a)
($zero? (lambda (b)
(if b
((setq fact/cont cont) 1)
($- (lambda (c)
($factorial (lambda (d)
($* cont a d))
c))
a 1)))
a)))
 
(setq factorial
(lambda (n)
(if (zero? n)
(call/cc (lambda(r) (setq fact/cont r) 1))
(* n (factorial (- n 1))))))
 
> (factorial 20)
2432902008176640000
> ($factorial halt 20)
2432902008176640000
> (fact/cont 1)
2432902008176640000
> (begin ($factorial halt 10000) #t)
#t
На вычисление затрачено: 671,875 мс.
> (begin (fact/cont 1) #t)
#t
На вычисление затрачено: 625 мс.
> (begin (factorial 10000) #t)
#t
На вычисление затрачено: 250 мс.
> (begin (fact/cont 10000) #t)
#t
На вычисление затрачено: 218,75 мс.
Вывод: использование замыканий не самый лучший способ хранить остаточные вычисления.

misha

Moderators


Статус

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

#4590   2011-08-01 01:11 GMT+3 часа(ов)      
Цитата
"создать environment" - это значит "передать аргументы."
"Создать environment" надо понимать как создать объект.
Цитата
Ну если вы аргументы в продолжение передаете - нужно. Если не передаете - не нужно, да. Все в точности так, как при вызове функции.
При вызове продолжения environment не создается.
Цитата
1. с чего вы взяли?
2. даже если так - как это отменяет тот факт, что во всех схемах таки все хвостовые вызовы не расходуют стек?

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

Kergan

Members


Статус

300 сообщений

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

#4591   2011-08-01 11:50 GMT+3 часа(ов)      
Цитата
Вы слишком неубедительно аргументируете. Где доказательства?

Доказательства чего именно? Того, что в CL скомпилированный код не делится по фазам, а в Racket - делится? Ну, собственно, спецификация CL и Racket соответственно

Цитата
У cps есть одна проблема - где лучше хранить остаточные вычисления. Самый примитивный подход подразумевает использование замыканий.

Это и называется cps-преобразование

Цитата
Давайте сравним его производительность с моим подходом.

Ну а где реализация вашего call/cc? У вас какая-то странная мания сравнивать непонять что

Цитата
"Создать environment" надо понимать как создать объект.

Зачем? ведь на самом деле это и есть передача аргументов, а никакое ни создание объекта.

Цитата
При вызове продолжения environment не создается.

Если аругменты не передаете - не создается. если передаете - создается (помним, что создание environment = передача аргументов).

Цитата
Все зависит от разработчика, если он позаботился об этом, то хвостовые вызовы не будут расходовать стек.

разработчик тут не при чем, proper tail-call optimisation - требование стандарта любой схемы. еще с самой первой - той самой, которая для SICP.

Kergan

Members


Статус

300 сообщений

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

#4592   2011-08-01 12:06 GMT+3 часа(ов)      
Цитата
Ну, собственно, спецификация CL и Racket соответственно

и прсотой примерчик:

 
> (module m racket
(begin-for-syntax (displayln "phase 1"))
(displayln "phase 0"))
phase 1 ; модуль скомпилирован и исполнены сайдэффекты первой фазы
> (require 'm)
phase 1 ; сайд-эффект первой фазы в первой фазе (несмотря на то, что модуль УЖЕ скомпилирован)
phase 0 ; сайд-эффект нулевой фазы в нулевой фазе
> (require (for-syntax 'm))
phase 0 ; сайд-эффект нулевой фазы в первой фазе
> (require (for-template 'm))
phase 1 ; сайдэффект первой фазы в нулевой фазе (то есть переносим в "рантайм" вычисления "компайлтайма")
>
 


Онлайн :

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




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