Prolog. We program automatic machines
After reading the article about Prolog, I decided to write a small addition to it in the form of 2 small tasks.
Here they are:
1. The brainfuck language interpreter
2. Turing machine
First we need a SWI-Prolog and some free time.
Let's start with copy-paste from Wikipedia .
Brainfuck - one of the most famous esoteric programming languages, invented by Urban Muller in 1993 for fun. The language has eight commands, each of which is written in one character. The source code of the Brainfuck program is a sequence of these characters without any additional syntax.
The machine managed by the Brainfuck commands consists of an ordered set of cells and a pointer to the current cell, resembling a ribbon and a head of a Turing machine. In addition, it implies a device for communicating with the outside world (see commands. And,) through the input stream and the output stream.
')
The tape is presented in the form of a database.
data (Address, Value).
The head is represented by the cell address.
pos (Address).
Actually code with comments:
To check in the terminal we write:
freest @ PC: $ swipl -s <path.tofile>
? -run ('Path.to.Brainfuck.code').
Let's test on an example from wiki .
Hello World! on brainfuck
++++++++++ [> +++++++> +++++++++> +++> + <<<< -]> ++
.> +. +++++++ .. +++.> ++. << ++++++++++++++.>. +++.
------.--------.> +.>.
Something like this should come out:
freest @ PC: / media / C6984667984655D9 $ swipl -s bf.pro
% library (swi_hooks) compiled into pce_swi_hooks 0.00 sec, 2,224 bytes
% /media/C6984667984655D9/bf.pro compiled 0.00 sec, 4,676 bytes
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.10.4)
Copyright © 1990-2011 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit www.swi-prolog.org for details.
For help, use? - help (Topic). or? - apropos (Word).
? - run ('a.txt').
Hello World!
true
? -
Again a bit of theory from Wiki.
Machine Turinga (MT) - abstract artist (abstract computer). It was proposed by Alan Turing in 1936 to formalize the concept of an algorithm.
The Turing machine is an extension of the finite state machine and, according to Church’s – Turing thesis, is able to imitate all other executors (by setting transition rules) that somehow implement the step-by-step calculation process, in which each step of the calculation is quite elementary.
A specific Turing machine is specified by enumerating the elements of the set of letters of the alphabet A, the set of states Q, and the set of rules by which the machine operates. They have the form: qiaj → qi1aj1dk (if the head is in the qi state, and the letter aj is written in the monitored cell, then the head changes to the qi1 state, the aj1 is recorded in the cell instead of aj, the head makes the movement dk, which has three options: one cell to the left (L), to the cell to the right ®, stay in place (N)). For each possible configuration <qi, aj> there is exactly one rule. There are no rules only for the final state, once in which the car stops. In addition, it is necessary to specify the final and initial states, the initial configuration on the tape and the location of the machine head.
We will use the MT proposed by Vika
q0 * → q0 * R
q01 → q01R
q0 × → q1 × R
q11 → q2aR
q21 → q21L
q2a → q2aL
q2 = → q2 = L
q2 × → q3 × L
q31 → q4aR
q3a → q3aL
q3 * → q6 * R
q4 × → q4 × R
q4a → q4aR
q4 = → q4 = R
q41 → q41R
q4 * → q51R
q5 * → q2 * L
q6a → q61R
q6 × → q7 × R
q7a → q7aR
q71 → q2aR
q7 = → q8 = L
q8a → q81L
q8 × → q9H
data (L, V, R) is the tape view (L is the left, R is the right, V is the current cell).
... [1] [2] [3] [ 4 ] [5] [6] [7] ...
L = [3,2,1] V = 4 R = [5,6,7]
Empty cell value is *
We start MT
$ swipl -s 1.pro
? - initData ([], *, [1,1,1, x, 1,1, =, *]).
? - start (q0).
And here is the result.
$ swipl -s 1.pro
...
? - initData ([], *, [1,1,1, x, 1,1, =, *]).
true
? - start (q0).
q0: (*)
q0: (*): r
[[*], 1,1,1, x, 1,1, =, *]
q0: 1
q0: 1: r
[*, [1], 1,1, x, 1,1, =, *]
...
...
...
q8: a
q8: 1: l
[*, 1,1,1, x, [a], 1, =, 1,1,1,1,1,1, *]
q8: x
e: x: n
[*, 1,1,1, [x], 1,1, =, 1,1,1,1,1,1, *]
end
true
Here they are:
1. The brainfuck language interpreter
2. Turing machine
First we need a SWI-Prolog and some free time.
Task 1. The brainfuck language interpreter
Let's start with copy-paste from Wikipedia .
Brainfuck - one of the most famous esoteric programming languages, invented by Urban Muller in 1993 for fun. The language has eight commands, each of which is written in one character. The source code of the Brainfuck program is a sequence of these characters without any additional syntax.
The machine managed by the Brainfuck commands consists of an ordered set of cells and a pointer to the current cell, resembling a ribbon and a head of a Turing machine. In addition, it implies a device for communicating with the outside world (see commands. And,) through the input stream and the output stream.
Commands and their description:
- > move to the next cell
- <go to previous cell
- + increase the value in the current cell by 1
- - reduce the value in the current cell by 1
- . print the value from the current cell
- , enter value from outside and save to current cell
- [if the value of the current cell is zero, go forward in the program text to the cell next to the corresponding one] (taking into account nesting)
- ] if the value of the current cell is not zero, go back through the program text to the symbol [(including nesting)
')
The tape is presented in the form of a database.
data (Address, Value).
The head is represented by the cell address.
pos (Address).
Actually code with comments:
% , cout:- % pos(Addr), % data(Addr,Value), % put_char([Value]). % . cin:- % pos(Addr), % retract(data(Addr,_)), % get_single_char(Value), % assert(data(Addr,Value)). % + - add(AddValue):- % pos(Addr), % retract(data(Addr,Value)), % 1 NewValue is Value+AddValue, % assert(data(Addr,NewValue)). % > < addr(Side):- % retract(pos(Addr)), % NewAddr is Addr+Side, % assert(pos(NewAddr)), % (data(NewAddr,_),!;assert(data(NewAddr,0))). % ] goto:- % pos(Addr), % 0 data(Addr,Value),Value==0,!, % 0, retract(circle([_|L])), % assert(circle(L)). goto:- % circle([[N,_]|_]), seeing(Stream), seek(Stream,N,bof,_). % [ loop:- % retract(circle(L)), seeing(Stream), % character_count(Stream,Pos), % %( = 0, ) pos(Addr), data(Addr,Value), assert(circle([[Pos,Value]|L])). do:- % get_char(X), % step(X), % not(at_end_of_stream),!, do. do:- % , seeing(Stream), close(Stream), seen. step('['):-loop,!. step(']'):-goto,!. % " " %( ) step(_):-circle([[_,StartValue]|_]),StartValue==0,!. step('>'):-addr( 1),!. step('<'):-addr(-1),!. step(','):-cin,!. step('.'):-cout,!. step('+'):-add( 1),!. step('-'):-add(-1),!. step(_). run(Path):- see(Path), % ( ) retractall(pos(_)), retractall(data(_,_)), retractall(circle(_)), % assert(pos(1)), % 0 assert(data(1,0)), assert(circle([])),do. To check in the terminal we write:
freest @ PC: $ swipl -s <path.tofile>
? -run ('Path.to.Brainfuck.code').
Let's test on an example from wiki .
Hello World! on brainfuck
++++++++++ [> +++++++> +++++++++> +++> + <<<< -]> ++
.> +. +++++++ .. +++.> ++. << ++++++++++++++.>. +++.
------.--------.> +.>.
Something like this should come out:
freest @ PC: / media / C6984667984655D9 $ swipl -s bf.pro
% library (swi_hooks) compiled into pce_swi_hooks 0.00 sec, 2,224 bytes
% /media/C6984667984655D9/bf.pro compiled 0.00 sec, 4,676 bytes
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.10.4)
Copyright © 1990-2011 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit www.swi-prolog.org for details.
For help, use? - help (Topic). or? - apropos (Word).
? - run ('a.txt').
Hello World!
true
? -
Task 2. Turing machine
Again a bit of theory from Wiki.
Machine Turinga (MT) - abstract artist (abstract computer). It was proposed by Alan Turing in 1936 to formalize the concept of an algorithm.
The Turing machine is an extension of the finite state machine and, according to Church’s – Turing thesis, is able to imitate all other executors (by setting transition rules) that somehow implement the step-by-step calculation process, in which each step of the calculation is quite elementary.
A specific Turing machine is specified by enumerating the elements of the set of letters of the alphabet A, the set of states Q, and the set of rules by which the machine operates. They have the form: qiaj → qi1aj1dk (if the head is in the qi state, and the letter aj is written in the monitored cell, then the head changes to the qi1 state, the aj1 is recorded in the cell instead of aj, the head makes the movement dk, which has three options: one cell to the left (L), to the cell to the right ®, stay in place (N)). For each possible configuration <qi, aj> there is exactly one rule. There are no rules only for the final state, once in which the car stops. In addition, it is necessary to specify the final and initial states, the initial configuration on the tape and the location of the machine head.
We will use the MT proposed by Vika
q0 * → q0 * R
q01 → q01R
q0 × → q1 × R
q11 → q2aR
q21 → q21L
q2a → q2aL
q2 = → q2 = L
q2 × → q3 × L
q31 → q4aR
q3a → q3aL
q3 * → q6 * R
q4 × → q4 × R
q4a → q4aR
q4 = → q4 = R
q41 → q41R
q4 * → q51R
q5 * → q2 * L
q6a → q61R
q6 × → q7 × R
q7a → q7aR
q71 → q2aR
q7 = → q8 = L
q8a → q81L
q8 × → q9H
data (L, V, R) is the tape view (L is the left, R is the right, V is the current cell).
... [1] [2] [3] [ 4 ] [5] [6] [7] ...
L = [3,2,1] V = 4 R = [5,6,7]
Empty cell value is *
% revers([],R,R):-!. revers([H|T],L,R):-revers(T,[H|L],R). % l:- % (retract(data([Hl|Tl],V,R)),!; % , (*) retract(data([],V,R)),Hl=(*),Tl=[]), % assert(data(Tl,Hl,[V|R])). r:- % (retract(data(L,V,[Hr|Tr])),!; % , (*) retract(data(L,V,[])),Hr=(*),Tr=[]), % assert(data([V|L],Hr,Tr)). % n. % . %revers ( data). initData(L,V,R):- % ( ) retractall(data(_,_,_)), % ( ) revers(L,[],Lr), % . assert(data(Lr,V,R)). % input(Value):- % , . retract(data(L,_,R)), % . assert(data(L,Value,R)). % info(Q:A:Qn:An:D):- % write(Q:A),nl, write(Qn:An:D),nl, % « » data(L,Value,R),revers(L,[],Lr),append(Lr,[[Value]|R],Data), write(Data),nl. % %(, , , ). % q0(*,q0,*,r). q0(1,q0,1,r). q0(x,q1,x,r). q1(1,q2,a,r). q2(1,q2,1,l). q2(a,q2,a,l). q2(=,q2,=,l). q2(x,q3,x,l). q3(1,q4,a,r). q3(a,q3,a,l). q3(*,q6,*,r). q4(x,q4,x,r). q4(a,q4,a,r). q4(=,q4,=,r). q4(1,q4,1,r). q4(*,q5,1,r). q5(*,q2,*,l). q6(a,q6,1,r). q6(x,q7,x,r). q7(a,q7,a,r). q7(1,q2,a,r). q7(=,q8,=,l). q8(a,q8,1,l). q8(x,e,x,n). %e — . start(e):-write(end),!. % Q start(Q):- % data(_,A,_), % apply(Q,[A,Qn,An,D]), % info(Q:A:Qn:An:D), % input(An), % call(D), % start(Qn). We start MT
$ swipl -s 1.pro
? - initData ([], *, [1,1,1, x, 1,1, =, *]).
? - start (q0).
And here is the result.
$ swipl -s 1.pro
...
? - initData ([], *, [1,1,1, x, 1,1, =, *]).
true
? - start (q0).
q0: (*)
q0: (*): r
[[*], 1,1,1, x, 1,1, =, *]
q0: 1
q0: 1: r
[*, [1], 1,1, x, 1,1, =, *]
...
...
...
q8: a
q8: 1: l
[*, 1,1,1, x, [a], 1, =, 1,1,1,1,1,1, *]
q8: x
e: x: n
[*, 1,1,1, [x], 1,1, =, 1,1,1,1,1,1, *]
end
true
Sources:
Source: https://habr.com/ru/post/136670/
All Articles