SOKOBAN.F Bug 
Author Message
 SOKOBAN.F Bug

        I've run across a bug in the sokoban distributed, I think, with
gforth.  The way that this sokoban performs a move is by comparing the
three characters in the direction that soko is moving with a string, and
then replacing them by the three characters in the result string.
Depending on whether a rock has been pushed onto or off of a target, it
also updates the total "rocks to go" variable.


not on a target, a rock that is not on a target, and soko is pushing the

position that the rock did, and the rock occupying the target.  This works
for any direction, with the direction encapsulated into determining where
the 'next' space is from the 'current' space (forward one, back one, up
one, down one).  Its real neat, because illegal moves simply fail to match
the list of possible moves, so that if none of the legal moves is matched,
the effort to move fails.
        But what will happen if a legal move is omitted from the list?
You guessed it, soko will get stuck.  And this is exactly what was
happening in maze #11, where there is an array of targets something like:

        .
        .. ...
        ....#.
        ......

        The problem is that gap in the second line.  If soko is trying to
push something across the second row (which is necessary if the maze is to
be solved), he/she will reach a position such as:

        .
        ..$&..
        ....#.
        ......

And going "backward", the string that has to be matched to find out what
to do next is S" &$." but, in the version I had, there was no such string.
So I copied a case that involved moving a rock onto a target, and put in
this string, with its successor:


(See why soko and the rocks have to change shape when going onto a target
-- otherwise the targets would get lost as soko pushed rocks over top of
them).  And after making this change, it worked.

        BTW, how would we write a utility to read a file and translate the
ANS standard words into upper case, for case sensitive forth's like
hforth?  I did this by hand as a testbench for my modified MF.F, to get
sokoban running on hforth, but its a tedious job.  Simplest would be to
translate everything to upper case if it wasn't wrapped in quotes,
parentheses, or in a "\" comment line, but preferable would be one that
read a file of ANS standard words and only upper-cased those words.  This
can be done in mf with it's search and replace, but it's tedious.

Virtually,

Bruce R. McFarling, Newcastle, NSW



Mon, 22 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

"Bruce R. McFarling"  writes:

Quote:
>    BTW, how would we write a utility to read a file and translate the
> ANS standard words into upper case, for case sensitive forth's like
> hforth?  I did this by hand as a testbench for my modified MF.F, to get
> sokoban running on hforth, but its a tedious job.  Simplest would be to
> translate everything to upper case if it wasn't wrapped in quotes,
> parentheses, or in a "\" comment line, but preferable would be one that
> read a file of ANS standard words and only upper-cased those words.  This
> can be done in mf with it's search and replace, but it's tedious.

> Virtually,

> Bruce R. McFarling, Newcastle, NSW


Redefine INTERPRET, ( and \ --in a distinct wordlist-- so that

        a) found => uppercase;
        b) number => number;
        c) ~found & ~number => leave alone;
        d) comments & drop lines are also untouched;

then write the words (i.e. text delineated by spaces) to an output
file. You will lose the white space, but that should do it.
Additional formatting is up to you.

This was inspired by something Rick Van Norman did several years
ago.

--
Julian V. Noble

"Elegance is for tailors!"    -- Ludwig Boltzmann



Mon, 22 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug


"RM>    BTW, how would we write a utility to read a file and translate
"RM> the ANS standard words into upper case, for case sensitive forth's
"RM> like hforth?  I did this by hand as a testbench for my modified
"RM> MF.F, to get sokoban running on hforth, but its a tedious job.
"RM> Simplest would be to translate everything to upper case if it
"RM> wasn't wrapped in quotes, parentheses, or in a "\" comment line,
"RM> but preferable would be one that read a file of ANS standard words
"RM> and only upper-cased those words.  This can be done in mf with
it's
"RM> search and replace, but it's tedious.  

I guess, convertion is needed for compilation only and not for reading.
For converting case insensitive writing, it is enough to uppercase all.
One exception should be taken care of when writing the source (not when
converting): Use of [CHAR] <character> needs to withstand the
conversion, when written for a case insensitive machine.

For that contest, I added a conversion tool to my version, since I
prefer to introduce new names uppercase and re-use the names lower-case,
which helps reading especially if some lot of defining words come
along:

''''''''''' upper.fth ''''''''''''''''

: WITHIN    ( N1 N2 N3 -- F)
   OVER - >R - R> U< ;

