Lambda the Ultimate

I keep an extensive symbol table for each function in memory and it is that structure that I wouldn't want duplicated many times.

My model is typically to encapsulate collections of objects instead of single objects so if the same byte code is executing in more than 1 location, then it would be duplicate copies rather than just 1.

I do believe I can enable recursion within a function by just using an additional command and a different return command but I am looking for a name a little better than just "recurse"!

Joke:
Given the way you've said you feel about recursion, I'm surprised you don't translate 'recurse' simply as 'curse_again.'
/Joke.

It really is very embedded (or not) in the way people think.

I recall one of my classmates who wrote a strictly imperative, non-recursive solution to the 'Towers of Hanoi' problem using for loops. Each of us was pretty surprised when we saw how the other had solved it. Neither of us had ever considered the other possibility. We both got full credit for the assignment, although my classmate was also required to demonstrate that he understood what recursion was and how to use it before he was given full credit; that was the idea that the material presented in that week's lesson plan was trying to cover and his solution to 'Towers of Hanoi', while correct, did not demonstrate mastery of that concept.

I want to include a simple recursive capability, I just don't want to use my call stack to do it.

I consider the call stack to be an implementation detail that for many reasons I want to keep to myself.

I also wrote simple recursive functions in University for toy problems before I started my 35 year programming career!

I can't say I understood exactly all that you are saying but I will give it a better look in the morning.

Thanks for your help.

I understand almost everything you say here and I really appreciate the post.

I have already implemented my "green threads" and I don't actually give functions a "stack" in the sense that is used in most computer languages. I know it is hard to stop circular function call bugs but I am determined to at least catch ones I can see at compile time.

This is an example of a possible solution to my "recursion" problem.

function myfunc(long i) return long {  // start of function definition

// some code

recursion this(long i) return long stack=rstack // setup a stack that contains return address and parms : just a long in this case

// some code

ans=this(crec)        // calling recursive code : push next address and value of "i" on the rstack

if ans>20
  rstack.return(ans)  // pop the rstack : return to next instruction
end if
return ans           // return result and exit the function

}                    // end of function

There are 3 features that implement this idea.

1. A "recursion" command that sets up a stack and a function signature for the recursive code
2. Calling the function by using a function named "this". All recursive code in every function would be called "this".
3. Providing a "recursive" return by implementing it on the stack variable type.

I am not stuck on this solution but I think it could work. Having a "recursive function" inside a normal function also means that creating an object to work on, wouldn't require another function. The scope of the normal function code and the "recursive" part would be the same so no need for big parameter lists and no stacking local variables that don't need to be stacked.

I know my implementation of multiple functions within a single "Server Object" might not be orthodox but it allows me to switch functions by just changing a row number. It also allows me to contain all state information in 1 record and save or remove them from memory without any programmer involvement or affecting any other code. Programmers use functions as if they are all in memory and the system looks after the details.

My call stack is just a variable that tells me which row I came from so I know where to go on return.

I just find stuff like that interesting. I spent a lot of time thinking about call discipline options in the 90's. I can also recommend Andrew Appel's Compiling with Continuations, but you may not like it since examples are given in Standard ML, which is hard to get without a little functional language familarity. I had to read a book on FP around 1994 before I started understanding Appel's code examples well enough. It also gave me just enough insight to recognize STL in C++ as functional programming when my former manager showed it to me around 1995. (I said, "This looks like compile-time functional programming — that's crazy." He confirmed template meta-programming was Turing complete when I asked. I never liked templates much.)

Continuations are often presented in a very confusing way, so it's a lot of trouble to pick up for the reward involved. If the idea is new to you, it's related to return addresses (which I phrase that way since you mentioned a row returning). Since returning from a function is typically a jump in code, similar to a function call, you can approach it as if return is actually a function call to your caller's continuation (where a caller resumes after you return). A lot of entertaining things can be done with this, including tail call optimization, which I don't expect you to find interesting. But if you roll your own green thread library, and use a trampoline (a standard term you can look up), you can structure both downward and upward calls in a call tree as returns to a trampoline along with the continuation you want called next. You can do it manually in C, without writing your own code generator, if you don't mind how confusing it looks. (And since I do mind, because code clarity and simplicity matters, I'm going to have a C rewriter do it instead.)

The last paragraph only aims to explain whether you might ever want to read about continuations. If that wasn't interesting, the answer's probably no. Unless you have a practical problem to solve with control flow going against the grain of your implementation language (for example: my problem is that C is not async), it's likely unrewarding to think about a unified way to organize several sorts of control flow, including non-local exits if you want to simulate exceptions.

Anyway, it sounds like you thought of something to try, maybe involving a private helper function to organize self-recursion. Your description of a "this" function seems to imply scope of that name is the current function, so you can't see another function's "this" entry point. If so, doesn't that mean mutual recursion of several functions would be hard?

