Code snippets, ideas and events from IT related projects

Zakres tematyczny posta

Kod źródłowy pisany jest w języku/formie pozwalającej programiście na szybkie i eleganckie rozwiązanie problemu (języki wysokiego poziomu, jak C, Erlang, czy też mnemoniczny zapis asemblera). Kod taki jest nieprzydatny dla maszyny, gdyż zawiera abstrakcyjne konstrukcje, musi więc zostać przetłumaczony do prostszej/innej postaci - temu służą kompilatory. Efektem jest kod, który maszyna może wykonać (kod maszynowy, kod pośredni).

Wspomnianą maszyną może być komputer, może to być też aplikacja potrafiąca wykonać instrukcje skompilowanego programu. Taka aplikacja nosi nazwę maszyny wirtualnej (VM), a jej implementacji poświęcony jest ten post. Druga część poświęcona zostanie projektowi i implementacji własnego języka programowania (już niedługo - właśnie kończę:)).

Koncepcja, jak ma działać opisywana tu maszynka powstała drogą analizy kompilacji przykładowych kodów źródłowych w C do asemblera, stąd całość jest mało abstrakcyjna, a bardziej przypomina właśnie sprzętowy twór.

VM jest w pełni sprawna, a na końcu notki podane są przykłady programów, które może wykonać. Przed napisaniem posta wykonałem kilka prototypów (C, Erlang, Python), finalny napisałem w Pythonie - znam go w miarę dobrze i szybko się w nim pisze ale mam zamiar kiedyś przepisać kod do Erlanga.

Zasada działania

Program wykonywany przez VM składa się z procedur, każda z nich oznaczona jest etykietą, oznaczony jest również jej koniec. Wykonywanie programu zaczyna się od procedury oznaczonej etykietą main. Z każdej można skoczyć do każdej i wrócić po jej skończeniu. Procedura może mieć argumenty wejściowe (dowolna ilość) i zwracać wyniki (dowolna ilość).

Kluczem hasha labels jest nazwa etykiety, a wartością numer linijki. Wyliczane jest to raz, po uruchomieniu programu (CALL, JZ). Zmienna ip (instruction pointer) określa numer aktualnie wykonywanej linijki.

Odpowiednikiem sprzętowego stosu w CPU jest data_stack. Tablica variables przechowuje zmienne, dodatkowe pola, razem z zmienną vsp pozwalają usuwać zmienne, do które wyszły z zasięgu oraz odkładać zawartość zmiennych podczas skoku do innej procedury. Stos functions zawiera ip z których skoczyliśmy do procedury, tak, by po osiągnięciu jej końca można było wrócić do poprzedniej. Służy to też zatrzymaniu działania aplikacji po zakończeniu głownej procedury.

   1  import re
   2  import sys
   3  from instructiondecoder import InstructionDecoder
   4  from alu import ALU
   5  
   6  class VirtualMachine:
   7      def __init__(self):
   8          self.ins_dec = InstructionDecoder()
   9          self.alu = ALU()
  10          self.data_stack = []
  11          self.variables = []
  12          self.instructions = []
  13          self.functions = []
  14          self.labels = {} # label -> instruction index
  15          self.ip = 0 # instruction pointer
  16          self.vsp = 0 # base variable stack pointer
  17          self.commands = {
  18              'push':  lambda args: self._push(args),
  19              'load':  lambda args: self._load(args),
  20              'store': lambda args: self._store(args),
  21              'jz':    lambda args: self._jump_if_zero(args), 
  22              'call':  lambda args: self._call(args),
  23              'ret':   lambda args: self._return(args),
  24              'int':   lambda args: self._interrupt(args)
  25          }
  26  
  27      def run(self, program):
  28          self.instructions = program
  29          self.get_labels()
  30          self.ip = self.labels['main']+1
  31          self.variables.append(0)
  32          self.vsp = 0
  33          self.functions.append(-1)
  34          self._move_to_next_instruction()
  35  
  36      def get_labels(self):
  37          islabel = re.compile(r"[a-z][a-z0-9]*:")
  38          index = 0
  39          for instruction in self.instructions:
  40              if islabel.match(instruction):
  41                  instruction = instruction[:-1] # remove ':'
  42                  self.labels[instruction] = index
  43              index+=1
  44  
  45      def _move_to_next_instruction(self):
  46          instruction = self.instructions[self.ip]
  47          parts = self.ins_dec.get_instruction_parts(instruction)
  48          if parts:
  49              self._instruction_execute(parts[0], parts[1:]) 
  50          if self.ip > -1:
  51              self.ip+=1
  52              self._move_to_next_instruction()
  53  
  54      def _instruction_execute(self, command, args):
  55          # labels can't be executed, they only point places in code
  56          if re.compile(r"[a-z][a-z0-9]*:").match(command):
  57              return
  58          alu_mnem = self.alu.get_mnemonics() 
  59          if re.compile(alu_mnem).match(command):
  60              self.alu.execute(command, self.data_stack)
  61          else:
  62              self.commands[command](args)
  63  
  64      def _call(self, argumments):
  65          (label) = (argumments[0])
  66          self.functions.append(self.ip)
  67          self.ip = self.labels[label]
  68          self.variables.append(self.vsp)
  69          self.vsp = len(self.variables)
  70  
  71      def _return(self, argumments):
  72          self.ip = self.functions.pop()
  73          self.vsp = self.variables[self.vsp-1]
  74  
  75      def _interrupt(self, argumments):
  76          (interrupt_id) = (argumments[0])
  77          if int(interrupt_id)==0:
  78              print '-> %s' % self.data_stack.pop()
  79          elif int(interrupt_id)==1:
  80              v = int(sys.stdin.readline())
  81              self.data_stack.append(v)
  82  
  83      def _push(self, argumments):
  84          (value) = (argumments[0])
  85          self.data_stack.append(value)
  86  
  87      def _store(self, argumments):
  88          (index) = (argumments[0])
  89          index = int(index)
  90          val = self.data_stack.pop()
  91          if index+self.vsp+1 > len(self.variables):
  92               self.variables.append(val)
  93          else:
  94              self.variables[index+self.vsp]=val
  95  
  96      def _load(self, argumments):
  97          (index) = (argumments[0])
  98          index = int(index) #+ self.vsp
  99          self.data_stack.append(self.variables[index+self.vsp])
 100  
 101      def _jump_if_zero(self, argumments):
 102          (label) = (argumments[0])
 103          if int(self.data_stack.pop())==0:
 104              self.ip = self.labels[label]
 105  

