LINUX.ORG.RU

Пара вопросов по реализации Scheme

 ,


0

4

Продолжаю свою эпопею по имплементации r5rs на Java.
D общем-то, все (что реализовано) работает, совпадает с результатами в Guile, Racket и Chicken Scheme.
Беру рандомные примеры с Rosetta Code - в 90% случаев они выполняются правильно, в остальных - нахожу какую-нибудь багу и чиню ее.
Но, периодически возникают различные вопросы по реализации. В Интернете найти вразумительныe ответы не всегда получается.

Вопрос 1:
Как в современных Лиспах/Схемах реализованы списки?
Действительно ли везде берут Cons и из них создают связный список?

Изначально в своей реализации в качестве списков я просто использовал джавовский LinkedList (точнее, наследовал свой класс от него).
Все прекрасно работает, плюс, бесплатно получаю все оптимизации, все полезные методы LinkedList'а, реализацию интерфейсов List, Deque.
Cons же сделал просто отдельным классом, который используется в некоторых случаях, а при любой возможности перехожу на List.

Потом я решил все-таки сделать нормальный Cons и Cons Lists (та еще задача!) - и началось...
Казалось бы, такая простая штука - тупо пара двух значений.
Но потом оказывается, что там много нестандартных специальных случаев, когда эта штука ведет себя немного по-другому (nil-terminated lists, dotted notation, cyclic lists etc. NIL объект должен быть синглтоном. Плюс, так как это Джава, то нельзя использовать рекурсию, все приходится переделывать в итеративную версию)

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

Так вот, действительно ли сейчас реализовывают списки через кучу связанных Cons cells?

Есть ли какой-нибудь красивый и простой способ остаться на стандартных джавовских коллекциях, реализовать и список, и cons-ячейку, да еще и сделать, чтобы список был реализован непосредственно через cons'ы, либо наследовал от них?


Вопрос 2:
Есть ли какой-то стандартных набор юнит тестов/кейсов на которых можно было бы тестировать свою имплементацию?
Т.е. если все эти тесты пройдены, то имплементация считается успешной.
Я, конечно, стараюсь покрывать все возможные случаи, плюс, проверяю на примерах из Интернетов (той же Rosetta Code), но в спецификации же полно редких случаев и тп.

★★★★★

Плюс, так как это Джава, то нельзя использовать рекурсию, все приходится переделывать в итеративную версию)

У тебя Scheme без Tail-call optimization? А как тогда циклы делаешь?

Так вот, действительно ли сейчас реализовывают списки через кучу связанных Cons cells?

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

Есть ли какой-нибудь красивый и простой способ остаться на стандартных джавовских коллекциях, реализовать и список, и cons-ячейку, да еще и сделать, чтобы список был реализован непосредственно через cons'ы, либо наследовал от них?

Да. Просто делаешь списковые операции на коллекциях Java:

Cons(Item, LinkedList) -> LinkedList;
Cons(Item, Item) -> Pair
Car(LinkedList l) = l.first
Cdr(LinkedList l) = ... как в Java получить список со второго элемента?
monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

У тебя Scheme без Tail-call optimization? А как тогда циклы делаешь?

Ну, это все in progress.
С TCO в Джаве вообще проблема.
Tail-recursive calls, допустим, еще смогу как-то оптимизировать через какой-нибудь trampoline или tail recursion modulo cons (но это все еще TODO), а вот general tail calls вряд ли получится оптимизировать (это сложно, в той же Kawa по дефолту full TCO тоже выключен).

Еще не уверен, что полные continuations получится сделать.

Да. Просто делаешь списковые операции на коллекциях Java:

Примерно так и начал делать, но возникло много сложностей, например:

как в Java получить список со второго элемента?

list.sublist(1, list.size()); // cdr

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

В общем, думаю да, буду стараться использовать джавовские коллекции по максимому.

Есть ли какой-нибудь набор тестов для проверки правильности реализации Схемы?

kovrik ★★★★★ ()

Есть ли какой-то стандартных набор юнит тестов/кейсов на которых можно было бы тестировать свою имплементацию?

Нет. Можно использовать https://github.com/justinethier/husk-scheme/tree/master/tests

Т.е. если все эти тесты пройдены, то имплементация считается успешной.

Если придумаешь такой набор тестов хотя бы для функции (+ ...), то покажи. Тесты не могут гарантировать корректность программы.

monk ★★★★★ ()
Ответ на: комментарий от kovrik

Но проблема в том, что sublist возвращает не новый список.

cdr и не должен возвращать новый список

(define a (list 1 2 3))
(set-car! (cdr a) 4)
a ; => '(1 4 3)
monk ★★★★★ ()

Действительно ли везде берут Cons и из них создают связный список?

Да. Проблемы с производительностью решаются за счет GC, который умеет выделять память оптимально для консов.