I get that you're likely not using the stack belonging to whatever language you use to implement yours. (In a server, I don't think it's a good idea to use one native thread per request, because that doesn't scale to handling as many concurrent requests as feasible when max useful native threads is not the limit.) I assumed each request you process has some context allocated to manage state needed by your language executing a computation. So any time you need a stack-like effect, you just simulate it. (Green threads generally involve an extreme of stack simulation.)

Elsewhere you mention writing a lot of assembler in earlier work, so I know perfectly well you're comfortable simulating whatever you want done using machine resources at hand. When I talk about a stack, I usually mean any kind of simulation of one you need. You didn't mention what language you're using to implement your current stuff, but I'm assuming it's not assembler, and that's why doing recursion is not trivial. Any other language typically won't give you fine-grained control over its simulation of stack features, so if you want to prevent stack overflow in your server, you need to subvert your implementation language's normal approach. Hmm, my line of thinking here isn't going to gel unless you talk about more concrete details I can use to be more specific. So ignore this paragraph, unless you feel like describing what feature you're fighting against as a constraint in your implementation language.

You asked about the implementation language: just plain C (I do program C with an OOP style.). This was so that I could have a source code that would compile for Windows and Linux without much source swapping. Almost every function is custom coded rather than from some code library. My system must run many programs at the same time and stay running so using the C stack for other than the implementations use was out of the question. The system can only be changed while it runs!

• I implement 2 quite different kinds of Objects.
• Server Objects (SO)
• All data contained in the SO and all functions are private.
• Data is automatically persisted to the disk.
• Only interfaces are visible from other SOs.
• Security is implemented on interfaces.
• Communication between SOs is done by flexible messages.
• All messages are queued for all SOs.
• Scope for functions in an SO is inside itself and all data and functions defined in the SO.
• All objects defined in a SO function are local to that function.
• Normal Objects
• Implemented using Classes that can be defined in non local SOs.
• Classes can inherit other classes but only if they are defined in the same SO.
• All functions and data of normal objects are public.

• SOs always seem to be in memory and available.
• Hundreds of SOs could run at the same time but the orientation of an SO is toward collections of Objects rather than lone Objects.

The consequences of the above design is that all functions run in an SO which has it's own local memory and access to heap memory. All memory management is custom done rather than using the operating system as executing many small concurrent programs, requires a more robust memory manager than the operating system provides. All functions can only call local functions or functions associated with local normal objects and therefore there is no sharing of code at execution time. Functions can communicate with all other SOs by sending messages.

All data defined in an SO and all of it's functions and interfaces are automatically saved to the disk. These are loaded into memory as needed and are discarded when no longer used, automatically.

There is no constructor or destructor code and no garbage collector. Memory is managed automatically in 3 different ways , with freed memory automatically joined into bigger chunks. Over time, functions inside the SOs can "timeout" and release whatever memory was allocated by that function to the local memory manager. Over time, SOs can "timeout" and give up whatever memory they used, to the heap and persistent memory managers. SOs are implemented as many "green threads", allocated over a user definable number of operating system threads. Communication, Email, web services etc are implemented as system defined SOs that are sent messages just like all other SOs.

If recursion (functions calling functions that include itself) isn't allowed then I can call a function from any other function within an SO by just remembering what row (in my SO function list) it was last called from. Each SO is totally isolated from all other SOs, so there is no conflict with whatever functions other SOs are calling. The "row" I mention contains all the data that makes my functions re-entrant.

There are many things I could do. As you have noted, I have extensive assembler and other programming experience so I have no shortage of tools to implement whatever I want.

I want my language to implement what I call "traditional programmer make-work coding" automatically. There is no programmer access to memory, disk files (some importing is allowed), ports, printers, sockets, code libraries or pointers. I want the programmer to concentrate on their project rather than abstract Computer Science techniques or Math concepts, unless that is the easiest way to their solution. I will give an example: I don't implement any "hash techniques". The reason is that the best hash techniques take into consideration the kind and frequency of the data to be "hashed" so you have to think about them in detail. I believe this is CS thinking below the level I want for this language and so I include a very adequate automatic B+TREE and binary tree implementation that will do the job without the programmer even knowing what technique is used. I see examples of "quick sort" in other languages but all my object collections include a function called "sort" so there is no need to know anything about sorting. Just use whats there.

Back to the function calling. I could mix the return address and whatever local variables need stacked onto a function call stack like many other languages. I think allowing programmers to use the same structure as the language does, mixes the responsibility of the programmer and the language.

Contrary to what you have written, I do want a facility that easily allows recursive algorithms to be implemented. I just don't want to give the programmer access to my function stack for the reasons I have noted above. I think "recursion" would be better implemented by using a totally user accessible stack that the programmer has full responsibility for.