Dekoder instrukcji oparty jest o automat skończony. W prezentowanym tu rozwiązaniu można zrezygnować z maszyny stanów (np. na rzecz wyrażeń regularnych), lecz jej wykorzystanie zapewnia dużą elastyczność i łatwy rozwój. Każdą taką maszynę charakteryzuje tabela przejść (którą można zaprezentować jako graf, lecz to jest IMHO trudniejsze w analizie). Modyfikacją standardowego algorytmu jest tutaj dodanie dla każdego przejścia jednej z poniższych czynności:

• porcja danych (w naszej VM znak ASCII) dokładna jest do buforu (oznaczymy jako ↓)
• zawartość buforu przenoszona jest do listy przetworzonych wartości (oznaczymy jako ↑)
• nic

Przy poprawnej tabeli stanów oraz poprawnie przyporządkowanych czynności każdemu z przejść trafimy do stanu błąd (tu nie zaimplementowany, pewnie kod się po prostu ordynarnie posypie) lub do stanu koniec, a w liście przetworzonych wartości będziemy mieli części mnemonika. Przykładowo z load 0 będziemy mieć [load, 0].

   1  import re
   2  
   3  class InstructionDecoder:
   4      def __init__(self):
   5          ''
   6  
   7      def get_instruction_parts(self, instruction):
   8          p = self._split(instruction, 0, [], '')
   9          if not p or (len(p)==1 and p[0]==''):
  10              return None
  11          return p
  12  
  13      def _split(self, instruction, state, output, buff):
  14          '''its a finite state machine, see documentation'''
  15          (char, instruction) = self._get_char(instruction)
  16  
  17          # init
  18          if state==0:
  19              # init -> number (append)
  20              if re.compile(r"[0-9]").match(char):
  21                  buff+=char
  22                  return self._split(instruction, 1, output, buff)
  23              # init -> keyword (append)
  24              if re.compile(r"[a-z]").match(char):
  25                  buff+=char
  26                  return self._split(instruction, 2, output, buff)
  27              # int -> separator (skip)
  28              if char==' ':
  29                  return self._split(instruction, 0, output, buff)
  30              # init -> end (skip)


  31              if re.compile(r"[;]").match(char) or char=='\0':
  32                  return self._split(instruction, 4, output, buff)
  33  
  34          # number
  35          if state==1:
  36              # number -> number (append)
  37              if re.compile(r"[0-9.]").match(char):
  38                  buff+=char
  39                  return self._split(instruction, 1, output, buff)
  40              # number -> separator (flush)
  41              if char==' ':
  42                  output.append(buff)
  43                  buff=''
  44                  return self._split(instruction, 3, output, buff)
  45              # number -> end (skip)
  46              if re.compile(r"[;]").match(char) or char=='\0':
  47                  return self._split(instruction, 4, output, buff)
  48           
  49          # keyword
  50          if state==2:
  51              # keyword -> keyword (append)
  52              if re.compile(r"[a-z:]").match(char):
  53                  buff+=char
  54                  return self._split(instruction, 2, output, buff)
  55              # keyword -> number (append)
  56              if re.compile(r"[0-9]").match(char):
  57                  buff+=char
  58                  return self._split(instruction, 2, output, buff)
  59              # keyword -> separator (flush)
  60              if char==' ':
  61                  output.append(buff)
  62                  buff=''
  63                  return self._split(instruction, 0, output, buff)
  64              # keyword -> end (skip)
  65              if re.compile(r"[;]").match(char) or char=='\0':
  66                  return self._split(instruction, 4, output, buff)
  67  
  68          # separator
  69          if state==3:
  70               # separator -> number (apped)
  71               if re.compile(r"[0-9]").match(char):
  72                  buff+=char
  73                  return self._split(instruction, 1, output, buff)
  74               # separator -> keyword (append)
  75               if re.compile(r"[a-z]").match(char):
  76                  buff+=char
  77                  return self._split(instruction, 2, output, buff)
  78  
  79          # end
  80          if state==4:
  81              output.append(buff)
  82              return output
  83  
  84      def _get_char(self, instruction):
  85          if not instruction:
  86              return ('\0', '\0')
  87          char = instruction[0]
  88          if len(instruction)>1:
  89              instruction = instruction[1:]

  90          else:
  91              instruction = '\0'
  92          return (char, instruction)
  93  

