re: "n could have been changed by a function call inside the optimized function". This normally can't happen on a function call. This can only happen in the following cases:

1) n is a global variable, in which case you can't safely optimize on it anyway

2) n is enclosed both by this function and the function it calls - e.g. if the function it calls is a subfunction that can see this local variable - and the function it calls does 'set on that variable.

3) if the function itself does 'set on that variable.

Otherwise, 'n cannot possibly change (i.e. purely functional programming)

Note also that you simply need to create a really big data structure to handle each part of the program.

Say you have the following canonical definition:

  (def fib (n)
    (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(of course, infinite sets can be modelled using lazy eval.)

Now let's also consider the "+ could have been modified". In most cases this happens only if someone has a new type. Otherwise, any modification of '+ which doesn't involve someone defining a new type is probably someone screwing your system, in which case we assume that it's screwed anyway so you might as well ignore that possibility (and consider how to stop someone screwing your system in the first place).

But if the modification of + is itself based on having a new type, then we should also include '+ itself in the optimizing type system. So now '+ itself represents an infinite set of functions, based on (type n). Adding a definition for '+ based on type must thus extend the lazy set of '+ functions.

Thus at compilation, we only have to detect what gets called at top-level (that is, the repl). We can trivially determine the types of the arguments at top-level (just do 'type on each of them!).

Now any variables defined in the called function will be either the arguments themselves or will be other local variables, based on computations. Those computations will simply be a call to another function, based on the arguments (and globals).

For the functions called within other functions, we simply analyze them downwards and determine: if a function is given type a, what is the output type? Then we can determine the type of local variables.

We can determine the output type of the called functions by simply recursively determining what the possible outputs are. The output of the function is always the result of the last expression in the function and we can then determine the type from there. If the last expression is some sort of conditional, then it could be the output of the types from any of them.

Then we eventually reach one of a set of basic functions. These basic functions would have defined exactly what type it returns, based on its inputs. For example '+ would be applied to a list of stuff, [a], and return a type of a. (obviously such basic functions can also be defined by the user - all you have to do is support some sort of a -> a syntax, like in Haskell). Basically, '+ promises that if given a list of objects of type a, it will return an object of type a, or die trying (i.e. raise an exception).

Then we can select which '+ to use, based on the actual type we've determined.

So the flow on your 'fib function would be:

1) 'fib receives an object of type a. If it's received an object of this type before, it will use the function created for that type.

2) otherwise, the analyzer goes through the 'fib code, looking for locals and temporaries (i.e. return values of functions, which will be temporarily placed in a stack-like location) and determining their types.

3) the analyzer reaches (if ...) and enters into each expression in it

4) it sees (< n 2) and determines that < is a (a,b) -> t/nil basic function. It then knows that the 'if it has to use just has to handle t and nil, and doesn't have to handle random objects (could be useful nfo, who knows? maybe some computer hardware somewhere can branch based on that faster than normal)

5) since the last expression in 'fib is an 'if form, it knows that 'fib itself returns several possible types. The first type is (type n) itself.

6) The other type is the type returned on '+. It knows that the type returned by '+ is the same type as all its inputs.

7) The type input into '+ is the type of 'fib. Since we're analyzing 'fib itself, we use a separate type, b.

8) The input into 'fib is the output of '-, which is also a basic function whose type is the same as its inputs. Since the inputs are of (type n), we know that the input to 'fib is therefore (type n).

Currently, I'm working on a naïve approach : it supposes native numerical functions (only numerics as for now) are not redefined, or, at least, that they are redefined in a conservative way (that is, as you mention it, e.g. + was redefined to be able to add apple, a user type, but still works the regular way with numbers), and it knows that, if a numerical operation is called only with numbers :

- it can use its inlined version,

- the result will be a number too, so nested numerical operations can be taken into account too.

