Proposal: Refactor Substitution Logic to Use the Strategy Pattern with `Substitutable` Interface

Summary
The current implementation of SubstitutionImpl introduces unintended behavior by evaluating functional terms (FunctionalTerm) and computed atoms (ComputedAtom) when applying substitutions. This violates the expected behavior, as substitutions should only replace variables with their corresponding terms, without triggering evaluation.

Additionally, it is currently impossible to apply a substitution to functional terms or computed atoms recursively without evaluating them, due to the lack of a dedicated method for substitution in these classes. This results in tight coupling between SubstitutionImpl and specific term/atom implementations, making the system hard to extend.

Proposed Solution
I propose refactoring the substitution logic with the Strategy Pattern by introducing a Substitutable interface. This interface allows each class (e.g., FunctionalTerm, Atom) to define its own substitution behavior. This eliminates the need for SubstitutionImpl to hardcode logic for specific types, and ensures functional terms and computed atoms are not evaluated unless explicitly required.

Proposed Interfaces

Substitutable Interface

public interface Substitutable<R> {
    /**
     * Applies the given substitution to this object.
     *
     * @param substitution the substitution to apply
     * @return a new instance with the substitution applied
     */
    R applySubstitution(Substitution substitution);
}

Substitution Interface

public interface Substitution {
    /**
     * Applies this substitution to a Substitutable object.
     *
     * @param substitutable the object to apply the substitution on
     * @param <S> the type of the substitutable object
     * @param <R> the return type of the substitution
     * @return the substituted object of type R
     */
    <S extends Substitutable<R>, R> R createImageOf(S substitutable);

    /**
     * Retrieves the term mapped to a specific variable in this substitution.
     *
     * @param variable the variable to substitute
     * @return the image of the variable
     */
    Term getImageOfVariable(Variable variable);
    
    [...]
}

Term interface

public interface Term extends Substitutable<Term> { [...] }

Atom interface

public non-sealed interface Atom extends FOFormula, Substitutable<Atom> { [...] }

Example Implementations

AtomImpl Class

@Override
public Atom applySubstitution(Substitution substitution) {
    return new AtomImpl(predicate, Arrays.stream(terms)
                                         .map(substitution::createImageOf)
                                         .toList());
}

FunctionalTermImpl Class

@Override
public Term applySubstitution(Substitution substitution) {
    return new FunctionalTermImpl(functionName, invoker, subTerms.stream()
                                                                .map(substitution::createImageOf)
                                                                .toList());
}

Advantages of This Approach

1. No Premature Evaluation

   • Functional terms and computed atoms remain unevaluated after substitution, preserving expected behavior.

2. Extensibility

   • New term or atom types can implement Substitutable without requiring changes to SubstitutionImpl.
   • Also, it is easy to make other objects Substitutable, without any need to modify SubstitutionImpl: objects such as FOFormulas, FOQueries or FactBases could easily become substitutable if required.
   • A user that would want to make an object Substitutable does not need to modify Integraal to do so, it is only necessary to implement this interface.

3. Decoupling

   • SubstitutionImpl no longer depends on the internal details of terms or atoms, making the codebase cleaner and easier to maintain.

added Refactoring label

assigned to @gperutio

changed the description