Self Modifying Code - Some Later Insight From Dijkstra That Is Surprising
soshimo
Posts: 215
Circa 1999
I am jumping down to assembler for a new requirement and when I first read that you had to self modify code in order to do indexed addressing I was at first a little hesitant. After all, it goes against everything I've ever been taught in the last 20 years or so. I'm probably a pup compared to some of you, but I've always felt comfortable with index registers and understood them at a very basic level. There are lots of analogies to compare them against.
We all know that Dijkstra may or may not have said that self modifying code is harmful but the above statement made during a keynote speech in 1999 points out that he didn't understand the difference between code and data at the time. Of course, after years of study he realized that there is a distinction and the two can actually share the same space and quite often do. At least that's my take on the statement. Here's a link to the entire address to get a context of what he was talking about: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1284.html.
This implies, without really admitting it, that he was naive to self-modifying code in his earlier years and if he did make that statement it was based on an incorrect understanding of his industry. With proper code management and structure writing self-modifying code does seem as natural as using indexed registers as long as you think of the program location as really data.
These are my early observations after my first foray into assembler for the prop in earnest.
E.W Dijkstra said...
The reason I had been unable to design that program was that at the time I was programming in a machine code in which, due to the absence of index registers, programs had to modify their own instructions in store, and, as a consequence, my poor, uneducated head did not know how to make the distinction between the program on the one hand and the variables it operated upon on the other hand.
I am jumping down to assembler for a new requirement and when I first read that you had to self modify code in order to do indexed addressing I was at first a little hesitant. After all, it goes against everything I've ever been taught in the last 20 years or so. I'm probably a pup compared to some of you, but I've always felt comfortable with index registers and understood them at a very basic level. There are lots of analogies to compare them against.
We all know that Dijkstra may or may not have said that self modifying code is harmful but the above statement made during a keynote speech in 1999 points out that he didn't understand the difference between code and data at the time. Of course, after years of study he realized that there is a distinction and the two can actually share the same space and quite often do. At least that's my take on the statement. Here's a link to the entire address to get a context of what he was talking about: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1284.html.
This implies, without really admitting it, that he was naive to self-modifying code in his earlier years and if he did make that statement it was based on an incorrect understanding of his industry. With proper code management and structure writing self-modifying code does seem as natural as using indexed registers as long as you think of the program location as really data.
These are my early observations after my first foray into assembler for the prop in earnest.
Comments
Another example of JMPRET's self-modifying advantages (abetted by the instruction pipeline) is its use in "ping-pong" coroutine implementation. You can see examples of this in a many of Chip's programs.
-Phil
Just mention stack unwinding
I had similar observations. My experience, prior to the Propeller was with register to memory designs. Not having an index register, as well as using an instruction long to hold a constant, such as a mask, seemed limiting. Additionally, the model was clear. There was the CPU, and then there was memory.
The interesting thing about the propeller is that code and data do, in fact, share the same space in the COG, and are differentiated in the more traditional fashion, more of the time in the HUB. The sharing is forced in such a way as to make one seriously reconsider what is code and what is data?
Fetch a jump instruction, based on a number, added to a base table address, then execute it, for example. The jump instruction starts out as a data element, then transitions to being a code element. Doing this kind of thing is easy on the prop. What's hard is thinking to actually do it!
Fun stuff!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
Self-modifying code also really only works well on Von Neumann architectures, as on Harvard there is usually a hefty penalty moving data between the address spaces.
Debugging self-modifying code can be harder, as not only the state of the data needs to be examined, but the state of the program as well.
Personally I like the efficiency self-modifying code can produce.
When inventing, let·2/3·of your thinking be in probing opposition to all you've been taught. Only consider "fact" to be what you know from multiplicity of personal experience. Expect to have·simple, sound understandings of how things work -- because that's reality. If it's complicated, your understanding is either not complete, or you haven't partitioned it properly in your mind.
It's an ongoing fight to keep boxes from forming closely around our heads which·block our view and limit our consideration. Recognize their·opacity and·smash them.
There are·amazing and simple things yet to be invented that are going to be obvious·in hindsight, but are hidden now because of our·indolent allegiances to convention.
PROTECT and CULTIVATE your common sense. Beware that, for whatever reason, the world will destroy this within you if you are not vigilant. Without common sense, you can't understand anything worth understanding.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 1/12/2009 10:31:29 PM GMT
····"When debugging, let 2/3 of your thinking be in probing opposition to all you've written."
This is one of the hardest things to learn as a new programmer: ferreting out what's wrong with a program instead of rationalizing why it's right and ought to work.
I might augment the two-thirds, though.
-Phil
Made the other thread worth it to get that nugget!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Sometime you should look up the ICL (previously Singer and Friden) System Ten and System 25 instruction set (minicomputer 1969-1993/9).
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Prop Tools under Development or Completed (Index)
http://forums.parallax.com/showthread.php?p=753439
My cruising website http://www.bluemagic.biz
1) Propeller doesn't have a stack??? Ugh!
2) Code and data share the same RAM space? What else is new? We've been doing that since Babbage.
3) Exacuting a jump table is _NOT_ "self-modifying code." The table is data, pure and simple, and is never anything else. The fact that the table entries are addresses doesn't change that.
Jack
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Sorry about the "Let's build a compiler" series. I had planned 21-22 installments. The last few were going to include multiple data types, passed parameters, and code optimizations. I had already worked out a really neat expression optimization strategy. But progress got stopped by a layoff at #16. I found it necessary to get a new paying job, instead of working for free.
Several folks have asked me to complete the tutorial, but technology has simply overtaken it. That whole thing was done in Turbo Pascal on a Kaypro. The target was a 68000 running SK*DOS. The docs were posted on CompuServe. None of those things even exist anymore, for all practical purposes. I'd have to start over completely, probably using HTML docs and Windows-based tools.
Anyone want to see a KISS compiler for a Propeller?
To heater re: the language spec: The whole point of the series was not to design a language for you, but to show you how to design your own, then build a compiler for that language. I only used KISS as a talking point. The spec was always ... er... "fluid." The tutorial wasn't like a book; you guys were basically looking over my shoulder as I worked. Not many authors allow such.
Jack
Jack Crenshaw shows up.. My day is made.. Absolutely! This would be a real treat!
@Chip: Awesome advice, needs to be tattooed to my forehead in reverse so I see it every
morning in the mirror. [noparse]:)[/noparse] Defiantly made the other thread worthwhile.
OBC
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?
Check out: Protoboard Introduction , Propeller Cookbook 1.4 & Software Index
Updates to the Cookbook are now posted to: Propeller.warrantyvoid.us
Got an SD card connected? - PropDOS
You made my day too. BTW: You can still get a pascal and work through that series.
Hell yes, I would love to see that thinking applied to the Propeller!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
It's an honour to be speaking with you. This has really made my day as well.
I do understand the point of the series I and appreciate what you did there greatly. I think I was just frustrated that KISS was not completed as something of a reference. Actually I was just sad that the series stopped, I was enjoying your style so much. Over the decades I have occasionally delved into various compiler writing books and always ended up with the conclusion I was too dumb to even begin to understand so "Let's build a compiler" was a God send to me.
As it happens last summer I started through the series ending up with something of a TINY compiler for the Propeller. See attachment. Basically I was "looking over you shoulder" and redoing your experiments in C. The resulting code follows that in your text quite closely. The generated code is for the Prop in Large Memory Model (LMM) The LMM kernel is included. The implementation goes as far as TINY in the series but my functions have no way to return a value yet.
A few years back I worked through the series ending up with a typed language signed/unsigned bytes words longs also in C generating x86 assembler as per your challenge. I hope I still have that on an old hard drive somewhere I would love to re-target it to the Prop. Otherwise I will have to continue on again with my new TINY effort.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
Hrm.. I just wished I'd read that series *before* I wrote bstc. Oh, bst[noparse][[/noparse]cl] is written in Pascal too...
mpark pointed me at it a while back, and I've read / bookmarked the entire series. Great stuff.
Jack, if you ever decide to further the docs, please don't tie things to a windows target.. pretty please..
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Cardinal Fang! Fetch the comfy chair.
I'm also voting for a Windows independent, cross platform world.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
BradC said:
> Jack, if you ever decide to further the docs, please don't tie things to a windows target.. pretty please..
No, I would _NEVER_ do that! I was talking about Windows (or HTML) as the learning/development tool, not the target.
To clarify: In the original series, you had the tutorial itself, which was all in text. Then you had the compiler fragments, which were in Pascal. Then, of course, you needed Turbo or some other compiler. Then you had the compiler output, which was ASM. So you needed an assembler, and a way to get the compiler output into it (mine was on a separate computer, with incompatible media). Then, for any serious work, you needed a debugger.
Alternatively, I suppose you could run a processor emulator on a host (good luck finding a CP/M based 68000 emulator).
If I count write, that's something like 6 different file formats and 6 different programs. In my environment, you could only run one at a time.
Doing it the "modern" way, I think I'd want a single tool, with multiple windows open, and be able to read the tutorial, see the compiler IDE, copy the code fragments to it, run the TINY/KISS compiler, see the ASM generated, and run the assembler and emulator/debugger, all from a single app. Visual C++ project, perhaps? Visual C#? Or perhaps even better, a live HTML web documented, with the ability to pass data between the elements.
I guess that's why I haven't done it. I can't decide how. Even if I did, I don't _KNOW_ how <g>.
Jack
<snip>
Hrm. I think what I had intended to convey was to ask "Please don't tie it to a Microsoft product". Requiring the use of Windows or any Visual(cough/hack) product is just another barrier to entry.
I thought your original series in Pascal was a fantastic and neutral way to demonstrate the concepts and was not particularly tied to any platform without getting clouded by ugly language semantics and obfuscation. Pascal tends to be easy to read and write even for those not familiar with languages. It was a teaching language after all [noparse]:)[/noparse]
If you were to choose another language, one that did not require a 90/100MB runtime (C#/Java respectively) would probably be nice [noparse]:)[/noparse] (C++ does make me twitch though)
As I read your original series *after* I'd written a compiler, it taught me a lot about what I did wrong and how not to do things. Next time I'll re-read it before I start [noparse]:)[/noparse]
As as aside, the cross-platform cpu/system emulator Qemu (do you sense multi-platform is important to me?) has a great 68k emulator in it. It would be a neat way of demonstrating code when they can bring it up and see it operate in a completely self-contained VM.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Cardinal Fang! Fetch the comfy chair.
Jack
-Phil
(I really don't miss my Perl days.)
Version: 0.01
P++c?P6!R--M O?MA-E PU-BD-C++$D!S
X+WP-MO!PP n CO?PO--o?G A--OL!Ee!Ev!Eon
Eot Eob!Eoa!uL++uB!uS
uH!uo+w-$m!osA+osBE+
OBC
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?
Check out: Protoboard Introduction , Propeller Cookbook 1.4 & Software Index
Updates to the Cookbook are now posted to: Propeller.warrantyvoid.us
Got an SD card connected? - PropDOS
Doesn't have to be ugly OBC. Though it can easily be. LOL!!
I also think somebody who wants to build a compiler can also build an environment to work in, and probably has one! So then, simple text and command line stuff seems a good overall baseline. Could always build up an "out of box" environment on a web site, or VM too.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
Python on the other hand would be very nice.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net
Safety Tip: Life is as good as YOU think it is!
How complete a clone is it? The reason I ask is that the Propeller IDE is written in Delphi. If it were possible to port it to Freepascal (and if Parallax were willing), the IDE could be portable as well.
BTW, my Perl suggestion was made tongue-in-cheek. As much as I like it and as powerfull as it is for processing text, I know the kind of reputation it suffers (undeservedly IMO). My CLEAN app is written in Perl, as are the Scribbler GUI and AVR loader for the MoBoStamp-pe. All would have been much more difficult in a different language.
-Phil
Addendum: I think a minimum language requirement for the app in question is that it have built-in garbage collection. Explicit memory management using malloc or its ilk is a distraction from the application itself, inevitably results in memory leaks, and makes any language requiring it unworthy of the moniker "high-level".
Post Edited (Phil Pilgrim (PhiPi)) : 1/18/2009 7:32:02 PM GMT
Perl: The trouble is if you get people writing their compilers in Perl very quickly their code is going to be full of regular expression "line noise". Given the nature and level of the "Let's Build a Compiler" text I think it's great that people do all their scanning and parsing the long way round as a learning exercise.
I don't see garbage collection as a requirement. As you scan and parse and generate you may pile up a ton of "leaked" tokens or other objects. So what? We have tons of RAM now, small modules of TINY or KISS are not going to even show up in ps, all is released when done. Not as if we are writing long running process here.
Boy have we come a long way from the topic of this thread !
I do have some thoughts about Dijkstra's downer on GOTO and self modifying code, perhaps tomorrow.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.