PDA

View Full Version : Self Modifying Code - Some Later Insight From Dijkstra That Is Surprising



soshimo
01-13-2009, 01:36 AM
Circa 1999


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.

Phil Pilgrim (PhiPi)
01-13-2009, 02:03 AM
An example of the Propeller's use of self-modifying code that absolutely delights me is the JMPRET (CALL). In now-traditional processors, a stack is used to store the return address of a calling program. That's okay, too, since it makes recursion easier and reentrancy possible. But it makes exception handling more of a challenge. To give an example of the difference, I have a subroutine that looks for a certain input pattern that may or may not arrive in a timely fashion. If it arrives, fine, I can return with the time of arrival. But what if it doesn't? In a normal processor, I'd have to raise a flag and return, forcing the calling program to deal with it. If the subroutine is called from several locations (as mine is), the exception has to be handled in each of them. But without a stack to maintain, I can just JMP to the exception handler and reenter the top of the main code from there. (Now, I can just hear the Greek Chorus warming up to moan, "Oooooh, spaghetti code, ooooooh! Doooom!" Yes, it's certainly a technique you want to use sparingly, but it comes in handy when you need it.)

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

soshimo
01-13-2009, 02:13 AM
Phil Pilgrim (PhiPi) said...
(Now, I can just hear the Greek Chorus warming up to moan, "Oooooh, spaghetti code, ooooooh! Doooom!" Yes, it's certainly a technique you want to use sparingly, but it comes in handy when you need it.)

-Phil


Just mention stack unwinding http://forums.parallax.com/images/smilies/tongue.gif . I'll take the spaghetti in this case thank you very much.

potatohead
01-13-2009, 03:19 AM
LOL!!

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! (http://propeller.wikispaces.com/)
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net (http://propeller.wikispaces.com/Join+us+on+IRC%21/)
Safety Tip: Life is as good as YOU think it is!

Andrew E Mileski
01-13-2009, 04:54 AM
One cannot execute self-modifying code from ROM. As the Propeller can only execute code from RAM, this isn't a problem.

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.

cgracey
01-13-2009, 05:04 AM
This thread and the one about comparing the Propeller to other micros got me somewhat stirred up about our whole thinking process, so I want to throw out some advice to anyone who'll take any stock in it...

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

Phil Pilgrim (PhiPi)
01-13-2009, 05:36 AM
Well said, Chip! And if you'll permit me to adapt one of those pearls to debugging:

····"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. http://forums.parallax.com/images/smilies/smile.gif

-Phil

potatohead
01-13-2009, 05:46 AM
:)

Made the other thread worth it to get that nugget!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness! (http://propeller.wikispaces.com/)
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net (http://propeller.wikispaces.com/Join+us+on+IRC%21/)
Safety Tip: Life is as good as YOU think it is!

cgracey
01-13-2009, 05:54 AM
Good point, Phil. I do that all the time. Sometimes I'll even notice myself dismissing symptoms because they imply a more difficult fix. It's really silly. In the end, my conscience won't let me relax, so I've got to correct it at last, even if it means tearing up the foundation to replace the linoluem.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Cluso99
01-13-2009, 11:18 AM
Good one Chip. Like I've said before, if you remained in "that" box we would not have the Prop http://forums.parallax.com/images/smilies/smile.gif

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

Javalin
01-15-2009, 07:04 PM
Well said Chip!

Jack Crenshaw
01-15-2009, 11:34 PM
Three thoughts:
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

mpark
01-16-2009, 02:01 AM
Jack "Let's Build a Compiler" Crenshaw?

heater
01-16-2009, 06:58 AM
@Jack: Is that "Let's build a Compiler Jack" if so I really want to speak to you about, well, "Lets build a Compiler" I've been through that series twice now and am never sure if I'm getting to the correct language spec. So frustrating to be left "up in the air":)

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

Jack Crenshaw
01-16-2009, 09:46 PM
Yep, I'm that Jack. See me also at embedded.com.

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

Oldbitcollector (Jeff)
01-16-2009, 09:54 PM
Jack Crenshaw said...

Anyone want to see a KISS compiler for a Propeller?



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. :) Defiantly made the other thread worthwhile.

OBC

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
New to the Propeller?

Check out: Protoboard Introduction (http://jeffledger.googlepages.com/Protoboard_Introduction.pdf) , Propeller Cookbook 1.4 (http://ucontroller.com/Propeller%20Protoboard%20Designs%20for%20the%20Beg inner.pdf) & Software Index (http://forums.parallax.com/showthread.php?p=770318)
Updates to the Cookbook are now posted to: Propeller.warrantyvoid.us (http://propeller.warrantyvoid.us)
Got an SD card connected? - PropDOS (http://www.orrtech.net/propdos/)

potatohead
01-16-2009, 11:13 PM
Hi Jack!

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! (http://propeller.wikispaces.com/)
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net (http://propeller.wikispaces.com/Join+us+on+IRC%21/)
Safety Tip: Life is as good as YOU think it is!

heater
01-16-2009, 11:16 PM
Jack,

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.

BradC
01-16-2009, 11:30 PM
potatohead said...

You made my day too. BTW: You can still get a pascal and work through that series.



Hrm.. I just wished I'd read that series *before* I wrote bstc. Oh, bst[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.

heater
01-16-2009, 11:42 PM
Actually I think that the fact that the series code is in Pascal and the generated code is for 68000 is perfectly OK. If the thing was written in C/C++/Java, whatever, with output in x86 people would be tempted to cut/paste/compile with out running it through their brain. For me, at least, adapting the implementation and target languages forced me to follow and understand all the details of what I was looking at.


I'm also voting for a Windows independent, cross platform world.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

Jack Crenshaw
01-18-2009, 01:12 AM
heater: Awesome! I think you've already passed me in terms of compiler theory!

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

BradC
01-18-2009, 02:09 AM
Jack Crenshaw said...
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.




<snip>


Jack Crenshaw said...

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.



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 :)

If you were to choose another language, one that did not require a 90/100MB runtime (C#/Java respectively) would probably be nice :) (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 :)

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 Crenshaw
01-18-2009, 10:33 PM
Ok, so I hear that you don't want a tutorial written using something like Visual <anything>. Keep it portable (KIP?). I guess that means Java and/or Java invoking C++ or C# programs. How about something interactive on a website?

Jack

Phil Pilgrim (PhiPi)
01-19-2009, 01:06 AM
Perl is portable. http://forums.parallax.com/images/smilies/smile.gif

-Phil

Oldbitcollector (Jeff)
01-19-2009, 01:18 AM
...and I'll need a secret decoder ring too!
(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 (http://jeffledger.googlepages.com/Protoboard_Introduction.pdf) , Propeller Cookbook 1.4 (http://ucontroller.com/Propeller%20Protoboard%20Designs%20for%20the%20Beg inner.pdf) & Software Index (http://forums.parallax.com/showthread.php?p=770318)
Updates to the Cookbook are now posted to: Propeller.warrantyvoid.us (http://propeller.warrantyvoid.us)
Got an SD card connected? - PropDOS (http://www.orrtech.net/propdos/)

potatohead
01-19-2009, 01:23 AM
Was gonna mention PERL too.

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! (http://propeller.wikispaces.com/)
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net (http://propeller.wikispaces.com/Join+us+on+IRC%21/)
Safety Tip: Life is as good as YOU think it is!

heater
01-19-2009, 01:43 AM
PERL is not portable, my brain is absolutely incapable of running it.

Python on the other hand would be very nice.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

potatohead
01-19-2009, 01:50 AM
LOL!!!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness! (http://propeller.wikispaces.com/)
Chat in real time with other Propellerheads on IRC #propeller @ freenode.net (http://propeller.wikispaces.com/Join+us+on+IRC%21/)
Safety Tip: Life is as good as YOU think it is!

waltc
01-19-2009, 01:51 AM
I'd go with Freepascal which is TP/Delphi clone that runs on multiple platforms.

Phil Pilgrim (PhiPi)
01-19-2009, 02:20 AM
waltc,

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

heater
01-19-2009, 03:08 AM
I have no idea about how portable Pascal is but I imagine the problem is not compiling the Propeller IDE with Free Pascal or whatever but having to use a different Windowing and widget tool kit. Anyway BradC has already got one !

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.

waltc
01-19-2009, 03:16 AM
Phil,

As far the Delphi question is concerned AFAIK if the code is Delphi Pascal and uses standard components(non-visual ones) then its possible to port over Delphi code.
http://www.freepascal.org

The visual components though need the Lazarus RAD add-on for Freepascal. According to the developers programs written with Lazarus will work on FreeBSD, Linux and Mac.
http://www.lazarus.freepascal.org/

A caveat is in order though, I mostly write Dosbox and command line programs nowadays so I can't vouch for how good the GUI/RAD stuff is. The FreePascal compiler though seems to be rock solid and fast.

And then there's Bloodshed Pascal(the one I use) which incorporates Freepascal into a windows based IDE. The IDE is written in Delphi and source code is freely available.
http://www.bloodshed.net/

Hope this helps.

BradC
01-19-2009, 06:43 AM
Phil Pilgrim (PhiPi) said...
waltc,

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.



It's a fairly complete clone actually.

I've picked through various disassemblies of the PropellerTool while I was trying to fix WINE to run it properly and they have used a couple of custom components that are not standard off the shelf Delphi components. They would not be incredibly easy to port.

You can hide a certain amount of the platform specific stuff, but in the end the last 5% is quite a lot of work.

The other problem with the Parallax tool is the compiler is written in x86 ASM, so it'd never run on a PPC Mac anyway.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Cardinal Fang! Fetch the comfy chair.