Lambda the Ultimate

I have learned a few things from CTM, but in order to get further I feel like I need to get my head wrapped around the OZ language that the examples are presented in. Maybe I'm just lazy, but am looking for that "ah-ha" moment with a bit lighter reading (although I do agree that CTM is very well written). I'll start looking through the other texts that you mentioned.
an overwhelmingly key point you did not demonstrate was lexical scoping of open variables in the function body: we call this a closure,
Yep, I forgot about scoping issues. What I've done in my language, 2e, is as follows:
A function is defined by specifying "@name(expression)", where expression is any amount of code. This not only assigns the expression to the given name, so it can be called like a C function "name(p1, p2, ...)" but the definition also returns a value that can be assigned or called. Now anonymous functions have two forms: "@@(expression)" and "@(expression)". They can both be assigned to a variable or array element, but the second form has its variables in the same scope as the parent function. So in that sense, you can do closures (I think). Like this:

addfunc = @($1 + $2);
add5 = @(addfunc($1, 5));

result = add5(7)   #result should be equal to "12"

In this case, the "add5()" function closes over the "addfunc()" function. This is the example that I've seen in other discussions on closures, hopefully I've got it right. If anyone wants to try out some variations, I've uploaded the latest version of my language to lang2e.sourceforge.net -- version 0.9. If I have got closures correct, then I'm going to go for continuations next (or at least get enough in so I can implement co-routines as described by Knuth).

BTW, one weakness that I've got is that all variables in my functions are "static". So you can use recursion, but it is a bit tricky with variables getting clobbered (I've got code samples to show how to work around this). And another weakness is that I haven't done anything with tail call optimization yet. I've figured out an easy way to do it, just got to get time to test it is all.

Thanks for the reading list, it looks like I've got some (fun) work ahead of me.

BTW, one weakness that I've got is that all variables in my functions are "static".

If all your variables are global, and your syntax has no way to refer to outer function arguments either (which seems to be the case), then you don't have closures. For the same reason, C does not have closures. Closures are an implementation technique for accessing variables (including function arguments) that are local, but to some enclosing scope.

So your example does not exhibit closures. Here it is in lambda-calculus notation:

add = \(x,y).x+y
add5 = \x.add(x,5)
result = add5(7)

You witness closures when you are able to express it like this:

add = \x.(\y.x+y)
add5 = add(5)     -- closes over x
result = add5(7)

Of course, this is a rather boring example. It becomes more interesting if the add function actually does something before returning the inner function, e.g.:

add = \x.(let y = some_f(x); \z.y+z)

Then, some_f only gets called once, when add5 is defined. With your version you could not avoid calling it each time add5 is used.

What I mean by static variables is that within a function, variables values don't disappear after the function exits, similar to C when you use the "static" keyword to declare a variable. (This is partly do to laziness on my part in implementing the interpreter). But there are two types of functions -- one type shares variable scope with whatever function it was defined in (function definitions can be nested), and the other type has variables that are in a private scope (but they are still persistent after the function exits). Only anonymous functions defined with a single "@" symbol have shared variable scope -- ones defined with two "@@" symbols have separate scope, same with named functions. So far I don't have any syntax to get global variables (except for the fact that the names of named-functions are global).

But I can see now that this fact still doesn't help me with closures. I think I understand why I don't have closures, but will have to experiment a bit to see what it would take syntax-wise to get them. From what it appears, you have to be able to have a function with local variable scope, but also be able to attach a group of variables to it that are seen within it's scope as well as the scope of whatever function attached them to it. Kind of similar to a C++ class definition (but somewhat different)?

Kind of similar to a C++ class definition (but somewhat different)?

There is a very strong correspondence between OO style objects and closures.

I think I understand why I don't have closures, but will have to experiment a bit to see what it would take syntax-wise to get them.

