Effective ATS:
Let's build a template-based package!

ATS is a feature-rich language, and dependent types, linear types and embeddable templates can be seen as three of its most prominent features. The richness of programming features can potentially make it highly demanding for a programmer to rein in the inherent complexity associated with ATS. In this article, I would like to present a template-based package that is designed to (partially) relieve a programmer from the heavy burden that is so often associated with programming in ATS.

The code presented in this article is essentially based on some library code of ATS available on-line.

Divide-and-Conquer

In problem-solving, divide-and-conquer (D&C) is a strategy that divides a given problem of certain size into a collection of subproblems of less size and then solves the subproblems (recursively) and then combines the obtained solutions to the subproblems to form a solution to the original given problem.

Formally, D&C can be given a template-based implemenation as follows:

//
implement
{}(*tmp*)
DC_solve(x0) = let
//
val
test =
DC_base_test<>(x0)
//
in (* in-of-let *)
//
if
(test)
then
DC_base_solve<>(x0)
else r0 where
{
  val xs = DC_divide<>(x0)
  val r0 = DC_conquer<>(x0, xs)
} (* end of [else] *)
//
end // end of [DC_solve]
//
Note that DC_solve is the main function for solving a problem. The following interface is assigned to DC_solve:
fun{} DC_solve : input -> output
where input and output are two abstract types for the input and output, respectively, that are associated with the problem to be solved. In the body of DC_solve, DC_base_test is called to test whether a given input can be classified as a base case; if it is, then DC_base_solve is called to return the output for the given input immediately; otherwise, DC_divide is called to divide the input into a list of inputs, which are then passed to DC_conquer defined as follows:

//
implement
{}(*tmp*)
DC_conquer
  (x0, xs) = r0 where
{
//
val rs =
list0_map<input><output>
( xs
, lam(x) => DC_solve<>(x)
) (* end of [val] *)
//
val r0 = DC_conquer_combine<>(x0, rs)
//
} (* end of [DC_conquer] *)
//
As can be expected, the function DC_conquer is called to process a given list of inputs and then form an output (for the original input) by combining (in some manner unspecified here) the obtained outputs corresponding to the list of inputs.

Example: Fibonacci Numbers

Let us use Fibonacci to refer to the function that maps natural numbers to Fibonacci numbers 0, 1, 1, 2, 3, 5, etc. A recursive implementation of Fibonacci is given as follows:

implement
Fibonacci(n) =
if n <= 1
  then (n)
  else Fibonacci(n-1)+Fibonacci(n-2)
// end of [if]
We can also implement Fibonacci as follows:
implement
Fibonacci(n) = DC_solve<>(n)
after giving the following (specific) implementations for various function templates introduced in the above template-based implementation of D&C:
//
implement
DC_base_test<>(n) =
  if n <= 1 then true else false
//
(* ****** ****** *)
//
implement
DC_base_solve<>(n) = n
//
(* ****** ****** *)
//
implement
DC_divide<>(n) =
  g0ofg1($list{int}(n-1, n-2))
//
(* ****** ****** *)
//
implement
DC_conquer_combine<>
  (_, rs) = r1 + r2 where
{
//
val-list0_cons(r1, rs) = rs
val-list0_cons(r2, rs) = rs
//
} (* end of [DC_conquer_combine] *)
//
Given the simplicity of the (first) recursive implementation of Fibonacci, one may not be able to immediately appreciate the (second) templated-based implementation of Fibonacci. Let me elaborate a bit on this point. Assume that we need to parallelize an implementation of Fibonacci. For the recursive implementation, we probably need to rewrite it substantially in order to parallelize it. For the template-based implementation, we can simply choose an already parallelized implementation of D&C (while having little need for modifying the implementation of Fibonacci). In particular, code that implements D&C is generic and can thus be employed repeatedly in settings where D&C is the underlying problem-solving strategy.

If we replace Fibonacci with a (much) more involved implementation of some algorithm (e.g., in the field of AI), then benefits from a template-based implementation can hardly be missed. What is particularly beneficial to a programmer is that he or she, with the template-based approach as is outlined above, can concentrate on the specifics of the problem being solved while largely, if not completely, skipping generic issues that are not directly pertinent to the problem. For instance, the programmer can focus on specific issues such as dividing inputs and combining outputs while relying on the chosen implementation of D&C to handle a generic issue like parallelization. In other words, the template-based approach can be seen as a concrete means that reduces complexity in problem-solving by employing the very principle of separation of concerns.

