Форум программистов, компьютерный форум, киберфорум
Наши страницы
Clojure
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.93/14: Рейтинг темы: голосов - 14, средняя оценка - 4.93
dserp18
27 / 12 / 1
Регистрация: 20.01.2013
Сообщений: 137
Записей в блоге: 6
1

Реализация ф-ций CONS, CAR, CDR (Sheme,CLisp)

05.11.2016, 12:16. Просмотров 2778. Ответов 47
Метки нет (Все метки)

В книге SICP описан алгоритм реализации функций CONS,CAR,CDR на языке Sheme
Lisp
1
2
3
4
5
6
7
8
define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Аргумент не 0 или 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
Вот как я реализовал в CLisp
Lisp
1
2
3
4
5
6
7
8
9
10
(defun cons(x y) 
(defun dispatch (m)
(cond 
((eq m 0) x)
((eq m 1) y)
((and(not (eq m 1))(not(eq m 0))) "Аргумент не 0 или 1")
))
)
(defun car(z)(funcall z 0))
(defun cdr(z)(funcall z 1))
Но, наверное, этот же алгоритм можно реализовать с помощью глобальных переменных defvar
Что-то типа этого
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defvar m 0)
(defvar x 0)
(defvar y 0)
(defun dispatch (m)
(cond 
((= m 0) x)
((= m 1) y)
((> m 1) "Arg is not 0 or 1")
))
(defun cons(x y) (dispatch m))
(defun car(z)(funcall z  0))
(defun cdr(z)(funcall z  1))
Но тут что-то не то. Как вызвать dispatch из cons,вызвать cons из car или cdr
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2016, 12:16
Ответы с готовыми решениями:

Композицией базовых функций CAR, CDR, CONS, LIST
Добрый день! прошу помочь в решении задачи: Композицией базовых функций CAR, CDR, CONS, LIST...

Lisp. По какому принципу работают функции CAR,CDR,CONS?
Здравствуйте! Помогите пожалуйста понять как работают функции CAR,CDR,CONS. Например, есть список:...

Работа со списками в LISP, используя базовые функции CAR, CDR, CONS
Дан список ( (A B ( C ) ) (D (E) (K L M))) получить: список (C) список (A B C D) ...

Заменить каждый второй элемент списка на 0,используя только рекурсию, CAR, CDR, CONS,COND
Заменить каждый второй элемент списка на 0,используя только рекурсию, CAR, CDR, CONS,COND

каждый нечетный элемент списка умножить на 2, каждый четный на 3. использовать только рекурсию CAR,CDR,COND,CONS
каждый нечетный элемент списка умножить на 2, каждый четный на 3. использовать только рекурсию ...

47
_Ivana
4062 / 1896 / 237
Регистрация: 01.03.2013
Сообщений: 5,147
Записей в блоге: 22
11.11.2016, 20:27 21
Нет, никакого двумерного синтаксиса и отступозависимости - все одномерно и парсуемо по лиспу - в списки.
0
vlisp
566 / 540 / 116
Регистрация: 10.08.2015
Сообщений: 2,056
Завершенные тесты: 1
11.11.2016, 21:19 22
Цитата Сообщение от _Ivana Посмотреть сообщение
парсуемо по лиспу
глупости, в лиспе выражения обрамляются скобками и весь список однозначно интерпретируется, а тут отсебятина, интерпретатор берет и добавляет скобки без спросу... лучше б он кофе умел варить
0
_Ivana
4062 / 1896 / 237
Регистрация: 01.03.2013
Сообщений: 5,147
Записей в блоге: 22
11.11.2016, 22:43 23
Цитата Сообщение от vlisp Посмотреть сообщение
глупости
в этой теме пишете вы, причем с завидной настойчивостью. Но это никому не вредит: ТС-у все равно, а остальным - забава
0
Catstail
12.11.2016, 13:34
  #24

Не по теме:

vlisp, _Ivana, - не ругайтесь...

0
dserp18
27 / 12 / 1
Регистрация: 20.01.2013
Сообщений: 137
Записей в блоге: 6
15.11.2016, 22:20  [ТС] 25
Вот если бы _Ivana предоставил больше информации по реализации своего диалекта Lisp'а на Java, начав с описания фундаментальных концепций самой Java, это помогло бы изучающим лучше понять и Lisp и Java, но судя по публикациям на Хабре он этого делать не собирается
0
_Ivana
4062 / 1896 / 237
Регистрация: 01.03.2013
Сообщений: 5,147
Записей в блоге: 22
16.11.2016, 01:33 26
dserp18, хорошо, давайте подумаем над некоторыми вопросами.

