[racket-dev] Math library initial commit almost ready; comments on issues welcome
On 10/01/2012 04:20 PM, Sam Tobin-Hochstadt wrote:
> On Mon, Oct 1, 2012 at 6:08 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
>> On 10/01/2012 02:06 PM, Sam Tobin-Hochstadt wrote:
>>>
>>> On Mon, Oct 1, 2012 at 2:26 PM, Neil Toronto <neil.toronto at gmail.com>
>>> wrote:
>> My timing tests also show that typechecking is apparently quadratic in the
>> depth of expressions, regardless of how simple the types are. Is that
>> something you already knew?
>
> This surprises me in general, but I wouldn't be surprised if it were
> the case for some examples. If you have particular examples, that
> would be helpful for trying to fix them. However, some algorithms in
> TR are inherently super-linear.
This is similar to the testing code I wrote, and it also exhibits
quadratic behavior. The `apply*' macro generates the simplest deep
expression possible. It's used to repeatedly apply a function with the
simplest one-argument floating-point type possible.
#lang typed/racket/base #:no-optimize
(require racket/flonum
(for-syntax racket/base))
(define-syntax (apply* stx)
(syntax-case stx ()
[(_ f x 0) #'(f x)]
[(_ f x n) #`(f (apply* f x #,(- (syntax->datum #'n) 1)))]))
(: simple-flabs (Flonum -> Flonum))
(define simple-flabs flabs)
(: flabs* (Flonum -> Flonum))
(define (flabs* x)
(apply* simple-flabs x 1000))
Typechecking is quadratic in the number of nested applications done in
`flabs*'. Changing `simple-flabs' to `flabs' doubles the time; changing
it to `abs' apparently changes typechecking to O(n^3).
>> (The latter is a medium-ish deal for the math library. Most special
>> functions have domains in which they're computed by evaluating a 25- to
>> 50-degree polynomial. Using Horner's method, that's an expression 50 to 100
>> deep; if they're Chebyshev polynomials, it's more like 200-400.)
>
> Is there a reason to generate these expressions statically? Is it
> genuinely faster?
Yes. I assume it's because the CPU can pipeline the entire computation.
I might try splitting them up. There's probably a dividey-conquery way
to minimize the depth of the expression.
>> I've managed to make some headway here in another part of the library, by
>> defining macros only in #lang racket. If their expansions contain typed
>> identifiers, it seems TR is smart enough to not check their contracts when
>> the macros are used in typed code.
>
> Yes, TR should be able to make this work in general -- the contract
> wrapping doesn't happen until the real reference to the identifier is
> expanded.
Nice.
Related question: How do I make this work?
#lang typed/racket
(: plus (Flonum Flonum -> Flonum))
(define (plus a b)
(+ a b))
(module provider racket
(require (submod ".."))
(provide inline-plus)
(define-syntax-rule (inline-plus a b) (plus a b)))
(require 'provider)
(inline-plus 1.2 2.3)
I've tried the various module-declaration forms, but can't find the
right incantation. Am I trying to do something that I can't? (FWIW, I
can't make it work in untyped Racket, either.)
Neil ⊥