File size: 3,216 Bytes
d8df231
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
-- Copyright (c) 2026 Ahmad Ali Parr. All rights reserved.
-- SPDX-License-Identifier: LicenseRef-Proprietary
-- Public source visibility does not grant an open-source license. See LICENSE.

module Main

import Data.Nat

%default total

||| Abstract execution status. Resource exhaustion is not successful termination.
data Status = Running | Halted | OutOfFuel | OutOfMemory | Failed

||| Minimal control term for the first machine milestone.
||| Extend only after the selected Unlambda dialect is specified.
data Term = PrimI | PrimK | PrimS | Apply Term Term | DelayedTerm Term

record Machine where
  constructor MkMachine
  control : Term
  fuel : Nat
  status : Status

||| A transition outcome always records the next explicit machine status.
data Transition = Advanced Machine | Finished Machine

||| Fuel is consumed exactly once for an ordinary transition.
consumeRunning : Term -> Nat -> Machine
consumeRunning t Z = MkMachine t Z OutOfFuel
consumeRunning t (S k) = MkMachine t k Running

consumeFuel : Machine -> Machine
consumeFuel (MkMachine t n Running) = consumeRunning t n
consumeFuel (MkMachine t n Halted) = MkMachine t n Halted
consumeFuel (MkMachine t n OutOfFuel) = MkMachine t n OutOfFuel
consumeFuel (MkMachine t n OutOfMemory) = MkMachine t n OutOfMemory
consumeFuel (MkMachine t n Failed) = MkMachine t n Failed

||| The transition function is intentionally a control-model stub until
||| the full Unlambda operational semantics are fixed in spec/.
stepControl : Machine -> Transition
stepControl m@(MkMachine _ Z Running) = Finished (consumeFuel m)
stepControl m@(MkMachine _ (S _) Running) = Advanced (consumeFuel m)
stepControl m = Finished m

||| A structural fact: consuming fuel never increases the fuel counter.
natLteRefl : (n : Nat) -> LTE n n
natLteRefl Z = LTEZero
natLteRefl (S n) = LTESucc (natLteRefl n)

natLteNext : (n : Nat) -> LTE n (S n)
natLteNext Z = LTEZero
natLteNext (S n) = LTESucc (natLteNext n)

fuelDoesNotIncrease : (m : Machine) -> fuel (consumeFuel m) `LTE` fuel m
fuelDoesNotIncrease (MkMachine t Z Running) = LTEZero
fuelDoesNotIncrease (MkMachine t (S k) Running) = natLteNext k
fuelDoesNotIncrease (MkMachine t n Halted) = natLteRefl n
fuelDoesNotIncrease (MkMachine t n OutOfFuel) = natLteRefl n
fuelDoesNotIncrease (MkMachine t n OutOfMemory) = natLteRefl n
fuelDoesNotIncrease (MkMachine t n Failed) = natLteRefl n

||| One running transition consumes exactly one unit, not two or zero.
positiveFuelConsumesOne : (t : Term) -> (n : Nat) ->
  fuel (consumeFuel (MkMachine t (S n) Running)) = n
positiveFuelConsumesOne t n = Refl

||| Heap exhaustion remains distinct from generic failure and termination.
memoryExhaustionIsPreserved : (t : Term) -> (n : Nat) ->
  status (consumeFuel (MkMachine t n OutOfMemory)) = OutOfMemory
memoryExhaustionIsPreserved t n = Refl

||| Resource exhaustion is explicit when a running machine has zero fuel.
zeroFuelIsNotHalted : (t : Term) -> status (consumeFuel (MkMachine t Z Running)) = OutOfFuel
zeroFuelIsNotHalted t = Refl

main : IO ()
main = do
  let initial = MkMachine PrimI 1 Running
  case stepControl initial of
    Advanced next => putStrLn "step: advanced"
    Finished next => putStrLn "step: finished"