Geek asks and answers

How to define type predicates in a schema

"Normal" functions are usually defined only in the domain of objects of a given type, but certain functions, such as predicates of the type of a scheme list?or procedure?, are defined for arguments of any type and can even be applied to themselves. So, for example, it (list? procedure?)is evaluated as #f, and (procedure? procedure?)- #t. I am trying to figure out how to write a fully defined function of this kind, but I could not find a source that discusses this.

For example, suppose we implement a pair data type as described in Exercise 2.4 Structure and interpretation of computer programs using the following constructor and selectors

    (define (cons x y)
      (lambda (m) (m x y)))

    (define (car z)
      (z (lambda (p q) p)))

    (define (cdr z)
      (z (lambda (p q) q)))

How then do I define a predicate pair?that returns #tfor everything that was built with help cons, and #ffor something that was not? More generally, how are predicates of type list?and implemented procedure??

+5
source share
3 answers

It is easy. Override the procedures to have the first argument of the type of the object being created:

(define +type-pair+ 'pair)
(define +type-number+ 'number)

(define (cons a d)
  (lambda (m) (m +type-pair+ a d)))

(define (type x)
  (x (lambda (t . rest) t)))

(define (pair? c)
  (eq? (type c) +type-pair+))

(define (car c)
  (if (pair? c)
      (c (lambda (t a d) a))
  (error "Argument is not pair!")))

(define (cdr c)
  (if (pair? c)
      (c (lambda (t a d) d))
  (error "Argument is not pair!")))

(define (number? c)
   (if (type c) +type-number+))

, , , ( x), , , , . , , , SICP , , . Arc , . Arc, , .

+4

Racket, , , struct, , .

. . SRFI-9, , .

+3

, , . .

You will need to modify the constructor / accessors to use tagged lists as one of the possibilities.

(define *church-pair-tag* (list '*church-pair-tag*))

(define (cons x y)
   (cons *church-pair-tag* (lambda(m) (m x y))))

(define (church-pair? x)
   (and (pair? x) 
        (eq? *church-pair-tag* (car x))
        (procedure? (cdr x))))

....

but this is obviously not flawless.

Predicates are pair?both procedure?built-in and probably implemented using some kind of magic under the hood. list?can be implemented in terms of pair?null ?, carand cdr.

+1
source

More articles:


All Articles