search

part-cw / lambdanative

LambdaNative is a cross-platform development environment written in Scheme, supporting Android, iOS, BlackBerry 10, OS X, Linux, Windows, OpenBSD, NetBSD, FreeBSD and OpenWrt.
http://www.lambdanative.org
Other
1.39k stars 86 forks source link

Consider a documented update policy #406

Closed 0-8-15 closed 3 years ago

0-8-15 commented 3 years ago

Well, the trust statement was, and is, my personal opinion.

I know your safety attitude, which I'd summarize as "never touch a running system". And I welcome it on those grounds.

Nevertheless I'd still like to strongly suggest to deprecate the predicate and eventually remove it after having gone to the trouble to check every single use case and fix it.

The issue is not (not (null? x)) vs. (pair? x). While I'd still change in former into the latter for saving one nesting level, the gain (as in runtime) would likely be nothing at all the microseconds. The other issues are all worse:

  1. When list-notemtpy? is equivalent to pair? then the compiler will inline the pair? (at least in LN production mode), the predicate becomes a call to a top level binding, no matter what.
  2. Calling an actual procedure is always costlier than inline code, let alone that calling a procedure from another module is like much worse than one defined in the same module, possibly even with local scope.
  3. Offering this predicate invites usage, which in turn disables optimizations even in those other modules, where the predicate is used, but since it is not inlineble, results in an inter-module call. The worst we can have.
  4. Asking the question "who would use it", and knowing 1..3 already, I'd say: those who don't.
  5. "Why would one use it?", given (4), I'd assume it likely being used by users having read (= (length lst) 0) as a loop-aborting condition. They might not look at the code while taking computational complexity in mind. And IMHO list-notempty? looks even more innocent than the former, where length clearly indicates that the operation is O(n) with being the length of lst.
  6. When a predicate of class O(n) is used in a loop, the resulting operation is O(n*m) -- already exponential. This works for a while while there are only very small numbers of elements in each dimension. (That's where my mistrust origins.)
  7. If it was not for (1) than 96a92581 mentions O(n) as in (5). So why? The list? predicate is like length, O(n).
  8. simply removing the (list? lst) from line 41 changes the semantics.

My conclusion: the predicate is broken beyond repair and was better removed. Even when this means fixing all the app.

NB: I've been bitten by complexity issues before. :-/

Originally posted by @0-8-15 in https://github.com/part-cw/lambdanative/issues/405#issuecomment-741920871

0-8-15 commented 3 years ago

Nah, don't include the full comment.