BTW, I added your mail to the milter ACL so you can post to kragen-discuss. Let me know if you get any more bounces from the kragen-discuss list.
On Thu, Apr 28, 2011 at 05:44:53PM -0700, Greg Alt wrote: > On Thu, Apr 28, 2011 at 3:54 PM, Kragen Javier Sitaker > <[email protected]> wrote: > > How much is way too much? Is it exponential or something? That might > > cause difficulty with execution time even once you have garbage > > collection implemented. > > Part of it is that I'm using only a small portion of 64k for my heap. > And part of it is that my first stab at compiling if's actually > compiles the true and false clauses twice each - once to get the size > and once to emit the machine code. And both cases end up consing the > same amount. > > So if you do something like: > > (if (eq x 1) (do1) > (if (eq x 2) (do2) > (if (eq x 3) (do3) > (if (eq x 4) (do4) > (if (eq x 5) (do5) (do6)))))) > > (do1) gets compiled twice, (do2) gets compiled 4 times, ... and (do6) > gets compiled 64 times. So, yeah, that's exponential. You might want to fix that, because even after you have a GC, someone can drop an (and a b c d e f g h i j) on you and make you do 1024× work. Dave's suggestion of handling jumps to labels in a separate pass simplified Ur-Scheme a lot (for Ur-Scheme, the separate pass was gas, but it could be something much simpler) but I haven't done that yet in StoneKnifeForth. Instead, SKF uses the traditional Forth approach for IF THEN (spelled [ ]) and BEGIN WHILE REPEAT (spelled { }) — BEGIN pushes the current address on the stack, and WHILE REPEAT pops that address off the stack and compiles a conditional jump to it, while IF compiles a conditional jump to 0 and pushes its address on the stack, while THEN pops that address off the stack and backpatches the jump target to be the current address. You can fit ELSE into the same scheme pretty easily. SKF also supports compiling CALLs to previously defined labels, of course, but no mutual recursion or forward references. > Since compiling anything ends up consing up a > list of bytes to emit, if (do6) is an expression that ends up taking > 256 bytes, it ends up consing 16k cons cells ignoring all the other > overhead, and cons cells are 4 bytes, so that's already 64k which is > way over my limit. :) Ur-Scheme uses an approach like ropes or Erlang iolists, in which (a . b) is used to represent the concatenation of a and b. This way, concatenating two strings of arbitrary size allocates just a single cons cell (12 bytes in Ur-Scheme, including the type tag — hurts minimalism but sure helped debugging!), and so if you have 10 places in a piece of code that, say, load the cdr of a cons, they can all share the same copy of the machine code to do that (until you emit it). > > I found debugging Ur-Scheme was aided substantially by having GDB handy. > > I didn't resort to it often, though, because the emitted code is full of > > run-time type-checks, which were usually what failed. And being able to > > hit F5 in Emacs and immediately see the diff of the emitted assembly > > code, followed by any test failures, was a big help. > > My goal was to start from as scratch as possible and cheat as little > as possible. I ended up using debug.com to avoid wasting lots of time > just to stick to my principles, but anything fancier just didn't seem > right. :) > Sure. When I start fun projects, I like to double-up the fun. A > while back I wrote a real-time raytracer in SBCL common lisp. I was > interested in real-time raytracing and also was intrigued by the idea > of writing super-optimized common lisp, so I combined both objectives > in one project. Later I did a project using the OpenCV computer > vision library in python to try to take pictures of a go board with go > stones on it in mid-game and generate a .sgf file with the stone > positions - that let me accomplish three objectives at once. Wow, those are really awesome projects! Have you made any of them public? I've been fairly disappointed with SBCL performance, but I admit I haven't really learned to push it. > So as for general bootstrapping concepts, outside of computers, I've > been thinking about how to grow organizations of people in a way that > is self-sustaining, also starting from scratch. A lot of similar > things apply. As an engineer, I really want to fully spec out my end > goal and then methodically put the pieces together until I'm done, but > that's not at all what you want to do when you bootstrap anything. That's a fascinating insight! > Instead, I hit on an idea of broad-strokes planning. You look at your > ideal end-goal and where you are at. And since it's clearly not > possible to get from here to there in one effort, you break it down > logarithmically. Planning out my life, I started from a 300-year goal, and worked from there to 100-year, 30-year, 10-year, 3-year, 1-year, 3-month, 1-month, 1-week, and 1-day goals. Is that what you mean by "break it down logarithmically"? One tricky thing about this sort of thing is that as time goes on, the things you learn and abilities you gain change not only the means you can apply toward reaching your goals, but also the goals themselves. So it seems somewhat tricky to make good decisions at the outset, and there's the temptation not to commit to anything — which is itself a bad decision! > Before I started, this bootstrappy way of thinking tied my brain in > knots with even relatively simple problems. Now it's starting to make > sense. And I like the way you can get boxed in a corner and just > imagine some magic to unblock you, and if it's simple enough magic and > it works, you feel like you're getting away with something that > shouldn't be possible, like you're using your first wish to ask the > genie for 5 more wishes. That's awesome. Inspirational, even. It's like the "law of attraction" with less bullshit. Kragen -- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
