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 ⊥
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
