--
-- AnBnCn Turing Machine in SQL with arrays
--

DROP SCHEMA IF EXISTS Turing CASCADE;
CREATE SCHEMA Turing;

-- list of states
-- 0 is always the initial state
CREATE TABLE Turing.State(
  sid INTEGER PRIMARY KEY,
  sname TEXT UNIQUE NOT NULL, -- just for show
  isFinal BOOLEAN NOT NULL,
  scomment TEXT DEFAULT NULL
);

-- list of symbols (not really useful)
CREATE TABLE Turing.Symbol(
  cid INTEGER PRIMARY KEY,
  cname TEXT UNIQUE NOT NULL,
  ccomment TEXT DEFAULT NULL
);

-- initial tape contents
CREATE TABLE Turing.Tape(
  tid INTEGER PRIMARY KEY,
  symbol INTEGER REFERENCES Turing.Symbol,
  scomment TEXT DEFAULT NULL
);

-- TM Transition Function
CREATE TABLE Turing.Transition(
  -- initial state & symbol
  sid INTEGER NOT NULL REFERENCES Turing.State,
  symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
  UNIQUE(sid, symbol),
  -- new state, symbol and move
  new_state INTEGER NOT NULL REFERENCES Turing.State,
  new_symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
  move INTEGER NOT NULL CHECK(move=-1 OR move=1),
  -- explanation
  tcomment TEXT DEFAULT NULL
);

-- record state/tape/pos of TM while running
CREATE TABLE Turing.Run(
  rid INTEGER PRIMARY KEY,
  -- current state
  sid INTEGER NOT NULL REFERENCES Turing.State,
  -- full tape stored in an array
  tape INTEGER[] NOT NULL,
  -- next position on tape
  pos INTEGER NOT NULL CHECK(pos BETWEEN 0 AND array_length(tape, 1)+1)
);

-- display a tape with its symbols and head as:
-- AAaBBbCcc
--        ^
CREATE FUNCTION Turing.ShowTape(tape INTEGER[], pos INTEGER) RETURNS TEXT
IMMUTABLE STRICT AS $$
  SELECT array_to_string(
           ARRAY(SELECT s.cname
                 FROM generate_series(1, array_length(tape, 1)) AS i
                 JOIN Turing.Symbol AS s ON (tape[i]=s.cid)
                 WHERE tape[i]<>0
                 ORDER BY i ASC),
	   '') || E'\n' || repeat(' ', pos-1) || '^' ;
$$ LANGUAGE SQL;

--
-- define AnBnCn Turing Machine
--

COPY Turing.State(sid, sname, isFinal, scomment) FROM STDIN;
0	a?	FALSE	look for 'a'
1	>b	FALSE	look for 'b' once 'a' was seen
2	>c	FALSE	look for 'c' once 'b' was seen
3	A<	FALSE	look back for 'A' marker
4	>0	FALSE	check scan at the end
5	Y	TRUE	input matches a^nb^nc^n
6	N	TRUE	input does not match a^nb^nc^n
\.

COPY Turing.Symbol(cid, cname, ccomment) FROM STDIN;
0	 	special blank symbol
1	a	'a' input symbol
2	b	'b' input symbol
3	c	'c' input symbol
4	A	marker when 'a' is seen
5	B	marker when 'b' is seen
6	C	marker when 'c' is seen
\.

-- mark a as A, b as B, c as C, and loop back
COPY Turing.Transition(sid,symbol,new_state,new_symbol,move,tcomment) FROM STDIN;
0	1	1	4	+1	a -> A
0	5	4	5	+1	B -> check end
0	0	5	0	+1	blank => n=0 => ok
1	1	1	1	+1	skipping a
1	5	1	5	+1	skipping B
1	2	2	5	+1	b -> B
2	2	2	2	+1	skipping b
2	3	3	6	-1	c -> C, return
2	6	2	6	+1	skipping C
3	1	3	1	-1	return, skip a
3	2	3	2	-1	return, skip b
3	4	0	4	+1	stop return on A
3	5	3	5	-1	return, skip B
3	6	3	6	-1	return, skip C
4	0	5	0	+1	check end, blank => ok
4	4	4	4	+1	check end, skip A
4	5	4	5	+1	check end, skip B
4	6	4	6	+1	check end, skip C
0	2	6	2	+1	KO
0	3	6	2	+1	KO
0	4	6	4	+1	KO
0	6	6	6	+1	KO
1	0	6	0	+1	KO
1	3	6	3	+1	KO
1	4	6	4	+1	KO
1	6	6	6	+1	KO
2	0	6	0	+1	KO
2	1	6	1	+1	KO
2	4	6	4	+1	KO
2	5	6	5	+1	KO
3	0	6	0	+1	KO
3	3	6	3	+1	KO
4	1	6	1	+1	KO
4	2	6	2	+1	KO
4	3	6	3	+1	KO
\.

-- initial tape contents for test run: aabbcc
INSERT INTO Turing.Tape(tid, symbol) VALUES
  (1, 1),
  (2, 1),
  (3, 2),
  (4, 2),
  (5, 3),
  (6, 3);

--
-- Run TM
--
TRUNCATE Turing.Run;

-- current iteration optimization
-- CREATE SEQUENCE Turing.running_seq MINVALUE 0 START WITH 0;

-- RECURSIVE constraints make it hard to build a TM
-- only one (not two) direct (no subquery) reference is allowed
WITH RECURSIVE running(rid, sid, tape, pos) AS (
  -- first store initial tape contents
  SELECT 0, 0, ARRAY(SELECT symbol FROM Turing.Tape ORDER BY tid), 1
  UNION
  -- then proceed to compute iterations
  SELECT p.rid+1, t.new_state,
         -- build updated tape as an array
         p.tape[1:p.pos-1] ||                      -- prefix
           t.new_symbol ||                         -- updated cell
           p.tape[p.pos+1:array_length(p.tape,1)], -- suffix
         -- move cursor position
         p.pos+t.move
  -- p is previous state thanks to WHERE condition hack below
  FROM running AS p
  -- get state details, to know whether to stop
  JOIN Turing.State AS s ON (p.sid=s.sid)
  -- get corresponding state transition
  JOIN Turing.Transition AS t ON (p.sid=t.sid AND
                                  -- coalesce defaults to blank
                                  t.symbol = COALESCE(p.tape[p.pos],0))
  WHERE -- *hack*: get last state optimization
        -- otherwise UNION would cleanup regenerated states
        -- p.rid = NEXTVAL('turing.running_seq') AND
    -- stop on a final state
        NOT s.isFinal
)
-- just store the computed table
INSERT INTO Turing.Run
  SELECT * FROM running;

-- cleanup helper sequence
-- DROP SEQUENCE Turing.running_seq;

SELECT
  r.rid AS n, s.sname,
  Turing.ShowTape(r.tape, r.pos) AS tape,
  s.isFinal AS fin, r.sid, r.pos
FROM Turing.Run AS r
JOIN Turing.State AS s USING (sid)
ORDER BY rid ASC;
