Следующая страница > 1 < [2]

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

kaizer131

Members


Статус

3 сообщений
http://www.global-live.net
Где: Russia
Род занятий: kaizer131
Возраст:

#2848   2010-09-14 16:08 GMT+3 часа(ов)      
Помогите пожалуйста с задачей
Определить рекурсивную функцию, возвращающую количество элементов в списке без какого-либо указываемого элемента.
В лиспе пока не силён поэтому обращаюсь к знающим людям.

misha

Moderators


Статус

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

#2851   2010-09-14 18:13 GMT+3 часа(ов)      
Без счетчика и учета циклических ссылок (CONS-циклов)
(defun len (l e)
(defun len0 (l n)
(if (consp l)
(+ (if (eq (car l) e) 0 1)
(len0 (cdr l) n))
n))
(len0 l 0))

отредактировал(а) misha: 2010-09-14 18:21 GMT+3 часа(ов)

ander-skirnir

Members


Статус

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

#2852   2010-09-14 21:41 GMT+3 часа(ов)      
misha, в common-lisp, в отличии от схем,
макрос defun всегда объявляет топлевельную функцию,
поэтому в этом варианте мы получаем аж две объявленных функции.

В cl для локальных функций используются формы flet и labels
(первая оптимизированее, но не поддерживает рекурсию).

Ну и по производительности можно было чуть улучшить - счётчик в len0 не обязателен.

(defun len (l e)
(labels
((len0 (l n)
(if (consp l)
(+ (if (eq (car l) e) 0 1)
(len0 (cdr l) n))
n)))
(len0 l 0)))
 
(defun count-without (e l)
(if l (+ (if (eq e (car l)) 0 1)
(count-without e (cdr l)))
0))
 
(defun count-without% (e l)
(labels ((rec (l)
(if l (+ (if (eq e (car l)) 0 1)
(rec (cdr l)))
0)))
(rec l)))
 
