Effective ATS:
Let's start with package-based programming!

In this article, I present an example that makes use of a package for (generic) graph search. It should be plainly evident that this style of package-based programming can greatly facilitate sharing of ATS code, which is essential to building a community based on the ATS programming language system.

Generic Graph Search

A template-based implementation of generic graph search plus detailed explanation can be found on-line, which serves as the basis for the code used in this article and should therefore be thoroughly studied first.

Solving 8-Queen Puzzle

The famous 8-queen puzzle asks the player to find ways to put eight queen pieces on a chess board such that no queen piece can attack any other ones. In other words, no two queen pieces can be put on the same row, the same column, or the same diagnal. This puzzle can be readily solved with a tree-based search, which is a special case of graph search.

There is a package of the name atscntrb-bucs320-graphsearch for generic graph search that is stored on-line, and the content of the package is available for viewing here. One can simply use the npm tool (for node package management) to install the package directly by issuing the following command-line:

npm install atscntrb-bucs320-graphsearch

Or one can compose a file of the name package.json to direct npm regarding package installation.

The following lines in QueenPuzzle.dats are for statically loading some files in atscntrb-bucs320-graphsearch:

//
#define GRAPHSEARCH_DFS 1 // for depth-first search
//
#include "$PATSHOMELOCS/atscntrb-bucs320-graphsearch/mylibies.hats"
//
The #include directive indicates to patsopt, the ATS compiler, that the file following it should be included. Note that the variable PATSHOMELOCS in this case should be set to the name of the directory ./node_modules as npm installs packages in it. The name mylibies.hats is conventional in the sense that it refers to a file that should be only used to statically load files into certain namespaces. The content of this file is listed as follows:
//
staload GS = "./DATS/GraphSearch.dats"
//
(* ****** ****** *)
//
#ifdef
GRAPHSEARCH_BFS
staload GS_bfs = "./DATS/GraphSearch_bfs.dats"
#endif // #ifdef(GraphSearch_bfs)
//
(* ****** ****** *)
//
#ifdef
GRAPHSEARCH_DFS
staload GS_dfs = "./DATS/GraphSearch_dfs.dats"
#endif // #ifdef(GraphSearch_dfs)
//
Therefore, the two chosen namespaces are GS (for storing names in GraphSearch.dats) and GS_dfs (for storing names in GraphSearch_dfs.dats) in this case.

The rest of QueenPuzzle.dats is mostly similar to what is presented on-line on solving 8-queen puzzle. Basically, various function templates in GS and GS_dfs needs to be given specific implementations pertinent to the particular task of solving 8-queen puzzle. For instance, the following implementations are given because node marking is not needed for a tree-based search used in this case (as there are no circular paths in a tree):

//
implement
$GS_dfs.node_mark<>(nx) = ()
implement
$GS_dfs.node_unmark<>(nx) = ()
implement
$GS_dfs.node_is_marked<>(nx) = false
//

Playing Doublets Game

Doublets is a word game invented by Lewis Carroll (1832-1898), the author of children's classics "Alice in Wonderland". Given two words recognized in a chosen dictionary, they are said to be one-step connected if they differ precisely at one position in their spellings. Clearly, two connected words must contain the same number of characters. Two given words W1 and W2 are many-step connected if a sequence of words beginning with W1 and ending with W2 can be found such that any two consecutive words in this sequence are one-step connected. The game Doublets basically asks the player to tell whether two given words are many-step connected. For instance. head and tail form a doublet as is shown by the sequence: head, held, hell, tell, tall, tail. One may play Doublets on-line by visiting this link.

The following lines in Doublets.dats are for statically loading some files in atscntrb-bucs320-graphsearch:

//
#define GRAPHSEARCH_BFS 1 // for breadth-first search
//
#include "$PATSHOMELOCS/atscntrb-bucs320-graphsearch/mylibies.hats"
//
The #include directive indicates to patsopt that the file following it should be included. The name mylibies.hats is conventional in the sense that it refers to a file that should be only used to statically load files into certain namespaces. In this case, the two chosen namespaces are GS (for storing names in GraphSearch.dats) and GS_bfs (for storing names in GraphSearch_bfs.dats).

The rest of Doublets.dats is mostly similar to what is presented on-line on playing the doublets game.

Compiling and Testing

Please find in the following files the entirety of the code presented in this article:

package.json // for using with the npm tool-chain
QueenPuzzle.dats // solving 8-queen puzzle with GraphSearch_dfs
DoubletsPlay.dats // implementing Doublets based on GraphSearch_bfs
In addition, there is an accompanying Makefile for compiling and testing the code.


This article is written by Hongwei Xi.