Implementing goto in an ast

Question

Background: As a short project over winter break, I'm trying to implement a programming language called Axe (designed for graphing calculators) using Python and PLY. A brief note: the language allows only global variables and makes heavy use of pointers.

I'm trying to implement goto in this language, but have no idea how to do it.

My general method is to first use PLY to parse the code into an ast, then walk through it executing as I go.

For example, the statement

If 3
    Disp 4
    Disp 6
End

...would turn into...

['PROGRAM', 
  ['BLOCK', 
    ['IF', 
      ['CONDITION', 3], 
      ['BLOCK', 
        ['DISP', 4], 
        ['DISP', 6]
      ]
    ]
  ]
]

...which I would execute recursively (I added indents for readability).

Because the ast is a tree, I'm not sure how to jump between different nodes. I've considered perhaps converting the tree to a flat-ish array ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]] so that I can use the indices of the flat-ish array to go to specific lines in the code, but this seems to lack a certain elegance and almost feels like a step backwards (although I could be wrong).

I've looked at this, but was unable to understand how it worked.

Any help or hints would be appreciated.

Oatis

"Jump"? What do you think you mean by "Jump"? Why would you "jump" between nodes? Please provide a specific example where you would "jump" to an arbitrary node. It's difficult to find a sensible need for a jump in a tree-based language. – Sucre

The language I'm choosing to implement has goto statements in it. I wanted to match the spec, which is why I need goto. I made this tree-based because it seemed like a sensible thing to do at the time. I'm guessing that was a mistake: what other forms of languages are there? – Oatis

AXE really requires a GOTO? Seems odd. There an infinite number of "forms" of languages: procedural, functional, etc., etc. Among procedural languages, Python and Java (among others) have no GOTO. It's a pretty rare thing. – Sucre

AST is good at compiling, not at evaluation. Except goto there are other problem - loops. How you want to implement loops without some sort of program counter? – Heddi

It's a low level language. Also, I implemented loops earlier by using a 'while' loop. – Oatis

Answer 1

"execute recursively" doesn't fit well with goto. For goto to work, you need a PC, a "program counter" and each statement in your program must have a distinct address. As it is executed, the address of each statement is assigned to the PC. When goto is encountered, the target address of the goto (it's argument) is put into the PC and the execution resumes from there.

This is almost impossible to achieve with a stack-based, recursive approach. You have two options:

• Flatten your AST into a sequence where you can assign a distinct address to each statement

• Add a "skip" mode to your interpreter. When goto is encountered, throw a GotoException which breaks out of all of the stack frames and goes back to the root. Process statements (skip them without executing) until you reach the target address.

I think you can imagine that this implementation of goto isn't very performant and probably brittle to implement.

Bosom

Ok, thanks for the suggestions! I think I'm going to go with flattening the tree. – Oatis

Answer 2

I've considered perhaps converting the tree to a flat-ish array ... but this seems to lack a certain elegance and almost feels like a step backwards (although I could be wrong).

You are wrong. Machine code is always flat. Languages like C are flattened to create machine code.

A calculator (like other simple machines) is flat.

However. Flattening out your AXE syntax tree is not completely necessary.

You simply need to apply the programming source labels to each node in your tree.

Then a "GOTO" simply searches the tree for that label and resumes execution at that label.

Sucre

Ah, good point about the machine code. I guess I was wrong about that then :) – Oatis

Because machine code is flat, we don't use it often for programming nowadays. We prefer structured languages and use tools to flatten a nice, structured language into the flat world of machine execution. – Sucre

Answer 3

You can also flatten the AST to a directed graph (the control-flow graph). An example of how this can be done to produce a networkx graph that can be traversed by the interpreter can be found in the Python package promela. Note that you'll have to write some AST classes for that purpose.

Traceetracer