headers
Neil Toronto | 15 Aug 2012 05:52
Picon
Gravatar

Wrapping loops for TR isn't working, and the type annotations are for the wrong value

I like the idea of wrapping Racket's standard "for" loops with a few 
annotations and letting inference figure out the rest of the types.

The problem is, it doesn't work very well.

  1. Even though the loop's type is technically optional, it seems to 
always be required.

  2. Many simple loops don't typecheck anyway.

  3. It's a PITA to write new kinds of "for" loops in the same style.

  4. A #:when clause can only be last.

#4 is acknowledged in the TR reference.

As an example of #1, the following is one of the simplest loops:

   ;; "Type Checker: ... add more type annotations"
   ;(for/list: ([i  (in-range 5)]) i)

   ;; This works:
   (for/list: : (Listof Integer) ([i  (in-range 5)]) i)

Besides being annoying, it's obviously redundant.

For examples of #2, these don't typecheck:

   (for/vector: : (Vectorof Integer) ([i  (in-range 5)]) i)
(Continue reading)

Permalink | Reply |
headers
Sam Tobin-Hochstadt | 15 Aug 2012 13:24
Favicon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On Tue, Aug 14, 2012 at 11:52 PM, Neil Toronto
<neil.toronto@...> wrote:
>
> Some typed "for" loops would have to be reimplemented, unless inference
> improves a lot. To make this easier, I've attached an example implementation
> of `for/vector:' and `for*/vector:'. It allows both body and result
> annotations, handles #:length properly, allows #:when clauses anywhere, and
> fixes the two bugs in `for/vector' I reported today.

Thanks for doing this.  I worry a little about re-implementing
`for/vector`, since now we have two implementations to keep in sync.
Eventually, I think Typed Racket needs to support more agressive
inference than it currently does; that's the reality of dealing with a
macro-generated language.  But for the moment, this would make things
better for people.

Two questions: (1) how similar is the generated code to the expansion
of plain `for/vector`, and (2) would it be possible to abstract the
implementation of Racket's `for/vector` to allow you to re-use some of
that code here?
--

-- 
sam th
samth@...
_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
Permalink | Reply |
headers
Neil Toronto | 15 Aug 2012 15:54
Picon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On 08/15/2012 05:24 AM, Sam Tobin-Hochstadt wrote:
> On Tue, Aug 14, 2012 at 11:52 PM, Neil Toronto <neil.toronto <at> gmail.com> wrote:
>>
>> Some typed "for" loops would have to be reimplemented, unless inference
>> improves a lot. To make this easier, I've attached an example implementation
>> of `for/vector:' and `for*/vector:'. It allows both body and result
>> annotations, handles #:length properly, allows #:when clauses anywhere, and
>> fixes the two bugs in `for/vector' I reported today.
>
> Thanks for doing this.  I worry a little about re-implementing
> `for/vector`, since now we have two implementations to keep in sync.
> Eventually, I think Typed Racket needs to support more agressive
> inference than it currently does; that's the reality of dealing with a
> macro-generated language.  But for the moment, this would make things
> better for people.

Agree on all counts.

BTW, what do you think of deprecating result annotations and using body 
annotations instead?

> Two questions: (1) how similar is the generated code to the expansion
> of plain `for/vector`[?]...

In the case where #:length is missing, not very. I couldn't use 
`for/list:' and convert to a vector because I couldn't reliably generate 
(Listof T) from the result type (because of type aliases). On the plus 
side, mine's about twice as fast. It expands to plain `for:' and bangs 
values into a growable vector.
(Continue reading)

