[racket-dev] Machinery for eliding contracts

On 06/09/2014 10:25 AM, Neil Toronto wrote:
> On 06/09/2014 01:19 AM, Eric Dobson wrote:
>>
>> Does this seem like a reasonable thing to support/do people see issues
>> with it?
>
> I can only speak on reasonableness, and my answer is emphatically YES.
>
> Typed Racket is a great language in which to define and use data
> structures: access is very fast, and many properties are checked
> statically. But accessor performance suffers badly when the data types
> are used in untyped Racket. If access uses higher-order functions (e.g.
> math/array), wrapping the functions slows access by a very high constant
> factor. If the data structures are first-order, every O(1) access
> becomes O(n).
>
> I recently had to work around this in Plot when I needed an untyped
> module to be able to operate on typed BSP trees. I ended up making a
> typed weak hash map from "BSP tree handles" (gensyms) to BSP trees, and
> writing a new untyped API for operating on trees using handles. It was
> ugly. If the untyped and typed modules had been too tightly coupled, it
> would have been impossible.
>
> IIUC, your proposal would make untyped use of typed data structures
> actually feasible for real-world use. So again, YES.

Here's a concrete example, using Typed Racket to define a new list type.


#lang racket

(module typed-defs typed/racket
   (provide list->my-list
            my-first)

   (define-type (My-Listof A) (U Null (my-cons A)))
   (struct (A) my-cons ([fst : A] [snd : (My-Listof A)]) #:transparent)

   (: list->my-list (All (A) (-> (Listof A) (My-Listof A))))
   (define (list->my-list xs)
     (if (empty? xs) xs (my-cons (first xs) (list->my-list (rest xs)))))

   (: my-first (All (A) (-> (My-Listof A) A)))
   (define (my-first xs)
     (if (empty? xs) (error 'bad) (my-cons-fst xs)))

   ;; Timing loop speed is very fast and O(1)
   (define lst (list->my-list '(1)))
   (for ([_  (in-range 5)])
     (time (for ([_  (in-range 1000000)])
             (my-first lst))))
   )

(require 'typed-defs)

;; Timing loop speed is very slow and O(n)
(define lst (list->my-list '(1)))
(for ([_  (in-range 5)])
   (time (for ([_  (in-range 1000000)])
           (my-first lst))))


I get 4ms for the timing loop in the typed module, and 620ms for the 
timing loop in the untyped module, so the constant factor is about 150.

When I change the test data from '(1) to '(1 2), the untyped module's 
timing loop takes about 1010ms. The contract boundary has changed the 
asymptotic complexity of `my-first' from O(1) to O(n).

Neil ⊥