<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Orthogonality and invariants --> <!--X-From-R13: [vebfyni Evybivp <fvybivpNmrfbv.sre.ue> --> <!--X-Date: Wed, 05 Apr 2000 08:27:08 -0700 --> <!--X-Message-Id: 7eln2s3bp2.fsf#zesoi,fer.hr --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Orthogonality and invariants</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:silovic#zesoi,fer.hr"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00059.html">Previous</a> | <a href="msg00062.html">Next</a> ] Thread: [ <a href="msg00068.html">Previous</a> | <a href="msg00065.html">Next</a> ] Index: [ <A HREF="author.html#00060">Author</A> | <A HREF="#00060">Date</A> | <A HREF="thread.html#00060">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Orthogonality and invariants</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] Orthogonality and invariants</LI> <LI><em>From</em>: Miroslav Silovic <<A HREF="mailto:silovic#zesoi,fer.hr">silovic#zesoi,fer.hr</A>></LI> <LI><em>Date</em>: 05 Apr 2000 15:43:37 +0200</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> Okay, I've been prompted by the previous programming language discussion to write a quick essay. Feel free to dissect/flame. :) First, in my experience, the main time-sink in writing MUDs is not coding per se, it's debugging. In most 1,000,000 line applications, you won't even notice a crash every 12 hours, or a memory leak that fills the swap after a couple of days - this is because most applications don't run for hours, let alone days. A MUD that crashes daily is (in my experience) unplayable. This goes especially for persistent MUDs that don't even see regular reboots more often than twice per year. So, MUD servers (and more generally, application servers) have EXTREMELY severe stability constraint: they have to be able to run stably for months, without visible bloat, fd leak, heap corruption, thread forking, thread blocking, and all other types of weirdness that plague applications. Several MUD codebases already reached this plateaou (MOO, various types of MUSH, Cold are those I know about for sure). I don't think that a less stable codebase can compete at all (because crashes and losses are just too annoying to bother with - especially with all those stable MUDs laying around). Now... the topic is achieving this stability. The main issue, IMHO, is the lack of orthogonality, and orthogonality is lost each time you have to spread functionality that logically belongs to the same unit throughout the code (I'll use the word orthogonality to mean funcionality separation along logical, rather than pragmatic boundaries). Let's start with a canonic example: memory management in C. Each time you need a chunk of memory, you request it from the system, and each time you don't need it any more, you free it. The problem, as anybody who tried to debug memory leaks can tell, is that you have to code memory management each time you want to deal with memory - i.e. throughout the program. Wouldn't it be nicer if you could just point at a big chunk of code and just say, "That thing manages my memory. Touch only if memory management is broken, and then that's the place responsible." -- this is exactly what garbage collectors do. This example illustrates one related issue: dynamic invariants (namely, the statements that must hold true, and can not always be checked just by reading the program source). The C malloc/free paradigm sets one such invariant: 'each path of control that allocates a memory block must contain a free with that same block' (it posts some more dynamic invariants, for example, 'a block passed to the free call must have been allocated with malloc call and it must not have been already freed', but let's keep the focus). Now, since C compiler can not check this (and it'd require really hellishly powerful lint, as well as limits on the use of malloc/free, to check this statically), the programmer has to worry about this each time. Since programmers *always* make mistakes, this invariant will *not* hold true in a freshly written code. The lack of orthogonality, in this case, manifests itself in the fact that in practice it's highly nontrivial to check for dynamic invariant breakage. So, let's state two principles of orthogonality: 1. Whenever it's possible to reorganise the code so that distributed functionality can be sequestrated into a module, it should be done so, even when the cost is a (reasonably small) loss of performance. 2. The code should not have dynamic invariants. There are also some classical orthogonality principles (I assume they're well-known to the more technically oriented people here): 3. Functions shouldn't have side-effects (and more generally, broader language constructs, such as objects, classes, or defmacro constructs in LISP, shouldn't have side-effects) Okay, to conclude, here are some common sources of orthogonality breaks: Resource management ------------------- The C example above can be extended to cover broad range of idioms: malloc/free, mutex lock/unlock, file open/close, socket accept/close, and socket connect/disconnect. In each of these cases, there are two functions (let's call them mumble and unmumble), with the following dynamic invariant: each path of control that contains mumble(object) must contain unmumble(object) such that it executes after the object has been mumbled, and such that there is no other mumble or unmumble between it and the opening mumble. Now, there are two ways of removing this invariant: First, for malloc/free pair, you can use garbage collector. It works by taking the snapshot of your system and finding all the allocated resources at that moment, and then finds the resources that the code can't use (because it doesn't have references to them). Those resources get released. The other way is with construct in LISP: (with-mumbled-object (object) code...) This construct does mumble(object), executed the code, and then unmumbles the object. If this is the only way for the object to ever get mumbled, this code will never break the invariant. This is also how constructor/destructor pairs work in C++. Now, if your system supports nonlocal exits (throws, exceptions, conditions - whatever name you're used to), with will have to catch the throw, unmumble the object, and pass the throw onward (this is why exceptions in C++ cause the codesize to increase by 30-50% - every block that has constructor/destructor pair will also have to trap the exception and handle the cleanup before passing it on). In my experience, this is the main reason to use garbage collection - you can have exceptions without unwinding (more or less) each block that has variables in it. Note that reference counting does NOT solve the memory management issue - it simply moves the issue from malloc/free (pointer) to grab/ungrab (reference). Also, circular references HEAVILY complicate the issues - but certain MUD languages are designed to make circular references impossible. Object persistence ------------------ All MUDs have to handle persistence in some way - if nothing, they have to save the snapshot of all the players before each reboot. Now, the raw LPMUD handles this by providing save function (I'm not sure if it's in the LPMUD driver or mudlib). So, if you want the object saved, you do something like save(object), whenever the object has changed. So, here's the dynamic invariant: each persistent object that has been changed has to be saved. Breaking this invariant causes the well-known Bubba shouts 'wheres my gear?!?!?!' Again you can implement persistence library, one that places each loaded object on a list that is guaranteed to get saved before the process terminates. However, there is another, related issue: how to automate object loads? If your objects are indirected (i.e. implemented via some abstract reference type), you can just check for the load status each time you transform the reference to the actual object pointer (Cold and MOO do this). You can also use object pointers that point to write-protected pages and then load the objects from segfault handler (this is done by Texas Persistent Store, and despite the technical coolness, it's unfortunately quite slow). Database integrity ------------------ Each working MUD has a large number of invariants that are rarely, if ever, checked (remember, in C, ASSERT macro is your friend). For example, for each container, the location of each object within the container must be the container itself It's quite interesting that some languages (Eiffel) actually support class invariants - statements that are true for each instance of the class and get checked on a regular basis. Languages with a MOP (Common LISP and the new, yet-to-be-released Python) can implement this on top of their existing object systems. While class invariants don't eliminate dynamic invariants, they at least cause the program to complain now rather than later. Transactional integrity ----------------------- While forgetting to unlock the mutexes falls under resource management, forgetting to lock them in the first place is a beast in its own right. There have been some articles on this list (including those by me and JCL) that cover this. The invariant here is non-reentrant code should be protected by a mutex My solution to this is to put mutexes on each object and handle the deadlocks automatically - recent post on dgd mailing list suggests that they took the same approach; JC instead makes all the code reentrant by copying and timestamping objects). I'd be really interested in a solution to this that is generic (i.e. would work for any application server, not just a MUD server), and that doesn't have performance penalty of the solutions above. -- How to eff the ineffable? _______________________________________________ MUD-Dev mailing list MUD-Dev#kanga,nu <A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</A> </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="00065" HREF="msg00065.html">Uptime numbers (was Re: [MUD-Dev] Orthogonality and invariants)</A></strong> <ul compact><li><em>From:</em> "Jay Carlson" <nop#mitre,org></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00059.html">Re: [MUD-Dev] Re: J (was: Re: 16K mud server competition !)</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00062.html">Re: [MUD-Dev] MUD-Dev request rejected (fwd)</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00068.html">Re: [MUD-Dev] Object and class heirarchies -- are they reallynecessary?</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00065.html">Uptime numbers (was Re: [MUD-Dev] Orthogonality and invariants)</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00060"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00060"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><strong><A NAME="00071" HREF="msg00071.html">[MUD-Dev] Schmuse</A></strong>, J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Thu 06 Apr 2000, 05:44 GMT <LI><strong><A NAME="00068" HREF="msg00068.html">Re: [MUD-Dev] Object and class heirarchies -- are they reallynecessary?</A></strong>, Brandon J. Rickman <a href="mailto:dr.k#pc4,zennet.com">dr.k#pc4,zennet.com</a>, Wed 05 Apr 2000, 21:32 GMT <LI><strong><A NAME="00060" HREF="msg00060.html">[MUD-Dev] Orthogonality and invariants</A></strong>, Miroslav Silovic <a href="mailto:silovic#zesoi,fer.hr">silovic#zesoi,fer.hr</a>, Wed 05 Apr 2000, 15:27 GMT <UL> <LI><strong><A NAME="00065" HREF="msg00065.html">Uptime numbers (was Re: [MUD-Dev] Orthogonality and invariants)</A></strong>, Jay Carlson <a href="mailto:nop#mitre,org">nop#mitre,org</a>, Wed 05 Apr 2000, 20:06 GMT <UL> <LI><strong><A NAME="00069" HREF="msg00069.html">Re: Uptime numbers (was Re: [MUD-Dev] Orthogonality and invariants)</A></strong>, Ben Greear <a href="mailto:greearb#candelatech,com">greearb#candelatech,com</a>, Thu 06 Apr 2000, 03:16 GMT </LI> </UL> </LI> </UL> <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00070" HREF="msg00070.html">Re: [MUD-Dev] Orthogonality and invariants</A></strong>, cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Thu 06 Apr 2000, 04:52 GMT </LI> </UL> </LI> <LI><strong><A NAME="00057" HREF="msg00057.html">[MUD-Dev] MUD-Dev request rejected (fwd)</A></strong>, Matthew Mihaly <a href="mailto:the_logos#achaea,mudservices.com">the_logos#achaea,mudservices.com</a>, Wed 05 Apr 2000, 06:40 GMT </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>