"Continuations" are another example. I think the concept of "continuations" is beneath the level of my language. I provide the ability, at execution time, to load an arbitrary function from a standard data structure into a common variable and then run it. I could also retrieve the source code from that function, change it using normal string functions and then run it compiled. I can grab any arbitrary list of variables into a Map variable (bag of variables), manipulate them in any way I want and then dump any or all of them into my function variable space while still executing the same function. There is more but I don't see how "continuations" would add to what I provide already.

I provide full "system" and "user" exceptions at any function level that can catch all errors. I do this while not messing up the source code with more than a single line of code that identifies the error handler.

I hope this post makes some of my other posts a little clearer.

Thanks, that was fairly interesting to read. (I have trouble with boredom, so my motivation to ask questions is to hear neat design plans.) To suit convention on this site, I'll constrain comments to things related to programming language when possible, even though I find system and runtime issues just as fun, and often more so.

Clarkd: You asked about the implementation language: just plain C (I do program C with an OOP style.).

That gives me a really good idea of typical limits and gotchas. I plan to use C with an OOP style too, but the project I have in mind sounds like a grind, so I'm putting it off until I can stand the idea of work on my own time without learning a lot. I've been tempted to take time off just to work on it a while. First I'll be doing a C-to-C module rewriter (as part of green thread and process support), then later a Lisp with Smalltalk class extensions using that. Both those have only mildly interesting language issues -- sorta boring for folks around here. So I expect folks to only find semantics of green threads and processes interesting, when it supports problem decomposition with green pipes. Something about how I want a daemon to run may be interesting too, but design is dime-a-dozen until there's code to try. And implementation discussion is little encouraged on this site.

I like the message passing character of your SOs (server objects) quite a bit, and I suppose folks have told you that part sounds a bit like the Actors model. But given the other discussion topic you started about the Actors model, I don't feel like that's safe to talk about, because I gather it's a sore point of some kind. So I'll just talk about message passing, and maybe GPs (green processes) as a generic point of comparison to your SOs. Incidentally, big thumbs-up for queueing. I like an almost pure queue-in/queue-out model, with bounded buffer semantics to limit queue sizes (including byte stream queues like those used for text pipes, though the same idea applies to other sorts of queue).

So far I'm not getting your Normal Objects idea. The only hypothesis I have so far is that it might be something client-side, as opposed to server-side for SOs. Clearly what you mean by non local SOs is key to grasping context you have in mind. Is it the same programming language in each case? (Incidentally, thanks for not talking about syntax so far. I'm not a big fan of fancy syntax design, so I can only listen politely when topics tend that way. I care more about what it means.)

Sounds like automatic persistence to disk is one of the main features you emphasize. Let me know if you want me to ask questions, and how searchingly they can be phrased without giving offense. One of my first questions is usually, "What happens when resources are exhausted?" For example, suppose folks write code generating data at a high rate -- anything on the order of a gigabit or ten per second is enough to explore use cases. What happens on disk full? And assuming this is how a system becomes functional again, how do you discard data you don't want any more? Do user visible knobs express or influence retention policy? I don't want to rain on your parade; I just enjoy seeing problems handled in nice ways.

Your paragraph mentioning memory management implies the runtime has a scheme or three, but maybe that doesn't apply to disk too. If it does (and RAM and disk are just layers in the same memory hierarchy), I guess that would answer every question I asked above, when it implies disk is just larger secondary storage for runtime memory.

Glad to hear you'll have B+trees (I usually just say btrees). I've done those before; they make a nice mechanism spanning runtime memory and disk. No need to convince me how hash maps can require highly detailed tuning. :-) I've written many dozens of them, and the bigger they get, the more it matters exactly how they get used. Around the time more than half your memory is consumed by one hashmap, you care a lot exactly how it gets used, so capacity is maximized and nothing linear ever occurs since latency to touch many megs in RAM is crushing.

Ignoring continuations as a feature sounds like a good idea unless you can't excape it, or unless it simplifies a problem you can't solve as easily otherwise. A C-to-C rewriter I plan will output some code with reified continuations, and no one could debug it (say under gdb) without a mental model of what it means. It would only seem simple in comparison to really gnarly and awkward callback systems. I wouldn't expect anyone to willingly manipulate continuations in Lisp, even though they can be exposed using one or another flavor of standard api. (I don't mean to pitch my plan; when there's code I'll just tell folks to read docs and do whatever they want.)

I like hearing about your SOs because they create a use case for me to think of how I might simulate them with green processes. But the row metaphor in your model throws me a little bit. I still like hearing your plan even with rows in it.

edit - I forgot to include an idea I had about this part:

Contrary to what you have written, I do want a facility that easily allows recursive algorithms to be implemented. I just don't want to give the programmer access to my function stack for the reasons I have noted above. I think "recursion" would be better implemented by using a totally user accessible stack that the programmer has full responsibility for.

Sorry if I implied otherwise. You could add a feature helping users employ an explicit stack instead of making recursive calls. I think it's always possible to rewrite recursion as explicit local stacks with looping (though I don't recall doing this with much mutual recursion before).

