# #include "fpa.h"

This page has information from files fpa.h and fpa.c.

## Contents

- Public Routines
- Public Definitions
- Introduction

## Public Routines in File fpa.c

#### Index

fpa_cancel | fpa_update | mega_next_calls | p_fpa_state
fpa_empty | fprint_fpa_index | p_fpa_density | p_path
fpa_first_answer | fprint_fpa_mem | p_fpa_index | zap_fpa_index
fpa_init_index | fprint_fpa_state | p_fpa_mem |
fpa_next_answer | fprint_path | p_fpa_query |

#### Details

    void fpa_cancel(Fpa_state q);

This routine should be called if you get some, but not all answers to an fpa query. See fpa_first_answer() and fpa_next_answer().

    BOOL fpa_empty(Fpa_index idx);

This Boolean routine checks if an FPA/Path index is empty.

    Term fpa_first_answer(Term t, Context c, Querytype query_type,
    		      Fpa_index idx, Fpa_state *ppos);

This routine extracts and returns the first answer term from an Fpa_state tree. If there are no more answers, NULL is returned, and the tree is freed. If you wish to stop getting answers before NULL is returned, call zap_fpa_state(q) to free the Fpa_state tree.

The query types are UNIFY, INSTANCE, GENERALIZATION, VARIANT, and IDENTICAL.

If Context c is not NULL, then the instance of the term (in the context) is used for the query.

    Fpa_index fpa_init_index(int depth);

This routine allocates and returns an empty FPA/Path index. Parameter depth tells how deep to index the terms. For example, depth=0 means to index on the root symbol only.

    Term fpa_next_answer(Fpa_state q);

This routine extracts and returns the next answer term from an Fpa_state tree. If there are no more answers, NULL is returned, and the tree is freed. If you wish to stop getting answers before NULL is returned, call zap_fpa_state(q) to free the Fpa_state tree.

    void fpa_update(Term t, Fpa_index idx, Indexop op);

This routine inserts (op==INSERT) a term into an Fpa_index or deletes (op==DELETE) a term from an Fpa_index.

IMPORTANT: FPA indexing owns the FPA_ID field of the term.

A fatal error occurs if you try to delete a term that was not previously inserted.

    void fprint_fpa_index(FILE *fp, Fpa_index idx);

This routine prints (to FILE *fp) an Fpa_index. WARNING: An Fpa_index can be very big, and it is printed as a tree, so if you use this routine, I suggest trying it on a small index first.

    void fprint_fpa_mem(FILE *fp, BOOL heading);

This routine prints (to FILE *fp) memory usage statistics for data types associated with the fpa package. The Boolean argument heading tells whether to print a heading on the table.

    void fprint_fpa_state(FILE *fp, Fpa_state q, int depth);

This (recursive) routine prints (to FILE *fp) an Fpa_state tree. The depth parameter should be 0 on the top call. This is an AND/OR tree, with lists of terms (ordered by FPA_ID) at the leaves. If FPA_DEBUG is not defined in fpa.h, the paths corresponding to the leaves are not printed, and the tree is hard to understand without the paths.

    void fprint_path(FILE *fp, Ilist p);

This routine prints (to FILE *fp) an FPA Path. A newline is NOT printed.

    unsigned mega_next_calls(void);

    void p_fpa_density(Fpa_index idx);

    void p_fpa_index(Fpa_index idx);

This routine prints (to stdout) an Fpa_index. WARNING: An Fpa_index can be very big, and it is printed as a tree, so if you use this routine, I suggest trying it on a small index first.

    void p_fpa_mem();

This routine prints (to stdout) memory usage statistics for data types associated with the fpa package.

    void p_fpa_query(Term t, Querytype query_type, Fpa_index idx);

This routine constructs an fpa_query tree and prints it to stdout.

    void p_fpa_state(Fpa_state q);

This routine prints (to stdout) an Fpa_state tree. See the description of fprint_fpa_state().

    void p_path(Ilist p);

This routine prints (to stdout) an FPA Path. A newline is NOT printed.

    void zap_fpa_index(Fpa_index idx);

This routine removes all the entries from an Fpa_index idx and frees all of the associated memory.

## Public Definitions in File fpa.h

    /* #define FPA_DEBUG */

    typedef struct fpa_index * Fpa_index;
    typedef struct fpa_state * Fpa_state;

## Introduction

This package implements FPA/Path indexing for first-order terms. It is used to retrieive terms that are likely to unify (in various ways) with a query term. The answers are not guaranteed to unify, and the caller must call some kind of unification routine to check and to construct a substitution.

The unification types are FPA_UNIFY, FPA_INSTANCE, FPA_GENERALIZATION, FPA_VARIANT, and FPA_IDENTICAL. Performance is very good for FPA_INSTANCE, FPA_VARIANT, and FPA_IDENTICAL, fair for FPA_UNIFY, and poor for FPA_GENERALIZATION. (Use Discrimination indexing for FPA_GENERALIZATION, e.g., forward demodulation and forward subsumption.)

Associative-commutative (AC) function symbols are handled by simply ignoring all subterms of AC symbols (which can give bad performance). Commutative/symmetric (C) operations are handled.