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

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

|#

(define (len l e)

 (foldr (lambda (a b) (+ (if (eq? a e) 0 1) b)) 0 l))

>Я, например, в ужасе от костылей, которыми нужно обкладываться в ракете для топлевельных замыканий, связанных с локальным define
Приведите пример)

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

> Вполне вероятно она реализована плохо.
Ну мужики иногда в шоке, что 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...)

Как оказалось почти тоже самое, что ранее реализовал я:

(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)))))))))

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

>Речь шла о замкнутом на переменную макросе.
Макрос не замкнут на переменную, он просто подставляет константу полученную в результате вычисления (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))))

> Просто мне нравится 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 в макросе мутабельную форму, мы по сути неявно задаём самомодифицируемый макро-трансформер.

Если голова списка равна искомому элементу, то пропускает его и вызывает себя же, передавая хвост списка. Если голова не равна, то добавляет к обработанному хвосту еще единицу. Зачем там n не знаю, судя по всему оно хранит "количество элементов в пустом списке, которые не равны заданому элементу", т.е. 0.

>Не могли бы Вы, пожалуйста, привести аналог вышеописанного макроса 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-макросы посути представляют собой замыкания, со всеми вытекающими) например, если Вы при написании макроса допустили ошибку, то о ней Вы узнаете только во время выполнения программы.

На CL:
(count 's '(a b s c d s m n))
Тяжело привыкнуть к простоте? ;)

А оно и не должно работать. Дело в том, что с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
...

> И на SBCL должно работать, только правильно. Но не работает ведь)
Нет, не должно. Это некорректный код, и его работоспособность является ошибкой компилятора.

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

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

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

> Это Вы так считаете)
Стандарт так считает: http://www.lispworks.com/documentation/HyperSpec/Issues/iss104_w.htm

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

Эмуляция сайд-эффекта)

> (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)))