You could take source code with recursion as input, then rewrite this via a tool specifically tasked to this issue, so output uses an explicit stack the way you're prefer users write by hand. And then they'd use that version of the source instead. Your compiler might emit that sort of stuff as part of a warning about recursion, if you wanted to deprecate some recursion. (But UI might need testing to see what users find offensive or confusing.)

I think the last time I rewrote recursion into explicit stacks by hand was about ten years ago, inside a mini expression compiler for ESI (edge side include) markup in server-side web-page processing. It was easier for me to think about first as recursion, then transform that. Depending on a problem, your users might feel the same and get a mental block when directly using explicit stacks, though it's easy to see the stack version is the same as equivalent recursion.

So far I'm not getting your Normal Objects idea. The only hypothesis I have so far is that it might be something client-side, as opposed to server-side for SOs. Clearly what you mean by non local SOs is key to grasping context you have in mind. Is it the same programming language in each case? (Incidentally, thanks for not talking about syntax so far. I'm not a big fan of fancy syntax design, so I can only listen politely when topics tend that way. I care more about what it means.)

I have many built-in data types (32 at last count) and all are treated as objects. They can be inherited and include many object containers (List, Tables, Index, Stack, Queue, Map etc). SOs can't be contained in a List but Objects can. Objects are light weight, lack interfaces, persistence, don't have their own memory space etc. Normal Objects are used inside SOs to implement "cross cutting concerns" while SOs are used to implement object collections. Client side means Javascript in a browser and that is handled by a Wiki Text like, content manager. SOs can also provide an interface to other groups of SOs. Security is only implemented at the SO level so all "normal objects" are considered local. Server Objects, Interface Functions, Functions, Procedures, Classes, Data are created and changed by using a "document" sent to the SO that contains these Objects. Only 1 language is used everywhere. BTW, I agree with your "fancy syntax" comment and my syntax looks a lot like pseudo code with no sugar.

One of my first questions is usually, "What happens when resources are exhausted?" For example, suppose folks write code generating data at a high rate -- anything on the order of a gigabit or ten per second is enough to explore use cases. What happens on disk full? And assuming this is how a system becomes functional again, how do you discard data you don't want any more? Do user visible knobs express or influence retention policy? I don't want to rain on your parade; I just enjoy seeing problems handled in nice ways.

If memory gets exhausted, a closing sequence is initiated that frees memory. Memory can also be moved from "persistence" memory to the heap and then to local memory managers as needed. All functions can be restarted at any even command. The presence of an SO in memory or not is automatically taken care of. I am relying on modern computers with lots of memory for larger systems. Because of message passing, some SO groups can be moved to other local computers without changing the calling messages at all. I have a Table variable type that is identical to a List but it only keeps 1 record in memory at a time (a List is always fully in memory or not). Data could be added to a Table in a stream and it would only be limited by the disk size. Normally all data is written to a single operating system file that grows but you could allow more than 1 file on different disks. A single table, however, would be limited to living in a single disk file. 2T disks are cheap and bigger disks are coming. My system can access disk space from a 8 byte integer so no problem from my end. When I talk about "1 file" above, I am referring to an operating system file that could contain any number of Tables and other Objects used in my language. My system has it's own filing system.

Any data item that is defined in an SO is automatically persisted to the disk. Interfaces and functions defined in an SO are persisted. All data defined in interfaces and functions isn't. Persistence is a matter of where a data item, interface or function is defined. To delete a function for example, you ask for the SO's design document, delete the reference to the function and send it back to that SO. The SO finds your change, removes the function, frees the memory and disk space. The same would be true if you wanted to delete a List with 20 million records. You could also delete an SO (with the proper permissions) and that would delete each object contained in the SO from the disk and then from memory. Sorry, no knobs. I seems easy to me but remember, you can only create and change the system while it runs. Unlike most languages and somewhat like Smalltalk, you never start over with each program change.

Your paragraph mentioning memory management implies the runtime has a scheme or three, but maybe that doesn't apply to disk too. If it does (and RAM and disk are just layers in the same memory hierarchy), I guess that would answer every question I asked above, when it implies disk is just larger secondary storage for runtime memory.

The disk also has an extensive manager. It automatically resizes disk blocks, reuses others, buffers writes, provides replication and reshuffles the data when too many holes are detected. Disk space isn't treated the same as normal memory. There is no access to the disk routines available to a programmer.

Glad to hear you'll have B+trees (I usually just say btrees). I've done those before; they make a nice mechanism spanning runtime memory and disk. No need to convince me how hash maps can require highly detailed tuning. :-) I've written many dozens of them, and the bigger they get, the more it matters exactly how they get used. Around the time more than half your memory is consumed by one hashmap, you care a lot exactly how it gets used, so capacity is maximized and nothing linear ever occurs since latency to touch many megs in RAM is crushing.

