Documentation
¶
Overview ¶
Package bom rolls up a bill of materials by tail recursion, as a state machine. A part has a value, its own cost, and lines, each a quantity of another part. The cost of one part is its value plus, for each line, the quantity times the cost of that part, and the number of each part a system needs is the quantities multiplied down every path to it, summed.
That recursion is not a tail call: a part calls itself once per line. Passing the work still to do as an argument, a stack, makes it one:
walk(stack, need, subtotal) = need, subtotal if stack is empty walk(stack, need, subtotal) = walk(stack', need', subtotal')
where stack', need' and subtotal' are what visiting the top entry makes of them. Going down to a part, the system needs times more of it, and the entry becomes one to come back to the part, with an entry for each line pushed above it. Coming back, every line's part has its subtotal, so the part's is its value plus theirs, and the entry is popped.
The machine is the call: it holds the bill and all three arguments, and each EvCall evaluates it once. A tail call replaces the arguments, so the machine is the next call and nothing is left to return to. The holder's loop is the trampoline: it fires until the call has returned.
The machine refuses a part that contains itself, numbers that would not fit in 64 bits, and more calls than the limit New is given.
Index ¶
Constants ¶
const ( MaxParts = 16 // parts in a bill MaxLines = 8 // lines in a part )
The size of a bill the machine holds.
const MaxStack = MaxParts * (MaxLines + 1)
MaxStack is the most entries the stack holds. Every entry on it is the way back to a part on the current path, or a line of one, and a part is on the path at most once, so an acyclic bill never needs more.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Event ¶
type Event uint8
Event is an input to Fire.
const (
EvCall Event // evaluate walk(stack, need, subtotal) once
)
Event values.
type Line ¶
type Line struct {
Part int64 // the part, an index into the bill
Quantity int64 // how many, at least one
}
Line is a quantity of one part in another.
type Machine ¶
type Machine struct {
// contains filtered or unexported fields
}
Machine is the call walk(stack, need, subtotal) on one bill. Build it with New and change it only with Fire.
func New ¶
New returns the call walk([top], 0, 0) on the bill parts, making at most calls tail calls. A bill of no parts or more than MaxParts, a part of more than MaxLines lines, a negative value, a line to a part not in the bill or of a quantity below one, or a limit below one gives a walk in BadInput.
type Part ¶
Part is a part or an assembly. Its value is its own cost, such as the labour to assemble it.
type State ¶
type State uint8
State is the walk's control state.
const ( Calling State // walk(stack, need, subtotal) is being evaluated Returned // the stack is empty: the walk returned Cyclic // a part is on the path to itself TooLarge // a number would not fit in 64 bits, or the calls passed their limit BadInput // New was given a bill or limit it does not accept )
State values.
Source Files
Directories