search

christoff-buerger / racr

Metacompiler library supporting incremental transformation based on reference attribute grammar controlled rewriting.
MIT License
30 stars 9 forks source link

GNU Guile fails test suite #37

Open christoff-buerger opened 9 years ago

christoff-buerger commented 9 years ago

GNU Guile fails some of the rewrite and Petri net tests (rewrite-basics, rewrite-lists, rewrite-refine-abstract, purchase-processing, runtime-structure-example-slide).

Further investigation for the reasons and fixes, if it is not an implementation error of GNU Guile, are required.

Note: Other R6RS Scheme systems pass these tests; most likely GNU Guile is bugged.

christoff-buerger commented 9 years ago

The equal? implementation of GNU Guile does not satisfy the R6RS standard. It has problems with cyclic entities. RACR ASTs are cyclic (each node knows its parent, the parent knows its children etc). This problem is particularly tricky, because nodes can be cached or used as keys for caching; since RACR uses equal-hashtables this may break Guile.

christoff-buerger commented 9 years ago

To fix the Petri net composition tests (purchase-processing and runtime-structure-example-slide) is more complicated (cf. ac0c706c643df40acf207cfb7587de51ac820e1b). It is postponed because the reason seems to be the erroneous equal? implementation of Guile. It looks like a Guile fix requires to switch to eq? hashtables instead of equal?-based hashtables for attribute caching.

Regarding the failed Petri net test cases, the circularity cache used for the evaluation of the fused-places attribute seems to fail because of the usage of equal?-based hashtables. A hint for this explanation is, that the Petri net test cases non-deterministically (i.e., sometimes) fail with a stack overflow, which indicates missing cache hits. The reason is not 100% clear though.

christoff-buerger commented 9 years ago

The issues of equal? in Guile are documented in Guile's reference manual, Section 7.6.1 Incompatibilities with the R6RS (http://www.gnu.org/software/guile/manual/html_node/R6RS-Incompatibilities.html#R6RS-Incompatibilities).

christoff-buerger commented 8 years ago

Since commit 8cb1b57feeef3709d90b8570531a0ce30cddb040 the composed Petri net examples are excluded from RACR's test suite for GNU Guile.

christoff-buerger commented 8 years ago

Regarding to issue #55, the problems of GNU Guile may also be due to its equal-hash implementation not working properly if cyclic entities are used as keys in hash-tables. Such keys are used to cache parameterised attributes whose arguments are AST nodes, which are by definition cyclic data structures (each node knows its parent, which in turn knows its children etc).

christoff-buerger commented 6 years ago

Status update

Currently the following tests are failing for GNU Guile:

The reason for GNU Guile to fail is the usage of circular record entities (AST nodes) as arguments for cached parameterised attributes; since GNU Guile's equal-hash is not cycle-save, this cases fail.

christoff-buerger commented 4 years ago

Since GNU Guile 3.0.2, the failing tests do not always fail with stack overflows anymore, but sometimes just do not terminate. The tests failing are still:

but now additional tests/ast-construction.scm fails (it tests racr-meta, not the stable racr AST construction).

Because of the now non-terminating behaviour for some of these tests, a need to exclude them for GNU Guile was needed. For RACR libraries, like the composed Petri nets, this already can be and is done in the library configuration. But for the simple source code file tests like tests/ast-construction.scm, a new exclusion feature has been added with commit a242621bb2ba09242af3e52c943a6c7e817745e3.

The rationale why GNU Guile fails some tests is still the same: GNU Guile does not support cycle safe equal?. It is somehow worse however, because the record type for AST nodes (define-record-type node) is declared to be opaque, which according to R6RS semantic implies that the content of an AST node must never be inspected via generic record accessors (cf. conclusions of issue #85). Such are however the only way the standard equal? can start to unfold AST structure for equivalence tests. This is forbidden! It is intentional, that an AST node is only equal to itself; a structural equivalence test must never be applied. In case of opaque records, equal? must fall back to a simple eq? test. GNU Guile therefore violates a whole set of R6RS semantic.