How to define type predicates in Scheme

5
votes

"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?

3
typesschemeracketpredicate
Why would you care how the pair was constructed? If it's a pair, then it's a pair regardless. You could define pair? as a list that is not null, and whose cdr is not null, but where recursion on the cdr is #f. I'm pretty sure the list? predicate needs to be a built-in function, as it's too fundamental. - d11wtq
@d11wtq (define (list? x) (and (pair? x) (or (null? (cdr x)) (list? (cdr x))))) checks whether an argument object is a finite proper list. pair? only checks whether it is a cons cell data object. (let ((a (list 1))) (set-cdr! a a) (pair? (cdr a))) must be able to return #t. - Will Ness

3 Answers

4
votes

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.

3
votes

In Racket, by the way, the structure predicates made with struct do this work for you already, so that you don't have to implement it by hand.

Every professional-level Scheme provides similar functionality via structures or records. See SRFI-9, which describes what many other Scheme implementations will do for you already.

1
votes

You couldn't, with the code that you've shown. Procedures are opaque.

You'd have to change the constructor/accessors to use tagged lists, as one possibility.

(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 that is obviously not fool-proof.

The predicates pair? and procedure? are built-in, and probably are implemented through some kind of under-the-hood magic. list? could be implemented in terms of pair?, null?, car and cdr.