Showing posts with label Lisp. Show all posts
Showing posts with label Lisp. Show all posts

Wednesday, 23 January 2019

Mad software

I was listening to Eric Normand's podcast this morning, as I was making breakfast and tidying my room; he was talking about semantics and data. It started a train of thought which I shall try to unroll.

I have blogged a lot in the past about madness and about software, but I don't think I've ever blogged about madness and software in the same essay. But the reasons I'm mad and the reasons I'm (sometimes) very good at software are related; both have their roots in autism and dyslexia, or, to put it differently, how my brain is wired.

I first wrote about post scarcity software thirteen years ago. It was a thought about how software environments should be designed if were weren't held back by the cruft of the past, by tradition and by a lack, frankly, of anything much in the way of new creative thought. And seeing that the core of the system I described is a Lisp, which is to say it builds on a software architecture which is almost as old as I am, perhaps it is infected by my own take on tradition and my own lack of creativity, but let's, for the purposes of this essay, assume not.

I started actually writing the post scarcity software environment on the second of January 2017, which is to say two years ago. It's been an extremely low priority task, because I don't have enough faith in either my vision or my skill to think that it will ever be of use to anyone. Nevertheless, it does now actually work, in as much as you can write software in it. It's not at all easy yet, and I wouldn't recommend anyone try, but you can check out the master branch from Github, compile it, and it works.

As my mental health has deteriorated, I have been working on it more over the past couple of months, partly because I have lost faith in my ability to deliver the more practical projects I've been working on, and partly because doing something which is genuinely intellectually hard helps subdue the chaos in my mind.