: CAPITAL   ( CHAR -- CHAR')
            ( ** SIMPLE UPPERCASE)

   DUP [CHAR] A 32 OR
       [CHAR] Z 32 OR 1+ WITHIN
   IF 32 INVERT AND THEN ;

: SKIP          ( A N CHAR -- A+ N-)
                ( ** ADVANCE IN STRING PAST LEADING CHAR)

   WHILE 1 /STRING   REPEAT THEN    R> DROP ;

: SCAN          ( A N CHAR -- A+ N-)
                ( ** ADVANCE IN STRING TO CHAR OR END)

   WHILE 1 /STRING   REPEAT THEN    R> DROP ;

: /PARSED       ( A N CHAR -- A' N' N+)
                ( ** ISOLATE PART-STRING DELIMITED BY CHAR,)
                (    CALC LENGTH TO ADVANCE)


   ROT OVER -       ( A' N1 N5)
   ROT ROT          ( N5 A' N1)
   2DUP R> SCAN NIP ( N5 A' N1 N2)
   DUP >R -         ( N5 A' N')
   ROT OVER +       ( A' N' N6)
   R> IF 1+ THEN ;

: PARSE-WORD    ( CHAR -- A N)
                ( ** FETCH STRING FROM INPUT STREAM)


   ROT /PARSED >IN +! ;

    255 CONSTANT LINESIZE
          CREATE LINESCRT     \ LINE-READ BUFFER
                 LINESIZE 3 + CHARS ALLOT ALIGN

: FILE-UPPERCASE ( -- // "NAME")

            LINESCRT LINESIZE
            BL PARSE-WORD
            R/W OPEN-FILE THROW >R


            TUCK = >R DUP
   WHILE    2DUP 0
      DO    DUP COUNT CAPITAL ROT C!
      LOOP  DROP
            2SWAP R> 0= ROT ROT


   UNTIL
   ELSE     R> DROP 2DROP 2DROP
   THEN     2DROP R> CLOSE-FILE THROW ;

''''''''''''''''''''''''''''''''''''''''''''''



Tue, 23 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug


:       BTW, how would we write a utility to read a file and translate the
: ANS standard words into upper case, for case sensitive forth's like
: hforth?  I did this by hand as a testbench for my modified MF.F, to get
: sokoban running on hforth, but its a tedious job.  Simplest would be to
: translate everything to upper case if it wasn't wrapped in quotes,
: parentheses, or in a "\" comment line, but preferable would be one that
: read a file of ANS standard words and only upper-cased those words.  This
: can be done in mf with it's search and replace, but it's tedious.

A utility to parse Forth isn't easy.

And it will never be completed.

It has been said that Forth has no syntax but sequence.  This is not so.

The syntax of a Forth word may be different whether it's being compiled
or interpreted.  For example, `CHAR`, `'`, `:`, `CREATE`, _etc_.

A word may also have special syntax given by Parsed-text notation (2.2.3).

These are the initial special syntaxes used in my program to give
canonical spelling to Forth words.

( COMMENTS:  Paren, S-Paren, Backslash )

"comment"
    (

"ccc<paren>"
    .(

"ccc<eol>"
    \

( QUOTATIONS:  S-Quote Dot-Quote Abort-Quote C-Quote [CHAR] CHAR etc)

"ccc<quote>"
    S"

?"ccc<quote>"
    ."   ABORT"   C"

"<spaces>char"
    [CHAR]

?"<spaces>char"
    CHAR

char"<chars>ccc<char>"
    WORD

char"ccc<char>"
    PARSE

( CITATIONS:  POSTPONE TO ['] [COMPILE] )

"<spaces>name"  
    POSTPONE   TO   [']   [COMPILE]

( DEFINITIONS:  Colon :NONAME Right-Bracket etc. )

+Compile"<spaces>name"
    :

+Compile
    :NONAME   ]

-Compile
    ;   ;CODE   [

?"<spaces>name"
    '   2CONSTANT   2VARIABLE   CONSTANT   CREATE   FCONSTANT
        FORGET   FVARIABLE   MARKER   VALUE   VARIABLE

"names<bar>"  
    LOCALS|

A user can add new words or new syntaxes.

A list of words is primed with the Standard words and their syntax.

The program uses `LEFT-JUSTIFY`, `SPLIT-AT-SPACE`, and `SPLIT-AT-CHAR` to
go through source.  Each word is looked up in the list of words with
case-insensitivity.  If not found it is added to the list.  If found
the spelling in the source is made the same as the spelling in the list,
and any special syntax is followed.

--
Wil



Tue, 23 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

[about his conversion tool]

In the Standard in A.6.2.2000 it is written:

QUOTE

The behavior of WORD with respect to skipping leading delimiters is useful for
parsing blank-delimited names.  Many system implementations include an
additional word for this purpose, similar to PARSE with respect to the c-addr
u return value, but without an explicit delimiter argument (the delimiter set
is implicitly white space), and which does skip leading delimiters.  A common
description for this word is:

PARSE-WORD  ( <spaces>name -- c-addr u )

    Skip leading spaces and parse name delimited by a space.  
    c-addr is the address within the input buffer and u is the
    length of the selected string.  If the parse area is empty, that;
    the resulting string has a zero length.

If both PARSE and PARSE-WORD are present, the need for WORD is largely
eliminated.

UNQUOTE

In the OpenFirmware Standard it is written:

QUOTE

parse-word  ( "text<>" -- str len )

    Parse text from the input buffer, delimited by white space.

    Skip lead spaces and parse _name_ delimited by a space.  _str_ is the
    address (within the  input buffer) and _len_ is the length of the
    selected string.  If the parse area was empty, the resulting string
    has a zero length.

UNQUOTE

I strongly believe that we should follow such definition of `PARSE-WORD`.

The easy way in the example is replace `: PARSE-WORD   ( CHAR -- A N)` with
`: PARSE-WORD   ( "<SPACES>NAME" -- A N )  BL` and `BL PARSE-WORD` with
`PARSE-WORD`.

In the Standard in 3.4.1.1 Delimiters it is also written:

QUOTE

If the delimiter is the space character, hex 20 (BL), control characters may
be treated as delimiters.  The set of conditions, if any, under which a "space"
delimiter matches control characters is implementation defined.

UNQUOTE

To accommodate this is a little more effort.

In modern source files `-TRAILING`, `SKIP`, and `SCAN` are no longer
appropriate.  Expanding their meaning will bite you.  For some time I have
replaced them with `TRIM-TRAILING`, `LEFT-JUSTIFY`, `SPLIT-AT-SPACE`, and
`SPLIT-AT-CHAR`.  I use them in my program to canonize spelling.

--

Procedamus in pace.   Wil Baden Costa Mesa, California



Tue, 23 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug


Quote:
> "Bruce R. McFarling"  writes:

> >       BTW, how would we write a utility to read a file and translate the
> > ANS standard words into upper case, for case sensitive forth's like
> > hforth?  I did this by hand as a testbench for my modified MF.F, to get
> > sokoban running on hforth, but its a tedious job.  Simplest would be to
> > translate everything to upper case if it wasn't wrapped in quotes,
> > parentheses, or in a "\" comment line, but preferable would be one that
> > read a file of ANS standard words and only upper-cased those words.  This
> > can be done in mf with it's search and replace, but it's tedious.

> > Virtually,

> > Bruce R. McFarling, Newcastle, NSW

> Redefine INTERPRET, ( and \ --in a distinct wordlist-- so that

>    a) found => uppercase;
>    b) number => number;
>    c) ~found & ~number => leave alone;
>    d) comments & drop lines are also untouched;

> then write the words (i.e. text delineated by spaces) to an output
> file. You will lose the white space, but that should do it.
> Additional formatting is up to you.

        Aha! I aksed an incomplete question.  "Is there a way to ..."
without making changes in the file *except* for changing words to
uppercase?  I.e., unless the above can be jiggered to keep whitespace,
that's not the target.

Virtually,

Bruce R. McFarling, Newcastle, NSW



Wed, 24 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:
Bruce McFarling writes:


....

Quote:

> > Redefine INTERPRET, ( and \ --in a distinct wordlist-- so that

> >  a) found => uppercase;
> >  b) number => number;
> >  c) ~found & ~number => leave alone;
> >  d) comments & drop lines are also untouched;

> > then write the words (i.e. text delineated by spaces) to an output
> > file. You will lose the white space, but that should do it.
> > Additional formatting is up to you.
>  Aha! I aksed an incomplete question.  "Is there a way to ..."
> without making changes in the file *except* for changing words to
> uppercase?  I.e., unless the above can be jiggered to keep whitespace,
> that's not the target.

As Wil says, a program to parse Forth is never complete.  

Take CHAR for example:

If interpreting, you need to skip the next word, otherwise "CHAR a"
becomes "CHAR A", but you don't skip if compiling, because then the
next word after CHAR would be a valid word.

One way out would be to do the conversion as a by-product of loading
the code.  This means changing the system FIND so that it will
uppercase before searching the dictionary.  With block source you can
then simply copy back each uppercased word as it is found, and UPDATE
the block.  This keeps the format exactly as it was before.  Files
would be trickier, but I don't use them.

BTW, Wil's program looks very much like what I need to convert source
code to a tokenised form that will avoid parsing and dictionary
search at load time.  Thanks, Wil.

--
Jack Brien
"All bugs are obvious - given enough eyes"
www.users.zetnet.co.uk/aborigine/forth



Wed, 24 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:

> As Wil says, a program to parse Forth is never complete.  

> Take CHAR for example:

> If interpreting, you need to skip the next word, otherwise "CHAR a"
> becomes "CHAR A", but you don't skip if compiling, because then the
> next word after CHAR would be a valid word.

        But how many ANS standard words are single characters, such as
would follow CHAR?  The target is to upper case standard ANS words -- any
other case changes are simply a (mildly undesireable) side affect.

Quote:
> One way out would be to do the conversion as a by-product of loading
> the code.  This means changing the system FIND so that it will
> uppercase before searching the dictionary.  With block source you can
> then simply copy back each uppercased word as it is found, and UPDATE
> the block.  This keeps the format exactly as it was before.  Files
> would be trickier, but I don't use them.

        I think that files would be simpler, since you could just write
out all whitespace before searching, echo the upper space converted word
if it was found while searchimg, and echo the original of everything not
found when searching.

Virtually,

Bruce R. McFarling, Newcastle, NSW



Fri, 26 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:


> "RM>    BTW, how would we write a utility to read a file and translate
> "RM> the ANS standard words into upper case, for case sensitive forth's
> "RM> like hforth?  I did this by hand as a testbench for my modified
> "RM> MF.F, to get sokoban running on hforth, but its a tedious job.
> "RM> Simplest would be to translate everything to upper case if it
> "RM> wasn't wrapped in quotes, parentheses, or in a "\" comment line,
> "RM> but preferable would be one that read a file of ANS standard words
> "RM> and only upper-cased those words.  This can be done in mf with
> it's
> "RM> search and replace, but it's tedious.  

> I guess, convertion is needed for compilation only and not for reading.

        Conversion is also needed for publishing.  Standard words should
be all caps, to work whatever.  Words defined in the source may be either
or mixed -- as long as there are no assumptions that words may be
distinguished based on case alone.

Quote:
> For converting case insensitive writing, it is enough to uppercase all.

        I prefer minimum mods to universal upper casing, but ...

Quote:
> One exception should be taken care of when writing the source (not when
> converting): Use of [CHAR] <character> needs to withstand the
> conversion, when written for a case insensitive machine.

        This adds to the list of things not to upper case in a "upper case
everything in site" strategy:
        lines following \
        text between " " (inclusive of S" ", EMIT" " etc.)
        text between ( ) (inclusive of .( ) etc.)
        character following [CHAR] and CHAR

Any more?

Virtually,

Bruce R. McFarling, Newcastle, NSW



Fri, 26 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug


"RM>    Conversion is also needed for publishing.  Standard words
should
"RM> be all caps, to work whatever.  Words defined in the source may be
"RM> either or mixed -- as long as there are no assumptions that words
"RM> may be distinguished based on case alone.

I want to be able to have sources readable first of all. I want TO BE
able TO HAVE sources readable first OF ALL. IF I continue WITH writing
THE latter style mayBE YOU GET An idea WHAT THIS IS about. Surely
nothing about standards, and just a personal preference.

If you write for publishing, so I'd assume you did it from the moment of
writing to be for the purpose and not rely on a conversion tool... (if
it were sources from someone else, I guess you had to respect the
author's layout).

"RM>    This adds to the list of things not to upper case in a "upper
"RM> case everything in site" strategy:
"RM>    lines following \
"RM>    text between " " (inclusive of S" ", EMIT" " etc.)
"RM>    text between ( ) (inclusive of .( ) etc.)
"RM>    character following [CHAR] and CHAR

I have more than one (source code) parsing conversion tools here, each
for its purpose. If I were not stuck with several other tasks, maybe
this one for 'smart' uppercasing could come in. But I never needed it:
either I write with a context bound capitalizing style (which I find
easier to read, but it needs a cases independant parser), or it is all
uppercase, or all is changed to uppercase (if a parser demands it) with
a more trival kind of tool, so it is for compilation only - then I see
no need for to hide a personal style of layout for human reading. Anyway
AS TO BE seen above, YOU MAY guess THAT I hate THIS VERY strange mixed
CASES lay-out, since IT HAS nothing TO DO WITH reading TEXT (and makes
sources reading harder than necessary - IT IS MORE EASY THEN, TO READ
ALL-UPPERCASE INSTEAD).

If it comes very hard, so I may type some lot of times 'ESC u' in Emacs,
which may be faster than programming, measured against how rarely I need
it. ;) Let's not forget that in Forth this is dealing with a magnitude
more of different names than in most other languages. This plays a role
for readability in a different kind, so rules may not that easily be
borrowed from the programming neighbourhood. Say, e.g., how many
programming languages combine the existance of defining words with the
lack of syntactic parsing?



Sat, 27 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:


> "RM>    Conversion is also needed for publishing.  Standard words
> should
> "RM> be all caps, to work whatever.  Words defined in the source may be
> "RM> either or mixed -- as long as there are no assumptions that words
> "RM> may be distinguished based on case alone.

> I want to be able to have sources readable first of all. I want TO BE
> able TO HAVE sources readable first OF ALL. IF I continue WITH writing
> THE latter style mayBE YOU GET An idea WHAT THIS IS about. Surely
> nothing about standards, and just a personal preference.

        Standard words in lower case gives an implementation dependency on
case insensitive interpretation that need not be there.  You can throw
lower case versions of ANS standard CORE words at an ANS forth
implementing the words without those words doing what you want them to.
Sounds like it has something to do with standard to me.

Quote:
> If you write for publishing, so I'd assume you did it from the moment of
> writing to be for the purpose and not rely on a conversion tool... (if
> it were sources from someone else, I guess you had to respect the
> author's layout).

        I am not going to distribute tools along with anything I write for
academic publishing if it requires me to include unecessary implementation
dependencies.  Of course if it is under copyright, I'd have to seek
permission to distribute them, and if its in the public domain, I can do
it without permission.  But this is one of those little "gotcha's"
[Note 1] about Forth that makes it difficult to use in academic work that
that ANS can help us avoid, and I not about to distribute uneccessarily
unportable source.

Virtually,

Bruce R. McFarling, Newcastle, NSW

[ Note 1] gotcha: slang -- "I got you!" = "gotcha!" as a way to say, for
example, "I tricked you!"



Sun, 28 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:

> So I copied a case that involved moving a rock onto a target, and put in
> this string, with its successor:



Thanks. I never got up to level 11, since I find sokoban dull.

--
Bernd Paysan
"Late answers are wrong answers!"
http://www.informatik.tu-muenchen.de/~paysan/



Sun, 28 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

In article <Pine.PMDF.3.95.971208163906.690115128A


Quote:
>    This adds to the list of things not to upper case in a "upper case
>everything in site" strategy:
>    lines following \
>    text between " " (inclusive of S" ", EMIT" " etc.)
>    text between ( ) (inclusive of .( ) etc.)
>    character following [CHAR] and CHAR

Be careful with S"   "  since it might EVALUATEd.


Sun, 28 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:

> In article <Pine.PMDF.3.95.971208163906.690115128A


> >       This adds to the list of things not to upper case in a "upper case
> >everything in site" strategy:
> >       lines following \
> >       text between " " (inclusive of S" ", EMIT" " etc.)
> >       text between ( ) (inclusive of .( ) etc.)
> >       character following [CHAR] and CHAR

> Be careful with S"   "  since it might EVALUATEd.

        Yeah.  I don't have anything against a semi-automatic stage, that
detects when an ANS standard word is sitting inside an S" " string, and
asks whether or not to capitalise.  After all, the tool would only have
to be run over a source file once.

Virtually,

Bruce R. McFarling, Newcastle, NSW



Mon, 29 May 2000 03:00:00 GMT  
 SOKOBAN.F Bug

Quote:


>> So I copied a case that involved moving a rock onto a target, and put in
>> this string, with its successor:


>Thanks. I never got up to level 11, since I find sokoban dull.

Perhaps more interesting:  Why this bug?

Leo Wong

http://www.albany.net/~hello/



Tue, 30 May 2000 03:00:00 GMT  
 
 [ 18 post ]  Go to page: [1] [2]

 Relevant Pages 

1. delimiters (was: SOKOBAN.F Bug)

2. Minor bug with FS in gawk 3.0.x

3. FINALLY, The Sokoban Contest Winner

4. Sokoban Contest

5. My 1995 Sokoban Contest Entry

6. Programmable Robotic Sokoban with Elica

7. Programmable Robotic Sokoban with Elica

8. Sokoban in Oberon for Linux

9. Sokoban

10. Sokoban

11. Array out of bounds in Sokoban solver and hash of arrays

12. BUGS, BUGS, BUGS, BUGS, C4 BUGS

 

 
Powered by phpBB® Forum Software