Als Data/Analytics Engineers schrijven we vaak Snowflake procedures in Python. Snowflake maakt dat heel makkelijk: we kunnen in de body van een CREATE STATEMENT gewoon Python code zetten. Vervolgens laten we Snowflake weten welke Python functie uit de body aanroepen moet worden. Als we main willen laten uitvoeren schrijven we bijvoorbeeld HANDLER = 'main‘. Dat we gewoon Python kunnen gebruiken in Snowflake procedures en functies maakt veel mogelijk. Zo kunnen we met Python API’s aanroepen. Iets wat niet gaat in puur SQL. Vaak kiezen we hierbij een procedurele benadering, maar dat hoeft niet. We kunnen functionaliteit vastleggen in aanvullende functies, maar we kunnen ook gebruik maken van de objectgeoriënteerde mogelijkheden van Python. In deze blog gaan we onderzoeken hoe we op een objectgeoriënteerd manier een Turingmachine kunnen maken met Python.
Objectgeoriënteerd programmeren met Python
Object-oriented programming is een veel gebruikte stijl of benadering van programmeren. In plaats van met functies werken we dan vooral met klassen. Zo’n klasse (class in Python) kan methoden definiëren die dan als een soort functies gebruikt kunnen worden bij objecten van die klasse (de instances). Ook kunnen die objecten bepaalde eigenschappen hebben, de attributen. Deze attributen kunnen veranderen! Dus we moeten ervoor zorgen dat we goed weten in welke staat een object zich bevindt, dat wil zeggen, wat de waardes zijn van deze attributen op enig moment. Dat is niet altijd handig, maar het is wel een heel krachtige manier om een bepaalde situatie te modelleren. Ik denk dat het namaken van een soort hypothetisch computertje (dat extreem veel kan!) een goed voorbeeld is voor wanneer je dat zou willen doen en het is heel leuk!
Turingmachines
Turingmachines zijn een heel complex onderwerp met (letterlijk) oneindige implicaties. Oorspronkelijk een gedachte-experiment van Alan Turing (1912-1954) waarmee kan worden nagedacht over het wiskundige concept van berekenbaarheid1, wordt het ook gezien als een belangrijk inspiratiebron voor de uitvinding van de computer2. Daar gaan we ons allemaal niet mee bezig houden. Een Turingmachine is namelijk ook relatief simpel, in die zin dat het maar een paar dingen doet. Daarom is het leuk om met Python code na te maken. (Voor zover dat kan, eigenlijk maken we meer een soort Turing-geïnspireerde machine.)
Onze Turingmachine moet aan een aantal dingen voldoen:
- De machine bevat een oneindig uitbreidbare band waarop symbolen gestempeld kunnen worden. We beperken ons daarbij tot de symbolen
1en0(ofTrueenFalsein Python). In de representatie van de band kiezen we er in het vervolg voor om1(True) alsxte tonen en0(False) also. - De machine kan een symbool tegelijkertijd lezen. Daarna kan de machine het stukje band direct links of rechts van het huidige stukje band lezen. Grotere sprongen zijn dus niet mogelijk!
- Als de machine een symbool heeft gelezen, vervangt de machine het symbool door een nieuw symbool. Dat kan hetzelfde symbool zijn, maar er wordt altijd een symbool gestempeld op de band nadat de machine iets heeft gelezen!
- Vervolgens verplaatst de machine zich naar een nieuw stukje band ernaast (dat ook een symbool bevat). De machine kan dus direct naar links of naar rechts gaan.
- Wat de machine stempelt en in welke richting het zich verplaatst wordt bepaald door de staat waarin de machine zich bevindt. Er zijn verschillende staten en die bepalen wat er gebeurt wanneer een bepaald symbool wordt gelezen.
- De combinatie lezen, stempelen, verplaatsen en naar een nieuwe staat gaan noemen we de zetten van de machine.
- In plaats van naar een nieuwe staat gaan kan de machine ook stoppen.
Turingmachine in objectgeoriënteerd Python
Laten we aan de slag gaan! De code in deze blog is gebaseerd op mijn uitgebreidere GitHub repository. Ik zal niet alle code bespreken die daar staat. In plaats daarvan heb ik een aantal dingen versimpeld en laat ik een aantal dingen weg zodat het wat overzichtelijker wordt.
Laten we beginnen met het stukje band waarop het symbool staat te definiëren als klasse:
class Square:
def __init__(self, symbol: bool = False):
self.symbol: bool = symbol
@classmethod
def from_pattern(cls, pattern: str) -> 'Square':
if pattern not in ['o', 'x']:
raise ValueError("Pattern should be either 'o' or 'x'")
return Square(pattern[0] == 'x')We kunnen nu een stukje band maken. We moeten __init__ definiëren om objecten van de klasse Square te kunnen maken. Later in de code zullen we dan Square(False), Square(True) of Square() doen. Python roept dan __init__ voor ons aan en geeft ons de daadwerkelijke objecten of instanties van de klasse. Daar kunnen we dan mee aan de slag. Overigens betekent Square() eigenlijk ook Square(False) omdat we een default hebben meegegeven: symbol: bool = False.
Merk daarnaast op dat we een @classmethod decorator gebruiken. Dat stelt ons in staat om een Square op 2 manieren te maken, met Square() en met Square.from_pattern('o'). @classmetod is standaard meegeleverd met Python en zorgt ervoor dat niet de instantie zelf maar de klasse meegegeven wordt aan de method, waardoor we een nieuwe instantie kunnen maken in plaats van iets uitvoeren op een bestaande instantie. De andere objecten hebben ook zo’n class method, maar die zullen we niet meer bespreken.
Nu kunnen we de band van de Turingmachine samenstellen uit de stukjes:
class Tape:
def __init__(self, squares: list[Square] = [Square()]):
self.squares: list[Square] = squares
def __getitem__(self, i: int) -> Square:
return self.squares[i]
def feed_left(self) -> None:
"""Adds new squares on the left side of the tape."""
self.squares.insert(0, Square())
def feed_right(self) -> None:
"""Adds new squares on the right side of the tape."""
self.squares.append(Square())We zien dat de band bestaat uit een lijst van Squares (of stukjes band). Verder definiëren we hoe we een van die stukjes kunnen bemachtigen met __getitem__. Daardoor kunnen we met de band werken op eenzelfde manier als dat we met lists werken. Als we onze band band noemen, pakt band[5] het vijfde stukje van die band. Verder hebben we ook methods nodig die onze band oneindig uit kunnen breiden! Daarvoor gebruiken we feed_left en feed_right.
De machine
We hebben de band van onze Turingmachine gemaakt. Waar bestaat de machine nog meer uit? Zoals gezegd kan de machine in een bepaalde staat zijn. We willen dus die staten definiëren. Een aantal staten samen vormen een programma dat het gedrag van de machine kan bepalen. De combinatie van de band met waardes en het programma dat uit staten bestaat zorgt ervoor dat de machine kan draaien en voor een bepaalde uitkomst kan zorgen.
Laten we even naar het volgende overzicht kijken:
We zien dat onze Turingmachine in Python bestaat uit een aantal Python objecten. Het Machine object maakt gebruik van een Tape object en een Program object. We kunnen een Tape object zien als een lijst van Square objecten en we kunnen een Program zien als een lijst met State objecten. Tot slot zien we nog een laatste soort object: Bahavior. Een State bevat twee van dat soort objecten. Een Behavior voor als we op de band een 1 (of True als x) tegenkomen en een Behavior voor als we op de band een 0 (of False als o) tegenkomen:
Het programma
Laten we kijken naar de objecten die nodig zijn voor een programma. Allereerst hebben we de Behavior objecten:
class Behavior:
def __init__(self, symbol: bool, goes_right: bool, state_i: int):
self.symbol: bool = symbol
self.goes_right: bool = goes_right
self.state_i: int = state_iWe zien dat we het symbool vastleggen (met een waarde True of False). Verder bepalen we of we naar rechts gaan, goes_right, en tot slot definiëren we de State waar we naartoe zouden gaan. Voor nu is dat alleen nog een nummer dat aangeeft welke van de staten in het programma we bedoelen.
Dan gaan we met de State objecten aan de slag:
class State:
def __init__(self, when_false: Behavior, when_true: Behavior):
self.when_false: Behavior = when_false
self.when_true: Behavior = when_true
def __getitem__(self, p: bool) -> Behavior:
if p == False:
return self.when_false
else:
return self.when_trueNaast vaststellen welke Behavior we willen als we een 0 (of False) tegenkomen en vaststellen welke Behavior we juist willen als we een 1 (of True) tegenkomen, voegen we hier ook weer een __getitem__() methode toe. Nu kunnen we bij de juiste Behavior komen door het symbool dat we tegen komen in te vullen bij de State. Als we een State hebben die staat heet kunnen we staat[True] doen en dan weten we wat er verder moet gebeuren.
Nu is het tijd om het programma samen te stellen:
class Program:
def __init__(self, states: list[State] = []):
self.states: list[State] = states
def __getitem__(self, i: int) -> State:
if i < 1:
raise IndexError("0 is out of range: Program is 1-based")
return self.states[i - 1]Zoals we zien is het Program object eigenlijk gewoon een lijst van State objecten, maar er gebeurt wel iets bijzonders met __getitem__(). We willen namelijk dat 0 betekent dat de Turingmachine stopt. Daarom gebruiken we niet de gebruikelijke zero-based numbering van lists. In plaats daarvan kiezen we voor one-based numbering waarbij we beginnen met tellen vanaf 1. Als we de eerste staat willen van een Program object met de naam programma doen we dus programma[1] in plaats van programma[0].
De objecten samen laten komen
Nu we een band (Tape) en een programma (Program) hebben voor de Turingmachine, kunnen we het object voor de machine maken (Machine):
class Machine:
def __init__(self, tape: Tape = Tape(), program: Program = Program()):
self.tape: Tape = tape
self.program: Program = program
self.square_i: int = 0
self.state_i: int = 1 # 0 means halt!
self.configuration: BehaviorWe doen hierboven een aantal dingen: we zorgen ervoor dat de machine een Tape en een Program object bevat en we initialiseren de indexen van deze objecten. We willen namelijk van de band het meest linker stukje hebben: het Square object met de index 0. Van het programma willen we de eerste staat hebben: het State object met de index 1! Daarnaast zeggen we dat we later een attribute configuration verwachten waarvan het type Behavior is. Deze Behavior krijgen we als we het gescande symbool invullen bij het State object. We weten dan wat we moeten stempelen, welke kant we op moeten gaan en naar welke volgende staat we moeten gaan. Bovenstaande handelingen worden als methodes gedefinieerd:
def scan(self) -> None:
scanned_symbol = self.tape[self.square_i].symbol
self.configuration = self.program[self.state_i][scanned_symbol]
def stamp(self) -> None:
self.tape[self.square_i].symbol = self.configuration.symbol
def change_square(self) -> None:
goes_right: bool = self.configuration.goes_right
goes_left: bool = not goes_right
last_i: int = len(self.tape) - 1
if goes_left and self.square_i == 0:
self.tape.feed_left()
elif goes_left:
self.square_i -= 1
elif goes_right and self.square_i == last_i:
self.tape.feed_right()
self.square_i += 1
else:
self.square_i += 1
def change_state(self) -> None:
self.state_i = self.configuration.state_i
def rewind(self) -> None:
self.square_i = 0
self.state_i = 1 # 0 means halt!
if hasattr(self, 'configuration'):
delattr(self, 'configuration')De scan methode kijkt gewoon naar het huidige stukje band en vraagt daarvan het symbool op. Vervolgens gaan we naar de huidige staat en vullen we daar dat symbool in. We krijgen dan bij een False het .when_false attribuut van de staat terug en bij een True het .when_true attribuut. Dat is een Behavior waarvan we vervolgens het configuration attribuut maken dat we nodig gaan hebben bij de .stamp(), de .change_square() en de .change_state() methodes.
.stamp() verandert het symbool van het stukje band waar we op staan. .change_square verandert naar welk stukje band we kijken. Daar zit alleen een complicerende factor: de band is oneindig uitbreidbaar! Als we aan de meest linker kant van de band zijn gekomen en we gaan naar links, dan moet er dus een stukje band bij. Dat gebeurt met de .feed_left() method van de Tape klasse. Als we naar rechts gaan vanaf het meest rechter stukje band gebruiken we juist .feed_right().
We willen natuurlijk wel een resultaat krijgen! Hoe draaien we de Turingmachine? Dat doen we door het Machine object iterable te maken. Doorvoor gebruiken we 2 methods: __iter__() en __next__(). De logica bevind zich vooral in de tweede method die door python steeds aangeroepen gaat worden terwijl we de machine laten draaien. In feite doen we elke keer het volgende:
- We kijken of we moeten stoppen. Dat is als we een staat-index (
state_i) van0hebben. De nulde staat is bij wijze van spreken de stop-staat. - We gaan met
.scan()kijken welke symbool er op ons stukje band staat en op basis daarvan bepalen we wat er moet gebeuren. Dat leggen we dan weer vast in het.configurationattribuut. - We vervangen het symbool op het huidige stukje band met het symbool dat we in
.configurationhebben staan. - We veranderen het stukje band waarnaar we kijken op basis van
.configuration. - We veranderen de staat waarin de machine zich bevind. Daarvoor gebruiken we opnieuw
.configuration.
Bovenstaande zien we hieronder gebeuren:
def __iter__(self) -> Iterator[Move]:
return self
def __next__(self):
if self.state_i == 0:
raise StopIteration
self.scan()
self.stamp()
from_square_i = self.square_i
from_state_i = self.state_i
self.change_square()
self.change_state()
to_square_i = self.square_i
to_state_i = self.state_i
move = Move(
[bool(s) for s in self.tape],
from_square_i,
to_square_i,
from_state_i,
to_state_i
)
return move
def run(self) -> None:
for move in self:
passMerk op dat we hier ook nog een aantal dingen doen die te maken hebben met een object dat we nog niet hebben geïntroduceerd: het Move object. Dit object representeert in zekere zin een zet van de Turingmachine. Het legt vast waar we ons op de band bevonden en waar we naartoe zijn gegaan. Ook toont het in welke staat de machine zich bevond aan het begin van de zet en in welke staat aan het einde. Tot slot bevat de Move een representatie van de band aan het einde van de zet:
class Move:
def __init__(
self,
symbols: list[bool],
from_square_i: int,
to_square_i: int,
from_state_i: int,
to_state_i: int
):
self.symbols: list[bool] = symbols
self.from_square_i: int = from_square_i
self.to_square_i: int = to_square_i
self.from_state_i: int = from_square_i
self.to_state_i: int = to_state_iDeze Move objecten kunnen we later gebruiken om het hele proces wat een machine heeft doorlopen vast te leggen, maar we hebben ze niet nodig om de machine de laten draaien. Dat kunnen we al doen!
Interpretatie van de band
Voordat we naar een voorbeeld gaan kijken, is het even belangrijk om stil te staan bij wat onze Turingmachine doet en wat niet. Onze machine kan, met een aantal simpele handelingen, berekeningen uitvoeren. We geven de machine een band waar al symbolen op staan. De machine overschrijft sommige van die symbolen en de band, die we dan kunnen bekijken, bevat het resultaat van de berekening. Om de berekening te begrijpen moeten we dus de band die we geven en de band die we terug krijgen, kunnen interpreteren. We moeten er voor onszelf betekenis aan geven. Dat is een belangrijk onderdeel.
Voorbeeld
Als we kijken naar de volgende representatie van een band, zien we dat we eerst 4 keer een x hebben, vervolgens een o en daarna weer 2 keer een x:
| x | x | x | x | o | x | x |
Deze band heeft voor ons nog geen betekenis. Of het zou heel veel verschillende betekenissen kunnen hebben. Om er iets mee te kunnen moeten we er iets over afspreken. Laten we een opeenvolging van een aantal keer x zien als een getal en een enkele keer o als een soort spatie die die getallen scheidt. Hierboven zien we dus 2 getallen. Verder kunnen we afspreken dat we beginnen bij 0, dat is 1 keer een x. Dus xox betekent 0 0. 2 keer een x is 1: xxox staat dus voor 1 0. Daarna kunnen we gewoon doortellen: elke x erbij is het getal daarvoor plus 1. xxx is 2, xxxx is 3 enzovoorts. In de tabel hierboven zien we dus 3 1. ooxxxxx staat voor 4 als we de eerste o‘s negeren (er komt geen getal voor). Als we 3 en 1 bij elkaar op willen tellen kunnen we dat doen door de band te veranderen van xxxxoxx naar ooxxxx. Dat kunnen we daar onze Turingmachine laten doen!3
De machine programmeren
Om dat te bewerkstelligen hebben we een aantal staten nodig die we als programma aan de machine kunnen geven:
| Nummer van de staat | Wat doen we als we een o tegenkomen? | Wat doen we als we een x tegenkomen? |
| 1 | – Stempel o– Ga naar rechts – Ga naar staat 0 (stop!) | – stempel o– Ga naar rechts – Ga naar staat 2 |
| 2 | – Stempel x– Ga naar links – Ga naar staat 3 | – Stempel x– Ga naar rechts – Blijf in staat 2 |
| 3 | – Stempel o– Ga naar rechts – Ga naar staat 4 | – Stempel x– Ga naar links – Blijf in staat 3 |
| 4 | – Stempel o– Ga naar rechts – Ga naar staat 0 (stop!) | – Stempel o– Ga naar rechts – Ga naar staat 0 (stop!) |
Dit kunnen we vastleggen met onze objecten:
from turmac import *
tape = Tape([
Square(True),
Square(True),
Square(True),
Square(True),
Square(False),
Square(True),
Square(True),
])
program = Program([
State(Behavior(False, True, 0), Behavior(False, True, 2)),
State(Behavior(True, False, 3), Behavior(True, True, 2)),
State(Behavior(False, True, 4), Behavior(True, False, 3)),
State(Behavior(False, True, 0), Behavior(False, True, 0))
])
machine = Machine(tape, program)
machine.run()Als we nu kijken naar de band van de machine (met machine.tape), zien we dat de band is verandert in Tape([Square(False), Square(False), Square(True), Square(True), Square(True), Square(True), Square(True)]), oftewel ooxxxxx.
Dit kunnen we allemaal op een mooiere manier doen als we een extra object maken: Operator. Deze kan gebruik maken van een .from_patterns() classmethod zoals besproken bij de Square klasse. We kunnen hetzelfde als hierboven doen met het volgende:
Operator.from_patterns('xxxxoxx', ['oR0,oR2', 'xL3,xR2', 'oR4,xL3', 'oR0,oR0'])Dit geeft ons ook een manier om de zetten van de machine te tonen, maar daarvoor verwijs ik graag door naar mijn eerder genoemde repository. Het is op zich leuk om naar de output te kijken die dit extra object mogelijk maakt:
┌─┬─┬─┬─┬─┬─┬─┬─┐
4 1 │x│x│x│x│x│o│x│x│
├─┼─┼─┼─┼─┼─┼─┼─┤
State 0 ├o┤x│x│x│x│o│x│x│
State 1 │o├x┤x│x│x│o│x│x│
State 2 │o│x├x┤x│x│o│x│x│
State 3 │o│x│x├x┤x│o│x│x│
State 4 │o│x│x│x├x┤o│x│x│
State 5 │o│x│x│x│x├x┤x│x│
State 4 │o│x│x│x├x┤x│x│x│
State 3 │o│x│x├x┤x│x│x│x│
State 2 │o│x├x┤x│x│x│x│x│
State 1 │o├x┤x│x│x│x│x│x│
State 0 ├o┤x│x│x│x│x│x│x│
State 1 │o├o┤x│x│x│x│x│x│
├─┼─┼─┼─┼─┼─┼─┼─┤
5 │o│o│x│x│x│x│x│x│
└─┴─┴─┴─┴─┴─┴─┴─┘We zien hier ook welke stappen de machine heeft doorlopen: op welke stukje band doen we wat en langs welke staten gaan we. Dat is het! We hebben een objectgeoriënteerde Turingmachine gemaakt met Python.
Conclusie
Python is heel belangrijk, ook voor Data/Analytics Engineers. Objectgeoriënteerd programmeren kan een wezenlijk onderdeel uitmaken van werken met Python. Hopelijk verduidelijkt het op deze manier maken van een Turingmachine een aantal cruciale technieken op een leuke manier. We hebben gekeken naar hoe te werken met __init__, __getitem__, __iter__ en __next__. Ook hebben we een aantal eigen klassen met eigen methoden gedefinieerd en een structuur opgezet van hoe de objecten samen gebruikt kunnen worden om een Turingmachine na te maken in objectgeoriënteerde Python-code.
Bedankt voor het lezen van deze blog. Bekijk onze blog page voor meer blogs over Snowflake, dbt, Tableau, Alteryx.
Werk samen met een van onze consultants en haal meer uit je data.
Contacteer ons en we zullen je helpen.
Voetnoten
- Turing, A.M., 1936–7, “On Computable Numbers, With an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, s2–42: 230–265; correction ibid., s2–43: 544–546 (1937). ↩︎
- De Mol, Liesbeth, “Turing Machines”. https://plato.stanford.edu/entries/turing-machine. Accessed 2025-05-22. ↩︎
- Ik heb me hier in belangrijke mate laten inspireren door het online Stanford Encyclopedia of Philosphy artikel Turing Machines dat ook specifieker genoemd wordt in voetnoot 2. ↩︎