Having said that, it is hard and I am not sharp, and so progress is slow. I started work on big number arithmetic a three weeks ago, and where I'm up to at this point is:
  • addition seems to work up to at least the second bignum boundary;
  • multiplication doesn't work beyond the first bignum boundary;
  • subraction doesn't work, and turns out not to be as easy as just inverting addition;
  • division sort of trivially works, but only in the sense that we can create a rational number out of arbitrary bignums;
  • reading works beyond the first bignum boundary, but not up to the second (because multiplication doesn't work);
  • printing doesn't work beyond the first bignum boundary.
I knew bignums were going to be a challenge, and I could have studied other people's bignum code and have consciously chosen not to do so; but this is not fast progress.

(I should point out that in those three weeks I've also done four days of customer work, which is .Net and boring but it's done, spent two days seeing my sister, spent several days so depressed I didn't actually do anything at all, and done a bit or practical work around the croft. But still!)

In a sense, it wasn't expected to be. Writing the underpinnings of a software environment which is conceptually without limits has challenge after challenge after challenge.

But there are ideas in post scarcity which may have wider utility than this mad idea in itself. Layering homogeneities and regularities onto Clojure maps might - perhaps would - make a useful library, might would make a very useful component for exactly the sort of data wrangling Eric Normand was talking about. Yes, you can use a map - raw data soup - to represent a company. But if this map is a member of a homogeneity, 'Companies', then we know every member of it has employees, and that every employee has a salary and an email address. Regularities and homogeneities form the building blocks of APIs; to use the example Eric discussed in his podcast, the salary is the property of the employee, but the payroll is a property of the company. So in the notation I'm using for post scarcity, you'd get the payroll figure for a company by using a method on the 'Companies' homogeneity. How it computes that value is part of the general doctrine of 'Don't Know, Don't Care': the principal that people writing software at any layer in the system do not need to know, and should not need to care, about how things are implemented in the layers below them.

So, the user needing to find the payroll value for a company would enter something like this:

    (with ((companies . ::shared:pool:companies)
           (acme . companies:acme-widgets-plc))
        (companies:methods:payroll acme))

In practice, in post scarcity notation, the payroll method probably looks something like this:

    (λ (company)
        (reduce + 
            (map ::shared:pool:employees:methods:salary 
                (:employees company))))

There are issues that I haven't resolved yet about the mutability of regularities and homogeneities; obviously, in order to provide multi-user visibility of current values of shared data, some regularities must be mutable. But mutability has potentially very serious perfomance issues for the hypercube architecture, so I think that in general they should not be.

However, that's detail, and not what I'm trying to talk about here.

What I'm trying to talk about here is the fact that if I were confident that these ideas were any good, and that I had the ability to persuade others that they were any good, it would make far more sense to implement them in Clojure and promote them as a library.

But the problem with depression is that you cannot evaluate whether your ideas are any good. The black dog tells me that I'm shit, and that my ideas are shit, and that I don't really know enough to be worth listening to, and that I'm an old tramp who lives in a hut in the woods, and probably smells, and that in any case interaction with other people quickly makes me shaky and confused, and that I can never get my act together, and that I never finish anything.

And all that is objectively true, and I know that it is true. But I also know that I can (or at least have in the past been able to) build really good software, and that I can (or have been able, in the past, to) present ideas really well.

These two collections of statements about me are both true at the same time. But the difference is that I believe the first and I don't believe the second.

And behind all this is the fact that bignum arithmetic is a solved problem. I could dig out the SBCL source code and crib from that. I could read Muhammad ibn Musa al-Khwarizmi, who wrote down the algorithms (the word is a europeanisation of his name) for the general problems of long addition, multiplication and division in around 820AD. I could reread section 4.3 in Knuth.

I am bashing my head against bignum arithmetic and trying to solve it myself, not because it's the most efficient way to produce good code quickly, but because what I'm really trying to do is just distract myself and waste time while I can get on with dying.

And the reason beyond that that I'm working on a software system I know I'll never finish, which is designed to run on computers which don't even exist yet - and although I'm very confident that enormously parallel hardware will be used in future, I'm not at all sure it will look anything like what I'm envisaging - the reason I'm building this mad software is that, because it will never be finished, no-one will ever use it except me, and no-one will say how crap it is and how easily it could have been done better.

Because the other thing that I'm doing in writing this stuff, apart from distracting from the swirling chaos and rage in my head, apart from waiting to die, the other thing I'm doing is trying to give myself a feeling of mastery, of competence, of ability to face problems and solve them. And, to an extent, it works. But I have so little confidence that I actually have that mastery, that competence, that I don't want to expose it to criticism. I don't want my few fragile rags of self worth stripped away.

And so I work, and work, and work at something which is so arcane, so obscure, so damned pointless that no-one will ever use it.

Not because I'm even enjoying it, but just to burn the time.

This is mad.

I am mad.

I hate, hate, hate being mad.

Postscript: just writing this essay has made me tearful, headachey, sick, shaky. It's very hard to face up to the irrationalities and self-deceptions in one's own behaviour.

Friday, 1 December 2017

Before Wildwood: the Arboretum engine

(this piece was written as an email in a response to a question by Chas Emerick about whether it is possible to explain inference to ordinary people. It describes the Arboretum engine, which started me thinking about how you make a computable logic which people can understand.)

Right, let's try to set this out in some sensible detail. I'll start by giving you the bones of the story, and then move on to talk about the things you're actually interested in. I'm copying Peter Mott in so he can correct any misrememberings of mine (I have long term severe depression, and it really messes with your memory).

I did a minor course in logic and metaphysics when I was an undergrad. When I graduated in 1986, my logic tutor, Peter Mott, who was entirely deaf, was invited to join an AI project - the "Alvey DHSS Large Demonstrator" essentially as the formal logic input to the process. He invited me to join him as his research associate, mainly I think because having been in his seminars for two years I was pretty fluent at discussing technicalities of logic in sign language, and could interpret for him. I was never the world's most brilliant logician, but I could more or less do it.

Peter was certainly responsible for the logic of the "D-Engine", and I think wrote the first prototype in Acornsoft Lisp himself. The D-Engine logic is a Popperian propositional logic, and the goal of the engine at any stage is to seek to falsify what it currently believes. Again I think it was Peter's insight that this would map naturally onto a systematic practice for interviewing domain experts, but, being deaf, he couldn't develop this interviewing practice himself.

A rule in D-Engine logic is naturally a tree, which we called a "D-Tree". It nodes are propositions "coloured" with truth values, and edges essentially represent "unless" relationships. Because D-Engine logic naturally argues from the general to the particular, it's possible to recover extremely good natural language explanations of decisions from simple boilerplate fragments on the nodes.

There's a paper explaining all this: Mott, P. & Brooke, S. A Graphical Inference Mechanism. Expert Systems, May 1987. vol. 4. No. 2 pp. 106-117

(Golly. I've just - for the first time ever - done a google search for that paper, to see it it was online anywhere. It isn't, but it's cited in lots of places - including by Marc Eisenstadt! I'm pleasantly suprised).

I built the second prototype, Arboretum, in Interlisp on Xerox 1108 Dandelion and 1186 Daybreak machines, and that was the one that was used in the project; we demonstrated that it was possible to automate decision making on a piece of legislation (eligibility for widows' allowance), and, critically, to automatically generate letters to claimants which claimants could understand.

At the end of the project, Peter and I and a number of others of Peter's ex-students spun out a company to try to commercialise D-Engine logic. As (again) Peter was deaf, and as he intended to continue as a lecturer, he chose not to head up the company, and I was elected Chief Exec; I was also the technical lead. We knew we couldn't commercialise our work on the Xerox workstations, because they were way too specialist and expensive to sell into industry. I had a look at Windows, which was at version 2 at that stage, and it was just a horrible mess. We couldn't afford Macintosh (and, in any case, the M68000 Macs of those days were really not very powerful); so we decided to write the new version on Acorn Archimedes ARM machines, on the basis that I already had one. The plan was always to port it to UN*X later.

There was a good Lisp compiler for the Archimedes machines, but it was Portable Standard Lisp which was going out of favour (Common Lisp had just been standardised). It suffered from another problem which was for us more serious: the garbage collector moved things in memory, and the Archimedes window manager held fixed pointers to things; so, while I did a lot of work on this and got somewhere, the solution wasn't going to be portable.

So we decided to rewrite the system in C (which at that stage none of us knew). We also decided to do something else ambitious: we decided that because our new version - called KnacqTools for "Knowledge Acquisition Tools" - would require a graphics workstation, and such machines were then uncommon in industry and expensive, we should compile the knowledge once elicited down to run on one of a number of rule engines that were then available for PCs; and we decided that these rule language compilers should be pluggable.

We got the Archimedes version of KnacqTools feature complete and working well within a year. We demonstrated it to Acorn, who gave us two of the UN*X (BSD 4.3) version of their ARM workstations, called R260. On these we ported KnacqTools to OSF-Motif, which was the then-dominant window manager for X11. We got this feature complete in not very long, and it looked extremely impressive - so impressive that NCR gave us UN*X workstations with the intention that they would adopt KnacqTools as a product. However, the OSF-Motif version suffered from persistent memory leaks which we never fully resolved.

But in the meantime the company was in financial trouble. We'd started without capital and had funded the company organically by doing consulting. Members of the team wanted me to concentrate on product development, but I was also the person who could do the sort of consulting work which brought in money. And in the winter of 1981-2, recession hit the UK economy and our customers stopped spending on experimental AI projects.

If I knew then what I know now, the company could have been saved. What we needed was an angel, and we actually had a very good story to tell to angels. Our customers included Courtaulds - for whom one of our systems ran a critical chemical plant - Ford Motor Company, Bull, De La Rue, and a number of other industrial big players. We had a very impressive product, which was very close to finished. And we were teaching successful courses on the adoption of artificial intelligence into industry. But I didn't know about angels and I didn't have the contacts, so the company went down.

OK, that's the background: onwards!

Over a period of about three years I taught three-day courses on knowledge acquisition to around a hundred people mainly drawn from industry and the civil service - I can't remember why we didn't do more with financial services, which would have been an obvious market, but it's a fact we didn't. In teaching knowledge acquisition I obviously also taught an understanding of representing and structuring knowledge. The people I taught it to were mostly degree educated, and many were extremely senior people - ranging from senior engineers in charge of industrial plant, to executives evaluating future technologies for their companies. But they weren't by any means universally people with advanced maths skills or any previous experience of formal logic. These courses were generally very successful, and at the end of them participants typically could build working systems to make decisions in a domain of knowledge.

What made this possible was the very simple logical schema: ask the domain expert to choose the question to be answered, the proposition whose truth value was to be determined:

This person satisfies the conditions for widows' benefit

Ask them what the default value of the proposition is - in this case, 'false', most people aren't eligible for widows' benefit.

We would notate this as follows:

        Satisfies conditions for Widows' Benefit -

So OK, you ask the expert, what's the first thing you can think of which would make you change your mind, make you think a given person was eligible?

If they were a widow.

And if they were a widow, would they then be eligible?

No, their husband's national insurance contributions would have to have been up to date

And if their husband's national insurance contributions were up to date, would they then be eligible?

No.

We can now extend the graph:

        Satisfies conditions for Widows' Benefit -
                            |
                            |
                         Widow -
                            |
                            |
               Husband's contributions OK -

So, given they are a widow, and their husbands contributions were up to date, what's the first thing you can think of which would make you change your mind?

If they were under pension age when bereaved.

And if they were under pension age when bereaved, would they then be eligible?

Yes.

We now have a condition which overturns our original assumption that the person isn't eligible, and we notate it thus:

        Satisfies conditions for Widows' Benefit -
                            |
                            |
                         Widow -
                            |
                            |
               Husband's contributions OK -
                            |
                            |
                   Under pension age +

Is there any further condition that would change your mind and lead you to conclude that they were not eligible?

No.

So that closes one path and we recurse back up:

OK, so we've got someone who is a widow and whose husband's contributions were OK, but was not under pension age when bereaved. Is there anything else that would make you think they satisfied the conditions for widows benefit?

Yes, if their husband wasn't entitled to a retirement pension they would be eligible.

        Satisfies conditions for Widows' Benefit -
                            |
                            |
                         Widow -
                            |
                            |
               Husband's contributions OK -
                         /     \
                        /       \
       Under pension age +     Husband not entitled to retirement pension +

Again, you probe for further conditions; if there are none, you close the path, and recurse back.

OK, so we've got someone who is a widow and whose husband's contributions were OK, but was not under pension age when bereaved, and their husband was entitled to a retirement pension. Is there anything else that would make you think they satisfied the conditions for widows benefit?

No.

Again, we've nowhere further to go from this node, so we recurse back up:

OK, so we've got someone who is a widow but whose husband's contributions were not OK. Is there anything else at all which would make you think they satisfied the conditions for widows benefit?

No.

Again recurse back up:

OK, so we've got someone who is not a widow. Is there anything else at all which would make you think they satisfied the conditions for widows benefit?

No.

And so we can close this tree: it's complete. As you can see, this is a very simple procedure: the interviewer always knows what the next question to ask is, and the answers can be systematically recorded. So it's very easy to teach, and people easily understand how this process maps on to real world decision making. There may still be some things which aren't completely clear - for example, what is entailed by 'Husbands contributions OK'? But we can use that as the start of a new tree and repeat the process. We had special notepads printed with a triangular grid to make drawing trees easier, but that was mainly sales collateral; essentially anyone who can ask questions and scribble on paper can conduct one of these interviews.

So, again, I didn't have the original idea, that was down to Peter. But I did develop the interviewing practice, and I was the person who mainly delivered the courses on it.

The nature of logic is that you can operate on it with logic. A logical formalism can be translated into another logical formalism with similar (or lesser) expressivity, so it was trivial to translate D-Trees into production rules which would run on a conventional backward chaining production rule engine. I'd also argue, from experience, that D-Trees are easier for non-logicians to understand than production rules, since a non-specialist can assess whether a D-Tree has complete coverage of an area of domain knowledge, whereas it's much harder to assess whether a corpus of production rules does.

So to come back to your original question, yes, I know from experience that you can enable 'ordinary people' to understand inference, provided you can find a simple enough expression of it. Of course the D-Engine logic wasn't as sophisticated as a first-order predicate logic, and certainly wasn't as sophisticated as a constraint propagation logic, but I don't believe those are insuperable issues. You can't expect 'ordinary people' to understand dense code or complex formalisms; upside down 'A's and back turned 'E's, and all the various hooks of set notation, quickly alienate those who are not mathematically inclined. But all inference is the systematic performance of a limited number of individually simple legal moves, like chess; and 'ordinary people' can understand chess, even if many are (like me) not very good at it.

Tuesday, 19 September 2017

Implementing post-scarcity hardware

The address space hinted at by using 64 bit cons-space and a 64 bit vector space containing objects each of whose length may be up to 1.4e20 bytes (2^64 of 64 bit words) is so large that a completely populated post-scarcity hardware machine can probably never be built. But that doesn't mean I'm wrong to specify such an address space: if we can make this architecture work for machines that can't (yet, anyway) be built, it will work for machines that can; and, changing the size of the pointers, which one might wish to do for storage economy, can be done with a few edits to consspaceobject.h.

But, for the moment, let's discuss a potential 32 bit PoSH machine, and how it might be built.

Pass one: a literal implementation

Let's say a processing node comprises a two core 32 bit processor, such as an ARM, 4GB of RAM, and a custom router chip. On each node, core zero is the actual processing node, and core one handles communications. We arrange these on a printed circuit board that is 4 nodes by 4 nodes. Each node is connected to the nodes in front, behind, left and right by tracks on the board, and by pins to the nodes on the boards above and below. On the edges of the board, the tracks which have no 'next neighbour' lead to some sort of reasonably high speed bidirectional serial connection - I'm imagining optical fibre (or possibly pairs of optical fibre, one for each direction). These boards are assembled in stacks of four, and the 'up' pins on the top board and the 'down' pins (or sockets) on the bottom board connect to similar high speed serial connectors.

This unit of 4 boards - 64 compute nodes - now forms both a logical and a physical cube. Let's call this cube module a crystal. Connect left to right, top to bottom and back to front, and you have a hypercube. But take another identical crystal, place it along side, connect the right of crystal A to the left of crystal B and the right of B to the left of A, leaving the tops and bottoms and fronts and backs of those crystals still connected to themselves, and you have a larger cuboid with more compute power and address space but slightly lower path efficiency. Continue in this manner until you have four layers of four crystals, and you have a compute unit of 4096 nodes. So the basic 4x4x4 building block - the 'crystal' - is a good place to start, and it is in some measure affordable to build - low numbers of thousands of pounds, even for a prototype.

I imagine you could get away with a two layer board - you might need more, I'm no expert in these things, but the data tracks between nodes can all go on one layer, and then you can have a raster bus on the other layer which carries power, backup data, and common signals (if needed).

So, each node has 4Gb of memory (or more, or less - 4Gb here is just illustrative). How is that memory organised? It could be treated as a heap, or it could be treated as four separate pages, but it must store four logical blocks of data: its own curated conspage, from which other nodes can request copies of objects; its own private housekeeping data (which can also be a conspage, but from which other nodes can't request copies); its cache of copies of data copied from other nodes; and its heap.

Note that a crystal of 64 nodes each with 4Gb or RAM has a total memory of 256Gb, which easily fits onto a single current generation hard disk or SSD module. So I'm envisaging that either the nodes take turns to back up their memory to backing store all the time during normal operation. They (obviously) don't need to backup their cache, since they don't curate it.

What does this cost? About £15 per processor chip, plus £30 for memory, plus the router, which is custom but probably still in tens of pounds, plus a share of the cost of the board; probably under £100 per node, or £6500 for the 'crystal'.

Pass two: a virtual implementation

OK, OK, this crystal cube is a pretty concept, but let's get real. Using one core of each of 64 chips makes the architecture very concrete, but it's not necessarily efficient, either computationally or financially.

64 core ARM chips already exist:

1. Qualcom Hydra - 64 of 64 bit cores;
2. Macom X-Gene - 64 of 64 bit cores;
2. Phytium Mars - 64 cores, but frustratingly this does not say whether cores are 32 or 64 bit

There are other interesting chips which aren't strictly 64 core:

1. Cavium ThunderX - ARM; 96 cores, each 64 bit, in pairs of two, shipping now;
2. Sparc M8 - 32 of 64 bit cores each capable of 8 concurrent threads; shipping now.

Implementing the virtual hypercube

Of course, these chips are not designed as hypercubes. We can't route our own network of physical connections into the chips, so our communications channels have to be virtual. But we can implement a communications channel as a pair of buffers, an 'upstream' buffer writable by the lower-numbered processor and readable by the higher, and a 'downstream' buffer writable by the higher numbered processor and readable by the lower. Each buffer should be at least big enough to write a whole cons page object into, optionally including a cryptographic signature if that is implemented. Each pair of buffers also needs at least four bits of flags, in order to be able, for each direction, to be able to signal

0. Idle - the processor at the receiving end is idle and can accept work;
1. Busy writing - the processor at the sending end is writing data to the buffer, which is not yet complete;
2. Ready to read - the processor at the sending end has written data to the buffer, and it is complete;
3. Read - the processor at the receiving end has read the current contents of the buffer.

Thus I think it takes at least six clock ticks to write the buffer (set busy-writing, copy four 64 bit words into the buffer, set ready-to-read) and five to read it out - again, more if the messages are cryptographically signed - for an eleven clock tick transfer (the buffers may be allocated in main memory, but in practice they will always live in L2 cache). That's probably cheaper than making a stack frame. All communications channels within the 'crystal' cost exactly the same.

But note! As in the virtual design, a single thread cannot at the same time execute user program and listen to communications from neighbours. So a node has to be able to run two threads. Whether that's two threads on a single core, or two cores per node, is a detail. But it makes the ThunderX and Spark M8 designs look particularly interesting.

But note that there's one huge advantage that this single-chip virtual crystal has over the literal design: all cores access the same memory pool. Consequently, vector space objects never have to be passed hop, hop, hop across the communications network, all can be accessed directly; and to pass a list, all you have to pass is its first cons cell. So any S-Expression can be passed from any node to any of its 6 proximal neighbours in one hop.

There are downsides to this, too. While communication inside the crystal is easier and quicker, communication between crystals becomes a lot more complex and I don't yet even have an idea how it might work. Also, contention on the main address bus, with 64 processors all trying to write to and read from the same memory at the same time, is likely to be horrendous, leading to much lower speed than the solution where each node has its own memory.

On a cost side, you probably fit this all onto one printed circuit board as against the 4 of the 'literal' design; the single processor chip is likely to cost around £400; and the memory will probably be a little cheaper than on the literal design; and you don't need the custom routers, or the connection hardware, or the optical transceivers. So the cost probably looks more like £5,000. Note also that this virtual crystal has 64 bit processors (although address bus contention will almost certainly burn all that advantage and more).

Conclusion

An experimental post-scarcity machine can be built now - and I can almost afford to build it. I don't have the skills, of course; but I can learn.


Sunday, 8 January 2017

Post scarcity: Memory, threads and communication


One benefit of getting really annoyed with Daniel Holden's book on how to Build Your Own Lisp is that I have finally started work on building software for my decade-old Post Scarcity Software idea. There are some problems you don't really see until you start to build something.

Almost all previous Lisps have been primarily single threaded; I think all previous Lisps have been single user. Some problems occur with a multi-threaded, multi-user system which don't occur (or at least aren't problematic) on a single-threaded, single-user system.

In this note I use the words 'thread' and 'process' interchangeably; for the purposes of this argument, there is no difference between a thread and a process.

In a multi-threaded system, whenever one writes to an object, one needs to get an exclusive lock on it, in order to prevent any other thread trying to write to it at the same time. In theory, immutable data gets round this problem, since once a piece of memory is allocated it can't be written to. The problem with that is that memory management requires to keep track of the use of objects, and in typical schemes that involves writing all over the place. Also, memory allocation in a common pool must normally require locks.

Post Scarcity Hardware and the locking problem

The Post Scarcity Hardware proposal partly gets around this problem. Main memory is curated by one process running on one processor which does nothing else but curate main memory. It runs no user space programs, but instead only listens for requests for memory objects from 'normal' processors and streams the requested data over the data bus.

Each 'normal' processor has its own local data pool which both caches data requested from main memory and stores work-in-progress not yet returned to main memory. Each 'normal' processor  runs only a single thread of user-space program (it runs at least one background process managing bus access). But because there are at least hundreds and possibly millions of 'normal' processors the number of concurrent threads can be very large.

However, we don't yet have special purpose Post Scarcity Hardware, so for now Post Scarcity Software has to run on systems with low numbers - a few tens - of processors, running in a common memory pool.

Commodity hardware, and reference counting

I'm still experimenting with reference counting garbage collection. Reference counting garbage collection requires that every time one makes a link to a cell, the reference count on that cell must be updated, so the cell must be locked by one process in order that that update can be carried out. Having a lock on each cell makes every cell bigger, and consequently is expensive of memory. So reference counting makes the problem of multi-threading more difficult than would mark-and-sweep. Does this mean I should abandon reference counting? I don't think so.

The Page Per Thread model

The nature of immutable data is that a thread can 'see' - hold pointers to - only data written by its parent, grandparent or older ancestor threads. It also can't see new data written by its ancestor threads after it was spawned. This is because an older cell, being immutable, cannot hold a pointer to a newer cell. If new data is created by other, concurrent threads, then 'our' thread cannot except by extraordinary mechanisms see that data, and so it can't make links to that data.

A new cell can of course be created with a link to an older cell, but only an older cell which is visible to its process; which is to say, in the normal run of things, only a cell written by its own process or by an ancestor process. But in typical running, cells most frequently link to cells of similar age - to cells only a little bit older, and so, typically, in the same process.

This suggests an optimisation. We're organising cells into pages anyway, for a number of pragmatic reasons. If, instead of a lock-per-cell model, if we have a lock-per-page model we not only save a lot of memory; we also save a lot of contention. Threads can be assigned a page 'of its own' to work with, and, when that page is exhausted, can be assigned further pages. A separate free list is maintained for each page.

This means no thread will contend with other threads when writing new data into memory. Contention with other threads may occur when updating reference counts to older data either written by a still running parent process or by a common ancestor of another still-running thread. So there still needs to be a mechanism for locking pages, and a process must still verify that it has a lock before it can update a reference count, much less write new data. But since it will mostly be working in its own page, waiting for locks will be relatively infrequent.

Note that the 'page per thread' model works equally for mark-and-sweep as for reference counting. Indeed for mark-and-sweep it has an additional benefit - only one thread has to be halted while mark-and-sweep is done.

Communicating in an immutable environment

The problem

If we stick rigidly to the principle that data is immutable, it is impossible to set up a communication channel between two processes, and it is impossible for a process to access, for example, a newer version of some function written since the process was started. Indeed, strictly immutable data means a process cannot see any data written by its grandparent since its parent was spawned, by its great grandparent since its grandparent was spawned, and so on back to the root process. So we cannot create a communication channel between two processes, since neither can see what the other is writing.

If namespaces are implemented as association lists, then namespaces themselves will form trees mapping exactly onto the process tree. A name in a namespace, as visible to a process, will refer to the value it had when its parent was spawned, or to a value written by its parent before it was itself spawned, and so on back, recursively.

This is deeply undesirable. It means that if the root of the process tree - the ultimate ancestor process, equivalent to the init process on UNIX - is kept alive, and a critical software update is deployed in that ancestor, nevertheless that critical software update will not be available to any other process. Windows, of course, needs a reboot after any system update, but that is exactly the sort of crap that post-scarcity software is supposed to be making obsolete.

As I'm envisaging systems which stay up for very long periods - many years - a reboot to deploy new versions of system functions is not acceptable.

But the problem is worse than that. If Anne and Bill are working concurrently on a new bit of software, Bill cannot see the changes Anne has made and vice versa. If they aren't working in the same building, they can't even open a chat channel to one another.

Mutable namespaces

What I think this means is that some (not necessarily all; indeed, very probably not all) namespaces must be mutable. Of course this means that a namespace must have not only a reader access list but also a writer access list. Anything that is to be communicated between concurrent processes, or whose most recent value must be visible to other processes, must be named in a mutable namespace and, if requested by name, the most recently written value must be returned.

In this way system software updates are immediately available to all processes, and people can work collaboratively on the same things. It also provides a very crude mechanism for communication between processes, but I think as a mechanism for communication this is too crude and I shall propose another in a moment.

Automatic revision control in namespaces

If it's possible to rebind a name in a namespace to point to something new, what happens to its previous value? Is it lost and garbage collected, or is it retained as a 'previous version'? Both possibilities are desirable, but if we're serious about 'post scarcity' then economy of store is not a significant issue. I'd prefer automatic revision control to be the default behaviour, so that all previous values were retained and could be explored; so we can ask not only for the current binding of a name but also for a history of its previous bindings and for any particular binding from that history.

Inter-process communication

I already have the concept of read streams and write streams. A pipe can be implemented as a pair of a write stream and a read stream; if there's a shared mutable namespace visible to two processes, possibly owned by different users, then it's possible for one process to advertise a request to communicate to another, and for the other to accept that request.

Obviously if there's a pipe it's possible to print a datastructure to the write end, and for the read end to create a copy; but I believe that it would be desirable also to be able to pass pointers over a pipe, so that instead of Bill being able to make his own local copy of Anne's datastructure he could just link to it directly.

Summary

Multiple processes means that there's potential contention when writing to memory; a fairly simple segmentation of writable memory should make it much less onerous. Immutable data makes interprocess communication hard; some relaxation of immutability is needed to make it possible.

Creative Commons Licence
The fool on the hill by Simon Brooke is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License