On Apr 21, 12:58 am, Jonah Thomas <jethom...@[EMAIL PROTECTED]
> wrote:
> Gerry <ge...@[EMAIL PROTECTED]
> wrote:
> > I've emailed you a copy. I'd appreciate it if you let me know how you
> > got on with it or if the email doesn't reach you
>
> It arrived intact. I've spent half an hour looking at it, I can follow
> in general what it's doing. It looks more complicated than I expected. I
> probably haven't noticed all the subtle problems that need to be solved.
>
> I want to ask anyone who's interested about a programming puzzle I ran
> into when I tried something similar.
>
> The idea is to have a routine GOOD-STRING that accepts a string ( ca len
> ) and an execution token that acts on the string and checks the first
> part of the string for some condition. Like, it couild test whether a
> character is an uppercase letter, or whether it's a digit, or
> alphanumeric, or whether two characters are ":=" or whatever.
Ruby:
--- code ---
p "abc"[ /^\d*/ ]
p "8abc"[ /^\d*/ ]
p "89abc"[ /^\d*/ ]
--- output ---
""
"8"
"89"
--- code ---
def good_string str
str.size.times do |i|
return str[0,i] if not yield str[i..-1]
end
str
end
p good_string( 'abc' ){|s| s =~ /^\d/ }
p good_string( '8abc' ){|s| s =~ /^\d/ }
p good_string( '89abc' ){|s| s =~ /^\d/ }
--- output ---
""
"8"
"89"
> The
> execution token should accept an address in the string, and it returns a
> flag.
>
> XT ( ca -- flag )
>
> The routine does ( ca len xt -- ca len' ) . It returns as much of the
> string as meets the condition the execution token tests for.
>
> So I'd wind up with:
>
> : STRING-CHECKER ( S: xt "name" -- )
> ( child: ca len -- ca len' )
> CREATE ,
> DOES> @[EMAIL PROTECTED]
GOOD-STRING ;
>
> to make a collection of named routines to check strings in various ways.
>
> My first attempt at GOOD-STRING was like this:
>
> : GOOD-STRING1 ( S: ca len xt -- ca len' )
> >R
> 2DUP BEGIN
> DUP 0 > WHILE
> OVER R@[EMAIL PROTECTED]
EXECUTE WHILE
> 1 /STRING
> REPEAT
> THEN
> NIP - RDROP ;
>
> This works adequately but it's clumsy. A complicated loop and a return
> stack item. No way to simplify it that matters, not without getting rid
> of either the complex loop or the >R or both. Using locals would handle
> it easily but I didn't want to do that. I thought there ought to be a
> good way to do this without locals. I only care about 3 items, surely I
> can handle 3 stack items.
>
> So I tried to get rid of the loop with recursion. I had just the looping
> part recurse.
>
> : CHECK-STRING2 ( ca len xt -- ca' len' xt )
> OVER 0 > IF
> >R OVER R@[EMAIL PROTECTED]
EXECUTE IF
> 1 /STRING R> RECURSE
> ELSE
> R>
> THEN
> THEN ;
>
> This is not great. My first recursive approach was even worse. I tried
> to get rid of the xt, but then I needed extra branches to get rid of it
> consistently. Easier to DROP it once when the routine is done. I figure
> branches are a little better than loops and there's only one RECURSE
> isntead of two WHILEs. But it isn't simple and there's no obvious way to
> factor it.
>
> I could get rid of the return stack ops by using DEFER .
>
> DEFER CHECKER
> : CHECK-STRING3 ( ca len -- ca' len' )
> DUP 0 > IF
> OVER CHECKER IF
> 1 /STRING RECURSE
> THEN
> THEN ;
>
> The DOES> child can simply put the xt into CHECKER and it works. Simple.
> But not easily re-entrant. I will want to be checking a string and in
> the middle I'll need to start checking for something else, and then
> continue where I left off. To do that I have to save the old value of
> CHECKER and there's no standard way to get that. I'd have to save the
> old value on a stack. The complication pops up there.
>
> So I did without the deferred variable.
>
> : CHECK-STRING4 ( xt ca len -- xt ca' len' )
> DUP 0 > IF
> OVER 2OVER DROP EXECUTE IF
> 1 /STRING RECURSE
> THEN
> THEN ;
>
> Changing the stack order helped some. The return stack mess is gone, and
> the side branches. The only troublesome bit is a little spot of stack
> noise. Would 3PICK look better than 2OVER DROP ?
>
> I can make it look nicer.
>
> : CHECK-STRING5 ( xt ca len -- xt ca' len' )
> 3DUP 0 > IF
> SWAP EXECUTE IF 1 /STRING RECURSE THEN
> THEN ;
>
> 3DUP is not really simpler than 3PICK . It's easier for me to see what's
> going on, but the obvious way to implement 3DUP in high-level standard
> Forth is : 3DUP 2PICK 2PICK 2PICK ;
>
> Only 3 stack items. Why is it so hard? Because with ( a b c ) the things
> we need to do require copies
>
> len
> ca xt
> ca len original, not copy
> xt ca len original
>
> There's no way to get all four patterns without some stack juggling. (Or
> locals.)
>
> When is this sort of perfectionism justified? I got something that
> worked in 3 minutes. After a series of false starts I got something that
> approched elegance. It still has a RECURSE so it wouldn't be as easy to
> debug at the keyboard as something that didn't have recursion or loops.
> Luckily it passed my tests the first try.
>
> : GOOD-STRING2 { ca len xt }
> ca len BEGIN
> DUP 0 > WHILE
> OVER xt EXECUTE WHILE
> 1 /STRING
> REPEAT
> THEN
> NIP ca len ROT - ;
>
> A few locals are enough to get past some of the worst problems. And if a
> few locals are good, maybe more locals are better. With 2 more locals
> and liberal use of TO I can eliminate every stack word.
>
> : GOOD-STRING2 0 0 { ca len xt ca' len' }
> ca TO ca' len TO len' BEGIN
> len' 0 > WHILE
> ca' xt EXECUTE WHILE
> ca' len' 1 /STRING TO len' TO ca'
> REPEAT
> THEN
> ca len len' - ;
>
> Better? Not only do you eliminate the stack words, the stack comments
> are part of the code.
>
> When is it worthwhile to make the code simple? I have to figure the
> ideal approach is to do it simply the first time. If you write elegant
> code quickly, so the first version is easy to understand and easy to
> test and easy to document etc, then you don't have to think about how
> much time to spend improving it.
|