You probably don't need syntax. Most languages with closures don't do anything to specially flag variables that can be captured. They typically just follow the normal block scoping conventions for the language. E.g. in the curly braced syntax of JavaScript* it looks something like this

function add(x) {
 return function(y) {
    return x + y;
 }
}

var add5 = add(5);
alert(add5(7));

At the implementation level there may very well be a difference between captured variables and non-captured variables but that doesn't mean the syntax needs to show it.

Also, one point to clarify from your original post is that anonymous lambdas aren't a prerequisite for first class functions and closures. Again, some JavaScript

function add(x) {
  function addx(y) {
    return x + y;
  }
  return addx;
}

var add5 = add(5);
alert(add5(7));

If a language has local first class named functions then anonymous lambdas are just a syntactic convenience.

* note that JavaScript doesn't really have block scoping, but the difference isn't that important for this example.

So in my languages context:

f1 = @@(
    fv1 = 123;
    f2 = @(
        print($1, fv1)
    );
    ### additional code;
    f2("foo")
)

In this case, f1() has separate namespace from the rest of the program since it is defined with two "@@" symbols. But f2() shares namespace with f1(). Therefore, the print statement when f2 is called prints "foo123". So in this sense it looks like I have closures (f1 closes over f2).
But here is where it falls apart:

some_variable = 123;
f1 = @(
    print(some_variable)
);
f2 = @@(
    some_variable = 456;
    $1()
);

### now call f2, passing f1 as it's argument
f2(f1)

In this case, the variable name "some_variable" that f1() sees is the one that was defined above it, so it prints out "123". Even when it is called from within f2(). I think that to make this useful, I should get f1 to access the variable as it is set from within f2, when it is called from there.

(Also, to make it useful, I should define a way so that named functions can get either a separate or shared namespace, just like I have for anonymous functions).

Most languages are lexically scoped by default. That just means that the meaning of a symbol is bound based on its position in the (static) code rather than when the variable is examined during the dynamic execution of the program. Assuming that in your second example you have two different variables named "some_variable" and you aren't just mutating one global variable, then lexical scoping would say that "123" is the right answer.

The alternative you propose is called dynamic scoping (again, assuming you aren't just mutating one variable). Before committing one way or the other be sure to dive into some explanations of the trade-offs involved. There's a very good reason that lexical scoping has been the far more common default for the last several decades : it's usually much easier to reason about. On the other hand, dynamic scoping does have power and even some very recent languages offer dynamically scoped variables as a non-default alternative.

I'm confused by what you are trying to accomplish with namespacing.

Right, the way the interpreter is currently implemented is each variable, when it is found by the parser, is assigned an index number into the variable storage data structure. So the variable name is combined with the function reference i.d. that it is found in, and this is used to find the variable's index. This index number is what gets loaded into the final compiled code. So lexical scoping is the most natural at the moment.

But right now I don't have any implementation for object oriented features. So as a quick fix, I thought that if a function could access the variables of a wrapper function, then that would be a way to get a form of objects. Now they would act different that C++ classes, but that also fits in with one of my goals -- by re-inventing the wheel without exactly copying what was done before, I might discover something a bit more powerful (kind of like looking at old ideas with fresh eyes).

Another idea was to emulate objects strictly through operator overloading. So far I've got a syntax that works great for using these "objects", but setting them up is a pain an non-intuitive. But I guess that is part of the learning experience.

BTW, I like your idea of defaulting to lexical scoping, and using alternate syntax to get dynamic scoping. I was thinking of something like "namespace::varname" where namespace is the name of some other function, and this will retrieve the variable from that other function ( ::varname will grab variables from the main function which is unnamed)).

So the variable name is combined with the function reference i.d. that it is found in, and this is used to find the variable's index. This index number is what gets loaded into the final compiled code.

Does that mean functions aren't reentrant? Well, I have to say that's...bold :-)

yes, even though functions have separate namespaces, if a function calls itself then the inner calling can clobber variables that may be needed once the inner loop returns. The way I get around it is to pass a counter parameter to the function, and replace any variable that needs to be preserved with an array -- using that counter parameter as an index. So,

