Manipulating Return Addresses 
Author Message
 Manipulating Return Addresses

Quote:

>Gordon's FOSM runs on MPE's GEMForth/ST for the Atari, which both of us
>owned but not any longer.  Now I want to do some more work with it (and
>maybe share it with this newsgroup) I have to port it to F-PC or ANS
>first.  And perhaps porting issues are an interesting challenge :)

Chris, the architecture with double-cell return addresses is a mistake
for which the forth community pays and will pay
(although it seems that some people like to posess what they pay for).

Do not use F-PC for FOSM! The FOSM source will lose its idea on F-PC,
even if it will work (=even if you will be enough persistent to finish it).
You'll create a crippled version which will (it may, but let's think it will)
become popular. If you really need namely F-PC, you may use the threaded code
emulator---it uses nothing that could not run on an ANSIfied F-PC.

--
Michael L. Gassanenko



Mon, 25 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses

Quote:

> Gordon's FOSM runs on MPE's GEMForth/ST for the Atari, which both of us
> owned but not any longer.  Now I want to do some more work with it (and
> maybe share it with this newsgroup) I have to port it to F-PC or ANS
> first.  And perhaps porting issues are an interesting challenge :)

If you're going to port it, please consider ANS Forth. One of the hopes of
the standard was that packages such as this would become useful to a large
audience, not just those who use a particular Forth implementation.

There is an ANS-Compatibilty program available for F-PC, so you can use this
to develop the code. But I think it would benefit us all if you found some
other way to implement the backtracking that hacking the return stack.

--

Finnigan Corporation            
2215 Grand Avenue Parkway        Tel: (512) 251-1574
Austin, TX  78728-3812           Fax: (512) 251-1547



Tue, 26 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses



Quote:

>> Gordon's FOSM runs on MPE's GEMForth/ST for the Atari, which both of us
>> owned but not any longer.  Now I want to do some more work with it (and
>> maybe share it with this newsgroup) I have to port it to F-PC or ANS
>> first.  And perhaps porting issues are an interesting challenge :)

>If you're going to port it, please consider ANS Forth. One of the hopes of
>the standard was that packages such as this would become useful to a large
>audience, not just those who use a particular Forth implementation.
>There is an ANS-Compatibilty program available for F-PC, so you can use this
>to develop the code.

Yes, that's what I've done.  FoSM is now successfully ported to ANS and
also to F-PC.  I'm adding some examples and instructions before posting.

Quote:
>But I think it would benefit us all if you found some
>other way to implement the backtracking than hacking the return stack.

