freenode/#sicl - IRC Chatlog
Search
10:47:55
beach
Finished moving component for enabling ALLOCATE-INSTANCE from phase 2 to phase 3. It required moving some prerequisites as well, of course.
10:48:55
beach
In about an hour or so, my favorite coauthor will come over for lunch and I will be busy for a few hours. I did get to a point where the part of phase 4 that is enabled at the moment works.
11:00:27
splittist
Am I the only one that finds it slightly confusing - or, at least, finds it takes a tiny bit more mental energy - that both Phases and Environments are numbered 1 to 4, but the relationship between them is not a straightforward mapping? I'm wondering if it would be less confusing (for me - and perhaps I am unique in this respect, too) if the Phases were A - D (or alpha - delta, or ...).
14:09:03
beach
It is probably better to rename the environments. The phases are strictly ordered and sequential. The environments are messier. Several environments are involved in each phase.
14:09:23
beach
In fact, the environments don't even have to have names that suggest any ordering at all.
14:54:35
jcowan
beach: I was reading sicl.pdf and got to the sorting chapter. There is AFAIK no stable n log n vector sort that runs in constant space, though I know of no proof that there cannot be one.
14:57:49
jcowan
I don't know if I mentioned Shivers's destructive list merge sort to you, though; it does run in constant space (in fact, it never conses)
14:58:12
jcowan
https://github.com/scheme-requests-for-implementation/srfi-32/blob/master/sort-ref-impl/lmsort.scm (in Scheme, but translation to CL should be trivial)
15:48:01
beach
That is one of the SICL projects I would like to subcontract, in fact. I would like to see an intermediate between an ordinary merge sort and one of the O(1) space algorithms suggested. One could use the stack as additional space if there is enough stack space. Certainly, for the base case of only a few dozen elements.
15:51:35
jcowan
Most list sorts are list->vector, vector sort, vector->list, which is disturbingly non-optimal
15:56:49
beach
shka_: I am, but I am only collecting documentation at the moment. I have no time to even think about sorting right now.
16:00:30
shka_
https://ac.els-cdn.com/S1877050910005478/1-s2.0-S1877050910005478-main.pdf?_tid=4398908f-dfbf-4465-b074-8a0320bfa7dd&acdnat=1542211323_ed2db6f6133a7976bb324bcdedff783e
16:02:54
jcowan
https://www.sciencedirect.com/science/article/pii/S1877050910005478 is a more canonical URL
16:03:29
beach
shka_: Looks interesting. I would want the taker of the challenge to implement several algorithms and compare them, of course. And perhaps even combine them in interesting ways, depending on the situation.