[m-dev.] proof-of-concept code for choosing a grade
zoltan.somogyi at runbox.com
Sat Dec 5 13:39:41 AEDT 2015
Around oct 22-26 we discussed my proposal for a new approach
to specifying grades. We agreed that it would need to be accessible
not just in the Mercury compiler, but also in shell scripts.
While writing a constraint solver as a shell script is a VERY unappealing
prospect, writing it in standard C allows it to be called from shell
scripts, even before we have configured Mercury. So the attached
code is in C. While this code is now a standalone program, my intention
is that it should eventually divided into two or more separate .c files.
One .c file would contain the actual constraint solver, but would do
no I/O. Other .c files would act as wrappers: they would get the
list of desired features and the results of autoconfiguration tests
(such as whether we can use GCC registers), either from a file or
from the command line, give this info to the solver, and output the
results. There may be more than one of these, because you may
want more than one input format and/or output format. And
of course we could wrap the solver with Mercury code as well;
such a wrapper should be able to replace (most of) the current
This code is VERY preliminary. It implements only four solver
variables instead of the couple of dozen we discussed, and
only a few constraints. It takes input and generate output
in a very simple form, as a set of solver var name = value
pairs, which is NOT intended to be final. It is designed
to be as simple as possible, not to run as fast as possible,
but given the small problem size, I don't expect runtime
to be a problem anyway.
I am mostly seeking feedback on the overall design approach.
- The decision to do it in C.
- The representation of constraints. A conceptual constraint
such as "debugging requires low level code" is expressed
as two low-level constraints in cg.c: DBG=debug is allowed
only if CL=lo, and CL=hi is allowed only if DBG=none.
Each of the low level constraints expresses a requirement
on a given solver variable s1 having a given value s1a:
it requires that some other solver variable s2 have value
s2a or s2b or ... If s1=s1a imposes requirements on
more than other solver variable, those requirements
need to be implemented as more than one low-level
constraint. These low level constraints act as one
directional propagators: if s2 cannot have ANY of
the values listed (s2a, s2b etc), then s1 cannot be s1a.
- When we rule out a value for a solver variable, we record
the id of the rule that did it. This SHOULD allow us,
eventually, to give detailed reasons why e.g. asking for
DBG=debug and TARGET=java at the same time won't work.
(The code does not yet handle inconsistent constraints.)
- The solving process consists of alternating propagation
and labeling steps, but we don't backtrack over labeling
steps; we commit to them. This works in this small
constraint set; I am not sure whether it will work on
our full constraint set.
- The labeling step works by choosing a value for the
lowest numbered solver variable, and the value it chooses
is the lowest numbered value that hasn't been ruled
out yet. Therefore order matters for both solver vars
and their values.
- C is typeless, but I tried to use a naming scheme that
makes putting e.g. an integer representing a solver var id
into a slot that expects e.g. an integer representing a value
stand out. I also added a sanity check.
I await your comments. I want us to get to a consensus
on the overall approach before I work on finishing the solver
(much less writing the wrappers), and before we discuss
such details as the names of the options that ask for
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 15252 bytes
Desc: not available
More information about the developers