Реализация стека в SWI-Prolog - PullRequest
Новая
       44

Реализация стека в SWI-Prolog

0 голосов
/ 09 мая 2020

Итак, я должен реализовать ADT, в данном случае стек в SWI-Prolog. Мне нужна помощь, потому что я новичок в этом языке программирования и не знаю, с чего начать.

Это началось как реализация в python (3), где я определил класс и добавил функции для работы с (пу sh, пусто?, поп, пик). Но теперь мне нужно сделать что-то подобное в прологе.

Я посетил несколько других вопросов о стеке, похожих на мой, но я все еще беспомощен.

Я думаю, что это не только для определения список в SWI-Prolog, пожалуйста, помогите.

1 Ответ

0 голосов
/ 09 мая 2020

Поскольку вы упомянули ADT, я буду использовать 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

Это достойно определения протокола? Протоколы особенно полезны, когда ожидается несколько различных реализаций (например, словарь или генератор случайных чисел). Но в этом случае список является настолько естественным кандидатом для реализации стека, что полезность определения протокола в основном связана с его образовательной ценностью. В большинстве случаев, когда требуется стек, программисты просто используют список напрямую.

...