<div dir="ltr">What if you added an extra field to immutable values (ie all TR structs would have this hidden field) such that, when they passed across a boundary, the field got mutated to say what type it passed at. Then, when the value passed back into TR, TR could check to see if has this secret field and what the type was and then avoid more checking.<div> <br></div><div style>Assuming that I understood Neil's situation properly (an ADT whose struct manipulations happen entirely in TR but where opaque values pass in and out of TR), I bet that would make the checks a lot cheaper.</div> <div style><br>Robby</div><div style><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Jan 6, 2013 at 9:50 AM, Sam Tobin-Hochstadt <span dir="ltr"><<a href="mailto:samth@ccs.neu.edu" target="_blank">samth@ccs.neu.edu</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Sat, Jan 5, 2013 at 6:55 PM, Neil Toronto <<a href="mailto:neil.toronto@gmail.com">neil.toronto@gmail.com</a>> wrote:<br> ><br> > What if RAList could be exported as a polymorphic, opaque type?<br> ><br> > It seems the contract system could then exploit the fact that an RAList is<br> > always well-typed. What would it take? Tagging structs? A special chaperone?<br> > User-definable contracts for user struct types?<br> ><br> > If RAList were a polymorphic, opaque type, how could we put a contract on<br> > the following function, which instantiates it?<br> ><br> > (: ralist-sum ((RAList Real) -> Real))<br> > (define (ralist-sum lst)<br> > (apply + (ralist->list lst)))<br> ><br> > Could exhaustively checking the structure of a polymorphic type be put off<br> > until such functions are called?<br> ><br> > Would it be impossible for mutable struct types to be opaque? Would having a<br> > type variable in positive position cause problems?<br> ><br> > I really don't want to write "Performance Warning: Using random-access lists<br> > in untyped Racket is currently 500x slower than using them in Typed Racket"<br> > at the top of the documentation for `data/ralist'.<br> <br> </div>There are two answers to the questions asked here.<br> <br> 1. Could we turn the structural checks into simpler constant-time<br> checks? Answer: no. The problem is that an untyped module can get<br> its hands on an (RAList Integer) and an (RAList String), and then<br> confuse them, say with `append`. The only way to distinguish these<br> types is with structural checks of the implementation.<br> <br> 2. Could we delay some of these checks, so that `list-ref` could be<br> faster than O(N)? Answer: yes. Robby has added the `#:lazy` variant<br> of structure contract checking, and you could try adding that to the<br> contract generation (in `typed-racket/private/type-contract.rkt`) and<br> see if that improves performance. However, this may impose other<br> expensive overheads from chaperones and delayed checking, and thus may<br> not make you happy overall. Also, this does not work for mutable<br> fields.<br> <br> It may be that there's something clever here that I haven't thought<br> of, but I believe that polymorphic data structures and contract<br> boundaries involve substantial inherent costs, as you have discovered.<br> <span class="HOEnZb"><font color="#888888"><br> Sam<br> </font></span><div class="HOEnZb"><div class="h5">_________________________<br> Racket Developers list:<br> <a href="http://lists.racket-lang.org/dev" target="_blank">http://lists.racket-lang.org/dev</a><br> </div></div></blockquote></div><br></div>