#include "fpa.h"

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

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.)