From 5b9f0f45a9ada42deacb089d1b66881da8ec6e99 Mon Sep 17 00:00:00 2001 From: Markus Triska Date: Mon, 21 Dec 2020 19:55:15 +0100 Subject: [PATCH] document first instantiated argument indexing Many thanks to @notoria for this brilliant idea and implementation! --- README.md | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) diff --git a/README.md b/README.md index a0364d65..6688f01f 100644 --- a/README.md +++ b/README.md @@ -226,6 +226,37 @@ arithmetic operators with the usual precedences, New operators can be defined using the `op` declaration. +### First instantiated argument indexing + +Scryer Prolog indexes on the leftmost argument that is not a variable +in all clauses of a predicate's definition. We call this strategy +first *instantiated* argument indexing. + +A key motivation for first instantiated argument indexing is to enable +indexing for meta-predicates such as `maplist/N` and `foldl/N`, where +the first argument is a goal or partial goal that is a variable in the +definition of these predicates and therefore cannot be used for +indexing. + +For example, a natural definiton of `maplist/2` reads: + +``` +maplist(_, []). +maplist(Goal, [L|Ls]) :- + call(Goal, L), + maplist(Goal, Ls). +``` + +In this case, first instantianted argument indexing automatically uses +the *second* argument for indexing, and thus prevents choicepoints for +calls with lists of fixed lengths (and deterministic goals). +Conveniently, no auxiliary predicates with reorderd arguments are +needed to benefit from indexing in such cases. + +Conventional first argument indexing naturally arises as a +special case of this strategy, if the first argument is instantiated +in any clause of a predicate's definition. + ### Strings and partial strings In Scryer Prolog, the default value of the Prolog flag `double_quotes` -- 2.54.0