| Archived News
| ||||||||||||||||||||
2007-03 | ||||||||||||||||||||
29: |
I have eliminated my "corrections" to the Mercury
extras xml library (I had an outdated version of the library as outlined in the 2007-03-18 news post, so my corrections were redundant the the Mercury team's). At the same time, I have moved my XML enhancements into the utils library and promoted thedoug_graph module from alpha; it is now also included in utils. | |||||||||||||||||||
18: |
A new library and several improvements can be found in the shared repository:
| |||||||||||||||||||
2007-02 | ||||||||||||||||||||
14: |
| |||||||||||||||||||
02: |
We present a very tiny foreign interface to libtiff. The module
tiffany allows reading and writing simple RGBA TIFFs with two-dimensional arrays. As thematrix module matures, we will use that protocol for more comprehensive image filtering. This interface is presented with some samples and (currently) no documentation (other than code comments) as is available from our shared repository. Both libtiff and the matrix protocol must be available to run the samples.Update 2007-02-06: | |||||||||||||||||||
2007-01 | ||||||||||||||||||||
31: |
As the Mercury standard library does not have a matrix protocol, I am building a module that handles some basic matrix operations; this module and its test suites will be added to the
utils library when in serviceable condition. | |||||||||||||||||||
30: |
Thanks to the efforts of the Mercury research group at Melbourne, their Mercury compiler (
mmc) is now available for Macintosh computers with the Intel chipset. This is the alpha ROTD (2007-01-21) as opposed to the currently sanctioned 0.13.1 release, so some things are experimental in this version of the compiler. Email logicaltypes.com if you wish to have a binary distribution.
Our compiler,
ltq (that allows syntactic extensions with the op/3 directive, see the news archives at 2006-03-02), may need some work as the Mercury research team has changed the ops module. This, of course, also means that systems that depend on these improvements, such as the test-building framework qcpt (see news archive post 2006-05-12), must also be retested. We will post an update when qld is again tested and working. | |||||||||||||||||||
2006-07 | ||||||||||||||||||||
17: |
The various data structures provided in the ROTD extras/ distribution that handles
solver types (particularly the various any modes) do not compile because of purity issues; also, since their release, the coding style has changed for module qualification. The fixes to get these types compiled are here. For the Mercury team's review are the diffs to fold back into the distribution. | |||||||||||||||||||
2006-05 | ||||||||||||||||||||
13: |
We present a complete rewrite of Mercury's QuickCheck implementation: qcheck2 (the sample unit test module (
peano_unit_tests) requires the peanomodule in order to run). The essence of testing à la qcheck -- type discernment to obtain (random) test values with a test specification language -- remains unchanged. The new features of this new version enhance the system with:
The documentation for
qcheck (upon which qcheck2 is built) is a model for any system to follow; so, documentation, to include a system description and transition guide, for qcheck2 is under development.Update 2006-05-20: Update 2006-05-21: | |||||||||||||||||||
12: | ltq (Logical Types Quicksilver compiler) now comes with qcpt (QuickCheck Predicate Types), a system that discerns the interface predicates and functions of a system (to facilitate comprehensive unit testing). Perhaps even more important is the inclusion of a README that doubles as a HOWTO and INSTALL document. | |||||||||||||||||||
11: |
Completed the document describing an implementation of mutable syntax for Mercury. This article in available in the literature section (see above).
| |||||||||||||||||||
2006-04 | ||||||||||||||||||||
30: |
The
graph module takes a rather non-directed approach to locating a path from Node1 to NodeN. This is fine if the path has no associated cost, but if one is looking for the best path (where a path has an associated cost), this laissez-faire approach becomes problematic.
As I often need a efficient path in a graph, I have added
best_path/5 and other supporting predicates that cannot be implemented well operationally given the protocol of module graph and submitted these changes to the Mercury team for review. While they consider these changes, I provide the implementation here as module doug_graph, with an associated example. Locating the best path in the given example using the naive pathimplementation took over 20 seconds; the reimplementation here completes the computations in less than a second. | |||||||||||||||||||
27: |
The following Mercury compiler distributions are available from here on request:
These distributions include the
extras/, the samples/ (in extras/) and the HTML documentation (in doc/). | |||||||||||||||||||
2006-03 | ||||||||||||||||||||
| ||||||||||||||||||||
2006-02 | ||||||||||||||||||||
| ||||||||||||||||||||
2006-01 | ||||||||||||||||||||
| ||||||||||||||||||||
2005-12 | ||||||||||||||||||||
| ||||||||||||||||||||
Showing posts with label LogicalTypes. Show all posts
Showing posts with label LogicalTypes. Show all posts
Tuesday, December 18, 2012
Logical Types, LLC, Archived News
Logical Types Libraries
Libraries, etc. | ||||||||||||||||||||||||||||
Logical types has the following libraries, systems, and sample code. All provided with the usual caveats (they are not guaranteed to work, and Logical Types is not liable for you downloading and using this code):
| ||||||||||||||||||||||||||||
| Libraries | ||||||||||||||||||||||||||||
utils |
a set of utilities useful for building production systems
contains modules: | |||||||||||||||||||||||||||
qcheck2 |
A testing/verification framework for Mercury programs
see
| |||||||||||||||||||||||||||
| Systems | ||||||||||||||||||||||||||||
ltq |
Extends Mercury with
op/3 declarations, allowing syntax modificationsee installation instructions | |||||||||||||||||||||||||||
| Fixes/Patches | ||||||||||||||||||||||||||||
anys |
A set of fixes to the utilities provided in the Mercury
extras distribution supporting operations with the any mode
see
| |||||||||||||||||||||||||||
| Alpha: You Have Been Warned! | ||||||||||||||||||||||||||||
matrix |
Work in progress to add a viable matrix protocol; will be rolled into the
utils library. | |||||||||||||||||||||||||||
tiffany |
A very small, thread-un-safe, foreign interface to libtiff; also requires
matrix (which it already bundles). | |||||||||||||||||||||||||||
Installation Instructions for QuickSilver
| Installation Instructions for Quicksilver | ||||
| PowerPC/Apple architecture | ||||
| ||||
Creating syntax with op/3 can become complicated when several operators interact to create a term. I've provided a module that prints the canonical representation of a parsed term (write_canonical.m) and a testing module (test_op.m) that allows prototyping of operator declarations and allows submitting terms under that syntax. The whole test system may be built in the usual way:$ mmake test_op.depend $ mmake test_op |
Logical Types Company Mission Statement
| Rule-based Systems |
Rule-based systems process data according to sets of constraints established by the user. The results of these systems is a collection of rule findings that can be used to construct the final product or to assist the user in rendering an informed decision.
The above description may seem all-too-general, as that describes the what most programs do. This is indeed correct: rule-based programming is sufficiently powerful enough to describe any computable system. In fact, the rule-based approach is now being viewed by the mainstream as the preferred method for workflow analysis, process, resource scheduling, service-based systems, etc. Nearly every software system has a set of rules, explicit or implied, to which it adheres. The rule-based programming style model these rule constructs directly and facilitate their manipulation as the system grows and changes.
| ||
| Deductive Logic |
The traditional approach to building logic systems is to construct a set of clauses where the head of the clause matches a condition and the rest of the clause verifies the match through a set of goals for that match. These clauses are known as rules and a set of rules is a predicate, and this predicate can be used, in turn, as a goal in a new rule. Deductive logic matches problem specifications very closely and is a very effective way to convert a set of requirements into a production system. Some examples of types of problems that are easily modelled in deductive logic are expert systems, planning systems and scheduling systems.
Deductive systems are used when the rules are clear, when the user requires certain outcomes, and are very good at "explaining" what the rule findings are and how they were arrived at.
| ||
| Inductive Logic |
The opposite approach to a deductive system is an inductive one. Whereas in an deductive system, the user has very exacting control over the process and outcome, in an inductive system, the rules are obtained by deriving the relations between input data and their outcomes, with very little guidance, if any, from the builder of the system. Traditional inductive systems required very clean data and had little tolerance for deviation -- a slight perturbation in the data set could cause the system to fall into an undefined state. Modern inductive systems have taken a different approach: reaping the benefits of recent advances in probability and statistics, these systems (such as Bayesian systems and neural networks) are highly redundant and adaptive. These new systems consistently perform well: they have excellent success narrowing to a classification from apparently unrelated attributes, and they have a high rate of stability, being very fault-tolerant, even in the presence of very noisy data. It is also trivial to convert a statically trained inductive system to one that learns continuously from new inputs and outcomes.
Inductive systems are used when users cannot explain how they arrive at decisions (attributing the outcomes to a "feel" for the situation), and where gradual trends result in eventual changes to outcomes. These systems excel at making the correct decision with a very high degree of confidence, but are poor at explaining what prompted the decision.
| ||
| Our Approach |
Logical Types, LLC uses both deductive and inductive logic to build systems as the needs of the customer demand:
| ||
Testing with qcheck, version 2.0
qcheck, version 2.0
Introduction
QuickCheck is a system developed by John Hughes and Koen Claessen. Its premise is that comprehesive testing can be obtained by combining a testing specification language and test data automation ("random testing"). It has been ported to several languages from its native Haskell: the Mercury programming language provides a QuickCheck facility in their "extras" distribution, called
qcheck.
As it stands, the original
qcheck (herein after referred to as Q1) is an excellent piece of work, fully capable of testing entire systems. It can decipher how to generate example data from user-defined types. It also provides examples for various general and specific situations where the user may wish to exercise control over the ranges or frequencies of the data generated. What, then, would need to be changed?
Not much, it turns out. The fundamental aspects of the system -- comprehesive unit testing fed by randomly-generated values and directed by a test specification remain intact, but there are several features to comprehensive testing that can be added to improve this system.
Q1 is good at verifying that one particular predicate behaves as it should, but it gives no indication that all the (interface) predicates of a system have been tested. Further, the user has some control over the detail reported for each test, but, for a user wishing a summary report, even the smallest report allowed is too much detail: adding a facility that give the user complete control over reportage becomes necessary for larger systems. Finally, Q1 has an excellent facility to generate random values for user-defined types, but for primitive types (such as char, int, and float), the approach is a bit arcane (only mentioned in one of the last examples) and lossy -- giving the user control over the random number generator itself, and integrating that part of the system with the goal of ease of use will carry forward the automation of user-defined typed values as well as simplify controlling ranges of generated primitive values.
These improvements were the aim of this new version: keep the essence of previous version while adding these new layers to help the tester verify much larger systems. The first two aims outlined above, that of comprehension and detail, are addressed by the new reporting facility that exists both outside
qcheck2 proper and is also integrated into its state. The third aim, more and simpler control over randomly-generated values, incorporate changes that now allow the user to define their own random number generator (or to use the very excellent one supplied) and also to change the generator's behavior in the midst of testing. We will address each aim, and their implementations, in the following sections.Aims
Aim 1: Comprehension
One question that testing frameworks, such as QuickCheck, must eventually address, particularly for larger systems, is the one of completeness. Or, "has the entire functionality of the system been tested?" Under the first implementation this is a difficult question to answer, and the root of this problem is a rather trivial one to fix: the second input argument to
qcheck/[4,7,8] is a string that has the purpose of describing the test to be performed. Typing this argument as a string is rather limitting: although the (human) user can seen the purpose from the description, the problem is that encoding the test description as a string does not facilitate reasoning about test results mechanically, which makes it difficult for the system to report on what was and, importantly, was not, covered in the testing.A new accumulated state variable
The fix to this problem is therefore simple: generalize the test description argument to any (univeral) type. This way other systems may, for example, generate a model of the system being tested and then, after the tests are completed, a method of tabulating and reporting the results. The internals of
Q1 change in two ways: first, the description type signature is relaxed, and second, as reportage is spread across several calls to qcheck/[4,7,8], we will defer the commitment of outputting results until the user so determines. In this case, we convert the state variable from io.state (which commits the output) to a specific accumulator (that simply collects it)::- pred qcheck(T, Desc, int, list(list(frequency)), general_frequencies, list(user_gen_type(RNG)), qstate(RNG, Desc), qstate(RNG, Desc)) <= (testable(T), random_number_generator(RNG)). :- mode qcheck(in, in, in, in, in, list_skel_in(user_gen_inst(RNG)), in, out) is det.where:
T the type (pred/func) to test Desc a generic type describing the test intnumber of tests list(list(frequency))list of specific frequencies (as per Q1)general_frequencieslist of general frequencies for testing (described later) list(user_gen_type(RNG))user-defined types for value generation, as per Q1, specialized on the random number generatorqstate(RNG, Desc)The state variable collecting test results and keeping the random number generator au courant The typeclasstestable(T)is as perQ1; and the random number generator typeclass (random_number_generator(RNG)) will be discussed under the value generator aim.For the new types forqcheck2::- type general_frequencies == assoc_list(type_desc, list(frequency)). :- type qstate(RNG, Description) ---> qstate(generator(RNG), map(Description, test_results)). :- type test_results ---> test_results(int, int, int, bag(univ)) ; falsifiable(univ).
The above
qstate type shows that the test description is mapped to the test_results type, as qcheck/[4,7,8] is called for each test, it accumulates the test results indexed by the (generic) description.The Program Modelling Tool
As Description can be of any type, we can now allow the user to pass in a simple description
string, as in Q1, or, alternatively, we can enhance the description with something that we can use as a declarative index. In Prolog, we could use the index of the module-qualified name of the predicate. Mercury is not as dynamic a system to allow any number of module/predicate/function values for Description,1 so we will employ a preprocessing system to identify and alias all interface predicate/function types to a uniform (enumerated) type. One such system is qcpt available from logicaltypes.com packaged into the ltq system. From an input set of files, qcpt generates the following types:
:- program_module
--->
Example
Say we wish to test a single module, for example the
peano module. By running ...$ qcpt peano.m
... the file
qcheck2.tests_digests_types.m is generated with the above type declarations and the following specific realizations:
% ...
:- type program_module
---> peano.
% ...
:- type public_predicate
---> increment
; peano
; to_peano.
:- implementation.
all_program_modules = [
peano
].
all_public_predicates = [
public(peano, increment/2),
public(peano, peano/2),
public(peano, to_peano/2)
].
A new reporting facility
Given that we now have collected all the public (or interface) predicates and functions of a system, it is now also possible to determine the completeness of the testing, in that all of those predicates were tested. It simply now falls to a system to collect the results of testing and report the results. The user may attack this task any number of ways, but we also provide one implementation in module
qcheck2.tests_digest_reports. The predicate
show_module_tests_summary(Results, !IO)
does all this work by comparing the accumulated test Results (typed as an
assoc_list(test_desc, test_results), where test_desc is provided by moduleqcheck2.tests_digest_types (generated from the tested module using qcpt), and the assoc_list is the accumulated result of calling a set of qcheck/[4,7,8] goals).
The
show_module_tests_summary/3 predicate reports the total number of tests (and those that passed) within each module and reports the number of predicates that succeeded all unit testing. This predicate also reports, by name and arity, the predicates not tested by the framework.Example
The following report ...
$ ./peano_unit_tests_missing_to_peano
Qcheck2 tested the following modules:
*** 6/6 tests passed on 2/3 predicates in peano
(did not test to_peano/2)
... shows that my modifications to module
peano_unit_tests (I commented out the to_peano/2 tests) resulted in all tests passing, but the test suite did not provide full coverage of the peano module's functionality.Traditional Reportage
Module
qcheck2.reports provides two ways to report results as Q1 did:show_test_results_sets(Results, !IO) show_test_results(Description, test_results, !IO)
The predicate
show_test_results_sets/3 simply iterates over Results, calling show_test_results/4 at each iteration. The predicate show_test_results/4 reports the results from qcheck/[4,7,8] in the style of Q1.Example
Here are some of the results reported from running
peano_unit_tests_with_failing_test with a call to show_test_results_sets/3:
1) 2) Test description : public(peano, increment / 2) - "Checks increment/2\'s compare" Number of test cases that succeeded : 19 Number of trivial tests : 0 Number of tests cases which failed the pre-condition : 81 Distributions of selected arguments : 13 {0, 1} 5 {1, 2} 1 {2, 3}3)
The above examples demonstrate 1) a sample test report where all the tests succeeded (with no reportage on the test values used), 2) a sample where some test values were unusable (with reportage), and 3) a sample where the predicate and test values (by intention) failed the test. These tests are of the same form as those of
Q1. The major difference is that test tests are reported separately from the qcheck/[4,7,8] call. This separation allows delayed (even permanently delayed) reporting of results.Aim 2: Generation
Q1 offers a dizzying array of options when giving the user control over what test values are generated and how they are generated, that is, if these values are to be generated from user-defined, or complex (not builtin), types. It also offers a generator of such power that it is dubbed: "The Mother of all Random Number Generators" by its creator. Impressive as the above offerings are (and they are, in fact, impressive) there are two glaring wants: first, one is required to use the supplied generator -- users are not permitted alternate generators for their own testing, and this becomes an issue when, for example, "pure" randomness (such as the values provided by random.org), or cryptological-strength randomness is a requirement of the tested system, and, second, restricting the ranges of primitive builtins (or other "unbound" enumerated types (such as integer)) is not directly feasible (albeit possibly with some esoteric indirection). We address each of these wants in the new system in this document by turns.Want 1: User-supplied random number generators
Q1 was built to hide its inner workings. This software principle is considered to be good practice, but, since one of the inner workings is random number generation to generate test values, this good practice obstructs the ability to replace the random number generator when so required. The new architecture in qcheck2 exposes the random number generator in the state variable, allowing its replacement by alternate equivalent types. The change also comes with a supplied state initialization predicate that provides the default random number generator.
The design of the system requires the user to wrap their random number generator (hereinafter referred to as the RNG) in type described in the next section, and it must conform to the following typeclass:
:- typeclass random_number_generator(RNG) where [ % gives a random float on the range [0, 1) pred rnd(float::out, RNG::in, RNG::out) is det, pred reseed(int::in, RNG::unused, RNG::out) is det ].where:
rnd/3supplies a float between 0.0 and 1.0 and updates the state of the RNG; and reseed/3reinitializes the RNG with the seed supplied as the first argument.
Want 2: User-controllable numeric ranges
It is very easy for the user of
Q1 to specify a discriminated-union type and have the system generate test examples. The problem is for builtin types: Q1 does not consider bounds when generating floats, ints and, surprisingly, chars.2 One could argue that by choosing unbound types, the user must be prepared to accept any value those types describe, and indeed this is true. Where this argument falls apart is when the user wishes to test predicates within their nominal ranges. Certainly the test framework should generate test data that tests beyond the ranges, but when every test case offered is extrinsic, nothing is gained by submitting that predicate to random testing. In short, the user must be allowed direct control over ranges of test values of builtin types when the situation warrants.:- type generator(RNG) ---> generator(int_range, float_range, character_type, RNG).where:
int_rangeis either range(int, int)orunbound
Endnotes
| 1 |
Well, this statement is not true in all cases -- if all the tested predicates had the same type and modality then one may simply use the name of the predicate as the Description. See, for example, modules
foo and foo_unit_tests included in the distribution. The material point here is that although it is possible to use the name of a predicate as the Description it is not realistic given that most systems use predicates with different types, arities, and modalities. |
| 2 | Q1 treats strings as list(int), where each element is a char-equivalent int, which can be positive, negative or, as is most often the case, of very large magnitude. |
(article posted circa 2006)
Mutable Syntax in the Mercury Programming Language
Introduction
The Mercury programming language is a compiled, strict, pure, type-safe logical and functional programming language. Its programming methodology is based on predicate logic, with syntax and semantics in line with that of Prolog. Along with logic, it has a fully integrated Hindley-Milner type system with lambda-terms, very much in the style of the Haskell programming language.
The smooth integration of Prolog with Haskell sounds like a marriage of programming paradigms to release the programmer into Coding Nirvana, as it were. This is how it is for most cases, as the language has a consistent design philosophy backed up by well-researched principles and explained by copious and clear documentation with numerous practical examples. What remains are niche constructs, that is: constructs that may be helpful for specific problems, but are not strictly necessary, nor generally applicable.
One such niche construct, one that I turn to quite often when programming in Prolog, is the
op/3 declaration, or, the ability to introduce new syntax into the language so that I may model the problem more naturally. This document covers extending the language to include the op/3 declaration in its full breath of functionality.Alternatives, and Raison d'être
The approach we take is the modify the compiler so that it accepts the
op/3 directive in a module and thereafter, within only that module, parse the operator declared with the specification and priority given in the directive. This may seem like a drastic measure, so we must consider the alternatives before choosing this course of action. There are basically four viable, albeit inferior, alternatives:- The Mercury programming language provides the grave syntactic construct which converts the standard prefixed call to an infix one:
fn(X, Y)becomesX `fn` YSee, for example, thepprintmodule, as it used to make extensive use of this style (until it recently deprecated this approach to use one of the builtin operators, instead). Just as the Mercury language developers have discovered, this approach has at least two drawbacks:- these infix "operators" are clearly marked as second-class citizens, unnecessarily lengthening what is supposed to be a concise representation;1 and,
- only binary infix operators are allowed under this syntax; I often find it useful to type values using a postfix type.
- One could construct a specialized instance of the
op_tabletypeclass from theopsmodule and thereafter useread_term_with_op_table/4from theterm_iomodule to parse strings at runtime. See samples/calculator2.m provided with the distribution for an example program that demonstrates this approach.This approach also has its own set of associated problems:- Constructing one's own
op_tableis excessive when using only a few operators and tedious when introducing many operators. This manual process steals precious time away from program development that addresses the problem, itself. - Until now, there was no "cookbook" approach addressing the problem of how to create a mutable syntax. The
opsmodule and the sample calculator program are well-documented and provide good examples of how to implement static syntax, but provide no guidance for constructing dynamic, mutable, syntax. For this, one had to design such a framework from first principles.2 - An user-defined
op_tableinstance may only be used at runtime. The Mercury compiler, as implemented, does not allow such tables during module compilation.
- Constructing one's own
- Third, use one of the available scanners (such as samples/lex/) or parser generators (such as samples/moose/) to create a language syntax-aware preprocessor that substitutes operators and their arguments with the well-formed term replacement. Problems:
- This is highly redundant and fruitless exercise, as the compiler has its own parse phase that does the same work, and with the language itself in flux (as is the case for any living language) changes to the syntax quickly render a system created by these means obsolete. Parser generators for other programming languages provide complete grammars for every version of the host programming language, Mercury has no parser generator with such grammars, so this task is left to a user of these kinds of systems.
- Furthermore, although the domain-specific languages for these tools closely follow the Mercury programming language to do their work, they do have their own languages that require time and effort to master. When presented with powerful parsing facilities built right into logic programming languages (I'm referring specifically to Definite Clause Grammars (DCGs)), one must weigh the costs of learning these languages before embarking on such an endeavor.
- Worst for last: as with C/C++, create a specific preprocessor that parses the source file, converting annotated operators to equivalent Mercury terms by following the preprocessing directives. This approach requires so much work (the C preprocesser is a compiler-sized program) and has so many known pitfalls (such as replacing elements inappropriately (in a quoted string, for example) and causing an unacceptable disjunction between the generated executable and the original source base (confusing debugging and error reporting efforts), that it should not receive serious consideration;3 it does not in this document, at any rate.
By embedding the
op/3 syntax into the compiler, the changes we make are hygenic in that they are part of the language syntax, not external and blindly unaware of it, as is the case with with C preprocessor and immediate so that they may be used at compile time in the module in which they are declared. This implementation also limits the lexical scope of the operatorwithin the module in which it is declared,4 preventing these declarations from corrupting modules that eventually use modules with specialized syntax.
The desired state is to integrate the
op/3 declaration fully into the the language, so that, e.g., facts may be stated in their vernacular and still be compiled into executable content in the Mercury idiom, as in this real-world example:
for the open weekly timecard ending date(2006, 1, 6):
employee cgi_emp_001 billed [
3 hours on sunday - date(2006, 1, 1),
16.5 hours on monday - date(2006, 1, 2),
5 hours on tuesday - date(2006, 1, 3),
5 hours on wednesday - date(2006, 1, 4)
] against contract lt_2005_001.
Far from being a contrived pedagogical example,5 the above illustrates the various typing uses of
op/3 defined syntax, both prefix ('employee cgi_emp_001') and postfix ('3 hours'). The above fact is certainly "only" a data term (in fact, as well as being a data term, the above fact also contains op/3-based data terms), but fully actualized operators exist as well; the Prolog syntax module is rife with such examples. These uses of op/3-declared syntax (describing entity relationships clearly and as activated syntax) are in no way limited to the rather straightforward problems of accounting, but are also used in production expert systems handling over 1,000,000 transactions per day; the use of these extensions are tied directly to rule findings satisfying customer requirements.
In short,
op/3-declared syntax is used extensively in production systems built using Prolog serving real-world requirements under heavy demands. With the preexisting extensions for purity, typing, and functional programming, imagine the utility and expressivity that could be obtained with Mercury so extended!Implementation
Now that we have justification for modifying the compiler, nothing remains but to get to it. Fortunately, the Mercury compiler, after some study, yields a straightforward implementation approach.
First things first: the
ops module uses a discriminator (the type category) to choose among different uses for an operator (e.g. unary '-' verses binary '-'). This discriminator is internal, and, as we need the same functionality when defining new operators, so we externalize that type in library/ops.m by moving the type declaration from the implementation section to the interface.
Given this type, we now decorate predefined (inflexible) op table that will permit additional syntax declarations. For this, we need to index the operator and its
category to the syntax declaration, and then make this new type an op_table (typeclass) instance ... we add this type to the interface of compiler/prog_io_util.m::- type op_map == map(pair(string, ops.category), op_info). :- type mercury_op_map ---> mercury_op_map(ops.table, op_map). :- instance ops.op_table(mercury_op_map).
To further support the new type, we need information against which we index, and we need supporting predicates to construct the information for the parser when encountering the operator (the declarations for this also go into the interface of compiler/prog_io_util.m):
:- type op_info ---> op_info(ops.specifier, ops.priority). :- func op_specifier_from_string(string) = ops.specifier. :- func op_category_from_specifier(ops.specifier) = ops.category.
The
op_specifier_from_string function simply takes an input string, e.g. "xfx", and coverts it to the equivalent specifier representation, e.g. the functor xfx. Theop_category_from_specifier function follows the (implied) convention of the ops module, which is all prefix specifier types (including binary prefix) are the before categoryand all other specifier types (one of several different infix and postfix possibilities) are the after category type. The complete set of changes are enumerated explicitly in the email on the implementation.
After we augment the functional of the
ops module, we need to integrate this into the compiler's parser module (which is actually called prog_io). The efficacious point is where the parser works at the module level,6 this occurs, after some initialization in read_module/11, in read_all_items/7. We initialize the op map here (with a call to init_mercury_op_map), and then pass along that nascent syntax map to the calls that parse the items in the module (by modifying the signatures of read_first_item/9 and the recursive callsread_items_loop_2/11 and read_items_loop/10).
So, for example,
read_items_loop/9 becomes:
read_items_loop(ModuleName, SourceFileName, !Msgs, !Items, !Error, Syn0, !IO)
... where Syn0 is the new syntax map. This map is initialized in the new
read_all_items/7 before calling read_items_loop/10 with the goal:
init_mercury_op_map(init_mercury_op_table, Syntax)
The magic occurs in module
parser's read_term_with_op_table/5 (called via read_item/7) which normally scans and parses the items in the module. When it encounters anop/3 declaration, however, it eventually resolves to the process_decl/8 back in the prog_io module, which reads the declaration and then adds the syntax declaration to the op map, enhancing the syntax for the current module.
When
read_all_items/7 completes its iteration on a module's items, it exits, discarding the op_map instance and any syntax it accumulated from op/3 declarations in that module, returning the compiler to the base, Mercury-defined, syntax. So that the "next" module starts fresh without syntax from other modules polluting the compilation.Reconsideration
"Worse is Better"7
After some discussion on the Mercury maillist, it was resolved that dynamic syntactic extensions should be external to the compiler. So, Logical Types has developed separate compiliation system that converts modules with syntactic enhancements to plain-jane Mercury equivalents. For modules with no syntactic enhancements, `
ltq' is equivalent to `mmc --make --infer-all'. For modules with op/3 declarations in the implementation, `ltq' first parses the module and writes out all terms canonically. After this translation, the system compiles the modules into the resulting executable or library.Operation
This system reduces rather nicely by using facilities provided by the Mercury compiler, and another declarative system: .ms) in the file
make. `mmc -M <file>' discovers file's dependencies and stores these in a makefile variable $(<file>.dv Given this, ltq simply builds a makefile with the enumerated dependencies and then calls the system that manages the dynamic syntax, which then writes out syntactically-enhanced modules in their canonical form (called `dopp'). Both ltq and dopp are available, along with samples as dynamic_ops.tgz.Conclusion
This study came from my experience with the ease of use of mallable syntax in Prolog and comments in the Mercury sources about the need to add
op/3 declarations as well as at least two aborted implementation attempts to do so. In the ensuing process, where I did implement this solution, quite a discussion emerged on the maillist on the estetic of allowing the user to introduce or to change syntax, and how to go about doing it properly. This implementation is one approach, and is offered to assist those who wish to add syntactic extensions to their Mercury systems.Endnotes
| 1 |
The normal infix operators do not have this grave branding, and for good reason. Imagine writing algebraic statements, such as the following:
while shackled to the grave syntax:
Note the extra parentheses -- these are now necessary, as the grave syntax does not communicate operator precedence. Also note that the single-character operators are now three times their original size. Given the above, it's tempting to avoid infix syntax altogether...
...but I have no desire to write out the parsed internal representation by hand (it may look like Lisp, circa 1965, because the syntax of most Lisps (with one notable exception) is also its parsed internal representation), so the Mercury prefix code is therefore presented:
There! Isn't the canonical tree syntax so much better than the cons syntax? Drek!
|
| 2 |
This is not all that bad, given the documentation and the calculator2.m sample. In calc4.m we provide a straightforward example using the
map type. |
| 3 |
This pronouncement in no way prevented this author from submitting such a proposal to the Mercury team. Ah, the blessed ignorance of youth! All was not in vain, however: every misstep hides the seeds of greatness: one of the responses showed that samples/expand_term.m (the responder was the author of that module, in fact) provides the functionality of Prolog's
term_expansion/2 predicate, which is an essential prerequesite for implementing Aspect-Oriented Programming (AOP) in predicate-logic based languages (specifically Prolog). How aspects are implemented in Mercury shall be a topic for another paper. |
| 4 |
In ISO Prolog
op/3 declarations have global extent. |
| 5 |
:- op(300, xfx, plays). :- op(200, xfy, and). Term1 = jimmy plays football and squash. Term2 = susan plays tennis and basketball and volleyball.
...but then the textbook quickly redeems itself -- it is still my preferred Prolog textbook -- with a meatier problem, which I adapt for your enjoyment:
ruth was the executive director at wncog. sally was the executive administrative_assistant at wncog. diane was the director of the human_resources department at wncog. juan was the administrative_assistant of the human_resources department at wncog. sunny was the director of the finance department at wncog. stuart was the director of the operations department at wncog. joe was the system_administrator of the operations department at wncog. ?- Who was the director of the What department at wncog. Who = diane, What = human_resources ; Who = sunny, What = finance ; Who = stuart, What = operations ; no
I leave the
op/3 declarations as a coding challenge to the enterprising reader. |
| 6 |
Prolog's
op/3 declarations have global extent, but I consider this a mistake in the presence of a module system -- op/3 should only affect the module in which is it declared. |
| 7 |
"Worse Is Better" the catchy title of one of the most fameous apologies (after Socrates', of course), is available from several sources: http://www.jwz.org/doc/worse-is-better.html is one such.
|
Works Consulted
| [Bratko2001] | Prolog Programming for Artificial Intelligence, 3rd ed., Ivan Bratko, Addison-Wesley, Reading, Massachusetts, 2001. |
(article originally posted January 3, 2006)
Subscribe to:
Posts (Atom)