How can C have no inner functions, but languages implemented in C can?

Question

I've been coding in scripting languages like Lua recently and the existence of anonymous inner functions has got me thinking. How can a language implemented with C, like Lua, have inner functions while in C, no matter what you do,you cannot escape that fact that functions must be declared well beforehand during compile time? Does this mean that in C, there is actually a way to achieve inner functions, and it's simply a matter of implementing a huge code base to make them possible?

For example

void *block = malloc(sizeof(1) * 1024); // somehow 
// write bytes to this memory address to make it operate
// like an inner function?
// is that even possible?
char (*letterFunct)(int) = ((char (*letterFunct)(int))block;
// somehow trick C into thinking this block is a function?
printf("%c\n", (*letterFunct)(5)); // call it

What is the key concept I'm missing that bridges this gap in understanding why some languages with advanced features (classes, objects, inner functions, multi threading) can be implemented in languages devoid of all of those?

Answer 1

Just because the compiler / interpreter for a particular language is written in C doesn't mean that that language has to translate into C and then get compiled.

I don't know about Lua, but in the case of Java the code is compiled to Java Byte Code, which (loosely speaking) a Java VM reads and interprets.

The original C compiler was written in assembly, and the original C++ compiler was written in C, so it's possible to write a compiler for a higher-level language in a lower-level language.

Answer 2

Closures and inner functions usualluy involve passing an extra (hidden) argument to the function that holds the environment of the closure. In C you don't have those hidden extra arguments, so to implement closures or inner functions in C, you need to make those extra arguments explicit. So to implement an "inner function" in C, you might end up with something like:

struct shared_locals {
    // locals of function shared with inner function
};

int inner_function(struct shared_locals *sl, /* other args to inner function */...) {
    // code for the inner function -- shared locals accessed va sl
}

int function(...) {
    struct shared_locals sl;  // the shared locals

    // call inner function directly
    inner_function(&sl, ...);

    // pass inner function as a callback
    func_with_callback(inner_function, &sl);
}

The above kind of code is why 'callbacks' in C code usually involve both a function pointer and an extra void * argument that is passed to the callback.

Answer 3

To implement inner functions, you need closures. To implement closures you need some more advanced mechanism of allocating local variables than just the stack. C was meant to be a lightweight language, so advanced concepts like closures and garbage collectors were excluded.

C++ is kind of extension of C that has all the advanced concepts, closures and inner functions included.

Your example with a memory block that you fill with assembler code: You can do that, but it will not be portable. It would require cooperation from operating system and from the compiler. The only portable solution I can think of would be embedding the compiler into every executable, which is again too much.

And this would still be a normal non-inner function. To implement inner functions compiled at runtime you would again need closures.

Answer 4

Lua is a program---just like any other program---you run it, it reads input, it produces output. When you run lua MyProgram.lua, the lua program reads from the file MyProgram.lua, and it writes output to the console. As with many other programs, what it spits out depends on what it read in.

The lua program is written in C.

If your MyProgram.lua file contains print("x") at top level, then when the lua program reads that line it will print x.

Note: It was lua that printed x. It wasn't really MyProgram.lua. MyProgram.lua is just a data file. The lua program reads it in, and it uses the data to decide what it's supposed to do.

When the lua program reads that line, it doesn't "translate" the line into C or into any other language. It just does what the line says to do. It prints x.

There's a name for that: We say that the lua program interprets MyProgram.lua.

Note: I lied. The lua program doesn't really do anything. The lua program is just a data file. When you type lua MyProgram.lua, the computer reads the data into memory, and then it uses the data to decide what it is supposed to do.

When we talk about a computer system, we speak at different levels of abstraction. When we say, "the computer hardware did X," we are speaking about a low level of abstraction. When we say, "MyProgram.lua did Z", we are speaking about a higher level of abstraction. And, when we say that the lua interpreter did something, we are talking about a level somewhere in-between.

In between the hardware and the end user's experience, you can find many levels of abstraction if you look deep enough.

But, back to Lua...

If your MyProgram.lua contains function p() print("y") end at top level, then the Lua program doesn't do anything with that right away. It just remembers what you wanted p() to mean. Then later, if it sees p() at top-level, then it prints y.

You could write the program that does those things (i.e., you could write Lua) in almost any language. Your choice of what language you used to implement lua might affect the internal architecture of your Lua interpreter, but it need not limit the language that your interpreter understands (i.e., the Lua language) in any way.

Answer 5

You're confusing the C source code with the binary executable. The Lua interpreter (the program that reads and runs Lua scripts) is written in C. But after it's compiled, it's not C anymore. It would behave the same if it were written in Fortran (assuming it compiled to the same binary CPU instructions).

There's no such thing as a "running C environment". There are only binary machine instructions. The CPU doesn't know C anymore than it knows French.

As far as how Lua handles inner functions, the designers of Lua sat down and figured out all of the context they would need to keep track of whenever the interpreter encounters an inner function, and wrote the code to assemble and keep track of that context for as long as the inner function is viable. The inner function is a specifically Lua construct -- it has nothing to do with C, because when the Lua interpreter is running, there is no C anywhere.