cek-scheme (empty) → 0.1.0.2
raw patch · 7 files changed
+986/−0 lines, 7 filesdep +basedep +cek-coredep +cek-pykinos
Dependencies added: base, cek-core, cek-pykinos, cek-scheme, ghc-prim, hspec, primitive, pykinos-core
Files
- CHANGELOG.md +22/−0
- LICENSE +391/−0
- README.md +27/−0
- cek-scheme.cabal +59/−0
- src/Cek/Examples/Scheme.hs +12/−0
- src/Cek/Scheme.hs +431/−0
- test/Main.hs +44/−0
+ CHANGELOG.md view
@@ -0,0 +1,22 @@+# Changelog for `cek-scheme`++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-scheme` as an independent example package from `cek-examples`.+- Implemented R5RS/R7RS Call-by-Value mini-interpreter with `Generic1` dissection.+- O(1) Copy-on-Write continuation capture and restoration via `captureKontSoA` and `restoreKontSoA` (`call/cc`).+- Unboxed mutable lexical environment cells (`set!`) backed by `SoAStore`.+- Full Hspec unit 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,27 @@+# cek-scheme++> **Important Notice:** This package is an educational and demonstrative reference implementation showcasing CEK machine execution with first-class continuations (`call/cc`), mutable lexical environments (`set!`), and automatic GHC `Generic1` polynomial functor dissection. It is provided primarily as an executable example and architectural pattern within the `cek` ecosystem documentation.++## Overview++`cek-scheme` implements a Call-by-Value mini-Scheme interpreter demonstrating how higher-order control flow and mutable state are cleanly evaluated on top of the `cek` abstract machine infrastructure:++1. **Pure Syntactic Spines:** Arithmetic operations (`SAdd`, `SSub`, `SMul`), relational comparisons, and sequencing (`SSeq`) are evaluated without manual frame plumbing via automatic `Generic1` dissection (`Dissectable`).+2. **First-Class Continuations (`call/cc`):** Continuations capture the unrolled 32-frame `KontStack` in strictly $O(1)$ time via Copy-on-Write (`captureKontSoA`). Reinstating a captured continuation (`restoreKontSoA`) resumes execution with zero stack unwinding.+3. **Mutable Lexical Scope (`set!`):** Lexical variables occupy mutable cells allocated in the unboxed `SoAStore`.++## Module Structure++- `Cek.Scheme`: Primary reference evaluator and AST definitions.+- `Cek.Examples.Scheme`: Backward-compatibility re-export module.++## Building and Testing++```bash+cabal build cek-scheme+cabal test cek-scheme:tests+```++## License++EUPL-1.2.
+ cek-scheme.cabal view
@@ -0,0 +1,59 @@+cabal-version: 3.0+name: cek-scheme+version: 0.1.0.2+synopsis: Demonstrative Call-by-Value Scheme reference interpreter for CEK machines+description:+ An educational and demonstrative reference interpreter showcasing Call-by-Value+ Scheme with automatic Generic1 polynomial functor dissection, first-class call/cc+ continuations with O(1) Copy-on-Write capture, and mutable lexical variables+ over the CEK abstract machine architecture.++ 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-scheme++library+ exposed-modules:+ Cek.Scheme+ Cek.Examples.Scheme+ 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-scheme >= 0.1.0.0 && < 0.2,+ primitive >= 0.9 && < 0.10,+ hspec >= 2.10 && < 2.12
+ src/Cek/Examples/Scheme.hs view
@@ -0,0 +1,12 @@+-- |+-- Module : Cek.Examples.Scheme+-- Description : Backward-compatible alias for Cek.Scheme+-- Copyright : (c) Nadia Yvette Chambers, 2026+-- License : EUPL-1.2+--+-- Re-exports 'Cek.Scheme' for backward compatibility with existing codebases.+module Cek.Examples.Scheme+ ( module Cek.Scheme+ ) where++import Cek.Scheme
+ src/Cek/Scheme.hs view
@@ -0,0 +1,431 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DerivingStrategies #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StrictData #-}+{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}++-- |+-- Module : Cek.Examples.Scheme+-- Description : Call-by-Value Scheme interpreter showcasing Generic1 Dissection and O(1) CoW call/cc.+--+-- Demonstrates how a language can combine automatic polynomial functor dissection+-- ('Dissectable' derived via 'Generic1') for uniform left-to-right expression spines+-- with explicit control and state effects ('SCallCC', 'SSet') backed by 'KontStack'+-- and 'SoAStore'.+--+-- === Architecture of the Scheme Showcase+--+-- The Scheme interpreter models R5RS/R7RS Call-by-Value semantics:+--+-- 1. Pure syntactic expressions (such as arithmetic operations 'SAdd', 'SSub', 'SMul',+-- comparisons 'SEq', and sequencing 'SSeq') require zero manual frame management:+-- they are evaluated left-to-right automatically by GHC's derived 'Generic1'+-- dissection ('FT_PureDissect').+-- 2. Mutable variables (@set!@) manipulate memory cells allocated in the unboxed 'SoAStore'.+-- 3. First-class continuations (@call/cc@) capture the entire 32-frame unrolled+-- 'KontStack' in strictly $O(1)$ time via Copy-on-Write ('captureKontSoA').+-- Invoking a captured continuation reinstates the execution context immediately+-- ('restoreKontSoA') with zero stack unwinding overhead.+--+-- > **Demonstrative Reference Implementation**: This package is an educational+-- > and demonstrative reference implementation showcasing CEK machine execution with+-- > first-class continuations (@call/cc@), mutable lexical state, and automatic+-- > GHC 'Generic1' polynomial functor dissection. It is provided primarily as an+-- > executable architectural example within the @cek@ ecosystem documentation.+--+module Cek.Scheme+ ( -- * Syntax Functors and Trees+ Fix(..)+ , SchemeF(..)+ , SchemeTerm++ -- * Values and Environments+ , SchemeVal(..)+ , SchemeEnv(..)+ , SchemeError(..)++ -- * Continuation Frame Tags+ , pattern FT_SchemeIf+ , pattern FT_SchemeSet+ , pattern FT_SchemeCallCC+ , pattern FT_SchemeAppFn+ , pattern FT_SchemeAppArgs++ -- * Evaluator Entry Point+ , evalScheme+ ) where++import Control.Monad.ST (ST, runST)+import Data.Bits (shiftR, (.&.))+import Data.Int (Int32)+import Data.Primitive.ByteArray (writeByteArray)+import Data.Primitive.SmallArray+ ( SmallArray+ , indexSmallArray+ , readSmallArray+ , sizeofSmallArray+ , smallArrayFromList+ , writeSmallArray+ )+import GHC.Exts (unsafeCoerce#)+import GHC.Generics (Generic1)++import Cek.Core.Dissect (Dissect, Dissectable(..))+import Cek.Pykinos.Kont+ ( CapturedKont(..)+ , FrameTag(..)+ , KontStack+ , captureKontSoA+ , newKontStack+ , pattern FT_PureDissect+ , popFrameSoA+ , pushFrameSoA+ , restoreKontSoA+ )+import Cek.Pykinos.Store+ ( SoAStore(..)+ , StoreChunk(..)+ , acquireSlot+ , newSoAStore+ , pattern CT_WRecord+ , unCellTag+ )++-- | Fixed-point wrapper for recursive syntax functors.+newtype Fix f = In { out :: f (Fix f) }++-- | Base pattern functor for the Call-by-Value Scheme showcase calculus.+--+-- Uniform expression nodes ('SAdd', 'SSub', 'SMul', 'SEq', 'SSeq') are handled+-- automatically by the derived 'Generic1' 'Dissectable' instance.+-- Special binding/control forms ('SVar', 'SLam', 'SLet', 'SSet', 'SIf', 'SCallCC', 'SApp')+-- are intercepted in the evaluator before entering generic dissection.+data SchemeF r+ = SLit !Int32+ -- ^ 32-bit signed integer literal constant.+ | SBool !Bool+ -- ^ Boolean literal constant (@#t@ or @#f@).+ | SVar !Int+ -- ^ Lexical variable reference indexed by De Bruijn offset into 'SchemeEnv'.+ | SLam !Int !r+ -- ^ Lambda abstraction with arity and body term.+ | SLet !r !r+ -- ^ Let binding @(let ((x rhs)) body)@ desugared to immediate 1-argument application.+ | SSet !Int !r+ -- ^ Mutable lexical assignment @(set! var rhs)@ mutating the 'SoAStore' cell in place.+ | SIf !r !r !r+ -- ^ Short-circuiting conditional expression @(if cond thenBranch elseBranch)@.+ | SCallCC !r+ -- ^ First-class continuation reification @(call/cc (lambda (k) ...))@.+ | SApp !r ![r]+ -- ^ Multi-argument function or continuation application @(fn arg0 arg1 ...)@.+ | SAdd !r !r+ -- ^ Pure primitive addition @(+ a b)@.+ | SSub !r !r+ -- ^ Pure primitive subtraction @(- a b)@.+ | SMul !r !r+ -- ^ Pure primitive multiplication @(* a b)@.+ | SEq !r !r+ -- ^ Pure primitive equality comparison @(= a b)@.+ | SSeq !r !r+ -- ^ Sequencing expression @(begin e1 e2)@.+ deriving stock (Show, Functor, Generic1)+ deriving anyclass (Dissectable)++-- | Closed syntax tree for the Scheme calculus.+type SchemeTerm = Fix SchemeF++-- | Lexical environment mapping De Bruijn indices to mutable 'SoAStore' cell addresses.+newtype SchemeEnv = SchemeEnv (SmallArray Int32)++-- | Runtime values of the Scheme abstract machine.+--+-- Note that 'VCont' holds an O(1) copy-on-write snapshot of the 32-frame SoA 'KontStack'.+data SchemeVal s+ = VInt !Int32+ -- ^ Evaluated integer value.+ | VBool !Bool+ -- ^ Evaluated boolean truth value.+ | VUnit+ -- ^ Evaluated unit value returned by side-effecting operations like @set!@.+ | VClosure !Int !SchemeTerm !SchemeEnv+ -- ^ Lexical closure capturing arity, AST body, and captured environment.+ | VCont !(CapturedKont s)+ -- ^ First-class captured continuation snapshot supporting multi-shot resumption.++-- | Terminal outcome or error condition for a fuel-bounded Scheme evaluation.+data SchemeError+ = ErrOutOfFuel+ -- ^ Evaluation step counter reached zero before termination.+ | ErrTypeError !String+ -- ^ Value type did not match expected operator signature.+ | ErrArityMismatch !Int !Int+ -- ^ Actual argument count did not match procedure arity.+ | ErrUnboundVar !Int+ -- ^ Variable De Bruijn index exceeded current lexical environment depth.+ deriving stock (Eq, Show)++-- | Custom continuation frame tags for Scheme special forms in 'KontStack'.+pattern FT_SchemeIf :: FrameTag+pattern FT_SchemeIf = FrameTag 40++-- | Frame tag for pending assignment to a variable cell address.+pattern FT_SchemeSet :: FrameTag+pattern FT_SchemeSet = FrameTag 41++-- | Frame tag for evaluating the receiver of @call/cc@.+pattern FT_SchemeCallCC :: FrameTag+pattern FT_SchemeCallCC = FrameTag 42++-- | Frame tag for evaluating a function term before its arguments.+pattern FT_SchemeAppFn :: FrameTag+pattern FT_SchemeAppFn = FrameTag 43++-- | Frame tag for evaluating an argument list spine left-to-right.+pattern FT_SchemeAppArgs :: FrameTag+pattern FT_SchemeAppArgs = FrameTag 44++-- | Allocate a mutable value cell in 'SoAStore' and return its 'Int32' address.+{-# INLINE allocSchemeVal #-}+allocSchemeVal :: SoAStore s -> SchemeVal s -> ST s Int32+allocSchemeVal store !val = do+ (!addr, StoreChunk{..}, !slot) <- acquireSlot store+ writeByteArray scUnboxed slot (unCellTag CT_WRecord)+ writeSmallArray scPtrA slot (unsafeCoerce# val)+ pure addr++-- | Read a 'SchemeVal' from a mutable 'SoAStore' cell address in O(1) time.+{-# INLINE readSchemeVal #-}+readSchemeVal :: SoAStore s -> Int32 -> ST s (SchemeVal s)+readSchemeVal SoAStore{..} !addr = do+ let !ix = fromIntegral addr :: Int+ !slot = ix .&. 0xFFF+ StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)+ unsafeCoerce# <$> readSmallArray scPtrA slot++-- | Mutate an existing 'SoAStore' cell in place (implementing Scheme @set!@).+{-# INLINE writeSchemeVal #-}+writeSchemeVal :: SoAStore s -> Int32 -> SchemeVal s -> ST s ()+writeSchemeVal SoAStore{..} !addr !val = do+ let !ix = fromIntegral addr :: Int+ !slot = ix .&. 0xFFF+ StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)+ writeSmallArray scPtrA slot (unsafeCoerce# val)++-- | Extend a lexical environment with a list of freshly allocated argument addresses.+extendSchemeEnv :: [Int32] -> SchemeEnv -> SchemeEnv+extendSchemeEnv newAddrs (SchemeEnv oldArr) =+ let !n = sizeofSmallArray oldArr+ !oldList = [indexSmallArray oldArr i | i <- [0 .. n - 1]]+ in SchemeEnv (smallArrayFromList (newAddrs ++ oldList))++-- | Safe index helper for 'SchemeEnv'.+lookupSchemeEnv :: SchemeEnv -> Int -> Maybe Int32+lookupSchemeEnv (SchemeEnv arr) !ix =+ let !n = sizeofSmallArray arr+ in if ix >= 0 && ix < n+ then Just (indexSmallArray arr ix)+ else Nothing++-- | Reduce a fully dissected pure syntax node (all children evaluated to 'SchemeVal').+reducePureScheme :: SchemeF (SchemeVal s) -> Either SchemeError (SchemeVal s)+reducePureScheme = \case+ SLit n -> Right (VInt n)+ SBool b -> Right (VBool b)+ SAdd (VInt a) (VInt b) -> Right (VInt (a + b))+ SSub (VInt a) (VInt b) -> Right (VInt (a - b))+ SMul (VInt a) (VInt b) -> Right (VInt (a * b))+ SEq (VInt a) (VInt b) -> Right (VBool (a == b))+ SEq (VBool a) (VBool b) -> Right (VBool (a == b))+ SSeq _v1 v2 -> Right v2+ _ -> Left (ErrTypeError "Scheme: invalid operand types in primitive operation")++-- | Run a fuel-bounded Call-by-Value Scheme evaluation using 'KontStack' and 'SoAStore'.+--+-- Returns the terminal integer or boolean result (or 'SchemeError' on fuel exhaustion).+evalScheme :: Int -> SchemeTerm -> Either SchemeError (Either Bool Int32)+evalScheme !initialFuel rootTerm = runST $ do+ store <- newSoAStore+ kont <- newKontStack+ let emptyEnv = SchemeEnv (smallArrayFromList [])+ evalLoop store kont initialFuel rootTerm emptyEnv+ where+ -- Phase 1: Downward syntax traversal (Eval)+ evalLoop+ :: SoAStore s+ -> KontStack s+ -> Int+ -> SchemeTerm+ -> SchemeEnv+ -> ST s (Either SchemeError (Either Bool Int32))+ evalLoop !store !kont !fuel (In node) !env+ | fuel <= 0 = pure (Left ErrOutOfFuel)+ | otherwise = case node of+ -- 1. Variable lookup from SoAStore+ SVar ix -> case lookupSchemeEnv env ix of+ Nothing -> pure (Left (ErrUnboundVar ix))+ Just addr -> do+ val <- readSchemeVal store addr+ applyLoop store kont (fuel - 1) val++ -- 2. Lambda abstraction produces a closure immediately+ SLam arity body ->+ applyLoop store kont (fuel - 1) (VClosure arity body env)++ -- 3. Let binding: evaluate rhs, then bind in body (desugared as 1-arg app)+ SLet rhs body -> do+ pushFrameSoA kont FT_SchemeAppFn 0 0+ (unsafeCoerce# (VClosure 1 body env))+ (unsafeCoerce# ([] :: [SchemeTerm], [] :: [SchemeVal s], env))+ evalLoop store kont (fuel - 1) rhs env++ -- 4. Lexical mutation (set! ix rhs)+ SSet ix rhs -> case lookupSchemeEnv env ix of+ Nothing -> pure (Left (ErrUnboundVar ix))+ Just addr -> do+ pushFrameSoA kont FT_SchemeSet addr 0+ (unsafeCoerce# ()) (unsafeCoerce# ())+ evalLoop store kont (fuel - 1) rhs env++ -- 5. Short-circuiting conditional (if cond thenBranch elseBranch)+ SIf condT thenT elseT -> do+ pushFrameSoA kont FT_SchemeIf 0 0+ (unsafeCoerce# (thenT, elseT))+ (unsafeCoerce# env)+ evalLoop store kont (fuel - 1) condT env++ -- 6. First-class continuation capture (call/cc receiver)+ SCallCC receiverTerm -> do+ pushFrameSoA kont FT_SchemeCallCC 0 0+ (unsafeCoerce# env) (unsafeCoerce# ())+ evalLoop store kont (fuel - 1) receiverTerm env++ -- 7. Multi-argument function or continuation application+ SApp fnTerm argTerms -> do+ pushFrameSoA kont FT_SchemeAppArgs 0 0+ (unsafeCoerce# argTerms)+ (unsafeCoerce# env)+ evalLoop store kont (fuel - 1) fnTerm env++ -- 8. All other pure syntax nodes: delegate to Generic1 McBride Dissection!+ _ -> case stepIn node of+ Left valNode -> case reducePureScheme valNode of+ Left err -> pure (Left err)+ Right val -> applyLoop store kont (fuel - 1) val+ Right (firstChild, dissected) -> do+ pushFrameSoA kont FT_PureDissect 0 0+ (unsafeCoerce# dissected)+ (unsafeCoerce# env)+ evalLoop store kont (fuel - 1) firstChild env++ -- Phase 2: Upward continuation application (Apply)+ applyLoop+ :: SoAStore s+ -> KontStack s+ -> Int+ -> SchemeVal s+ -> ST s (Either SchemeError (Either Bool Int32))+ applyLoop !store !kont !fuel !val+ | fuel <= 0 = pure (Left ErrOutOfFuel)+ | otherwise = do+ mbFrame <- popFrameSoA kont+ case mbFrame of+ Nothing -> case val of+ VInt n -> pure (Right (Right n))+ VBool b -> pure (Right (Left b))+ _ -> pure (Left (ErrTypeError "Scheme: non-primitive root result"))++ Just (ft, intA, _intB, ptrA, ptrB)+ -- Generic McBride Dissection frame: plug Clown 'val' and step to next Joker!+ | ft == FT_PureDissect -> do+ let !dis = unsafeCoerce# ptrA :: Dissect SchemeF (SchemeVal s) SchemeTerm+ !env = unsafeCoerce# ptrB :: SchemeEnv+ case stepNext val dis of+ Left completedNode -> case reducePureScheme completedNode of+ Left err -> pure (Left err)+ Right val' -> applyLoop store kont (fuel - 1) val'+ Right (nextTerm, dis') -> do+ pushFrameSoA kont FT_PureDissect 0 0+ (unsafeCoerce# dis')+ (unsafeCoerce# env)+ evalLoop store kont (fuel - 1) nextTerm env++ -- Conditional branch selection+ | ft == FT_SchemeIf -> do+ let (!thenT, !elseT) = unsafeCoerce# ptrA :: (SchemeTerm, SchemeTerm)+ !env = unsafeCoerce# ptrB :: SchemeEnv+ case val of+ VBool False -> evalLoop store kont (fuel - 1) elseT env+ _ -> evalLoop store kont (fuel - 1) thenT env++ -- In-place SoAStore variable mutation (set!)+ | ft == FT_SchemeSet -> do+ writeSchemeVal store intA val+ applyLoop store kont (fuel - 1) VUnit++ -- call/cc: capture O(1) CoW KontStack and invoke receiver closure+ | ft == FT_SchemeCallCC -> do+ captured <- captureKontSoA kont+ invokeTarget store kont (fuel - 1) val [VCont captured]++ -- Function evaluated; now evaluate argument spine left-to-right+ | ft == FT_SchemeAppArgs -> do+ let !argTerms = unsafeCoerce# ptrA :: [SchemeTerm]+ !env = unsafeCoerce# ptrB :: SchemeEnv+ case argTerms of+ [] -> invokeTarget store kont (fuel - 1) val []+ (a0 : rest) -> do+ pushFrameSoA kont FT_SchemeAppFn 0 0+ (unsafeCoerce# val)+ (unsafeCoerce# (rest, [] :: [SchemeVal s], env))+ evalLoop store kont (fuel - 1) a0 env++ -- Evaluating argument list spine+ | ft == FT_SchemeAppFn -> do+ let !fnVal = unsafeCoerce# ptrA :: SchemeVal s+ (!remArgs, !accVals, !env) =+ unsafeCoerce# ptrB :: ([SchemeTerm], [SchemeVal s], SchemeEnv)+ !accVals' = val : accVals+ case remArgs of+ [] -> invokeTarget store kont (fuel - 1) fnVal (reverse accVals')+ (nextArg : moreArgs) -> do+ pushFrameSoA kont FT_SchemeAppFn 0 0+ (unsafeCoerce# fnVal)+ (unsafeCoerce# (moreArgs, accVals', env))+ evalLoop store kont (fuel - 1) nextArg env++ | otherwise ->+ pure (Left (ErrTypeError "Scheme: unknown continuation frame tag"))++ -- Invoke either a lexical closure or a first-class captured continuation:+ invokeTarget+ :: SoAStore s+ -> KontStack s+ -> Int+ -> SchemeVal s+ -> [SchemeVal s]+ -> ST s (Either SchemeError (Either Bool Int32))+ invokeTarget !store !kont !fuel !target !args = case target of+ VClosure arity body cEnv+ | length args /= arity ->+ pure (Left (ErrArityMismatch arity (length args)))+ | otherwise -> do+ argAddrs <- mapM (allocSchemeVal store) args+ evalLoop store kont (fuel - 1) body (extendSchemeEnv argAddrs cEnv)++ VCont captured -> case args of+ [retVal] -> do+ -- O(1) restoration of the captured 32-frame SoA KontStack!+ restoreKontSoA kont captured+ applyLoop store kont (fuel - 1) retVal+ _ -> pure (Left (ErrArityMismatch 1 (length args)))++ _ -> pure (Left (ErrTypeError "Scheme: attempt to call non-procedure"))
+ test/Main.hs view
@@ -0,0 +1,44 @@+{-# LANGUAGE OverloadedStrings #-}++-- |+-- Module : Main+-- Description : Unit test suite for Cek.Scheme+-- Copyright : (c) Nadia Yvette Chambers, 2026+-- License : EUPL-1.2+module Main (main) where++import Data.Int (Int32)+import Test.Hspec++import Cek.Scheme++main :: IO ()+main = hspec $ do+ describe "Cek.Scheme (Call-by-Value with Generic1 Dissection & call/cc)" $ do+ it "evaluates arithmetic expressions via automatic Generic1 Dissection" $ do+ -- (10 + 20) * 2 = 60+ let term = In (SMul (In (SAdd (In (SLit 10)) (In (SLit 20)))) (In (SLit 2)))+ evalScheme 100 term `shouldBe` Right (Right (60 :: Int32))++ it "evaluates conditional branches" $ do+ -- if True then 42 else 0+ let term = In (SIf (In (SBool True)) (In (SLit 42)) (In (SLit 0)))+ evalScheme 100 term `shouldBe` Right (Right (42 :: Int32))++ it "evaluates lambda abstraction and application" $ do+ -- (\x -> x + 5) 10 = 15+ let lam = In (SLam 1 (In (SAdd (In (SVar 0)) (In (SLit 5)))))+ term = In (SApp lam [In (SLit 10)])+ evalScheme 100 term `shouldBe` Right (Right (15 :: Int32))++ it "supports early-exit call/cc escaping from deep inside addition" $ do+ -- 100 + (call/cc (\k -> 10 + k 42)) = 142+ let receiver = In (SLam 1 (In (SAdd (In (SLit 10)) (In (SApp (In (SVar 0)) [In (SLit 42)])))))+ term = In (SAdd (In (SLit 100)) (In (SCallCC receiver)))+ evalScheme 100 term `shouldBe` Right (Right (142 :: Int32))++ it "supports mutable lexical variables via set!" $ do+ -- let x = 10 in (set! 0 25 ; x) = 25+ let body = In (SSeq (In (SSet 0 (In (SLit 25)))) (In (SVar 0)))+ term = In (SLet (In (SLit 10)) body)+ evalScheme 100 term `shouldBe` Right (Right (25 :: Int32))