cek-oneml-0.1.0.2: src/Cek/OneML.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}
-- |
-- Module : Cek.Examples.OneML
-- Description : Rossberg 1ML first-class module evaluator with MergeMorph3 existential sealing.
--
-- Models 1ML structures and signatures as flat 'SchemaId'-indexed arrays of lazy
-- 'SoAStore' addresses, using 'MergeMorph3' for module @include@ ('OpPreferR')
-- and existential sealing @Mod :> Sig@ ('OpRestrict').
--
-- === Background: Rossberg's 1ML
--
-- Andreas Rossberg's /"1ML — Core and the Modules in the Same Language"/ (ICFP 2015)
-- showed that the traditional stratified distinction between ML core expressions
-- and ML modules (structures, signatures, functors) can be completely dissolved.
-- Modules become first-class records, functors become ordinary functions, and
-- signatures become first-class record types with existential components.
--
-- === Efficient Interpretation with MergeMorph3
--
-- Traditional implementations of 1ML require heavy elaborators that translate
-- module constructs into System \(F_\omega\) terms with dynamic dictionary passing.
-- This CEK machine implementation executes 1ML directly on flat unboxed structures:
--
-- 1. Structures and signatures are flat arrays of lazy cells indexed by 'FieldId'
-- and mapped to structural 'SchemaId' identifiers in 'Pykinos.Schema.HiddenClass'.
-- 2. Module extension (@include M@) compiles into a single $O(N_1 + N_2)$ linear
-- merge plan ('OpPreferR') via 'synthesizeMergeMorph3'.
-- 3. Existential sealing (@Mod :> Sig@) computes a domain restriction ('OpRestrict')
-- in $O(|Sig|)$ time. For every abstract type field ('SpecAbstract'), the evaluator
-- mints a fresh, globally unique skolem constant ('CT_WNeu') in 'SoAStore',
-- hiding the concrete implementation without dynamic wrapper closures.
--
-- > **Demonstrative Reference Implementation**: This package is an educational
-- > and demonstrative reference implementation showcasing Andreas Rossberg's 1ML
-- > first-class module system over the CEK abstract machine with MergeMorph3
-- > existential sealing and Pykinos hidden classes. It is provided primarily as an
-- > executable architectural example within the @cek@ ecosystem documentation.
--
module Cek.OneML
( -- * Type Specifications
TypeSpec(..)
-- * 1ML Syntax
, OneMLTerm(..)
-- * Values and Weak-Head Normal Forms
, OneMLWHNF(..)
-- * Continuation Frame Tags
, pattern FT_1ML_App
, pattern FT_1ML_Proj
, pattern FT_1ML_IncludeL
, pattern FT_1ML_IncludeR
, pattern FT_1ML_SealSig
, pattern FT_1ML_SealMod
-- * Sealing and Evaluation
, stepOneMLSealing
, evalOneML
) 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.PrimArray
( PrimArray
, indexPrimArray
, sizeofPrimArray
)
import Data.Primitive.SmallArray
( SmallArray
, indexSmallArray
, readSmallArray
, sizeofSmallArray
, smallArrayFromList
, writeSmallArray
)
import Data.Word (Word32)
import GHC.Exts (unsafeCoerce#)
import Cek.Pykinos.Kont
( FrameTag(..)
, newKontStack
, pattern FT_UpdateWHNF
, popFrameSoA
, pushFrameSoA
)
import Cek.Pykinos.Store
( CellTag(..)
, SoAStore(..)
, StoreChunk(..)
, allocThunkSoA
, allocWNeuSoA
, newSoAStore
, pattern CT_Thunk
, pattern CT_WBinder
, pattern CT_WLit
, pattern CT_WNeu
, pattern CT_WRecord
, readCellPhaseSoA
, unCellTag
)
import Pykinos.Schema.HiddenClass
( FieldId(..)
, MergeMorph3(..)
, RecordOp(..)
, SchemaId(..)
, decodeMergeCode3
, findFieldSlot
, synthesizeMergeMorph3
)
-- | Frame tag for evaluating a functor argument cell.
pattern FT_1ML_App :: FrameTag
pattern FT_1ML_App = FrameTag 30
-- | Frame tag for projecting a field from an evaluated module structure.
pattern FT_1ML_Proj :: FrameTag
pattern FT_1ML_Proj = FrameTag 31
-- | Frame tag for evaluating the left-hand module in an @include@ (@//@) expression.
pattern FT_1ML_IncludeL :: FrameTag
pattern FT_1ML_IncludeL = FrameTag 32
-- | Frame tag for evaluating the right-hand module in an @include@ (@//@) expression.
pattern FT_1ML_IncludeR :: FrameTag
pattern FT_1ML_IncludeR = FrameTag 33
-- | Frame tag for evaluating the signature expression in existential sealing.
pattern FT_1ML_SealSig :: FrameTag
pattern FT_1ML_SealSig = FrameTag 34
-- | Frame tag for applying signature restriction and skolemization to the module structure.
pattern FT_1ML_SealMod :: FrameTag
pattern FT_1ML_SealMod = FrameTag 35
-- | Type specifications inside a 1ML signature structure.
data TypeSpec
= SpecAbstract
-- ^ Opaque abstract type field (@type t@): generates a fresh skolem 'CT_WNeu'.
| SpecManifest !OneMLTerm
-- ^ Transparent type alias (@type t = tau@): preserves the underlying type cell.
| SpecVal !OneMLTerm
-- ^ Value field specification (@val x : tau@): preserves the lazy value thunk.
deriving (Eq, Show)
-- | Unified 1ML Core and Module AST.
data OneMLTerm
= MVar !Int
-- ^ Variable reference resolved via De Bruijn indexing into the environment.
| MLit !Int32
-- ^ 32-bit signed integer literal value.
| MReified !TypeSpec
-- ^ Reified first-class type specification treated as a value.
| MFunctor !OneMLTerm !OneMLTerm
-- ^ First-class functor / function abstraction taking a domain signature and body.
| MApp !OneMLTerm !OneMLTerm
-- ^ Application of a functor to a module argument.
| MLet !OneMLTerm !OneMLTerm
-- ^ Lexical let binding introducing a local module or value definition.
| MStruct !SchemaId !(SmallArray OneMLTerm)
-- ^ First-class module structure pairing an interned 'SchemaId' with component terms.
| MProj !OneMLTerm !FieldId
-- ^ Structure projection @M.x@ retrieving the field labeled by 'FieldId'.
| MInclude !OneMLTerm !OneMLTerm
-- ^ Asymmetric module inclusion / union @include M1 in M2@ using 'OpPreferR'.
| MSeal !OneMLTerm !OneMLTerm
-- ^ Existential signature sealing @M :> S@ using 'OpRestrict' and skolem generation.
deriving (Eq, Show)
-- | Weak-Head Normal Form representation for 1ML values and modules.
data OneMLWHNF
= V1Lit !Int32
-- ^ Unboxed integer literal value.
| V1Spec !TypeSpec ![Int32]
-- ^ Evaluated type specification closure.
| V1Functor !Int32 !OneMLTerm ![Int32]
-- ^ Evaluated functor closure capturing parameter domain address, body, and env.
| V1Struct !SchemaId !(SmallArray Int32)
-- ^ Evaluated structure pairing a 'SchemaId' with an array of lazy store addresses.
| V1AbstractType !Int32
-- ^ Opaque existential skolem type constant generated during signature sealing.
deriving (Eq, Show)
-- | Execute 1ML existential sealing (@Mod :> Sig@) in O(|Sig|) using 'MergeMorph3'
-- with 'OpRestrict'. Private fields omitted from 'Sig' are never forced, while
-- 'SpecAbstract' fields mint fresh skolem symbols in 'SoAStore'.
stepOneMLSealing
:: SoAStore s
-> MutableByteArray s
-> MergeMorph3
-> SchemaId
-> SmallArray Int32
-> SmallArray Int32
-> ST s OneMLWHNF
stepOneMLSealing store symCounter (MergeMorph3 !restrictPlan) !sigSchema !modAddrs !sigAddrs = do
let !nOut = sizeofPrimArray restrictPlan
sealedAddrs <- mapM (\i -> do
let !code = indexPrimArray restrictPlan i
!modSlot = case decodeMergeCode3 code of
Left (Left idx1) -> idx1
_ -> error "OneML: invalid OpRestrict code"
!modAddr = indexSmallArray modAddrs modSlot
!sigAddr = indexSmallArray sigAddrs i
(!sigTag, !_aux, !sigChk, !sigSlot) <- readCellPhaseSoA store sigAddr
if sigTag == CT_WBinder
then do
spec :: TypeSpec <- unsafeCoerce# <$> readSmallArray (scPtrA sigChk) sigSlot
case spec of
SpecAbstract -> do
sym :: Int32 <- readByteArray symCounter 0
writeByteArray symCounter 0 (sym + 1)
allocWNeuSoA store sym
SpecManifest _ -> pure modAddr
SpecVal _ -> pure modAddr
else pure modAddr
) [0 .. nOut - 1]
pure (V1Struct sigSchema (smallArrayFromList sealedAddrs))
-- | Store a computed 'OneMLWHNF' into an existing 'SoAStore' cell address.
writeOneMLWHNF :: SoAStore s -> Int32 -> OneMLWHNF -> ST s ()
writeOneMLWHNF SoAStore{..} !addr !whnf = do
let !ix = fromIntegral addr :: Int
!slot = ix .&. 0xFFF
StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
case whnf of
V1Lit n -> do
writeByteArray scUnboxed slot (unCellTag CT_WLit)
writeByteArray scUnboxed (5120 + slot) n
V1AbstractType sym -> do
writeByteArray scUnboxed slot (unCellTag CT_WNeu)
writeByteArray scUnboxed (5120 + slot) sym
V1Spec spec env -> do
writeByteArray scUnboxed slot (unCellTag CT_WBinder)
writeSmallArray scPtrA slot (unsafeCoerce# spec)
writeSmallArray scPtrB slot (unsafeCoerce# env)
V1Functor domAddr body env -> do
writeByteArray scUnboxed slot (unCellTag CT_WBinder)
writeByteArray scUnboxed (5120 + slot) domAddr
writeSmallArray scPtrA slot (unsafeCoerce# body)
writeSmallArray scPtrB slot (unsafeCoerce# env)
V1Struct (SchemaId sid) addrs -> do
writeByteArray scUnboxed slot (unCellTag CT_WRecord)
writeByteArray scUnboxed (5120 + slot) (fromIntegral sid :: Int32)
writeSmallArray scPtrA slot (unsafeCoerce# addrs)
-- | Evaluate a closed 1ML expression given a schema lookup table mapping
-- 'SchemaId' to its sorted 'PrimArray Word32' field descriptor.
evalOneML
:: (SchemaId -> PrimArray Word32)
-> (PrimArray Word32 -> SchemaId)
-> OneMLTerm
-> OneMLWHNF
evalOneML lookupSchema internSchema rootTerm = runST $ do
store <- newSoAStore
kont <- newKontStack
symCounter <- newByteArray 4
writeByteArray symCounter 0 (0 :: Int32)
let evalTerm !term !env = case term of
MVar ix -> evalAddr (env !! ix)
MLit n -> applyWHNF (V1Lit n)
MReified spec -> applyWHNF (V1Spec spec env)
MFunctor dom body -> do
domAddr <- allocThunkSoA store dom env
applyWHNF (V1Functor domAddr body env)
MLet e1 e2 -> do
a1 <- allocThunkSoA store e1 env
evalTerm e2 (a1 : env)
MApp fn arg -> do
argAddr <- allocThunkSoA store arg env
pushFrameSoA kont FT_1ML_App argAddr 0 (unsafeCoerce# ()) (unsafeCoerce# ())
evalTerm fn env
MStruct sid terms -> do
let !n = sizeofSmallArray terms
addrs <- mapM (\i -> allocThunkSoA store (indexSmallArray terms i) env) [0 .. n - 1]
applyWHNF (V1Struct sid (smallArrayFromList addrs))
MProj modT (FieldId fid) -> do
pushFrameSoA kont FT_1ML_Proj (fromIntegral fid) 0 (unsafeCoerce# ()) (unsafeCoerce# ())
evalTerm modT env
MInclude m1 m2 -> do
a1 <- allocThunkSoA store m1 env
pushFrameSoA kont FT_1ML_IncludeL a1 0 (unsafeCoerce# ()) (unsafeCoerce# ())
evalTerm m2 env
MSeal modT sigT -> do
modAddr <- allocThunkSoA store modT env
pushFrameSoA kont FT_1ML_SealSig modAddr 0 (unsafeCoerce# ()) (unsafeCoerce# ())
evalTerm sigT env
evalAddr !addr = do
(!tag, !aux, !chk, !slot) <- readCellPhaseSoA store addr
case tag of
CT_Thunk -> do
t :: OneMLTerm <- unsafeCoerce# <$> readSmallArray (scPtrA chk) slot
env :: [Int32] <- unsafeCoerce# <$> readSmallArray (scPtrB chk) slot
pushFrameSoA kont FT_UpdateWHNF addr 0 (unsafeCoerce# ()) (unsafeCoerce# ())
evalTerm t env
CT_WLit -> applyWHNF (V1Lit aux)
CT_WNeu -> applyWHNF (V1AbstractType aux)
CT_WRecord -> do
addrs :: SmallArray Int32 <- unsafeCoerce# <$> readSmallArray (scPtrA chk) slot
applyWHNF (V1Struct (SchemaId (fromIntegral aux)) addrs)
CT_WBinder -> do
pA <- readSmallArray (scPtrA chk) slot
pB <- readSmallArray (scPtrB chk) slot
if aux == 0
then applyWHNF (V1Spec (unsafeCoerce# pA) (unsafeCoerce# pB))
else applyWHNF (V1Functor aux (unsafeCoerce# pA) (unsafeCoerce# pB))
_ -> error "OneML: invalid cell phase"
applyWHNF !whnf = do
mbFrame <- popFrameSoA kont
case mbFrame of
Nothing -> pure whnf
Just (ft, intA, _intB, ptrA, _ptrB)
| ft == FT_UpdateWHNF -> do
writeOneMLWHNF store intA whnf
applyWHNF whnf
| ft == FT_1ML_App -> case whnf of
V1Functor _dom body env ->
evalTerm body (intA : env)
_ -> error "OneML: non-functor in MApp"
| ft == FT_1ML_Proj -> case whnf of
V1Struct sid addrs ->
let !fids = lookupSchema sid
!fid = FieldId (fromIntegral intA)
in case findFieldSlot fids fid of
Just slotIx -> evalAddr (indexSmallArray addrs slotIx)
Nothing -> error "OneML: missing field in MProj"
_ -> error "OneML: non-struct in MProj"
| ft == FT_1ML_IncludeL -> do
pushFrameSoA kont FT_1ML_IncludeR 0 0 (unsafeCoerce# whnf) (unsafeCoerce# ())
evalAddr intA
| ft == FT_1ML_IncludeR -> do
let !rhsWHNF = unsafeCoerce# ptrA :: OneMLWHNF
case (whnf, rhsWHNF) of
(V1Struct sid1 addrs1, V1Struct sid2 addrs2) -> do
let (!fOut, MergeMorph3 !plan) =
synthesizeMergeMorph3 OpPreferR (lookupSchema sid1) (lookupSchema sid2)
!sidOut = internSchema fOut
!nOut = sizeofPrimArray plan
!outArr = smallArrayFromList
[ case decodeMergeCode3 (indexPrimArray plan i) of
Left (Left idx1) -> indexSmallArray addrs1 idx1
Left (Right idx2) -> indexSmallArray addrs2 idx2
_ -> error "OneML: impossible collision in OpPreferR"
| i <- [0 .. nOut - 1]
]
applyWHNF (V1Struct sidOut outArr)
_ -> error "OneML: non-struct in MInclude"
| ft == FT_1ML_SealSig -> case whnf of
V1Struct (SchemaId sigSid) sigAddrs -> do
-- Evaluate the signature's TypeSpec cells to WHNF so stepOneMLSealing can inspect them:
let forceSpecs !i
| i >= sizeofSmallArray sigAddrs = pure ()
| otherwise = do
let !sAddr = indexSmallArray sigAddrs i
(!sTag, _, !sChk, !sSlot) <- readCellPhaseSoA store sAddr
when (sTag == CT_Thunk) $ do
sTerm :: OneMLTerm <- unsafeCoerce# <$> readSmallArray (scPtrA sChk) sSlot
sEnv :: [Int32] <- unsafeCoerce# <$> readSmallArray (scPtrB sChk) sSlot
case sTerm of
MReified sp -> writeOneMLWHNF store sAddr (V1Spec sp sEnv)
_ -> pure ()
forceSpecs (i + 1)
forceSpecs 0
pushFrameSoA kont FT_1ML_SealMod (fromIntegral sigSid) 0
(unsafeCoerce# sigAddrs) (unsafeCoerce# ())
evalAddr intA
_ -> error "OneML: non-signature struct in MSeal"
| ft == FT_1ML_SealMod -> case whnf of
V1Struct modSchema modAddrs -> do
let !sigSchema = SchemaId (fromIntegral intA)
!sigAddrs = unsafeCoerce# ptrA :: SmallArray Int32
(!_fOut, !restrictMorph) =
synthesizeMergeMorph3 OpRestrict (lookupSchema modSchema) (lookupSchema sigSchema)
sealed <- stepOneMLSealing store symCounter restrictMorph sigSchema modAddrs sigAddrs
applyWHNF sealed
_ -> error "OneML: non-module struct in MSeal"
| otherwise -> error "OneML: unknown continuation frame"
evalTerm rootTerm []