229: Tagged Procedures

by Marc Nieper-Wißkirchen

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-229@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

• Received: 2021-08-26
• Draft #1 published: 2021-08-31
• Draft #2 published: 2021-11-07
• Finalized: 2021-11-15

Abstract

This SRFI defines tagged procedures, which are procedures that are tagged with a Scheme value when created through the syntax lambda/tag and case-lambda/tag. The value of the tag of a procedure can be retrieved with procedure-tag, and the predicate procedure/tag? discerns whether a procedure is tagged.

Rationale

The only way to interact with an ordinary Scheme procedure, besides applying predicates like eqv? or procedure? to it, is to call it. Some applications, however, have the need to associate data with a procedure that can be retrieved without calling the procedure. For an R7RS system, this can be achieved in principle by associating the data through a weak hash table. For an R6RS system, this is not possible because R6RS does not expose a coarse-enough equivalence predicate for procedures. But even for an R7RS system, such an approach is not straightforward. Firstly, weak hash tables are not necessarily available and, secondly, even for an R7RS system, procedure equivalence is not trivial because the expression types that create procedures, lambda and case-lambda, are not necessarily generative.

Therefore, this SRFI defines a simple interface that can be used to create tagged procedures, to detect the existence of a tag, and to retrieve it. Through this mechanism, even R6RS procedures can be given an identity that can be tested in Scheme code.

The mechanism defined in this SRFI can be used to implement procedure properties, documentation strings, source location information, and other things in Scheme.

Scheme records as defined by R⁶RS or R⁷R7 cannot be called as procedures, but this SRFI can be used to implement an alternative record system where the record instances are procedures whose actual fields are stored in a private record as the procedure's tag.

In order to not prevent certain optimizations, the procedure tags defined through the facilities presented here are immutable. In other words, the Scheme object used as a tag is fixed at procedure creation time. If an application needs mutable fields attached to a procedure, a Scheme object that is itself mutable (like a pair, a string, a vector, or a record with mutable fields) has to be used as a tag.

Contrary to proposals that conceptually attach properties to every procedure, this SRFI gives implementations the freedom to have disjoint types of tagged and untagged procedures, both non-empty. In particular, this SRFI can be implemented at zero cost for the general case of untagged procedures.

In fact, in the context of SRFI 229, one shouldn't think of procedures falling in just two classes, untagged and tagged ones (note that all procedures may be implementable as tagged ones), but falling into infinitely many classes, one for each type of its tag. So one can really think of them as callable structs, where the struct is in the tag. (See MIT/GNU Scheme's apply hooks for an example.)

Future SRFIs are expected to build on SRFI 229 to provide a procedure type with an extensible tag field, allowing independent composition.

Application Hooks

MIT/GNU Scheme Scheme defines application hooks and entities, which are objects that can applied like procedures. As a demonstration of the generality of the primitives defined by this SRFI, we give a portable sample implementation of application hooks and entities on top of this SRFI:

(define-library (application-hook)
  (export make-apply-hook
          apply-hook?
          apply-hook-procedure
          set-apply-hook-procedure!
          apply-hook-extra
          set-apply-hook-extra!
          make-entity
          entity?
          entity-procedure
          set-entity-procedure!
          entity-extra
          set-entity-extra!)
  (import (scheme base)
          (srfi 229))
  (begin
    (define-record-type apply-hook-tag
      (make-apply-hook-tag procedure extra)
      apply-hook-tag?
      (procedure apply-hook-tag-procedure apply-hook-tag-set-procedure!)
      (extra apply-hook-tag-extra apply-hook-tag-set-extra!))

    (define (make-apply-hook proc obj)
      (let ((tag (make-apply-hook-tag proc obj)))
        (lambda/tag tag arg*
          (apply (apply-hook-tag-procedure tag) arg*))))

    (define (apply-hook? obj)
      (and (procedure/tag? obj)
           (apply-hook-tag? (procedure-tag obj))))

    (define (apply-hook-procedure hook)
      (apply-hook-tag-procedure (procedure-tag hook)))

    (define (set-apply-hook-procedure! hook proc)
      (apply-hook-tag-set-procedure! (procedure-tag hook) proc))

    (define (apply-hook-extra hook)
      (apply-hook-tag-extra (procedure-tag hook)))

    (define (set-apply-hook-extra! hook obj)
      (apply-hook-tag-set-extra! (procedure-tag hook) obj))

    (define-record-type entity-tag
      (make-entity-tag procedure extra)
      entity-tag?
      (procedure entity-tag-procedure entity-tag-set-procedure!)
      (extra entity-tag-extra entity-tag-set-extra!))

    (define (make-entity proc obj)
      (let ((tag (make-entity-tag proc obj)))
        (define f
          (lambda/tag tag arg*
            (apply (entity-tag-procedure tag) f arg*)))
        f))

    (define (entity? obj)
      (and (procedure/tag? obj)
           (entity-tag? (procedure-tag obj))))

    (define (entity-procedure hook)
      (entity-tag-procedure (procedure-tag hook)))

    (define (set-entity-procedure! hook proc)
      (entity-tag-set-procedure! (procedure-tag hook) proc))

    (define (entity-extra hook)
      (entity-tag-extra (procedure-tag hook)))

    (define (set-entity-extra! hook obj)
      (entity-tag-set-extra! (procedure-tag hook) obj))))

