Programming Languages – How Functions Are Defined

functionslanguage-designmethodsprogramming-languages

How do programming languages define and save functions/methods? I am creating an interpreted programming language in Ruby, and I am trying to figure out how to implement function declaration.

My first idea is to save the content of the declaration in a map. For example, if I did something like

def a() {
    callSomething();
    x += 5;
}

Then I would add an entry into my map:

{
    'a' => 'callSomething(); x += 5;'
}

The problem with this is that it would become recursive, because I would have to call my parse method on the string, which would then call parse again when it encountered doSomething, and then I would run out of stack space eventually.

So, how do interpreted languages handle this?

Best Answer

Would I be correct in assuming that your "parse" function not only parses the code but also executes it at the same time? If you wanted to do it that way, instead of storing the contents of a function in your map, store the location of the function.

But there's a better way. It takes a bit more effort up-front, but it yields much better results as complexity increases: use an Abstract Syntax Tree.

The basic idea is that you only parse the code once, ever. Then you have a set of data types representing operations and values, and you make a tree of them, like so:

def a() {
    callSomething();
    x += 5;
}

becomes:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(This is just a text representation of the structure of a hypothetical AST. The actual tree would probably not be in text form.) Anyway, you parse your code out into an AST, and then you either run your interpreter over the AST directly, or use a second ("code generation") pass to turn the AST into some output form.

In the case of your language, what you would probably do is have a map that maps function names to function ASTs, instead of function names to function strings.

Related Topic