Welcome, guest | Sign In | My Account | Store | Cart

A Python implementation of an interpreter for the TRAC programming language developed by Calvin Mooers in the early 1960s. This implementation reconstructs Mooers' original algorithm in Python and supports only a limited number of TRAC primitives for demonstration purposes.

Python, 432 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
import sys
import unittest

BEGIN_ACTIVE_FUNC = "\x80"
BEGIN_NEUTRAL_FUNC = "\x81"
END_FUNC = "\x8f"
END_ARG = "\x8e"
SEGMENT_GAP = "\xff"

class TracError(Exception): 
    pass

def list_get(list_, index, default=""):
    try:
        return list_[index]
    except:
        return default
    
def scan_char(list_, pos):
    return list_get(list_, pos)

def scan_chars(list_, pos, n):
    chars = []
    for i in range(n):
        c = scan_char(list_, pos + i)
        if c:
            chars.append(c)
    return "".join(chars)

class Processor(object):
    def __init__(self, program=""):
        self.work = []           # workspace containing current TRAC program
        self.sp = 0              # position of scanning pointer in workspace
        self.forms = {}          # key-value storage for program variables
        self.output = ""         # last string printed to output by ps for unit testing
        self.trace = True        # flag for printing trace results of function evaluation
        self.primitives = {}     # dictionary containing bound methods for TRAC primitives
        self.initialize(program)
        
    def tn(self, args):
        self.trace = True
        return ""

    def tf(self, args):
        self.trace = False
        return ""

    def ds(self, args):
        key = list_get(args, 0)
        value = list_get(args, 1)
        self.forms[key] = value
        return ""

    def ps(self, args):
        try:
            s = list_get(args, 0)
            print s
            self.output = s
        except:
            pass
        return ""

    
    def ad(self, args):
        try:
            num1 = int(list_get(args, 0))
            num2 = int(list_get(args, 1))
            return str(num1 + num2)
        except:
            return ""
    
    def su(self, args):
        try:
            num1 = int(list_get(args, 0))
            num2 = int(list_get(args, 1))
            return str(num1 - num2)
        except:
            return ""
    
    def ml(self, args):
        try:
            num1 = int(list_get(args, 0))
            num2 = int(list_get(args, 1))
            return str(num1 * num2)
        except:
            return ""
    
    def dv(self, args):
        try:
            num1 = int(list_get(args, 0))
            num2 = int(list_get(args, 1))
            return str(num1 / num2)
        except:
            return ""

    def eq(self, args):
        try:
            s1 = list_get(args, 0)
            s2 = list_get(args, 1)
            eq_result = list_get(args, 2)
            neq_result = list_get(args, 3)
            if s1 == s2:
                return eq_result
            else:
                return neq_result
        except:
            return ""
    
    def ss(self, args):
        try:
            form_key = args.pop(0)
            form = self.forms[form_key]
            form_marked = form
            for i in range(len(args)):
                arg = args[i]
                marker = "%s%s" % (SEGMENT_GAP, chr(i))
                form_marked = form_marked.replace(arg, marker)
            self.forms[form_key] = form_marked
            form_list = []
            form_list += form_marked
            #print "ss: %s" % (form_list)
            return ""
        except:
            return ""
            
    def cl(self, args):
        try:
            form_key = args.pop(0)
            form = self.forms[form_key]
            form_processed = form
            for i in range(len(args)):
                arg = args[i]
                marker = "%s%s" % (SEGMENT_GAP, chr(i))
                form_processed = form_processed.replace(marker, arg)
            return form_processed
        except:
            return ""

    def initialize(self, program=""):
        self.forms = {}
        self.work = []
        self.reset()
        self.work += program
        self.primitives = {"ds":self.ds, \
                           "ps":self.ps, \
                           "ss":self.ss, \
                           "cl":self.cl, \
                           "ad":self.ad, \
                           "su":self.su, \
                           "ml":self.ml, \
                           "dv":self.dv, \
                           "tn":self.tn, \
                           "tf":self.tf, \
                           "eq":self.eq \
                            }
        
    def run(self):
        args = []
        handler = self.scan_next_char
        while handler:
            try:
                next_handler, args = handler(args)
            except TracError, e:
                sys.stderr.write("TracError: %s\n" % e )
                next_handler, args = self.reset, []
            handler = next_handler      
                    

    def scan_next_char(self, args):  # Rule 1
        args = []
        #self.db("scan_next_char")
        c = scan_char(self.work, self.sp)
        if c:
            if c == '(':
                handler = self.handle_begin_paren
            elif c in "\n\r\t":
                handler = self.handle_tab_return
            elif c == ',':
                handler = self.handle_comma
            elif c == '#' and scan_chars(self.work, self.sp, 2) == '#(':
                handler = self.handle_begin_active_func
            elif c == '#' and scan_chars(self.work, self.sp, 3) == '##(':
                handler = self.handle_begin_neutral_func
            elif c == '#':
                handler = self.handle_sharp_sign
            elif c == ')':
                handler = self.handle_end_paren
            else:
                args.append(c)
                handler = self.handle_char
        else:
            self.db("exit")
            print "Forms: %s" % (self.forms)
            print "Output: [%s]" % (self.output)
            handler = None
        return handler, args
     
    def handle_begin_paren(self, args): # Rule 2 
        args = []
        nested_count = 1
        chars = []
        matched = False
        del self.work[self.sp]
        c = scan_char(self.work, self.sp)
        while c and not matched:
            if c == ')':
                nested_count -= 1
                if nested_count == 0:
                    matched = True         
                    break         
            if not matched:                
                if c == '(':
                    nested_count += 1
                chars.append(c)
            self.sp += 1
            c = scan_char(self.work, self.sp)
        if matched:
            del self.work[self.sp]
        else:
            raise TracError, "%s: can't find matching end parenthesis" %("handle_begin_paren") 
        return self.scan_next_char, []
    
    def handle_tab_return(self, args):  # Rule 3
        args = []
        del self.work[self.sp]
        self.sp -= 1
        return self.inc_scan_pointer_continue, args
    
    def handle_comma(self, args):  # Rule 4
        args = []
        self.work[self.sp] = END_ARG
        return self.inc_scan_pointer_continue, args

    def handle_begin_active_func(self, args):  # Rule 5 
        args = []
        del self.work[self.sp:self.sp + 2]
        self.work.insert(self.sp, BEGIN_ACTIVE_FUNC)
        self.sp += 1
        return self.scan_next_char, args
    
    def handle_begin_neutral_func(self, args):  # Rule 6
        args = []
        del self.work[self.sp:self.sp + 3]
        self.work.insert(self.sp, BEGIN_NEUTRAL_FUNC)
        self.sp += 1
        return self.scan_next_char, args
    
    def handle_sharp_sign(self, args):  # Rule 7
        args = []
        return self.inc_scan_pointer_continue, args
        
    def handle_end_paren(self, args): # Rule 8
        #self.db("end_paren_0")
        args = []
        self.work[self.sp] = END_FUNC 
        func_begin = self.get_func_begin()
        func_result = self.eval_func(func_begin)
        func_marker = self.work[func_begin]
        args.append(func_begin)
        if func_result == "":
            handler = self.handle_null_func_result  # Rule 10
        elif func_marker == BEGIN_ACTIVE_FUNC:
            args.append(func_result)
            handler = self.handle_active_func_result  # Rule 11
        elif func_marker == BEGIN_NEUTRAL_FUNC:
            args.append(func_result)
            handler = self.handle_neutral_func_result  # Rule 12
        else:
            raise TracError, "%s: invalid func_marker" %("handle_end_paren") 
        #self.db("end_paren_1")
        return handler, args
        
    def get_func_begin(self):
        pos = self.sp - 1
        c = self.work[pos]
        while c:
            if c == BEGIN_ACTIVE_FUNC or c == BEGIN_NEUTRAL_FUNC:
                break
            pos -= 1
            if pos >= 0:
                c = self.work[pos]
            else:
                raise TracError, "%s: can't find begin function marker" %("get_func_begin") 
        return pos

    def get_func_end(self, func_begin):
        pos = func_begin
        c = self.work[pos]
        while c:
            if c == END_FUNC:
                break
            pos += 1
            c = self.work[pos]
        return pos
    
    def get_func_args(self, func_begin):
        args = []
        cur_arg = []
        pos = func_begin
        c = self.work[pos]
        db = []
        while c:
            db.append(c)
            if c == BEGIN_ACTIVE_FUNC or c == BEGIN_NEUTRAL_FUNC:
                pass
            elif c == END_ARG or c == END_FUNC:
                arg = "".join(cur_arg)
                args.append(arg)
                cur_arg = []
            else:
                cur_arg.append(c)    
            if c != END_FUNC:
                pos += 1
                c = self.work[pos]   
                db = []
            else:
                break
        return args
    
    def eval_func(self, func_begin):
        result = ""
        try:
            args = self.get_func_args(func_begin)
            func_name = args[0]
            primitive = self.primitives.get(func_name, None)
            if primitive:
                result = primitive(args[1:])
                if self.trace:
                    print "eval_func: %s %s -> [%s]" % (func_name, args[1:], result)
        except Exception, e:
            raise TracError, "%s: failed - %s" %("eval_func", e) 
        return result
    
    def handle_char(self, args):  # Rule 9
        c = args[0]
        args = []
        return self.inc_scan_pointer_continue, args
    
    def handle_null_func_result(self, args):  # Rule 10
        return self.handle_func_cleanup, args
    
    def handle_active_func_result(self, args):  # Rule 11 
        func_begin = args[0]
        func_result = args[1]
        args = []
        self.work[self.sp+1:self.sp+1] += func_result
        args.append(func_begin)
        #self.db("handle_active_func_result")
        return self.handle_func_cleanup, args
         
    def handle_neutral_func_result(self, args):  # Rule 12
        func_begin = args[0]
        func_result = args[1]
        args = []
        self.work[self.sp+1:self.sp+1] += func_result
        func_end = self.sp
        del self.work[func_begin:func_end + 1]
        self.sp = func_begin + len(func_result) - 1
        #self.db("handle_neutral_func_result")
        return self.inc_scan_pointer_continue, args
    
    def handle_func_cleanup(self, args):  # Rule 13
        if args:
            func_begin = args[0]
            func_end = self.get_func_end(func_begin)
            args = []
            del self.work[func_begin:func_end + 1]
            self.sp = func_begin - 1
        #self.db("handle_func_cleanup")
        return self.inc_scan_pointer_continue, args
    
    def reset(self, args=[]):  # Rule 14
        args = []
        self.work = []
        self.sp = 0
        return self.scan_next_char, args
    
    def inc_scan_pointer_continue(self, args):  # Rule 15
        args = []
        self.sp += 1
        return self.scan_next_char, args
    
    def db(self, msg="db"):
        print "%s: %s SP:%d %s" % (msg, self.work[0:self.sp], self.sp, self.work[self.sp:])       


