phino-0.0.166: src/Morph.hs
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DuplicateRecordFields #-}
{-# LANGUAGE OverloadedRecordDot #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TupleSections #-}
{-# OPTIONS_GHC -Wno-name-shadowing #-}
{-# OPTIONS_GHC -Wno-unused-record-wildcards #-}
-- SPDX-FileCopyrightText: Copyright (c) 2025 Objectionary.com
-- SPDX-License-Identifier: MIT
module Morph (Answer (..), Budget (..), Deadline (..), Firing (..), Facts, Kept (..), ReduceContext (..), ReduceException (..), EvaluationFunc, Memo (..), Kindred, ReductionFunc, adopted, kindle, kindred, minting, placed, Morphed, Steps (..), Tally (..), admitting, argued, awaited, called, carried, charged, coined, counted, declared, deeper, emptyState, ended, enter, execBuildTerm, expired, fired, inferred, insideUniverse, isLambda, lambda, leadsTo, factual, memoized, morph, noted, remembering, morph', morphing, normalized, onward, opening, parking, recalled, refused, remember, remembered, repeats, retained, settled, severing, starved, tallied, timed, universed, unparked, vetted, voided) where
import AST
import Builder (buildExpressionThrows, nameIn)
import Control.Applicative ((<|>))
import Control.Exception (Exception, catch, evaluate, throwIO, try)
import Control.Monad (forM_, guard, unless, when)
import Data.Bifunctor (first, second)
import Data.Either (lefts)
import Data.IORef (IORef, atomicModifyIORef', modifyIORef', newIORef, readIORef, writeIORef)
import Data.List (find, partition, sortOn)
import qualified Data.List as List
import Data.List.NonEmpty (NonEmpty (..))
import qualified Data.List.NonEmpty as NE
import qualified Data.Map.Strict as Map
import Data.Maybe (fromMaybe, isJust, listToMaybe, maybeToList)
import qualified Data.Set as Set
import qualified Data.Text as T
import Deps (Acyclic (..), BuildTermFunc, BuildTermMethod, Evaluation (..), Judgment (..), SaveEvalFunc, SaveStepFunc, State (..), Term (..), dispatched, dontSaveStep, sized)
import Engine (Engine (..))
import GHC.Clock (getMonotonicTime)
import GHC.Stats (GCDetails (..), RTSStats (..), getRTSStats, getRTSStatsEnabled)
import qualified Inference as In
import Lambdas (Lambdas, stayed, thrown)
import Locator (locatedExpression, withLocatedExpression)
import Matcher (substEmpty)
import Must (Must (..))
import Printer (printExpression)
import Random (shuffle)
import Rewriter (RewriteContext (RewriteContext), Rewritten, Seen, rewrite, seenInsert)
import Rule (RuleContext (RuleContext), xiFree)
import Sides (Sides, minted, named, opened, resolver, spelled)
import System.Timeout (timeout)
import Text.Printf (printf)
import Yaml (ExtraArgument (..))
type Morphed = (Expression, NonEmpty Rewritten)
type ReductionFunc = Expression -> ReduceContext -> Expression -> State -> IO (Maybe Bytes, State)
type EvaluationFunc = ReduceContext -> State -> Expression -> Expression -> IO (Expression, State)
emptyState :: State
emptyState = State Nothing Nothing []
data Steps = Steps
{ _limit :: Int
, _spent :: Int
}
data Tally = Tally
{ _ceiling :: Int
, _count :: IORef Int
}
data Deadline = Deadline
{ _seconds :: Int
, _until :: Double
}
data Memo = Memo (IORef (Store (Int, Kept))) (IORef (Map.Map Firing (Expression, Answer))) (IORef Int) (IORef Int) Kin
data Kin = Kin (IORef Spots) (IORef (Map.Map Int [Kindred])) (IORef (Map.Map Int Firing))
data Spots = Spots (Store Int) (Map.Map Int Expression)
data Kindred = Kindred Expression Expression Firing Answer
data Renaming = Renaming (IORef (Map.Map Int Int)) Spots (IORef (Set.Set Firing))
data Answer
= Answer Expression Expression
| Joined Expression
| Raised
ended :: Answer -> Expression
ended (Answer _ normal) = normal
ended (Joined normal) = normal
ended Raised = ExTermination
data Firing = Firing T.Text [Either Int Bytes] [Expression]
deriving (Eq, Ord)
data Kept
= Answered Answer
| Looped Expression
| Stalled T.Text Int
type Store answer = Map.Map Int [(Expression, answer)]
data Facts = Facts (IORef (Store Expression)) (IORef Lodgings)
data Lodging = Lodging [(Expression, Attribute)] [(Attribute, Expression)]
data Lodgings = Lodgings !(Store Lodging) !(Map.Map Int [Expression])
data ReduceContext = ReduceContext
{ _locator :: Expression
, _site :: Expression
, _universe :: Maybe Expression
, _maxDepth :: Int
, _maxCycles :: Int
, _maxNodes :: Maybe Int
, _maxMemory :: Maybe Int
, _steps :: Steps
, _tally :: Maybe Tally
, _minted :: IORef Int
, _sides :: Sides
, _deadline :: Maybe Deadline
, _memo :: Maybe Memo
, _nesting :: Int
, _opened :: Maybe (Int, Judgment, Expression)
, _depthSensitive :: Bool
, _shuffle :: Bool
, _partial :: Bool
, _acyclic :: Maybe Acyclic
, _maxLoops :: Int
, _judgment :: Judgment
, _parked :: [T.Text]
, _entered :: Seen
, _facts :: Maybe Facts
, _symbolic :: Lambdas
, _raising :: [T.Text]
, _reckoning :: Bool
, _working :: Maybe Expression
, _buildTerm :: BuildTermFunc
, _reduce :: ReductionFunc
, _evaluate :: EvaluationFunc
, _saveStep :: SaveStepFunc
, _saveEval :: SaveEvalFunc
, _engine :: Engine
}
data Budget
= Depth Judgment Int
| Firings Int
| Cycles Int
| Nodes Int
| Memory Int
| Seconds Int
data ReduceException
= OutOfSteps Budget
| Stuck T.Text
| StuckAt T.Text (NonEmpty Rewritten) State
| OutOfStepsAt Budget (NonEmpty Rewritten) State
| Diverged T.Text
| Looping Expression
| LoopingAt Expression (NonEmpty Rewritten) State
| Undataizable Expression (NonEmpty Rewritten) State
| Unmorphable Expression
| Abnormal Judgment Expression
deriving anyclass (Exception)
instance Show ReduceException where
show (OutOfSteps (Depth judgment limit)) =
printf "%s did not finish before reaching the limit of steps: --max-steps=%d" (show judgment) limit
show (OutOfSteps (Firings limit)) =
printf "Evaluation did not finish before reaching the limit of firings: --max-firings=%d" limit
show (OutOfSteps (Cycles limit)) =
printf "Normalization did not finish before reaching the limit of cycles: --max-cycles=%d" limit
show (OutOfSteps (Nodes limit)) =
printf "Evaluation did not finish before reaching the limit of nodes: --max-nodes=%d" limit
show (OutOfSteps (Memory limit)) =
printf "Evaluation did not finish before reaching the limit of memory: --max-memory=%s" (sized limit)
show (OutOfSteps (Seconds limit)) =
printf "Evaluation did not finish before reaching the limit of seconds: --max-seconds=%d" limit
show (OutOfStepsAt budget _ _) = show (OutOfSteps budget)
show (Stuck func) = printf "No entry of --symbolic answers the λ function '%s'" (T.unpack func)
show (StuckAt func _ _) = show (Stuck func)
show (Diverged func) = printf "The λ function '%s' could not join its two sides" (T.unpack func)
show (Looping term) = printf "Reduction entered a formation it is already inside: %s" (printExpression term)
show (LoopingAt term _ _) = show (Looping term)
show (Undataizable ExTermination _ _) = "dataization reached the terminator ⊥, which signals an error and cannot be dataized"
show (Undataizable term _ _) = printf "no dataization rule matched, while dataization expects a normal form: %s" (printExpression term)
show (Unmorphable term) = printf "Morphing expects a normal form, but no morphing rule matches: %s" (printExpression term)
show (Abnormal Morphing term) = printf "Morphing expects a normal form, but the term at the locator is not one: %s" (printExpression term)
show (Abnormal _ term) = printf "Dataization expects a normal form, but the term at the locator is not one: %s" (printExpression term)
deeper :: ReduceContext -> IO ReduceContext
deeper ctx@ReduceContext{_steps = Steps limit spent} = do
clocked ctx
when (spent >= limit) $ do
starve ctx._memo
ctx._saveEval (EvStarved ctx._nesting limit ctx._judgment ctx._site)
throwIO (OutOfSteps (Depth ctx._judgment limit))
pure ctx{_steps = Steps limit (spent + 1)}
where
starve :: Maybe Memo -> IO ()
starve Nothing = pure ()
starve (Just (Memo _ _ _ exhausted _)) = modifyIORef' exhausted (+ 1)
measured :: ReduceContext -> Expression -> IO ()
measured ctx term = do
forM_ ctx._maxNodes $ \cap ->
when (countNodes term > cap) (overflown (EvOversized ctx._nesting cap ctx._judgment ctx._site) (Nodes cap))
forM_ ctx._maxMemory $ \cap -> do
enabled <- getRTSStatsEnabled
unless enabled (ioError (userError "--max-memory needs the statistics of the runtime, which this binary was linked without"))
stats <- getRTSStats
when (toInteger (gcdetails_live_bytes (gc stats)) > toInteger cap) (overflown (EvBlown ctx._nesting cap ctx._judgment ctx._site) (Memory cap))
where
overflown :: Evaluation -> Budget -> IO ()
overflown record budget = do
ctx._saveEval record
throwIO (OutOfSteps budget)
tallied :: Maybe Int -> IO (Maybe Tally)
tallied = traverse (\cap -> Tally cap <$> newIORef 0)
timed :: Maybe Int -> IO (Maybe Deadline)
timed = traverse (\cap -> Deadline cap . (+ fromIntegral cap) <$> getMonotonicTime)
charged :: ReduceContext -> IO ()
charged ctx = do
clocked ctx
mapM_ billed ctx._tally
where
billed :: Tally -> IO ()
billed (Tally cap count) = do
fired <- readIORef count
when (fired >= cap) $ do
ctx._saveEval (EvSpent ctx._nesting cap ctx._judgment ctx._site)
throwIO (OutOfSteps (Firings cap))
writeIORef count (fired + 1)
clocked :: ReduceContext -> IO ()
clocked ctx = mapM_ clock ctx._deadline
where
clock :: Deadline -> IO ()
clock (Deadline cap due) = do
now <- getMonotonicTime
when (now >= due) (expired ctx cap)
expired :: ReduceContext -> Int -> IO a
expired ctx cap = do
ctx._saveEval (EvTimeout ctx._nesting cap ctx._judgment ctx._site)
throwIO (OutOfSteps (Seconds cap))
awaited :: ReduceContext -> IO a -> IO a
awaited ctx action = case ctx._deadline of
Nothing -> action
Just (Deadline cap due) -> do
now <- getMonotonicTime
maybe (expired ctx cap) pure =<< timeout (ceiling (max 0 (due - now) * 1000000)) action
memoized :: Maybe Acyclic -> IO (Maybe Memo)
memoized (Just Plausible) = Just <$> (Memo <$> newIORef Map.empty <*> newIORef Map.empty <*> newIORef 0 <*> newIORef 0 <*> (Kin <$> newIORef (Spots Map.empty Map.empty) <*> newIORef Map.empty <*> newIORef Map.empty))
memoized _ = pure Nothing
recalled :: Maybe Memo -> Expression -> Int -> IO (Maybe Kept)
recalled Nothing _ _ = pure Nothing
recalled (Just (Memo store _ answers _ _)) form spent = do
kept <- readIORef store
count <- readIORef answers
let live = [known | (term, (stamp, known)) <- Map.findWithDefault [] (hashExpression form) kept, term == form, current count stamp known]
pure (find answered live <|> listToMaybe live)
where
current :: Int -> Int -> Kept -> Bool
current count stamp (Stalled _ least) = stamp == count && spent >= least
current _ _ _ = True
answered :: Kept -> Bool
answered (Answered _) = True
answered _ = False
counted :: Maybe Memo -> IO Int
counted Nothing = pure 0
counted (Just (Memo _ _ answers _ _)) = readIORef answers
starved :: Maybe Memo -> IO Int
starved Nothing = pure 0
starved (Just (Memo _ _ _ exhausted _)) = readIORef exhausted
retained :: Maybe Memo -> Expression -> Int -> Kept -> IO ()
retained Nothing _ _ _ = pure ()
retained (Just (Memo store _ _ _ _)) form stamp kept =
modifyIORef' store (Map.insertWith (++) (hashExpression form) [(form, (stamp, kept))])
remembered :: Maybe Memo -> Firing -> IO (Maybe (Expression, Answer))
remembered Nothing _ = pure Nothing
remembered (Just (Memo _ firings _ _ _)) firing = Map.lookup firing <$> readIORef firings
remember :: Maybe Memo -> Firing -> Expression -> Answer -> IO ()
remember Nothing _ _ _ = pure ()
remember (Just (Memo _ firings answers _ _)) firing form answer = do
modifyIORef' firings (Map.insert firing (form, answer))
modifyIORef' answers (+ 1)
placed :: Maybe Memo -> Expression -> Int -> IO ()
placed (Just (Memo _ _ _ _ (Kin places _ _))) term idx
| not (bare term) = modifyIORef' places (\spots -> List.foldl' spot spots (List.nub [term, stayed term]))
where
spot :: Spots -> Expression -> Spots
spot spots@(Spots known spelt) spelling = maybe (Spots (Map.insertWith (++) (hashExpression spelling) [(spelling, idx)] known) (Map.insertWith (\_ old -> old) idx spelling spelt)) (const spots) (spotted spots spelling)
bare :: Expression -> Bool
bare (ExFormation [BiLambda (FnSymbol _)]) = True
bare _ = False
placed _ _ _ = pure ()
spotted :: Spots -> Expression -> Maybe Int
spotted (Spots known _) term = lookup term (Map.findWithDefault [] (hashExpression term) known)
abstracted :: Sides -> Spots -> Expression -> IO (Expression, [(Int, Expression)])
abstracted store spots form = do
cache <- newIORef Map.empty
goExpr cache form
where
goExpr :: IORef (Map.Map T.Text (Expression, [(Int, Expression)])) -> Expression -> IO (Expression, [(Int, Expression)])
goExpr cache term = maybe (nested cache term) (\idx -> pure (ExFormation [BiLambda (FnSymbol idx)], [(idx, term)])) (spotted spots term)
nested :: IORef (Map.Map T.Text (Expression, [(Int, Expression)])) -> Expression -> IO (Expression, [(Int, Expression)])
nested cache term@(ExMeta name)
| isName name = do
done <- readIORef cache
case Map.lookup name done of
Just again -> pure again
Nothing -> do
side <- opened store term
made <-
if side == term
then pure (term, [])
else do
(side', posed) <- goExpr cache side
if side' == side then pure (term, posed) else (,posed) <$> named store side'
made <$ modifyIORef' cache (Map.insert name made)
nested cache term@(ExFormation bds) = do
parts <- mapM (goBinding cache) bds
pure (intact bds term ExFormation (map fst parts), concatMap snd parts)
nested cache term@(ExApplication expr arg) = do
(expr', one) <- goExpr cache expr
(arg', two) <- goArgument cache arg
pure (intact (expr, arg) term (uncurry ExApplication) (expr', arg'), one ++ two)
nested cache term@(ExDispatch expr attr) = first (intact expr term (`ExDispatch` attr)) <$> goExpr cache expr
nested _ term = pure (term, [])
goBinding :: IORef (Map.Map T.Text (Expression, [(Int, Expression)])) -> Binding -> IO (Binding, [(Int, Expression)])
goBinding cache bd@(BiTau attr expr) = first (intact expr bd (BiTau attr)) <$> goExpr cache expr
goBinding _ bd = pure (bd, [])
goArgument :: IORef (Map.Map T.Text (Expression, [(Int, Expression)])) -> Argument -> IO (Argument, [(Int, Expression)])
goArgument cache arg@(ArTau attr expr) = first (intact expr arg (ArTau attr)) <$> goExpr cache expr
goArgument cache arg@(ArAlpha alpha expr) = first (intact expr arg (ArAlpha alpha)) <$> goExpr cache expr
kindle :: Sides -> Maybe Memo -> Expression -> Firing -> Answer -> IO ()
kindle store (Just (Memo _ _ _ _ (Kin places likes _))) form firing answer = do
spots <- readIORef places
key <- fst <$> abstracted store spots form
modifyIORef' likes (Map.insertWith (++) (hashShape key) [Kindred key form firing answer])
kindle _ _ _ _ _ = pure ()
minting :: Maybe Memo -> Firing -> Answer -> IO ()
minting (Just (Memo _ _ _ _ (Kin _ _ minters))) firing@(Firing _ operands normals) answer =
modifyIORef' minters (\known -> List.foldl' (\held idx -> Map.insertWith (\_ old -> old) idx firing held) known [idx | idx <- answered answer, idx `notElem` inputs])
where
inputs :: [Int]
inputs = lefts operands ++ concatMap symbols normals
minting _ _ _ = pure ()
answered :: Answer -> [Int]
answered (Answer built normal) = List.nub (symbols built ++ symbols normal)
answered (Joined normal) = List.nub (symbols normal)
answered Raised = []
kindred :: ReduceContext -> Expression -> IO (Maybe (Kindred, Map.Map Int Int, [(Int, Expression)]))
kindred ctx@ReduceContext{_memo = Just (Memo _ _ _ _ (Kin places likes _))} form = do
spots <- readIORef places
known <- readIORef likes
(key, posed) <- abstracted ctx._sides spots form
look <- resolver ctx._sides
let found = listToMaybe [(kin, pairing, posed) | kin@(Kindred before _ _ _) <- Map.findWithDefault [] (hashShape key) known, Just pairing <- [bijection' look before key]]
awaited ctx (evaluate (isJust found `seq` found))
kindred _ _ = pure Nothing
adopted :: ReduceContext -> (Kindred, Map.Map Int Int, [(Int, Expression)]) -> Expression -> IO Answer
adopted ctx@ReduceContext{_memo = Just (Memo _ _ _ _ (Kin places _ _))} (Kindred key form firing answer, pairing, posed) target = do
table <- newIORef pairing
visiting <- newIORef Set.empty
Spots known _ <- readIORef places
adopt ctx (Renaming table (Spots known (Map.fromList [(idx, fromMaybe (ExFormation [BiLambda (FnSymbol idx')]) (lookup idx' posed)) | idx <- symbols key, Just idx' <- [Map.lookup idx pairing]])) visiting) firing key form answer (Just target)
adopted _ _ _ = throwIO (userError "A renamed answer needs the memo of --acyclic=plausible")
adopt :: ReduceContext -> Renaming -> Firing -> Expression -> Expression -> Answer -> Maybe Expression -> IO Answer
adopt ctx renaming@(Renaming table _ visiting) firing key form answer target = do
modifyIORef' visiting (Set.insert firing)
firing' <- refired ctx renaming firing
existing <- remembered ctx._memo firing'
look <- resolver ctx._sides
case existing >>= \(first', answer') -> (first',answer',) <$> bijection' look (ended answer) (ended answer') of
Just (first', answer', pairing) -> do
modifyIORef' table (`Map.union` pairing)
forM_ target $ \form' -> do
ctx._saveEval (EvRecalled (ctx._nesting + 1) first' (ended answer'))
stamp <- counted ctx._memo
retained ctx._memo form' stamp (Answered answer')
ctx._saveEval (EvMemoized (ctx._nesting + 1) form' (ended answer'))
pure answer'
Nothing -> do
minters <- held ctx._memo
let own = [idx | idx <- answered answer, Map.lookup idx minters == Just firing]
known <- readIORef table
forM_ [idx | idx <- own, Map.notMember idx known] $ \idx -> do
fresh <- coined ctx
modifyIORef' table (Map.insert idx fresh)
answer' <- reanswered answer
form' <- maybe (renamedTerm ctx renaming form) pure target
remember ctx._memo firing' form' answer'
table' <- readIORef table
minted' ctx._memo firing' [fresh | idx <- own, Just fresh <- [Map.lookup idx table']]
stamp <- counted ctx._memo
retained ctx._memo form' stamp (Answered answer')
ctx._saveEval (EvRenamed (ctx._nesting + 1) form' (ended answer') form [(idx, idx') | idx <- List.nub (symbols key ++ answered answer), Just idx' <- [Map.lookup idx table'], idx' /= idx])
pure answer'
where
reanswered :: Answer -> IO Answer
reanswered (Answer built normal) = Answer <$> renamedTerm ctx renaming built <*> renamedTerm ctx renaming normal
reanswered (Joined normal) = Joined <$> renamedTerm ctx renaming normal
reanswered Raised = pure Raised
held :: Maybe Memo -> IO (Map.Map Int Firing)
held (Just (Memo _ _ _ _ (Kin _ _ minters))) = readIORef minters
held Nothing = pure Map.empty
minted' :: Maybe Memo -> Firing -> [Int] -> IO ()
minted' (Just (Memo _ _ _ _ (Kin _ _ minters))) firing' fresh = modifyIORef' minters (\known -> List.foldl' (\kept idx -> Map.insert idx firing' kept) known fresh)
minted' Nothing _ _ = pure ()
refired :: ReduceContext -> Renaming -> Firing -> IO Firing
refired ctx renaming (Firing func operands normals) = Firing func <$> mapM operand operands <*> mapM (renamedTerm ctx renaming) normals
where
operand :: Either Int Bytes -> IO (Either Int Bytes)
operand (Left idx) = Left <$> renamedSymbol ctx renaming idx
operand bytes = pure bytes
renamedTerm :: ReduceContext -> Renaming -> Expression -> IO Expression
renamedTerm ctx renaming@(Renaming _ spots@(Spots _ spelt) _) term = do
renamed <- newIORef Map.empty
goExpr renamed term
where
goExpr :: IORef (Map.Map T.Text Expression) -> Expression -> IO Expression
goExpr renamed expr = maybe (nested renamed expr) (spot renamed expr) (spotted spots expr)
spot :: IORef (Map.Map T.Text Expression) -> Expression -> Int -> IO Expression
spot renamed expr idx = maybe (nested renamed expr) pure (Map.lookup idx spelt)
nested :: IORef (Map.Map T.Text Expression) -> Expression -> IO Expression
nested renamed expr@(ExMeta name)
| isName name = do
done <- readIORef renamed
case Map.lookup name done of
Just again -> pure again
Nothing -> do
side <- opened ctx._sides expr
made <- if side == expr then pure expr else named ctx._sides =<< goExpr renamed side
made <$ modifyIORef' renamed (Map.insert name made)
nested renamed expr = walked renamed expr
walked :: IORef (Map.Map T.Text Expression) -> Expression -> IO Expression
walked renamed whole@(ExFormation bds) = intact bds whole ExFormation <$> suffixed (goBinding renamed) bds
walked renamed whole@(ExApplication expr arg) = intact (expr, arg) whole (uncurry ExApplication) <$> ((,) <$> goExpr renamed expr <*> goArgument renamed arg)
walked renamed whole@(ExDispatch expr attr) = intact expr whole (`ExDispatch` attr) <$> goExpr renamed expr
walked _ expr = pure expr
goBinding :: IORef (Map.Map T.Text Expression) -> Binding -> IO Binding
goBinding renamed bd@(BiTau attr expr) = intact expr bd (BiTau attr) <$> goExpr renamed expr
goBinding _ (BiLambda (FnSymbol idx)) = BiLambda . FnSymbol <$> renamedSymbol ctx renaming idx
goBinding _ bd = pure bd
goArgument :: IORef (Map.Map T.Text Expression) -> Argument -> IO Argument
goArgument renamed arg@(ArTau attr expr) = intact expr arg (ArTau attr) <$> goExpr renamed expr
goArgument renamed arg@(ArAlpha alpha expr) = intact expr arg (ArAlpha alpha) <$> goExpr renamed expr
renamedSymbol :: ReduceContext -> Renaming -> Int -> IO Int
renamedSymbol ctx renaming@(Renaming table _ visiting) idx = do
known <- readIORef table
maybe unknown pure (Map.lookup idx known)
where
unknown :: IO Int
unknown = do
minter <- case ctx._memo of
Just (Memo _ _ _ _ (Kin _ _ minters)) -> Map.lookup idx <$> readIORef minters
Nothing -> pure Nothing
seen <- readIORef visiting
case minter of
Just firing | Set.notMember firing seen -> do
kept <- remembered ctx._memo firing
forM_ kept (\(form, answer) -> adopt ctx renaming firing form form answer Nothing)
maybe fresh pure . Map.lookup idx =<< readIORef table
Just _ -> fresh
Nothing -> idx <$ modifyIORef' table (Map.insert idx idx)
fresh :: IO Int
fresh = do
made <- coined ctx
made <$ modifyIORef' table (Map.insert idx made)
parking :: NonEmpty Rewritten -> State -> IO a -> IO a
parking seq state action = action `catch` rethrow
where
rethrow :: ReduceException -> IO a
rethrow (Stuck func) = throwIO (StuckAt func seq state)
rethrow (OutOfSteps budget) = throwIO (OutOfStepsAt budget seq state)
rethrow (Looping term) = throwIO (LoopingAt term seq state)
rethrow failure = throwIO failure
unparked :: IO a -> IO a
unparked action = action `catch` rethrow
where
rethrow :: ReduceException -> IO a
rethrow (StuckAt func _ _) = throwIO (Stuck func)
rethrow (OutOfStepsAt budget _ _) = throwIO (OutOfSteps budget)
rethrow (LoopingAt term _ _) = throwIO (Looping term)
rethrow failure = throwIO failure
admitting :: Expression -> ReduceContext -> IO (Either (Acyclic, Expression) ReduceContext)
admitting term ctx = maybe (pure (Right ctx)) (`admitted` ctx) (entrance ctx._judgment term)
enter :: Expression -> ReduceContext -> IO ReduceContext
enter form ctx = admitted form ctx >>= either (refused form ctx) pure
refused :: Expression -> ReduceContext -> (Acyclic, Expression) -> IO a
refused form ctx (mode, before) = do
ctx._saveEval (EvLooped ctx._nesting ctx._judgment mode before ctx._site Nothing)
throwIO (Looping form)
severing :: Expression -> Expression -> State -> ReduceContext -> IO (Expression, ReduceContext)
severing term univ state ctx = case entrance ctx._judgment term of
Just form -> either (,ctx) (term,) <$> sever (over term) form univ state ctx
Nothing -> pure (term, ctx)
where
over :: Expression -> Maybe Attribute
over (ExDispatch _ attr) = Just attr
over _ = Nothing
sever :: Maybe Attribute -> Expression -> Expression -> State -> ReduceContext -> IO (Either Expression ReduceContext)
sever taken form univ state ctx = admitted form ctx >>= either cut (pure . Right)
where
cut :: (Acyclic, Expression) -> IO (Either Expression ReduceContext)
cut loop = case form of
ExFormation bds -> Left <$> severed taken univ ctx state form bds loop
_ -> refused form ctx loop
severed :: Maybe Attribute -> Expression -> ReduceContext -> State -> Expression -> [Binding] -> (Acyclic, Expression) -> IO Expression
severed taken univ ctx state form bds (mode, before) = do
call <- tracing ctx form before
reckoned <- traverse (spelled taken) call
fresh <- coined ctx
ctx._saveEval (EvLooped ctx._nesting ctx._judgment mode before ctx._site (Just (fresh, reckoned)))
pure (ExFormation [BiLambda (FnSymbol fresh)])
where
spelled :: Maybe Attribute -> Expression -> IO Expression
spelled (Just attr) found = pure (ExDispatch found attr)
spelled Nothing found
| ctx._reckoning = pure found
| otherwise = argued univ ctx{_reckoning = True} state form bds found
passing :: ReduceContext -> Expression -> (Acyclic, Expression) -> IO ()
passing ctx form (mode, before) = do
call <- tracing ctx form before
ctx._saveEval (EvPassed ctx._nesting ctx._judgment mode before ctx._site form call)
tracing :: ReduceContext -> Expression -> Expression -> IO (Maybe Expression)
tracing ctx form before = do
call <- awaited ctx (evaluate =<< ((<|>) <$> traced ctx._facts form <*> traced ctx._facts before))
forM_ call (recited ctx . snd)
pure (fst <$> call)
recited :: ReduceContext -> [(Expression, Expression)] -> IO ()
recited ctx = mapM_ (\(term, source) -> ctx._saveEval (EvRecalled ctx._nesting term source))
factual :: IO Facts
factual = Facts <$> newIORef Map.empty <*> newIORef (Lodgings Map.empty Map.empty)
noted :: ReduceContext -> Expression -> Expression -> IO ()
noted ctx object source = forM_ ctx._facts $ \(Facts facts lodgings) -> do
known <- (Just source ==) . lookup object . Map.findWithDefault [] (hashExpression object) <$> readIORef facts
unless known $ do
modifyIORef' facts (Map.insertWith (++) (hashExpression object) [(object, source)])
modifyIORef' lodgings (\index -> fst (lodged Nothing index object))
ctx._saveEval (EvRemembered ctx._nesting object source)
where
lodged :: Maybe (Expression, Attribute) -> Lodgings -> Expression -> (Lodgings, Expression)
lodged edge index@(Lodgings nodes shapes) term@(ExFormation bds) = case [node | (node, _) <- Map.findWithDefault [] (hashExpression term) nodes, node == term] of
node : _ -> (maybe index (\parent -> Lodgings (Map.adjust (map (adopted node parent)) (hashExpression node) nodes) shapes) edge, node)
[] -> case List.foldl' (lodging term) (index, []) [(attr, body) | BiTau attr body@(ExFormation _) <- bds, attr /= AtRho] of
(Lodgings inner shapes', kids) -> (Lodgings (Map.insertWith (++) (hashExpression term) [(term, Lodging (maybeToList edge) (reverse kids))] inner) (Map.insertWith (++) (shaped bds) [term] shapes'), term)
lodged _ index term = (index, term)
lodging :: Expression -> (Lodgings, [(Attribute, Expression)]) -> (Attribute, Expression) -> (Lodgings, [(Attribute, Expression)])
lodging parent (index, kids) (attr, body) = case lodged (Just (parent, attr)) index body of
(index', kid) -> index' `seq` (index', (attr, kid) : kids)
adopted :: Expression -> (Expression, Attribute) -> (Expression, Lodging) -> (Expression, Lodging)
adopted node parent (term, Lodging parents kids)
| term == node = (term, Lodging (parent : parents) kids)
| otherwise = (term, Lodging parents kids)
shaped :: [Binding] -> Int
shaped bds = hashExpression (ExFormation (rholess bds))
rholess :: [Binding] -> [Binding]
rholess = filter ((/= Just AtRho) . attributeFromBinding)
remembering :: Maybe Facts -> Expression -> IO Bool
remembering Nothing _ = pure False
remembering (Just (Facts facts _)) term = isJust . lookup term . Map.findWithDefault [] (hashExpression term) <$> readIORef facts
traced :: Maybe Facts -> Expression -> IO (Maybe (Expression, [(Expression, Expression)]))
traced Nothing _ = pure Nothing
traced (Just (Facts facts lodgings)) form = do
known <- readIORef facts
index <- readIORef lodgings
pure (go index known [] form)
where
go :: Lodgings -> Store Expression -> [Expression] -> Expression -> Maybe (Expression, [(Expression, Expression)])
go index known passed term = listToMaybe [(named, (object, source) : hops) | (path, object, source) <- lodged index known term, object `notElem` passed, let (base, hops) = resolved index known (object : passed) source, Just named <- [rooted (foldl ExDispatch base path)]]
resolved :: Lodgings -> Store Expression -> [Expression] -> Expression -> (Expression, [(Expression, Expression)])
resolved index known passed source = case lookup source (Map.findWithDefault [] (hashExpression source) known) of
Just _ -> fromMaybe (source, []) (go index known passed source)
Nothing -> case source of
ExApplication target arg -> first (`ExApplication` arg) (resolved index known passed target)
ExDispatch target attr -> first (`ExDispatch` attr) (resolved index known passed target)
_ -> (source, [])
rooted :: Expression -> Maybe Expression
rooted term = term <$ guard (grounded term)
grounded :: Expression -> Bool
grounded ExRoot = True
grounded (ExDispatch target _) = grounded target
grounded (ExApplication target _) = grounded target
grounded _ = False
lodged :: Lodgings -> Store Expression -> Expression -> [([Attribute], Expression, Expression)]
lodged (Lodgings nodes shapes) known (ExFormation bds) = sortOn (\(path, _, _) -> length path) [(descended distances object, object, source) | digest <- Set.toAscList (Set.fromList (map hashExpression (concatMap (map fst) (Map.elems distances)))), (object, source) <- Map.findWithDefault [] digest known, isJust (lookup object (Map.findWithDefault [] digest distances))]
where
distances :: Store Int
distances = spread 0 matched (Map.fromListWith (++) [(hashExpression node, [(node, 0)]) | node <- matched])
matched :: [Expression]
matched = [node | node@(ExFormation inner) <- Map.findWithDefault [] (shaped bds) shapes, rholess inner == rholess bds]
spread :: Int -> [Expression] -> Store Int -> Store Int
spread _ [] reached = reached
spread depth frontier reached = uncurry (spread (succ depth)) (List.foldl' (climbed (succ depth)) ([], reached) [parent | node <- frontier, (parent, _) <- lodging node])
climbed :: Int -> ([Expression], Store Int) -> Expression -> ([Expression], Store Int)
climbed depth (next, reached) parent
| isJust (lookup parent (Map.findWithDefault [] (hashExpression parent) reached)) = (next, reached)
| otherwise = (parent : next, Map.insertWith (++) (hashExpression parent) [(parent, depth)] reached)
descended :: Store Int -> Expression -> [Attribute]
descended reached node = case lookup node (Map.findWithDefault [] (hashExpression node) reached) of
Just depth | depth > 0 -> concat (take 1 [attr : descended reached kid | (attr, kid) <- children node, lookup kid (Map.findWithDefault [] (hashExpression kid) reached) == Just (pred depth)])
_ -> []
lodging :: Expression -> [(Expression, Attribute)]
lodging node = maybe [] (\(Lodging parents _) -> parents) (lookup node (Map.findWithDefault [] (hashExpression node) nodes))
children :: Expression -> [(Attribute, Expression)]
children node = maybe [] (\(Lodging _ kids) -> kids) (lookup node (Map.findWithDefault [] (hashExpression node) nodes))
lodged _ _ _ = []
coined :: ReduceContext -> IO Int
coined ctx = atomicModifyIORef' ctx._minted (\count -> (succ count, succ count))
fired :: Expression -> ReduceContext -> Expression -> State -> Expression -> IO (Expression, State)
fired univ ctx site state form = sever Nothing form univ state ctx{_judgment = Evaluation, _site = site} >>= either (pure . (,state)) kindled
where
kindled :: ReduceContext -> IO (Expression, State)
kindled entered = do
deep <- deeper entered
deep._evaluate deep state form univ
voided :: ReduceContext -> Expression -> IO (Maybe [Attribute])
voided ReduceContext{_facts = Nothing} _ = pure Nothing
voided ctx@ReduceContext{_facts = Just (Facts facts _)} form@(ExFormation bds) = do
known <- readIORef facts
case lookup form (Map.findWithDefault [] (hashExpression form) known) of
Just source -> do
let (voids, hops) = placed known (Map.size known) bds source
recited ctx ((form, source) : hops)
pure voids
Nothing -> pure Nothing
where
placed :: Store Expression -> Int -> [Binding] -> Expression -> (Maybe [Attribute], [(Expression, Expression)])
placed known budget _ (ExApplication head' _) = headed known budget head'
placed _ _ own (ExDispatch _ _) = (Just [attr | BiVoid attr <- own], [])
placed _ _ _ _ = (Nothing, [])
headed :: Store Expression -> Int -> Expression -> (Maybe [Attribute], [(Expression, Expression)])
headed known budget (ExApplication head' _) = headed known budget head'
headed known budget head'@(ExFormation inner) = case lookup head' (Map.findWithDefault [] (hashExpression head') known) of
Just source | budget > 0 -> second ((head', source) :) (placed known (budget - 1) inner source)
_ -> (Just [attr | BiVoid attr <- inner], [])
headed _ _ _ = (Nothing, [])
voided _ _ = pure Nothing
called :: Expression -> ReduceContext -> Expression -> [Binding] -> IO (Maybe Expression)
called univ ctx form known = fmap (uncurry applied) <$> declared univ ctx form
where
applied :: Expression -> [Binding] -> Expression
applied path voids = foldl ExApplication path [ArTau attr value | BiTau attr value <- known, attr /= AtRho, BiVoid attr `elem` voids]
declared :: Expression -> ReduceContext -> Expression -> IO (Maybe (Expression, [Binding]))
declared univ ctx form = traced ctx._facts form >>= maybe (pure Nothing) placed
where
placed :: (Expression, [(Expression, Expression)]) -> IO (Maybe (Expression, [Binding]))
placed (call, hops) = do
recited ctx hops
pure ((erased call,) <$> located (erased call) (fromMaybe univ ctx._universe))
located :: Expression -> Expression -> Maybe [Binding]
located ExRoot (ExFormation bds) = Just bds
located (ExDispatch path attr) whole = case located path whole of
Just siblings -> listToMaybe [inner | BiTau attr' (ExFormation inner) <- siblings, attr' == attr]
Nothing -> Nothing
located _ _ = Nothing
erased :: Expression -> Expression
erased (ExApplication target _) = erased target
erased (ExDispatch target attr) = ExDispatch (erased target) attr
erased other = other
argued :: Expression -> ReduceContext -> State -> Expression -> [Binding] -> Expression -> IO Expression
argued univ ctx state site bds call = foldl ExDispatch <$> go inner <*> pure attrs
where
attrs :: [Attribute]
inner :: Expression
(attrs, inner) = dispatched call
go :: Expression -> IO Expression
go (ExApplication target (ArTau attr body)) = do
target' <- go target
ExApplication target' . ArTau attr <$> reckoned attr body
go term = pure term
reckoned :: Attribute -> Expression -> IO Expression
reckoned _ body@(ExFormation [BiLambda (FnSymbol _)]) = pure body
reckoned attr body = do
placed <- ctx._engine._contextualize body (ExFormation (filter (not . named attr) bds))
figured (ExDispatch site attr) placed
named :: Attribute -> Binding -> Bool
named attr (BiTau attr' _) = attr == attr'
named _ _ = False
figured :: Expression -> Expression -> IO Expression
figured place placed = unparked $ do
(answer, state') <- worked place placed state
if hanging answer
then fst <$> worked (ExDispatch place AtPhi) (ExDispatch answer AtPhi) state'
else pure answer
where
worked :: Expression -> Expression -> State -> IO (Expression, State)
worked place' placed' state' = do
(normal, morphed) <- settled placed' univ state' =<< opening Morphing ctx{_site = place'}
case normal of
ExFormation _
| thrown ctx._raising normal -> pure (normal, morphed)
| otherwise -> fired univ ctx place' morphed normal
_ -> pure (normal, morphed)
hanging :: Expression -> Bool
hanging (ExFormation bds) = not (any isLambda bds) && or [not (xiFree body) | BiTau AtPhi body <- bds]
hanging _ = False
admitted :: Expression -> ReduceContext -> IO (Either (Acyclic, Expression) ReduceContext)
admitted form ctx = maybe (pure (Right ctx)) remembered ctx._acyclic
where
remembered :: Acyclic -> IO (Either (Acyclic, Expression) ReduceContext)
remembered mode = maybe (Right ctx{_entered = seenInsert (digest mode form) form ctx._entered}) (\before -> Left (mode, before)) . listToMaybe . drop ctx._maxLoops <$> repeats mode form ctx
repeats :: Acyclic -> Expression -> ReduceContext -> IO [Expression]
repeats mode form ctx = do
look <- resolver ctx._sides
let hits = take (succ ctx._maxLoops) (filter (repeated look mode) (Map.findWithDefault [] (digest mode form) ctx._entered))
awaited ctx (evaluate (length hits `seq` hits))
where
repeated :: (T.Text -> Maybe Expression) -> Acyclic -> Expression -> Bool
repeated look Proven before = alike' look form before
repeated look Plausible before
| atomic form = akin' look before form
| otherwise = within' look before form
atomic :: Expression -> Bool
atomic (ExFormation bds) = any isLambda bds
atomic _ = False
digest :: Acyclic -> Expression -> Int
digest Proven = hashShape
digest Plausible = hashSkeleton
entrance :: Judgment -> Expression -> Maybe Expression
entrance Dataization term@(ExFormation bds)
| boxed bds || isJust (lambda bds) = Just term
entrance Morphing (ExDispatch form@(ExFormation bds) _)
| isJust (lambda bds) || boxed bds = Just form
entrance Evaluation term@(ExFormation bds)
| isJust (lambda bds) = Just term
entrance _ _ = Nothing
lambda :: [Binding] -> Maybe (T.Text, Expression)
lambda bds = case partition isLambda bds of
([BiLambda (Function func)], rest) -> Just (func, ExFormation rest)
_ -> Nothing
isLambda :: Binding -> Bool
isLambda (BiLambda _) = True
isLambda _ = False
morph' :: Morphed -> Expression -> State -> ReduceContext -> IO (Morphed, State)
morph' = morph'' True
morph'' :: Bool -> Morphed -> Expression -> State -> ReduceContext -> IO (Morphed, State)
morph'' owner start univ state entry = go start univ state entry
where
go :: Morphed -> Expression -> State -> ReduceContext -> IO (Morphed, State)
go (expr@(ExMeta name), seq) univ state caller
| isName name = do
side <- opened caller._sides expr
if side == expr then throwIO (Unmorphable expr) else go (side, seq) univ state caller
go (expr, seq) univ state caller = do
(term, entered) <- severing expr univ state =<< parking seq state (universed univ caller{_judgment = Morphing})
ctx <- opening Morphing =<< deeper entered
parking seq state $ do
reached <- maybe (inferred term univ state ctx ctx._engine._morphing) (\raise -> pure (Just (In.Answered (Morphing, "raise") raise, state))) (raised term)
case reached of
Just (In.Answered step built, state') -> do
when owner (ctx._saveEval (EvMorphed ctx._nesting built))
seq' <- leadsTo seq step built ctx
pure ((built, seq'), state')
Just (In.Onward way built world, state') -> do
(morphed, state'') <- onward seq state' way univ built ctx
go morphed world state'' ctx
Nothing -> throwIO (Unmorphable term)
where
raised :: Expression -> Maybe Expression
raised (ExDispatch target@(ExFormation _) _)
| thrown caller._raising target = Just target
raised _ = Nothing
morph :: Expression -> State -> ReduceContext -> IO (Expression, [Rewritten], State)
morph universe state caller@ReduceContext{..} = do
expr <- locatedExpression _locator universe
vetted Morphing expr caller
prepared <- try (universed universe caller)
case prepared of
Left (OutOfSteps _) | _partial -> pure (expr, [(universe, Nothing)], state)
Left failure -> throwIO (failure :: ReduceException)
Right univCtx -> reduced expr =<< opening Morphing univCtx
where
reduced :: Expression -> ReduceContext -> IO (Expression, [Rewritten], State)
reduced expr ctx = do
result <- try (morph' (expr, (universe, Nothing) :| []) universe state ctx)
case result of
Right ((morphed, seq), state') -> (,reverse (NE.toList seq),state') <$> spelled _sides morphed
Left (StuckAt func seq parked) | _partial -> residue seq parked{_stuck = Just func}
Left (OutOfStepsAt _ seq parked) | _partial -> residue seq parked
Left (OutOfSteps _) | _partial -> pure (expr, [(universe, Nothing)], state)
Left (LoopingAt _ seq parked) -> residue seq parked
Left failure -> throwIO (failure :: ReduceException)
residue :: NonEmpty Rewritten -> State -> IO (Expression, [Rewritten], State)
residue seq parked = do
expr <- spelled _sides =<< locatedExpression _locator (fst (NE.head seq))
pure (expr, reverse (NE.toList seq), parked)
vetted :: Judgment -> Expression -> ReduceContext -> IO ()
vetted judgment expr ctx = unless (ctx._engine._normal expr) (throwIO (Abnormal judgment expr))
inferred :: Expression -> Expression -> State -> ReduceContext -> [In.Inference value] -> IO (Maybe (In.Conclusion value, State))
inferred expr univ state ctx rules = do
ordered <- if ctx._shuffle then shuffle rules else pure rules
matched <- go ordered
traverse (premised state) matched
where
go :: [In.Inference value] -> IO (Maybe (In.Premises value))
go [] = pure Nothing
go (rule : rest) = rule (RuleContext (execBuildTerm univ ctx) (Just univ) ctx._engine._normal False) expr univ >>= maybe (go rest) (pure . Just)
premised :: State -> In.Premises value -> IO (In.Conclusion value, State)
premised state' (In.Concludes conclusion) = pure (conclusion, state')
premised state' (In.Morphs term world next) = do
(morphed, state'') <- detached term world state' ctx
next morphed >>= premised state''
premised state' (In.Evaluates form world next) = do
(answer, state'') <- ctx._evaluate ctx{_working = Just expr} state' form world
next answer >>= premised state''
premised state' (In.Contextualizes term context next) = ctx._engine._contextualize term context >>= next >>= premised state'
onward :: NonEmpty Rewritten -> State -> In.Way -> Expression -> Expression -> ReduceContext -> IO (Morphed, State)
onward seq state (In.Taken step) _ expr ctx = do
seq' <- leadsTo seq step expr ctx
pure ((expr, seq'), state)
onward seq state (In.Normalized step) univ expr' ctx = do
expr <- shared ctx expr'
labelled <- leadsTo seq step expr ctx
normal@(term, _) <- normalized expr labelled ctx
unless (term `elem` [expr, bare expr]) (ctx._saveEval (EvNormalized ctx._nesting (rooted expr) term))
pure (normal, state)
where
bare :: Expression -> Expression
bare (ExApplication inner _) = bare inner
bare inner = inner
rooted :: Expression -> Expression
rooted inner
| inner == univ = ExRoot
rooted (ExDispatch inner attr) = ExDispatch (rooted inner) attr
rooted (ExApplication inner arg) = ExApplication (rooted inner) arg
rooted inner = inner
onward seq state (In.Named step) univ expr ctx = case ctx._universe of
Just world -> onward seq state (In.Taken step) univ world ctx
Nothing -> onward seq state (In.Normalized step) univ expr ctx
onward seq state (In.Staged stage) _ expr ctx = morph' (expr, seq) stage state ctx
shared :: ReduceContext -> Expression -> IO Expression
shared ctx = go
where
go :: Expression -> IO Expression
go term@(ExApplication head' arg) = do
head'' <- go head'
arg' <- goArgument arg
pure (if head'' == head' && arg' == arg then term else ExApplication head'' arg')
go term@(ExDispatch inner attr) = do
inner' <- go inner
pure (if inner' == inner then term else ExDispatch inner' attr)
go term = pure term
goArgument :: Argument -> IO Argument
goArgument arg@(ArTau AtRho _) = pure arg
goArgument arg@(ArTau attr expr) = intact expr arg (ArTau attr) <$> (goValue =<< go expr)
goArgument arg@(ArAlpha alpha expr) = intact expr arg (ArAlpha alpha) <$> (goValue =<< go expr)
goValue :: Expression -> IO Expression
goValue value@(ExMeta _) = pure value
goValue value@(ExApplication inner (ArTau AtRho _))
| closed value && growing value = do
look <- resolver ctx._sides
if dispatching look inner then goValue inner else kept value
goValue value = kept value
dispatching :: (T.Text -> Maybe Expression) -> Expression -> Bool
dispatching _ (ExDispatch _ _) = True
dispatching look (ExApplication inner _) = dispatching look inner
dispatching look (ExMeta name) = maybe False (dispatching look) (look name)
dispatching _ _ = False
kept :: Expression -> IO Expression
kept value
| closed value && growing value = do
(name, fresh) <- minted ctx._sides value
when fresh (ctx._saveEval (EvShared ctx._nesting name value))
pure name
| otherwise = pure value
growing :: Expression -> Bool
growing (ExMeta _) = True
growing (ExDispatch inner _) = not (path inner) || growing inner
growing (ExApplication inner (ArTau _ arg)) = growing inner || growing arg
growing (ExApplication inner (ArAlpha _ arg)) = growing inner || growing arg
growing _ = False
path :: Expression -> Bool
path (ExDispatch inner _) = path inner
path ExRoot = True
path _ = False
closed :: Expression -> Bool
closed (ExApplication inner (ArTau _ arg)) = closed inner && closed arg
closed (ExApplication inner (ArAlpha _ arg)) = closed inner && closed arg
closed (ExDispatch inner _) = closed inner
closed (ExFormation _) = True
closed ExRoot = True
closed (ExBytes _) = True
closed ExTermination = True
closed (ExMeta name) = isName name
closed _ = False
leadsTo :: NonEmpty Rewritten -> (Judgment, String) -> Expression -> ReduceContext -> IO (NonEmpty Rewritten)
leadsTo ((current, _) :| rest) rule expr ReduceContext{..} = do
updated <- withLocatedExpression _locator expr current
pure ((updated, Nothing) :| (current, Just rule) : rest)
normalized :: Expression -> NonEmpty Rewritten -> ReduceContext -> IO (Expression, NonEmpty Rewritten)
normalized expr seq ctx@ReduceContext{..} = do
measured ctx expr
taken <- newIORef Map.empty
peeled <- newIORef Map.empty
copies <- newIORef Map.empty
go taken peeled copies expr seq
where
go :: IORef (Store Expression) -> IORef (Store Expression) -> IORef (Store Expression) -> Expression -> NonEmpty Rewritten -> IO (Expression, NonEmpty Rewritten)
go taken peeled copies term chain = do
whole <- withLocatedExpression _locator term (fst (NE.head chain))
(rewrittens, exceeded) <- rewrite whole _engine._normalization (rewriteContext taken peeled copies ctx)
when exceeded $ do
_saveEval (EvExceeded _nesting _maxCycles _judgment _site)
throwIO (OutOfSteps (Cycles _maxCycles))
let (rw :| rws) = NE.reverse rewrittens
chain' = rw :| rws <> NE.tail chain
term' <- locatedExpression _locator (fst rw)
look <- resolver _sides
let unfolded = spined look False term'
if unfolded == term' then pure (term', chain') else go taken peeled copies unfolded chain'
spined :: (T.Text -> Maybe Expression) -> Bool -> Expression -> Expression
spined look _ (ExDispatch term attr) = ExDispatch (spined look True term) attr
spined look _ (ExApplication term arg) = ExApplication (spined look True term) arg
spined look True term@(ExMeta name) = fromMaybe term (look name)
spined _ _ term = term
rewriteContext :: IORef (Store Expression) -> IORef (Store Expression) -> IORef (Store Expression) -> ReduceContext -> RewriteContext
rewriteContext taken peeled copies whole@ReduceContext{..} =
RewriteContext _locator _maxDepth _maxCycles _depthSensitive _universe _buildTerm _engine._normal _engine._matching MtDisabled Nothing (\term -> clocked whole >> (measured whole =<< locatedExpression _locator term) >> _saveStep term) (made taken peeled copies whole)
made :: IORef (Store Expression) -> IORef (Store Expression) -> IORef (Store Expression) -> ReduceContext -> Expression -> Expression -> IO ()
made _ _ copies whole redex@(ExApplication head' (ArTau attr _)) object@(ExFormation bds)
| attr /= AtRho && object /= head' = do
made' <- readIORef copies
if lookup redex (Map.findWithDefault [] (hashExpression redex) made') == Just object
then whole._saveEval (EvRecalled whole._nesting (called whole._universe redex) object)
else do
modifyIORef' copies (Map.insertWith (++) (hashExpression redex) [(redex, object)])
whole._saveEval (EvApplied whole._nesting whole._judgment (called whole._universe redex) object whole._site)
known <- remembering whole._facts head'
when (known && copied bds) (noted whole object redex)
made taken _ _ whole redex@(ExApplication _ (ArTau AtRho _)) object@(ExFormation bds)
| copied bds = do
pending <- readIORef taken
forM_ (lookup redex (Map.findWithDefault [] (hashExpression redex) pending)) (noted whole object)
made taken peeled _ whole redex@(ExDispatch target attr) object
| attr /= AtRho = do
stripped peeled whole target attr
dispatched taken peeled whole redex object
made _ _ _ _ _ _ = pure ()
stripped :: IORef (Store Expression) -> ReduceContext -> Expression -> Attribute -> IO ()
stripped peeled whole target@(ExFormation bds) attr = do
known <- remembering whole._facts target
when known (modifyIORef' peeled (Map.insertWith (++) (hashExpression (left bds)) [(left bds, target)]))
where
left :: [Binding] -> Expression
left inner = ExFormation [bd | bd <- inner, attributeFromBinding bd /= Just attr]
stripped _ _ _ _ = pure ()
dispatched :: IORef (Store Expression) -> IORef (Store Expression) -> ReduceContext -> Expression -> Expression -> IO ()
dispatched taken peeled whole redex object@(ExApplication (ExFormation bds) (ArTau AtRho _))
| copied bds = sourced peeled whole redex >>= mapM_ (\path -> modifyIORef' taken (Map.insertWith (++) (hashExpression object) [(object, path)]))
dispatched _ peeled whole redex object@(ExFormation bds)
| copied bds = sourced peeled whole redex >>= mapM_ (noted whole object)
dispatched taken peeled whole redex (ExApplication name@(ExMeta _) rho@(ArTau AtRho _)) = do
side <- opened whole._sides name
case side of
ExFormation bds
| copied bds && side /= name ->
let object = ExApplication side rho
in sourced peeled whole redex >>= mapM_ (\path -> modifyIORef' taken (Map.insertWith (++) (hashExpression object) [(object, path)]))
_ -> pure ()
dispatched _ _ _ _ _ = pure ()
sourced :: IORef (Store Expression) -> ReduceContext -> Expression -> IO (Maybe Expression)
sourced peeled whole redex@(ExDispatch target attr) = case worldly whole._universe redex of
Just path -> pure (Just path)
Nothing -> do
known <- remembering whole._facts target
held <- readIORef peeled
pure (if known then Just redex else (`ExDispatch` attr) <$> lookup target (Map.findWithDefault [] (hashExpression target) held))
sourced _ _ _ = pure Nothing
copied :: [Binding] -> Bool
copied bds = boxed bds || isJust (lambda bds)
worldly :: Maybe Expression -> Expression -> Maybe Expression
worldly universe (ExDispatch target attr) = (`ExDispatch` attr) <$> worldly universe target
worldly _ ExRoot = Just ExRoot
worldly universe target = ExRoot <$ guard (Just target == universe)
called :: Maybe Expression -> Expression -> Expression
called universe (ExApplication head' arg) = ExApplication (nameIn universe head') arg
called _ redex = redex
universed :: Expression -> ReduceContext -> IO ReduceContext
universed _ ctx@ReduceContext{_universe = Just _} = pure ctx
universed univ ctx = do
(normal, _) <- normalized univ ((univ, Nothing) :| []) ctx{_locator = ExRoot, _maxNodes = Nothing, _saveStep = dontSaveStep}
ctx._saveEval (EvWorld normal)
pure ctx{_universe = Just normal}
insideUniverse :: Expression -> Expression -> ReduceContext -> IO (Expression, ReduceContext)
insideUniverse expr univ ctx@ReduceContext{_buildTerm = buildTerm} = case univ of
ExFormation bds -> do
(TeAttribute attr) <- buildTerm "random-tau" [] substEmpty
let aiming = ctx{_locator = ExDispatch ExRoot attr}
synthetic = ExFormation (BiTau attr expr : bds)
(normal, _) <- normalized expr ((synthetic, Nothing) :| []) aiming
pure (ExFormation (BiTau attr normal : bds), aiming{_universe = extended attr normal})
_ -> throwIO (userError "Can't reduce an expression inside a universe which is not a formation")
where
extended :: Attribute -> Expression -> Maybe Expression
extended attr normal = case ctx._universe of
Just (ExFormation bds) -> Just (ExFormation (BiTau attr normal : bds))
_ -> Nothing
opening :: Judgment -> ReduceContext -> IO ReduceContext
opening judgment ctx
| ctx._opened == Just (ctx._nesting, judgment, ctx._site) = pure ctx{_judgment = judgment}
| otherwise = do
ctx._saveEval (EvStarted ctx._nesting judgment ctx._site)
pure ctx{_judgment = judgment, _nesting = ctx._nesting + 1, _opened = Just (ctx._nesting + 1, judgment, ctx._site)}
settled :: Expression -> Expression -> State -> ReduceContext -> IO (Expression, State)
settled term univ state ctx = do
(normal, _) <- normalized term ((univ, Nothing) :| []) ctx
((morphed, _), state') <- morph' (normal, (univ, Nothing) :| []) univ state ctx
pure (morphed, state')
morphing :: Expression -> ReduceContext -> Expression -> State -> IO (Expression, State)
morphing univ ctx expr state = do
(universe, aiming) <- insideUniverse expr univ ctx
normal <- locatedExpression aiming._locator universe
unparked $ do
opened <- opening Morphing =<< universed universe aiming
((morphed, _), state') <- morph' (normal, (universe, Nothing) :| []) universe state{_copies = []} opened
recurring morphed state'{_copies = state._copies ++ state'._copies} opened
where
recurring :: Expression -> State -> ReduceContext -> IO (Expression, State)
recurring term@(ExFormation bds) state' opened
| Just mode <- opened._acyclic
, boxed bds = do
hits <- repeats mode term opened
forM_ (listToMaybe (drop opened._maxLoops hits)) (passing opened term . (mode,))
pure (term, if null hits then state' else state'{_copies = state'._copies ++ [term]})
recurring term state' _ = pure (term, state')
carried :: State -> ReduceContext -> (State, ReduceContext)
carried state ctx = (state{_copies = []}, maybe ctx (\mode -> ctx{_entered = foldr (\form -> seenInsert (digest mode form) form) ctx._entered state._copies}) ctx._acyclic)
execBuildTerm :: Expression -> ReduceContext -> BuildTermFunc
execBuildTerm _ ctx "evaluate" = evaluated ctx
execBuildTerm univ ctx "morph" = _morph univ ctx
execBuildTerm _ ctx func = _buildTerm ctx func
evaluated :: ReduceContext -> BuildTermMethod
evaluated ctx [ArgExpression expr, ArgExpression universe] subst = do
form <- buildExpressionThrows expr subst
world <- buildExpressionThrows universe subst
TeExpression . fst <$> ctx._evaluate ctx emptyState form world
evaluated _ _ _ = throwIO (userError "Function evaluate() requires exactly 2 expression arguments")
_morph :: Expression -> ReduceContext -> BuildTermMethod
_morph univ ctx [ArgExpression expr] subst = do
built <- buildExpressionThrows expr subst
TeExpression . fst <$> detached built univ emptyState ctx
_morph _ _ _ _ = throwIO (userError "Function morph() requires exactly 1 expression argument")
detached :: Expression -> Expression -> State -> ReduceContext -> IO (Expression, State)
detached expr univ state ctx = unparked $ do
((morphed, _), state') <- morph'' (ctx._judgment /= Morphing) (expr, (univ, Nothing) :| []) univ state ctx
pure (morphed, state')