Программирование практической схемы

Прошло несколько месяцев с тех пор, как я коснулся Scheme и решил реализовать разделитель доходов из командной строки с помощью Scheme.

Моя первоначальная реализация использовала простую рекурсию вместо продолжения, но я решил, что продолжение будет более подходящим для этого типа программы. Я был бы признателен, если бы кто-нибудь (более опытный в Scheme, чем я) мог взглянуть на это и предложить улучшения. Я считаю, что несколько строк (display... — это также идеальная возможность использовать макрос (просто я еще не добрался до макросов).

(define (ab-income)
  (call/cc
   (lambda (cc)
     (let
         ((out (display "Income: "))
          (income (string->number (read-line))))
       (cond
         ((<= income 600)
          (display (format "Please enter an amount greater than $600.00~n~n"))
          (cc (ab-income)))
         (else
          (let
              ((bills    (* (/ 30 100) income))
               (taxes    (* (/ 20 100) income))
               (savings  (* (/ 10 100) income))
               (checking (* (/ 40 100) income)))
            (display (format "~nDeduct for bills:---------------------- $~a~n" (real->decimal-string bills 2)))
            (display (format "Deduct for taxes:---------------------- $~a~n" (real->decimal-string taxes 2)))
            (display (format "Deduct for savings:-------------------- $~a~n" (real->decimal-string savings 2)))
            (display (format "Remainder for checking:---------------- $~a~n" (real->decimal-string checking 2))))))))))

Вызов (ab-income) запрашивает ввод, и если предоставляется что-либо ниже 600, он (насколько я понимаю) возвращает (ab-income) в current-continuation. Моя первая реализация (как я уже говорил ранее) использовала рекурсию простого Джейна. Это тоже было неплохо, но я полагал, что каждый обратный вызов (ab-income), если значение было ниже 600, продолжал расширять функцию.

(пожалуйста, поправьте меня, если это опасение неверно!)


person Ixmatus    schedule 17.04.2010    source источник
comment
Я думаю, что у вас 3 ))) слишком много.   -  person kennytm    schedule 17.04.2010
comment
Это правильная программа, по какой-то причине stackoverflow удалял ввод, когда я помещал код в ‹pre› блоки; Я просто удалил их и разделил каждую строку на 4...   -  person Ixmatus    schedule 17.04.2010
comment
@lxmatus: понятно. Текст внутри <pre> по-прежнему интерпретируется как HTML, поэтому содержимое между <= и > будет скрыто. Всегда делайте отступ в 4 пробела (используйте кнопку 101010 на панели инструментов).   -  person kennytm    schedule 17.04.2010


Ответы (1)


Во-первых, вам не нужно продолжение. Согласно стандарту, Scheme всегда выполняет оптимизацию хвостового вызова. Хвостовой вызов — это вызов функции, который находится в последней позиции в функции; после выполнения этого вызова больше ничего не произойдет. В этой ситуации нам не нужно сохранять активационную запись, в которой мы сейчас находимся; как только функция, которую мы вызываем, вернется, мы просто вытолкнем ее. Следовательно, хвостовой вызов повторно использует текущую запись активации. В качестве примера рассмотрим следующее:

(define (some-function x y)
  (preprocess x)
  (combine (modified x) y))
(some-function alpha beta)

Когда мы вызываем some-function, мы выделяем место в стеке для записи его активации: локальные переменные, параметры и т.д. Затем мы вызываем (preprocess x). Поскольку нам нужно вернуться к some-function и продолжить обработку, мы должны сохранить запись активации some-function, поэтому мы добавляем новую запись активации для preprocess. Как только он возвращается, мы извлекаем кадр стека preprocess и продолжаем работу. Далее нам нужно оценить modified; то же самое должно произойти, и когда modified возвращается, его результат передается в combine. Можно было бы подумать, что нам нужно создать новую запись активации, запустить combine, а затем вернуть ее в some-function, но some-function не нужно ничего делать с этим результатом, кроме как вернуть его! Таким образом, мы перезаписываем текущую активационную запись, но оставляем адрес возврата в покое; когда combine вернется, то он вернет свое значение именно к тому, что его ждало. Здесь (combine (modified x) y) — это хвостовой вызов, и для его оценки не требуется дополнительной записи активации.

