Invocation Lists

Invocation lists are lists of alternate readings of the same wording to invoke a phrase.

§1. Introduction. Here is a "To..." phrase definition, and then a rule making two invocations of it:

To advance (the piece - a chess piece) by (N - a number):
    ...

Every turn:
    advance the pawn by 2;
    advance false by 10:21 PM.

An invocation is a usage of a phrase in a particular case, so here the every turn rule is making two invocations. Even control structures in Inform are phrases, so in fact every line of an imperative definition is exactly one invocation.

Clearly only the first of these invocations makes sense in terms of what the phrase is being applied to. The truth state "false" is not a chess piece, and the time "10:21 PM" is not a number. So this invocation will certainly lead to problem messages being issued, but it is an invocation just the same.

Invocations are stored in the parse tree. The above "every turn" rule comes out thus:

    IMPERATIVE_NT "every turn"
        CODE_BLOCK_NT
            INVOCATION_LIST_NT "advance the pawn by 2"
                INVOCATION_NT "advance the pawn by 2"
            INVOCATION_LIST_NT "advance the pawn by 2"
                INVOCATION_NT "advance false by 10:21 PM"

Each line of the original definition corresponds to an INVOCATION_LIST_NT node: the possible readings of the text as an invocation are then listed as its children, which are all INVOCATION_NT nodes. In this example the text was unambiguous, but for a definition like this:

Every turn:
    let the good old stand by be a random bishop;
    advance the good old stand by by 1;

...the second line can now be read in two different ways:

    advance the good old stand by by 1
            ~~~~~~~~~~~~~~~~~~    ~~~~
    advance the good old stand by by 1
            ~~~~~~~~~~~~~~~~~~~~~    ~

These possibilities each become INVOCATION_NT nodes, and therefore the invocation list for the line has two entries. Those two nodes are joined with next_alternative links, not next links, since they are alternative readings of the same text: they cannot both be right.

Finally, it is worth noting three complications:

(a) Invocation lists arise from expressions as well as from entire code lines, much as functions in C can be used in expressions, int x = f(2); as well as in void context, printf("I do have a return value, you know! Nobody cares.").
- (1) See Imperative Subtrees (in assertions) for how invocation lists for the body of imperative definitions are put together.
- (2) See Conditions and Phrases for how invocation lists from expressions are put together.
(b) "Say" phrases are a special case, in that they can perform more than one invocation. say "Very cold for [time of day], I think?" performs three invocations — one of say (T - text), one of say (T - time), and then another of say (T - text). These three invocations are joined by ->next not ->next_alternative links because all three must be performed.
(c) A small number of invocations for adaptive text do not invoke phrases, but instead print an inflected form of a verb, adjective or similar.

In this section, we provide basic functions for dealing with invocation lists; similarly, Invocations provides tools for dealing with individual invocations; and in Parse Invocations we show how to refine the bare syntax tree for a definition into the above parse tree structure. But choosing between the readings, and compiling the result, is done much deeper in the compiler: see Compile Blocks and Lines (in imperative) for more.

§2. Creation and conversion. Lists are sometimes made new, and sometimes converted from existing but less thoroughly parsed parts of the syntax tree:

parse_node *InvocationLists::new(wording W) {
    parse_node *L = Node::new(INVOCATION_LIST_NT);
    if (Wordings::nonempty(W)) Node::set_text(L, W);
    CompilationUnits::assign_to_same_unit(L, current_sentence);
    return L;
}
parse_node *InvocationLists::new_singleton(wording W, parse_node *inv) {
    parse_node *L = InvocationLists::new(W);
    L->down = inv;
    return L;
}
parse_node *InvocationLists::make_into_list_node(parse_node *p) {
    Node::set_type(p, INVOCATION_LIST_NT);
    return p;
}

§3. Operations on lists. Once lists are created, we tend to represent them not by a pointer to the INVOCATION_LIST_NT node but with a pointer to first_inv, the first of the invocations in the list, i.e., the child of the list node.

Using that convention, where NULL represents the empty list, this extends the list by one:

parse_node *InvocationLists::add_alternative(parse_node *first_inv, parse_node *inv) {
    if (first_inv == NULL) return inv;
    parse_node *p = first_inv;
    while (p->next_alternative) p = p->next_alternative;
    p->next_alternative = inv;
    return first_inv;
}

§4. For convenience, there is a cap on the length of invocation lists, though at least it is preposterously high:

define MAX_INVOCATIONS_PER_PHRASE 4096

§5. The following macro abstracts the process of looping through the invocations in such a list:

define LOOP_THROUGH_INVOCATION_LIST(inv, first_inv)
    LOOP_THROUGH_ALTERNATIVES(inv, first_inv)

§6. And again using this convention, we get:

parse_node *InvocationLists::first_reading(parse_node *first_inv) {
    return first_inv;
}

