Browse Prior Art Database

Backtracking Interpreter

IP.com Disclosure Number: IPCOM000114999D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Merritt, CR: AUTHOR

Abstract

The Backtracking Interpreter is a variation of an interpreter control loop for use with a Threaded Interpreter Language (TIL). This TIL is in the form of a binary sequence of numbers that may be (loosely) viewed as an instruction set for some abstract machine.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Backtracking Interpreter

      The Backtracking Interpreter is a variation of an interpreter
control loop for use with a Threaded Interpreter Language (TIL).
This TIL is in the form of a binary sequence of numbers that may be
(loosely) viewed as an instruction set for some abstract machine.

The interpreter's execution environment is as follows:

      There exists a single-dimension array of pointers (entry point
addresses) to a set of executable subroutines.  An interpreted
program is represented as a sequence of binary numbers (referred to
as 'opcodes').  Each opcode represents an array index value used to
select a particular entry from the subroutine array.  The interpreter
control loop uses a pointer (referred to as the 'opcode pointer')
into the sequence of opcodes to select a given opcode.  The opcode
pointer is incremented after an opcode is selected.

A high-level "meta-language" description of the interpreter control
loop follows:
      do forever;
               fetch opcode using opcode pointer;
               fetch subroutine entry point from subroutine array
                 using opcode as subroutine array index;
               increment opcode pointer;
               call selected subroutine;
      end do;

      The loop iterates forever to meet the criteria of minimum
number of steps to run an "execution thread" through the subroutines
in the subroutine array.  Since this iteration constitutes the
control of a general program that will require eventual termination,
a backtracking method was invented to break such an iteration...