Вот как вы можете реализовать циклы в Scheme, например:

(define (my-while cond body)
  (when (cond)
    (body)
    (my-while cond body)))

(let ((i 0))
  (my-while (lambda () (< i 10))
            (lambda () (display i) (newline) (set! i (+ i 1)))))

Без оптимизации хвостовых вызовов это было бы неэффективно и потенциально могло бы переполниться длительным циклом, создающим множество вызовов my-while. Однако благодаря оптимизации хвостового вызова рекурсивный вызов my-while cond body является переходом и не выделяет памяти, что делает его таким же эффективным, как итерация.

Во-вторых, здесь не нужны никакие макросы. Хотя вы можете абстрагироваться от блока display, вы можете сделать это с помощью простой функции. Макросы позволяют вам на каком-то уровне изменить синтаксис языка, добавить свои собственные define, реализовать некоторую конструкцию type-case, которая не оценивает все его ветви, и т. д. Конечно, это все еще s-выражения, но семантика больше не просто «оценивает аргументы и вызывает функцию». Здесь, однако, семантика вызова функции — это все, что вам нужно.

С учетом сказанного, я думаю, что именно так я бы реализовал ваш код:

(require (lib "string.ss"))

(define (print-report width . nvs)
  (if (null? nvs)
    (void)
    (let ((name  (car  nvs))
          (value (cadr nvs)))
      (display (format "~a:~a $~a~n"
                       name
                       (make-string (- width (string-length name) 2) #\-)
                       (real->decimal-string value 2)))
      (apply print-report width (cddr nvs)))))

(define (ab-income)
  (display "Income: ")
  (let ((income (string->number (read-line))))
    (if (or (not income) (<= income 600)) 
      (begin (display "Please enter an amount greater than $600.00\n\n")
             (ab-income))
      (begin (newline)
             (print-report 40 "Deduct for bills"       (* 3/10 income)
                              "Deduct for taxes"       (* 2/10 income)
                              "Deduct for savings"     (* 1/10 income)
                              "Remainder for checking" (* 4/10 income))))))

Во-первых, по крайней мере, в моей версии mzscheme мне нужна была строка (require (lib "string.ss")) для импорта real->decimal-string. Затем я абстрагировался от блока display, о котором вы говорили. Мы видим, что каждая строка хочет напечатать деньги в одном и том же формате в 40-м столбце, напечатав имя тега и ряд дефисов перед ним. Следовательно, я написал print-report. Первый аргумент — начальная ширина; в данном случае 40. Остальные аргументы представляют собой пары поле-значение. Длина каждого поля (плюс два для двоеточия и пробела) вычитается из ширины, и мы генерируем строку, состоящую из указанного количества дефисов. Мы используем format, чтобы расположить поля в правильном порядке, и display, чтобы напечатать строку. Функция выполняет рекурсию по всем парам (используя хвостовую рекурсию, поэтому мы не будем взорвать стек).

В основной функции я переместил (display "Income: ") перед let; вы игнорируете его результат, так зачем присваивать его переменной? Затем я расширил условие if, чтобы проверить, является ли input ложным, что происходит, когда string->number не может проанализировать ввод. Наконец, я удалил ваши локальные переменные, поскольку все, что вы делаете, это печатаете их, и использовал синтаксис дроби Scheme вместо деления. (И, конечно же, я использую print-report вместо displays и formats.)

Я думаю, что это все; если у вас есть другие вопросы о том, что я сделал, не стесняйтесь спрашивать.

person Antal Spector-Zabusky    schedule 17.04.2010
comment
Это был отличный ответ. Большое вам спасибо - я получил хорошую дозу теории и практических объяснений; точно (если не больше), чем я хотел. Большое спасибо! - person Ixmatus; 18.04.2010