[OEIS] Python-development. Was: Request for more Python programs

[Antti Karttunen]

Jaap Spies wrote:

 > N. J. A. Sloane wrote:
 >
 >> Dear Seqfans,  There are very few Python programs in the OEIS.
 >> I would like to get more - even for the simplest sequences,
 >> and especially for all the important sequences, whenever appropriate.
 >>
 >> I would prefer readable programs (rather than the opaque one-line
 >> Mma programs that the OEIS is full of).  For one thing, that
 >> will enable people to learn Python.
 >>
 >
 > And or SAGE! As SAGE _is_ Python in a way, all Python programs run in 
SAGE.
 > So :g/Python/s//SAGE/g
 >
 > Agreed Python/SAGE is far more readable compared to Mathematica 
(don't flame!).
 >
 > As I wrote before about SAGE, we are in the proces of making 
available the OEIS
 > within SAGE. The database of sequences is already there, but in
 > sage-1.6 or sage-2.0 there will be a growing number of functions
 > to produce sequences:
 > A111776(n) will give the n-th number and
 > A111776_list(n) wil give the list of the first n numbers of ...
 >
 > So in the long run we may see a line
 > %o A111776 (SAGE) sloane.A111776(n)

 > See http://www.research.att.com/~njas/sequences/A111776
 >

This is very interesting development! Especially since I have been 
daydreaming
about creating a similar library for Scheme.

Just a few question come to my mind. In the original examples
given by Neil, namely:
http://www.research.att.com/~njas/sequences/A071531
http://www.research.att.com/~njas/sequences/A001047
http://www.research.att.com/~njas/sequences/A005150
http://www.research.att.com/~njas/sequences/A048927
and
http://www.research.att.com/~njas/sequences/A086638

there occurs almost every possible way to dispatch the
result. E.g. returning it as a result of function (with return),
constructing a list (with seq.append), just printing it out
and finally, yield:ing it from generator.

Eppstein gives more examples of the latter way:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/221457
which is a very elegant way for certain kind
of self-generated sequences.

But when constructing a library, there should be standard
way to deliver results. I have noticed by myself that
defining ALL the OEIS-sequences as N -> Z functions has
many merits, even if the sequence itself would be more
of "list of integers that match a certain criteria" variety,
like primes are. Moreover, if the programming language
has an ability to define "cached" or "memoized" functions
(like with "option remember" in Maple) then one can
use simple, elegant recursive definitions without
actually incurring much overhead, compared to
iterative approach.

In my OEIS-related Scheme-programs I use the macro definec,
whose use is totally transparent to the user, i.e. instead of saying
(define (A000045 n) (if (< n 2) n (+ (A000045 (- n 1)) (A000045 (- n 2)))))
one just says
(definec (A000045 n) (if (< n 2) n (+ (A000045 (- n 1)) (A000045 (- n 2)))))

which creates a function closure with its own "cache", a vector, which
stores all the values so far asked, and is automatically
grown when A000045(i) is called with the first i >= the current size
of the cache. At some point there's a memory limit, where
the cache cannot grow anymore, and then the function reverts
to the old-fashioned non-cached mode. (Possibly with dramatically longer
execution times, depending on the function to be defined.)
However, when submitting new sequences, and only a hundred or
few hundred terms are needed for OEIS, this is usually not a problem,
there is enough memory for Scheme runtime system.
(I usually have (define *MAX-CACHE-SIZE-FOR-DEFINEC* 290512) in my code.)


Not only have I this macro, I have also higher-order functions like

fun-succ-matching-is1
fun-succ-distincts0
fun-succ-recpositions1

etc. which, in the first case is given N -> boolean, and in the rest
are given a N -> Z function as argument (preferably a cached implementation
defined with definec, or otherwise of modest running time) and these
then return new cached N -> N functions, where

  (fun-succ-matching-is1 predicate?)

defines a function which returns the successive positions
(starting from i=1) where (predicate? i) is true
(one can think it as a characteristic function
of the sequence whose function fun-succ-matching-is1
defines).


  (fun-succ-distincts0 fun)

defines a function which returns the successive positions
(starting from i=0) where (fun i) gets new values distinct
from all of its previous values,

and

  (fun-succ-recpositions1 fun)

similarly defines a function which returns the successive
positions (starting from i=1) where (fun i) gets values
larger than any of the previous values.


With more higher-order, function-defining functions like these,
it will be possible to avoid most of the tedious and error-prone
programming involved with explicit loops.
Compare also to the approach in
http://www.research.att.com/~njas/sequences/transforms.txt
(although these work more with power series and lists,
but on the abstract level the idea is same.
Consider e.g. the RECORDS transform.)

Now, I'm just a beginner myself with Python,
and don't know whether it for example allows
defining of the cached/memoized recursive functions,
where the function to be defined can itself
access (transparently!) its own cache.
But what I have read for example from

http://myhdl.jandecaluwe.com/doku.php/meps:mep-100

about the "decorators", it seems promising.
And also, if one could include both the ordinary
returning functions and yielding generators
under the same framework (the former under
the latter?), it might be very good for
the self-describing sequences, of which
there are many in OEIS.


In any case, I am interested to hear more news about your project!

Yours,

Antti



 > A few more examples: http://www.jaapspies.nl/oeis/
 >
 >> Since leading spaces and newlines have a special meaning in Python,
 >> we are using the style illustrated below:
 >>
 >
 > As an alternative: place a link to an external location. This is 
certainly
 > more attractive for larger programs.
 >
 >
 > Best wishes,
 >
 > Jaap
 >
 >
 >