24 March 2011

More on List combiners in Klink

Klink list combiners 2

Since the last post, I've implemented a sort of general listloop facility in Klink. It consists of:

  • Two new T_ types
  • A number of predefined styles (Two for now, easily expanded)
  • A C function to create a listloop
  • A C function to iterate a listloop

What it accomplishes

  • It takes the place of a number of specialized loop facilities.
  • It potentially can turn most map-like operations into streaming operations by changing just a few parameters. I haven't written that part yet, because promises are implemented but are not yet available in the C part of Klink.
  • It can potentially build somewhat more powerful list loop functionality almost directly in C, again by just passing parameters. For instance, assoc, find, and position.
  • It appears possible to reason about it in a fairly general way, for optimization purposes.

Dimensions of loop behavior

Last time, I spoke of two dimensions of looping: Family and Argument Arrangement. And a mea culpa: I was wrong to group $sequence with for-each. They are similar but $sequence returns its final value unless the list is circular, `for-each' never does.

On further analysis, I ended up with more dimensions than that. I considered 9 dimensions of loop behavior, and ended up with 6 style parameters and 6 loop instantiation parameters, plus 2 parameters that are always supplied outside.

The dimensions of loop behavior are not independent. There are a few combinations that make no sense.

The dimensions themselves

From my design notes:

  • Termination control
    • Cases:
      • When countdown is zero
      • When arglist is empty
      • When value is #t/is #f
        • But for this case we also need an empty or countdown condition.
        • Could be generalized to any eq? test, possibly useful for find.
      • (Unlikely to need a case for when arglist is empty except for N elements, since neighbors is figured out by count first)
  • The effective operative return value
    • Cases:
      • Map: Cons of value and accumulator
        • Final value is reverse accumulator
      • Boolean/reduce/sequence: Value itself
        • Final value is value
      • Each: No return value
  • Terminator:
    • Cases:
      • Usually none
      • Map: Reverse the value
        • That's just reverse
      • For-each: Give #inert
        • Just curry the K_INERT value
    • All can be done without reference to the loop object itself
  • Treatment of the arglist(s). Cases:
    • Use a single element (car, cdr remains)
    • Use elements from multiple lists (car across, cdr across remains)
    • Use multiple consecutive elements ((car, cadr), cdr remains)
  • Other arguments to the operative
    • Pass the accumulator too (reduce does this)
      • This is really passing the previous value, which is sometimes an accumulator.
    • Pass the index too
    • Pass the "countdown" index too.
    • Make the value the first arg in a list
      • For $sequence, mapeval, etc. Basically those that use a single element.
  • The operative
    • Cases:
      • Freeform (The fully general case)
      • None, value is directly used (Basically for booleans)
        • Could be 0 and be skipped, but early let's use `identity'
      • Eval the arg (Just suitable for 1-list)
        • Could be special, but early let's just use eval.
      • No-K
        • Means we can loop in C.
    • This is just which operative to use, maybe with specializations.
  • The initial value
    • Cases:
      • For reduce this sometimes has to be flexible. Otherwise no.
      • Bools: #t, #f
      • Map: ()
    • Since it passes thru the setup, maybe it could be outside if the setup makes a combiner rather than schedules anything.
  • Checking value's type, error if it's not as expected. This is really a debugging move, but is important in its place.
  • Making a stream or not.

The parameters

Style parameters

combiner
Default combiner used in each iteration. It can be NULL for no default.
collect_p
A boolean whether to collect a list of result values. This actually makes a reversed list, and callers generally pass the result to `reverse'.
step
How to get successive values from the list being processed. There's no attempt to deal with circulatiry here. Possibilities:
1-list
The list consists of many unary arguments
many
The list consists of lists, whose heads collectively form a single n-ary argument. Ie, what `map' sees.
neighbors
The list again consists of many unary arguments, but we pass the current head and the cadr. Ie, we use successive pairs of list neighbors.
many-streams
(Not implemented yet) Like many, but the top elements may be streams instead of lists. This will terminate when any element runs out.
mk_val
A C function how to make the value that we pass to the combiner. Can be NULL, meaning to just use the result of the "step" phase. This is needed for `reduce', so that we can pass the accumulator to the binary combiner.
destructurer
A destructurer, usually of type T_DESTRUCTURE. Used with argselect to turn Kernel arguments into something C mklistloop understands.
arg_select
A set of selections from the arguments destructurer finds, used with destructurer.

Listloop parameters

style
A listloop style object, as above.
list
The actual input list.
combiner
The combiner used for each iteration. If not assigned, the default will be used.
top_length
For `many', the length of the top element in case it happens to be circular. Listloop does not encycle the value to make it structurally correct, that has to be done in the combiner.
countdown
Number of elements left in the list, or a negative number if unused.
countup
Number of elements seen so far. Unused as yet.
stop_on
Stop if the return value is eq? this. For boolean list operations like and?, $and?, every?, and the various predicates.

No comments:

Post a Comment