Re: [racket-dev] Using licensed code
Hi, 2012/7/1 Eli Barzilay e...@barzilay.org Three hours ago, Neil Toronto: [*] Unfortunately, the `science' collection has a license problem: the stated license (LGPL) at the top any of its files can't be the actual license if the file was derived from the Gnu Science Library (GSL), which is GPL. Most of the files I'm interested in converting to Typed Racket are from the GSL. GPL is a problem. I would absolute *love* to get proper linear algebra libraries. With proper I mean that areas such as eigenvalue computations and singular value decomposition is included. The license of GSL is of course a problem. The readline solution doesn't really fit well in this context. However GSL is not the only matrix library out there. LAPACK ( http://www.netlib.org/lapack/) has license that fits better. The code is in Fortran 90 though, so it might be harder to translate directly. That said, it might make sense to go the FFI-route for matrix computations. Getting the details right for the more advanced algorithms is hard, very hard. -- Jens Axel Søgaard _ Racket Developers list: http://lists.racket-lang.org/dev
[racket-dev] Proposal for a no-argument
There rare cases where it is useful to have a value that means that no argument was passed to a function. In many of these cases there is a plain value that is used as that mark, with the most idiomatic one being #f, but sometimes others are used. IMO, while such uses of #f are idiomatic, they're a hack where an argument's domain is extended only to mark no argument. A more robust way to do that, which has become idiomatic in Racket is to use (gensym). (And as a sidenote, in other implementations there are various similar eq-based hacks.) IMO, this is an attempt to improve on the #f case by guaranteeing a unique value, but at its core it's still a similar hack. Recently, I have extended the `add-between' function in a way that ran against this problem at the interface level, where two keyword arguments default to such a gensymed value to detect when no argument is passed. Natually, this leaked into the documentation in the form of using `' to avoid specifying the default value and instead talking about what happens when no argument is given for the keywords in question. After a short discussion that I had with Matthew, the new version uses a new keyword that holds the unique no-value value, to simplify things: (define (foo x #:nothing [nothing (gensym)] [y nothing]) (printf y is ~s\n (if (eq? y nothing) 'omitted y))) The idea is that this does not depend on some specific unique value, since one can be given. For end-users of the function, there is no need to know about this. It's useful only for wrapper functions which want to mirror the same behavior, and call `foo' in a way that makes their own input passed to it, including not passing it when its own input is missing. In this case, you'd do something like this: (define (bar #:nothing [nothing (gensym)] [x nothing]) (foo 10 x #:nothing nothing)) This works, but I dislike this solution for several reasons: 1. Instead of finding a solution for the `gensym' problem, this approach embraces it as the proper way to do such things. 2. But more than that, it also exposes it in the interface of such functions, which means that simple end users need to read about it too. There is no easy way to somehow say you souldn't worry about this unless you're writing a function that ..., and if you look at the current docs for `add-between' you'd probably wonder when that #:nothing is useful. 3. There is also a half-story in this documentation -- even though the docs look like the above function definition, you obviously would want to define a single global gensymmed value and use it, to avoid redundant allocation. By the way the docs read, the above does look like the way to do these things, and I can see how a quick reading would make people believe that it's fine to write: (define (foo) (define (bar [x (gensym)]) ...) ... call bar many times ...) I considered a bunch of alternatives to this, and the one closest to looking reasonable is to use the #undefined value: it makes some sense because it is a value that is already used in some no value cases. However, it is probably a bad idea to use it for something different. In fact, that's how many languages end up with false, null, undefined, etc etc. (As a side note, a different approach would be to use a per-argument boolean flag that specifies if the corresponding argument. Since this started with a documentation point of view, I'm assuming that it won't be a good solution since it doesn't solve that problem -- a function that uses it similarly to `add-between' would still need to avoid specifying the default.) Instead, I suggest using a new special value, one that is used only for this purpose. The big difference from all of these special values is that I'm proposing a value that is used only for this. To discourage using it for other reasons, there would be no binding for it. Instead, there would be a fake one, say `no-argument', which is used only as a syntax in a default expression and only there the real no-argument gets used -- so the value is actually hidden and `no-argument' is a syntactic marker that is otherwise an error to use, like `else' and `='. (I'm no even suggesting making it a syntax parameter that has a value in default expressions, because you shouldn't be able to write (λ ([x (list no-argument)]) ...).) The only real binding that gets added is something that identifies that value, or even more convenient, something like `given?' that checks whether its input is *not* that value. To demonstrate how this looks like, assume that the kernel has only a three-argument `kernel-hash-ref', and you want to implement `hash-ref' on top of it without using a thunk (which avoid the problem in a different way). The so-far-idiomatic code could be as follows: (define none (gensym)) ; private binding (define (hash-ref t k [d none]) (cond [(not (eq? d none)) (kernel-hash-ref t k d)]
Re: [racket-dev] Proposal for a no-argument
If you're only going to use in keyword arguments (and optional arguments), you could make it an error to touch the value, unless it gets touched by a special predicate that checks for its existence. That is, in (define (f #:x [x]) ...) (where I'm saying that leaving off the default value means it gets this new, special behavior), you'd bind, at compile time, 'x' to something that expands to a code that signals error and (is-default? x) would look at its argument and be able to actually implement the predicate. In other words, I think you can devise a scheme where you don't actually have a value that leaks out at all. Robby On Sun, Jul 1, 2012 at 8:27 AM, Eli Barzilay e...@barzilay.org wrote: There rare cases where it is useful to have a value that means that no argument was passed to a function. In many of these cases there is a plain value that is used as that mark, with the most idiomatic one being #f, but sometimes others are used. IMO, while such uses of #f are idiomatic, they're a hack where an argument's domain is extended only to mark no argument. A more robust way to do that, which has become idiomatic in Racket is to use (gensym). (And as a sidenote, in other implementations there are various similar eq-based hacks.) IMO, this is an attempt to improve on the #f case by guaranteeing a unique value, but at its core it's still a similar hack. Recently, I have extended the `add-between' function in a way that ran against this problem at the interface level, where two keyword arguments default to such a gensymed value to detect when no argument is passed. Natually, this leaked into the documentation in the form of using `' to avoid specifying the default value and instead talking about what happens when no argument is given for the keywords in question. After a short discussion that I had with Matthew, the new version uses a new keyword that holds the unique no-value value, to simplify things: (define (foo x #:nothing [nothing (gensym)] [y nothing]) (printf y is ~s\n (if (eq? y nothing) 'omitted y))) The idea is that this does not depend on some specific unique value, since one can be given. For end-users of the function, there is no need to know about this. It's useful only for wrapper functions which want to mirror the same behavior, and call `foo' in a way that makes their own input passed to it, including not passing it when its own input is missing. In this case, you'd do something like this: (define (bar #:nothing [nothing (gensym)] [x nothing]) (foo 10 x #:nothing nothing)) This works, but I dislike this solution for several reasons: 1. Instead of finding a solution for the `gensym' problem, this approach embraces it as the proper way to do such things. 2. But more than that, it also exposes it in the interface of such functions, which means that simple end users need to read about it too. There is no easy way to somehow say you souldn't worry about this unless you're writing a function that ..., and if you look at the current docs for `add-between' you'd probably wonder when that #:nothing is useful. 3. There is also a half-story in this documentation -- even though the docs look like the above function definition, you obviously would want to define a single global gensymmed value and use it, to avoid redundant allocation. By the way the docs read, the above does look like the way to do these things, and I can see how a quick reading would make people believe that it's fine to write: (define (foo) (define (bar [x (gensym)]) ...) ... call bar many times ...) I considered a bunch of alternatives to this, and the one closest to looking reasonable is to use the #undefined value: it makes some sense because it is a value that is already used in some no value cases. However, it is probably a bad idea to use it for something different. In fact, that's how many languages end up with false, null, undefined, etc etc. (As a side note, a different approach would be to use a per-argument boolean flag that specifies if the corresponding argument. Since this started with a documentation point of view, I'm assuming that it won't be a good solution since it doesn't solve that problem -- a function that uses it similarly to `add-between' would still need to avoid specifying the default.) Instead, I suggest using a new special value, one that is used only for this purpose. The big difference from all of these special values is that I'm proposing a value that is used only for this. To discourage using it for other reasons, there would be no binding for it. Instead, there would be a fake one, say `no-argument', which is used only as a syntax in a default expression and only there the real no-argument gets used -- so the value is actually hidden and `no-argument' is a syntactic marker that is otherwise an error to use, like
Re: [racket-dev] Proposal for a no-argument
Just now, Robby Findler wrote: If you're only going to use in keyword arguments (and optional arguments), you could make it an error to touch the value, unless it gets touched by a special predicate that checks for its existence. That is, in (define (f #:x [x]) ...) (where I'm saying that leaving off the default value means it gets this new, special behavior), (Just to clarify, I mentioned this option for completeness, but I think that having a keyword will make things much simpler for macros etc.) you'd bind, at compile time, 'x' to something that expands to a code that signals error and (is-default? x) would look at its argument and be able to actually implement the predicate. In other words, I think you can devise a scheme where you don't actually have a value that leaks out at all. Yeah, something like that could be done -- but there is a case where you should be able to use `x' as a valid expression withouch checking, when you wrap a function. I should have added this to the examples to show that case too. Here's such an example for some `get-thing' function that uses the `get-hash' from the previous message. First, with the current idiom: (define none (gensym)) ; need my own none value (define (get-thing name [default none]) (if (eq? default none) (hash-ref things name) (hash-ref things name default))) Second, with the #:nothing thing this is a little easier: (define nothing (gensym)) ; still need my own (define (get-thing name #:nothing [nothing nothing] [default nothing]) (hash-ref things name default #:nothing nothing)) And using my proposal, it's much easier and there's no need for a new nothing value since there's a single one: (define (get-thing name [default no-argument]) (hash-ref things name default)) And that shows a use of `default' that would be valid even though it's not tested. -- ((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] Sublinear functions of superfloat numbers
How about more words and examples? Argument reduction is using function properties to reduce the magnitude of arguments to make computation more tractable or more accurate. I'll bet `log' uses this property: (log (sqrt x)) = (log (expt x 1/2)) = (* 1/2 (log x)) This form is nice for doing algebraic manipulations; not so much for computation. So multiply the outer sides by 2: (* 2 (log (sqrt x))) = (log x) You could define your own log function like this: (define (my-log x) (* 2 (log (sqrt x If `sqrt' could compute square roots of rational numbers larger than +max.0 (about 2^1024), then `my-log' could compute logs for those as well. But it can't. Here's a version of log that does reduces its argument with `integer-sqrt', which computes truncated square roots of bigints: (require racket/flonum (only-in unstable/flonum +max.0)) (define (real-log x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (fllog (real-double-flonum x))] [(x . . +max.0) (let loop ([x (exact-round x)]) (cond [(x . . +max.0) (* 2.0 (loop (integer-sqrt x)))] [else (fllog (real-double-flonum x))]))] [else +nan.0])) Computing (real-log #e1e800242) takes exactly the same amount of time as (log #e1e800242), and gives the same answer as well. (And I just discovered that that's how it's implemented in number.c.) Square root (for large real numbers) is much simpler. Floating-point numbers above 2^52 are all integers, so bigints above 2^1024 can be thought of as floating-point numbers with at least 1024 - 52 = 972 bits of precision. That means `integer-sqrt' will do the job perfectly, despite the fact that it always returns integers. (define (real-sqrt x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (flsqrt (real-double-flonum x))] [(x . . +max.0) (real-double-flonum (integer-sqrt (exact-round x)))] [else +nan.0])) But sine is much harder because it's periodic with an irrational period. It would look something like this, but with a rational approximation of pi whose precision depends on the magnitude of the argument: (define (real-sin x) (cond ... [(x . . +max.0) (let ([x (- x (truncate (/ x (* 2 pi]) (flsin (real-double-flonum x)))] ...)) On 07/01/2012 04:04 PM, Robby Findler wrote: 3. Can you explain the issue again, using smaller words? (I think I understand the first example, but then I'm lost.) Robby On Sun, Jul 1, 2012 at 5:02 PM, Matthias Felleisen matth...@ccs.neu.edu wrote: 1. What's the computational cost of such changes? The additional cost when applying `sqrt' and `sin' to numbers in typical ranges would be small: the cost of wrapping a kernel function and checking the size of arguments. 2. What is the impact on TR? None that I can tell. But TR would remove the additional cost when it could prove the arguments to `sqrt' and `sin' are Float. I think I've been trying to come up with a general rule for when argument reduction is necessary. But I can't, because there isn't one. For example, this is infinite: (log (make-rectangular #e1e400 1)) even though the actual answer is representable as a Float-Complex. Apparently, argument reduction only happens to reals, and only in a few functions. (But I'm glad it does, because the plot library uses `log' to format huge numbers.) Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Sublinear functions of superfloat numbers
I had misunderstood. I thought you had suggested 'reduction of strength' (say going from square to * or double to +), which is a generally useful compiler optimization. What you suggest is some form of conditional version of this. How many do you see? On Jul 1, 2012, at 8:00 PM, Neil Toronto wrote: How about more words and examples? Argument reduction is using function properties to reduce the magnitude of arguments to make computation more tractable or more accurate. I'll bet `log' uses this property: (log (sqrt x)) = (log (expt x 1/2)) = (* 1/2 (log x)) This form is nice for doing algebraic manipulations; not so much for computation. So multiply the outer sides by 2: (* 2 (log (sqrt x))) = (log x) You could define your own log function like this: (define (my-log x) (* 2 (log (sqrt x If `sqrt' could compute square roots of rational numbers larger than +max.0 (about 2^1024), then `my-log' could compute logs for those as well. But it can't. Here's a version of log that does reduces its argument with `integer-sqrt', which computes truncated square roots of bigints: (require racket/flonum (only-in unstable/flonum +max.0)) (define (real-log x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (fllog (real-double-flonum x))] [(x . . +max.0) (let loop ([x (exact-round x)]) (cond [(x . . +max.0) (* 2.0 (loop (integer-sqrt x)))] [else (fllog (real-double-flonum x))]))] [else +nan.0])) Computing (real-log #e1e800242) takes exactly the same amount of time as (log #e1e800242), and gives the same answer as well. (And I just discovered that that's how it's implemented in number.c.) Square root (for large real numbers) is much simpler. Floating-point numbers above 2^52 are all integers, so bigints above 2^1024 can be thought of as floating-point numbers with at least 1024 - 52 = 972 bits of precision. That means `integer-sqrt' will do the job perfectly, despite the fact that it always returns integers. (define (real-sqrt x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (flsqrt (real-double-flonum x))] [(x . . +max.0) (real-double-flonum (integer-sqrt (exact-round x)))] [else +nan.0])) But sine is much harder because it's periodic with an irrational period. It would look something like this, but with a rational approximation of pi whose precision depends on the magnitude of the argument: (define (real-sin x) (cond ... [(x . . +max.0) (let ([x (- x (truncate (/ x (* 2 pi]) (flsin (real-double-flonum x)))] ...)) On 07/01/2012 04:04 PM, Robby Findler wrote: 3. Can you explain the issue again, using smaller words? (I think I understand the first example, but then I'm lost.) Robby On Sun, Jul 1, 2012 at 5:02 PM, Matthias Felleisen matth...@ccs.neu.edu wrote: 1. What's the computational cost of such changes? The additional cost when applying `sqrt' and `sin' to numbers in typical ranges would be small: the cost of wrapping a kernel function and checking the size of arguments. 2. What is the impact on TR? None that I can tell. But TR would remove the additional cost when it could prove the arguments to `sqrt' and `sin' are Float. I think I've been trying to come up with a general rule for when argument reduction is necessary. But I can't, because there isn't one. For example, this is infinite: (log (make-rectangular #e1e400 1)) even though the actual answer is representable as a Float-Complex. Apparently, argument reduction only happens to reals, and only in a few functions. (But I'm glad it does, because the plot library uses `log' to format huge numbers.) Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Sublinear functions of superfloat numbers
Oh, that helps a lot, thanks. Is it not the problem that this: (sqrt (expt 10 402)) has no Racket number that could represent it? It is too big for a float (I think?), it isn't a rational, there isn't anything else...? No? Robby On Sun, Jul 1, 2012 at 7:00 PM, Neil Toronto neil.toro...@gmail.com wrote: How about more words and examples? Argument reduction is using function properties to reduce the magnitude of arguments to make computation more tractable or more accurate. I'll bet `log' uses this property: (log (sqrt x)) = (log (expt x 1/2)) = (* 1/2 (log x)) This form is nice for doing algebraic manipulations; not so much for computation. So multiply the outer sides by 2: (* 2 (log (sqrt x))) = (log x) You could define your own log function like this: (define (my-log x) (* 2 (log (sqrt x If `sqrt' could compute square roots of rational numbers larger than +max.0 (about 2^1024), then `my-log' could compute logs for those as well. But it can't. Here's a version of log that does reduces its argument with `integer-sqrt', which computes truncated square roots of bigints: (require racket/flonum (only-in unstable/flonum +max.0)) (define (real-log x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (fllog (real-double-flonum x))] [(x . . +max.0) (let loop ([x (exact-round x)]) (cond [(x . . +max.0) (* 2.0 (loop (integer-sqrt x)))] [else (fllog (real-double-flonum x))]))] [else +nan.0])) Computing (real-log #e1e800242) takes exactly the same amount of time as (log #e1e800242), and gives the same answer as well. (And I just discovered that that's how it's implemented in number.c.) Square root (for large real numbers) is much simpler. Floating-point numbers above 2^52 are all integers, so bigints above 2^1024 can be thought of as floating-point numbers with at least 1024 - 52 = 972 bits of precision. That means `integer-sqrt' will do the job perfectly, despite the fact that it always returns integers. (define (real-sqrt x) (cond [(x . = . +inf.0) +inf.0] [(x . = . +max.0) (flsqrt (real-double-flonum x))] [(x . . +max.0) (real-double-flonum (integer-sqrt (exact-round x)))] [else +nan.0])) But sine is much harder because it's periodic with an irrational period. It would look something like this, but with a rational approximation of pi whose precision depends on the magnitude of the argument: (define (real-sin x) (cond ... [(x . . +max.0) (let ([x (- x (truncate (/ x (* 2 pi]) (flsin (real-double-flonum x)))] ...)) On 07/01/2012 04:04 PM, Robby Findler wrote: 3. Can you explain the issue again, using smaller words? (I think I understand the first example, but then I'm lost.) Robby On Sun, Jul 1, 2012 at 5:02 PM, Matthias Felleisen matth...@ccs.neu.edu wrote: 1. What's the computational cost of such changes? The additional cost when applying `sqrt' and `sin' to numbers in typical ranges would be small: the cost of wrapping a kernel function and checking the size of arguments. 2. What is the impact on TR? None that I can tell. But TR would remove the additional cost when it could prove the arguments to `sqrt' and `sin' are Float. I think I've been trying to come up with a general rule for when argument reduction is necessary. But I can't, because there isn't one. For example, this is infinite: (log (make-rectangular #e1e400 1)) even though the actual answer is representable as a Float-Complex. Apparently, argument reduction only happens to reals, and only in a few functions. (But I'm glad it does, because the plot library uses `log' to format huge numbers.) Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
