Не понимаю списки в Lisp

l = cons h t

l - это список полученный из списка t добавлением элемента h слева

Потому что cons приделывает голову к хвосту списка, т.е. 1-й аргумент - 1-й элемент результата, 2-й аргумент - список к которому приделать первый. При чем тут структура списков - непонятно.

Чтобы в результате было ((1 2) (3 4)) надо (cons (list 1 2) (list (list 3 4))), то есть к списку из одного элемента (list 3 4) приделать спереди еще один элемент (list 1 2).

А (cons (list 1 2) (list 3 4)) значит к списку из 2 элементов 3 и 4 приделать элемент (list 1 2).

man cons. 1й параметр - новый элемент списка, а 2й - список, куда добавить. Для результата ((1 2) (3 4)) нужно (list (list 1 2) (list 3 4)).

Теперь стало более ли менее ясно, но остается 1 нюанс: что же такое (cons x y), если y - атом?

cons вообще создает пару. proper list - это пара ( из пары и далее рекурсивно), которая в конце концов терминируется пустым списком. improper list - соответственно когда терминируется чем-то другим.

Значит, (cons (cons 1 2) 3) - это как бы пара, левая часть которой пара (1 . 2), а правая - атом 3?

угу, типа того.

> (cons (cons 1 2) 3)
((1 . 2) . 3)

Список в Lisp - это односвязный список. (1 2 3 4) - сокращённая запись такой фигни: указатель на пару, где первый элемент - 1, а второй - указатель на пару, где первый элемент - 2, а второй - указатель на пару, где первый элемент - 3, а второй - указатель на пару, где первый элемент - 4, а второй - нулевой указатель. Функция cons сооружает пару из двух её аргументов и возвращает указатель на неё.

SICP почитай, иллюстрации посмотри, все сразу прояснится.

А как в лиспе сделать двусвязный список? В особенности кольцевой двусвязный список?

Использовать вектора, структуры, или те же списки но с некоторым оверхедом. И setf, конечно же.

Т.е. создать вручную элемент списка, в котором были бы два "указателя" - на предыдущий и на последующий элемент? Дело в том, что я посоветовал знакомой использовать лисп для курсовой. Тема была по обработке текста. Та курсовая успешно закончена, следующее курсовая по теме, в которой явно участвует двунаправленный кольцевой список. Вот и непонятно, следующую курсовую её делать также на лисп, или имеет смысел поюзать с например. Меня вопрос о двусвязных колцевых списках в лисп поставил в тупик :(

Лисп сасет в этом отношении...

А в чем проблема? Вот на scheme элементарный пример:

(define get-value car)
(define get-next cadr)
(define get-prev caddr)
(define (insert-after elt val)
  (let* ((next (get-next elt))
        (new-next (list val next elt)))
    (set-car! (cdr elt) new-next)
    (set-car! (cddr next) new-next)
    new-next))
(define (make-ring a b . others)
  (let* ((x (list a))
        (y (list b x x)))
    (set-cdr! x (list y y))
    (foldr insert-after y others)))

Пусть следующую на OCaml делает. Или на Haskell.