1#!/usr/bin/env python3
2
3# Nga: a Virtual Machine
4# Copyright (c) 2010 - 2020, Charles Childers
5# Floating Point I/O by Arland Childers, (c) 2020
6# Optimizations and process() rewrite by Greg Copeland
7# -------------------------------------------------------------
8# This implementation of the VM differs from the reference
9# model in a number of important ways.
10#
11# To aid in performance, it does the following:
12# - caching the Retro dictionary in a Python dict()
13# - replaces some Retro words with implementations in Python
14#   - s:eq?
15#   - s:length
16#   - s:to-number
17#   - d:lookup
18#
19# Each major component is managed as a separate class. We have
20# a class for each I/O device, for each stack, and for the
21# memory pool. The main VM is also in a separate class.
22#
23# It's intended that an amalgamation tool will be developed to
24# combine the separate files into a single one for deployment.
25# -------------------------------------------------------------
26
27import os, sys, math, time, struct, random, datetime
28
29
30class Clock:
31    def __getitem__(self, id):
32        import datetime
33        import time
34
35        now = datetime.datetime.now()
36        ids = {
37            "time": time.time,
38            "year": now.year,
39            "month": now.month,
40            "day": now.day,
41            "hour": now.hour,
42            "minute": now.minute,
43            "second": now.second,
44            # No time_utc?
45            "year_utc": now.utcnow().year,
46            "month_utc": now.utcnow().month,
47            "day_utc": now.utcnow().day,
48            "hour_utc": now.utcnow().hour,
49            "minute_utc": now.utcnow().minute,
50            "second_utc": now.utcnow().second,
51        }
52        return ids[id]
53
54
55import random
56
57
58class RNG:
59    def __call__(self):
60        return random.randint(-2147483647, 2147483646)
61
62
63import os
64
65
66class FileSystem:
67    def __init__(self):
68        self.files = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
69
70    def open(self, params):
71        name, mode = params
72        slot = 0
73        i = 1
74        while i < 8:
75            if self.files[i] == 0:
76                slot = i
77            i += 1
78        if slot > 0:
79            if mode == 0:
80                if os.path.exists(name):
81                    self.files[slot] = open(name, "r")
82                else:
83                    slot = 0
84            elif mode == 1:
85                self.files[slot] = open(name, "w")
86            elif mode == 2:
87                self.files[slot] = open(name, "a")
88            elif mode == 3:
89                if os.path.exists(name):
90                    self.files[slot] = open(name, "r+")
91                else:
92                    slot = 0
93        return slot
94
95    def read(self, slot):
96        return ord(self.files[slot].read(1))
97
98    def write(self, params):
99        slot, char = params
100        self.files[slot].write(chr(stack.pop()))
101        return 1
102
103    def close(self, slot):
104        self.files[slot].close()
105        self.files[slot] = 0
106        return 0
107
108    def pos(self, slot):
109        return self.files[slot].tell()
110
111    def seek(slot, pos):
112        return self.files[slot].seek(pos, 0)
113
114    def size(self, slot):
115        at = self.files[slot].tell()
116        self.files[slot].seek(0, 2)  # SEEK_END
117        end = self.files[slot].tell()
118        self.files[slot].seek(at, 0)  # SEEK_SET
119        return end
120
121    def delete(self, name):
122        name = extract_string(stack.pop())
123        i = 0
124        if os.path.exists(name):
125            os.remove(name)
126            i = 1
127        return i
128
129
130class FloatStack(object):
131    def __init__(self, *d):
132        self.data = list(d)
133
134    def __getitem__(self, id):
135        return self.data[id]
136
137    def add(self):
138        self.data.append(self.data.pop() + self.data.pop())
139
140    def sub(self):
141        self.data.append(0 - (self.data.pop() - self.data.pop()))
142
143    def mul(self):
144        self.data.append(self.data.pop() * self.data.pop())
145
146    def div(self):
147        a, b = self.data.pop(), self.data.pop()
148        self.data.append(b / a)
149
150    def ceil(self):
151        self.data.append(math.ceil(self.data.pop()))
152
153    def floor(self):
154        self.data.append(math.floor(self.data.pop()))
155
156    def eq(self):
157        return 0 - (self.data.pop() == self.data.pop())
158
159    def neq(self):
160        return 0 - (self.data.pop() != self.data.pop())
161
162    def gt(self):
163        a, b = self.data.pop(), self.data.pop()
164        return 0 - (b > a)
165
166    def lt(self):
167        a, b = self.data.pop(), self.data.pop()
168        return 0 - (b < a)
169
170    def depth(self):
171        return len(self.data)
172
173    def drop(self):
174        self.data.pop()
175
176    def pop(self):
177        return self.data.pop()
178
179    def swap(self):
180        a, b = self.data.pop(), self.data.pop()
181        self.data += [a, b]
182
183    def push(self, n):
184        self.data.append(n)
185
186    def log(self):
187        a, b = self.data.pop(), self.data.pop()
188        self.data.append(math.log(b, a))
189
190    def power(self):
191        a, b = self.data.pop(), self.data.pop()
192        self.data.append(math.pow(a, b))
193
194    def sin(self):
195        self.data.append(math.sin(self.data.pop()))
196
197    def cos(self):
198        self.data.append(math.cos(self.data.pop()))
199
200    def tan(self):
201        self.data.append(math.tan(self.data.pop()))
202
203    def asin(self):
204        self.data.append(math.asin(self.data.pop()))
205
206    def acos(self):
207        self.data.append(math.acos(self.data.pop()))
208
209    def atan(self):
210        self.data.append(math.atan(self.data.pop()))
211
212
213class IntegerStack(list):
214    def __init__(self):
215        stack = [] * 128
216        self.extend(stack)
217
218    def depth(self):
219        return len(self)
220
221    def tos(self):
222        return self[-1]
223
224    def push(self, v):
225        self.append(v)
226
227    def dup(self):
228        self.append(self[-1])
229
230    def drop(self):
231        self.pop()
232
233    def swap(self):
234        a = self[-2]
235        self[-2] = self[-1]
236        self[-1] = a
237
238
239import os
240import struct
241
242
243class Memory(list):
244    def __init__(self, source, initial, size):
245        m = [0] * size
246        self.extend(m)
247        if len(initial) == 0:
248            cells = int(os.path.getsize(source) / 4)
249            f = open(source, "rb")
250            i = 0
251            for cell in list(struct.unpack(cells * "i", f.read())):
252                self[i] = cell
253                i = i + 1
254            f.close()
255        else:
256            i = 0
257            for cell in initial:
258                self[i] = cell
259                i = i + 1
260
261    def load_image(self, name):
262        cells = int(os.path.getsize(name) / 4)
263        f = open(name, "rb")
264        i = 0
265        for cell in list(struct.unpack(cells * "i", f.read())):
266            self[i] = cell
267            i = i + 1
268        f.close()
269
270    def size(self):
271        return len(self)
272
273
274InitialImage = []
275
276
277class Retro:
278    def map_in(self, name):
279        return self.memory[self.find_entry(name) + 1]
280
281    def __init__(self):
282        self.ip = 0
283        self.stack = IntegerStack()
284        self.address = IntegerStack()
285        self.memory = Memory("ngaImage", InitialImage, 1000000)
286        self.clock = Clock()
287        self.rng = RNG()
288        self.files = FileSystem()
289        self.floats = FloatStack()
290        self.afloats = FloatStack()
291        self.Dictionary = self.populate_dictionary()
292        self.Cached = self.cache_words()
293
294        self.setup_devices()
295        self.instructions = [
296            self.i_nop,
297            self.i_lit,
298            self.i_dup,
299            self.i_drop,
300            self.i_swap,
301            self.i_push,
302            self.i_pop,
303            self.i_jump,
304            self.i_call,
305            self.i_ccall,
306            self.i_return,
307            self.i_eq,
308            self.i_neq,
309            self.i_lt,
310            self.i_gt,
311            self.i_fetch,
312            self.i_store,
313            self.i_add,
314            self.i_subtract,
315            self.i_multiply,
316            self.i_divmod,
317            self.i_and,
318            self.i_or,
319            self.i_xor,
320            self.i_shift,
321            self.i_zreturn,
322            self.i_halt,
323            self.i_ienumerate,
324            self.i_iquery,
325            self.i_iinvoke,
326        ]
327
328    def div_mod(self, a, b):
329        x = abs(a)
330        y = abs(b)
331        q, r = divmod(x, y)
332        if a < 0 and b < 0:
333            r *= -1
334        elif a > 0 and b < 0:
335            q *= -1
336        elif a < 0 and b > 0:
337            r *= -1
338            q *= -1
339        return q, r
340
341    def cache_words(self):
342        Cached = dict()
343        Cached["interpreter"] = self.map_in("interpret")
344        Cached["not_found"] = self.map_in("err:notfound")
345        Cached["s:eq?"] = self.map_in("s:eq?")
346        Cached["s:to-number"] = self.map_in("s:to-number")
347        Cached["s:length"] = self.map_in("s:length")
348        Cached["d:lookup"] = self.map_in("d:lookup")
349        Cached["d:add-header"] = self.map_in("d:add-header")
350        return Cached
351
352    def populate_dictionary(self):
353        Dictionary = dict()
354        header = self.memory[2]
355        while header != 0:
356            named = self.extract_string(header + 3)
357            if not named in Dictionary:
358                Dictionary[named] = header
359            header = self.memory[header]
360        return Dictionary
361
362    def find_entry(self, named):
363        if named in self.Dictionary:
364            return self.Dictionary[named]
365
366        header = self.memory[2]
367        Done = False
368        while header != 0 and not Done:
369            if named == self.extract_string(header + 3):
370                self.Dictionary[named] = header
371                Done = True
372            else:
373                header = self.memory[header]
374        return header
375
376    def get_input(self):
377        return ord(sys.stdin.read(1))
378
379    def display_character(self):
380        if self.stack.tos() > 0 and self.stack.tos() < 128:
381            if self.stack.tos() == 8:
382                sys.stdout.write(chr(self.stack.pop()))
383                sys.stdout.write(chr(32))
384                sys.stdout.write(chr(8))
385            else:
386                sys.stdout.write(chr(self.stack.pop()))
387        else:
388            sys.stdout.write("\033[2J\033[1;1H")
389            self.stack.pop()
390        sys.stdout.flush()
391
392    def i_nop(self):
393        pass
394
395    def i_lit(self):
396        self.ip += 1
397        self.stack.push(self.memory[self.ip])
398
399    def i_dup(self):
400        self.stack.dup()
401
402    def i_drop(self):
403        self.stack.drop()
404
405    def i_swap(self):
406        self.stack.swap()
407
408    def i_push(self):
409        self.address.push(self.stack.pop())
410
411    def i_pop(self):
412        self.stack.push(self.address.pop())
413
414    def i_jump(self):
415        self.ip = self.stack.pop() - 1
416
417    def i_call(self):
418        self.address.push(self.ip)
419        self.ip = self.stack.pop() - 1
420
421    def i_ccall(self):
422        target = self.stack.pop()
423        if self.stack.pop() != 0:
424            self.address.push(self.ip)
425            self.ip = target - 1
426
427    def i_return(self):
428        self.ip = self.address.pop()
429
430    def i_eq(self):
431        a = self.stack.pop()
432        b = self.stack.pop()
433        if b == a:
434            self.stack.push(-1)
435        else:
436            self.stack.push(0)
437
438    def i_neq(self):
439        a = self.stack.pop()
440        b = self.stack.pop()
441        if b != a:
442            self.stack.push(-1)
443        else:
444            self.stack.push(0)
445
446    def i_lt(self):
447        a = self.stack.pop()
448        b = self.stack.pop()
449        if b < a:
450            self.stack.push(-1)
451        else:
452            self.stack.push(0)
453
454    def i_gt(self):
455        a = self.stack.pop()
456        b = self.stack.pop()
457        if b > a:
458            self.stack.push(-1)
459        else:
460            self.stack.push(0)
461
462    # The fetch instruction also handles certain
463    # introspection queries.
464    #
465    # Of note is the min and max values for a cell.
466    # In most VM implementations, this is limited
467    # to 32 bit or 64 bit ranges, but Python allows
468    # an unlimited range.
469    #
470    # I report as if the cells are capped at 128 bits
471    # but you can safely ignore this if running on
472    # the Python VM. (This does have an impact on
473    # floating point values, if using the `e:` words
474    # for converting them to/from an encoded format in
475    # standard cells, but should not affect anything
476    # else in the standard system)
477
478    def i_fetch_query(self, target):
479        if target == -1:
480            self.stack.push(self.stack.depth())
481        elif target == -2:
482            self.stack.push(self.address.depth())
483        elif target == -3:
484            self.stack.push(self.memory.size())
485        elif target == -4:
486            self.stack.push(-2147483647)
487        elif target == -5:
488            self.stack.push(2147483646)
489        else:
490            raise IndexError
491
492    def i_fetch(self):
493        target = self.stack.pop()
494        if target >= 0:
495            self.stack.push(self.memory[target])
496        else:
497            self.i_fetch_query(target)
498
499    def i_store(self):
500        mi = self.stack.pop()
501        self.memory[mi] = self.stack.pop()
502
503    def i_add(self):
504        t = self.stack.pop()
505        v = self.stack.pop()
506        self.stack.push(t + v)
507
508    def i_subtract(self):
509        t = self.stack.pop()
510        v = self.stack.pop()
511        self.stack.push(v - t)
512
513    def i_multiply(self):
514        t = self.stack.pop()
515        v = self.stack.pop()
516        self.stack.push(v * t)
517
518    def i_divmod(self):
519        t = self.stack.pop()
520        v = self.stack.pop()
521        b, a = self.div_mod(v, t)
522        self.stack.push(a)
523        self.stack.push(b)
524
525    def i_and(self):
526        t = self.stack.pop()
527        m = self.stack.pop()
528        self.stack.push(m & t)
529
530    def i_or(self):
531        t = self.stack.pop()
532        m = self.stack.pop()
533        self.stack.push(m | t)
534
535    def i_xor(self):
536        t = self.stack.pop()
537        m = self.stack.pop()
538        self.stack.push(m ^ t)
539
540    def i_shift(self):
541        t = self.stack.pop()
542        v = self.stack.pop()
543
544        if t < 0:
545            v <<= t * -1
546        else:
547            v >>= t
548
549        self.stack.push(v)
550
551    def i_zreturn(self):
552        if self.stack.tos() == 0:
553            self.stack.pop()
554            self.ip = self.address.pop()
555
556    def i_halt(self):
557        self.ip = 9000000
558
559    def i_ienumerate(self):
560        self.stack.push(6)
561
562    def i_iquery(self):
563        device = self.stack.pop()
564        if device == 0:  # generic output
565            self.stack.push(0)
566            self.stack.push(0)
567        if device == 1:  # floating point
568            self.stack.push(1)
569            self.stack.push(2)
570        if device == 2:  # files
571            self.stack.push(0)
572            self.stack.push(4)
573        if device == 3:  # rng
574            self.stack.push(0)
575            self.stack.push(10)
576        if device == 4:  # time
577            self.stack.push(0)
578            self.stack.push(5)
579        if device == 5:  # scripting
580            self.stack.push(0)
581            self.stack.push(9)
582
583    def file_open_params(self):
584        mode = self.stack.pop()
585        name = self.extract_string(self.stack.pop())
586        return name, mode
587
588    def file_write_params(self):
589        slot = self.stack.pop()
590        char = self.stack.pop()
591        return slot, char
592
593    def setup_devices(self):
594        self.files_instr = {
595            0: lambda: self.stack.push(self.files.open(self.file_open_params())),
596            1: lambda: self.files.close(self.stack.pop()),
597            2: lambda: self.stack.push(self.files.read(self.stack.pop())),
598            3: lambda: self.files.write(self.file_write_params()),
599            4: lambda: self.stack.push(self.files.pos(self.stack.pop())),
600            5: lambda: self.files.seek(),
601            6: lambda: self.stack.push(self.files.size(self.stack.pop())),
602            7: lambda: self.files.delete(self.extract_string(self.stack.pop())),
603            8: lambda: 1 + 1,
604        }
605
606        self.rng_instr = {0: lambda: self.stack.push(self.rng())}
607
608        self.clock_instr = {
609            0: lambda: self.stack.push(int(time.time())),
610            1: lambda: self.stack.push(self.clock["day"]),
611            2: lambda: self.stack.push(self.clock["month"]),
612            3: lambda: self.stack.push(self.clock["year"]),
613            4: lambda: self.stack.push(self.clock["hour"]),
614            5: lambda: self.stack.push(self.clock["minute"]),
615            6: lambda: self.stack.push(self.clock["second"]),
616            7: lambda: self.stack.push(self.clock["day_utc"]),
617            8: lambda: self.stack.push(self.clock["month_utc"]),
618            9: lambda: self.stack.push(self.clock["year_utc"]),
619            10: lambda: self.stack.push(self.clock["hour_utc"]),
620            11: lambda: self.stack.push(self.clock["minute_utc"]),
621            12: lambda: self.stack.push(self.clock["second_utc"]),
622        }
623
624        self.float_instr = {
625            0: lambda: self.floats.push(float(self.stack.pop())),
626            1: lambda: self.floats.push(float(self.extract_string(self.stack.pop()))),
627            2: lambda: self.stack.push(int(self.floats.pop())),
628            3: lambda: self.inject_string(str(self.floats.pop()), self.stack.pop()),
629            4: lambda: self.floats.add(),
630            5: lambda: self.floats.sub(),
631            6: lambda: self.floats.mul(),
632            7: lambda: self.floats.div(),
633            8: lambda: self.floats.floor(),
634            9: lambda: self.floats.ceil(),
635            10: lambda: self.floats.sqrt(),
636            11: lambda: self.stack.push(self.floats.eq()),
637            12: lambda: self.stack.push(self.floats.neq()),
638            13: lambda: self.stack.push(self.floats.lt()),
639            14: lambda: self.stack.push(self.floats.gt()),
640            15: lambda: self.stack.push(self.floats.depth()),
641            16: lambda: self.floats.dup(),
642            17: lambda: self.floats.drop(),
643            18: lambda: self.floats.swap(),
644            19: lambda: self.floats.log(),
645            20: lambda: self.floats.pow(),
646            21: lambda: self.floats.sin(),
647            22: lambda: self.floats.cos(),
648            23: lambda: self.floats.tan(),
649            24: lambda: self.floats.asin(),
650            25: lambda: self.floats.atan(),
651            26: lambda: self.floats.acos(),
652            27: lambda: self.afloats.push(self.floats.pop()),
653            28: lambda: self.floats.push(self.afloats.pop()),
654            29: lambda: self.stack.push(self.afloats.depth()),
655        }
656
657    def i_iinvoke(self):
658        device = self.stack.pop()
659        #        print('dev:', device)
660        if device == 0:
661            self.display_character()
662        if device == 1:
663            action = self.stack.pop()
664            self.float_instr[int(action)]()
665        if device == 2:
666            action = self.stack.pop()
667            self.files_instr[int(action)]()
668        if device == 3:
669            self.rng_instr[0]()
670        if device == 4:
671            action = self.stack.pop()
672            self.clock_instr[int(action)]()
673        if device == 5:
674            action = self.stack.pop()
675            if action == 0:
676                self.stack.push(len(sys.argv) - 2)
677            if action == 1:
678                a = self.stack.pop()
679                b = self.stack.pop()
680                self.stack.push(self.inject_string(sys.argv[a + 2], b))
681            if action == 2:
682                self.run_file(self.extract_string(self.stack.pop()))
683            if action == 3:
684                b = self.stack.pop()
685                self.stack.push(self.inject_string(sys.argv[0], b))
686
687    def validate_opcode(self, I0, I1, I2, I3):
688        if (
689            (I0 >= 0 and I0 <= 29)
690            and (I1 >= 0 and I1 <= 29)
691            and (I2 >= 0 and I2 <= 29)
692            and (I3 >= 0 and I3 <= 29)
693        ):
694            return True
695        else:
696            return False
697
698    def extract_string(self, at):
699        s = ""
700        while self.memory[at] != 0:
701            s = s + chr(self.memory[at])
702            at = at + 1
703        return s
704
705    def inject_string(self, s, to):
706        for c in s:
707            self.memory[to] = ord(c)
708            to = to + 1
709        self.memory[to] = 0
710
711    def execute(self, word, notfound):
712        self.ip = word
713        if self.address.depth() == 0:
714            self.address.push(0)
715        while self.ip < 1000000:
716            if self.ip == self.Cached["s:eq?"]:
717                a = self.extract_string(self.stack.pop())
718                b = self.extract_string(self.stack.pop())
719                if a == b:
720                    self.stack.push(-1)
721                else:
722                    self.stack.push(0)
723                self.ip = self.address.pop()
724            elif self.ip == self.Cached["d:lookup"]:
725                name = self.extract_string(self.stack.pop())
726                header = self.find_entry(name)
727                self.stack.push(header)
728                self.memory[self.Cached["d:lookup"] - 20] = header  # "which"
729                self.ip = self.address.pop()
730            elif self.ip == self.Cached["s:to-number"]:
731                n = self.extract_string(self.stack.pop())
732                self.stack.push(int(n))
733                self.ip = self.address.pop()
734            elif self.ip == self.Cached["s:length"]:
735                n = len(self.extract_string(self.stack.pop()))
736                self.stack.push(n)
737                self.ip = self.address.pop()
738            else:
739                if self.ip == notfound:
740                    print("ERROR: word not found!")
741                if self.ip == self.Cached["d:add-header"]:
742                    self.Dictionary[self.extract_string(self.stack[-3])] = self.memory[
743                        3
744                    ]
745                opcode = self.memory[self.ip]
746                I0 = opcode & 0xFF
747                I1 = (opcode >> 8) & 0xFF
748                I2 = (opcode >> 16) & 0xFF
749                I3 = (opcode >> 24) & 0xFF
750                if self.validate_opcode(I0, I1, I2, I3):
751                    # print("Bytecode: ", I0, I1, I2, I3, "at", self.ip)
752                    if I0 != 0:
753                        self.instructions[I0]()
754                    if I1 != 0:
755                        self.instructions[I1]()
756                    if I2 != 0:
757                        self.instructions[I2]()
758                    if I3 != 0:
759                        self.instructions[I3]()
760                else:
761                    print("Invalid Bytecode: ", opcode, "at", self.ip)
762                    self.ip = 2000000
763            if self.address.depth() == 0:
764                self.ip = 2000000
765            self.ip = self.ip + 1
766        return
767
768    def run(self):
769        done = False
770        while not done:
771            line = input("\nOk> ")
772            if line == "bye":
773                done = True
774            else:
775                for token in line.split():
776                    self.inject_string(token, 1024)
777                    self.stack.push(1024)
778                    self.execute(self.Cached["interpreter"], self.Cached["not_found"])
779
780    def run_file(self, file):
781        if not os.path.exists(file):
782            print("File '{0}' not found".format(file))
783            return
784
785        in_block = False
786        with open(file, "r") as source:
787            for line in source.readlines():
788                if line.rstrip() == "~~~":
789                    in_block = not in_block
790                elif in_block:
791                    for token in line.strip().split():
792                        self.inject_string(token, 1024)
793                        self.stack.push(1024)
794                        self.execute(
795                            self.Cached["interpreter"], self.Cached["not_found"]
796                        )
797
798    def update_image(self):
799        import requests
800        import shutil
801
802        data = requests.get("https://forthworks.com/retro/ngaImage", stream=True)
803        with open("ngaImage", "wb") as f:
804            data.raw.decode_content = True
805            shutil.copyfileobj(data.raw, f)
806
807    def save_image(self):
808        print("Writing {0} cells to {1}".format(self.memory[3], sys.argv[1]))
809        with open(sys.argv[1], "wb") as file:
810            j = 0
811            while j <= self.memory[3]:
812                cell = struct.unpack(
813                    "=l", struct.pack("=L", self.memory[j] & 0xFFFFFFFF)
814                )[0]
815                file.write(struct.pack("i", cell))
816                j = j + 1
817
818
819if __name__ == "__main__":
820    retro = Retro()
821    for f in sys.argv[2:]:
822        retro.run_file(f)
823    retro.save_image()
824