1. Где предоставлять эту информацию?

- на хабре? не тот формат, и другие причины против этого.

- на этом форуме? можно, но я и так создал несколько тем по тем вопросам, которые кажутся мне интересными. Как вы заметили, здесь нет подразделов (хотя разных версий лиспов очень много). Даже модератор не создает свой отдельный раздел по HomeLisp, хотя по нему вопросы возникают у студентов регулярно. Хотя в принципе возможны 2 варианта - в отдельно созданных подразделах или в общем потоке тем.

- на отдельном персональном сайте, как HomeLisp? У меня нет сайта, и создавать его под этот проект имхо неоправданно.

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

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

2. Что, о чем, и в каком объеме рассусоливать?

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

ЗЫ есть множество реализаций разных лиспов на разных языках: https://github.com/kanaka/mal и много других. На фоне этого изобилия мой проект не является чем-то уникальным - он не самый быстрый, и т.п. Единственно что - наверное реализация на haskell может похвастаться лаконичностью - 250 строк на все на свете вместе в парсером. Поэтому я не уверен, что имеет смысл писать пространные статьи, описывающие никому не нужный очередной интерпретируемый лисп-диалект.

ЗЗЫ и конечно вы сами можете создать здесь тему, где оформите интересующие вас вопросы, а я отвечу. Будет прямая обратная (каламбурчик) связь, по запросам, без гаданий с моей стороны что интересно читающим
1
dserp18
27 / 12 / 1
Регистрация: 20.01.2013
Сообщений: 137
Записей в блоге: 6
18.11.2016, 23:44  [ТС] 27
Спасибо. Понял )) Пока пытаюсь "продраться через систему типов" на Hasckell. А вообще, с чего надо начать работу по реализации собственного диалекта, например, на Java?
0
_Ivana
4062 / 1896 / 237
Регистрация: 01.03.2013
Сообщений: 5,147
Записей в блоге: 22
18.11.2016, 23:53 28
Лучший ответ Сообщение было отмечено dserp18 как решение

Решение

Цитата Сообщение от dserp18 Посмотреть сообщение
Пока пытаюсь "продраться через систему типов" на Hasckell
имхо, это порой весьма непросто
Цитата Сообщение от dserp18 Посмотреть сообщение
с чего надо начать работу по реализации собственного диалекта
диалекта чего? Лиспа - со ссылок, которые я в изобилии давал в этом разделе форума. И с книжки "Лисп ин смалл писиз" Кристиана Кеннека. Схемы - с половины вышеупомянутых ссылок, с "Райт ё схеме ин 48 хаурс" и конечно же СИКП. Собственно, мне хватило СИКПа и трети "Райт ё схеме". Но для всяких оптимизирующих компиляторов/интерпретаторов надо курить более серьезные вещи. Хотя то же ТСО можно и самому на коленке сделать.
3
dserp18
27 / 12 / 1
Регистрация: 20.01.2013
Сообщений: 137
Записей в блоге: 6
14.01.2017, 21:29  [ТС] 29
Хочу обратить внимание участников форума на онлайн курсы по изучению функционального программирования
Lisp
https://openedu.ru/
Haskell
http://welcome.stepik.org/ru
Scala
https://ru.coursera.org/
Курсы условно-бесплатные (оплачивается только сертификат)
1
asmquest
Заблокирован
15.01.2017, 10:30 30
Цитата Сообщение от _Ivana Посмотреть сообщение
Эта реализация абстракции списка
это абстракция пары, а не списка
Цитата Сообщение от _Ivana Посмотреть сообщение
через замыкания
замыкания, как таковые, тут не при чем, просто в схеме нет нормальной объектной нотации и все приходится писать через жопу, имитируя объекты замыканиями
Цитата Сообщение от _Ivana Посмотреть сообщение
меня в свое время тоже весьма впечатлила и вдохновила
Там нет ничего особенного. У новичков глаза на лоб лезут из-за подобных финтов ушами из-за того, что в схеме слишком много сахарной подковерной возни, она форсит подход, когда о простых вещах приходится думать в сложной манере, продираясь сквозь дебри неочевидного синтаксиса. Если бы вы провели декомпозицию данного кода, и воспроизвели бы его без этого блевотного "функционального" сахара, сразу стало бы все очевидно. Вот эквивалент, написанный на Io:
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
Pair := Object clone do(
  first := method(x)
  rest := method(y)
  cons := method( x, y,
     pair := self clone
     pair x := x
     pair y := y 
     pair
  )
)
 
