markov.gno
7.62 Kb · 239 lines
1// Package markov ports the canonical Go example
2// "Generating arbitrary text: a Markov chain algorithm"
3// (https://go.dev/doc/codewalk/markov/) to a gno.land realm.
4//
5// The original reads words from an io.Reader, builds a map from each
6// two-word prefix to the list of words that followed it, then walks that
7// chain picking random suffixes to babble new text. Here the corpus lives
8// on-chain: Feed appends words to a persistent avl.Tree-backed chain, and
9// Generate walks it. The only change needed for on-chain determinism is the
10// source of randomness: instead of math/rand we seed a small LCG with
11// runtime.ChainHeight(), so Generate is a pure, reproducible query that still
12// varies block to block.
13//
14// Feed is a crossing function (takes `cur realm` first) because it mutates
15// on-chain state; Generate and Render are read-only.
16package markov
17
18import (
19 "chain"
20 "chain/runtime"
21 "strconv"
22 "strings"
23
24 "gno.land/p/nt/avl/v0"
25)
26
27// prefixLen is the number of words in a prefix. Two is the classic choice
28// from the Go codewalk: long enough to sound plausible, short enough to keep
29// the chain well-connected.
30const prefixLen = 2
31
32const maxGen = 200 // clamp for Generate / Render so output stays bounded
33
34// Prefix is a sliding window of the last prefixLen words seen. It mirrors the
35// Prefix type in the original program.
36type Prefix []string
37
38// key joins the prefix into the string used as the chain's map key. Two empty
39// strings (the initial prefix) join to a single space " ", which is exactly
40// the start-of-text key both Feed and Generate begin from.
41func (p Prefix) key() string { return strings.Join(p, " ") }
42
43// shift drops the oldest word and appends word, advancing the window by one.
44func (p Prefix) shift(word string) {
45 copy(p, p[1:])
46 p[len(p)-1] = word
47}
48
49// suffixList is the value stored per prefix: every word observed to follow it,
50// in order (duplicates kept so frequency biases the random walk, just like the
51// original []string in the chain map).
52type suffixList struct {
53 words []string
54}
55
56// Chain is the on-chain Markov chain. table maps prefix key -> *suffixList;
57// prefix is the rolling build window so successive Feed calls extend one
58// continuous corpus rather than restarting; words is the running word count.
59type Chain struct {
60 table avl.Tree
61 prefix Prefix
62 words int
63}
64
65func newChain() *Chain {
66 return &Chain{prefix: make(Prefix, prefixLen)}
67}
68
69// build tokenizes text on whitespace and folds each word into the chain,
70// recording it as a suffix of the current prefix and then shifting. This is
71// the on-chain analogue of Chain.Build from the codewalk.
72func (c *Chain) build(text string) int {
73 added := 0
74 for _, w := range strings.Fields(text) {
75 k := c.prefix.key()
76 var sl *suffixList
77 if c.table.Has(k) {
78 sl = c.table.Get(k).(*suffixList)
79 } else {
80 sl = &suffixList{}
81 }
82 sl.words = append(sl.words, w)
83 c.table.Set(k, sl)
84 c.prefix.shift(w)
85 c.words++
86 added++
87 }
88 return added
89}
90
91// generate walks the chain from the start prefix, picking one suffix per step
92// via the seeded LCG, and returns up to n words. It stops early if it reaches a
93// prefix with no recorded suffixes (a dead end). Pure: no global state touched.
94func (c *Chain) generate(n int, seed uint64) []string {
95 if n <= 0 {
96 return nil
97 }
98 p := make(Prefix, prefixLen)
99 rng := seed
100 out := make([]string, 0, n)
101 for i := 0; i < n; i++ {
102 k := p.key()
103 if !c.table.Has(k) {
104 break
105 }
106 choices := c.table.Get(k).(*suffixList).words
107 if len(choices) == 0 {
108 break
109 }
110 rng = nextRand(rng)
111 // use high bits of the LCG state — its low bits have short periods
112 idx := int((rng >> 33) % uint64(len(choices)))
113 next := choices[idx]
114 out = append(out, next)
115 p.shift(next)
116 }
117 return out
118}
119
120// nextRand is a 64-bit linear congruential generator (the PCG/Knuth
121// multiplier + increment). Deterministic and dependency-free — all the
122// entropy comes from the caller's seed.
123func nextRand(s uint64) uint64 {
124 return s*6364136223846793005 + 1442695040888963407
125}
126
127// seedFor derives a Generate seed from the current chain height so the babble
128// changes block to block yet stays reproducible for anyone querying the same
129// height.
130func seedFor() uint64 {
131 return uint64(runtime.ChainHeight())*2654435761 + 0x9e3779b97f4a7c15
132}
133
134// mc is the single on-chain corpus, seeded at deploy time.
135var mc = newChain()
136
137func init() {
138 // Two seed sentences with heavy two-word-prefix overlap, so a fresh deploy
139 // already babbles something recognizably chain-like.
140 mc.build("it was the best of times it was the worst of times " +
141 "it was the age of wisdom it was the age of foolishness")
142 mc.build("i am a free man i am not a number " +
143 "i am the master of my fate i am the captain of my soul")
144}
145
146// Feed appends text to the on-chain corpus, extending the Markov chain. Any
147// caller may enrich the corpus — this is the open-membership demo model.
148func Feed(cur realm, text string) string {
149 if strings.TrimSpace(text) == "" {
150 panic("markov: empty text")
151 }
152 added := mc.build(text)
153 chain.Emit("Feed", "words", strconv.Itoa(added), "total", strconv.Itoa(mc.words))
154 return "fed " + strconv.Itoa(added) + " words; corpus now " +
155 strconv.Itoa(mc.words) + " words across " +
156 strconv.Itoa(mc.table.Size()) + " prefixes"
157}
158
159// Generate babbles up to nWords of Markov text from the current corpus, seeded
160// deterministically by the chain height. Read-only.
161func Generate(nWords int) string {
162 if nWords <= 0 {
163 nWords = 20
164 }
165 if nWords > maxGen {
166 nWords = maxGen
167 }
168 return strings.Join(mc.generate(nWords, seedFor()), " ")
169}
170
171// Stats returns (totalWords, prefixCount) for the current corpus.
172func Stats() (int, int) {
173 return mc.words, mc.table.Size()
174}
175
176// parseN pulls a trailing positive integer out of a Render path such as
177// "/40" or "gen/40"; it returns 0 when there is none.
178func parseN(path string) int {
179 p := strings.Trim(path, "/")
180 if i := strings.LastIndex(p, "/"); i >= 0 {
181 p = p[i+1:]
182 }
183 n, err := strconv.Atoi(p)
184 if err != nil || n < 0 {
185 return 0
186 }
187 return n
188}
189
190// Render shows a freshly generated sample plus corpus stats. The path may
191// carry a word count, e.g. Render("/60").
192func Render(path string) string {
193 n := parseN(path)
194 if n == 0 {
195 n = 40
196 }
197 if n > maxGen {
198 n = maxGen
199 }
200
201 var b strings.Builder
202 b.WriteString("# Markov Babbler\n\n")
203 b.WriteString("An on-chain port of Go's classic *\"Generating arbitrary text: " +
204 "a Markov chain algorithm\"* codewalk. Every two-word **prefix** maps to " +
205 "the words that followed it; `Generate` walks that chain, picking suffixes " +
206 "with a PRNG seeded by the block height — deterministic, yet different each " +
207 "block.\n\n")
208
209 b.WriteString("## Fresh sample (" + strconv.Itoa(n) + " words, height " +
210 strconv.FormatInt(runtime.ChainHeight(), 10) + ")\n\n")
211 sample := strings.Join(mc.generate(n, seedFor()), " ")
212 if sample == "" {
213 sample = "_(empty corpus)_"
214 }
215 b.WriteString("> " + sample + "\n\n")
216
217 b.WriteString("## Corpus\n\n")
218 b.WriteString("- **Words:** " + strconv.Itoa(mc.words) + "\n")
219 b.WriteString("- **Distinct prefixes:** " + strconv.Itoa(mc.table.Size()) + "\n")
220 b.WriteString("- **Prefix length:** " + strconv.Itoa(prefixLen) + " words\n\n")
221
222 b.WriteString("## Some prefixes → suffixes\n\n")
223 b.WriteString("| prefix | can be followed by |\n|---|---|\n")
224 shown := 0
225 mc.table.Iterate("", "", func(k string, v interface{}) bool {
226 sl := v.(*suffixList)
227 disp := k
228 if disp == " " || disp == "" {
229 disp = "_(start)_"
230 }
231 b.WriteString("| `" + disp + "` | " + strings.Join(sl.words, ", ") + " |\n")
232 shown++
233 return shown >= 12 // cap the table
234 })
235 b.WriteString("\n_Call `Feed(\"your text here\")` to teach it new words, then " +
236 "reload for a new sample._\n")
237
238 return b.String()
239}
