FVP rush to the rescue

This article is about how elements of functional programming help in real life. There are many such articles on Habré, but as far as I remember, about Forth , nobody has written about this topic yet. In addition, I am not going to breed a theory about this (the theoretician of me is still the one). I will talk about a purely practical problem, which I encountered just yesterday. I hope my story will be interesting.


Strictly speaking, this is not about Forth , but about its specialized ForthScript dialect developed by Greg Schmidt, as part of his Axiom Development Kit project, for describing board games. I have been using this product for quite some time and managed to develop several games with it. Currently, I am working on a very interesting, in my opinion, game , something reminiscent of Go . I already mentioned it in the previous article . It will look something like this:


')
Display of field names is included specifically. The fact is that the platform Zillions of Games , on which the development is being carried out, does not allow placing the figures “with imposition” on each other. Each "figure" here is composed of 4 parts - tiles. Understanding this fact is extremely important for later presentation. The board becomes 4 times larger, and the code is more complicated (ZSG notation becomes completely unreadable), but the result is definitely worth it.

As you can easily guess, the board in this game is three-dimensional. For the 7x7 game variant, the easiest way to store the state is 14x14x7 = 1372 positions. In ZRF, there are no problems with this (this language allows defining multidimensional boards), but unfortunately, I have a problem with the ZRF itself. The shape removal algorithms, when performing a move in Margo, are too complex for this language. In addition, AI ZoG certainly can not cope with this game. Using Axiom, I try to kill two of these birds with one stone. Alas, Axiom brings new challenges. In particular, this product does not allow to define three-dimensional boards:


It is easy to see that a two-dimensional board is defined here. The layers of the third dimension are simply “laid out” one after the other along the Y coordinate. In fact, Axiom determines a one-dimensional array, guided by the following scheme:


Fields of the board are numbered from top to bottom from left to right. In addition, constants are automatically created that are used for naming fields, by analogy with a chessboard. For the 8x7 board shown above, there is no difference whether the name of position a2 or its corresponding numerical value will be used in the code (this is often convenient). It is allowed to define each position manually, without using the grid , but I’m afraid to even imagine the volume of such a description for a 14x14x7 board and, most importantly, its load time.

The grid design provides another extremely useful feature. In the game, not only the positions themselves are important for us, but also the connections between them. When using the grid design, the directions defining these relationships can be given by a simple increment of coordinates:


Traditionally, for the names of directions used one- and two-letter designations by the names of the cardinal points. Having the definitions of directions, you can easily write the following code (controlling the movement of the figure to the north):

 : move-to-north ( -- ) n verify (   ,     ) empty? verify (    ) from here move (   ) add-move (    ) ; 

Of course, writing one such (even if very small) function for each direction would be quite depressing. Here, the first- order functions (but not the last) come to our aid. The n direction is a function that changes the current position (as a side effect) and returns a sign of its success. We can take the address of this function (words, in Forth terminology) and transfer it to another function. It will only be necessary to perform the function posted at the received address. Here is how it is done:


This is a very common Axiom idiom and a rare program that does without it (of course, the more complicated the generalized function is, the more confusing this whole balancing act is). But back to Margo. The implementation of the board I described above works up to the size of 8x8 (16x16x8 = 2048 positions), but for the board 9x9 (18x18x9 = 2916 positions) it stops working. Apparently this value is more than the maximum allowable size of the board (I did not find references to this limitation in the Axiom documentation). Of course, I could not accept this. Only not after I long and stubbornly drew Hosi for this board (in fact, four san- sans and one tengen , but they are exactly what is required for a board of this size).

If you carefully look at the picture at the beginning of the article and the definition of the board that I gave above, you can understand that it will mainly be stored in the air. Each layer, starting with the second, contains less and less shapes. Keeping the lines in which the figures will never appear, we spend the RAM is not very rational. There would be no point in optimizing, if everything worked anyway, but since we were very much in the constraints of Axiom, why not try to store fewer lines for each subsequent layer? This is also not the most optimal way, but it is much more economical than the previous one:


For a 9x9 board you only need to store 18x90 = 1710 positions. Such volume Axiom is quite capable. Notice the change in the DDIR constant used to determine the direction “inward” of the board (I forgot to say that we will keep the board upside down). Unfortunately, this is not the only change needed. What happens if you try to go down from any position of the zero line? Since DDIR has become less by one, we will be on the last line of the same layer! This can break the whole logic of the game.

Also, it may turn out badly if you go from the last row of the layer to the south or from the first to the north (except for the zero row of the first layer). It would be possible to prohibit all unnecessary connections manually, but I don’t really like to work a lot with my hands. Let's try to solve the puzzle in an intelligent way. To begin, learn to determine the current coordinates. This is quite simple:

 : get-x ( pos -- x ) COLS MOD ; : get-y ( pos -- y ) COLS / ; 

Determining the layer boundary line is a bit more difficult:

 : is-edge? ( -- ? ) COLS here get-y BEGIN 2DUP <= IF OVER - SWAP 2 - SWAP FALSE ELSE TRUE ENDIF UNTIL SWAP 1- OVER = SWAP 0= OR ; 

The essence of this stack acrobatics is simple. We subtract from the current line number (until there is anything to be subtracted from) the layer width, starting with COLS and decreasing this value by 2 in each iteration of the loop. If, as a result, the value is zeroed out or became one less than the current layer width - the boundary line. Now, it is easy to prohibit all movements from these lines (for directions of interest to us):

 {directions -1 0 {direction} n-internal 1 0 {direction} s-internal 0 1 {direction} e 0 -1 {direction} w -1 -1 {direction} nw 1 -1 {direction} sw -1 1 {direction} ne 1 1 {direction} se DDIR 0 {direction} d-internal UDIR 0 {direction} u directions} : common-dir ( 'dir -- ? ) is-edge? IF (  ? ) DROP FALSE (         ) ELSE EXECUTE (         ) ENDIF ; : n ( -- ) ['] n-internal common-dir ; : s ( -- ) ['] s-internal common-dir ; : d ( -- ) ['] d-internal common-dir ; 

Higher-order functions are back with us! Unfortunately, this code contains a serious error. The fact is that only for a downward direction, it is necessary to prohibit movement from any boundary line. The northern direction should be prohibited only in the upper boundary lines, and the southern - in the lower ones. Is-edge predicate ? should be calculated differently, depending on the chosen direction! The ominous shadow of "copy-paste" reappears before us. Fortunately, no one forbids passing pointers to functions from multiple arguments. Here is the correct implementation :


Keep your eyes and mind open. In order to face functional programming it is not necessary to engage in academic activities. Higher order functions may be closer than you think.