Pair cons(1, 2) first #>>>> 1
Pair cons(1, 2) rest  #>>>> 2
Абсолютно прозрачный код
0
nullxdth
1890 / 854 / 65
Регистрация: 12.03.2013
Сообщений: 3,973
17.01.2017, 19:30 31
Цитата Сообщение от dserp18 Посмотреть сообщение
Вот как я реализовал в CLisp
Это кривая реализация.
Цитата Сообщение от dserp18 Посмотреть сообщение
Но, наверное, этот же алгоритм можно реализовать с помощью глобальных переменных defvar
Не стоит.
Цитата Сообщение от asmquest Посмотреть сообщение
замыкания, как таковые, тут не при чем, просто в схеме нет нормальной объектной нотации и все приходится писать через жопу, имитируя объекты замыканиями
Для красивой реализации этой задачи не нужен никакой ООП. Достаточно замыканий.
А так-то Scheme которая в ходу с ООП всё не плохо: https://docs.racket-lang.org/reference/mzlib_class.html
Цитата Сообщение от asmquest Посмотреть сообщение
У новичков глаза на лоб лезут из-за подобных финтов ушами из-за того, что в схеме слишком много сахарной подковерной возни
В Scheme как и в CL минимум синтаксиса и следовательно с синтаксисом нет никакой "подковёрной возни", скорее наоборот - всё понятно, единообразно и симметрично.
Цитата Сообщение от asmquest Посмотреть сообщение
и воспроизвели бы его без этого блевотного "функционального" сахара
Пример "блевотного функционального сахара" можно?
Цитата Сообщение от asmquest Посмотреть сообщение
Вот эквивалент, написанный на Io
Цитата Сообщение от asmquest Посмотреть сообщение
Абсолютно прозрачный код
Я бы не сказал, куча каких-то сущностей беспонтовых, методы, клоны, да self-ы
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defun cons% (car cdr)
  (lambda (sym)
    (ecase sym
      (car car)
      (cdr cdr))))
 
