CODEWITHSUNDEEP
functioncompareracket
dvvrd
dvvrd

Reputation: 1689

"Smart" comparison of functions in Racket

I've got a bit exotic situation. I need to compare functions, but rather by their "origin" than by "instances". Here what I actually mean:

(define-values (a b c d) (values #f #f #f #f))

(define (f x)
  (let ([g (λ (y) (printf "Please tell ~a this is ~a\n" x y))]
        [h (curry printf "Don't tell ~a this is ~a\n" x)])
    (if a
        (set! b g)
        (set! a g))
    (if c
        (set! d h)
        (set! c h))))

(f "me")
(f " me")

(a "possible")
(d "impossible")

(equal? a b) ; <====  Is it possible to compare these guys
(equal? c d) ; <====  to get #t in both cases?

In both cases we get two different "instances" of functions (even with different values captured), but both declared in the same location of the source code. Of course, getting the actual text of the body of those functions will solve the problem, but other answers here on SO tell that this is impossible in Racket. Are there some tricks that can help me?

Edit: This is not the question on theoretical equivalence of functions. This is completely technical question, much rather on Racket's functions representation in a compiled code. So it can be reformulated, for example, in a following way: can I get the line number of some routine from 'user' code? I suppose this should be feasible because Racket debugger somehow obtains it.

Upvotes: 1

Views: 579

Answers (1)

Sylwester
Sylwester

Reputation: 48745

It can be done even without support from racket internals if you control the code that makes the functions. If you keep a counter (or some identifier) that will denote the particular lambda it can wrap different closures in a struct that can have the same identity from macro expansion. Here is a demonstration:

#lang racket

;; makes a procedure object that can have other data connected to it
(struct proc (id obj) 
  #:property prop:procedure
  (struct-field-index obj)
  #:methods gen:custom-write
  [(define (write-proc x port mode)
     (display (format "#<procedure-id-~a>" (proc-id x)) port))])

;; compares the ids of two proc objects if they are proc objects
(define (proc-equal? a b)
  (and (proc? a)
       (proc? b)
       (= (proc-id a) (proc-id b))))

;; extends equal?, candidate to provide
(define (equal*? a b)
  (or (proc-equal? a b)
      (equal? a b)))

;; the state we keep
(begin-for-syntax
  (define unique-proc-id-per-code 0))

;; a macro that changes (lambda* ...) to 
;; (proc expansion-id (lambda ...)) 
(define-syntax (lambda* stx)
  (let ((proc-id unique-proc-id-per-code))
    (set! unique-proc-id-per-code (add1 unique-proc-id-per-code))
    #`(proc #,(datum->syntax stx proc-id) (lambda #,@(datum->syntax stx (cdr (syntax-e stx)))))))


;; test with making a counter
(define counter-from
  (lambda* (from)
    (lambda* ()
      (begin0
        from
        (set! from (add1 from))))))

;; evaluatin the outer shows it has id 0
counter-from ; ==> #<procedure-id-0>

;; make two counters that both use the inner lambda
(define from10 (counter-from 10))
(define from20 (counter-from 20))

;; both have the same expansion id
from10 ; ==> #<procedure-id-1>
from20 ; ==> #<procedure-id-1>

;; they are not equal?
(equal? from10 from20)      ; ==> #f (different object instances of proc)
;; but they are procedure-equal?
(proc-equal? from10 from20) ; ==> #t (same id, thus came from same macroexpansion)

Disclaimer: I'm more a schemer than a racketeer so this could perhaps have been done more elegantly and I have no idea what performance penalties this will give.

Upvotes: 1

Related Questions