libera/#commonlisp - IRC Chatlog
Search
1:42:29
ludston
beach: I like your "reverse-order" paper. It's using recursion in an interesting way. I am thinking this approach might have trouble though for O(n^2) algorithms. e.g. "(reduce (lambda (x y) (+ x y (reduce '+ some-large-list :from-end t))) some-large-list :from-end t)" as once the remaining stack space is small, nthcdr could be called a very large
1:46:28
ludston
This seems like a solvable problem except for in cases where you don't know the number of times that reduce will be recursively invoked.
1:50:24
ludston
My example of an O(n^2) algorithm is contrived, but yes there are algorithms where O(n^2) is optimal. Algorithms like O(n^m) are pretty rare though, given the run-time tends to become infinite when you have more than 10 elements.
3:06:20
beach
I don't have the paper fresh in memory, but as I recall, each invocation takes a logarithmic amount of stack space. It would appear to me then, that a quadratic algorithms would take logĀ² space.
3:34:09
beach
I added two more papers to http://metamodular.com/SICL today, namely "A modern implementation of the LOOP macro", and "Removing redundant tests by replicating control paths."
13:33:43
pjb
It' strange that compiler-macro-function takes an environment parameter, but it can only be NIL for (setf compiler-macro-function).
13:38:07
Bike
compiler-macro-function needs it because compiler macros can be shadowed by local functions
13:38:22
Bike
but also, typep and subtypep and find-class take environment parameters, and there's no concept of local types
13:39:44
beach
Can those just be different global environments, like the ones mentioned for file compilation?