search

ktakashi / sagittarius-scheme

A manual (beh...) clone from bitbucket to use hosted CI service which only support GitHub
https://bitbucket.org/ktakashi/sagittarius-scheme
Other
47 stars 4 forks source link

Problem with equal-hash? -- Segmentation fault: 11 #1

Closed christoff-buerger closed 8 years ago

christoff-buerger commented 8 years ago

I recently added support for Saggitarius Scheme to my project. My project is a portable R6RS library. Its test suite is passed by Racket, Larceny, Petite Chez Scheme, Iron Scheme and partially Guile. Sagittarius fails three test cases however. I am running Sagittarius 0.7 in Mac OS X (homebrew version).

I am not sure why Sagittarius fails, but judging from previous experience (cf. christoff-buerger/racr#37, christoff-buerger/racr#55, leppie/IronScheme#11), faulty equal? and equal-hash implementations for cyclic data structures are often the reason.

Short background: My RACR project is a metacompiler library based on reference attribute grammar controlled rewriting. One of the example languages is a Petri net interpreter supporting the composition of nets in execution. The composition is based on place fusion. Place fusion requires fixpoint semantics to find all places a place is fused with (transitive closure computation). I therefore use circular attributes to compute this reachability problem. Fixpoint semantics require a termination condition. In case of reachability, the computation should terminate when the set of reachable places does not change anymore. In that process I use equal? to compare circularity-caches. The content of these caches are R6RS records, that themselves encode circular data structures. Since equal? must be well-defined for circular data structures according to the R6RS, this is not a problem. Another example of the RACR metacompiler is a simple imperative programming language (SiPLE). The language supports static typing and type coercions. The coercions are performed using attributes to deduce if and where a type coercion is required and then apply rewrites introducing respective type casts. All analyses are automatically cached and re-evaluated, if, and only if, a rewrite influenced some information an analyse used. To cache analyses, R6RS equal? hashtables are used.

The actual test cases failed by Sagittarius When you checkout my project and navigate to examples/siple you can execute one example test case for SiPLE via ../../run-program.bash -s sagittarius -e run.scm -- examples/correct/closures.siple :false:. This yields the following error:

Segmentation fault: 11

Another test case that fails is at examples/composed-petrinets/examples and executed via ../../../run-program.bash -s sagittarius -l .. -e purchase-processing.scm:

Unhandled exception
  Condition components:
  1. petrinets-exception
  2. &message Cannot compose Petri nets; The composed net is not well-formed.
  3. &stack-trace

stack trace:
  [1] raise-continuable
  [2] run-tests
    src: (ap:exception: "Cannot compose Petri nets; The com
  [3] load

The thrown exception is a false-positive. The tested Petri net is well-formed and the composition performed by other R6RS Scheme systems. The reason for the error is, that the well-formed? attribute is not correctly computed; I think most likely because of an erroneous computation of the circular fused-places attribute caused by incorrect equal? or equal-hash implementations.

Note: The issue is also reported at christoff-buerger/racr#60.

ktakashi commented 8 years ago

Thank you for your report! I've confirmed both issues.

The first one seems a bug of equal? or eqv? of record. It tries to compare fields of 2 records, and if one of them has cyclic structure, then it goes into infinite loop and gets stack overflow.

I've also filed this issue on Bitbucket (which is the official repository of Sagittarius): https://bitbucket.org/ktakashi/sagittarius-scheme/issues/182/problem-with-equal-hash-segmentation-fault

ktakashi commented 8 years ago

There were 2 issues:

Since both R6RS and R7RS require not to compare record fields via eqv?, so I've removed it. The second one applies only on R6RS. R7RS allows implementators to let compare record fields. I've separated R6RS equal? and R7RS equal?. The first one follows R6RS requirements strictly, thus it doesn't inspect record fields. The latter one does compare record fields, and this is very convenient and some of the code (e.g. reference test case of SRFI-116) depend on this behaviour.

I've also checked that there's no SEGV nor error. The fix will be available on 0.7.4, scheduled in May. (NB: I'm not the one maintaining Homebrew so not sure when it'll be available on OS X)

Commit: https://bitbucket.org/ktakashi/sagittarius-scheme/commits/a40b2b1018da

christoff-buerger commented 8 years ago

Thanks a lot for fixing!

I will test it when 0.7.4 is released.