SWI-Prolog中堆栈的实现

Question

因此，我必须实现一个ADT，在本例中是SWI-Prolog中的Stack。我需要帮助，因为我是这个编程语言的新手，不知道如何开始。

这是从python(3)中的一个实现开始的，我在其中定义了一个类并添加了要使用的函数(push、is_empty、pop、peak)。但是现在，我需要在prolog中做一些类似的事情。

我已经访问了其他一些与我的类似的堆栈溢出问题，但我仍然无能为力。

我认为这不仅仅是为了在SWI-Prolog中定义一个列表，请帮助。

Answer 1

既然您提到了ADTs，我将使用Logtalk (您可以在大多数Prolog系统中运行)首先定义一个堆栈协议/接口：

:- protocol(stack_protocol).

    :- public(new/1).
    :- mode(new(--stack), one).
    :- info(new/1, [
        comment is 'Creates a new empty stack.',
        argnames is ['Stack']
    ]).

    :- public(empty/1).
    :- mode(empty(@stack), one).
    :- info(empty/1, [
        comment is 'True if the stack is empty.',
        argnames is ['Stack']
    ]).

    :- public(top/2).
    :- mode(top(?stack, ?element), zero_or_one).
    :- info(top/2, [
        comment is 'True if Top is the top element of the stack.',
        argnames is ['Stack', 'Top']
    ]).

    :- public(push/3).
    :- mode(push(?stack, ?element, ?stack), zero_or_one).
    :- info(push/3, [
        comment is 'Adds an element to the stack.',
        argnames is ['Stack0', 'Element', 'Stack']
    ]).

    :- public(pop/3).
    :- mode(pop(?stack, ?element, ?stack), zero_or_one).
    :- info(pop/3, [
        comment is 'Removes an element from the stack.',
        argnames is ['Stack0', 'Element', 'Stack']
    ]).

:- end_protocol.

我们现在可以为堆栈ADT定义一个实现。显而易见的选择是简单地使用列表：

:- object(stack,
    implements(stack_protocol)).

    new([]).

    empty(Stack) :-
        Stack == [].

    top([Top| _], Top).

    push(Stack, Element, [Element| Stack]).

    pop([Element| Stack], Element, Stack).

:- end_object.

假设在stack.lgt源文件中定义了协议和对象，则示例调用将为：

| ?- {stack}.
...
% (0 warnings)

(4 ms) yes
| ?- stack::(
         new(S0),
         push(S0, 1, S1),
         push(S1, 2, S2),
         push(S2, 3, S3),
         top(S3, T),
         pop(S3, E, S)
     ).

E = 3
S = [2,1]
S0 = []
S1 = [1]
S2 = [2,1]
S3 = [3,2,1]
T = 3

yes

是否值得定义该协议？当需要几种不同的实现(例如，字典或随机数生成器)时，协议特别有用。但是，在这种情况下，列表是实现堆栈的自然候选者，以至于定义协议的有用性主要是为了它的教育价值。在大多数情况下，当需要堆栈时，程序员直接使用列表。