AI, machine learning and deep learning · Intermediate

Pruning the search by means of cut

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

The cut operator (!) in Prolog prunes the SLD-tree to optimize search efficiency by eliminating unnecessary backtracking. It distinguishes between 'green cuts', which preserve logical completeness, and 'red cuts', which alter the program's logical meaning by pruning valid success branches.

Intuition

Prolog uses a depth-first search strategy that relies on a goal stack to remember previous resolvents for backtracking. The cut acts as a control device that, when reached, signifies the system should stick to current variable substitutions and not reconsider previous choices. Specifically, it removes choice points on the stack, preventing the system from trying alternative solutions for literals to its left or alternative clauses for the head of the current clause. However, it does not prune choice points above the clause head or those created by literals to the right of the cut that are not yet on the stack. This pruning can optimize performance but risks changing the program's declarative meaning if valid success branches are removed.

Derivation

  1. Prolog employs depth-first search, requiring a goal stack to store previous resolvents for backtracking.
  2. When the cut (!) is reached, it prunes choice points on the stack, removing the need to backtrack to those points.
  3. The cut prevents trying alternative solutions for literals to its left and alternative clauses for the head of the clause in which it appears.
  4. The cut does not prune choice points above the clause head or those created by literals to the right of the cut that are not yet on the stack.
  5. If the cut prunes subtrees containing success branches, it alters the logical meaning (red cut); otherwise, it merely indicates determinism (green cut).

Worked example

Problem

Consider a query about any parent of Paul where a cut is used to optimize for a specific individual. How might this affect the logical meaning?

  1. Identify that the cut is intended to optimize the query by pruning alternatives.
  2. Recognize that if the cut prunes a subtree containing a success branch for a more general query, it removes valid answers.
  3. Conclude that this alteration of the logical meaning constitutes a 'red cut'.

Answer The cut may inadvertently prune valid answers for a more general query, altering the program's logical meaning from a red cut.

Common mistakes

  • Assuming that a cut always preserves the logical meaning of the program; red cuts change the declarative meaning.
  • Believing that a cut prunes all choice points; it only prunes those on the stack at the time of the cut and below the clause head.
  • Thinking that the cut prevents backtracking to literals to its right; it only affects literals to its left and the current clause's alternatives.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

This is a text lesson: it has no animation code yet.

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.