Contracts for (partially) specifying dictionary key -> value-predicates

[William J. Bowman]

I'm considering implementing, maybe as a library or a pull-request to
racket/dict, contracts for (partially) specifying which keys exist in a
dictionary and a contract for the value on that key.
I've got a quick prototype here:

https://gist.github.com/wilbowma/7e97c8a38130c720568d008b288466f0

(dictof (id expr) ...)
A contract for a dictionary that contains exactly the keys id ... that map to
values that satisfy the contracts expr ... (respectively).

(rho-dictof (id expr) ...)
A contract for a dictionary that contains at least the keys id ... that map to
values that satisfy the contracts expr ... (respectively).

Before I start documenting and making it a thing, I thought I'd solicit
feedback.

--
William J. Bowman

[Ben Greenman]

On 10/29/20, William J. Bowman <w...@williamjbowman.com> wrote:
> I'm considering implementing, maybe as a library or a pull-request to
> racket/dict, contracts for (partially) specifying which keys exist in a
> dictionary and a contract for the value on that key.

Great!

Please make the contract error messages point out the bad key and bad
value. The error messages from hash/dc are usually too big for me, and
I end up moving my key-check and value-check contracts into a function
that checks things one-by-one.

(Maybe hash/dc can give better errors ... I never looked into a fix.)

> I've got a quick prototype here:
>
> https://gist.github.com/wilbowma/7e97c8a38130c720568d008b288466f0
>
> (dictof (id expr) ...)
> A contract for a dictionary that contains exactly the keys id ... that map
> to
> values that satisfy the contracts expr ... (respectively).
>
> (rho-dictof (id expr) ...)
> A contract for a dictionary that contains at least the keys id ... that
> map to
> values that satisfy the contracts expr ... (respectively).
>
> Before I start documenting and making it a thing, I thought I'd solicit
> feedback.

Two comments:

1. make these functions, not macros