Zadaniem ALU jest obsługa operacji arytmetycznych oraz logicznych. Zarówno dane jak i wyniki zapisywane są na stosie.

   1  class ALU:
   2      def __init__(self):
   3          self.commands = { 
   4              # s means stack
   5              'add':   lambda s: self._math_opr(lambda a,b: b+a, s),
   6              'sub':   lambda s: self._math_opr(lambda a,b: b-a, s),
   7              'mul':   lambda s: self._math_opr(lambda a,b: b*a, s),
   8              'div':   lambda s: self._math_opr(lambda a,b: b/a, s),
   9              'and':   lambda s: self._math_opr(lambda a,b: b&a, s),
  10              'or':    lambda s: self._math_opr(lambda a,b: b|a, s),
  11              #'lshr':  lambda s: self._math_opr(lambda a,b: b<<a, s),
  12              #'rshr':  lambda s: self._math_opr(lambda a,b: b>>a, s),
  13          }
  14  
  15      def get_mnemonics(self):
  16          ans = ''
  17          for k in self.commands:
  18              ans += '%s|' % k
  19          return '(' + ans[:-1] + ')'  # [:-1] removes last '|' sign 
  20  
  21      def execute(self, command, stack):
  22          self.commands[command](stack)
  23  
  24      def _math_opr(self, operation, stack):
  25          a = stack.pop()
  26          b = stack.pop()
  27          result = operation(float(a), float(b))
  28          stack.append(result)
  29  

Dokumentacja

Instalacja oraz uruchomienie

Do uruchomienia konieczny jest interpreter Pythona. W linii poleceń uruchamiamy skrypt main.py, jako parametr podając ścieżkę do kodu, który ma być wykonany.

Przykładowe kody źródłowe

main:
    int 1
    call square
    int 0
ret

square:
    store 0
    load 0
    load 0
    mul
    load 0
    mul
ret

rgawron@vk1004:/tmp/vm$ ./main.py cube.asm 
3
-> 27.0

Program wypisujący n (n=17) liczb Fibonacciego. Liczby te określa ciąg:

F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2)

Dla przejrzystości kodu nie wypisywany jest zerowy element. Jak trzeba przerobić kod by zamiast 17 wyświetlana była ilość liczb podawana przez usera (odczytywana z klawiatury)?

; foo(x(n-1), x(n-2), n)
fib:
    ; x(n-1)
    store 0
    ; x(n-2)
    store 1
    ; n
    store 2

    ; print x(n-1)
    load 0
    int 0
    ; n = n - 1
    load 2
    push 1
    sub
    store 2
    ; if n equival 0 return
    load 2
    jz a00
    ; assign new n value    
    load 2
    ; assign x(n-2) as x(n-1)
    load 0
    ; count x(n-1)
    load 0
    load 1
    add
    ; count nex element
    call fib
    ; never been here 
a00:
    ; empty
ret

main:
    push 17
    push 0
    push 1
    call fib; foo(1,1,17)
ret

rgawron@vk1004:/tmp/vm$ ./main.py ./fib.asm 
-> 1
-> 1.0
-> 2.0
-> 3.0
-> 5.0
-> 8.0
-> 13.0
-> 21.0
-> 34.0
-> 55.0
-> 89.0
-> 144.0
-> 233.0
-> 377.0
-> 610.0
-> 987.0
-> 1597.0

Poniżej zaprezentowany jest program, w którym procedura foo może przyjmować dowolną ilość argumentów.

foo:
a00:
    store 0
    load 0
    jz a01

    int 0

    load 0
    push 1
    sub

    push 0
    jz a00
a01:
    ; empty
ret

main:
    push 11
    push 31
    push 2
    call foo

    push 100
    push 1000
    push 1
    push 3
    call foo

    push 0
    call foo
ret

rgawron@foo:~/fire/vm$ ./main.py free.asm
-> 31
-> 11
-> 1
-> 1000
-> 100

Bardziej skomplikowane przykłady będą w następnym poście poświęconym nowemu językowi programowania, który będzie kompilowany do tego asemblera. Inny kod prostej maszyny wirtualnej można znaleźć na blogu Indefinite Studies.

Materiały do pobrania

Link do źródeł maszyny wirtualnej oraz w/w przykładowych programów.