No, I'm sticking with manipulating Return Addresses.  I'm not writing
this from scratch but giving Gordon's brainchild a wider audience.
Ariel Scolnicov (Forth Dimensions July & Sep.'92) has already given us a
pattern matcher which avoids 'hacking the return stack'.  Gordon's
approach is of interest to me _because_ it compiles patterns into
executable words - an approach impossible in other languages.

Previous posters have reported some Forths which will not be able to run
FoSM, but I hope most will.  Pattern-matching is quite fascinating -
very different from straight-line programming.

Bye for now                                                       _
                                          _______________________| |_____
Chris Jakeman                            / _Forth_Interest_Group_| |____/
                                        / /_  __  ______  _   _  | | __
at Peterborough                        / __/ / / / __  / | | | | | |/ /
(a cathedral city                     / /   / / / /_/ /  | \_| | |   <
 80 miles north of London)           /_/   /_/ /___  /    \____| |_|\_\
Where do you come from?                           / /
                                   ______________/ /     United Kingdom
Voice +44 (0)1733 346477          /_______________/          Chapter



Thu, 28 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses

Quote:


> >If you're going to port it, please consider ANS Forth. One of the hopes of
> >the standard was that packages such as this would become useful to a large
> >audience, not just those who use a particular Forth implementation.

> Yes, that's what I've done.  FoSM is now successfully ported to ANS and
> also to F-PC.  I'm adding some examples and instructions before posting.

> >But I think it would benefit us all if you found some
> >other way to implement the backtracking than hacking the return stack.

> No, I'm sticking with manipulating Return Addresses...

> Previous posters have reported some Forths which will not be able to run
> FoSM, but I hope most will...

If you've truly written an ANS Forth version, it will run on _any_
ANS-compatible system.  However, it's hard to imagine doing the return address
manipulation you've been discussing here in a way compatible with ANS Forth.  
Surely there's a better way.

--
Elizabeth D. Rather
FORTH, Inc.                 Products and services for
111 N. Sepulveda Blvd.      professional Forth programmers
Manhattan Beach, CA  90266  since 1973.  See us at:
310-372-8493/fax 318-7130   http://www.forth.com



Fri, 29 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses

Quote:



> > >If you're going to port it, please consider ANS Forth. One of the hopes of
> > >the standard was that packages such as this would become useful to a large
> > >audience, not just those who use a particular Forth implementation.

> > Yes, that's what I've done.  FoSM is now successfully ported to ANS and
> > also to F-PC.  I'm adding some examples and instructions before posting.

> > >But I think it would benefit us all if you found some
> > >other way to implement the backtracking than hacking the return stack.

> > No, I'm sticking with manipulating Return Addresses...

> > Previous posters have reported some Forths which will not be able to run
> > FoSM, but I hope most will...

> If you've truly written an ANS Forth version, it will run on _any_
> ANS-compatible system.  However, it's hard to imagine doing the return address
> manipulation you've been discussing here in a way compatible with ANS Forth.
> Surely there's a better way.

How about using CATCH and THROW, nothing says they can only be used for errors.
At least that is a known "standard" way of manipulating the return stack.

Tom Zimmer



Fri, 29 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses



Quote:


>> >If you're going to port it, please consider ANS Forth. One of the hopes of
>> >the standard was that packages such as this would become useful to a large
>> >audience, not just those who use a particular Forth implementation.

>> Yes, that's what I've done.  FoSM is now successfully ported to ANS and
>> also to F-PC.  I'm adding some examples and instructions before posting.
>If you've truly written an ANS Forth version, it will run on _any_
>ANS-compatible system.  However, it's hard to imagine doing the return address
>manipulation you've been discussing here in a way compatible with ANS Forth.  
>Surely there's a better way.

Here is an extract from the new ANS version:
\ FoSM is an ANS Forth Program with Environmental Dependencies:
\ - requiring -ROT NIP TUCK WITHIN ?DO and \ from the Core Extensions
\    word set.
\ - requiring CS-ROLL from the Control Flow word set.
\ - using lower case for standard definition names.
\ - requiring the non-standard words below which manipulate Return
\   Addresses.
\   RA-sys below indicates an implementation-defined return address
\   which may be more than 1 cell wide:
\   - RAStash   ( -- ) Allow access to Return Stack by removing RA-sys
\                      if kept on Return Stack.  Only one RA-sys is
\                      stashed at any time.
\   - RAUnstash ( -- ) Undo RAStash.
\   - RAGet     ( -- RA-sys ) Move RA-sys to Data Stack.
\   - RACopy    ( -- RA-sys ) Copy RA-sys to Data Stack.
\   - RAPut     ( RA-sys -- ) Move RA-sys back from Data Stack.
\   - RADrop    ( RA-sys -- ) Drop RA-sys from the Data Stack.

Porting FoSM has been a process of refinement, from a single Forth
(MPE's GEMForth/ST) to many ANS Forths and Forths like F-PC that can
provide some ANSI compatibility.  Some ANS Forths cannot provide access
to Return Addresses and will not be able to provide the environment FoSM
needs.

Pattern-matching is possible without manipulating the Return Addresses.
That's how it's done in Pascal etc..  But I reckon that manipulating
Return Addresses is the natural way to implement backtracking.  What
FoSM does is extend the Forth compiler to create executable words
(patterns) which match the current string.  

This seems a very Forth-like way to do things and perhaps the next round
of ANS might consider including it.
Bye for now                                                       _
                                          _______________________| |_____
Chris Jakeman                            / _Forth_Interest_Group_| |____/
                                        / /_  __  ______  _   _  | | __
at Peterborough                        / __/ / / / __  / | | | | | |/ /
(a cathedral city                     / /   / / / /_/ /  | \_| | |   <
 80 miles north of London)           /_/   /_/ /___  /    \____| |_|\_\
Where do you come from?                           / /
                                   ______________/ /     United Kingdom
Voice +44 (0)1733 346477          /_______________/          Chapter



Sat, 30 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses



Quote:



>> > >But I think it would benefit us all if you found some
>> > >other way to implement the backtracking than hacking the return stack.

>> > No, I'm sticking with manipulating Return Addresses...

>> > Previous posters have reported some Forths which will not be able to run
>> > FoSM, but I hope most will...

>> If you've truly written an ANS Forth version, it will run on _any_
>> ANS-compatible system.  However, it's hard to imagine doing the return address
>> manipulation you've been discussing here in a way compatible with ANS Forth.
>> Surely there's a better way.

>How about using CATCH and THROW, nothing says they can only be used for errors.
>At least that is a known "standard" way of manipulating the return stack.

Thanks for the idea, Tom, but I don't think it will work.  Yes, you
could use THROW to back out of a pattern when a mis-match was found, but
after the mis-match, you will want to resume from the most recent point
where there was an alternative and try that.  In other words, you are
jumping back into a pattern at a point where you've been before.  I
can't see how to do that with the standard CATCH and THROW.
Bye for now                                                       _
                                          _______________________| |_____
Chris Jakeman                            / _Forth_Interest_Group_| |____/
                                        / /_  __  ______  _   _  | | __
at Peterborough                        / __/ / / / __  / | | | | | |/ /
(a cathedral city                     / /   / / / /_/ /  | \_| | |   <
 80 miles north of London)           /_/   /_/ /___  /    \____| |_|\_\
Where do you come from?                           / /
                                   ______________/ /     United Kingdom
Voice +44 (0)1733 346477          /_______________/          Chapter


Sat, 30 Jan 1999 03:00:00 GMT  
 Manipulating Return Addresses

Quote:






> >> > >But I think it would benefit us all if you found some
> >> > >other way to implement the backtracking than hacking the return stack.

> >> > No, I'm sticking with manipulating Return Addresses...

> >> > Previous posters have reported some Forths which will not be able to run
> >> > FoSM, but I hope most will...

> >> If you've truly written an ANS Forth version, it will run on _any_
> >> ANS-compatible system.  However, it's hard to imagine doing the return address
> >> manipulation you've been discussing here in a way compatible with ANS Forth.
> >> Surely there's a better way.

> >How about using CATCH and THROW, nothing says they can only be used for errors.
> >At least that is a known "standard" way of manipulating the return stack.

> Thanks for the idea, Tom, but I don't think it will work.  Yes, you
> could use THROW to back out of a pattern when a mis-match was found, but
> after the mis-match, you will want to resume from the most recent point
> where there was an alternative and try that.  In other words, you are
> jumping back into a pattern at a point where you've been before.  I
> can't see how to do that with the standard CATCH and THROW.

I suppose if you are are not returning up to the same caller, it could be
more complex, you would have to pass back a code to tell all the CATCHes
above, which one was to actuall catch the THROW.  If you give codes to
particular levels, then something like;

: process      whatever if TWO_LEVEL THROW then
               whatever-else if THREE_LEVEL THROW then ;

: level_three  ['] process catch dup THREE_LEVEL =
               if    drop process-at-level-three
               else  throw
               then ;

: level_two    ['] level_three catch dup TWO_LEVEL =
               if    drop process-at-level-two
               else  throw
               then ;

could work.  Might be slower as well, but also might be STANDARD.

Tom Zimmer



Mon, 01 Feb 1999 03:00:00 GMT  
 Manipulating Return Addresses



Quote:


>> >> Surely there's a better way.

>> >How about using CATCH and THROW, nothing says they can only be used for
>errors.
>> >At least that is a known "standard" way of manipulating the return stack.

>> Thanks for the idea, Tom, but I don't think it will work.  Yes, you
>> could use THROW to back out of a pattern when a mis-match was found, but
>> after the mis-match, you will want to resume from the most recent point
>> where there was an alternative and try that.  In other words, you are
>> jumping back into a pattern at a point where you've been before.  I
>> can't see how to do that with the standard CATCH and THROW.

>I suppose if you are are not returning up to the same caller, it could be
>more complex, you would have to pass back a code to tell all the CATCHes
>above, which one was to actuall catch the THROW.

<snip>

Your ideas are much appreciated, but I still don't think it will work
because we need to jump back _into_ a pattern.  For example, the 3
patterns:
        << ABA  A { B } A >>    matches "AA" and "ABA"
        << ACA  A { C } A >>    matches "AA" and "ACA"
        << Pattern  ABA ACA >>
will match only "AAAA", "ABAAA", "AAACA" and "ABAACA"

If we try to match the string "ABACA", then pattern ABA will match
"ABA.. and save the token for the possible alternative match "AA... on
the Data Stack on top of a Return Address.  The next pattern ACA will
try to match ...CA" and fail.

All failures backtrack by executing the token on the Data Stack.  There
will be one left by << which unnests out of ACA.  Then there will be
another left by >> which re-nests back into ABA.  Finally there is one
left by {.  This last token pulls a Return Address off the Data Stack
and uses it to resume from part-way through ABA.

I hope this hasn't muddied the waters still further.  CATCH isn't enough
because it one way only - un-nesting words.

Bye for now                                                       _
                                          _______________________| |_____
Chris Jakeman                            / _Forth_Interest_Group_| |____/
                                        / /_  __  ______  _   _  | | __
at Peterborough                        / __/ / / / __  / | | | | | |/ /
(a cathedral city                     / /   / / / /_/ /  | \_| | |   <
 80 miles north of London)           /_/   /_/ /___  /    \____| |_|\_\
Where do you come from?                           / /
                                   ______________/ /     United Kingdom
Voice +44 (0)1733 346477          /_______________/          Chapter



Tue, 02 Feb 1999 03:00:00 GMT  
 Manipulating Return Addresses

Quote:



> >I suppose if you are are not returning up to the same caller, it could be
> >more complex, you would have to pass back a code to tell all the CATCHes
> >above, which one was to actuall catch the THROW.
> <snip>

> Your ideas are much appreciated, but I still don't think it will work
> because we need to jump back _into_ a pattern.  For example, the 3
> patterns:
>         << ABA  A { B } A >>    matches "AA" and "ABA"
>         << ACA  A { C } A >>    matches "AA" and "ACA"
>         << Pattern  ABA ACA >>
> will match only "AAAA", "ABAAA", "AAACA" and "ABAACA"

> If we try to match the string "ABACA", then pattern ABA will match
> "ABA.. and save the token for the possible alternative match "AA... on
> the Data Stack on top of a Return Address.  The next pattern ACA will
> try to match ...CA" and fail.

> All failures backtrack by executing the token on the Data Stack.  There
> will be one left by << which unnests out of ACA.  Then there will be
> another left by >> which re-nests back into ABA.  Finally there is one
> left by {.  This last token pulls a Return Address off the Data Stack
> and uses it to resume from part-way through ABA.

> I hope this hasn't muddied the waters still further.  CATCH isn't enough
> because it one way only - un-nesting words.

I'm slowly getting a clearer picture, and it does appear that there may not
be a good standard way to handle this kind of problem.  It sounds to me
like what is needed is a state machine, and a bunch of gotos.

Thanks for all the explaination :-)

Tom Zimmer



Wed, 03 Feb 1999 03:00:00 GMT  
 Manipulating Return Addresses

Let me first present the problem in a simplified context:

Assume that ONE-or-TWO ( -- n ) can deliver two solutions: on calling
it, it delivers 1; when backtracking into it, it succeeds again,
delivering 2; then it fails on backtracking. The word FAIL always
fails. Let's define

: foo \ always fails
 ONE-or-TWO . FAIL ;

Calling foo prints 1, then it prints 2, the fails.

How can we implement this?

I will use THROW to implement FAIL, but this does not work with calls
and returns as we know them. So we have to use a different
implementation of calling and EXITing. The trouble for backtracking is
the EXIT, so let's make it explicit (if you ever see
"continuation-passing style", that's what this is about).

We have to make the return information explicit; in Forth (without
locals), this is just the return stack. Let's implement it as linked
list; a return address is represented as xt:

: push-return ( ret-stack1 ret-addr -- ret-stack2 )
 2 cells allocate throw
 swap over cell+ !
 swap over ! ;

: pop-return ( ret-satck1 -- ret-stack2 ret-addr )


: return ( ret-stack1 -- ret-stack2 )
\ never EXITs; stack-effect with respect to the word returned to.
    pop-return execute ;

This, of course, requires some transformations of the programs that
should use this explicit return mechanism. E.g.,

: bar ( ... -- ... )
 PRIM1 DEF1 PRIM2 PRIM3 ;

becomes

: bar-part2 ( ... ret-stack1 -- ... ret-stack2 )
 >r PRIM2 PRIM3 r> return ;

: bar ( ... ret-stack1 -- ... ret-stack2 )
 \ does not EXIT; stack-effect with respect to "return"ing
 >r
 PRIM1
 ['] bar-part2 r> push-return
 DEF1 \ def1 never EXITs, so no return is necessary
;

This does not look pretty (and with control structures it's even
worse), but the transformation can be done automatically. It also
leaks memory, but in the context of backtracking we could use a memory
management mechanism (instead of allocate) that reclaims memory on
failure. Moreover, all these never returning definitions and EXECUTEs
could overflow the return stack; but they are tail calls, so the Forth
system can use tail call optimization.

Let's get back to backtracking.

: choice
   \ works like return ( ret-stack1 -- ret-stack2 ), but creates a choicepoint
   \ i.e., it catches a failure;
   \ EXITs upon failure with stack effect ( ret-stack -- )
   pop-return CATCH
   dup 1 <> if \ it's not a failure, but something else
       THROW
   then
   drop ;

Here's how FAIL and ONE-or-TWO could be implemented:

: FAIL \ neither EXITs nor returns
 1 THROW ;

: ONE-or-TWO ( ret-stack1 -- n ret-stack2 )
 >r

 2 r> return ;

It should be helpful to remember that choice behaves like return,
except that it will catch a failure, upon which it will EXIT and
continue with the rest of ONE-or-TWO.

We have to convert foo to use the explicit return mechanism:

\ original:
\ : foo \ always fails
\  ONE-or-TWO . FAIL ;

: foo-part2 ( ret-stack -- ... ) \ never EXITs, never returns
\ we can treat "." as primitive here; it does not do choicepoints, failure etc.
    >r . FAIL ;

: foo ( ret-stack -- ... ) \ never EXITs, never returns
    ['] foo-part2 swap push-ret ONE-OR-TWO ;

Now we just need a wrapper to get into and out of the
return/backtracking execution mode:

: success-throw
    \ get out of the return/backtracking mode
    2 throw ;

: wrapper ( xt -- )
    \ execute xt in return/backtrackin mode
    ['] success-throw 0 push-return swap catch
    case
      1 of ." failure" endof
      2 of ." success" endof
      throw
    endcase ;

and we can call foo thus:

' foo wrapper

So: it's ugly, but it's ANS Forth. I'm sure you can find ways to make
it syntactically more pleasant. In applications such as FOSM, it may
even be possible to hide the mechanism completely.

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Sat, 06 Feb 1999 03:00:00 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. Manipulating Return Addresses

2. Manipulating Return Addresses

3. Is there an extension for manipulating IPv4 addresses?

4. How to manipulate return path

5. Return Address

6. Return code from ADDRESS

7. hostent extension problem - returning the ip address

8. Modifying return address from interrupt.

9. Return Address

10. 1750A compilers? [With return address this time]

11. how to get the return address in Fortran?

12. HandyMailTemplates - how to get email address from a recipients address

 

 
Powered by phpBB® Forum Software