Реализация арифметики по модулю N с контрактами - PullRequest
Новая
       12

Реализация арифметики по модулю N с контрактами

0 голосов
/ 28 апреля 2019

Я пытаюсь реализовать арифметику в поле по модулю N. Вот упрощенный пример: 

(struct field-element (number prime) #:transparent)

(define (field-element-add fe1 fe2)
  (field-element (modulo (+ (field-element-number fe1)
                            (field-element-number fe2))
                         (field-element-prime fe1))
                 (field-element-prime fe1)))

(field-element-add (field-element 3 5) (field-element 4 5))    ; (1)
(field-element-add (field-element 3 5) (field-element 4 6))    ; (2)

(1) должно вернуть (field-element 2 5), потому что 3 + 4 = 7 = 2 mod 5

(2) должно вызвать ошибку, потому что вы не можете добавлять элементы в поля с другим модулем простого числа (в этом примере 5 и 6).

Мой вопрос: как использовать контракты, которые проверяют все аргументы для field-element-add, совместно используют один и тот же prime и вызывают ошибки, когда их нет?

Все контракты, которые я видел в документах , вводят ограничения для каждого аргумента в отдельности, например, integer?. Но я хочу применить ограничение к аргументам как к группе: они должны иметь общее свойство prime.

И я знаю, что я мог бы просто проверить это вручную без контракта, но похоже, что именно для этого были заключены контракты на обстоятельства.

Заранее спасибо!

1 Ответ

2 голосов
/ 28 апреля 2019

На странице, которую вы упомянули, посмотрите в разделе 7.3.6 , как использовать ->i, чтобы вы могли "упомянуть" другие аргументы.

Для вашего случая: 

(struct field-element (number prime) #:transparent)

(define field-binop/c
  (->i ([a field-element?]
        [b (a) (struct/c field-element
                         number?
                         (=/c (field-element-prime a)))])
       [result field-element?]))

(define/contract (field-element-add fe1 fe2) field-binop/c
  (field-element (modulo (+ (field-element-number fe1)
                            (field-element-number fe2))
                         (field-element-prime fe1))
                 (field-element-prime fe1)))

(field-element-add (field-element 3 5) (field-element 4 5)) ;=> (field-element 2 5)
(field-element-add (field-element 3 5) (field-element 4 6))

#|
../../Applications/Racket v7.2/collects/racket/contract/private/blame.rkt:347:0: field-element-add: contract violation
  expected: (struct/c field-element number? (=/c 5))
  given: (field-element 4 6)
  in: the fe2 argument of
      (->i
       ((fe1 field-element?)
        (fe2
         (fe1)
         (struct/c
          field-element
          number?
          (=/c (field-element-prime fe1)))))
       (result field-element?))
  contract from: (function field-element-add)
  blaming: anonymous-module
   (assuming the contract is correct)
  at: unsaved-editor:5.18
|#
...