Есть ли какой-то стандартных набор юнит тестов/кейсов на которых можно было бы тестировать свою имплементацию?

Стянуть тесты из какой-нибудь известной реализации?

anonymous ()

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

Они могут быть персисентными, что на языке других языков звучит примерно, как разделяемые данные. Это когда новая структура наследует до 99,99% от той, на основе которой была создана. При этом обе структуры будут совершенно разными и независимыми объектами.

Как я понимаю, с LinkedList такое не получится.

dave ★★★★★ ()

Продолжаю свою эпопею по имплементации r5rs на Java.

А чем тебе kawa не угодил? Можешь поглядеть все свои ответы там.

no-such-file ★★★★★ ()
Ответ на: комментарий от no-such-file

Да просто хочу свою реализацию написать, чем и занимаюсь. Просто интересно.
Да, реализаций полно, но:
1. Не хочется разбираться в готовом чужом коде. Хочется постепенно, по шагам, дойти самому.
2. Большинство реализаций включают в себя много оптимизаций и хаков. Из-за этого код становится сложночитаемым (по крайней мере для меня).

Т.е. цель всего этого - не создать промышленную реализацию r5rs. А понять, как оно работает, как это все можно сделать самому.

kovrik ★★★★★ ()
Ответ на: комментарий от monk

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

Сейчас у меня 3 варианта:

1. Придерживаться Java Collections API и использовать тамошний LinkedList + сделать дополнительную прослойку для Cons.
Вариант замечателен всем, кроме того факта, что, например, вышеупомянутый sublist() возвращает не просто sublist, а особую обертку (отдельный класс SubList), которая шарит элементы с оригинальным списком. Но при этом уже имеет другой класс.
А, следовательно, становятся невозможны вызовы вида (car (cdr (cdr '(1 2 3)))) - кидает ClassCastException.
А все потому, что джавовский LinkedList не дает доступа к своим Nodes, только к их значениям.
Жаль, но пока что я не нашел способа подружить их.

2. Второй вариант точно такой же, как и первый, только при вызовах типа sublist оборачивать все в новый список.
Car, cdr и тп. будут прекрасно работать, но тогда списки становятся иммутабельными и не получится сделать set-cdr!, например.

3. Третий вариант самый простой - отказаться от Java Collections API и полностью использовать уже написанный самодельный вариант Cons.
Все будет прекрасно работать. Но теряется Java Collections API + производительность.

kovrik ★★★★★ ()
Ответ на: комментарий от kovrik

вышеупомянутый sublist() возвращает не просто sublist, а особую обертку (отдельный класс SubList)

Судя по "http://www.docjar.com/docs/api/java/util/AbstractList.html#subList(int, int)" это всё равно List

Определяй car и cdr для List, а не для LinkedList

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 2)

не сильно разбираюсь в теме, но в jvm9(хахаха) обещали завезти TCO. в clojure поэтому есть recur, так что скорее всего в твоем тоже без такого не обойтись...

zarkone ★★ ()

Нашел на чем лисп, а особенно, схему реализовывать.

JVM не приспособлена для лиспов(а для схемы - особенно), им нужен отдельный свой, специализированный рантайм.

Коллекции JVM не используй вообще(кроме банальных массивов для схемовских векторов). Не используй джавовский стек. Храни фреймы в памяти(как ты, кстати с джавовским стеком то продолжения сделал?). Пиши свой байткод, который джавой выполняется линейно.

Либо делай не схему. Для CL хвостовая рекурсия не так критична, там обычно все делают итеративно. У Clojure, опять же - свои костыли на тему JVM.

Что до конкретных вопросов. Да, в лиспах обычные связные списки это тупо связанные CONS-ячейки. Насчет них существует куча оптимизаций в специализированных лисповых рантаймах. К примеру, в SBCL, NIL это, вообще, символ, но в SBCL указатели тегированные, и указатель с lowtag list-pointer(на x64 0b0111) может указывать либо на cons, либо на nil, и layout у символа в памяти такой, что car и cdr cons-ячейки лежат там, где у символа nil лежат ссылки на него же самого. Сам же NIL лежит в static space по константному адресу, поэтому например сравнение с ним делается простой инструкцией CMP.

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

lovesan ★☆ ()
Ответ на: комментарий от lovesan

Нашел на чем лисп, а особенно, схему реализовывать.

Да я это прекрасно понимаю.
Это была одна из целей хобби-проекта: посмотреть, как близко можно приблизиться к реализации Схемы на Джаве, понять, какие ограничения есть и тп.

Насчет тех же продолжений: так вон в Каве сделали (https://www.politesi.polimi.it/bitstream/10589/108685/3/2015_07_Bernardini.pdf).

Но, если честно, то пока что сомневаюсь, что так далеко зайду.

kovrik ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.