2. make "at least" the default behavior for dictof, add an option to
override (#:exact-keys?), and remove rho-dictof

[William J. Bowman]

Thanks! One follow-up:

> 1. make these functions, not macros

The main implementation is a procedure, but I think I need a macro to get the
syntactic interface I want.

Is there some reason to avoid macros?

[Robby Findler]

I didn't look at the code yet myself, but generally you want to minimize the amount of code you compile into (and so using a function is pretty minimal). Another reason is that a lot of stuff "just works" when you use functions (because they would be documented as functions and so come with certain expectations). Debugging stuff, other little details.

But in the case of the contract system you might want macros because that way you can cooperate with the check syntax blame annotations (which need work in other parts of the contract library).

Ben: if you have an example of the bad hash/dc error message I'd be interested to see it.

Robby

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20201030171407.GP1611044%40williamjbowman.com.

[Philip McGrath]

I've wanted this several times (and written more than one ad-hoc partial version): a general-purpose combinator would be great!

On Fri, Oct 30, 2020 at 1:14 PM William J. Bowman <w...@williamjbowman.com> wrote:

> 1. make these functions, not macros

The main implementation is a procedure, but I think I need a macro to get the
syntactic interface I want.

Personally, I'd think about an approach like `->` and `dynamic->*`: a nice syntactic interface that covers most use-cases paired with a somewhat-less-ergonomic procedural interface for more comprehensive functionality, e.g. when aspects of the contract to be generated aren't statically known.

On Fri, Oct 30, 2020 at 11:06 AM Ben Greenman <benjamin...@gmail.com> wrote:

2. make "at least" the default behavior for dictof, add an option to
override (#:exact-keys?), and remove rho-dictof

To go a step further, I think there are two dimensions of "exactness":

1. Are keys other than those specified permitted?
   
2. Is a particular key required or optional?

There are some combinations of answers to those questions that I think make for poor API design, but, in many of the cases when I've wanted these types of contracts, I've been working with messy pre-existing APIs (often JSON), which inhabit a whole lot of different points in this space.

An even-more-general way of asking "Are keys other than those specified permitted?" would be, "What is the contract for a key–value pair not otherwise specified?", where `any/c` and `none/c` are important special cases. Even more generally, this could be a function to produce a contract à la `hash/dc`: I'll see if I can remember an example, but I think I've encountered APIs where this would have been useful.

As far as "Is a particular key required or optional?", I'd want a nice syntax to specify this for all keys (I don't have a considered opinion about what the default should be), but I'd also want support for specifying it at the level of the individual key–value pair.

Of course, even an implementation that didn't support all of this would be useful!

-Philip

 

[George Neuner]

You certainly can use macros in the implementation, but just remember
that macros evaluate at compile time and most contracts have to be
checked at runtime: so a contract can't *exclusively* be a macro ...
runtime code has to be generated.

Robby's comment about code size is relevant also:  contracts are not
debug mode only like assertions in C ... Racket's contracts live on in
release mode compiles, so you want to minimize the amount of runtime
code required to implement them.

George

[William J. Bowman]

Let me aid this discussion by copying in the ~10 lintes of code in question:

> (define-syntax (dictof syn)
> (syntax-parse syn
> [(_ (k:id pred?) ...)
> (quasisyntax/loc syn
> (dictof/proc `((k . ,pred?) ...)))]))
>
> (define ((dictof/proc spec) h)
> (and (eq? (dict-keys h) (dict-keys spec))
> (for/and ([(k pred?) (in-dict spec)])
> (pred? (dict-ref h k)))))

The macro is merely a syntactic transformation to 1 line of code that implements
the functionality of the contract at run-time.
Is there some reason to avoid macros in this particular case?

--
William J. Bowman

[Robby Findler]

On Fri, Oct 30, 2020 at 2:08 PM William J. Bowman <w...@williamjbowman.com> wrote:

Let me aid this discussion by copying in the ~10 lintes of code in question:

> (define-syntax (dictof syn)
>   (syntax-parse syn
>     [(_ (k:id pred?) ...)
>      (quasisyntax/loc syn
>        (dictof/proc `((k . ,pred?) ...)))]))
>
> (define ((dictof/proc spec) h)
>   (and (eq? (dict-keys h) (dict-keys spec))
>        (for/and ([(k pred?) (in-dict spec)])
>          (pred? (dict-ref h k)))))

The macro is merely a syntactic transformation to 1 line of code that implements
the functionality of the contract at run-time.
Is there some reason to avoid macros in this particular case?

I don't think so. 

But I do think that you'd need more checking so things like (dictof (,(something scary) i-am-not-a-procedure)) give reasonable error messages. And eq? is probably not the right comparison (consider large integers for example).

Robby

 

--
William J. Bowman

On Fri, Oct 30, 2020 at 03:04:04PM -0400, George Neuner wrote:
>
> On 10/30/2020 1:14 PM, William J. Bowman wrote:
> > Thanks! One follow-up:
> >
> > > 1. make these functions, not macros
> > The main implementation is a procedure, but I think I need a macro to get the
> > syntactic interface I want.
> >
> > Is there some reason to avoid macros?
>
> You certainly can use macros in the implementation, but just remember that
> macros evaluate at compile time and most contracts have to be checked at
> runtime: so a contract can't *exclusively* be a macro ... runtime code has
> to be generated.
>
> Robby's comment about code size is relevant also:  contracts are not debug
> mode only like assertions in C ... Racket's contracts live on in release
> mode compiles, so you want to minimize the amount of runtime code required
> to implement them.
>
> George

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

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20201030190826.GA1988871%40williamjbowman.com.

[George Neuner]

On 10/30/2020 3:08 PM, William J. Bowman wrote:
> Let me aid this discussion by copying in the ~10 lintes of code in question:
>
> > (define-syntax (dictof syn)
> > (syntax-parse syn
> > [(_ (k:id pred?) ...)
> > (quasisyntax/loc syn
> > (dictof/proc `((k . ,pred?) ...)))]))
> >
> > (define ((dictof/proc spec) h)
> > (and (eq? (dict-keys h) (dict-keys spec))
> > (for/and ([(k pred?) (in-dict spec)])
> > (pred? (dict-ref h k)))))
>
> The macro is merely a syntactic transformation to 1 line of code that implements
> the functionality of the contract at run-time.
> Is there some reason to avoid macros in this particular case?

There's rarely any problem with macros that only provide syntactic sugar.

The issues wrt contracts are how heavy are the dictionary functions. 
The FOR loop is concerning because the check time is proportional to the
size of the dictionary  [again recalling that contracts live on in
release code].

For performance it would be better to enforce the predicate on values as
they are entered, and then assume anything already in the dictionary is
correct.  It is sensible to provide a function that validates the whole
dictionary, but I would make it something the programmer has to invoke
deliberately rather than a contract to be enforced at (even just 1st in
module) mention of the dictionary.

YMMV,
George

[William J. Bowman]

Thanks for the feedback! Some of these were not concerns for my use case, so I’ll do a bit more design before submitting something.

--
Sent from my phoneamajig

> On Oct 30, 2020, at 12:36, George Neuner <gneu...@comcast.net> wrote:
>
> 

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

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/95997336-33d4-5c5b-b329-9ea691fe59ef%40comcast.net.

[jackh...@gmail.com]

I'm not sure, but I have a feeling Ben's suggestion to make them functions instead of macros wasn't about the performance implications of macros. I think it was about this particular symmetry:

- A (list 1 'apple "banana") is a (list/c number? symbol? string?)
- A (hash 'a 1 'b "foo") is a (dictof 'a number? 'b string?)

That is, when the keys are known statically, all the functions for creating dictionaries and hashes typically go with a flat and alternating sequence of key-value arguments. I think a contract combinator for dicts where the keys are known should have the same shape.

One other point: dictof is a confusing name. We would have list/c and listof, vector/c and vectorof, and hash/c and dictof. And the first two pairs would make the exact opposite decision as the third pair about which name is for the heterogeneous known-size case and which is for homogeneous collections.

Honestly I'd suggest naming it heterogeneous-dict/c. The contract will almost always span multiple lines no matter how long a name you pick, and I'm sick and tired of guessing which one of list/c, listof, *list/c, and list*of is the one I actually want. Words are underrated.

[Ben Greenman]

On 10/31/20, jackh...@gmail.com <jackh...@gmail.com> wrote:
> I'm not sure, but I have a feeling Ben's suggestion to make them functions
> instead of macros wasn't about the performance implications of macros.

Right. I was only thinking that macros are hard to build on. But then,
I can use dictof/proc here.

[William J. Bowman]

For the curious/eager, I've submitted a PR with my initial implementation redesigned along the lines of the discussion here:

https://github.com/racket/racket/pull/3670

--
William J. Bowman

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

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAFUu9R7xVB7KTkBPms40qLLhqcqPhKB_gVVXeYKKAMH0V1-BRQ%40mail.gmail.com.