CODEWITHSUNDEEP
typesschemeracketpredicate
EB Mudd
EB Mudd

Reputation: 193

How to define type predicates in Scheme

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

Upvotes: 5

Views: 5161

Answers (3)

dyoo
dyoo

Reputation: 12013

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.

Upvotes: 3

Sylwester
Sylwester

Reputation: 48745

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.

Upvotes: 4

Will Ness
Will Ness

Reputation: 71065

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.

Upvotes: 1

Related Questions