foo(var1, 0);

@foo(
    x[$1] = something;
...
    foo(var1, $1 + 1);
    bla(x[$1]);
...
)

In this example, x is a variable that is used before and after a recursive call to foo(). So it was replaced by an array, and everytime foo calls itself it increments the second parameter by one.

In a future version, I'll use a built-in internal function, called "varpush(x)", which will push the current value of x onto a stack at the beginning of the function. Then when the function exits, it will pop the old value back off the stack.
This way, instead of setting up and tearing down all of a functions variables every time it is entered / exited, only the variables that need to be preserved will get extra handling, thereby keeping the performance up.

Yes, bold, I know, and potentially error prone. But I couldn't bear the overhead of messing with all the variables every time I entered or exited a function (and it makes the interpreter code that much easier to understand).

Based off of this conversation, I really suggest following something like PLAI and using Scheme. You'll write the entire thing in 20 lines of functions and lists and quickly progress well beyond this point. For example, if you properly wrote the interpreter, making such changes should only impact 1-5 lines of code.

Recursive functions, lexical scoping, mutable variables, continuations, futures, etc. require minimal but conceptually powerful changes in such an approach. You'll figure out the naive implementation approach, and, more importantly, the basic 'clean' semantic design space and sample usage patterns. After you understand what's interesting to include, then start thinking about what optimizations (local or global) are possible for your restricted set of features: for example, profile-driven inlining of functions and subsequent expression elimination transforms might yield a much bigger win than a funky stack discipline.

In essence, all your variables are mutable as well as global (though not necessary globally visible). That's the opposite of lexical scoping - or any scoping at all, for that matter - and a sure recipe for disaster. And it is not only extremely error-prone and precludes recursion, as James points out, it also makes first-class functions practically useless.

I feel that the discussion is evidence that your approach of trying to understand advanced PL concepts in terms of C does not fly. You should take the advise already given by others and invest time to actually learn some high-level language and respective implementation techniques.