int InvocationLists::length(parse_node *first_inv) {
    int L = 0;
    parse_node *inv;
    LOOP_THROUGH_INVOCATION_LIST(inv, first_inv) L++;
    return L;
}

void InvocationLists::log(parse_node *first_inv) {
    parse_node *inv;
    LOG("Invocation list (%d):\n", InvocationLists::length(first_inv));
    int n = 0;
    LOOP_THROUGH_INVOCATION_LIST(inv, first_inv)
        LOG("P%d: $e\n", n++, inv);
}

void InvocationLists::log_in_detail(parse_node *first_inv) {
    parse_node *inv;
    int n = 1, L = InvocationLists::length(first_inv);
    LOOP_THROUGH_INVOCATION_LIST(inv, first_inv) {
        LOG("P%d/%d: $e\n", n++, L, inv);
        for (int j=0; j<Invocations::get_no_tokens(inv); j++) {
            parse_node *tok = Invocations::get_token_as_parsed(inv, j);
            LOG("  %d: $P\n", j, tok);
            if (Node::is(tok->down, INVOCATION_LIST_NT)) {
                LOG_INDENT;
                InvocationLists::log_in_detail(tok->down->down);
                LOG_OUTDENT;
            }
        }
    }
}

§7. Sorting the invocation list. This is crucial to the correct running of the compiler, since invocations earlier in the list are more likely to be accepted than later. The list is never very long, so performance is not an issue here, but it's a nuisance to sort a linked list: we must stash it into an array called pigeon_holes, sort that, and then convert it back into a linked list again.

typedef struct invocation_sort_block {
    struct parse_node *inv_data;
    int unsorted_position;
} invocation_sort_block;

invocation_sort_block *pigeon_holes = NULL;
int number_of_pigeon_holes = 0;

parse_node *InvocationLists::sort(parse_node *first_inv) {
    int L = InvocationLists::length(first_inv);
    if (L > 0) {
        Make sure there are at least L pigeonholes available for sorting into7.1;
        Copy the list of alternatives into the pigeonholes7.2;

        qsort(pigeon_holes, (size_t) L, sizeof(invocation_sort_block),
            InvocationLists::sort_cmp);

        Copy the pigeonholes back into the list of alternatives7.3;
    }
    return first_inv;
}

The structure invocation_sort_block is private to this section.

§7.1. We allocate 1000 pigeonholes in the first instance, then double each time we run out. (We will quite likely never run out, as 1000 is plenty. But we want to avoid all possible arbitrary limits.)

Make sure there are at least L pigeonholes available for sorting into7.1 =

    if (L > number_of_pigeon_holes) {
        number_of_pigeon_holes = 2*L;
        if (number_of_pigeon_holes < 1000)
            number_of_pigeon_holes = 1000;
        pigeon_holes =
            Memory::calloc(number_of_pigeon_holes, sizeof(invocation_sort_block),
                INV_LIST_MREASON);
    }

This code is used in §7.

§7.2. Copy the list of alternatives into the pigeonholes7.2 =

    int i = 0;
    for (parse_node *ent=first_inv; (i<L) && (ent); i++, ent=ent->next_alternative) {
        pigeon_holes[i].inv_data = ent;
        pigeon_holes[i].unsorted_position = i;
    }

This code is used in §7.

§7.3. Copy the pigeonholes back into the list of alternatives7.3 =

    parse_node *tail = NULL; first_inv = NULL;
    for (int i=0; i<L; i++) {
        parse_node *i_n = pigeon_holes[i].inv_data; i_n->next_alternative = NULL;
        if (tail) tail->next_alternative = i_n; else first_inv = i_n;
        tail = i_n;
    }

This code is used in §7.

§8. So much for the mechanism. The sorting order ranks invocations first (a) by logical priority of phrases — see To Phrase Family (in assertions); then, in cases of a tie, (b) by the order in which the excerpt parser found the possible reading.

Note that sequence counts for phrases, and unsorted positions in the list, are both unique. This is important since it means InvocationLists::sort_cmp never produces a tie (i.e. returns 0) unless i1 == i2; so the fact that qsort applies an unstable sorting algorithm does not affect the result — we are exactly defining the order of the list.

int InvocationLists::sort_cmp(const void *i1, const void *i2) {
    invocation_sort_block *isb1 = (invocation_sort_block *) i1;
    invocation_sort_block *isb2 = (invocation_sort_block *) i2;

     (a) sort by logical priority of phrases
    int delta =
        ToPhraseFamily::sequence_count(Node::get_phrase_invoked(isb1->inv_data)) -
        ToPhraseFamily::sequence_count(Node::get_phrase_invoked(isb2->inv_data));
    if (delta != 0) return delta;

     (b) sort by creation sequence
    return isb1->unsorted_position - isb2->unsorted_position;
}