class TestTrac(unittest.TestCase):
        
    def setUp(self):
        pass
        
    def __test(self, program, output):
        self.processor = Processor()
        self.processor.initialize(program)
        self.processor.run()
        self.assertEqual(self.processor.output, output)

    def test_1_ps(self):
        self.__test("#(ps,Hello world)", "Hello world")

    def test_2_equal(self):
        self.__test("#(ps,#(eq,Cat,Cat,equal,not equal))", "equal")

    def test_3_not_equal(self):
        self.__test("#(ps,#(eq,Cat,Dog,equal,not equal))", "not equal")

    def test_4_ds(self):
        self.__test("#(ds,AA,Cat)#(ps,#(cl,AA))", "Cat")

    def test_5_protect_parens(self):
        self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,(#(cl,BB)))", "#(cl,BB)")

    def test_6_neutral_func(self):
        self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,##(cl,BB))", "#(cl,AA)")

    def test_7_indirection(self):
        self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,#(cl,BB))", "Cat")

    def test_8_ss(self):
        self.__test("#(ds,AA,Hello X)#(ss,AA,X)#(ps,#(cl,AA,world))", "Hello world")

    def test_9_factorial(self):
        self.__test("""
#(ds,Factorial,(#(eq,X,1,1,(#(ml,X,#(cl,Factorial,#(su,X,1)))))))
#(ss,Factorial,X)
#(ps,#(cl,Factorial,5))
""", "120")


if __name__ == "__main__":
    print __file__
    unittest.main()

TRAC is a functional language based on strings similar in capability and appearance to LISP. I first read about TRAC in Ted Nelson's epochal "Computer Lib" book. Nelson recommended TRAC as an excellent programming language for beginners, because of its simplicity, and for advanced programmers, because of its flexibility.

TRAC's creator, Calvin Mooers, was a computing pioneer who in 1962 envisioned something he called the "reactive typewriter" which foreshadowed the personal computer. The TRAC language was to be the basis for the software supporting the reactive typewriter. A person skilled in TRAC could interact with a computer from the command line to store and retrieve information, run other programs, and write additional programs.

Peter Deutsch, of Xerox Parc and Sun fame, programmed the debut version of TRAC in PDP-1 assembler. It ran in a user space of 4K 18-bit words with 2K to spare. TRAC had something of a cult following in those early days, but as memory became plentiful and the competition between languages sharpened, TRAC lost traction. Calvin Mooers died in 1994 and since then TRAC has all but vanished.

In this recipe I reconstruct a TRAC interpreter based on Mooers' written description of that PDP-1 version in his ACM paper: "TRAC, A Procedure-Describing Language for the Reactive Typewriter" (1964). The largest web cache of materials on TRAC can be found at http://www.scribd.com/people/documents/73641-trac-fan. I also referred to the TRAC chapter in "Etudes for Programmers" (out of print) by Charles Wetherell and used some of his TRAC code examples as test cases in my unit testing.

By today's standards, the programming specification of TRAC is clumsy -- relying extensively on gotos for instance . But it is remarkable how much functionality Mooers and Deutsch squeezed out of one buffer, a pointer, and a handful of special characters and markers plus a minimal amount of code to support a real computer language.

Mooers specified the TRAC algorithm in terms of 15 rules. Each rule acts on the buffer and the scan pointer, then concludes literally with "Go to rule X." I wrote a handler for each rule and simulated the gotos by having each handler return its next handler and arguments to the command loop. (However, I didn't go so far as to make everything global. Except for some buffer utilities, I encapsulate the interpreter into the Processor class.)

The basic action of a TRAC interpeter is to scan incoming characters for functions, marked by begin and end parentheseses with interior arguments delimited by commas, in which the first argument is the name of a primitive function. The characters to be scanned are called the active string. The characters that have been processed are called the neutral string. In my implementation the neutral string and the active string are the left and right sides of buffer while the scan pointer points to the division between the two strings.

As each character from the active string is scanned, it is either deleted or moved to the neutral string. When an end parenthesis is scanned and a new function is complete, the function is evaluated then deleted from the neutral string, and its result is either placed on the neutral string, where the result becomes an argument for the next function, or it is placed back on the active string to be scanned again.

Compared to the complex workings of most programming languages, TRAC's mechanism is simple but with it almost anything can be accomplished.

It would be interesting to rewrite this interpreter with modern techniques and to implement the rest of the primitives, as well as to set up TRAC to run interactively. Here I implemented just enough of the primitives to validate TRAC processing and to run a small TRAC program which computes the factorial of 5.

1 comment

Nat Kuhn 8 years, 4 months ago  # | flag

I started programming with Trac at age 10, in 1968, on a PDP-8 with 4K of 12-bit words; I posted some reminiscences at http://nats-tech.blogspot.com/2013/07/the-land-of-trac.html

I just learned Python, and your post inspired me to finally write a "Trac processor" (interpreter); I did use modern techniques, implement the primitives, and make it interactive. I posted it on GitHub, at https://github.com/natkuhn/Trac-in-Python. (I didn't see your other implementations until after I'd finished).

Thanks for launching me on an interesting adventure!

Nat Kuhn