(defun car% (c)
  (funcall c 'car))
 
(defun cdr% (c)
  (funcall c 'cdr))
 
(let ((xs (cons% 1 (cons% 2 (cons% 3 nil)))))
  (car% (cdr% (cdr% xs))))
 
;; 3
Вот. Чисто и понятно

Добавлено через 24 минуты
Цитата Сообщение от helter Посмотреть сообщение
числа нельзя сравнивать с помощью eq (это оговорено в стандарте), нужно использовать или eql
Хех. И правда. А я не знал. Лет 10 уже на CL пишу и не знал.
В clhs есть пример вводящий в заблуждение:
http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.htm
Lisp
1
(eq 3 3) =>  true
Хотя далее идёт примечание:
An implementation is permitted to make ``copies'' of characters and numbers at any time. The effect is that Common Lisp makes no guarantee that eq is true even when both its arguments are ``the same thing'' if that thing is a character or number.
Добавлено через 3 минуты
Цитата Сообщение от dserp18 Посмотреть сообщение
Ну, наверное, можно сделать такую реализацию Лиспа с отступами как в Python. Это уже кому что больше нравится.
Золотце делал как-то на 0chan-е такое, помнится
3
antares0
249 / 118 / 8
Регистрация: 12.05.2015
Сообщений: 172
18.01.2017, 22:43 32
Цитата Сообщение от dserp18 Посмотреть сообщение
Ну, наверное, можно сделать такую реализацию Лиспа с отступами как в Python. Это уже кому что больше нравится.
Вот не надо делать отдельную и не с чем не совместимую
А просто python-like синтаксис для CL на отступах вот - cl-2dsyntax

Добавлено через 6 минут
Цитата Сообщение от dserp18 Посмотреть сообщение
Хочу обратить внимание участников форума на онлайн курсы по изучению функционального программирования ...
Только лучше бы такие ссылки складывать хотя бы в прикрепленную тему о литературе. А в этой они утонут и о них никто не узнает
1
asmquest
Заблокирован
18.01.2017, 23:56 33
Цитата Сообщение от nullxdth Посмотреть сообщение
числа нельзя сравнивать с помощью eq (это оговорено в стандарте)
lol, если нельзя сравнивать, то какого же хрена он сравнивает? Ах, да, это потому что там.
Цитата Сообщение от nullxdth Посмотреть сообщение
всё понятно, единообразно и симметрично.
Причем настолько все всё понятно, единообразно и симметрично, что
Цитата Сообщение от nullxdth Посмотреть сообщение
Лет 10 уже на CL пишу и не знал.
Добавлено через 34 минуты
nullxdth, кстати, прямое следствие отсутствия нормального ООП и полиморфизма. Дабы не плодить сущности, можно было бы унифицировать все одним словом, скажем equal, и это диспетчирезовалось бы в зависимости от того, какой тип/подтип получает сообщение.
0
nullxdth
1890 / 854 / 65
Регистрация: 12.03.2013
Сообщений: 3,973
19.01.2017, 00:14 34
Цитата Сообщение от asmquest Посмотреть сообщение
если нельзя сравнивать, то какого же хрена он сравнивает?
А что, не должна? Какое поведение на твой взгляд было бы логичным? eq проверяет идентичность объектов. Просто по стандарту допускается такая реализация CL, где eq на одинаковых (с виду ) числах или символах может давать nil. Причину цитировал.
Цитата Сообщение от asmquest Посмотреть сообщение
Причем настолько все всё понятно, единообразно и симметрично, что
Моё незнание не показатель. Я много чего не знаю.

Добавлено через 5 минут
Цитата Сообщение от asmquest Посмотреть сообщение
кстати, прямое следствие отсутствия нормального ООП и полиморфизма
Ого! Видимо, не в курсе, что на сегодняшний день самая фичастая реализация ООП (в мире ) в Common Lisp. CLOS называется. Вот теперь будешь знать.

Добавлено через 2 минуты
Цитата Сообщение от asmquest Посмотреть сообщение
Дабы не плодить сущности, можно было бы унифицировать все одним словом
Ага. И проиграть по производительности на runtime диспетчеризации.

Добавлено через 3 минуты
Цитата Сообщение от asmquest Посмотреть сообщение
equal
eq, eql, equal, equalp
Можно выбрать меру обобщений и использовать в зависимости от ситуации.
0
asmquest
Заблокирован
19.01.2017, 00:16 35
Цитата Сообщение от nullxdth Посмотреть сообщение
Какое поведение на твой взгляд было бы логичным?
Падать с ошибкой. Иначе отладка может продлиться на годы.
0
nullxdth
1890 / 854 / 65
Регистрация: 12.03.2013
Сообщений: 3,973
19.01.2017, 00:17 36
Цитата Сообщение от antares0 Посмотреть сообщение
А просто python-like синтаксис для CL на отступах вот - cl-2dsyntax
Забавно.
0
asmquest
Заблокирован
19.01.2017, 00:18 37
Цитата Сообщение от nullxdth Посмотреть сообщение
И проиграть по производительности
CL все еще считается языком высокого уровня, или я отстал от жизни?
0
nullxdth
1890 / 854 / 65
Регистрация: 12.03.2013
Сообщений: 3,973
19.01.2017, 00:22 38
Цитата Сообщение от asmquest Посмотреть сообщение
Падать с ошибкой.
Смысл eq в скорости. Фактически eq - это сравнение адресов (на сколько я понимаю). Дополнительных проверок не осуществляется. Если проверки нужны, следует использовать специализированные функции сравнения для конкретных типов. Собственно я всегда сравнивал числа функцией "=" и, видимо, поэтому никогда не сталкивался с вышеописанной потенциальной проблемой.
1
asmquest
Заблокирован
19.01.2017, 00:30 39
Цитата Сообщение от nullxdth Посмотреть сообщение
Фактически eq - это сравнение адресов (на сколько я понимаю)
Если я не ошибаюсь, числа и строки в CL являются примитивами. Поэтому, это еще умудриться надо сделать так, чтобы это не работало для чисел и строк единообразно. Кривизна дизайна наружу тут торчит. Любые примитивные типы можно легко сравнить по адресам.
0
nullxdth
1890 / 854 / 65
Регистрация: 12.03.2013
Сообщений: 3,973
19.01.2017, 00:32 40
Цитата Сообщение от asmquest Посмотреть сообщение
CL все еще считается языком высокого уровня, или я отстал от жизни?
Хм. А с каких пор повелось считать высокоуровневые языки обязались быть тормозными?
Common Lisp - язык сверхвысокого уровня и вместе с тем промышленного рода. Он проектировался с учётом написания эффективных реализаций.
1
19.01.2017, 00:32
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2017, 00:32

car и cdr
Выделите с помощью комбинации вызовов “car” и “cdr” элементы x, y, z из следующих списков, а также...

Car и Cdr
Выделите с помощью комбинации вызовов “car” и “cdr” элементы x, y, z из следующих списков, а...

функции CAR и CDR
На языке Лисп составьте композицию из функций CAR и CDR, для которой результатом применения этой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru