Could there be a O(1) type-of operator for Racket builtins?

[Alexis King]

This is something that has bothered me for a little while. As far as I
know, there is no way in Racket to determine the type of some built-in
structure in constant time. Traditionally, the solution is to just use
predicates, but this is obviously linear in the number of predicates to
be tested. It also needs to be extended for every single datatype that
gets added to the language (or was simply omitted).

I’d love to be able to have a type-of operator that produces a unique
key for each type of data structure Racket has. Why? Well, a little
while ago, I tried to implement multimethods in Racket in a safe way[1],
and I think my solution was a pretty good one. However, it is currently
pretty limited by the fact that it only works with structs, since it
uses the structure type as a key for dispatch. It would be really nice
to make dispatch O(1) for all conceivable datatypes, including the
builtins.

This doesn’t really seem all that hard to me, but I could be totally
wrong. Things are often a lot harder to do than they initially seem. Is
there any reason this isn’t in the language right now? I could imagine
an argument that it exposes too much about the implementation, but since
the predicates already exist, I’m not sure that’d actually be true. It’d
be really helpful for making a useful uniform interface for my
multiple-dispatch system.

Thanks,
Alexis

[1]: http://lexi-lambda.github.io/blog/2016/02/18/simple-safe-multimethods-in-racket/

[Jay McCarthy]

We could expose the C virtual machine's type tags and that would be
O(1) to a unique number. We could define the number as not being
stable across executions of Racket or versions, whichever we like
better.

If you're uncomfortable with the number, we could combine it with an
O(1) hash lookup from the number to a symbol.

I think an extension like this is achievable for someone with a
cursory knowledge of C. You should do it Alexis.

--

The numbers are given here in this enum:

https://github.com/racket/racket/blob/master/racket/src/racket/src/stypes.h

The type tag is just called type:

https://github.com/racket/racket/blob/master/racket/src/racket/include/scheme.h#L326`

Jay

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/D016C78B-7C44-42C1-90D8-3E8CB8F660EE%40gmail.com.
> For more options, visit https://groups.google.com/d/optout.



--
Jay McCarthy
Associate Professor
PLT @ CS @ UMass Lowell
http://jeapostrophe.github.io

"Wherefore, be not weary in well-doing,
for ye are laying the foundation of a great work.
And out of small things proceedeth that which is great."
- D&C 64:33

[Alexis King]

Ok, I’m happy to take a crack at it if you think that’s a good approach.
I am quite comfortable with C, but I have basically no idea how Racket’s
internals work, so that’d be the real barrier. I think one of the
less-technical questions would also just be how to expose this
information in Racket.

I do think using a number is probably too fragile, but even then, it
doesn’t matter too much, since somehow there needs to be a known set of
values for comparisons. Something like (eq? (type-of some-val)
type:list) needs to be possible, but I’m not sure where type:list should
go or what it should actually be called.

[Matthew Flatt]

There's an array of strings initialized in "type.c" that's indexed by
type tag. The strings are used for printing a value as "#<...>" when
the value has no other output form. A string like "<rational-number>"
can show up in `dump-memory-stats`, even though exact non-integer
numbers don't use that string for printing.

So, as a first cut, a symbol form of each string would probably make
sense as a result from the new function. You might want to make some
adjustments, such as 'number instead of 'rational-number, or maybe you
want to keep the distinction.

Beware of trying to allocate an array of symbols on initialization: New
type tags can get allocated at run time (though an unsafe API), and
allocating symbols after start-up means that they won't be interned in
the space that is shared by across places. So, any symbols allocated
after startup will need to be in a place-specific array. It may be
simplest to fill a place-local array on demand. You'll probably end up
changing "schthread.h" to add a new place-local variable.

> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/racket-dev/034504BF-6A0B-4158-B389-4DCA0DED6F
> FD%40gmail.com.

[Robby Findler]

If you want efficient conditionals you probably want a less than-like operator too I guess. 

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/034504BF-6A0B-4158-B389-4DCA0DED6FFD%40gmail.com.