I can have tables and indexes on millions of records and the indexes only need about 5 buffers with 5 disk accesses to get a row number with only 1 disk access to load the data. All tables have indexes accessed from the disk while Lists have indexes fully in memory. You can also optionally define the maximum number of entries in the index blocks. I used the hash example because some people have assumed I don't know about techniques just because I don't include them in my language. Many things are left out precisely because I know the problems they cause (pointers etc).

Ignoring continuations as a feature sounds like a good idea unless you can't excape it, or unless it simplifies a problem you can't solve as easily otherwise. A C-to-C rewriter I plan will output some code with reified continuations, and no one could debug it (say under gdb) without a mental model of what it means. It would only seem simple in comparison to really gnarly and awkward callback systems. I wouldn't expect anyone to willingly manipulate continuations in Lisp, even though they can be exposed using one or another flavor of standard api. (I don't mean to pitch my plan; when there's code I'll just tell folks to read docs and do whatever they want.)

I love the "macros at compile time" of Lisp but not much else (S expressions are ugly). I am trying to make a higher level language than Lisp and "continuations" and "callbacks" don't fit. However, messages can be sent to any arbitrary SO (that security permits) so I guess it would be easy to provide "callbacks" as well.

I like hearing about your SOs because they create a use case for me to think of how I might simulate them with green processes. But the row metaphor in your model throws me a little bit. I still like hearing your plan even with rows in it.

Stacks are just 1 of the data types I have built in. When calling a function, I don't need to stack any variables because they are all available in symbol tables (including names etc). All functions that are currently being used by an SO are readily available. If you have a function call 5 levels deep, then you have at least 6 functions with all their symbol table, source code, byte code etc sitting in your function table. If you don't allow recursion, then you only need to remember which row to return to. If I needed a stack, I could easily create one.

I have implemented my message passing and green threads so I will give you a little advice that I got from the creator of Erlang (not directly but from a paper he wrote). Pass all data with messages and keep all state local to the green thread. Of course you can't do that 100% but then, if it was easy, everybody would do it!

Your first paragraph on built-in data types (and client side Javascript etc) is nice and meaty, showing a well-formulated plan, but I'm drawing a blank on good questions. Which is good, because a lot of questions are driven by "What can go wrong?" considerations, as well as "But how would you do this?" puzzles. And later you acknowledge content can be explicitly discarded by users, so that makes me stop squirming in fear of plans to save everything forever. :-)

I am relying on modern computers with lots of memory for larger systems.

That's a reasonable expedient. For example, anticipating lots of RAM, I plan to do something totally evil in first C-to-C rewriter, and assume all files rewritten in one session can be loaded into memory at once, and probably also in contiguous blocks per module processed. This would permit shrinking token representation quite a bit when I want to know exactly where each token is located, since I can infer a lot. (It may be an unpopular first draft choice, but I can just tell folks to rewrite it.) I don't have any problem telling devs their build machines must be at least this tall to get on the ride, since only output code need work under harsher memory conditions.

Because of message passing, some SO groups can be moved to other local computers without changing the calling messages at all.

Excellent, migration and some location transparency has a really good smell. I expect it's also enormously helpful in testing, because it's trivially easy to create simulated networks which can be varied several ways to show behavior doesn't change.

Normally all data is written to a single operating system file that grows but you could allow more than 1 file on different disks. [...] My system has it's own filing system.

Very interesting, and someone could write a block device driver to use a disk as a single file too if they wanted to strip out every bit of overhead and indirection they could.

I had a design like that once, at the end of the 90's, which put everything in one file: streams in exodus blob btree format and indexing btrees too, managed with copy-on-write to get a log-structured file system result which recovers nicely from failures. (You probably already know this, but make sure you don't modify the description of free space in the slightest until you commit to a new root of the content tree; you can only re-use space recorded as free now as well as free in the prior system lifetime.)

Any data item that is defined in an SO is automatically persisted to the disk. Interfaces and functions defined in an SO are persisted. All data defined in interfaces and functions isn't. Persistence is a matter of where a data item, interface or function is defined. To delete a function for example, you ask for the SO's design document, delete the reference to the function and send it back to that SO. The SO finds your change, removes the function, frees the memory and disk space. The same would be true if you wanted to delete a List with 20 million records. You could also delete an SO (with the proper permissions) and that would delete each object contained in the SO from the disk and then from memory. Sorry, no knobs. I seems easy to me but remember, you can only create and change the system while it runs. Unlike most languages and somewhat like Smalltalk, you never start over with each program change.

Very nice description. I love short definitions with lots of "all" and "every" qualifications so hidden gotchas are difficult to get.

I can have tables and indexes on millions of records and the indexes only need about 5 buffers with 5 disk accesses to get a row number with only 1 disk access to load the data. All tables have indexes accessed from the disk while Lists have indexes fully in memory.

