packages feed

cek-mercury (empty) → 0.1.0.2

raw patch · 7 files changed

+968/−0 lines, 7 filesdep +basedep +cek-coredep +cek-mercury

Dependencies added: base, cek-core, cek-mercury, cek-pykinos, ghc-prim, hspec, primitive, pykinos-core

Files

+ CHANGELOG.md view
@@ -0,0 +1,23 @@+# Changelog for `cek-mercury`++All notable changes to this project will be documented in this file.++The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),+and this project adheres to the [Haskell Package Versioning Policy (PVP)](https://pvp.haskell.org/).++## [0.1.0.2] - 2026-11-19++### Changed+- Bump package version to 0.1.0.2 to synchronize forge releases, CI, and Hackage upload artifacts.+- Dual-license package under EUPL-1.2 OR Apache-2.0.+- Elaborate documentation corpus to Cellarius standards.++## [0.1.0.0] - 2026-11-18++### Added+- Extracted `cek-mercury` as an independent example package from `cek-examples`.+- Implemented Warren Abstract Machine (WAM) relational unification engine.+- Conditional trailing on monotonic `SoAStore` cell allocations.+- Delimited choice points and nondeterministic search over unrolled `KontStack`.+- Support for `semidet` deterministic cut / commit (`GOnce`).+- Full Hspec test suite and Hackage-compliant package manifest.
+ LICENSE view
@@ -0,0 +1,391 @@+CEK Dual Licensing++Copyright (c) 2026, Nadia Yvette Chambers <nadia.yvette.chambers@ik.me>+All rights reserved.++SPDX-License-Identifier: EUPL-1.2 OR Apache-2.0++CEK is dual-licensed: you may use, copy, modify, merge, publish,+distribute, sublicense, and/or sell copies of the software under the terms+of EITHER:++1. The European Union Public Licence, version 1.2 (EUPL-1.2), as published by+   the European Commission (available in 23 authentic language versions); OR+2. The Apache License, Version 2.0 (Apache-2.0).++You may choose whichever license best fits your requirements and compliance+environment.++Individual license files are available in the LICENSES/ directory:+- LICENSES/EUPL-1.2.txt+- LICENSES/Apache-2.0.txt++================================================================================+1. European Union Public Licence v. 1.2 (EUPL-1.2)+================================================================================++                      EUROPEAN UNION PUBLIC LICENCE v. 1.2+                      EUPL © the European Union 2007, 2016++This European Union Public Licence (the ‘EUPL’) applies to the Work (as defined+below) which is provided under the terms of this Licence. Any use of the Work,+other than as authorised under this Licence is prohibited (to the extent such+use is covered by a right of the copyright holder of the Work).++The Work is provided under the terms of this Licence when the Licensor (as+defined below) has placed the following notice immediately following the+copyright notice for the Work:++        Licensed under the EUPL++or has expressed by any other means his willingness to license under the EUPL.++1. Definitions++In this Licence, the following terms have the following meaning:++- ‘The Licence’: this Licence.++- ‘The Original Work’: the work or software distributed or communicated by the+  Licensor under this Licence, available as Source Code and also as Executable+  Code as the case may be.++- ‘Derivative Works’: the works or software that could be created by the+  Licensee, based upon the Original Work or modifications thereof. This Licence+  does not define the extent of modification or dependence on the Original Work+  required in order to classify a work as a Derivative Work; this extent is+  determined by copyright law applicable in the country mentioned in Article 15.++- ‘The Work’: the Original Work or its Derivative Works.++- ‘The Source Code’: the human-readable form of the Work which is the most+  convenient for people to study and modify.++- ‘The Executable Code’: any code which has generally been compiled and which is+  meant to be interpreted by a computer as a program.++- ‘The Licensor’: the natural or legal person that distributes or communicates+  the Work under the Licence.++- ‘Contributor(s)’: any natural or legal person who modifies the Work under the+  Licence, or otherwise contributes to the creation of a Derivative Work.++- ‘The Licensee’ or ‘You’: any natural or legal person who makes any usage of+  the Work under the terms of the Licence.++- ‘Distribution’ or ‘Communication’: any act of selling, giving, lending,+  renting, distributing, communicating, transmitting, or otherwise making+  available, online or offline, copies of the Work or providing access to its+  essential functionalities at the disposal of any other natural or legal+  person.++2. Scope of the rights granted by the Licence++The Licensor hereby grants You a worldwide, royalty-free, non-exclusive,+sublicensable licence to do the following, for the duration of copyright vested+in the Original Work:++- use the Work in any circumstance and for all usage,+- reproduce the Work,+- modify the Work, and make Derivative Works based upon the Work,+- communicate to the public, including the right to make available or display+  the Work or copies thereof to the public and perform publicly, as the case may+  be, the Work,+- distribute the Work or copies thereof,+- lend and rent the Work or copies thereof,+- sublicense rights in the Work or copies thereof.++Those rights can be exercised on any media, supports and formats, whether now+known or later invented, as far as the applicable law permits so.++In the countries where moral rights apply, the Licensor waives his right to+exercise his moral right to the extent allowed by law in order to make effective+the licence of the economic rights here above listed.++The Licensor grants to the Licensee royalty-free, non-exclusive usage rights to+any patents held by the Licensor, to the extent necessary to make use of the+rights granted on the Work under this Licence.++3. Communication of the Source Code++The Licensor may provide the Work either in its Source Code form, or as+Executable Code. If the Work is provided as Executable Code, the Licensor+provides in addition a machine-readable copy of the Source Code of the Work+along with each copy of the Work that the Licensor distributes or indicates, in+a notice following the copyright notice attached to the Work, a repository where+the Source Code is easily and freely accessible for as long as the Licensor+continues to distribute or communicate the Work.++4. Limitations on copyright++Nothing in this Licence is intended to deprive the Licensee of the benefits from+any exception or limitation to the exclusive rights of the rights owners in the+Work, of the exhaustion of those rights or of other applicable limitations+thereto.++5. Obligations of the Licensee++The grant of the rights mentioned above is subject to some restrictions and+obligations imposed on the Licensee. Those obligations are the following:++Attribution right: The Licensee shall keep intact all copyright, patent or+trademarks notices and all notices that refer to the Licence and to the+disclaimer of warranties. The Licensee must include a copy of such notices and a+copy of the Licence with every copy of the Work he/she distributes or+communicates. The Licensee must cause any Derivative Work to carry prominent+notices stating that the Work has been modified and the date of modification.++Copyleft clause: If the Licensee distributes or communicates copies of the+Original Works or Derivative Works, this Distribution or Communication will be+done under the terms of this Licence or of a later version of this Licence+unless the Original Work is expressly distributed only under this version of the+Licence — for example by communicating ‘EUPL v. 1.2 only’. The Licensee+(becoming Licensor) cannot offer or impose any additional terms or conditions on+the Work or Derivative Work that alter or restrict the terms of the Licence.++Compatibility clause: If the Licensee Distributes or Communicates Derivative+Works or copies thereof based upon both the Work and another work licensed under+a Compatible Licence, this Distribution or Communication can be done under the+terms of this Compatible Licence. For the sake of this clause, ‘Compatible+Licence’ refers to the licences listed in the appendix attached to this Licence.+Should the Licensee's obligations under the Compatible Licence conflict with+his/her obligations under this Licence, the obligations of the Compatible+Licence shall prevail.++Provision of Source Code: When distributing or communicating copies of the Work,+the Licensee will provide a machine-readable copy of the Source Code or indicate+a repository where this Source will be easily and freely available for as long+as the Licensee continues to distribute or communicate the Work.++Legal Protection: This Licence does not grant permission to use the trade names,+trademarks, service marks, or names of the Licensor, except as required for+reasonable and customary use in describing the origin of the Work and+reproducing the content of the copyright notice.++6. Chain of Authorship++The original Licensor warrants that the copyright in the Original Work granted+hereunder is owned by him/her or licensed to him/her and that he/she has the+power and authority to grant the Licence.++Each Contributor warrants that the copyright in the modifications he/she brings+to the Work are owned by him/her or licensed to him/her and that he/she has the+power and authority to grant the Licence.++Each time You accept the Licence, the original Licensor and subsequent+Contributors grant You a licence to their contributions to the Work, under the+terms of this Licence.++7. Disclaimer of Warranty++The Work is a work in progress, which is continuously improved by numerous+Contributors. It is not a finished work and may therefore contain defects or+‘bugs’ inherent to this type of development.++For the above reason, the Work is provided under the Licence on an ‘as is’ basis+and without warranties of any kind concerning the Work, including without+limitation merchantability, fitness for a particular purpose, absence of defects+or errors, accuracy, non-infringement of intellectual property rights other than+copyright as stated in Article 6 of this Licence.++This disclaimer of warranty is an essential part of the Licence and a condition+for the grant of any rights to the Work.++8. Disclaimer of Liability++Except in the cases of wilful misconduct or damages directly caused to natural+persons, the Licensor will in no event be liable for any direct or indirect,+material or moral, damages of any kind, arising out of the Licence or of the use+of the Work, including without limitation, damages for loss of goodwill, work+stoppage, computer failure or malfunction, loss of data or any commercial+damage, even if the Licensor has been advised of the possibility of such damage.+However, the Licensor will be liable under statutory product liability laws as+far such laws apply to the Work.++9. Additional agreements++While distributing the Work, You may choose to conclude an additional agreement,+defining obligations or services consistent with this Licence. However, if+accepting obligations, You may act only on your own behalf and on your sole+responsibility, not on behalf of the original Licensor or any other Contributor,+and only if You agree to indemnify, defend, and hold each Contributor harmless+for any liability incurred by, or claims asserted against such Contributor by+the fact You have accepted any warranty or additional liability.++10. Acceptance of the Licence++The provisions of this Licence can be accepted by clicking on an icon ‘I agree’+placed under the bottom of a window displaying the text of this Licence or by+affirming consent in any other similar way, in accordance with the rules of+applicable law. Clicking on that icon indicates your clear and irrevocable+acceptance of this Licence and all of its terms and conditions.++Similarly, you irrevocably accept this Licence and all of its terms and+conditions by exercising any rights granted to You by Article 2 of this Licence,+such as the use of the Work, the creation by You of a Derivative Work or the+Distribution or Communication by You of the Work or copies thereof.++11. Information to the public++In case of any Distribution or Communication of the Work by means of electronic+communication by You (for example, by offering to download the Work from a+remote location) the distribution channel or media (for example, a website) must+at least provide to the public the information requested by the applicable law+regarding the Licensor, the Licence and the way it may be accessible, concluded,+stored and reproduced by the Licensee.++12. Termination of the Licence++The Licence and the rights granted hereunder will terminate automatically upon+any breach by the Licensee of the terms of the Licence.++Such a termination will not terminate the licences of any person who has+received the Work from the Licensee under the Licence, provided such persons+remain in full compliance with the Licence.++13. Miscellaneous++Without prejudice of Article 9 above, the Licence represents the complete+agreement between the Parties as to the Work.++If any provision of the Licence is invalid or unenforceable under applicable+law, this will not affect the validity or enforceability of the Licence as a+whole. Such provision will be construed or reformed so as necessary to make it+valid and enforceable.++The European Commission may publish other linguistic versions or new versions of+this Licence or updated versions of the Appendix, so far this is required and+reasonable, without reducing the scope of the rights granted by the Licence. New+versions of the Licence will be published with a unique version number.++All linguistic versions of this Licence, approved by the European Commission,+have identical value. Parties can take advantage of the linguistic version of+their choice.++14. Jurisdiction++Without prejudice to specific agreement between parties,++- any litigation resulting from the interpretation of this License, arising+  between the European Union institutions, bodies, offices or agencies, as a+  Licensor, and any Licensee, will be subject to the jurisdiction of the Court+  of Justice of the European Union, as laid down in article 272 of the Treaty on+  the Functioning of the European Union,++- any litigation arising between other parties and resulting from the+  interpretation of this License, will be subject to the exclusive jurisdiction+  of the competent court where the Licensor resides or conducts its primary+  business.++15. Applicable Law++Without prejudice to specific agreement between parties,++- this Licence shall be governed by the law of the European Union Member State+  where the Licensor has his seat, resides or has his registered office,++- this licence shall be governed by Belgian law if the Licensor has no seat,+  residence or registered office inside a European Union Member State.++Appendix++‘Compatible Licences’ according to Article 5 EUPL are:++- GNU General Public License (GPL) v. 2, v. 3+- GNU Affero General Public License (AGPL) v. 3+- Open Software License (OSL) v. 2.1, v. 3.0+- Eclipse Public License (EPL) v. 1.0+- CeCILL v. 2.0, v. 2.1+- Mozilla Public Licence (MPL) v. 2+- GNU Lesser General Public Licence (LGPL) v. 2.1, v. 3+- Creative Commons Attribution-ShareAlike v. 3.0 Unported (CC BY-SA 3.0) for+  works other than software+- European Union Public Licence (EUPL) v. 1.1, v. 1.2+- Québec Free and Open-Source Licence — Reciprocity (LiLiQ-R) or Strong+  Reciprocity (LiLiQ-R+).++The European Commission may update this Appendix to later versions of the above+licences without producing a new version of the EUPL, as long as they provide+the rights granted in Article 2 of this Licence and protect the covered Source+Code from exclusive appropriation.++All other changes or additions to this Appendix require the production of a new+EUPL version.++================================================================================+2. Apache License, Version 2.0 (Apache-2.0)+================================================================================++Apache License+Version 2.0, January 2004+http://www.apache.org/licenses/++TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++1. Definitions.++"License" shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document.++"Licensor" shall mean the copyright owner or entity authorized by the copyright owner that is granting the License.++"Legal Entity" shall mean the union of the acting entity and all other entities that control, are controlled by, or are under common control with that entity. For the purposes of this definition, "control" means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity.++"You" (or "Your") shall mean an individual or Legal Entity exercising permissions granted by this License.++"Source" form shall mean the preferred form for making modifications, including but not limited to software source code, documentation source, and configuration files.++"Object" form shall mean any form resulting from mechanical transformation or translation of a Source form, including but not limited to compiled object code, generated documentation, and conversions to other media types.++"Work" shall mean the work of authorship, whether in Source or Object form, made available under the License, as indicated by a copyright notice that is included in or attached to the work (an example is provided in the Appendix below).++"Derivative Works" shall mean any work, whether in Source or Object form, that is based on (or derived from) the Work and for which the editorial revisions, annotations, elaborations, or other modifications represent, as a whole, an original work of authorship. For the purposes of this License, Derivative Works shall not include works that remain separable from, or merely link (or bind by name) to the interfaces of, the Work and Derivative Works thereof.++"Contribution" shall mean any work of authorship, including the original version of the Work and any modifications or additions to that Work or Derivative Works thereof, that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner. For the purposes of this definition, "submitted" means any form of electronic, verbal, or written communication sent to the Licensor or its representatives, including but not limited to communication on electronic mailing lists, source code control systems, and issue tracking systems that are managed by, or on behalf of, the Licensor for the purpose of discussing and improving the Work, but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as "Not a Contribution."++"Contributor" shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work.++2. Grant of Copyright License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable copyright license to reproduce, prepare Derivative Works of, publicly display, publicly perform, sublicense, and distribute the Work and such Derivative Works in Source or Object form.++3. Grant of Patent License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable (except as stated in this section) patent license to make, have made, use, offer to sell, sell, import, and otherwise transfer the Work, where such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted. If You institute patent litigation against any entity (including a cross-claim or counterclaim in a lawsuit) alleging that the Work or a Contribution incorporated within the Work constitutes direct or contributory patent infringement, then any patent licenses granted to You under this License for that Work shall terminate as of the date such litigation is filed.++4. Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions:++     (a) You must give any other recipients of the Work or Derivative Works a copy of this License; and++     (b) You must cause any modified files to carry prominent notices stating that You changed the files; and++     (c) You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works; and++     (d) If the Work includes a "NOTICE" text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License.++     You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License.++5. Submission of Contributions. Unless You explicitly state otherwise, any Contribution intentionally submitted for inclusion in the Work by You to the Licensor shall be under the terms and conditions of this License, without any additional terms or conditions. Notwithstanding the above, nothing herein shall supersede or modify the terms of any separate license agreement you may have executed with Licensor regarding such Contributions.++6. Trademarks. This License does not grant permission to use the trade names, trademarks, service marks, or product names of the Licensor, except as required for reasonable and customary use in describing the origin of the Work and reproducing the content of the NOTICE file.++7. Disclaimer of Warranty. Unless required by applicable law or agreed to in writing, Licensor provides the Work (and each Contributor provides its Contributions) on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are solely responsible for determining the appropriateness of using or redistributing the Work and assume any risks associated with Your exercise of permissions under this License.++8. Limitation of Liability. In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall any Contributor be liable to You for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising as a result of this License or out of the use or inability to use the Work (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if such Contributor has been advised of the possibility of such damages.++9. Accepting Warranty or Additional Liability. While redistributing the Work or Derivative Works thereof, You may choose to offer, and charge a fee for, acceptance of support, warranty, indemnity, or other liability obligations and/or rights consistent with this License. However, in accepting such obligations, You may act only on Your own behalf and on Your sole responsibility, not on behalf of any other Contributor, and only if You agree to indemnify, defend, and hold each Contributor harmless for any liability incurred by, or claims asserted against, such Contributor by reason of your accepting any such warranty or additional liability.++END OF TERMS AND CONDITIONS++APPENDIX: How to apply the Apache License to your work.++To apply the Apache License to your work, attach the following boilerplate notice, with the fields enclosed by brackets "[]" replaced with your own identifying information. (Don't include the brackets!)  The text should be enclosed in the appropriate comment syntax for the file format. We also recommend that a file or class name and description of purpose be included on the same "printed page" as the copyright notice for easier identification within third-party archives.++Copyright [yyyy] [name of copyright owner]++Licensed under the Apache License, Version 2.0 (the "License");+you may not use this file except in compliance with the License.+You may obtain a copy of the License at++http://www.apache.org/licenses/LICENSE-2.0++Unless required by applicable law or agreed to in writing, software+distributed under the License is distributed on an "AS IS" BASIS,+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+See the License for the specific language governing permissions and+limitations under the License.
+ README.md view
@@ -0,0 +1,28 @@+# cek-mercury++> **Important Notice:** This package is an educational and demonstrative reference implementation showcasing relational unification, Warren Abstract Machine (WAM) conditional trailing, and nondeterministic search over `KontStack` choice points. It is provided primarily as an executable architectural example within the `cek` ecosystem documentation.++## Overview++`cek-mercury` implements a high-performance relational unification and search engine inspired by the Warren Abstract Machine (WAM) and Mercury's deterministic execution models, executing entirely over unboxed CEK data structures:++1. **Term Allocation Heap:** Mapped onto the 4096-cell chunked `SoAStore`.+2. **Clause Dispatch Stack:** Mapped onto the unrolled 32-frame `KontStack`.+3. **WAM Conditional Trailing:** Bound variables allocate trail entries only if their address precedes the most recent choice point watermark (`heapWatermark`), bypassing trail overhead for transient intra-clause bindings.+4. **Delimited Commits (`semidet`):** Mercury's deterministic commits (`GOnce`) prune intermediate choice points instantaneously by resetting the choice point watermark.++## Module Structure++- `Cek.Mercury`: Primary reference engine and AST definitions.+- `Cek.Examples.Mercury`: Backward-compatibility re-export module.++## Building and Testing++```bash+cabal build cek-mercury+cabal test cek-mercury:tests+```++## License++EUPL-1.2.
+ cek-mercury.cabal view
@@ -0,0 +1,58 @@+cabal-version: 3.0+name: cek-mercury+version: 0.1.0.2+synopsis: Demonstrative Prolog/Mercury relational engine for CEK machines+description:+  An educational and demonstrative reference engine showcasing Prolog and Mercury+  relational unification, Warren Abstract Machine (WAM) conditional trailing,+  and nondeterministic search over unrolled KontStack choice points.++  Notice: This package is provided primarily as an executable architectural example+  and documentation case study within the @cek@ ecosystem.+license: EUPL-1.2 OR Apache-2.0+license-file: LICENSE+author: Nadia Yvette Chambers+maintainer: nadia.yvette.chambers@ik.me+category: Language, Compilers/Interpreters+homepage: https://github.com/NadiaYvette/cek+bug-reports: https://github.com/NadiaYvette/cek/issues+extra-doc-files:+  README.md+  CHANGELOG.md+build-type: Simple+tested-with: GHC == 9.14.1++source-repository head+  type: git+  location: https://github.com/NadiaYvette/cek+  subdir: packages/cek-mercury++library+  exposed-modules:+    Cek.Mercury+    Cek.Examples.Mercury+  hs-source-dirs: src+  default-language: Haskell2010+  ghc-options: -Wall -Wcompat -Wredundant-constraints+  build-depends:+    base >= 4.18 && < 5,+    ghc-prim >= 0.10 && < 0.14,+    primitive >= 0.9 && < 0.10,+    cek-core >= 0.1.0.0 && < 0.2,+    cek-pykinos >= 0.1.0.0 && < 0.2,+    pykinos-core >= 0.1.0.0 && < 0.2++test-suite tests+  type: exitcode-stdio-1.0+  main-is: Main.hs+  hs-source-dirs: test+  default-language: Haskell2010+  ghc-options: -Wall -Wcompat -Wredundant-constraints -threaded+  build-depends:+    base >= 4.18 && < 5,+    cek-core >= 0.1.0.0 && < 0.2,+    cek-pykinos >= 0.1.0.0 && < 0.2,+    pykinos-core >= 0.1.0.0 && < 0.2,+    cek-mercury >= 0.1.0.0 && < 0.2,+    primitive >= 0.9 && < 0.10,+    hspec >= 2.10 && < 2.12
+ src/Cek/Examples/Mercury.hs view
@@ -0,0 +1,12 @@+-- |+-- Module      : Cek.Examples.Mercury+-- Description : Backward-compatible alias for Cek.Mercury+-- Copyright   : (c) Nadia Yvette Chambers, 2026+-- License     : EUPL-1.2+--+-- Re-exports 'Cek.Mercury' for backward compatibility with existing codebases.+module Cek.Examples.Mercury+  ( module Cek.Mercury+  ) where++import Cek.Mercury
+ src/Cek/Mercury.hs view
@@ -0,0 +1,429 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StrictData #-}+{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}++-- |+-- Module      : Cek.Examples.Mercury+-- Description : Prolog/Mercury relational unification and backtracking engine on KontStack.+--+-- Demonstrates how 'KontStack' (O(1) copy-on-write continuation capture) and+-- 'SoAStore' (monotonic cell allocation with WAM conditional trailing) support+-- nondeterministic relational search, deep term unification, and @semidet@ commits.+--+-- === Architecture: WAM Relational Search on SoA Structures+--+-- The Warren Abstract Machine (WAM) achieves high-speed execution of Prolog and Mercury+-- by pairing three distinct memory areas:+--+--   1. An allocation heap for terms: mapped onto the 4096-cell chunked 'SoAStore'.+--   2. A continuation stack for clause dispatch: mapped onto the unrolled 32-frame 'KontStack'.+--   3. An undo trail for unbinding variables during backtracking: stored in an unboxed+--      'MutableByteArray' ('leTrail').+--+-- === WAM Conditional Trailing Invariant+--+-- When binding an unbound logic variable at cell @varAddr@ to a target term at @targetAddr@:+--+--   * If @varAddr < heapWatermark@ (where @heapWatermark@ is the store allocation cursor at+--     the most recent choice point), the variable was allocated /before/ the choice point+--     and must be recorded on the trail ('leTrail') so it can be reset to 'CT_Unbound'+--     upon failure.+--   * If @varAddr >= heapWatermark@, the variable was created /within/ the current alternative.+--     Backtracking simply resets the store allocation pointer, so trailing is bypassed.+--+-- === Delimited Commits and Choice-Point Pruning+--+-- Mercury's @semidet@ deterministic commits (or Prolog cuts @!@) prune choice points.+-- In 'solveMercury', cuts simply reset the choice point counter @cpCursor@ to the saved+-- watermark, instantly reclaiming all intermediate choice point states.+--+-- > **Demonstrative Reference Implementation**: This package is an educational+-- > and demonstrative reference implementation showcasing relational unification,+-- > WAM conditional trailing, and nondeterministic search over KontStack choice points.+-- > It is provided primarily as an executable architectural example within the @cek@+-- > ecosystem documentation.+--+module Cek.Mercury+  ( -- * Relational AST and Goals+    LogicTerm(..)+  , Goal(..)++    -- * WAM Engine State+  , LogicEngine(..)++    -- * Continuation Frame Tags+  , pattern FT_ConjR+  , pattern FT_CommitCut+  , pattern FT_UnifyArgs++    -- * Engine Lifecycle and Solver+  , newLogicEngine+  , solveMercury+  ) where++import Control.Monad (when)+import Control.Monad.ST (ST, runST)+import Data.Bits (shiftR, (.&.))+import Data.Int (Int32)+import Data.Primitive.ByteArray+  ( MutableByteArray+  , newByteArray+  , readByteArray+  , writeByteArray+  )+import Data.Primitive.SmallArray+  ( SmallArray+  , SmallMutableArray+  , indexSmallArray+  , newSmallArray+  , readSmallArray+  , sizeofSmallArray+  , smallArrayFromList+  , writeSmallArray+  )+import Data.Word (Word32)+import GHC.Exts (unsafeCoerce#)++import Cek.Pykinos.Kont+  ( CapturedKont(..)+  , FrameTag(..)+  , KontBlock+  , KontStack+  , captureKontSoA+  , newKontStack+  , popFrameSoA+  , pushFrameSoA+  , restoreKontSoA+  )+import Cek.Pykinos.Store+  ( CellTag(..)+  , SoAStore(..)+  , StoreChunk(..)+  , acquireSlot+  , allocWLitSoA+  , newSoAStore+  , pattern CT_Thunk+  , pattern CT_Unbound+  , pattern CT_WLit+  , pattern CT_WRecord+  , readCellPhaseSoA+  , unCellTag+  )++-- | Frame tag for evaluating the right-hand conjunct @g2@ after @g1@ succeeds.+pattern FT_ConjR     :: FrameTag+pattern FT_ConjR     = FrameTag 20++-- | Frame tag for committing a @once@ / cut block by pruning choice points.+pattern FT_CommitCut :: FrameTag+pattern FT_CommitCut = FrameTag 21++-- | Frame tag for continuing deep unification of remaining compound functor arguments.+pattern FT_UnifyArgs :: FrameTag+pattern FT_UnifyArgs = FrameTag 22++-- | First-order logic terms (variables, unboxed integer constants, and compound functors).+data LogicTerm+  = LVar !Int+    -- ^ Logic variable reference resolved through the local lexical environment.+  | LLit !Int32+    -- ^ 32-bit signed integer literal constant.+  | LFun !Word32 !(SmallArray LogicTerm)+    -- ^ Compound functor term @f(t0, t1, ...)@ with symbol ID and argument array.+  deriving (Eq, Show)++-- | Relational goal calculus supporting conjunction, disjunction, fresh variables, and commits.+data Goal+  = GSuccess+    -- ^ Trivial success goal (@true@ in Prolog).+  | GFail+    -- ^ Trivial failure goal that immediately triggers backtracking.+  | GUnify !LogicTerm !LogicTerm+    -- ^ Bidirectional Robinson unification between two terms @t1 = t2@.+  | GFresh !Goal+    -- ^ Fresh logic variable binder introducing a new unbound cell in 'SoAStore'.+  | GConj  !Goal !Goal+    -- ^ Logical conjunction @(g1 , g2)@ evaluated left-to-right.+  | GDisj  ![Goal]+    -- ^ Nondeterministic disjunction @(g1 ; g2 ; ...)@ creating a choice point.+  | GOnce  !Goal+    -- ^ Prune choice points created within @g@ upon first successful solution (@once/1@).+  deriving (Eq, Show)++-- | Mutable WAM execution state combining 'SoAStore', 'KontStack', an unboxed trail,+--   and an unboxed choice-point watermark stack.+data LogicEngine s = LogicEngine+  { leStore     :: !(SoAStore s)+    -- ^ Term and variable allocation arena.+  , leKont      :: !(KontStack s)+    -- ^ Small-step goal continuation stack.+  , leTrail     :: !(MutableByteArray s)+    -- ^ Unboxed array of trailed variable addresses to be reset on backtrack.+  , leCpUnboxed :: !(MutableByteArray s)+    -- ^ Unboxed choice-point table (kCur, storeNext, trailCur).+  , leCpKontBlk :: !(SmallMutableArray s (KontBlock s))+    -- ^ Saved top continuation blocks for frozen choice points.+  , leCpAlts    :: !(SmallMutableArray s ([Goal], [Int32]))+    -- ^ Remaining alternative goals and environment frames per choice point.+  , leCounters  :: !(MutableByteArray s)+    -- ^ Engine registers: Int32[0] = trailCursor, Int32[1] = cpCursor, Int32[2] = heapWatermark+  }++-- | Initialize a fresh 'LogicEngine' with pre-allocated trail and choice-point slabs.+newLogicEngine :: ST s (LogicEngine s)+newLogicEngine = do+  leStore     <- newSoAStore+  leKont      <- newKontStack+  leTrail     <- newByteArray (16384 * 4)+  leCpUnboxed <- newByteArray (1024 * 16)+  leCpKontBlk <- newSmallArray 1024 (unsafeCoerce# ())+  leCpAlts    <- newSmallArray 1024 ([], [])+  leCounters  <- newByteArray 12+  writeByteArray leCounters 0 (0 :: Int32)+  writeByteArray leCounters 1 (0 :: Int32)+  writeByteArray leCounters 2 (0 :: Int32)+  pure LogicEngine{..}++-- | Allocate an unbound unification variable ('CT_Unbound') in 'SoAStore' with 0 pointer writes.+{-# INLINE allocUnboundVar #-}+allocUnboundVar :: SoAStore s -> ST s Int32+allocUnboundVar store = do+  (!addr, StoreChunk{..}, !slot) <- acquireSlot store+  writeByteArray scUnboxed slot (unCellTag CT_Unbound)+  pure addr++-- | Dereference variable indirection chains ('CT_Thunk' -> targetAddr) in 'SoAStore'.+{-# INLINE derefLogicAddr #-}+derefLogicAddr :: SoAStore s -> Int32 -> ST s (Int32, CellTag, Int32, StoreChunk s, Int)+derefLogicAddr store !addr0 = go addr0+  where+    go !addr = do+      (!tag, !aux, !chunk, !slot) <- readCellPhaseSoA store addr+      if tag == CT_Thunk+        then go aux+        else pure (addr, tag, aux, chunk, slot)++-- | Bind an unbound logic variable at 'varAddr' to 'targetAddr' using WAM conditional trailing.+{-# INLINE bindLogicVar #-}+bindLogicVar :: LogicEngine s -> Int32 -> Int32 -> ST s ()+bindLogicVar LogicEngine{..} !varAddr !targetAddr+  | varAddr == targetAddr = pure ()+  | otherwise = do+      let !ix   = fromIntegral varAddr :: Int+          !slot = ix .&. 0xFFF+      StoreChunk{..} <- readSmallArray (ssChunks leStore) (ix `shiftR` 12)+      writeByteArray scUnboxed slot (unCellTag CT_Thunk)+      writeByteArray scUnboxed (5120 + slot) targetAddr+      watermark :: Int32 <- readByteArray leCounters 2+      when (varAddr < watermark) $ do+        tCur :: Int32 <- readByteArray leCounters 0+        writeByteArray leTrail (fromIntegral tCur) varAddr+        writeByteArray leCounters 0 (tCur + 1)++-- | Materialize a syntax 'LogicTerm' into a 'SoAStore' cell address.+instantiateTerm :: LogicEngine s -> [Int32] -> LogicTerm -> ST s Int32+instantiateTerm eng@LogicEngine{..} env = \case+  LVar ix        -> pure (env !! ix)+  LLit n         -> allocWLitSoA leStore n+  LFun fSym args -> do+    let !n = sizeofSmallArray args+    argAddrs <- mapM (\i -> instantiateTerm eng env (indexSmallArray args i)) [0 .. n - 1]+    (!addr, StoreChunk{..}, !slot) <- acquireSlot leStore+    writeByteArray scUnboxed slot (unCellTag CT_WRecord)+    writeByteArray scUnboxed (5120 + slot) (fromIntegral fSym :: Int32)+    writeSmallArray scPtrA slot (unsafeCoerce# (smallArrayFromList argAddrs))+    pure addr++-- | Execute a relational 'Goal' over @numQueryVars@ root variables and collect up to+--   @maxSolutions@ integer bindings per query variable across backtracking branches.+solveMercury :: Int -> Int -> Goal -> [[Maybe Int32]]+solveMercury !maxSolutions !numQueryVars rootGoal = runST $ do+  eng@LogicEngine{..} <- newLogicEngine+  queryAddrs <- mapM (\_ -> allocUnboundVar leStore) [1 .. numQueryVars]+  let readQueryBinding !qAddr = do+        (!_a, !tag, !aux, !_chk, !_slot) <- derefLogicAddr leStore qAddr+        if tag == CT_WLit+          then pure (Just aux)+          else pure Nothing++      evalGoal !goal !env !accSols+        | length accSols >= maxSolutions = pure (reverse accSols)+        | otherwise = case goal of+            -- Success: proceed to the next pending continuation frame in KontStack+            GSuccess -> continueSuccess accSols+            -- Failure: trigger choice-point restoration and trail unwinding+            GFail    -> backtrack accSols++            -- Allocate fresh unbound unification variable and extend lexical scope+            GFresh body -> do+              vAddr <- allocUnboundVar leStore+              evalGoal body (vAddr : env) accSols++            -- Conjunction: push right goal onto KontStack and evaluate left goal+            GConj g1 g2 -> do+              pushFrameSoA leKont FT_ConjR 0 0 (unsafeCoerce# g2) (unsafeCoerce# env)+              evalGoal g1 env accSols++            -- Once / Cut: save current choice point watermark and commit on success+            GOnce g -> do+              cpCur :: Int32 <- readByteArray leCounters 1+              pushFrameSoA leKont FT_CommitCut cpCur 0 (unsafeCoerce# ()) (unsafeCoerce# ())+              evalGoal g env accSols++            -- Empty disjunction: no alternatives left; initiate backtrack+            GDisj []       -> backtrack accSols+            -- Single disjunct: deterministic execution without creating a choice point+            GDisj [single] -> evalGoal single env accSols+            -- Multiple disjuncts: freeze KontStack, record trail and store cursors+            GDisj (firstAlt : restAlts) -> do+              CapturedKont topBlk kCur <- captureKontSoA leKont+              storeNext :: Int32 <- readByteArray (ssState leStore) 0+              trailCur  :: Int32 <- readByteArray leCounters 0+              cpCur     :: Int32 <- readByteArray leCounters 1+              let !cpIx = fromIntegral cpCur :: Int+                  !base = cpIx * 4+              -- Save choice point registers into unboxed table:+              writeByteArray leCpUnboxed (base + 0) (fromIntegral kCur :: Int32)+              writeByteArray leCpUnboxed (base + 1) storeNext+              writeByteArray leCpUnboxed (base + 2) trailCur+              -- Save frozen continuation block and remaining alternatives:+              writeSmallArray leCpKontBlk cpIx topBlk+              writeSmallArray leCpAlts    cpIx (restAlts, env)+              writeByteArray leCounters 1 (cpCur + 1)+              writeByteArray leCounters 2 storeNext+              evalGoal firstAlt env accSols++            -- Robinson first-order unification between instantiated terms+            GUnify t1 t2 -> do+              a1 <- instantiateTerm eng env t1+              a2 <- instantiateTerm eng env t2+              unifyAddrs a1 a2 accSols++      unifyAddrs !u1 !u2 !accSols = do+        (!a1, !tag1, !aux1, !chk1, !slot1) <- derefLogicAddr leStore u1+        (!a2, !tag2, !aux2, !chk2, !slot2) <- derefLogicAddr leStore u2+        -- Identical cell addresses unify trivially without memory writes+        if a1 == a2+          then continueSuccess accSols+          else case (tag1, tag2) of+            -- Unbound variable on left: bind to right address with trailing+            (CT_Unbound, _) -> bindLogicVar eng a1 a2 >> continueSuccess accSols+            -- Unbound variable on right: bind to left address with trailing+            (_, CT_Unbound) -> bindLogicVar eng a2 a1 >> continueSuccess accSols+            -- Primitive integer literals: test equality of unboxed AuxInt values+            (CT_WLit, CT_WLit)+              | aux1 == aux2 -> continueSuccess accSols+              | otherwise    -> backtrack accSols+            -- Compound record/functor structures: compare symbol IDs and unify arguments+            (CT_WRecord, CT_WRecord)+              | aux1 == aux2 -> do+                  arr1 :: SmallArray Int32 <- unsafeCoerce# <$> readSmallArray (scPtrA chk1) slot1+                  arr2 :: SmallArray Int32 <- unsafeCoerce# <$> readSmallArray (scPtrA chk2) slot2+                  let !n1 = sizeofSmallArray arr1+                      !n2 = sizeofSmallArray arr2+                  if n1 /= n2+                    then backtrack accSols+                    else if n1 == 0+                      then continueSuccess accSols+                      else do+                        -- Push remaining arguments onto KontStack for incremental verification:+                        when (n1 > 1) $+                          pushFrameSoA leKont FT_UnifyArgs 1 (fromIntegral n1)+                            (unsafeCoerce# arr1) (unsafeCoerce# arr2)+                        unifyAddrs (indexSmallArray arr1 0) (indexSmallArray arr2 0) accSols+            _ -> backtrack accSols++      continueSuccess !accSols = do+        mbFrame <- popFrameSoA leKont+        case mbFrame of+          -- No more frames on KontStack: an entire relational solution was derived+          Nothing -> do+            sol <- mapM readQueryBinding queryAddrs+            let !accSols' = sol : accSols+            if length accSols' >= maxSolutions+              then pure (reverse accSols')+              else backtrack accSols'++          Just (ft, intA, intB, ptrA, ptrB)+            -- Resume right-hand conjunct+            | ft == FT_ConjR -> do+                let !g2  = unsafeCoerce# ptrA :: Goal+                    !env = unsafeCoerce# ptrB :: [Int32]+                evalGoal g2 env accSols+            -- Commit cut: prune choice points older than the cut watermark+            | ft == FT_CommitCut -> do+                writeByteArray leCounters 1 intA+                if intA > 0+                  then do+                    prevWm :: Int32 <- readByteArray leCpUnboxed (fromIntegral (intA - 1) * 4 + 1)+                    writeByteArray leCounters 2 prevWm+                  else writeByteArray leCounters 2 (0 :: Int32)+                continueSuccess accSols+            -- Resume argument unification+            | ft == FT_UnifyArgs -> do+                let !cur  = fromIntegral intA :: Int+                    !len  = fromIntegral intB :: Int+                    !arr1 = unsafeCoerce# ptrA :: SmallArray Int32+                    !arr2 = unsafeCoerce# ptrB :: SmallArray Int32+                when (cur + 1 < len) $+                  pushFrameSoA leKont FT_UnifyArgs (intA + 1) intB ptrA ptrB+                unifyAddrs (indexSmallArray arr1 cur) (indexSmallArray arr2 cur) accSols+            | otherwise -> pure (reverse accSols)++      backtrack !accSols = do+        cpCur :: Int32 <- readByteArray leCounters 1+        -- If no choice points remain, all search branches have been exhausted+        if cpCur <= 0+          then pure (reverse accSols)+          else do+            let !cpIx = fromIntegral (cpCur - 1) :: Int+                !base = cpIx * 4+            !savedKCur      :: Int32 <- readByteArray leCpUnboxed (base + 0)+            !savedStoreNext :: Int32 <- readByteArray leCpUnboxed (base + 1)+            !savedTrailCur  :: Int32 <- readByteArray leCpUnboxed (base + 2)+            !savedKBlk      <- readSmallArray leCpKontBlk cpIx+            (!alts, !env)   <- readSmallArray leCpAlts cpIx++            -- 1. Unwind trailed variable bindings back to CT_Unbound+            curTrail :: Int32 <- readByteArray leCounters 0+            let unwindTrail !t+                  | t <= savedTrailCur = pure ()+                  | otherwise = do+                      !trailedAddr :: Int32 <- readByteArray leTrail (fromIntegral (t - 1))+                      let !ix   = fromIntegral trailedAddr :: Int+                          !slot = ix .&. 0xFFF+                      StoreChunk{..} <- readSmallArray (ssChunks leStore) (ix `shiftR` 12)+                      writeByteArray scUnboxed slot (unCellTag CT_Unbound)+                      unwindTrail (t - 1)+            unwindTrail curTrail+            writeByteArray leCounters 0 savedTrailCur++            -- 2. Reclaim all speculative SoAStore allocations in O(1)+            writeByteArray (ssState leStore) 0 savedStoreNext++            -- 3. Restore the 32-frame SoA KontStack in O(1)+            restoreKontSoA leKont (CapturedKont savedKBlk (fromIntegral savedKCur))++            -- 4. Advance or pop choice point+            case alts of+              [] -> do+                writeByteArray leCounters 1 (cpCur - 1)+                backtrack accSols+              [lastAlt] -> do+                writeByteArray leCounters 1 (cpCur - 1)+                if cpCur - 1 > 0+                  then do+                    prevWm :: Int32 <- readByteArray leCpUnboxed (fromIntegral (cpCur - 2) * 4 + 1)+                    writeByteArray leCounters 2 prevWm+                  else writeByteArray leCounters 2 (0 :: Int32)+                evalGoal lastAlt env accSols+              (nextAlt : moreAlts) -> do+                writeSmallArray leCpAlts cpIx (moreAlts, env)+                evalGoal nextAlt env accSols++  evalGoal rootGoal queryAddrs []
+ test/Main.hs view
@@ -0,0 +1,27 @@+{-# LANGUAGE OverloadedStrings #-}++-- |+-- Module      : Main+-- Description : Unit test suite for Cek.Mercury+-- Copyright   : (c) Nadia Yvette Chambers, 2026+-- License     : EUPL-1.2+module Main (main) where++import Test.Hspec++import Cek.Mercury++main :: IO ()+main = hspec $ do+  describe "Cek.Mercury (WAM Conditional Trailing & KontStack Choice-Points)" $ do+    it "finds all solutions via nondeterministic disjunction" $ do+      -- q(X) :- X = 1 ; X = 2 ; X = 3+      let goal = GDisj [GUnify (LVar 0) (LLit 1), GUnify (LVar 0) (LLit 2), GUnify (LVar 0) (LLit 3)]+          solutions = solveMercury 10 1 goal+      solutions `shouldBe` [[Just 1], [Just 2], [Just 3]]++    it "prunes remaining disjuncts with GOnce (semidet cut)" $ do+      -- q(X) :- once(X = 1 ; X = 2)+      let goal = GOnce (GDisj [GUnify (LVar 0) (LLit 1), GUnify (LVar 0) (LLit 2)])+          solutions = solveMercury 10 1 goal+      solutions `shouldBe` [[Just 1]]