Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On 10/01/2012 02:06 PM, Sam Tobin-Hochstadt wrote: On Mon, Oct 1, 2012 at 2:26 PM, Neil Toronto neil.toro...@gmail.com wrote: * `math/base' re-exports `racket/math', but with extra constants (like `phi.0') and functions (like `power-of-two?'). It also exports improved hyperbolic functions, such as a new `sinh' that's much more accurate near zero: in the worst case, 2e-16 relative error (which is great) instead of 0.5 (which is really bad). But its type in `math/base' is (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. Why aren't you able to do this? Shortly, because the type checker doesn't have enough information to check only reachable code in each pass through the function's definition. Here's `flsinh' without most of its implementation, and with only three of its potential `case-' types: #lang typed/racket (require racket/flonum) (: flsinh+ (Positive-Flonum - Positive-Flonum)) (define (flsinh+ x) (error 'unimplemented)) (: flsinh (case- (Negative-Flonum - Negative-Flonum) (Positive-Flonum - Positive-Flonum) (Flonum - Flonum))) (define (flsinh x) (cond [(x . fl . 0.0) (flsinh+ x)] [(x . fl . 0.0) (- (flsinh+ (- x)))] [else x])) While TR checks the definition of `flsinh' with the type Negative-Flonum - Negative-Flonum, it gives this type error: Type Checker: Expected Negative-Flonum, but got Positive-Flonum in: (flsinh+ x) It doesn't know that (flsinh+ x) is unreachable when x : Negative-Flonum. There are similar type errors in the second clause with flsinh : Positive-Flonum - Positive-Flonum. This definition also fails in the same way: (define (flsinh x) (cond [(negative? x) (- (flsinh+ (- x)))] [(positive? x) (flsinh+ x)] [else x])) This definition gives only one type error, in the first clause: (define (flsinh x) (cond [((make-predicate Positive-Flonum) x) (flsinh+ x)] [((make-predicate Negative-Flonum) x) (- (flsinh+ (- x)))] [else x])) By the second clause, x : Negative-Flonum when `flsinh' has either type. (It actually leaves Flonum-Nan out of the type of `x', which is impressively correct. :D) This WOULD work: (define (flsinh x) (cond [(flpositive? x) (flsinh+ x)] [(flnegative? x) (- (flsinh+ (- x)))] [else x])) if I could define `flpositive?' and `flnegative?' with the types (: flnegative? (case- (Nonnegative-Flonum - False : Nothing) (Flonum - Boolean : Negative-Flonum))) (: flpositive? (case- (Nonpositive-Flonum - False : Nothing) (Flonum - Boolean : Positive-Flonum))) But I haven't been able to implement them for the same reason I can't define `flsinh' with more specific types. Also, it looks like a hack. Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
I think this idea is worth exploring. Sam and Eli should implement it. On Oct 5, 2012, at 8:39 AM, Eli Barzilay wrote: Yesterday, Matthias Felleisen wrote: I know What I mean is an _abstraction mechanism_ inside of TR. Possibly something that nobody else has. +18.59 And a quick reminder -- below is the ancient hack I once did for such things, maybe something like this would be easier now. Possibly much easier: if a type is (foo ...) and `foo' is phase-1-bound to a macro (anything that is not a bound type), then just expand it -- so that in Neil's case the code could be: (define-syntax-rule (Xs-Xs T ...) (case- (T - T) ...)) (: foo : (Xs-Xs Zero Flonum Real Float-Complex Complex)) (Either way, this means that it's easy to create huge types, and therefore stressing TR's not-too-fast typechecker, but it sounds like not having an abstraction doesn't stand in Neil's way to write huge types anyway.) #lang typed-scheme (require (for-syntax scheme/base scheme/private/at-syntax)) ;; (define-syntax (STX stx) ;; (syntax-case stx () ;; [(_ expr) (at-syntax #'expr)])) (define-syntax (:: stx) (syntax-case stx (:) [(_ name : x ...) (with-syntax ([(x ...) (map at-syntax (syntax-list #'(x ...)))]) #`(: name : x ...))])) (define-for-syntax Number #'Number) (define-for-syntax (T1 . - . T2) #`(#,T1 - #,T2)) (:: twice : (let ([n (Number . - . Number)]) (n . - . n))) (define (twice f) (lambda (x) (f (f x ((twice add1) 10) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Mon, Oct 1, 2012 at 6:49 PM, Neil Toronto neil.toro...@gmail.com wrote: 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). As far as I can tell, there's not actually quadratic behavior here, it's just slow. However, the major slowness seems to be in `syntax-parse` itself, or at least that's what the profiler shows. As a simple benchmark, I tried writing a little syntax analyzing function in syntax-parse, syntax-case, and match: https://gist.github.com/3828408 . Unfortunately, it shows that `syntax-parse` is about 4x slower than `syntax-case`, and `match` is 2.5x faster again. Hopefully, there are ways to work around this, and I won't have to avoid `syntax-parse`. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Oct 1, 2012, at 2:26 PM, Neil Toronto wrote: (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. Sam, are we lacking a linguistic mechanism for people like Neil to write down such types in a concise way? I think this came up in the PADL context too. -- Matthias _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Thu, Oct 4, 2012 at 5:31 PM, Matthias Felleisen matth...@ccs.neu.edu wrote: On Oct 1, 2012, at 2:26 PM, Neil Toronto wrote: (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. Sam, are we lacking a linguistic mechanism for people like Neil to write down such types in a concise way? I think this came up in the PADL context too. Yes. Vincent has a slightly-nicer mechanism used internally, but nothing great that TR programmers can use. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Oct 4, 2012, at 5:34 PM, Sam Tobin-Hochstadt wrote: On Thu, Oct 4, 2012 at 5:31 PM, Matthias Felleisen matth...@ccs.neu.edu wrote: On Oct 1, 2012, at 2:26 PM, Neil Toronto wrote: (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. Sam, are we lacking a linguistic mechanism for people like Neil to write down such types in a concise way? I think this came up in the PADL context too. Yes. Vincent has a slightly-nicer mechanism used internally, but nothing great that TR programmers can use I know What I mean is an _abstraction mechanism_ inside of TR. Possibly something that nobody else has. -- Matthias _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Mon, Oct 1, 2012 at 9:44 PM, Neil Toronto neil.toro...@gmail.com wrote: The only bit that bothers me is the (begin (not (flonum-wrapper? x)) ...) stuff left lying around after TR's optimizer eliminates the branches in the expansions of `fw+'. IIRC, they cause futures to sync, but I'm going to believe that they won't always - or will be optimized away - just so I can have a decent solution to the typed macro problem. This code is left around because TR can't prove that `not` and `flonum-wrapper?` are pure functions. Eventually, TR should include a purity analysis that can fix this, but it can't do that now. The fact that basically all structure operations are future-unsafe is a bigger issue. I talked to James about it at ICFP, but I don't know what would be required to improve the situation. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
This surprises me, since not and make-struct-type are in '#%kernel, they should have this kind of information baked in, without a purity analysis. -Ian - Original Message - From: Sam Tobin-Hochstadt sa...@ccs.neu.edu To: Neil Toronto neil.toro...@gmail.com Cc: dev@racket-lang.org dev@racket-lang.org Sent: Tuesday, October 2, 2012 9:44:13 AM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome On Mon, Oct 1, 2012 at 9:44 PM, Neil Toronto neil.toro...@gmail.com wrote: The only bit that bothers me is the (begin (not (flonum-wrapper? x)) ...) stuff left lying around after TR's optimizer eliminates the branches in the expansions of `fw+'. IIRC, they cause futures to sync, but I'm going to believe that they won't always - or will be optimized away - just so I can have a decent solution to the typed macro problem. This code is left around because TR can't prove that `not` and `flonum-wrapper?` are pure functions. Eventually, TR should include a purity analysis that can fix this, but it can't do that now. The fact that basically all structure operations are future-unsafe is a bigger issue. I talked to James about it at ICFP, but I don't know what would be required to improve the situation. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Tue, Oct 2, 2012 at 9:55 AM, J. Ian Johnson i...@ccs.neu.edu wrote: This surprises me, since not and make-struct-type are in '#%kernel, they should have this kind of information baked in, without a purity analysis. If you're suggesting that the Racket compiler should perform the purity analysis, then that would be nice, but it would be harder, since it would require recording information for the output of `make-struct-type`. Typed Racket has information about structures at a higher level. -Ian - Original Message - From: Sam Tobin-Hochstadt sa...@ccs.neu.edu To: Neil Toronto neil.toro...@gmail.com Cc: dev@racket-lang.org dev@racket-lang.org Sent: Tuesday, October 2, 2012 9:44:13 AM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome On Mon, Oct 1, 2012 at 9:44 PM, Neil Toronto neil.toro...@gmail.com wrote: The only bit that bothers me is the (begin (not (flonum-wrapper? x)) ...) stuff left lying around after TR's optimizer eliminates the branches in the expansions of `fw+'. IIRC, they cause futures to sync, but I'm going to believe that they won't always - or will be optimized away - just so I can have a decent solution to the typed macro problem. This code is left around because TR can't prove that `not` and `flonum-wrapper?` are pure functions. Eventually, TR should include a purity analysis that can fix this, but it can't do that now. The fact that basically all structure operations are future-unsafe is a bigger issue. I talked to James about it at ICFP, but I don't know what would be required to improve the situation. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
The high level is that the predicate with identifier given by build-struct-names should have the same purity/predicate properties of something like string?. As for not, it's just an alias for false?, so it should have the same info again. -Ian - Original Message - From: Sam Tobin-Hochstadt sa...@ccs.neu.edu To: J. Ian Johnson i...@ccs.neu.edu Cc: dev dev@racket-lang.org, Neil Toronto neil.toro...@gmail.com Sent: Tuesday, October 2, 2012 10:02:50 AM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome On Tue, Oct 2, 2012 at 9:55 AM, J. Ian Johnson i...@ccs.neu.edu wrote: This surprises me, since not and make-struct-type are in '#%kernel, they should have this kind of information baked in, without a purity analysis. If you're suggesting that the Racket compiler should perform the purity analysis, then that would be nice, but it would be harder, since it would require recording information for the output of `make-struct-type`. Typed Racket has information about structures at a higher level. -Ian - Original Message - From: Sam Tobin-Hochstadt sa...@ccs.neu.edu To: Neil Toronto neil.toro...@gmail.com Cc: dev@racket-lang.org dev@racket-lang.org Sent: Tuesday, October 2, 2012 9:44:13 AM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome On Mon, Oct 1, 2012 at 9:44 PM, Neil Toronto neil.toro...@gmail.com wrote: The only bit that bothers me is the (begin (not (flonum-wrapper? x)) ...) stuff left lying around after TR's optimizer eliminates the branches in the expansions of `fw+'. IIRC, they cause futures to sync, but I'm going to believe that they won't always - or will be optimized away - just so I can have a decent solution to the typed macro problem. This code is left around because TR can't prove that `not` and `flonum-wrapper?` are pure functions. Eventually, TR should include a purity analysis that can fix this, but it can't do that now. The fact that basically all structure operations are future-unsafe is a bigger issue. I talked to James about it at ICFP, but I don't know what would be required to improve the situation. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Mon, Oct 1, 2012 at 1:26 PM, Neil Toronto neil.toro...@gmail.com wrote: I think I'm about a week away from having the math library's initial commit ready. It just needs some more docs and test cases. Here are the high-level issues, for which I'm soliciting comments, suggestions, questions, and answers: * Compile time. It currently takes 1m20s to compile `math' without docs on my beefy laptop. That's down from 2m30s, with the reduction from replacing general functions with flonum-specific functions in over half of the flonum code (e.g. replacing `+' with `fl+'). I think I can get it down to 45s or so by doing that in the rest of the files, maybe further if I use fixnum-specific ops on indexes and counters. That task is mind-numbing and takes time. Does anybody mind if I check the code in before doing it? (Maybe let the TR team take a crack at PR 13098 first, which is about this issue?) * flvectors don't print nicely, which puts them at odds with their new complex-valued counterpart, fcvectors: (require math/vector racket/flonum) (fcvector 1.0+0.0i 2.0+0.0i) (fcvector 1.0+0.0i 2.0+0.0i) (flvector 1.0 2.0) #flvector I looked at the C code for printing flvectors, and changing it is beyond me right now. Also, are there serious objections to making flvectors print in constructor style? * `math/base' re-exports `racket/math', but with extra constants (like `phi.0') and functions (like `power-of-two?'). It also exports improved hyperbolic functions, such as a new `sinh' that's much more accurate near zero: in the worst case, 2e-16 relative error (which is great) instead of 0.5 (which is really bad). But its type in `math/base' is (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. * It makes sense to me to have `racket/math' re-export `math/base', but `case-' types with one arity (like that of `sinh') can't be converted to contracts. FWIW, this particular contract can be written as a dependent contract. * Another typed/untyped barrier issue: certain functions are actually macros so that TR can optimize around their expansions. (Example: by making `fcvector-ref' a macro, (+ (fcvector-ref xs 0) (fcvector-ref ys 0)) operates entirely on unboxed Float-Complex values.) I really don't want to make an `untyped/math' library to expose the function versions, but I can't think of a way around it. I'm pretty sure none of this is bikeshedding, but I apologize in advance if I'm wrong about that. :) Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On 10/01/2012 02:06 PM, Sam Tobin-Hochstadt wrote: On Mon, Oct 1, 2012 at 2:26 PM, Neil Toronto neil.toro...@gmail.com wrote: PR 13098 isn't really fixable, in some sense. There's just more data there with broader types, so it will always take longer than for more specific types. All of the things I'd do to fix the problem would speed up both the slow and the fast case, without really affecting the gap between them. You're saying it wouldn't hurt to replace functions with more specifically typed functions in general, right? Good point. I think you can speed up the slow cases more than the fast ones, though. Huge `case-' types tend to have this structure: (case- (A0 - B0) ((U A0 A1) - B1) ((U A0 A1 A2) - B2) ((U A0 A1 A2 A3) - B3) ...) The `abs' function, for example, starts this way: (case- (Zero - Zero) (One - One) (Positive-Byte - Positive-Byte) (Byte - Byte) (Positive-Index - Positive-Index) (Index - Index) ...) I've done some timing tests using generated types like this: (case- (Zero - Zero) ((U Zero One) - (U Zero One)) ((U Zero One 2) - (U Zero One 2)) ...) The tests suggest that typechecking application of a function with a type like that is quadratic in the size of the function's type, which makes sense. Could you get something nearer to linear-time by dividing the case types into monotone groups? 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? (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.) * `math/base' re-exports `racket/math', but with extra constants (like `phi.0') and functions (like `power-of-two?'). It also exports improved hyperbolic functions, such as a new `sinh' that's much more accurate near zero: in the worst case, 2e-16 relative error (which is great) instead of 0.5 (which is really bad). But its type in `math/base' is (case- (Zero - Zero) (Flonum - Flonum) (Real - Real) (Float-Complex - Float-Complex) (Complex - Complex)) I haven't been able to give it a type as specific as the type of the `sinh' exported from `racket/math'. Why aren't you able to do this? Probably because I haven't tried hard enough. :p Also, every time I read its type, I get vertigo. I know I've been unable to make a case type mirror the runtime branching done in a function before, even when the computation only happened in the leaves and I used nothing but predicates with filters. I don't remember the specifics, though; it was two months ago. * Another typed/untyped barrier issue: certain functions are actually macros so that TR can optimize around their expansions. (Example: by making `fcvector-ref' a macro, (+ (fcvector-ref xs 0) (fcvector-ref ys 0)) operates entirely on unboxed Float-Complex values.) I really don't want to make an `untyped/math' library to expose the function versions, but I can't think of a way around it. There's no way around this at the moment. 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. Also, the optimizer can probably remove most of the sanity checks I'd need for things like `fcvector-ref'. Further, it looks like I can keep the macros in the files they're currently defined in using submodules. This part could be less painful than I thought. That would be great. Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Mon, Oct 1, 2012 at 6:08 PM, Neil Toronto neil.toro...@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.toro...@gmail.com wrote: PR 13098 isn't really fixable, in some sense. There's just more data there with broader types, so it will always take longer than for more specific types. All of the things I'd do to fix the problem would speed up both the slow and the fast case, without really affecting the gap between them. You're saying it wouldn't hurt to replace functions with more specifically typed functions in general, right? Good point. That isn't what I meant, but it's true as well ... I think you can speed up the slow cases more than the fast ones, though. Huge `case-' types tend to have this structure: (case- (A0 - B0) ((U A0 A1) - B1) ((U A0 A1 A2) - B2) ((U A0 A1 A2 A3) - B3) ...) The `abs' function, for example, starts this way: (case- (Zero - Zero) (One - One) (Positive-Byte - Positive-Byte) (Byte - Byte) (Positive-Index - Positive-Index) (Index - Index) ...) I've done some timing tests using generated types like this: (case- (Zero - Zero) ((U Zero One) - (U Zero One)) ((U Zero One 2) - (U Zero One 2)) ...) The tests suggest that typechecking application of a function with a type like that is quadratic in the size of the function's type, which makes sense. Could you get something nearer to linear-time by dividing the case types into monotone groups? I think the revision you're imagining only works in fairly simple cases -- I think the monotone groups would be small enough in practice that the binary search wouldn't help much. For example, in the snippet of the type of `abs` you give above, all of the monotone groups are of size 1 or 2. 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. (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? * Another typed/untyped barrier issue: certain functions are actually macros so that TR can optimize around their expansions. (Example: by making `fcvector-ref' a macro, (+ (fcvector-ref xs 0) (fcvector-ref ys 0)) operates entirely on unboxed Float-Complex values.) I really don't want to make an `untyped/math' library to expose the function versions, but I can't think of a way around it. There's no way around this at the moment. 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. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [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.toro...@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.toro...@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 ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On Mon, Oct 1, 2012 at 6:49 PM, Neil Toronto neil.toro...@gmail.com wrote: On 10/01/2012 04:20 PM, Sam Tobin-Hochstadt wrote: On Mon, Oct 1, 2012 at 6:08 PM, Neil Toronto neil.toro...@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.toro...@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 unlikely -- I expect it just increases the constant factor. But I'll look into this. (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. This also seems unlikely to me (but almost anything is possible at this level). Have you looked at the output of the decompiler and/or the disassembler on the results? 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.) This program doesn't make sense -- the outer module depends on 'provider (see the `(require 'provider)`) but 'provider depends on the outer module (that's what the inner `require` is doing). That's a cycle, and not allowed, typed or untyped. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Math library initial commit almost ready; comments on issues welcome
On 10/01/2012 06:29 PM, Sam Tobin-Hochstadt wrote: On Mon, Oct 1, 2012 at 6:49 PM, Neil Toronto neil.toro...@gmail.com wrote: #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) This program doesn't make sense -- the outer module depends on 'provider (see the `(require 'provider)`) but 'provider depends on the outer module (that's what the inner `require` is doing). That's a cycle, and not allowed, typed or untyped. You're right, that's wrong. Well, wrong-ish. Modules try to give the illusion of being evaluated top-to-bottom, but that apparently can't hold here. FWIW, here's something that does work, and does what I want: #lang racket/base ;; Struct definition (module typed-struct typed/racket/base (struct: flonum-wrapper ([value : Flonum]) #:transparent) (provide (struct-out flonum-wrapper))) ;; Macros (module untyped-syntax racket/base (require racket/flonum (submod .. typed-struct)) (provide fw+) (define-syntax-rule (fw+ x-expr y-expr) (let ([x x-expr] [y y-expr]) (cond [(not (flonum-wrapper? x)) (raise-argument-error 'fw+ flonum-wrapper 0 x y)] [(not (flonum-wrapper? y)) (raise-argument-error 'fw+ flonum-wrapper 1 x y)] [else (flonum-wrapper (fl+ (flonum-wrapper-value x) (flonum-wrapper-value y)))]))) ) ;; Definitions that depend on macros (module more-typed-struct typed/racket/base (require (submod .. typed-struct) (submod .. untyped-syntax)) (provide fwdbl) (: fwdbl (flonum-wrapper - flonum-wrapper)) (define (fwdbl x) (fw+ x x))) (require 'typed-struct 'untyped-syntax 'more-typed-struct) (provide (all-from-out (submod . typed-struct) ; `submod' is necessary? (submod . untyped-syntax) (submod . more-typed-struct))) The only bit that bothers me is the (begin (not (flonum-wrapper? x)) ...) stuff left lying around after TR's optimizer eliminates the branches in the expansions of `fw+'. IIRC, they cause futures to sync, but I'm going to believe that they won't always - or will be optimized away - just so I can have a decent solution to the typed macro problem. Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
