So a useful formula for counting digits is, a positive integer x has floor(log10(x)) + 1 digits. You can figure this out yourself by thinking, where does the digit-counting function bump up a notch? At 10, 100, 1000, etc. So asymptotically the number of digits in x is O(log x).

So n! has O(log n!) digits. The trickier part is figuring out or knowing that O(n log n) = O(log n!). Using log ab = log a + log b you can expand out the factorial:

  O(log n!) = O(log (n * (n-1) * ... * n * 1))
            = O(log n + log (n-1) + ... + log 2 + log 1)
            = O(n log n)

  log n + log (n-1) + ... + log 2 + log 1 < n log n

  log n + log (n-1) + ... + log 2 + log 2 > log n + log (n-1) + ... + log (n/2)
                                          > (n/2) log (n/2)

In general the rules of thumb you use to reduce O(log n!) are:

  1. complicated expressions inside factorials are ugly, you should simplify them
  2. O(sum of n things) is usually O(n * the biggest thing)

You can improve this by using the recursive formula for Pascal's triangle rather than the closed form. Specifically, n choose k equals (n-1) choose (k-1) + (n-1) choose k. Memoize and you can do (pascal-triangle n) in O(n^2), optimal since that's the amount of prints you have to do.

There is also probably an quicker formula for n choose k mod 2, if you don't have to print the entire triangle. Perhaps try using Legendre's formula for the largest power of a prime that divides a factorial.

see: http://mathworld.wolfram.com/Factorial.html

  def f(n, k):
    if n and k are both 0:
      return 1
    if n is even and k is odd:
      return 0
    return f(floor(n/2), floor(k/2))

  (def f (n k)
    (if
      (is n k 0)
        1
      (and (even n) (odd k))
        0
      ; else
        (f (round:/ n 2) (round:/ k 2)))) ; works if n and k are ints

  arc> (round 4.5)
  4
  arc> (round 5.5)
  6
  arc> (trunc 4.5)
  4
  arc> (trunc 5.5)
  5

from: http://en.wikipedia.org/wiki/Rounding

  Although it is customary to round the number 4.5 up to 5, 
  in fact 4.5 is no nearer to 5 than it is to 4 (it is 0.5 
  away from both). When dealing with large sets of 
  scientific or statistical data, where trends are 
  important, traditional rounding on average biases the data
  upwards slightly. Over a large set of data, or when many 
  subsequent rounding operations are performed as in digital
  signal processing, the round-to-even rule tends to reduce 
  the total rounding error, with (on average) an equal 
  portion of numbers rounding up as rounding down. This 
  generally reduces upwards skewing of the result.

Actually, how did you manage to key on thread? I couldn't figure out how to do this myself, since there isn't a "thread id" or anything that would work as a key...

"The hash-table-put! procedure is not atomic, but the table is protected by a lock."

As far as threadlocal goes... new-thread returns the thread descriptor and you can use that directly as a hash key.

  arc> (= a (table))
  #hash()
  arc> (= (a (new-thread (fn () (sleep 10)))) 5)
  5
  arc> a
  #hash((#<thread> . 5))

in python:

  >>> a = 3
  >>> a
  3
  >>> del a
  >>> a
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  NameError: name 'a' is not defined

  (w/temps
    (def foo (x) (+ x y))
    (tempset y 10)
    (foo 5))

  (w/temps x y
    (def foo (x) (+ x y))
    (tempset y 10)
    (foo 5))

  (with (y nil foo nil)
    (= foo (fn (x) (+ x y)))
    (= y 10)
    (foo 5))

  (mac make-things-difficult (c v)
    (if (some-property v)
      `(tempset ,c ,v)
      `(if (another-property ,v)
          (tempset ,c ,v)
          (= ,c ,v))))

http://arclanguage.org/item?id=4481

My implementation (lib/settable-fn.arc) is first described here: http://arclanguage.org/item?id=3595

nex-3's alternative (lib/settable-fn2.arc) is similar to absz's suggestion here: http://arclanguage.org/item?id=3723

The problem, I suppose, is the rather inconsistent formalization/nonformalization of type classes/interfaces/hindley-milner typesystem. In Ruby it's informal - you just say this or that object has this or that function which will just work, in the expected manner. In Haskell and Java it's formal - you say this type provides this type class or presents this interface, and must therefore have this or that function which must work, in the expected manner.

Using formal interfaces, both the people writing the polymorphic code and the people writing the polymorphic objects have to explicitly code polymorphically. Using informal interfaces, only the people writing polymorphic objects have to be explicit. The other people can* be aware of the polymorphism, which allows powerful stuff like Ruby's Enumerable module, but as long as the objects behave correctly ("quack like a duck"), you can use pass them to code that doesn't expect them at all and they'll still work.

There are still some parts that are stumping me. It seems like I need to either (a) mock annotate to use a different mechanism, or (b) prevent the code from annotating pre-existing variables. The same goes for accessing sig.

It seems like the most plausible way to keep scar/scdr/sref from mutating variables outside the no-side-effects scope is to keep a table of the variables they are allowed to operate on, which is basically anything the user created with cons or table inside the no-side-effects scope. This should invalidate code like

(= a (table))

(no-side-effects (= b a) (= (b "key") "value"))

Assuming

  (= a (table 'foo 'bar))

  (no-side-effects (= a!foo 'baz) a)

  (let a (copy a)
    (= a!foo 'baz)
    a)

You would still have to think about constructs like def and mac, but at least this deals with shared structure of lists and tables.

I don't know a priori what variables this code will try to access. I could possibly figure that out with a macro, but some of the details are still unclear to me. I also don't want side effects if annotate, def, mac, or anything like that was run from the no-side-effect'd code.

At any rate, I think just wrapping in a let is insufficient, even if you do know all the variable names. E.g. you can break out of the sandbox with scdr:

> (= a '(1 2))

(1 2)

> (let a a (scdr a '(3)))

(3)

> a