I love btrees with big node fanouts because how shallow trees get, even with huge leaf populations. In the 90's I had the misfortune to be handed custody of an address book using a third party library using (shudder) binary search in inner nodes with consequent high disk seek counts per index update. I was told, "Make this sync with a 100,000 entry LDAP server for these large customers." With five indexes and a worst case population of 2^17, this caused twelve disk seeks per index when 32 entries fit in each leaf node, for a total of sixty disk seeks per entry added, when user disks could only manage 60 disk seeks per second. So the last entry of address book sync would take a whole second of latency. Guess how long the entire sync would take? Without removing binary search, that library needed vast amounts of RAM to bring down whole operation time. (The third party vendor didn't like me.)

Let's see, I can come up with a question. At Apple in the mid 90's (earlier than above) I was asked to guess what would happen if we used a storage system, made by a company Apple wanted to buy, if deployed on Macs with either 4MB or 8MB of RAM at most in typical low end configurations. I can ask you the same question I asked that system's designer, since you might need the answer for something or other. For each entity in the storage system that has identity, how much footprint is consumed in RAM or on disk? Those might be related in systems that load the entire table of contents into RAM, as was done by Bento under OpenDoc. For Bento the answer was 100 bytes. For a mature database, the answer depends on how many indexes an entity must appear inside, how much index must appear in RAM, and on disk how much average overhead exists per nodes of trees. I don't need your numbers, but you might have customers ask this question. Designing to unpleasant realities of consumer grade machines can be interesting.

I love the "macros at compile time" of Lisp but not much else (S expressions are ugly).

I guess I don't find S expressions ugly, partly because I want to see parse trees. (Here I imagined a New Yorker style one-panel cartoon where an audience member interrupts a guy's PowerPoint slideshow to request, "Can you just send me the parse trees?") My tolerance of dense parens might be a learned response, a kind of information-theoretic grasp that anything repeated a lot means less, so you stop seeing it as much. This is like ignoring a name prefix in every symbol in a library that uses that prefix everywhere. So in S expressions I see groups of stuff in relationships, and parens not so much, though I know they induce great distaste in many people.

(Smalltalk syntax is also easy, which I can compile to identical parse trees; parsing Smalltalk is incredibly simple -- I did a parser once needing only one token look ahead. Adding other syntax or different scripting languages would be easy, but life is short and I expect more folks to want to use the C layer directly, as crazy as that sounds. A scripting language would only be helpful when pushing scripts from a browser client up for interpretation in a daemon; I guess that could be anything. I guess anyone using a client is operating in product delivery space and wants it to look exactly like the UI they prefer; so a tool maker has to deliver whatever is demanded, which could vary a lot. In contrast, what happens in a daemon can be whatever a tool maker wants.)

I have implemented my message passing and green threads so I will give you a little advice that I got from the creator of Erlang (not directly but from a paper he wrote). Pass all data with messages and keep all state local to the green thread. Of course you can't do that 100% but then, if it was easy, everybody would do it!

Well, sometimes you can only pursue such limits to scope of green threads so far. :-) If there's a big cache all green threads try to leverage, they all end up trying to cause updates to that cache, even if the local immutable data in green threads has no shared update problem.

After mulling it over, I decided my glib endorsement of queueing might cause someone to use queues blindly to poor effect in performance, unless context switching is explicitly minimized by design. These comments will apply to programming languages as well as other things.