(time
(dotimes (i 100000000)
(len '(1 2 3 4 5) 3)))
 
#|
Evaluation took:
6.491 seconds of real time
6.489642 seconds of total run time (6.489642 user, 0.000000 system)
99.98% CPU
13,812,997,679 processor cycles
0 bytes consed
|#
 
(time
(dotimes (i 100000000)
(count-without 3 '(1 2 3 4 5))))
 
#|
Evaluation took:
6.296 seconds of real time
6.286840 seconds of total run time (6.286840 user, 0.000000 system)
99.86% CPU
13,398,279,113 processor cycles
0 bytes consed
|#
 
(time
(dotimes (i 100000000)
(count-without% 3 '(1 2 3 4 5))))
 
#|
Evaluation took:
6.234 seconds of real time
6.224440 seconds of total run time (6.224440 user, 0.000000 system)
99.84% CPU
13,265,632,174 processor cycles
0 bytes consed
|#

отредактировал(а) ander-skirnir: 2010-09-14 22:23 GMT+3 часа(ов)

misha

Moderators


Статус

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

#2854   2010-09-14 22:00 GMT+3 часа(ов)      
>misha, в common-lisp, в отличии от схем,
А кто сказал что речь шла именно о CL? Поэтому я реализовал как можно совместимее) мой код совместим даже с Lisp 1.5)

>Ну и по производительности можно было чуть улучшить - счётчик в len0 не обязателен.
А там нет никакого счетчика) там используется локальная переменная, причем ее значение не изменяется в процессе вычисления. Конечно её можно заменить константой)
Если бы Вы добавили счетчик, то общая производительность бы несколько возрасла засчет уменьшения нагрузки на стек.

отредактировал(а) misha: 2010-09-14 22:09 GMT+3 часа(ов)

misha

Moderators


Статус

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

#2855   2010-09-14 22:06 GMT+3 часа(ов)      
(define (len l e)
(foldr (lambda (a b) (+ (if (eq? a e) 0 1) b)) 0 l))

ander-skirnir

Members


Статус

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

#2857   2010-09-14 22:17 GMT+3 часа(ов)      
Да ладно, это распространённая путаница схемеров, пишущих на cl, и наоборот.
Я, например, в ужасе от костылей, которыми нужно обкладываться в ракете для топлевельных замыканий, связанных с локальным define

> там используется локальная переменная, причем ее значение не изменяется в процессе вычисления. Конечно её можно заменить константой)
Я, кстати, так и не понял, зачем она там вообще.

А правосторонняя свёртка здесь жутко медленная же:

(defun count-without (l e)
(reduce (lambda (a b) (+ (if (eq a e) 0 1) b)) l :from-end t))
 
(time
(dotimes (i 100000000)
(count-without '(1 2 3 4 5) 3)))
 
#|
Evaluation took:
26.581 seconds of real time
26.473369 seconds of total run time (26.410969 user, 0.062400 system)
[ Run times consist of 1.201 seconds GC time, and 25.273 seconds non-GC time. ]
99.59% CPU
56,563,481,732 processor cycles
5,600,020,336 bytes consed
|#

misha

Moderators


Статус

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

#2858   2010-09-14 22:21 GMT+3 часа(ов)      
>Я, например, в ужасе от костылей, которыми нужно обкладываться в ракете для топлевельных замыканий, связанных с локальным define
Приведите пример)

>А правосторонняя свёртка здесь жутко медленная же:
Вполне вероятно она реализована плохо.

misha

Moderators


Статус

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

#2859   2010-09-14 22:31 GMT+3 часа(ов)      
А хотя нет) Общая проблема сверток состоит в том, что приходится создавать промежуточный навый список.

ander-skirnir

Members


Статус

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

#2860   2010-09-14 22:33 GMT+3 часа(ов)      
> Вполне вероятно она реализована плохо.
Ну мужики иногда в шоке, что reduce в sbcl вытворяет - он там очень скоростной
А можете глянуть, как такой фолдр на ракетке отработает?
Мне кажется, проблема здесь в самом принципе правосторонней свёртки.

> Приведите пример)
Пожалуйста (:

common-lisp:
(let ((a 1) (b 2) (c 3))
(defun foo-a (...)
(...))
(defun foo-b (...)
(...))
(defun foo-c (...)
(...)))


racket:
(define-values (foo-a foo-b foo-c) 
(let ((a 1) (b 2) (c 3))
(define (foo-a ...)
(...))
(define (foo-b ...)
(...))
(define (foo-c ...)
(...))
(values foo-a foo-b foo-c)))


Но это еще такое дело. Главная причина, по которой я предпочитаю cl racket'у - это макро-замыкания с сайд-эффектами.
В ракете макросы очень статичные и не позволяют такого:
(let ((i 0))
(defmacro moo (...)
`(... ,(incf i) ...))
...другой-код-воздействующий-на-i...)

misha

Moderators


Статус

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

#2862   2010-09-14 23:19 GMT+3 часа(ов)      
На мой взгляд такое поведение CL ущербно) Объяснить почему?)

>В ракете макросы очень статичные и не позволяют такого:
Это не совсем так) Можно и без make-parameter
(define xx #f)
(let ((x (make-parameter 1)))
(define-syntax (counter syntax-object)
#'(lambda () (x (add1 (x))) (x)))
(set! xx (counter)))

misha

Moderators


Статус

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

#2863   2010-09-14 23:22 GMT+3 часа(ов)      
Как оказалось почти тоже самое, что ранее реализовал я:
(define (fold-right fun start lst . lsts)
(if (null? lsts)
(let foldr-lst ((l lst))
(if (null? l)
start
(fun (car l) (foldr-lst (cdr l)))))
(let foldr-lsts ((l (cons lst lsts)))
(if (do ((l l (cdr l)))
((or (null? (car l))
(null? (cdr l))) (null? (car l))))
start
(apply fun
(append (map car l)
(list (foldr-lsts (map cdr l)))))))))


Т.е. в нашем случае имеет место простая рекурсия.

ander-skirnir

Members


Статус

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

#2864   2010-09-14 23:40 GMT+3 часа(ов)      
> На мой взгляд такое поведение CL ущербно) Объяснить почему?)
Валяйте, но это удобно, гибко, и этому посвящена целая книга.

Цитата
misha :
>В ракете макросы очень статичные и не позволяют такого:
Это не совсем так) Можно и без make-parameter
(define xx #f)
(let ((x (make-parameter 1)))
(define-syntax (counter syntax-object)
#'(lambda () (x (add1 (x))) (x)))
(set! xx (counter)))




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

Что Вы сделали:
(define (foo-a) (xx))
(define (foo-b) (xx))
> (foo-a)
2
> (foo-a)
3
> (foo-a)
4
> (foo-b)
5


Что имелось ввиду:
(let ((i 0))
(defmacro moo ()
(incf i)))
 
(defun f1 () (moo))
(defun f2 () (moo))
(defun f3 () (moo))
 
> (f1)
1
> (f1)
1
> (f1)
1
> (f2)
2
> (f3)
3
> (f1)
1

misha

Moderators


Статус

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

#2865   2010-09-15 00:15 GMT+3 часа(ов)      
>Речь шла о замкнутом на переменную макросе.
Макрос не замкнут на переменную, он просто подставляет константу полученную в результате вычисления (incf i)

>Что имелось ввиду:
Типа это)
(define-values (a b c)
(let ((x (make-parameter 0)))
(define-syntax (counter syntax-object)
#'(let() (x (add1 (x))) (x)))
(values (counter) (counter) (counter))))

misha

Moderators


Статус

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

#2866   2010-09-15 00:20 GMT+3 часа(ов)      
>Валяйте, но это удобно, гибко, и этому посвящена целая книга.
Просто мне нравится Racket, а Вам CL - вот собственно и все) И холивар разводить не стоит)

ander-skirnir

Members


Статус

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

#2877   2010-09-15 06:09 GMT+3 часа(ов)      
> Просто мне нравится Racket, а Вам CL - вот собственно и все) И холивар разводить не стоит)
На самом деле я бы с радостью перешёл на рэкит, если бы не эти ограничения. Потому меня это всё так и расстраивает

Цитата
misha :
>Что имелось ввиду:
Типа это)
(define-values (a b c)
(let ((x (make-parameter 0)))
(define-syntax (counter syntax-object)
#'(let() (x (add1 (x))) (x)))
(values (counter) (counter) (counter))))




Не в обиду, но мне это напомнило "метапрограммирование шаблоны c++"
Вообще, ограничение макросов пределами одной фазы кажется преступлением против лиспа.
Вы на фазе компиляции прибиндили 3 константы к 3 переменным, и что? Это опять не макрос с сайд эффектом.
Не могли бы Вы, пожалуйста, привести аналог вышеописанного макроса moo?

А желательно сразу что-то такое (чтобы макросы и функции замыкались по одним и тем же переменным):
(let ((i 0))
(defun get-current-date ()
(intern (concatenate 'string
(format nil "~a" (incf i))
".09.2010"))))
 
(let ((pw "qwerty"))
 
(defun set-password (new-pw)
(setf pw new-pw))
 
(defmacro entry (&body body)
`(defun ,(get-current-date) (password)
(if (string= password ,pw)
(progn ,@body)
(error "Access denied!")))))
 
(macroexpand-1 '(entry "test entry"))
 
#|
(DEFUN |3.09.2010| (PASSWORD)
(IF (STRING= PASSWORD "qwerty")
(PROGN "test entry")
(ERROR "Access denied!")))
|#
 
(set-password "my-secret-diary")
 
(macroexpand-1 '(entry '(this is private entry)))
#|
(DEFUN |4.09.2010| (PASSWORD)
(IF (STRING= PASSWORD "my-secret-diary")
(PROGN '(THIS IS PRIVATE ENTRY))
(ERROR "Access denied!")))
|#




> Макрос не замкнут на переменную, он просто подставляет константу полученную в результате вычисления (incf i)

Ну так это оно и есть. Используя в cl в макросе мутабельную форму, мы по сути неявно задаём самомодифицируемый макро-трансформер.

kaizer131

Members


Статус

3 сообщений
http://www.global-live.net
Где: Russia
Род занятий: kaizer131
Возраст:

#2878   2010-09-15 12:02 GMT+3 часа(ов)      
Познавательная дискуссия , а можно комментарии к коду

(defun len (l e)
 
(defun len0 (l n)
 
(if (consp l)
 
(+ (if (eq (car l) e) 0 1)
 
(len0 (cdr l) n))
 
n))
 
(len0 l 0))

В часности не могу сообразить последовательность аргументов при вызове
функции len

Raino

Members


Статус

18 сообщений

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

#2881   2010-09-15 17:55 GMT+3 часа(ов)      
Если голова списка равна искомому элементу, то пропускает его и вызывает себя же, передавая хвост списка. Если голова не равна, то добавляет к обработанному хвосту еще единицу. Зачем там n не знаю, судя по всему оно хранит "количество элементов в пустом списке, которые не равны заданому элементу", т.е. 0.

kaizer131

Members


Статус

3 сообщений
http://www.global-live.net
Где: Russia
Род занятий: kaizer131
Возраст:

#2882   2010-09-15 18:00 GMT+3 часа(ов)      
хорошо , а как передать функции список в котором необходимо произвести поиск и элемент количество вхождений которого необходимо подсчитать ?
PS: Оказывается не так просто после С++ и паскаля "мыслить" на лиспе.

misha

Moderators


Статус

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

#2883   2010-09-15 18:26 GMT+3 часа(ов)      
>Не могли бы Вы, пожалуйста, привести аналог вышеописанного макроса moo?
Программа на Racket состоит из модулей, поэтому сначала код трансформируется и переобразуется макросами, а затем уже компилируется и выполняется. Т.е. после трансформации код уже не содержит макросов. Поэтому Ваша просьба не выполнима.

>Используя в cl в макросе мутабельную форму, мы по сути неявно задаём самомодифицируемый макро-трансформер.
Для написания полиморфных макросов необходимо взаимодействовать с макро-трансформерами, например,
(define-for-syntax i 0)
 
(define-syntax (moo stx)
(datum->syntax stx (let () (set! i (add1 i)) i)))
 
(define-values (a b c) (values (moo) (moo) (moo)))
для более сложных задач необходимо создавать собственные трансформеры (этому посвящена целая глава).

CL-макросы посути представляют собой замыкания, со всеми вытекающими) например, если Вы при написании макроса допустили ошибку, то о ней Вы узнаете только во время выполнения программы.

misha

Moderators


Статус

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

#2884   2010-09-15 18:30 GMT+3 часа(ов)      
Цитата
kaizer131 :
хорошо , а как передать функции список в котором необходимо произвести поиск и элемент количество вхождений которого необходимо подсчитать ?
PS: Оказывается не так просто после С++ и паскаля "мыслить" на лиспе.

(len '(a s d f s) 's)

LinkFly

Members


Статус

152 сообщений

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

#2885   2010-09-15 22:16 GMT+3 часа(ов)      
На CL:
(count 's '(a b s c d s m n))
Тяжело привыкнуть к простоте? ;)

misha

Moderators


Статус

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

#2897   2010-09-16 15:27 GMT+3 часа(ов)      
Я проанализировал поведение макросов со слайд-эффектом в Clisp и SBCL, и сделал неутишительный для поклонников CL вывод: только в простых случаях можно ожидать желаемый результат.
[1]> (defun t ()
(let ((i 0))
(defmacro moo ()
(incf i))
(defun c () (moo))))
T
[2]> (t)
C
[3]> (c)
1
[4]> (c)
2
[5]> (c)
3
[6]> (c)
SBCL с этим не справился, как впрочем и с
(let ((i 0))
(defmacro moo ()
(incf i))
(defun f1 () (moo))
(defun f2 () (moo)))

ВЫВОД: ПРИМЕНЕНИЕ МАКРОСОВ СО СЛАЙД-ЭФФЕКТОМ МОЖЕТ ПРИВЕСТИ К НЕПРЕДСКАЗУЕМЫМ ПОСЛЕДСТВИЯМ.

ander-skirnir

Members


Статус

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

#2901   2010-09-16 19:36 GMT+3 часа(ов)      
А оно и не должно работать. Дело в том, что сlisp - самый кривой и бажный компилятор common-lisp'а из известных. И эффект "работы" этого кода странный - вызов с всегда должен возвращать одно и то же значение.

Вот как это делается:

(defmacro defun! (name &rest definition)
`(compile ',name '(lambda ,@definition)))
(let ((i 0))
(defmacro moox ()
(incf i))
(defun! f1 () (moox))
(defun! f2 () (moox)))


(f1) ;> 1
(f1) ;> 1
(f2) ;> 2
(f1) ;> 1
...

misha

Moderators


Статус

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

#2902   2010-09-16 19:51 GMT+3 часа(ов)      
>А оно и не должно работать.
И на SBCL должно работать, только правильно. Но не работает ведь)

>И эффект "работы" этого кода странный
Непредсказуемый результат ведь)

>Вот как это делается:
Не признаете опасности слайд-эффекта? Вы можете оправдывать недостатки Cl сколько Вам угодно, но я уже убедился в том, что макросы со слайд-эффектом не есть тру)

ander-skirnir

Members


Статус

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

#2903   2010-09-16 20:31 GMT+3 часа(ов)      
> И на SBCL должно работать, только правильно. Но не работает ведь)
Нет, не должно. Это некорректный код, и его работоспособность является ошибкой компилятора.

> Непредсказуемый результат ведь)
А какой еще эффект ожидать от некорректного кода?

> Не признаете опасности слайд-эффекта?
Сайд(side, побочный)-эффекты по определению опасны. Нужна хорошая самодисциплина и понимание того, что делаешь.

> я уже убедился в том, что макросы со слайд-эффектом не есть тру)
Ну, наверное, так даже лучше, ведь в ином случае Вам было бы очень обидно

misha

Moderators


Статус

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

#2905   2010-09-16 20:45 GMT+3 часа(ов)      
>Это некорректный код, и его работоспособность является ошибкой компилятора.
Это Вы так считаете)

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

ander-skirnir

Members


Статус

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

#2906   2010-09-16 21:03 GMT+3 часа(ов)      
> Это Вы так считаете)
Стандарт так считает: http://www.lispworks.com/documentation/HyperSpec/Issues/iss104_w.htm

> Так все-таки признаете...
Конечно же нет. Я имел ввиду, что если бы Вы не включили подсознательно механизм вытеснения пользы таких макросов, Вам стало бы очень обидно, что в ракете ничего такого и в помине нет.

misha

Moderators


Статус

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

#2907   2010-09-16 21:17 GMT+3 часа(ов)      
>что в ракете ничего такого и в помине нет.
Если мне это потребуется, то я это реализую в качестве дополнительной библиотеки. И если Вы думаете, что компилятору поступает точно такой же код, что Вы написали, то Вы глубоко ошибаетесь.

>механизм вытеснения пользы таких макросов
Если мне потребуется получить какую либо информацию в процессе работы макроса, то Racket позволяет это сделать. А Вы знали об этой возможности? И это не сайд-эффект) А другой пользы от него я не вижу.

misha

Moderators


Статус

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

#2909   2010-09-17 01:56 GMT+3 часа(ов)      
Эмуляция сайд-эффекта)
> (module side-effect racket
(provide f1 f2 foo)
 
(define-for-syntax shared-x 0)
 
(define-syntax (compile-shared-x stx)
(datum->syntax stx shared-x))
 
(define-syntax (moo stx)
(datum->syntax stx (let () (set! shared-x (add1 shared-x)) shared-x)))
 
(define f1 (moo))
(define (f2) (moo))
(define (foo) (set! x (add1 x)) x)
 
(define x (compile-shared-x)))
> (require 'side-effect)
> f1
1
> (foo)
3
> (foo)
4
> (f2)
2
> f1
1
Считайте это аналогом
(defmacro defun! (name &rest definition)
`(compile ',name '(lambda ,@definition)))
 
(let ((i 0))
(defmacro moox ()
(incf i))
(defun! f1 () (moox))
(defun! f2 () (moox)))

LinkFly

Members


Статус

152 сообщений

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

#2926   2010-09-19 14:01 GMT+3 часа(ов)      
Код на CL вообще не грамотный.
Так может писать человек не представляющий что значат в CL стадии обработки кода.
ander-skirnir прав - у вас явно какое-то предубеждение.


Онлайн :

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