My variables are mutable (so it's not pure-functional), and internally they are all stored in the same data structure, but from the 2e script a variable "foo" in one function is unique to that function, and the same variable named "foo" in another function (or the main program) is unique there, just like in C or Perl, etc. Isn't that what lexical scoping is? They are just statically allocated at "compile" time instead of dynamically allocated when a function is entered (which I'll change at some point).

Now another idea I've toyed with is to have a function inherit variable from it's parent function, but it would be copy-on-write. In this case, they would behave like environment variable inheritance in regular OS processes. That may be closer to what some of the functional languages provide?

As for mutability, if I wanted to make a pure functional language then a couple lines of code in the assignment operator handler could make sure that variables can only be assigned a value one time. At the moment, however, I don't want to go for that, since I want to keep a regular procedural language that has some functional features (maybe this is a contradiction?).

BTW, I've been reading through CTM, and find it extremely interesting, although it is a text that I will have to put a lot of energy into in order to get enough out of it. Also, PLAI appears to be helpful. I just hope it doesn't have a lot of "Use this magic Scheme feature to implement the same feature in our Scheme-like interpreter", since it can be a circular definition (I've seen this too much in other texts).

So far through this project, every time I've needed to add a new feature or change an underlying construct, I've managed to do it with only a few lines of tweaking. But to get the data management part straightened out is going to require a bit more re-working. I'll make sure I keep good notes on all the wrong paths I've taken, and the corrective actions, so that anyone else interested can learn from it.

a variable "foo" in one function is unique to that function, and the same variable named "foo" in another function (or the main program) is unique there, just like in C or Perl, etc.

That's exactly like C and Perl except that it's totally different. In both languages the memory for locally declared variables is freshly allocated on each invocation. That means that a function can call itself (directly or indirectly) without clobbering data set up in a previous invocation. And all that happens without any extra effort on the part of the user.

Isn't that what lexical scoping is?

Nope. You've got globally scoped variables that are namespaced by their enclosing function. Scoping and namespacing are two different things. Namespacing is just a clever way to let two things appear to have the same simple name because their simple names are in different "spaces"*. But namespacing doesn't really change much - if I can write foo.bar anywhere to access bar in the single globally available foo namespace then that's about the same difference as naming the variable foodotbar and putting it in a global namespace. Whether namespaced or not, it's one binding and it's accessible globally.

A binding is a relationship between a symbol and its "meaning." For variables you can roughly say that that means the relationship between a variable name and a location in memory (there are more formal ways to describe this but you're an implementation focused guy so "location in memory" will do). In C, if a function foo has a local variable named bar then there will be a new binding for bar each time foo is invoked because a new location on the stack will be allocated with each invocation.

Global scoping means that a binding made anywhere in a program holds across the entire program. As I've illustrated above, you've described a language with globally scoped variables. There's only ever one binding for the foo.bar variable and that binding is globally accessible. Lexical scoping means that each time a function is called it makes new bindings for its declared variables and that a binding made in one part of your program is available over a certain chunk of the program that can be determined by the lexical position of the declaration. Often lexical scoping is based on nested blocks. In lexical scoping bindings are not in general available across chained function invocations (except perhaps to lexically nested functions) nor are they global - they aren't available anywhere except in their lexical environment. Dynamic scoping means each function invocation makes new bindings for its declared variables and each binding made in a function is available across the calls (and the calls from calls) that the function makes but the binding is lost when the function returns to its caller.

Hope this helps clear up the confusion. Good luck with those books.

* Some languages also add access protection schemes to namespaces - at which point namespaces have become simple modules.

Those books primarily* use lambda and lists (and maybe numbers, if you feel like including them). CTM's use of Oz makes it the more exotic one to me.

*I think they resort to the native macro system when discussing macros, but I never read them that far.

Now I see. So in my documentation, I'll describe this as a global scope / local namespace implementation, since the variables are bound to a memory location at compile time. If I wanted lexical scoping, I'd have to bind the variables to a memory location at run time, whenever a function (or a separate scope) is entered. More likely, the variables will be bound to an index at compile time, but that index will be an offset to a chunk of memory allocated (at run time) whenever a new scope is entered.
And, instead of scoping based strictly on functions, I should have a generalized scoping syntax such as braces, that denote when I'm entering a new scope. Once this is straightened out, I think I'll have a serious language implementation (I originally didn't intend it to go even this far, but I've got most of the features of some of the mainstream languages, plus a few nice extras that they lack -- but that should probably be a separate topic).

Thanks.

There's a terminological snafu you keep repeating that suggests a deeper misunderstanding. Functions don't close over other functions (well they can), they close over their free variables. In your first example code, if you had higher order functions, f2 would be closing over fv1. In your second example, f1 closes over some_variable, though if some_variable is viewed as being in a "global" scope, then we don't usually close over them, though it is fine to do/say so but then we should say that f1 closes over print as well (unless print is a primitive construct in your language.)

It's a pain to encode this notion in traditional C/C++, yet it is also the starting point for many interesting things.

makes me wish for a taxonomy / hierarchy of such things, with examples of what each new "level" allows you to do vs. "lower" "levels".

Stress test it? If you go massively parallel, or deeply nested, won't you run out of stack-space fast?

(I'm only asking because I've got major problems with ML running out of stack space.)

No stress testing yet to be honest, and it's in a state of flux since I discovered that the latest glibc swizzle the jmp_buf in an odd way.

This library is not intended for massive fine-grained parallelism, but medium-grained parallelism. The approach is basically the same as Lua coroutines. On a 32-bit machine, you would max theoretically max out around 500,000 coroutines with 4 kB stacks. But at that point it would seem you're already incurring too many context switches, so a better algorithm would be preferable.