The basic conflict is one between centralization and decentralization, otherwise known roughly as global optimization and local flexibility. (Many years ago, Dilbert had a really funny piece on Dogbert's scheme to succeed in business by alternately pursuing one, then the other.)

Queues are a good way to unwedge monolithic processes by breaking them in pieces susceptible to rational management, using local dataflow reasoning. But done naively, they also can cause context switches more often than necessary: either thread switching, or just bouncing between L3 cache working sets. Slightly worse though is typical increase in latency, when a handoff only continues after another party finally gets around to polling an input queue. Thirdly, you can obscure cause-and-effect through control flow laundering as functions queue messages that send events etc in several layers, or multiple times inside a single layer. (When debugging, if your call tree seems to dry up without going anywhere, it usually means an event was queued to resume control flow later, but now in a slightly more anonymous way with blame scrubbed.)

So there's totally a Scylla vs Charybdis situation in being able to break things into convenient pieces, without losing context in enough contiguity to get efficient batch execution, by focusing on one thing as long as you can without blocking or over-running a deadline. The act of putting queue support in place can let you accidentally scramble execution order more vigorously than was strictly necessary. So for performance you want some pursuit of monolithic focus, which may seem to counter queueing effort, and looks complex.

Really fair scheduling can cause more switching, so you want to be as unfair as feasible sometimes to stay on one thing and avoid latency, as long as everything gets timely service. (Okay, I'm done. Don't quote me as saying queues are always good, no matter what.)

After mulling it over, I decided my glib endorsement of queueing might cause someone to use queues blindly to poor effect in performance, unless context switching is explicitly minimized by design. These comments will apply to programming languages as well as other things.

The basic conflict is one between centralization and decentralization, otherwise known roughly as global optimization and local flexibility. (Many years ago, Dilbert had a really funny piece on Dogbert's scheme to succeed in business by alternately pursuing one, then the other.)

Your points are exactly why I have 2 different kinds of Objects in my language.

My SO (Server Objects) are meant to call each other 100's or maybe thousands of times per second by not more (less is better). I use a very flexible (but relatively slow) interface function for SOs that always checks security and auto releases most local memory after each message. This would not be acceptable if you looped 10's of thousands or millions of messages at an SO. My "normal object functions" (light weight) and "normal SO functions" (pass parameters and return a single result) are used in the later case.

Queues are a good way to unwedge monolithic processes by breaking them in pieces susceptible to rational management, using local dataflow reasoning. But done naively, they also can cause context switches more often than necessary: either thread switching, or just bouncing between L3 cache working sets. Slightly worse though is typical increase in latency, when a handoff only continues after another party finally gets around to polling an input queue. Thirdly, you can obscure cause-and-effect through control flow laundering as functions queue messages that send events etc in several layers, or multiple times inside a single layer. (When debugging, if your call tree seems to dry up without going anywhere, it usually means an event was queued to resume control flow later, but now in a slightly more anonymous way with blame scrubbed.)

So there's totally a Scylla vs Charybdis situation in being able to break things into convenient pieces, without losing context in enough contiguity to get efficient batch execution, by focusing on one thing as long as you can without blocking or over-running a deadline. The act of putting queue support in place can let you accidentally scramble execution order more vigorously than was strictly necessary. So for performance you want some pursuit of monolithic focus, which may seem to counter queueing effort, and looks complex.

Really fair scheduling can cause more switching, so you want to be as unfair as feasible sometimes to stay on one thing and avoid latency, as long as everything gets timely service. (Okay, I'm done. Don't quote me as saying queues are always good, no matter what.)

I agree with you that queues aren't always a good thing, however, my language is built around very flexible message passing and the alternate is to block or throw an exception and try again. In my system, queues are a much better vehicle than either of these options. I use the queues more to order the incoming messages to the SOs than to release (un-block) the message sender right away. I do have 1 way, blocked and un-blocked messages, however.

I agree that minimizing the number of green threads per real thread and minimizing context switches on the same thread is a good thing. I would hope that most of the time, very few green threads would be utilized on a single thread. My switching time default is about 50 mil sec but only if you don't have the thread to yourself. I don't use a priority execution system at this time so my scheduling is fair.

I looked up your web site and found that you have implemented multi-threading for C yourself in 2011.

One potential problem is circular messages. I can have the system prevent this my using levels on the SOs.

• If an SO sends no messages outside itself, it has no level and can receive messages from any other SO.
• Otherwise, you declare the level of each SO.
• It would be an error at compile time to send a message to another SO that is not on a higher level.

This prevents circular messages regardless of how circuitous the message thread would be.

I may free associate, with neither recursion nor programming language focus — meaning off topic. So I'll try to keep it interesting. (We might have to let the queue sub-topic go if we can't make it relevant to other folks. I was afraid of giving folks a bum steer without adding caveats not to go overboard, as much as I like queues.)

I agree with you that queues aren't always a good thing, however, my language is built around very flexible message passing and the alternate is to block or throw an exception and try again. In my system, queues are a much better vehicle than either of these options. I use the queues more to order the incoming messages to the SOs than to release (un-block) the message sender right away. I do have 1 way, blocked and un-blocked messages, however.

Sounds good. I like the plan to avoid unblocking instantly on message arrival, so context switching happens less often. Here I segue into a comparison with condition variables, assuming monitor style thread sync primitives, and hope you see direct analogy to queues in condition variables (where blocked threads are waiting for signal or broadcast). I know you weren't talking about that, so this might seem like change of subject.

I recall operating systems classes used to show how several primitives were roughly equivalent to one another, including semaphores, monitors, and send/receive mailboxes. I tend to think of worker thread pools as using a send/receive mailbox in queue form that happens to be managed by a monitor, or just naked mutexes and condition variables. (If you implement green threads, you must implement locks and condition variables so they work under cooperative user space scheduling, and then they stop seeming very mysterious.) Anyway, I hate when a cond var's signal() instantly causes a context switch, so it burns me if an api contract says you don't need to know whether it happens right away, or only after you unlock the mutex. It does matter, so I want both flavors of signal() present as different calls.

In general, I think you should leave control in currently running code as long as there's more time slice, just so it keeps getting a cheap bang out of current L3 cache state. To me that seems directly related to queuing messages instead of unblocking instantly.

I agree that minimizing the number of green threads per real thread and minimizing context switches on the same thread is a good thing. I would hope that most of the time, very few green threads would be utilized on a single thread. My switching time default is about 50 mil sec but only if you don't have the thread to yourself. I don't use a priority execution system at this time so my scheduling is fair.

I don't mind there being an enormous number of green threads per native thread. I just don't want a native thread to switch which green thread is running too quickly. But whether that's a good idea depends on whether code is i/o bound or CPU bound. In network apps that are i/o bound (unless you made a mistake), you can give green threads their head and you'll still let them all run to completion or the next time they block. So frantic switching is waste.

I looked up your web site and found that you have implemented multi-threading for C yourself in 2011.

(Here's where I really go off topic. To make you understand what I've been working on in recent years, and how it relates to green threads, I'd have to say a lot about my job, which involves deduplication in many TCP connections at once inside the WAN optimization module of load balancers. But I'm not a spokesman for my company, and they'd prefer I not describe what I'm doing, especially if it sounds interesting. So below I'll aim for the least amount of context I can to comment on queues and threads.)

My site's not worth reading since I haven't posted anything for a couple years. It's still up only because I plan to redo it from scratch someday, with a new focus saying almost nothing except docs on green threads, a C-to-C rewriter, and tests as well as low level libraries. Part of that site was an experiment in formats. I plan to keep that scheme because it works for static web pages checked into a source code tree one can browse locally. I had hoped the site would be fun to write, but it wasn't, even after I gave it a while to soak. So I wrote less and thought more instead, especially about simplifying.

I've done more than one kind of green thread. A variant based on continuations is painful to do by hand. It was only during an exchange here on LtU that I realized I could write code in direct style, then convert it using CPS (continuation passing style) transform to what I might have done by hand, but with far fewer errors. And then I might run tests against both before and after versions, if the original direct style version had an api that worked under native threads. Then I'd be able to compare sync-under-native-threads to async-under-green-threads as part of unit testing. (My testing strategy leans toward "do it twice and compare.")

At work they didn't want that sort of green thread because it sounds like crazy CS wonkery, so I agreeably did another on demand which is far more ad hoc, using FSMs and callbacks, and of course lots of queueing since this requires a user space scheduler still. In this case, it's like a simulation of green threads, or at least I have to think about it that way to reason out what will happen. I have multi-year empirical results from this way of doing green threads full-time, but I can't discuss it, except theoretically — such as effect of queues. From a profiler, it's quite hard to directly measure latency due to queue handoffs, because no code to blame for the time is running.

If I do more green threads folks can use, I'll say so afterward. I might take down my site until it's done. The C-to-C rewriter is most interesting now, since it will simplify iterative green thread design when you can just recompile after changing your mind on how green threads work. If I had an app needing that setup, I'd be more interested in spending hobby time on it. But I have become far less interested in programming since the industry has become focused on social apps. Apps for gabbing bore me, but I'm not sure why. I might be able to talk myself into making my sons a game platform.

One potential problem is circular messages. I can have the system prevent this my using levels on the SOs.

That's interesting. I've been wondering how to stop folks from writing resource bombs (fork, message,and disk bombs) if casual programmers -- something closer to end users -- are allowed to write scripts that might chew through all available network bandwidth, as well as use all CPU cycles and disk space, perhaps on their friends' machines. Some kind of trickle-down quota scheme semantically similar to capabilities might work, to limit resource burn to some quality-of-service threshold. If manual intervention is required to re-up grants, users can shoot off only a toe and not a whole foot.

Your concern about circular messages reminds me of events in systems that post internal events. For example, Hypercard allowed users to script inter-object events. When I asked, "What stops an event storm from going on forever?" folks wondered what I was concerned about. It seems like a good plan to 1) limit max message chains, and 2) record and expose stats about actual length of those chains.

You and I seem to have similar tastes.

Appel's book shows that you don't need a stack (he also wrote a paper Garbage Collection can be Faster than Stack Allocation)

Doesn't the book basically cover the same info found in the paper as well? Chapter 16, page 206 has "... there is no inherent lower bound on the cost of copying collection." That was the gist of the paper wasn't it?

The Queinnec book is a delight. The closer you get to the end the more you realise he's setting you up for a big bootstrap. With regards to stacks, I figured out how to implement Prolog exceptions from implementing the Scheme interpreters in that book. It was a real education.

The best book for stacks, IMHO, is the Kluge book which I've mentioned before. Basically, after reading that book you have it hammered into your brain that stacks are at the core of any computing machine: stacks for values (S), stacks for environments (E), stacks for control (D). Pretty much all architectures are variations of the SECD machine.

Continuations are not exclusive to functional programming. In fact, both functional and imperative programming can be implemented on top of continuations (that is my approach with my dodo language).

Exactly! In the words of deBakker and deVink (Control Flow Semantics, MIT Press)

Continuations are the denotational counterpart of resumptions. Whereas the latter specify the remainder of the program which is still to be executed, the former embody the meaning of this remainder.