Permalink | Reply |
headers
Sam Tobin-Hochstadt | 15 Aug 2012 16:05
Favicon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On Wed, Aug 15, 2012 at 9:54 AM, Neil Toronto <neil.toronto@...> wrote:
> On 08/15/2012 05:24 AM, Sam Tobin-Hochstadt wrote:
>>
>> On Tue, Aug 14, 2012 at 11:52 PM, Neil Toronto <neil.toronto@...>
>> wrote:
>>>
>>>
>>> Some typed "for" loops would have to be reimplemented, unless inference
>>> improves a lot. To make this easier, I've attached an example
>>> implementation
>>> of `for/vector:' and `for*/vector:'. It allows both body and result
>>> annotations, handles #:length properly, allows #:when clauses anywhere,
>>> and
>>> fixes the two bugs in `for/vector' I reported today.
>>

> BTW, what do you think of deprecating result annotations and using body
> annotations instead?

I'm not sure yet.

>> Two questions: (1) how similar is the generated code to the expansion
>> of plain `for/vector`[?]...
>
>
> In the case where #:length is missing, not very. I couldn't use `for/list:'
> and convert to a vector because I couldn't reliably generate (Listof T) from
> the result type (because of type aliases). On the plus side, mine's about
> twice as fast. It expands to plain `for:' and bangs values into a growable
> vector.
(Continue reading)

Permalink | Reply |
headers
Neil Toronto | 15 Aug 2012 16:36
Picon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On 08/15/2012 08:05 AM, Sam Tobin-Hochstadt wrote:
> On Wed, Aug 15, 2012 at 9:54 AM, Neil Toronto <neil.toronto <at> gmail.com> wrote:
>> When #:length is given, it's similar in that it creates a vector outside the
>> loop and bangs values into it. But I have to start with (define vs (vector))
>> and then (set! vs (make-vector n v)) when the first value `v' is computed.
>> The docs for `for/vector' say any values not computed in the loop are
>> supposed to be 0, but that doesn't work well in TR: it'd have to create a
>> (Vectorof (U T 0)). Ick.
>
> So then the first value computed is replicated everywhere?  That seems
> unappealing as well.

It costs nothing, and if the #:length argument matches the number of 
iterations, the user never sees it.

Other options:

  1. Raise an error when the vector isn't filled.
  2. Return a (Vectorof (U T #f)) (better than (Vectorof (U T 0))?).
  3. Always return a vector whose length is the number of iterations.

For #3, the #:length argument would mean one of two things:

  A. An upper bound on the number of iterations.
  B. A "best guess" at the number of iterations.

For B, I could make it just as efficient as my current implementation 
when the guess is correct. Not giving #:length would be equivalent to 
giving #:length 1 (or some other small number).
(Continue reading)

Permalink | Reply |
headers
J. Ian Johnson | 15 Aug 2012 16:39
Favicon

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value


----- Original Message -----
From: "Neil Toronto" <neil.toronto@...>
To: "Sam Tobin-Hochstadt" <samth@...>
Cc: "<dev@...>" <dev@...>
Sent: Wednesday, August 15, 2012 10:36:36 AM GMT -05:00 US/Canada Eastern
Subject: Re: [racket-dev] Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On 08/15/2012 08:05 AM, Sam Tobin-Hochstadt wrote:
> On Wed, Aug 15, 2012 at 9:54 AM, Neil Toronto
<neil.toronto@...> wrote:
>> When #:length is given, it's similar in that it creates a vector outside the
>> loop and bangs values into it. But I have to start with (define vs (vector))
>> and then (set! vs (make-vector n v)) when the first value `v' is computed.
>> The docs for `for/vector' say any values not computed in the loop are
>> supposed to be 0, but that doesn't work well in TR: it'd have to create a
>> (Vectorof (U T 0)). Ick.
>
> So then the first value computed is replicated everywhere?  That seems
> unappealing as well.

>It costs nothing, and if the #:length argument matches the number of 
>iterations, the user never sees it.

Not so, it costs memory leaks if the first value would otherwise be garbage collected.
-Ian

_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
(Continue reading)

Permalink | Reply |
headers
Neil Toronto | 15 Aug 2012 16:42
Picon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On 08/15/2012 08:39 AM, J. Ian Johnson wrote:
>
> ----- Original Message -----
> From: "Neil Toronto" <neil.toronto <at> gmail.com>
> To: "Sam Tobin-Hochstadt" <samth <at> ccs.neu.edu>
>> So then the first value computed is replicated everywhere?  That seems
>> unappealing as well.
>
>> It costs nothing, and if the #:length argument matches the number of
>> iterations, the user never sees it.
>
> Not so, it costs memory leaks if the first value would otherwise be garbage collected.
> -Ian

I hadn't thought of memory leaks. Strike "it costs nothing," then.

Neil ⊥

_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
Permalink | Reply |
headers
Jens Axel Søgaard | 15 Aug 2012 17:38

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

2012/8/15 Neil Toronto <neil.toronto@...>:

> Other options:
>
>  1. Raise an error when the vector isn't filled.
>  2. Return a (Vectorof (U T #f)) (better than (Vectorof (U T 0))?).
>  3. Always return a vector whose length is the number of iterations.

Or a variation of 2.:

4. Let the user supply the value to fill the vector with.

This could be relevant in cases where less than the #:length specified
number of values is produced.

    > (for/vector #:length 10 ([i 5]) i)
    '#(0 1 2 3 4 0 0 0 0 0)

/Jens Axel
_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
Permalink | Reply |
headers
Matthew Flatt | 15 Aug 2012 17:42
Picon
Favicon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

At Wed, 15 Aug 2012 17:38:18 +0200, Jens Axel Søgaard wrote:
> 2012/8/15 Neil Toronto <neil.toronto <at> gmail.com>:
> 
> > Other options:
> >
> >  1. Raise an error when the vector isn't filled.
> >  2. Return a (Vectorof (U T #f)) (better than (Vectorof (U T 0))?).
> >  3. Always return a vector whose length is the number of iterations.
> 
> Or a variation of 2.:
> 
> 4. Let the user supply the value to fill the vector with.

At Wed, 15 Aug 2012 08:37:44 -0600, Matthew Flatt wrote:
> As for the problem with padding `#:length'-specified vectors with 0,
> maybe there should be a `#:default' clause to provide the fill value,
> instead?

I pushed this change, but as `#:fill' instead of `#:default'.

