How to define type predicates in Scheme

Question

"Ordinary" functions are usually only defined on a domain of objects of a given type, but certain functions, such the Scheme type predicates list? or procedure?, are defined for arguments of any type, and can even be applied to themselves. So e.g. (list? procedure?) evaluates to #f and (procedure? procedure?) evaluates to #t. I am trying to figure out how one would write a totally defined function of this sort, but haven't been able to find a source that discusses this.

For example, suppose we implement a pair data type as described in Exercise 2.4 of 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 would I then define a predicate pair? that returns #t for anything that was constructed using cons, and #f for anything that wasn't? More generally, how are type predicates like list? and procedure? implemented?

Answer 1

That is easy. Redefine you procedures to have the first argument the type of object you are creating:

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

You may use this to define everything in your language, even procedures, but all must support giving it's type with (type x) and all procedures that use something must make sure the type is correct. Implementing pairs as closures are probably the slowest way so it's just SICP thought experiment to make you understand what closures are. Arc uses tags for all data types, but keeps data as data. you should have a look at Arc to see how tagging can be a way to go.