nucleic2: removed unused files & simplify Makefile
[nofib.git] / spectral / hartel / nucleic2 / README
1 UPDATE(2017.01)
2 ---------------
3
4 To simplify the setup of the test, we have removed some of the unnecessary code
5 (e.g., non-Haskell versions of the program). Please see:
6 https://phabricator.haskell.org/D3041
7
8 ORIGINAL README
9 ---------------
10
11 This is the README file for the "nucleic2" benchmark program.
12
13 The following files are contained in the tar file associated with
14 the nucleic2 program:
15
16    README        This text
17    nucleic2.c    C version of the program
18    nucleic2.scm  Scheme version of the program (for Gambit, MIT-Scheme, and SCM)
19    nucleic2.sml  ML version of the program (for SML/NJ)
20    nucleic2.m    Miranda version of the program
21    paper.tex     First draft of the paper describing the benchmark project
22    paper.bbl     Bibliographic data
23    paper.ps      Postscript version of the daft paper
24    haskell/{Nuc, RA, RC, RG, RU, Types}.hs
25                  Haskell version (for HBC, by Lennart Augustsson)
26
27 We will hopefully be able to add a few more versions of the program soon.
28
29 15/6/94: sml version added
30 16/6/94: haskell version added
31
32 The nucleic2 program is a benchmark program derived from a
33 "real-world" application that computes the three-dimensional structure
34 of a piece of nucleic acid molecule.  The program searches a discrete
35 space of shapes and returns the set of shapes that respect some
36 structural constraint.  The original program is described in:
37
38    M. Feeley, M. Turcotte, G. Lapalme, "Using Multilisp for Solving
39    Constraint Satisfaction Problems: an Application to Nucleic Acid 3D
40    Structure Determination" published in the journal "Lisp and Symbolic
41    Computation".
42
43    (This paper is available from ftp.merl.com:/pub/LASC/nucleic.tar.Z)
44
45 The purpose of the modified program (i.e. nucleic2) is to benchmark
46 different implementations of functional programming languages.  One
47 point of comparison is the speed of compilation and the speed of the
48 compiled program.  Another important point is how the program can be
49 modified and "tuned" to obtain maximal performance on each language
50 implementation available.  Finally, an interesting question is whether
51 laziness is or is not beneficial for this application.
52
53 The new program "nucleic2" differs in the following ways from the
54 original:
55
56 1) The original program only computed the number of solutions found
57 during the search.  However, it is the location of each atom in the
58 solutions that are of interest to a biologist because these solutions
59 typically need to be screened manually by visualizing them one after
60 another.  The program was thus modified to compute the location of
61 each atom in the structures that are found.  In order to minimize IO
62 overhead, a single value is printed: the distance from origin to the
63 farthest atom in any solution (this requires that the position of each
64 atom be computed).
65
66 2) The original program did not attempt to exploit laziness in any
67 way.  However, there is an opportunity for laziness in the computation
68 of the position of atoms.  To compute the position of an atom, it is
69 necessary to transform a 3D vector from one coordinate system to
70 another (this is done by multiplying a 3D vector by a 3 by 4
71 transformation matrix).  The reason for this is that the position of
72 an atom is expressed relatively to the nucleotide it is in.  Thus the
73 position of an atom is specified by two values: the 3D position of the
74 atom in the nucleotide, and the absolute position and orientation of
75 the nucleotide in space.  However, the position of atoms in structures
76 that are pruned by the search process are not needed (unless they are
77 needed to test a constraint).  There are thus two ways to express the
78 position computation of atoms:
79
80   "On demand": the position of the atom is computed each time it is needed
81   (either for testing a constraint or for computing the distance to
82   origin if it is in a solution).  This formulation may duplicate work.
83   Because the placement of a nucleotide is shared by all the structures
84   generated in the subtree that stems from that point in the search, there
85   can be as many recomputations of a position as there are nodes in the
86   search tree (which can number in the thousands to millions).
87
88   "At nucleotide placement": the location of the atom is computed as soon
89   as the nucleotide it is in is placed.  If this computation is done lazily,
90   this formulation avoids the duplication of work because the coordinate
91   transformation for atom is at most done once.
92
93 The original program used the "on demand" method.  To explore the
94 benefits of laziness, the program was modified so that it is easy to
95 obtain the alternative "at nucleotide placement" method (only a few
96 lines need to be commented and uncommented to switch from one method
97 to the other; search for the string "lazy" in the program).  The C,
98 Scheme, and Miranda versions of the program support the "at nucleotide
99 placement" method.  The Miranda version uses the implicit lazy
100 computation provided by the language.  The Scheme version uses the
101 explicit lazy computation constructs "delay" and "force" provided by
102 the language.  The C version obtains lazy computation by explicit
103 programming of delayed computation (done by adding a
104 "not_transformed_yet" flag to 3D vectors).