[Caml-list] Symbol type

[José Romildo Malaquias]

Is there a symbol type in OCaml, with a constant time comparison
function? Something like symbols from Scheme and LISP or atoms from
Prolog. Useful in compiler construction.

Romildo

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[Michael Ekstrand]

On 06/27/2010 10:15 PM, José Romildo Malaquias wrote:
> Is there a symbol type in OCaml, with a constant time comparison
> function? Something like symbols from Scheme and LISP or atoms from
> Prolog. Useful in compiler construction.

Not directly. As I see it, you have two decent options:

- Use/write a symbol table which "interns" symbols to integers. The
resulting integers can be compared.
- Use/write a symbol table which interns symbols to unique string
instances, so SymTbl.intern "foo" returns the existing string object if
one already exists, and the string object passed in if it's never been
seen before. The resulting strings can be compared with == rather than
= in constant time.

Either of these options would be fairly similar to how symbols work
under the hood in a Lisp implementation, I believe.

- Michael

[bluestorm]

If your set of symbol is closed, you can use a variant type (sum type).

type symbols =
| A
| B

If you really need open symbols, you can use [polymorphic variants].

Let tag_a foo = (`A, foo)

[polymorphic variants]
http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html#toc36

However, you won't have convenience functions such as string_of_symbol; you
would have to define them yourself.

[Nicholas Kidd]

On Sun, Jun 27, 2010 at 9:33 PM, Michael Ekstrand <mic...@elehack.net>wrote:

> On 06/27/2010 10:15 PM, José Romildo Malaquias wrote:
> > Is there a symbol type in OCaml, with a constant time comparison
> > function? Something like symbols from Scheme and LISP or atoms from
> > Prolog. Useful in compiler construction.
>
> Not directly. As I see it, you have two decent options:
>
> - Use/write a symbol table which "interns" symbols to integers. The
> resulting integers can be compared.
> - Use/write a symbol table which interns symbols to unique string
> instances, so SymTbl.intern "foo" returns the existing string object if
> one already exists, and the string object passed in if it's never been
> seen before. The resulting strings can be compared with == rather than
> = in constant time.
>
> Either of these options would be fairly similar to how symbols work
> under the hood in a Lisp implementation, I believe.
>
>

Use the Ocaml hash-consing library.

http://gallium.inria.fr/ml2006/accepted/5.html
http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.pdf

Best,
-Nick