_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
Permalink | Reply |
headers
Matthew Flatt | 15 Aug 2012 16:37
Picon
Favicon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

At Wed, 15 Aug 2012 07:54:16 -0600, Neil Toronto wrote:
> I wouldn't want to because `for/vector' is currently broken when 
> #:length is given. (See PR 13029 and PR 13030.)
> 
> I think the only way to fix it is to implement it like I did: expand to 
> plain `for:' and mutate an external index.

I pushed a repair that doesn't involve `set!'.

At Wed, 15 Aug 2012 10:05:47 -0400, Sam Tobin-Hochstadt wrote:
> On Wed, Aug 15, 2012 at 9:54 AM, Neil Toronto
<neil.toronto@...> wrote:
> > On the plus side, mine's about
> > twice as fast. It expands to plain `for:' and bangs values into a growable
> > vector.
> 
> In that case, presumably we should change `for/vector` in
> `racket/base` to the faster version.
> 
> Matthew, does this seem reasonable?

I can change `for/vector' to avoid lists and grow a vector. On my test
of 1000 elements, the difference is more like x1.5 instead of x2,
though.

As for the problem with padding `#:length'-specified vectors with 0,
maybe there should be a `#:default' clause to provide the fill value,
instead?

_________________________
(Continue reading)

Permalink | Reply |
headers
Neil Toronto | 15 Aug 2012 20:17
Picon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

I've attached my latest. It's possibly better.

On 08/15/2012 08:05 AM, Sam Tobin-Hochstadt wrote:
> So then the first value computed is replicated everywhere?  That seems
> unappealing as well.

I've implemented #:fill in this one. If both #:length and #:fill are 
given, the vector is created with the fill value. If only #:fill is 
given, it's a syntax error. If only #:length is given, it fills the 
vector with the first computed value.

> Also, is there any way you could generate code that uses a binding,
> instead of `set!`?  That will probably improve the performance.

I tried, but `for/fold:' doesn't handle #:when, and `for*/fold:' doesn't 
work at all.

>> I think I could work one up that expands to code with annotations when used
>> from TR and to code without annotations otherwise. I'd use the
>> "maybe-annotate" macro (`ann:') for every annotation, not just for
>> annotating with the optional result and body types.
>
> I don't think that's a good idea -- then `racket/base` would have to
> expand to Typed Racket-specific code.  Is there a way that you can
> come up with an abstraction that is oblivious to Typed Racket?

This version defines a macro `base-for/vector'. Example:

   (base-for/vector for ann T K (clauses ...) body-expr)
(Continue reading)

Permalink | Reply |
headers
Neil Toronto | 15 Aug 2012 21:30
Picon
Gravatar

Re: Wrapping loops for TR isn't working, and the type annotations are for the wrong value

On 08/15/2012 08:05 AM, Sam Tobin-Hochstadt wrote:
> On Wed, Aug 15, 2012 at 9:54 AM, Neil Toronto <neil.toronto <at> gmail.com> wrote:
>> BTW, what do you think of deprecating result annotations and using body
>> annotations instead?
>
> I'm not sure yet.

This short exercise might convince you: implement `for/vector:' without 
a body type annotation in terms of `for/list:' or `for/fold:'. Don't use 
internal or unpublished Typed Racket goodies.

There's an O(n^2) solution that converts the vector to a list and back 
every iteration, but it doesn't count.

Neil ⊥

_________________________
  Racket Developers list:
  http://lists.racket-lang.org/dev
Permalink | Reply |

Gmane