From papierfalter at yahoo.de Mon Aug 14 08:13:48 2006 From: papierfalter at yahoo.de (Wolfram Fischer) Date: Mon Aug 14 10:04:05 2006 Subject: [icfp-discuss] UM in PLT-Scheme Message-ID: Hi, I'm learning Scheme and so I tried to write the UM in Scheme... The result was amazing to me: The Scheme UM runns the Benchmark in 3.52m (compiled with mzc without optimisations) - I guess a more experienced Scheme programmer who is also familiar with the tools (plt-scheme) could get better results. My C implementation (with cache for small array allocations) runs in ~1.0m, without any boundary checks etc. I attached my scheme source for everyone interested and I'd like to hear suggestions/hints/etc. :-) best regards, Wolf -- style (noun) 3. way of writing or performing: the way in which something is written or performed as distinct from the content of the writing or performance. Encarta Dictionary: English (North America) -------------- next part -------------- A non-text attachment was scrubbed... Name: um32sm.scm Type: application/octet-stream Size: 5141 bytes Desc: not available Url : http://lists.andrew.cmu.edu/pipermail/icfpcontest-discuss/attachments/20060814/58744b99/um32sm.obj From windenntw at gmail.com Tue Aug 15 15:54:45 2006 From: windenntw at gmail.com (Antonio Vargas) Date: Tue Aug 15 15:54:48 2006 Subject: [icfp-discuss] The "Eigenratio" of Self-Interpreters In-Reply-To: <000c01c6be81$91f2b9a0$0301a8c0@Owhango1> References: <44DA7C85.3060202@cs.cmu.edu> <000c01c6be81$91f2b9a0$0301a8c0@Owhango1> Message-ID: <69304d110608151254q2435b5a5u9affc8eedfe4cf40@mail.gmail.com> On 8/13/06, Clive Gifford wrote: > Greetings > * really big snip* > Clive Gifford > this explanation was really nice... don't know if it's common knowledge or not but anyways i dont recall ever seeing any website explainig any sort of comp-arch complexity measurement with this argument... mind you upping it somewhre on the web? i can host on my site (with full attrib ofcourse) if you want... -- Greetz, Antonio Vargas aka winden of network http://network.amigascne.org/ windNOenSPAMntw@gmail.com thesameasabove@amigascne.org Every day, every year you have to work you have to study you have to scene. From clive at xtra.co.nz Wed Aug 16 00:21:06 2006 From: clive at xtra.co.nz (Clive Gifford) Date: Wed Aug 16 00:21:43 2006 Subject: [icfp-discuss] The "Eigenratio" of Self-Interpreters References: <44DA7C85.3060202@cs.cmu.edu><000c01c6be81$91f2b9a0$0301a8c0@Owhango1> <69304d110608151254q2435b5a5u9affc8eedfe4cf40@mail.gmail.com> Message-ID: <000e01c6c0eb$6b387ef0$0301a8c0@Owhango1> "Antonio Vargas" wrote: > this explanation was really nice... Thanks. It could have been shorter and clearer but I was in a hurry to write *something* about before I got run over by a bus and and the idea of an "eigenratio" (possibly) disappeared forever! :-) > mind you upping it somewhre on the web? i can host on my > site (with full attrib ofcourse) if you want... Thanks for the offer. I'm still playing around with this whole thing. Unless someone points out that it's all been done before (or similar) then I will probably find some place on the web where I can write it up a bit more carefully and perhaps also add some further thoughts later if it seems appropriate. I'll let you know when and where later if you're still interested. Cheers Clive From rherb at microsoft.com Wed Aug 16 06:32:12 2006 From: rherb at microsoft.com (Ralf Herbrich) Date: Wed Aug 16 08:20:37 2006 Subject: [icfp-discuss] A faster UM. In-Reply-To: <20060805033226.GB29642@panix.com> References: <20060801094000.GA19452@panix.com> <20060805033226.GB29642@panix.com> Message-ID: <89575F4410F07F4985C7B936EB6061E60667DC36@EUR-MSG-10.europe.corp.microsoft.com> There is an interesting article about a UM written in F# at http://cs.hubfs.net/blogs/f_team/archive/2006/08/15/506.aspx. The benchmark takes ~65 seconds to run on a 3Ghz Xeon (which is comparable to pure C implementations). Ralf Herbrich -----Original Message----- From: icfpcontest-discuss-bounces@lists.andrew.cmu.edu [mailto:icfpcontest-discuss-bounces@lists.andrew.cmu.edu] On Behalf Of Jed Davis Sent: 05 August 2006 04:32 To: icfpcontest-discuss@lists.andrew.cmu.edu Subject: Re: [icfp-discuss] A faster UM. On Wed, Aug 02, 2006 at 01:01:04AM +0100, Ganesh Sittampalam wrote: > On Tue, 1 Aug 2006, Jed Davis wrote: > > >there was only so much that could be done within the confines of > >translating each UM insn into exactly 12 bytes of '386 code, and > >allowing branches to arbitrary locations of same > > I guess the "exactly 12 bytes" restriction is so you can compute > branches quickly? Some of that; and also so that individual instructions could, before I added on the VM trapping and such, be replaced individually in the case of self-modification (real or apparent). > How about having two versions of the code. One that obeys this > restriction, and another that allows both variable length and > cross-instruction optimisations. Every so often in the optimised > version, you can have a "resync point" across which optimisations are disabled. > Then replace the corresponding instruction in the unoptimised version > with a branch to this point. This is pretty much what I converged on independently while, uh, not checking my ICFP mailbox the past few days -- except that I'll be extracting assumptions from the initial register state, like "r6 is always 0", which I expect to hold over all uses of the code, and checking them as a condition for entry into the fast path. (I hate writing in the future tense like that, because then if it doesn't work for some reason....) -- (let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map ((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l)))))) (lambda (f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l)) (C k))))))) '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline))))) _______________________________________________ icfpcontest-discuss mailing list icfpcontest-discuss@lists.andrew.cmu.edu https://lists.andrew.cmu.edu/mailman/listinfo/icfpcontest-discuss From clive at xtra.co.nz Thu Aug 17 18:11:16 2006 From: clive at xtra.co.nz (Clive Gifford) Date: Thu Aug 17 18:12:07 2006 Subject: [icfp-discuss] The "Eigenratio" of Self-Interpreters References: <44DA7C85.3060202@cs.cmu.edu><000c01c6be81$91f2b9a0$0301a8c0@Owhango1><69304d110608151254q2435b5a5u9affc8eedfe4cf40@mail.gmail.com> <000e01c6c0eb$6b387ef0$0301a8c0@Owhango1> Message-ID: <002d01c6c24a$137b6460$0301a8c0@Owhango1> I'm trying to bring this thread back "on topic" (kind of).... Yesterday I thought I'd look at the organisers' self-interpreter (um.um) and see if I could build the corresponding matrix (as I described in my first post to this thread), and then calculate the "eigenratio" for this interpreter (= dominant eigenvalue of that matrix). I knew that my earlier description was probably a bit simplistic in some respects, although at the same time I (optimistically?) thought there was probably some way around that. The matrix I obtained (with some "simplifications" - described in more detail later) is: | 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 | | 6, 6, 6, 5, 5, 5, 5, 3, 4, 4, 4, 3, 5, 3 | | 1, 1, 1, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1 | | 2, 3, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3 | | 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 | | 3, 3, 3, 3, 3, 4, 3, 1, 2, 1, 1, 1, 2, 2 | | 6, 6, 6, 6, 6, 6, 7, 0, 4, 2, 2, 2, 4, 4 | | 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 | | 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 | | 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 | | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 | | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 | | 2, 3, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 1 | | 4, 8, 8, 4, 4, 4, 4, 3, 4, 3, 3, 3, 7, 4 | The first row/column is for opcode 0 (Conditional Move) and then all the others follow in numerical order until you get to the rightmost column and bottom row which correspond to operator 13. So, by reading down the first column (which corresponds to the sections of code executed in um.um whenever it is simulating a single opcode 0 from the next level up), we can see that um.um executes opcode 0 once, opcode 1 six times, opcode 2 once, opcode 3 twice, etc., etc. Reading across the rows shows us how often um.um is executing each instruction in the course of simulating the behaviour of other instructions. There are a number of rows that have juts a single count of 1 and are 0 elsewhere. These rows are instructions that um.um doesn't use except in a single place (in order to delegate the handling to the next level *down*). The first such row is for the multiplication instruction. Anyway, the dominant eigenvalue for this matrix is 24.4669... which agrees very closely with what I had seen in my "experiments". I obtained the matrix by first doing a kind of flow analysis of um.um and then wrote a short bit of code to use the results of that to count the different instructions used to in different sections of um.um and hence generate the matrix. But, as mentioned earlier, I had to make some simplifications because um.um includes some conditional branching and looping within its own code where it is simulating a single instruction from the "next level up". In particular it does this for opcodes 1 and 2 (with some different handling for array 0 from any other array) and also for opcode 12 (where as well as the business of skipping the array copy if the source is itself (0), it also has a loop to copy the contents of the source array when the source is not 0). That branching and looping makes counting the instructions executed rather difficult! At first I thought I could "decompose" these instructions that had multiple execution paths into some kind of micro ops, each with their own column and rows in the matrix. But that doesn't really work in any "easy way" because you can't generally look at an arbitrary piece UM code that (for example) is using opcode 1 (array index) and determine if it addressing array 0 or not. It depends on what register B holds. ("B" for bugger! Please excuse my "bad language". :-) However, after looking at the code a bit more I realised that (in this case at least) I could in fact make some reasonable assumptions. Um.um is always addressing array 0 in its "own code" and doesn't ever replace its own array 0 with anything else. So the matrix above is simplified in the sense that it only describes the situation correctly for the simulation of ops 1, 2, and 12 when register B is also zero. My earlier experiments with inventing my own VM complete with simple instruction set and then writing a self-interpreter for it didn't have this behaviour and so it was possible to derive the exact "characteristic matrix" for the interpreter directly and without complications. Obviously the real world is harder. For something like the UM language and um.um self-interpreter it might still be possible to do some kind of recursive, iterative analysis first to converge on a final version of the matrix that is "accurate" for an infinitely high "stack" (maybe the word "tower" is better?) of interpreters interpreting each other. This is pure speculation, and I have no idea how to do that or if it is even possible! But if something like that is possible, then perhaps the simplified matrix I'd given above is in fact the same result for um.um, which it turns means the "eigenratio" of 24.4669... is also correct. There are a bunch of other assumptions that I've made also. Even if you can describe build the matrix for a given self-interpreter exactly, do we know it will always exhibit the "convergence" that is desired (as per the Power Iteration algorithm to find the dominant eigenvalue and corresponding eigenvector)? I suspect it does but haven't found any proof. The matrix is non-negative (all values >= 0) and the same applies to the other vectors that are part of the series of matrix operations that can be used to describe multiple interpreters "running each other" in a tower of arbitrary size. That may be sufficient to imply convergence. Any matrix theory experts out there? Just for completeness, my incomplete examination of um.um's internals indicates the following: 000-009: Start-up (mainly NOPs in effect as these platters ultimately used for as the registers of the next level up and perhaps "execution finger" also. 010-017: Executed during start-up, but is also used to handle opcode 13. 018-027: Decode opcode and dispatch according to following table. 028-041: Addresses for code handling each of the 14 instructions. 042-056: Handle opcode 0. 057-065: Lead in for opcode 1, determine if reg B is 0. 066-077: Handle opcode 1 when reg B is 0. 078-089: Handle opcode 1 when reg B is not 0. 090-098:: Lead in for opcode 2, determine if reg B is 0. 099-110: Handle opcode 2 when reg B is 0. 111-122: Handle opcode 2 when reg B is not 0. 123-136: Handle opcode 3. 137-150: Handle opcode 4. 151-164: Handle opcode 5. 165-178: Handle opcode 6. 179-179: Handle opcode 7 (nothing too complex here!). 180-191: Handle opcode 8. 192-196: Handle opcode 9. 197-201: Handle opcode 10. 202-206: Handle opcode 11. 207-215: Lead in for opcode 12, determine if reg B is 0. 216-221: Handle opcode 12 when reg B is 0. 222-254: Handle opcode 12 when reg B is not 0 (create new array and copy contents of source array to it). 255-255: Platter (initially 0) storing the id of the program array for the "next level up". The simplified matrix given earlier therefore ignores instructions in platters 78-89, 111-122 and 222-254. Cheers Clive From dhebert at uci.edu Thu Aug 17 18:30:32 2006 From: dhebert at uci.edu (dhebert@uci.edu) Date: Thu Aug 17 18:30:35 2006 Subject: [icfp-discuss] Eigenratios Message-ID: <2768.130.221.81.163.1155853832.squirrel@webmail.uci.edu> Um, just a little suggestion since I noticed you were having some trouble with certain ops being handled differently under different cirucmstances (such as register B being zero). Why not just expand the matrix and treat those ops as if they were multiple distinct ops? Thus you would have something like 15 or 16 total ops and rows and columns in the matrix, but the results should work out the same. Unless I have no clue what I'm talking about. From clive at xtra.co.nz Thu Aug 17 19:01:00 2006 From: clive at xtra.co.nz (Clive Gifford) Date: Thu Aug 17 19:01:48 2006 Subject: [icfp-discuss] Eigenratios Message-ID: <003401c6c251$07b882f0$0301a8c0@Owhango1> From: > Um, just a little suggestion since I noticed you were having some trouble > with certain ops being handled differently under different cirucmstances > (such as register B being zero). Why not just expand the matrix and treat > those ops as if they were multiple distinct ops? Thus you would have > something like 15 or 16 total ops and rows and columns in the matrix, but > the results should work out the same. Unless I have no clue what I'm > talking about. Yeah - that's exactly what I thought at first also. In fact I started out by doing that, but then realised partway through (doh!) that you can't work out which "distinct op" column to increment when you see (for example, op 1) in the code execution path, because unless you are looking at it at runtime, you don't (generally) know if register B is 0 or not. You can put the extra columns in place, but I can't see how you can (in general) work out which one to use. Does that makes sense?! Then we also have the "ugly" op 12, which in um.um is handled (for reg B != 0) by creating a new array and copying (in a loop) all of the source to the destination. The size of the array being copied is variable so the number of times the instructions in that loop are executed is also variable. I'm still trying to get some kind of feeling for how wide a domain the idea of an "eigenratio" can be applied to really is. Does it only "work" for some class of low level "machine languages"? Can you get an eigenratio for some high level language self-interpreter without considering the implementation details? Does the whole concept require "fixed cost" per "instruction"? Or perhaps just that the cost have some upper bound?? What about self-interpreters for completely different kinds of architectures? Quantum computers anybody? (Probably find the eigenratio can be a complex number!) What does an eigenratio really tell us anyway? To borrow a phrase I saw recently, "I think I just sprained my brain"! (But I'm enjoying it all the same. :-) Clive From windenntw at gmail.com Fri Aug 18 14:24:29 2006 From: windenntw at gmail.com (Antonio Vargas) Date: Fri Aug 18 14:24:32 2006 Subject: [icfp-discuss] Eigenratios In-Reply-To: <003401c6c251$07b882f0$0301a8c0@Owhango1> References: <003401c6c251$07b882f0$0301a8c0@Owhango1> Message-ID: <69304d110608181124i55c80397o606a2a10b7062711@mail.gmail.com> On 8/18/06, Clive Gifford wrote: > From: > > > Um, just a little suggestion since I noticed you were having some trouble > > with certain ops being handled differently under different cirucmstances > > (such as register B being zero). Why not just expand the matrix and treat > > those ops as if they were multiple distinct ops? Thus you would have > > something like 15 or 16 total ops and rows and columns in the matrix, but > > the results should work out the same. Unless I have no clue what I'm > > talking about. > > Yeah - that's exactly what I thought at first also. In fact I started out by > doing that, but then realised partway through (doh!) that you can't work out > which "distinct op" column to increment when you see (for example, op 1) in > the code execution path, because unless you are looking at it at runtime, > you don't (generally) know if register B is 0 or not. You can put the extra > columns in place, but I can't see how you can (in general) work out which > one to use. Does that makes sense?! > > Then we also have the "ugly" op 12, which in um.um is handled (for reg B != > 0) by creating a new array and copying (in a loop) all of the source to the > destination. The size of the array being copied is variable so the number of > times the instructions in that loop are executed is also variable. > > I'm still trying to get some kind of feeling for how wide a domain the idea > of an "eigenratio" can be applied to really is. > > Does it only "work" for some class of low level "machine languages"? All high level languages depend on lower level ones, and so you can either measure the lower one and correlate sequences later, or the higher one directly. The problem here is that high level systems have a lot of different operations. For example on PowerPC OSX running on Apple hardware, you get a program with the developer tools that allows you to enable and see the performance counters both for the cpu, the main memory controller and also virtual counters provided by the OS such as context switches and the like... the hardware counters provide all counters you could ever need at low level detail, but of course the OS does not provide a counter for each single function call it does internally since that would be too costly. > Can you get an eigenratio for some high level language self-interpreter > without considering the implementation details? I think yes, if you only consider an upper bound or interval for the high level instructions. > Does the whole concept require "fixed cost" per "instruction"? Or perhaps > just that the cost have some upper bound?? Having a fixed cost or measuring with upper bounds is IIRC special cases of doing your matrix calculations with intervals instead of numbers, which is sometimes use for bounding errors in calculations. Anyways, what you are doing is taking a form of limit when you scale from 1 layer of emulation to N... so modifying the first layer so that it keeps a count of different instructions types with regard both to static and dynamic conditions is not going to change the overall limit provided you measure a big enough tower of emulators. maintaining the count for simple instructions is then as simple as an increment, and for complex ones, you can divide by cases... for the "op12" case, you divide in 2 ways: one that only changes the instruction pointer (and incs the ip-change counter) and another one that also copies the arrays (and adds the number of data copies to the data-copy counter. This reduces the statistics accounting to O(1) and thus should not change your overall limit when you tower um over um over um. My math is rusty at best, but I recall that taking a limit on the max of a function is not a problem provided the function is "well behaved" such as it's continous and the like... Also the fact that some instructions do more or less work depending on different dynamic status means that the matrix can't be fixed, and that only intervals or averages or 90-percentiles or somesuch calculation is going to give a reliable information. > What about self-interpreters for completely different kinds of > architectures? Quantum computers anybody? (Probably find the eigenratio can > be a complex number!) > What does an eigenratio really tell us anyway? That a OISC machine with only sub-and-jump-if-negative instruction is __measurably__ crappier than a real machine... btw which instruction sets did you use for your tests? > To borrow a phrase I saw recently, "I think I just sprained my brain"! (But > I'm enjoying it all the same. :-) > > Clive > > _______________________________________________ > icfpcontest-discuss mailing list > icfpcontest-discuss@lists.andrew.cmu.edu > https://lists.andrew.cmu.edu/mailman/listinfo/icfpcontest-discuss > -- Greetz, Antonio Vargas aka winden of network http://network.amigascne.org/ windNOenSPAMntw@gmail.com thesameasabove@amigascne.org Every day, every year you have to work you have to study you have to scene. From clive at xtra.co.nz Fri Aug 18 23:46:06 2006 From: clive at xtra.co.nz (Clive Gifford) Date: Fri Aug 18 23:47:00 2006 Subject: [icfp-discuss] Eigenratios References: <003401c6c251$07b882f0$0301a8c0@Owhango1> <69304d110608181124i55c80397o606a2a10b7062711@mail.gmail.com> Message-ID: <000901c6c342$047ebb30$0301a8c0@Owhango1> On 19 Aug 2006, Antonio Vargas wrote: > On 8/18/06, Clive Gifford wrote: > .... > > I'm still trying to get some kind of feeling for how wide a domain the idea > > of an "eigenratio" can be applied to really is. > > > > Does it only "work" for some class of low level "machine languages"? > > All high level languages depend on lower level ones, and so you can > either measure the lower one and correlate sequences later, or the > higher one directly. > > > Can you get an eigenratio for some high level language self-interpreter > > without considering the implementation details? > > I think yes, if you only consider an upper bound or interval for the > high level instructions. > > > Does the whole concept require "fixed cost" per "instruction"? Or perhaps > > just that the cost have some upper bound?? > > Having a fixed cost or measuring with upper bounds is IIRC special > cases of doing your matrix calculations with intervals instead of > numbers, which is sometimes use for bounding errors in calculations. > > Anyways, what you are doing is taking a form of limit when you scale > from 1 layer of emulation to N... so modifying the first layer so that > it keeps a count of different instructions types with regard both to > static and dynamic conditions is not going to change the overall limit > provided you measure a big enough tower of emulators. maintaining the > count for simple instructions is then as simple as an increment, and > for complex ones, you can divide by cases... for the "op12" case, you > divide in 2 ways: one that only changes the instruction pointer (and > incs the ip-change counter) and another one that also copies the > arrays (and adds the number of data copies to the data-copy counter. > This reduces the statistics accounting to O(1) and thus should not > change your overall limit when you tower um over um over um. > > My math is rusty at best, but I recall that taking a limit on the max > of a function is not a problem provided the function is "well behaved" > such as it's continous and the like... > > Also the fact that some instructions do more or less work depending on > different dynamic status means that the matrix can't be fixed, and > that only intervals or averages or 90-percentiles or somesuch > calculation is going to give a reliable information. > > > What about self-interpreters for completely different kinds of > > architectures? Quantum computers anybody? (Probably find the eigenratio can > > be a complex number!) > > What does an eigenratio really tell us anyway? > > That a OISC machine with only sub-and-jump-if-negative instruction is > __measurably__ crappier than a real machine... btw which instruction > sets did you use for your tests? Thanks for your response Antonio. My maths is almost certainly even more rusty than yours but after thinking about what you have said for little while I think I agree with pretty much all of it. I was particularly interested in what you said about matrix calculations with intervals - because I was just about ready to announce that I had "discovered" that also. :-) Anyway, I've now put some of my ramblings concerning stacks/towers of self-interpreters and eigenratios here: htttp://eigenratios.blogspot.com What is there now is mainly just rehashed versions of what I've previously posted here. But I hope to add more later so to avoid double handling I won't attempt to respond to all your points in detail right now. Instead I'll just outline the initial instruction set I used. (I added to this later.) Let's say memory is a (potentially infinite) array of words, each addressed by a non-negative integer. Each memory location is capable of holding any integer value: Op 0: HALT (Execution stops) Op 1: *addr = value (Set word at addr to value) Op 2: *addr1 = *addr2 + *addr3 (Add contents of addr2 and addr3 and store in addr1) Op 3: SWITCH *index table (multi-way branch using sequence of addresses at location 'table' indexed by contents of 'index'. Op 4: **addr1 = *addr2 (copy contents of addr2 to location pointed to by value in addr1) Op 5: *addr1 = **addr2 (copy value stored in location pointed to by contents of addr2 to location at addr1) Actually, there was an "Op 6" also but that was just for debugging really - spat out the contents of a given memory address). I didn't put too much effort into producing a complete and robust spec. I'm lazy like that. Cost cutting measures... you can use 32 bit unsigned ints for memory and addresses instead, with overflow in Op 2 leading to "undefined behaviour". 16 bits is probably even acceptable okay if you're short of memory on your "real machine"! :-) My second version added a "complex" instruction that replaced the sequence below (for reading and adjusting an address type operand from the "next level up") with a new single instruction needing four operands! *arg = *ip + *offset *arg = **arg *arg = *arg + *length The third version added: **addr1 = **addr2 The fourth version (not previously mentioned, allowing my self-interpreter to achieve an eigenratio of 10.74...) modified the original Op3 so the first operand needed to be de-referenced twice to get the offset into the dispatch table. At one point I did wonder about a two instruction set computer.... something like this: Op 0: HALT Op 1: MAGIC (Run/Interpret programme loaded at (ip + 2)) So, we could have the following "programs": HALT (hopefully bug-free) or MAGIC HALT HALT << Program being interpreted... or MAGIC HALT MAGIC HALT HALT etc. But that was when I decide there had to be a fixed non-zero cost (now perhaps a fixed lower and upper bound, both > 0?) for each instruction (plus an implementation to prove it was a workable idea!) Of course, with only two instructions we can use a single bit for each so the assembler is quite easy to write... Cheers Clive