For example, when we call (fib 30), the compiler knows the n arg and literal numbers are numbers, so (- n 1) and (- n 2) and (< n 2) are numbers too and this gets translated into (n- n 1), (n- n2) and (n< n 2). However, it cannot know (yet) (fib (n- n 1)) is a number, so the final sum cannot rely on the inlined + :

  (gen-ad-hoc (listtab '((n int))) '(fn (n)
    (if (< n 2)
      n
      (+ (fib (- n 1) (fib (- n 2)))))))

  -> (fn (n) (if (n< n 2) n (+ ((fib (n- n 1) (fib (n- n 2)))))))

nfib is faster than fib because it's compiled with the knowledge that its argument is an integer. But you could make it even faster if you knew that its argument was an integer that fit into a machine word. (That might not be what you want to do with nfib, but I imagine a lot of numerical functions are going to be used almost always with numbers that fit in machine words.)

My thought is that you should be able to specialize functions for arbitrary predicates. For instance,

  (def fib (n)  ; yeah, it's a bad definition
    (specialize (and (number? n) (< n  (exp 2 32)) (> n 0)))
    (if (< n 2)
        n
        (* n (fib (- n 1)))))

  (specialize (fib n) (and (number? n) (> n 0) (< n (exp 2 32))))

  (specialize [map f _]).

  (= fmapper (specialize [map f _]))

Now, every time the function is called, it :

- determines the types of all args

-checks whether this list of types is a key in the table

- if it is, the associated function is called with the current args

- if not, a new function is generated based on the given types. In the fib example, since the type of n is an int, we try to optimize the code. This way, (- n 1) is rewritten (n- n 1), etc.

Actually, the code that was given when calling the adef macro is never really called : it is just a skeleton to generate code adapted to the given types (if possible).

The algorithm is currently very naïve, as it is only able to know the return type of functions if it was manually declared (i.e., as for now, mathematical operators). In the fib example, it does not know the result of (fib (- n 1)), so we can't optimize the '+ operator there. almkglor's suggestions are the way to do I guess, but I already had hard time fighting with these macros, so we'll do type inference later ;)

And, well, there is another little problem. The lookup in the hash table takes a very long time. Most of the time is spent looking for the actual function to be called, thus slowing down the whole process... :( Maybe I should rewrite it using redef instead, or maybe I should write all of this directly in mzscheme (as what we are after is generated the best mzscheme code possible).

  (mac adef (name parms . body)
     (w/uniq (htypes tparms types)
        `(let ,htypes (table)
           (def ,name ,parms
              (withs
                 (,tparms (mergel ',parms (map type (list ,@parms)))
                  ,types (map cadr ,tparms))
                 (aif (,htypes ,types)
                    (apply it (list ,@parms))
                    (apply (= (,htypes ,types) (gen-fn ,parms ,tparms ,@body)) (list ,@parms))))))))

(promise 'no-redef)

- compiling Arc code is better done on the compiler side rather than on the arc side

- that way, I can get rid of n+ et al., as they never really get called in Arc code

- manipulating what is generated by the 'ac function is easier than manipulating raw Arc code : 'ac does macro-expansions and translates ssyntax in Scheme syntax.

In practice, until now, I added a function, inside 'ac, wrapping the result of the latter. This function explores and modifies the code generated by 'ac. Every time it sees a 'lambda, it takes its args and body and generates an actual lambda that looks like the arc code I wrote there : http://arclanguage.org/item?id=5216 .

So, 2 hash tables are generated for each lambda. Well, as you can guess, the code is eating as much memory as you can imagine, particularily if you arco the code in arc.arc (which should be done anyway, should it only be to accelerate loops). Now, I'm quite sure the solution based on hash tables is a dead end.

Maybe I should do otherwise : instead of using hash tables, I could make the function's code grow everytime a new type is applied on it :

  (if (type-is-the-new-type)
    (call new-generated-code-for-this-type)
    (call the-previously-generated-code))

It looks like a very interesting idea, and would certainly be very valuable if we can actually get it to work. But some of the issues you mention do look difficult.

Does Psyco itself have any documentation that discusses their implementation? It might be useful for finding ways around the difficulties in writing an "arco".

Edit : yes, I think that would be a good idea !

Btw, yes, these are really hard problems I think. It won't be done in a few hours. However, in our case, we already have mzscheme doing a good part of the work (it could be interesting to get even closer to the bare metal, though, but that could be done later). Psyco, on the other hand, compiles down to assembly code.