

# ε-prolog

[![img](https://melpa.org/packages/eprolog-badge.svg)](https://melpa.org/#/eprolog)
[![img](https://deepwiki.com/badge.svg)](https://deepwiki.com/tani/eprolog)

> [!TIP]
> For usage and API details, please check deepwiki!

ε-prolog (`eprolog`) is a complete Prolog engine implementation written in pure Emacs Lisp. It provides a fully functional Prolog system integrated into the Emacs environment, offering traditional Prolog programming capabilities with seamless Lisp interoperability.

# Features

## Core Prolog Engine

-   Complete unification algorithm with occurs check
-   Backtracking and choice points with proper cut (!) semantics
-   Clause database management for facts and rules
-   Interactive query execution with solution enumeration

## Built-in Predicates

-   Unification: `=`, `==`
-   Type checking: `atom/1`, `atomic/1`, `var/1`, `ground/1`, `number/1`, `string/1`
-   Control: `fail/0`, `!/0`, `true/0`, `false/0`, `not/1` (negation as failure)
-   Logical operators: `and/0+`, `or/0+`, `if/2-3`
-   List operations: `member/2`, `append/2-3`, `maplist/2-5`
-   Meta-call: `call/1+`
-   Arithmetic: `is/2` which is an alias of `lisp/2+`
-   Lisp integration: `lisp/2+`, `lisp!/1+`, `lispp/1+`
-   Dynamic parameters: `store/2`, `fetch/2` for stateful computation

## Advanced Features

-   Definite Clause Grammar (DCG) support
-   Spy/debugging functionality for tracing execution
-   Dynamic parameters (`store/2`, `fetch/2`) with backtracking-aware state management
-   Anonymous variable handling
-   Variable renaming for clause application
-   Explicit-stack proof engine for deep search without Lisp stack growth

# Requirements

ε-prolog requires Emacs 27.2 or later. Emacs 29+ is still recommended for general performance, but deep proof search no longer depends on recursive Lisp control flow.

# Installation

Place `eprolog.el` in your Emacs load path and add to your configuration:

```
(require 'eprolog)
```

# Quick Start

For detailed examples, tutorials, and comprehensive documentation, see the docs/ directory.

Basic usage involves defining facts and rules, then querying the knowledge base:

```
;; Define facts
(eprolog-define-predicate (parent tom bob))
(eprolog-define-predicate (parent bob ann))

;; Define rules  
(eprolog-define-predicate (grandparent _x _z)
  (parent _x _y)
  (parent _y _z))

;; Query the database
(eprolog-query (grandparent tom _x))
;; Returns: _x = ann

;; Dynamic parameters for stateful computation
(eprolog-query 
 (store counter 0)
 (fetch counter _old)
 (is _new (+ _old 1))
 (store counter _new)
 (fetch counter _result))
;; Returns: _result = 1
```

ε-prolog provides convenient aliases:

-   `eprolog-define-predicate` for `eprolog-define-prolog-predicate`
-   `eprolog-define-predicate!` for `eprolog-define-prolog-predicate!`

For complete API documentation, advanced examples, and comprehensive tutorials, see the docs/ directory.

# Testing

ε-prolog includes a comprehensive test suite in the docs/ directory with tests covering all major functionality.

Run tests with:

```
make test
```

See the docs/ directory for detailed testing instructions and interactive test examples.

# Debugging

Enable spy mode to trace predicate execution:

```
(setq eprolog-spy-predicates '(grandparent parent))
(setq eprolog-spy-state 'prompt) ; or 'always or 'disabled
```

See the docs/ directory for comprehensive debugging examples and techniques.

# Implementation Details

ε-prolog implements a complete Prolog engine with:

-   Unification: Standard unification algorithm with optional occurs check
-   Proof Search: Depth-first search with explicit goal and choice-point stacks
-   Cut Implementation: Proper cut semantics by trimming choice points
-   Variable Scoping: Automatic variable renaming for clause application
-   Runtime Safety: Optional engine step limit that signals an explicit error

The engine evaluates queries with a `while`-driven state machine. Solutions are enumerated by resuming saved engine state instead of chaining continuations, which keeps deep `repeat/0`, `member/2`, `append/3`, and DCG searches off the Lisp call stack.

Lisp predicates defined with `eprolog-define-lisp-predicate` run inside that engine and must return `eprolog--make-success` with the next engine state or `eprolog--make-failure`. If `eprolog-max-steps` is non-nil and a query exceeds it, ε-prolog signals `eprolog-step-limit-exceeded` instead of reporting logical failure.

# License

ε-prolog is released under the GNU General Public License v3.0. See LICENSE.org for details.

# Historical Note

This implementation has an interesting lineage.
It originally derives from Peter Norvig's Prolog implementation in [Paradigms of Artificial Intelligence Programming](https://github.com/norvig/paip-lisp) ([MIT licensed](https://github.com/norvig/paip-lisp/blob/9cea73837e439d331fe78d7b585e994c7113aac2/LICENSE)).
The code was first reimplemented in Scheme as [Athena](https://github.com/tani/athena), then ported back to Common Lisp,
and finally adapted for Emacs Lisp as ε-prolog.
Each iteration refined the implementation while maintaining the core algorithmic elegance of the original.

# Contributing

Contributions are welcome! Please feel free to submit issues and pull requests.

# Author

Masaya Taniguchi

# Acknowledgments

This implementation draws inspiration from classical Prolog systems and modern functional programming techniques, adapted specifically for the Emacs Lisp environment.
