Чисто функциональная реализация стека со схемой

ProgramBox

Чисто функциональная реализация стека со схемой

Post author:admin
Запись опубликована:25 февраля, 2023
Post category:Вопросы по программированию

#functional-programming #stack #scheme #purely-functional

#функциональное программирование #стек #схема #чисто функциональный

Вопрос:

Я хотел бы реализовать функциональный стек в схеме. Это моя попытка:

 (define make-stack
  (letrec ((do-op
            (lambda (stack op . val)
              (cond ((eq? op 'push)
                     (lambda (op . v)
                       (do-op (cons (car val) stack) op v)))
                    ((eq? op 'pop)
                     (lambda (op . v)
                       (do-op (cdr stack) op v)))
                    ((eq? op 'print)
                     (begin (display stack)
                            (newline)
                            (lambda (op . v)
                              (do-op stack op v))))))))
    (lambda (op . val)
      (do-op '() op val))))

Стек можно использовать, как в этом примере:

 (define s make-stack)
((((((s 'push 1) 'push 2) 'push 3) 'print) 'pop) 'print)

Вывод этого примера:

 ((3) (2) (1))
((2) (1))

Не совсем то, что я хотел, но и не так уж плохо.
Я хотел спросить опытных схемщиков здесь, есть ли способ заставить стек вести себя более естественно, например, так:

 (define s make-stack)
(s 'push 1)
(s 'push 2)
(s 'pop)
...

сохраняя при этом функциональность (так что никакой изменчивости, нет set! ).

Первое, о чем я подумал, это продолжать возвращать функцию без аргументов, но изменять каждый lambda (op . v) с:

 (lambda ()
  (lambda (op . v)
    ...

но это не работает, так как нам все еще нужно захватить возвращаемую функцию:

 > (define s make-stack)
> ((s) 'push 1)
#<procedure>

1. Ваш желаемый синтаксис выглядит так, как будто ему нужен изменяемый стек…

2. @Shawn Я ожидал, что более опытный разработчик придумает макрос, чтобы мой желаемый синтаксис был реализован путем вызова стека, а затем переопределения его путем захвата его вывода. Я согласен, что это было бы не очень чисто.

3. cons , car и cdr являются эквивалентом push , peek , и delete 😮 pop равно peek delete , но в функциональном стеке это невозможно,

Ответ №1:

Как предполагает Amalloy, принципы функционального стиля противоречат вашей цели. Однако сделать что-то подобное не невозможно —

 (define (run-stack s prgm)
  (foldl (lambda (step s) (apply s step))
         s
         prgm))

(run-stack
  make-stack
 '((push 1)
   (push 2)
   (push 3)
   (print)
   (pop)
   (print)))

Чтобы проверить это, я реализовал make-stack как —

 (define (dispatch-stack s)
  (lambda payload
    (match payload
      ((list 'pop)
       (dispatch-stack (cdr s)))
      ((list 'push v)
       (dispatch-stack (cons v s)))
      ((list 'print)
       (println (reverse s))
       (dispatch-stack s))
      (_ (error "invalid stack operation" payload)))))

(define make-stack
  (dispatch-stack null))

Вывод —

 '(1 2 3)
'(1 2)

Еще одна вещь, которую, я думаю, вы хотели бы увидеть, — это создание языка за один час: stacker. Это поможет вам увидеть, как языки, подобные Racket, принципиально отличаются от других, с которыми вы, вероятно, работали раньше.

1. Есть ли причина, по которой у вас есть lambda payload вместо lambda (payload) или это просто опечатка?

2. Д.Д., Это намеренно. это допустимая программа, которую вы можете запустить для проверки результатов. При записи (lambda payload <expr>) все аргументы, переданные лямбде, собираются payload и позволяют <expr> работать с ними в виде списка. Функция с изменяющимся числом параметров известна как вариационная функция . Форма определения является гибкой и позволяет выражать позиционные, каррированные, параметры в стиле ключевых слов, параметры в стиле rest и многое другое.

3. @J.D. lambda (payload) вместо этого вам нужно было бы определить run-stack to foldl with , (lambda (step s) (s step)) и в целом это было бы то же самое.

4. Мне очень нравится это решение, это отличная иллюстрация того, что иногда foldl и foldr не взаимозаменяемы.

Ответ №2:

Ваши цели противоречивы. Если s это стек, и ваши операции чисто функциональны, то (s 'push 1) должны возвращать одно и то же при каждом вызове. Чтобы уловить понятие изменения, вы должны s каждый раз использовать другое. Вот как работает ваш функциональный стек: он возвращает вам новый стек, и вы должны составлять вызовы функций с ним.

1. Хорошая мысль, спасибо. Ваш ответ заставил меня понять, что, по крайней мере, я могу переписать 'print часть, чтобы она не возвращала новую функцию, поскольку печать чего-либо на консоли не изменяет стек.