oeiuwq.com
A Golang runtime and compilation backend for Delta Interaction Nets.
1package lambda
2
3import (
4 "fmt"
5 "github.com/vic/godnet/pkg/deltanet"
6 "os"
7)
8
9var deltaDebug = os.Getenv("DELTA_DEBUG") != ""
10
11// Context for variables: name -> {Node, Port, Level}
12type varInfo struct {
13 node deltanet.Node
14 port int
15 level int
16}
17
18// ToDeltaNet converts a lambda term to a Delta Net.
19// Returns: root node, root port, and a map from Var node IDs to variable names.
20func ToDeltaNet(term Term, net *deltanet.Network) (deltanet.Node, int, map[uint64]string) {
21 // We return the Node and Port index that represents the "root" of the term.
22 // This port should be connected to the "parent".
23
24 vars := make(map[string]*varInfo)
25 varNames := make(map[uint64]string)
26
27 node, port := buildTerm(term, net, vars, 0, 0, varNames)
28 return node, port, varNames
29}
30
31func buildTerm(term Term, net *deltanet.Network, vars map[string]*varInfo, level int, depth uint64, varNames map[uint64]string) (deltanet.Node, int) {
32 switch t := term.(type) {
33 case Var:
34 if info, ok := vars[t.Name]; ok {
35 // Variable is bound
36
37 if info.node.Type() == deltanet.NodeTypeReplicator {
38 // Subsequent use
39 // info.node is the Replicator.
40 // We need to add a port to it.
41 // Create new Replicator with +1 port.
42 oldRep := info.node
43 oldDeltas := oldRep.Deltas()
44 newDelta := level - (info.level + 1)
45 newDeltas := append(oldDeltas, newDelta)
46
47 newRep := net.NewReplicator(oldRep.Level(), newDeltas)
48 // fmt.Printf("ToDeltaNet: Expand Replicator ID %d level=%d oldDeltas=%v -> newDeltas=%v (usage level=%d, binder level=%d)\n", oldRep.ID(), oldRep.Level(), oldDeltas, newDeltas, level, info.level)
49
50 // Move connections
51 // Rep.0 -> Source
52 sourceNode, sourcePort := net.GetLink(oldRep, 0)
53 net.LinkAt(newRep, 0, sourceNode, sourcePort, depth)
54
55 // Move existing aux ports
56 for i := 0; i < len(oldDeltas); i++ {
57 // Get what oldRep.i+1 is connected to
58 destNode, destPort := net.GetLink(oldRep, i+1)
59 if destNode != nil {
60 net.LinkAt(newRep, i+1, destNode, destPort, depth)
61 }
62 }
63
64 // Update info
65 info.node = newRep
66 info.port = 0
67
68 // Return new port
69 return newRep, len(newDeltas) // Index is len (1-based? No, 0 is principal. 1..len)
70 }
71
72 linkNode, _ := net.GetLink(info.node, info.port)
73
74 if linkNode.Type() == deltanet.NodeTypeEraser {
75 // First use
76 // Remove Eraser (linkNode)
77 // In `deltanet`, `removeNode` is no-op, but we should disconnect.
78 // Actually `Link` overwrites.
79
80 // Create Replicator
81 delta := level - (info.level + 1)
82
83 repLevel := info.level + 1
84
85 // Link Rep.0 to Source (info.node, info.port)
86 rep := net.NewReplicator(repLevel, []int{delta})
87 net.LinkAt(rep, 0, info.node, info.port, depth)
88 // fmt.Printf("ToDeltaNet: First-use: created Replicator ID %d level=%d deltas=%v for binder level=%d usage level=%d\n", rep.ID(), rep.Level(), rep.Deltas(), info.level, level)
89
90 // Update info to point to Rep
91 info.node = rep
92 info.port = 0 // Rep.0 is the input
93
94 // Return Rep.1
95 return rep, 1
96
97 } else {
98 // Should not happen if logic is correct (either Eraser or Replicator)
99 panic(fmt.Sprintf("Unexpected node type on variable binding: %v", linkNode.Type()))
100 }
101
102 } else {
103 // Free variable
104 // Create Var node
105 v := net.NewVar()
106 // Store the variable name for later reconstruction
107 varNames[v.ID()] = t.Name
108 // Create Replicator to share it (as per deltanets.ts)
109 // "Create free variable node... Create a replicator fan-in... link... return rep.1"
110 // Level 0 for free vars.
111 // Debug: record replicator parameters for free var
112 // fmt.Printf("ToDeltaNet: Free var '%s' at level=%d -> Rep(level=%d, deltas=%v)\n", t.Name, level, 0, []int{level - 1})
113 rep := net.NewReplicator(0, []int{level - 1}) // level - (0 + 1) ?
114 net.LinkAt(rep, 0, v, 0, depth)
115
116 // Register in vars so we can share it if used again
117 vars[t.Name] = &varInfo{node: rep, port: 0, level: 0}
118
119 return rep, 1
120 }
121
122 case Abs:
123 // Create Fan
124 fan := net.NewFan()
125 // fan.0 is Result (returned)
126 // fan.1 is Body
127 // fan.2 is Var
128
129 // Create Eraser for Var initially
130 era := net.NewEraser()
131 net.LinkAt(era, 0, fan, 2, depth)
132
133 // Register var
134 // Save old var info if shadowing
135 oldVar := vars[t.Arg]
136 vars[t.Arg] = &varInfo{node: fan, port: 2, level: level}
137
138 // Build Body
139 bodyNode, bodyPort := buildTerm(t.Body, net, vars, level, depth, varNames)
140 net.LinkAt(fan, 1, bodyNode, bodyPort, depth)
141
142 // Restore var
143 if oldVar != nil {
144 vars[t.Arg] = oldVar
145 } else {
146 delete(vars, t.Arg)
147 }
148
149 return fan, 0
150
151 case App:
152 // Create Fan
153 fan := net.NewFan()
154 // fan.0 is Function
155 // fan.1 is Result (returned)
156 // fan.2 is Argument
157
158 // Build Function
159 funNode, funPort := buildTerm(t.Fun, net, vars, level, depth, varNames)
160 net.LinkAt(fan, 0, funNode, funPort, depth)
161
162 // Build Argument (level + 1)
163 argNode, argPort := buildTerm(t.Arg, net, vars, level+1, depth+1, varNames)
164 net.LinkAt(fan, 2, argNode, argPort, depth+1)
165
166 return fan, 1
167
168 case Let:
169 // Should have been desugared by parser, but if we encounter it:
170 // let x = Val in Body -> (\x. Body) Val
171 desugared := App{
172 Fun: Abs{Arg: t.Name, Body: t.Body},
173 Arg: t.Val,
174 }
175 return buildTerm(desugared, net, vars, level, depth, varNames)
176
177 default:
178 panic("Unknown term type")
179 }
180}
181
182// FromDeltaNet reconstructs a lambda term from the network.
183// varNames maps Var node IDs to their original variable names.
184func FromDeltaNet(net *deltanet.Network, rootNode deltanet.Node, rootPort int, varNames map[uint64]string) Term {
185 // Debug
186 // fmt.Printf("FromDeltaNet: Root %v Port %d\n", rootNode.Type(), rootPort)
187
188 // We traverse from the root.
189 // We need to track visited nodes to handle loops (though lambda terms shouldn't have loops unless we have recursion combinators).
190 // But we also need to track bound variables.
191
192 // Map from (NodeID, Port) to Variable Name for bound variables.
193 // When we enter Abs at 0, we assign a name to Abs.2.
194
195 bindings := make(map[uint64]string) // Key: Node ID of the binder (Fan), Value: Name
196
197 // We need a name generator
198 nameGen := 0
199 nextName := func() string {
200 name := fmt.Sprintf("x%d", nameGen)
201 nameGen++
202 return name
203 }
204
205 visited := make(map[string]bool)
206 return readTerm(net, rootNode, rootPort, bindings, nextName, visited, varNames)
207}
208
209func readTerm(net *deltanet.Network, node deltanet.Node, port int, bindings map[uint64]string, nextName func() string, visited map[string]bool, varNames map[uint64]string) Term {
210 if node == nil {
211 return Var{Name: "<nil>"}
212 }
213
214 // Handle Phase 2 rotation
215 // Phys 0 -> Log 1
216 // Phys 1 -> Log 2
217 // Phys 2 -> Log 0
218 logicalPort := port
219 if net.Phase() == 2 && node.Type() == deltanet.NodeTypeFan {
220 switch port {
221 case 0:
222 logicalPort = 1
223 case 1:
224 logicalPort = 2
225 case 2:
226 logicalPort = 0
227 }
228 }
229
230 key := fmt.Sprintf("%d:%d", node.ID(), port)
231 if visited[key] {
232 if deltaDebug {
233 fmt.Printf("readTerm: detected revisit %s -> returning <loop>\n", key)
234 }
235 return Var{Name: "<loop>"}
236 }
237 visited[key] = true
238 defer func() { delete(visited, key) }()
239
240 if deltaDebug {
241 fmt.Printf("readTerm: nodeType=%v id=%d port=%d phase=%d\n", node.Type(), node.ID(), port, net.Phase())
242 }
243 if deltaDebug && node.Type() == deltanet.NodeTypeFan {
244 // Print where each physical port links to (nodeID:port)
245 for i := 0; i < 3; i++ {
246 n, p := net.GetLink(node, i)
247 if n != nil {
248 fmt.Printf(" Fan link[%d] -> %v id=%d port=%d\n", i, n.Type(), n.ID(), p)
249 } else {
250 fmt.Printf(" Fan link[%d] -> <nil>\n", i)
251 }
252 }
253 }
254
255 switch node.Type() {
256 case deltanet.NodeTypeFan:
257 if logicalPort == 0 {
258 // Entering Abs at Result -> Abs
259 // Or Entering App at Fun -> App (Wait, App Result is 1)
260
261 // If we enter at Logical 0:
262 // For Abs: 0 is Result. We are reading the Abs term.
263 // For App: 0 is Fun. We are reading the Function part of an App?
264 // No, if we are reading a term, we enter at its "Output" port.
265 // Abs Output is 0.
266 // App Output is 1.
267
268 // So if LogicalPort == 0, it MUST be Abs.
269 name := nextName()
270 bindings[node.ID()] = name
271
272 // Body is at Logical 1
273 // We need to find the PHYSICAL port for Logical 1.
274 // If Phase 2: Log 1 -> Phys 0.
275 // If Phase 1: Log 1 -> Phys 1.
276 bodyPortIdx := 1
277 if net.Phase() == 2 {
278 bodyPortIdx = 0
279 }
280
281 body := readTerm(net, getLinkNode(net, node, bodyPortIdx), getLinkPort(net, node, bodyPortIdx), bindings, nextName, visited, varNames)
282 return Abs{Arg: name, Body: body}
283
284 } else if logicalPort == 1 {
285 // Entering at Logical 1.
286 // Abs: 1 is Body. (We are reading body? No, we enter at Output).
287 // App: 1 is Result. We are reading the App term.
288
289 // So if LogicalPort == 1, it MUST be App.
290
291 // Fun is at Logical 0.
292 // Arg is at Logical 2.
293
294 funPortIdx := 0
295 argPortIdx := 2
296 if net.Phase() == 2 {
297 funPortIdx = 2
298 argPortIdx = 1
299 }
300
301 funNode := getLinkNode(net, node, funPortIdx)
302 funP := getLinkPort(net, node, funPortIdx)
303 argNode := getLinkNode(net, node, argPortIdx)
304 argP := getLinkPort(net, node, argPortIdx)
305 if deltaDebug {
306 fmt.Printf(" App at Fan id=%d funLink=(%v id=%d port=%d) argLink=(%v id=%d port=%d)\n", node.ID(), funNode.Type(), funNode.ID(), funP, argNode.Type(), argNode.ID(), argP)
307 }
308 fun := readTerm(net, funNode, funP, bindings, nextName, visited, varNames)
309 arg := readTerm(net, argNode, argP, bindings, nextName, visited, varNames)
310 return App{Fun: fun, Arg: arg}
311
312 } else {
313 // Entering at Logical 2.
314 // Abs: 2 is Var.
315 // App: 2 is Arg.
316 // This means we are traversing UP a variable binding or argument?
317 // Should not happen when reading a term from root.
318 // Unless we are tracing a variable.
319 if name, ok := bindings[node.ID()]; ok {
320 return Var{Name: name}
321 }
322 return Var{Name: "<binding>"}
323 }
324
325 case deltanet.NodeTypeReplicator:
326 // We entered a Replicator.
327 // If we entered at Aux port (>= 1), we are reading a variable usage.
328 // We need to trace back to the source (Port 0).
329 if deltaDebug {
330 fmt.Printf(" Replicator(id=%d) Deltas=%v Level=%d entered at port=%d\n", node.ID(), node.Deltas(), node.Level(), port)
331 }
332
333 if port > 0 {
334 sourceNode := getLinkNode(net, node, 0)
335 sourcePort := getLinkPort(net, node, 0)
336
337 // Trace back until we hit a Fan.2 (Binder) or Var (Free)
338 // If the source is a Fan (Abs/App), traceVariable will delegate
339 // to readTerm to reconstruct the full subterm.
340 return traceVariable(net, sourceNode, sourcePort, bindings, nextName, visited, varNames)
341 } else {
342 // Entered at 0?
343 // Reading the value being shared?
344 // This happens if we have `(\x. x) M`. `M` connects to `Rep.0`.
345 // If we read `M`, we traverse `M`.
346 // But here we are reading the *term* that `Rep` is part of.
347 // If `Rep` is part of the term structure (e.g. sharing a subterm),
348 // then `Rep.0` points to the subterm.
349 // So we just recurse on `Rep.0`?
350 // No, `Rep.0` is the *input* to the Replicator.
351 // If we enter at 0, we are going *upstream*?
352 // Wait, `Rep` directionality:
353 // 0 is Input. 1..N are Outputs.
354 // If we enter at 0, we are looking at the Output of `Rep`? No.
355 // If we enter at 0, we came from the Input side.
356 // This means we are traversing *into* the Replicator from the source.
357 // This implies the Replicator is sharing the *result* of something.
358 // e.g. `let x = M in ...`. `M` connects to `Rep.0`.
359 // If we are reading `M`, we don't hit `Rep`.
360 // If we are reading the body, we hit `Rep` at aux ports.
361 // So when do we hit `Rep` at 0?
362 // Only if we are traversing `M` and `M` *is* the Replicator?
363 // No, `Rep` is not a term constructor like Abs/App. It's a structural node.
364 // If `M` is `x`, and `x` is shared, then `M` *is* a wire to `Rep`.
365 // But `Rep` is connected to `x`'s binder.
366 // So `M` connects to `Rep` aux port.
367 // So we enter at aux.
368
369 // What if `M` is `\y. y` and it is shared?
370 // `Abs` (M) connects to `Rep.0`.
371 // `Rep` aux ports connect to usages.
372 // If we read `M` (e.g. if we are reading the `let` value), we hit `Rep.0`.
373 // So we should just read what `Rep` is connected to?
374 // No, `Rep` *is* the sharing mechanism.
375 // If we are reading the term `M`, and `M` is shared, we see `Abs`.
376 // We don't see `Rep` unless we are reading the *usages*.
377 // Wait. `Abs.0` connects to `Rep.0`.
378 // If we read `M`, we start at `Abs.0`.
379 // We don't start at `Rep`.
380 // Unless `M` is *defined* as `Rep`? No.
381
382 // Ah, `FromDeltaNet` takes `rootNode, rootPort`.
383 // This is the "output" of the term.
384 // If the term is `\x. x`, output is `Abs.0`.
385 // If the term is `x`, output is `Rep` aux port (or `Abs.2`).
386 // If the term is `M N`, output is `App.1`.
387
388 // So we should never enter `Rep` at 0 during normal read-back of a term,
389 // unless the term *itself* is being shared and we are reading the *source*?
390 // But `rootNode` is the *result* of the reduction.
391 // If the result is shared, then `rootNode` might be `Rep`?
392 // If the result is `x` (free var), and it's shared?
393 // `Var` -> `Rep.0`. `Rep.1` -> Output.
394 // So Output is `Rep.1`. We enter at 1.
395
396 // So entering at 0 should be rare/impossible for "Result".
397 if deltaDebug {
398 fmt.Printf(" Replicator(id=%d) entered at 0, returning <rep-0>\n", node.ID())
399 }
400 return Var{Name: "<rep-0>"}
401 }
402
403 case deltanet.NodeTypeVar:
404 // Free variable or wire
405 // If it's a named var, return it.
406 // But `Var` nodes don't store names in `deltanet` package?
407 // `deltanet.NewVar()` creates `NodeTypeVar`.
408 // It doesn't store a name.
409 // We lost the name!
410 // We need to store names for free variables if we want to read them back.
411 // But `deltanet` doesn't support labels.
412 // I can't modify `deltanet` package (user reverted).
413 // So I can't store names in `Var` nodes.
414 // I'll return "<free>" or generate a name.
415 if deltaDebug {
416 fmt.Printf(" Var node encountered (id=%d) -> <free>\n", node.ID())
417 }
418 return Var{Name: "<free>"}
419
420 case deltanet.NodeTypeEraser:
421 return Var{Name: "<erased>"}
422
423 default:
424 return Var{Name: fmt.Sprintf("<? %v>", node.Type())}
425 }
426}
427
428func traceVariable(net *deltanet.Network, node deltanet.Node, port int, bindings map[uint64]string, nextName func() string, visited map[string]bool, varNames map[uint64]string) Term {
429 // Follow wires up through Replicators (entering at 0, leaving at 0?)
430 // No, `Rep.0` connects to Source.
431 // So if we are at `Rep`, we go to `Rep.0`'s link.
432
433 currNode := node
434 currPort := port
435
436 for {
437 if currNode == nil {
438 return Var{Name: "<nil-trace>"}
439 }
440
441 if deltaDebug {
442 fmt.Printf("traceVariable: at nodeType=%v id=%d port=%d phase=%d\n", currNode.Type(), currNode.ID(), currPort, net.Phase())
443 }
444
445 switch currNode.Type() {
446 case deltanet.NodeTypeFan:
447 // Handle Rotation
448 logicalPort := currPort
449 if net.Phase() == 2 {
450 switch currPort {
451 case 0:
452 logicalPort = 1
453 case 1:
454 logicalPort = 2
455 case 2:
456 logicalPort = 0
457 }
458 }
459
460 // Hit a Fan.
461 // If Logical 2, it's a binder (Abs Var).
462 if logicalPort == 2 {
463 if name, ok := bindings[currNode.ID()]; ok {
464 return Var{Name: name}
465 }
466 return Var{Name: "<unbound-fan>"}
467 }
468 // If Logical 0 or 1, reconstruct the full term (Abs or App)
469 // readTerm handles rotation internally based on port passed.
470 return readTerm(net, currNode, currPort, bindings, nextName, visited, varNames)
471
472 case deltanet.NodeTypeReplicator:
473 // Continue trace from Rep.0
474 if currPort == 0 {
475 return Var{Name: "<rep-trace-0>"}
476 }
477 if deltaDebug {
478 fmt.Printf(" traceVariable: traversing Replicator id=%d -> follow .0\n", currNode.ID())
479 }
480 nextNode, nextPort := net.GetLink(currNode, 0)
481 currNode = nextNode
482 currPort = nextPort
483
484 case deltanet.NodeTypeVar:
485 if deltaDebug {
486 fmt.Printf(" traceVariable: hit Var id=%d, varNames has %d entries\n", currNode.ID(), len(varNames))
487 for id, name := range varNames {
488 fmt.Printf(" varNames[%d] = %s\n", id, name)
489 }
490 }
491 if name, ok := varNames[currNode.ID()]; ok {
492 return Var{Name: name}
493 }
494 return Var{Name: "<free>"}
495
496 case deltanet.NodeTypeEraser:
497 return Var{Name: "<erased>"}
498
499 default:
500 return Var{Name: fmt.Sprintf("<? %v>", currNode.Type())}
501 }
502 }
503}
504
505func getLinkNode(net *deltanet.Network, node deltanet.Node, port int) deltanet.Node {
506 n, _ := net.GetLink(node, port)
507 return n
508}
509
510func getLinkPort(net *deltanet.Network, node deltanet.Node, port int) int {
511 _, p := net.GetLink(node, port)
512 return p
513}