Specification

Equivalence

When invoked on two objects, the eqv? procedure returns #f if one object is a tagged procedure and the other object is a non-procedure or a procedure that is not tagged, or if both objects are tagged procedures but tagged with values such that eq? would return #f when invoked on them.

Note: Note that in an R⁷RS system, all procedures are conceptually tagged with a storage location and that eqv? returns #t when invoked on procedures whose location tags are equal. As each tagged procedure (in the sense of this SRFI) is also a procedure in the sense of the Scheme reports, tagged procedures inherit this behavior in R⁷RS systems.

On the other hand, the syntax and procedures of this SRFI can be used to give procedures also in R⁶RS systems an identity that can be discerned through Scheme procedures:

(define-syntax lambda/id
  (syntax-rules ()
    ((lambda/id formals body)
     (lambda/tag (list 'tag) formals body))))

(define lambda/id=?
  (lambda (f g)
    (assert (procedure/tag? f))
    (assert (procedure/tag? g))
    (eq? (procedure-tag f) (procedure-tag g))))

(define p (lambda/id (x) x))
(lambda/id=? p p)#t

Syntax

(case-lambda/tag expression (formals body) …)syntax

Semantics: First, expression is evaluated to obtain a value. Then a procedure is returned that accepts a variable number of arguments, that is lexically scoped in the same manner as a procedure resulting from a lambda expression, and that is tagged with the obtained value. When the procedure is called, it behaves as if constructed by a case-lambda expression with the same formals and bodies.

(lambda/tag expression formals body)syntax

Semantics: Operationally equivalent to (case-lambda/tag expression (formals body)).

Procedures

(procedure/tag? obj)procedure

Returns #t if obj is a tagged procedure and #f otherwise.

Note: It is unspecified whether a procedure created by a lambda or case-lambda expression or returned by a procedure of one of the standard libraries or defined by syntax of one of the standard libraries is tagged. In case it is tagged, the tag value is unspecified.

(procedure-tag proc)procedure

It is an error if proc is not a tagged procedure.

Returns the tag of proc.

(define f
  (lambda/tag 42
      (x)
    (* x x)))

(procedure/tag? f)#t
(f 3) 9
(procedure-tag f)42

(define f*
  (lambda/tag 43
      (x)
    (* x x)))

(eqv? f f*)#f

(define g
  (let ((y 10))
    (lambda/tag y ()
	(set! y (+ y 1))
	y)))

(procedure-tag g)10
(let ((y 9)) (procedure-tag g))10
(g)11
(procedure-tag g)10

(define h
  (let ((box (vector #f)))
    (case-lambda/tag box
      (() (vector-ref box 0))
      ((val) (vector-set! box 0 val)))))

(h 1)
(vector-ref (procedure-tag h) 0))1
(h)1

Implementation

The following is a portable R7RS implementation. It is fully conformant, but tagged procedures will never be garbage-collected.

(define-library (srfi 229)
  (export case-lambda/tag
	  lambda/tag
	  procedure/tag?
	  procedure-tag)
  (import (scheme base)
	  (scheme case-lambda))
  (begin
    (define *tagged-procedures* '())

    (define key (list 'key))

    (define make-procedure/tag
      (lambda (tag proc)
	(define f
	  (case-lambda
	    ((arg)
	     (if (eq? arg key) tag (proc arg)))
	    (arg*
	     (apply proc arg*))))
	(set! *tagged-procedures* (cons f *tagged-procedures*))
	f))

    (define-syntax case-lambda/tag
      (syntax-rules ()
	((case-lambda/tag expr (formals body1 ... body2) ...)
	 (make-procedure/tag
	  expr
	  (case-lambda (formals body1 ... body2) ...)))))

    (define-syntax lambda/tag
      (syntax-rules ()
	((lambda/tag expr formals body1 ... body2)
	 (make-procedure/tag
	  expr
	  (lambda formals body1 ... body2)))))

    (define procedure/tag?
      (lambda (f)
	(and (memv f *tagged-procedures*) #t)))

    (define procedure-tag
      (lambda (f)
	(f key)))))

Scheme implementers should replace the above implementation by a more efficient one where the tag value is stored like a closure variable.

A portable R6RS implementation is not possible because procedures in R6RS have no identity (exposed via Scheme predicates).

Acknowledgements

Thanks to the participants on the mailing list, and to Arthur A. Gleckler, who pointed out MIT/GNU Scheme's application hooks to me.

Some Scheme systems like Kawa implement procedure properties, which can be used to implement this SRFI.

Thanks to Göran Weinholt for implementing this SRFI during its draft period natively in his Loko compiler.

Copyright

© 2021 Marc Nieper-Wißkirchen.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.