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

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

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

stack functional-programming purely-functional scheme
person J. D.    schedule 22.10.2020    source источник
comment
Ваш желаемый синтаксис выглядит так, как будто ему нужен изменяемый стек...   -  person Shawn    schedule 23.10.2020
comment
@Shawn Я ожидал, что более опытный планировщик придумает макрос, чтобы мой желаемый синтаксис был реализован путем вызова стека, а затем переопределения его путем захвата его вывода. Я согласен, что это не было бы очень чистым.   -  person J. D.    schedule 23.10.2020
comment
cons, car и cdr эквивалентны push, peek и delete :-o pop равно peek + delete, но в функциональном стеке это невозможно,   -  person Sylwester    schedule 25.10.2020

Ответы (2)


arrow_upward
1
arrow_downward

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

person amalloy    schedule 23.10.2020
comment
Хороший вопрос, спасибо. Ваш ответ заставил меня понять, что по крайней мере я могу переписать часть 'print, чтобы она не возвращала новую функцию, так как печать чего-либо в консоли не меняет стек. - person J. D.; 23.10.2020

arrow_upward
2
arrow_downward

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

(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, фундаментально отличаются от других, с которыми вы, вероятно, работали раньше.

person Mulan    schedule 24.10.2020
comment
По какой причине у вас lambda payload вместо lambda (payload) или это просто опечатка? - person J. D.; 24.10.2020
comment
Джей Ди, это сделано намеренно. это действующая программа, которую вы можете запустить, чтобы проверить результаты. При записи (lambda payload <expr>) все аргументы, переданные лямбда-выражению, собираются в payload и позволяют <expr> работать с ними как со списком. Функция с различным количеством параметров называется вариативной функцией. Форма define является гибкой и позволяет выражать позиционные, каррированные, ключевые слова. , параметры остальных стилей и многое другое. - person Mulan; 24.10.2020
comment
@Дж.Д. с lambda (payload) вам нужно было бы вместо этого определить run-stack до foldl с (lambda (step s) (s step)), и в целом это было бы то же самое. - person Will Ness; 27.10.2020
comment
Мне очень нравится это решение, это отличная иллюстрация того, что иногда foldl и foldr не взаимозаменяемы. - person J. D.; 27.10.2020