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.
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.
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.
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.
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.
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.
{
"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 publishImmediately after effectivats-divideconquer is published, it is ready for downloading.
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).
One can download the package effectivats-divideconquer by issuing the following command-line:
npm i effectivats-divideconquerFor updating it, one can simply do:
npm up effectivats-divideconquerThe 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_moduleswhich reflects the way in which npm stores downloaded packages.
For further details, please find on-line some concrete examples on testing packages externally.
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 internallyNote 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.