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

Возможно, мои костыли и велосипеды вам в чем-то помогут: https://github.com/Ivana-/Liscript-GUI-Java-Swing

ЗЫ ни джаву ни схему не знаю, лепил по фантазии.

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

У тебя 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 получить список со второго элемента?

У тебя 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 возвращает не новый список.
Поэтому приходится оборачивать это все в создание нового списка.

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

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

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

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

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

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

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

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

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

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

О, спасибо!

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

Да, действительно.

Спасибо за помощь!

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

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

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

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

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

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

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

Тут написано как сделать функциональный лист на плюсах. Можно наверное адаптировать под джаву

https://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/

https://github.com/BartoszMilewski/Okasaki/blob/master/List/List.h

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

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

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

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

Может от суда что-то пригодится - CDR coding http://cpsc.yale.edu/sites/default/files/files/tr362.pdf

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

Сейчас у меня 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 + производительность.

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

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

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

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

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

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 это еще более верно.

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

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

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

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