Assembling a Package for D&C

I hereby outline some key steps involved in assembling a package for D&C that can be published via npm. Some basic knowledge of npm is assumed in the following presentation.

mydepies.hats

In general, a package should contain a file of the name mydepies.hats for specifying (static) loading of other packages upon which the current package depends. The file mydepies.hats for the package being built is empty as there is no issue of package dependency.

mylibies.hats

In general, a package should contain a file of the name mylibies.hats, which serves as the entry point to the package. For instance, the content of mylibies.hats for the package being built is listed as follows:

(* ****** ****** *)
//
// HX-2017-02-22:
//
// Effective-ATS:
// Generic Divide-Conquer
//
(* ****** ****** *)
//
#staload
DivideConquer =
"./DATS/DivideConquer.dats"
//
(* ****** ****** *)

(* end of [mylibies.hats] *)
Code that makes use of this package (which is given the name effectivats-divideconquer) is expected to contain a line like the following one:
#include "$PATSHOMELOCS/effectivats-divideconquer/mylibies.hats"
which introduces a namespace referred to as DivideConquer and populates it with all sorts of bindings declared in DivideConquer.dats (for implementing the template-based D&C as is outlined above). Of course, it is allowed to introduce more than one namespaces at once.

package.json

For each npm-package, a file of the name package.json is needed for specifying various properties of the package. For instance, the content of package.json for the package being built is given as follows:

{
"name":
"effectivats-divideconquer"
,
"version": "1.0.1"
,
"description":
"A generic implementation of divide-and-conquer for use in the Effective-ATS series"
,
"main": "N/A"
,
"scripts": {}
,
"repository": {
  "url":
  "https://github.com/githwxi/ATS-Postiats/tree/master/doc/EXAMPLE/EFFECTIVATS/DivideConquer"
}
,
"keywords": [
  "EFFECTIVATS",
  "divide-and-conquer"
]
,
"dependencies": {
}
,
"author":
"Hongwei Xi "
,
"license": "MIT"
,
"note-for-myself": "The package is stored at ${PATSHOME}/doc/EXAMPLE/EFFECTIVATS/DivideConquer/."
}
If needed, please see documentation on npm for further information on package.json.

With a correctly formatted package.json, one can simply issue the following command-line (from the directory containing the package) to publish the package:

npm publish
Immediately after effectivats-divideconquer is published, it is ready for downloading.

Internal Package Testing

The code for testing a package from within is supposed to be stored in a directory of the name TEST. For instance, the file TEST/Fibonacci.dats contains code for testing the package effectivats-divideconquer. In this file, one can find the following line for statically loading into the namespace DivideConquer all sorts of the bindings declared inside the file DivideConquer.dats:

//
#include "./../mylibies.hats"
//
Note that a path starting with the dot symbol (.) means that the path is relative to the directory that contains the current file (in which the path appears).

External Package Testing

One can download the package effectivats-divideconquer by issuing the following command-line:

npm i effectivats-divideconquer
For updating it, one can simply do:
npm up effectivats-divideconquer
The code for testing the package from outside is supposed to use the following line (or one of its variants) to statically load in the package:
//
#include "$PATSHOMELOCS/effectivats-divideconquer/mylibies.hats"
//
where PATSHOMELOCS is an evironmental variable whose value is set to be a string representing colon-separated path names. For instance, following is a typical setup for using npm:
PATSHOMELOCS=./node_modules:./../node_modules:./../../node_modules
which reflects the way in which npm stores downloaded packages.

For further details, please find on-line some concrete examples on testing packages externally.

Compiling and Testing

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

PackIt/mylibies.hats
PackIt/Makefile_test.hats
PackIt/DATS/DivideConquer.dats
PackIt/TEST/Fibonacci.dats // for testing internally
Note that the file Makefile_test can be used for compiling and testing the code (via the make utility).


This article is written by Hongwei Xi.