If a function can recurse, can a method do so as well?

If you have any questions, remarks, ... if you need help... its here...

If a function can recurse, can a method do so as well?

Postby bobgillies » 18 Feb 2017 06:59

Hi Franck, I've seen the Manual's example of a definition using recursion. But can an object's method recurse too? If so, I would appreciate seeing a simple coding example as to how it would be structured and what side-effects I would need to address.

Thank you in advance,

Bob
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby Franck » 18 Feb 2017 11:14

Hi,

Yes, a method can recurse too, provided that you put a receiver on the stack before calling it.

For instance :
Code: Select all
Integer method: fact -- n!
   self ifZero: [ 1 ] else: [ self self 1- fact * ] ;


Franck
Franck
 
Posts: 145
Joined: 29 Oct 2014 19:01

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 19 Feb 2017 21:21

Hi Franck,
In the example you've given, are my following assertions correct if I were to explain this to someone else?

1. The INTEGER on the stack is the number referred to by SELF.
2. SELF only refers to objects.
2. The INTEGER referred to by SELF is the RECIEVER.
3. All positive and negative integers in oforth are a class of object called aINTEGER.

And in the example you've given:
4. SELF ifZero: is an equivalent process for " dup ifZero " because you're putting one extra copy of aINTEGER on the stack.
5. else: [ Self Self 1- Fact * ] is an equivalent process for " else: [ 2dup 1- Fact * ] " because you're putting two extra copies of aINTEGER on the stack.

Bob
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby Franck » 20 Feb 2017 00:33

Hi

1 and 2 : Yes

3 : all positive and negative integers in oforth are objects of class called Integer.

4 Not quite.
When the code start the receiver has been removed from the stack and stored into the "self" parameter.
The receiver is no more on the stack.
So SELF ifZero: just pushes back the receiver on the stack, it is not an extra copy.

5. Same : self self pushes the receiver 2 times on the stack.

Think about methods as words with an implicit parameter : self

Code: Select all
Integer method: fact
   self ifZero:[ 1 ] else: [ self self 1- fact * ] ;

: fact ( self ) 
   self ifZero:[ 1 ] else: [ self self 1- fact * ] ;


Thoses two implementations of #fact are doing the same thing. One is a method, the other is a function.

Franck
Franck
 
Posts: 145
Joined: 29 Oct 2014 19:01

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 20 Feb 2017 01:11

Hi Franck,
Ok, I see now. Integer is a class and positive and negative numbers are objects of that class.

In regards to SELF, if I understand it right, objects are ALWAYS popped off the stack into the return stack, like ">R" in ANSI Forth, but in oforth this is automatic for objects. The return stack is "off limits" in oforth except to push the object back onto the stack using SELF.
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby Franck » 20 Feb 2017 12:49

That's right.

For self, and only with methods (not with functions), yes, one object is popped off the stack into the return stack (like >R, yes).
In Oforth, this is automatic for the receiver of a method and for parameters (word or method).

The return stack is "off limits", except :
- For the method's receiver to push it back on the stack using self (like R@ ).
- For locals (parameters or variables) : you can push thems back using their name and you can update them on the return stack using "->" word.

For instance :

Code: Select all
: sumDigits ( n -- m )
   0 while ( n ) [ n 10 /mod ->n + ] ;


Franck
Franck
 
Posts: 145
Joined: 29 Oct 2014 19:01

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 24 Feb 2017 17:11

Hi Franck, here's a neat side effect I wasn't expecting. It would seem that the THEN clause gets pushed onto the return stack each time SELF is called.

: barfly (self )
self 8 > ifTrue: [ "\n\nI've had me a beer ev'time ah been here!" .
"\n\nAnd ahwul have me another! " . return ]
else: [ "chug " . self 1+ barfly ]
"\nAnd another!" .
;

true barfly

:lol:
Last edited by bobgillies on 24 Feb 2017 17:25, edited 1 time in total.
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 24 Feb 2017 17:24

I was just being silly but seriously I can think of using that feature in a recursive coding challenge I'm engaged in. Do the computer algorithms on recursion take into account this kind of specific feature I've displayed or are there different flavors of recursion?

The reason for my asking is that I'm getting close to coding an 8 Queens problem and I'm just now getting around to the recursive part. I haven't quite yet got into my comfort zone regarding recursion.

Cordially,
Bob
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 24 Feb 2017 21:46

There are many examples around of the algoritm on the web, but I didn't see an oforth example on Rosettacode.org. Unless someone beats me to it, I hope to put up my version there but I'm not at that point yet. :)
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 25 Feb 2017 00:15

Code: Select all
// global variables

tvar: board
tvar: laneMask
tvar: currentLane
tvar: queenCount
tvar: queenRank



//*************************************************************************************************

Object Class new: Queens
    ( numQueens, mutable lane ) 

Queens method: initialize( numQueens -- )
    numQueens := numQueens

//* lanes for downleft diagonal, downright diagonal, and vertical threats. *//
    ArrayBuffer newWith( 3 , 0 ) := lane   
    numQueens 2* to laneMask
         numQueens to queenCount
         0 to queenRank
         1 to currentLane
;

 Queens method: at        \ i -- x    //* I don't know why this works! *//
    @lane at
;

 Queens method: put       \ i x --   //* this too! *//
   @lane put
;

       


// queenPut method - mark the position in the vertical lane bit where
// the queen is placed for that row. Usage:   0b0010 Queens queenPut

 Queens method: queenPut  ( n  -- ) 
//  n = bitpattern. 0b0010 queen in the 3rd column of a 4x4 board.   

    1 @lane at n bitOr 1 swap @lane put
    2 @lane at n bitOr 2 swap @lane put
    3 @lane at n bitOr 3 swap @lane put
    queenRank 1+ to queenRank
    1 @lane at 2* laneMask 2* 1- bitAnd 1 swap @lane put
    2 @lane at 2/  2 swap @lane put 
;   

Queens method: nextSpot \
      queenCount queenRank == if "\nAll the queens solved" . return  then
      1 @lane at  2 @lane at  3 @lane at bitOr bitOr laneMask
      while ( dup )     //* while the bitmask has not shifted down to zero. *//
         [ 2dup bitAnd                 
            ifZero: [ 2/                 //*IF it's safe, place Queen in this spot.   *//
                      "\nQueen is to be put next at col" .  currentLane . break
                    ]                       
              else: [ 2/ ]              //* ELSE the lanes of attack are detected.  *//
                                        //* THEN increment the current spot. *//   
              currentLane 1+ to currentLane       
         ]
    2drop  1 to currentLane                           
;


//********************************************test*******************************************


// This code pattern works for a solved 4x4 board.
// next version needs needs for nextSpot to supply the
// next safe spot as a parameter for queenPut or terminate.


: firstTry
4 Queens new to board
0b1000 board queenPut
board nextSpot
0b0010 board queenPut
board nextSpot
;

: secondTry
4  Queens new to board
0b0100 board queenPut
board nextSpot
0b0001 board queenPut
board nextSpot
0b1000 board queenPut
board nextSpot
0b0010 board queenPut
board nextSpot
;

firstTry
secondTry
Last edited by bobgillies on 25 Feb 2017 00:36, edited 2 times in total.
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Next

Return to General

Who is online

Users browsing this forum: No registered users and 0 guests

cron