oeiuwq.com
A Golang runtime and compilation backend for Delta Interaction Nets.
1package compiler
2
3import (
4 "fmt"
5 "strings"
6
7 "github.com/vic/godnet/pkg/lambda"
8)
9
10// CodeGenerator translates lambda AST to Go code.
11type CodeGenerator struct {
12 SourceFile string
13 SourceText string
14 buf strings.Builder
15 nodeCount int
16 vars map[string]*varInfo
17}
18
19type varInfo struct {
20 nodeName string
21 port int // Next available aux port (for replicators)
22 level int
23 uses int // Number of times variable has been used
24}
25
26// Generate produces Go source code from a lambda term.
27func (g *CodeGenerator) Generate(term lambda.Term) string {
28 g.vars = make(map[string]*varInfo)
29
30 g.writeHeader()
31 g.writeBuildNetFunction(term)
32 g.writeMainFunction()
33
34 return g.buf.String()
35}
36
37func (g *CodeGenerator) writeHeader() {
38 g.writeLine("package main")
39 g.writeLine("")
40 g.writeLine("// Generated by godnet compiler")
41 g.writeLine("// Source: %s", g.SourceFile)
42 g.writeLine("")
43 g.writeLine("import (")
44 g.writeLine("\t\"fmt\"")
45 g.writeLine("\t\"os\"")
46 g.writeLine("\t\"time\"")
47 g.writeLine("\t\"github.com/vic/godnet/pkg/deltanet\"")
48 g.writeLine("\t\"github.com/vic/godnet/pkg/lambda\"")
49 g.writeLine(")")
50 g.writeLine("")
51}
52
53func (g *CodeGenerator) writeBuildNetFunction(term lambda.Term) {
54 g.writeLine("func buildNet(net *deltanet.Network) (deltanet.Node, int, map[uint64]string) {")
55 g.writeLine("\tvarNames := make(map[uint64]string)")
56 g.writeLine("")
57
58 // Translate the term
59 rootNode, rootPort := g.translateTerm(term, 0, 0)
60
61 g.writeLine("")
62 g.writeLine("\treturn %s, %d, varNames", rootNode, rootPort)
63 g.writeLine("}")
64 g.writeLine("")
65}
66
67func (g *CodeGenerator) writeMainFunction() {
68 g.writeLine("func main() {")
69 g.writeLine("\tnet := deltanet.NewNetwork()")
70 g.writeLine("\troot, port, varNames := buildNet(net)")
71 g.writeLine("")
72 g.writeLine("\toutput := net.NewVar()")
73 g.writeLine("\tnet.Link(root, port, output, 0)")
74 g.writeLine("")
75 g.writeLine("\tstart := time.Now()")
76 g.writeLine("\tnet.ReduceAll()")
77 g.writeLine("\telapsed := time.Since(start)")
78 g.writeLine("")
79 g.writeLine("\tresultNode, resultPort := net.GetLink(output, 0)")
80 g.writeLine("\tresult := lambda.FromDeltaNet(net, resultNode, resultPort, varNames)")
81 g.writeLine("\tfmt.Println(result)")
82 g.writeLine("")
83 g.writeLine("\tstats := net.GetStats()")
84 g.writeLine("\tseconds := elapsed.Seconds()")
85 g.writeLine("\tfmt.Fprintf(os.Stderr, \"\\nStats:\\n\")")
86 g.writeLine("\tfmt.Fprintf(os.Stderr, \"Time: %%v\\n\", elapsed)")
87 g.writeLine("\tfmt.Fprintf(os.Stderr, \"Total Reductions: %%d\", stats.TotalReductions)")
88 g.writeLine("\tif seconds > 0 {")
89 g.writeLine("\t\tfmt.Fprintf(os.Stderr, \" (%%.2f ops/sec)\", float64(stats.TotalReductions)/seconds)")
90 g.writeLine("\t}")
91 g.writeLine("\tfmt.Fprintf(os.Stderr, \"\\n\")")
92 g.writeLine("}")
93}
94
95func (g *CodeGenerator) translateTerm(term lambda.Term, level int, depth uint64) (string, int) {
96 switch t := term.(type) {
97 case lambda.Var:
98 return g.genVar(t, level, depth)
99 case lambda.Abs:
100 return g.genAbs(t, level, depth)
101 case lambda.App:
102 return g.genApp(t, level, depth)
103 case lambda.Let:
104 // Desugar: let x = v in b → (λx. b) v
105 desugared := lambda.App{
106 Fun: lambda.Abs{Arg: t.Name, Body: t.Body},
107 Arg: t.Val,
108 }
109 return g.translateTerm(desugared, level, depth)
110 default:
111 panic(fmt.Sprintf("unknown term type: %T", term))
112 }
113}
114
115func (g *CodeGenerator) genVar(v lambda.Var, level int, depth uint64) (string, int) {
116 if info, ok := g.vars[v.Name]; ok {
117 // Bound variable - expand replicator
118 g.writeComment("Variable: %s (bound)", v.Name)
119
120 if strings.HasPrefix(info.nodeName, "rep_") {
121 // Already a replicator, expand it
122 oldRepName := info.nodeName
123 newRepName := g.nextNode("rep")
124 delta := level - (info.level + 1)
125 nextPort := info.uses + 1 // Next aux port index (1-based, since port 0 is principal)
126
127 g.writeLine("\t// Expand replicator for variable '%s' (use #%d)", v.Name, info.uses+1)
128 g.writeLine("\t%s := net.NewReplicator(%d, append(%s.Deltas(), %d))",
129 newRepName, info.level, oldRepName, delta)
130
131 // Move principal connection
132 g.writeLine("\tsourceNode, sourcePort := net.GetLink(%s, 0)", oldRepName)
133 g.writeLine("\tnet.LinkAt(%s, 0, sourceNode, sourcePort, %d)", newRepName, depth)
134
135 // Move existing aux ports
136 g.writeLine("\tfor i := 0; i < len(%s.Deltas()); i++ {", oldRepName)
137 g.writeLine("\t\tdestNode, destPort := net.GetLink(%s, i+1)", oldRepName)
138 g.writeLine("\t\tif destNode != nil {")
139 g.writeLine("\t\t\tnet.LinkAt(%s, i+1, destNode, destPort, %d)", newRepName, depth)
140 g.writeLine("\t\t}")
141 g.writeLine("\t}")
142
143 info.nodeName = newRepName
144 info.uses++
145 return newRepName, nextPort
146 } else {
147 // First use after eraser - create replicator
148 g.writeLine("\t// First use of variable '%s'", v.Name)
149 repName := g.nextNode("rep")
150 delta := level - (info.level + 1)
151 repLevel := info.level + 1
152
153 g.writeLine("\t%s := net.NewReplicator(%d, []int{%d})", repName, repLevel, delta)
154 g.writeLine("\tnet.LinkAt(%s, 0, %s, %d, %d)", repName, info.nodeName, info.port, depth)
155
156 info.nodeName = repName
157 info.uses = 1
158 return repName, 1
159 }
160 } else {
161 // Free variable
162 g.writeComment("Variable: %s (free)", v.Name)
163 varName := g.nextNode("var")
164 repName := g.nextNode("rep")
165
166 g.writeLine("\t%s := net.NewVar()", varName)
167 g.writeLine("\tvarNames[%s.ID()] = \"%s\"", varName, v.Name)
168 g.writeLine("\t%s := net.NewReplicator(0, []int{%d})", repName, level-1)
169 g.writeLine("\tnet.LinkAt(%s, 0, %s, 0, %d)", repName, varName, depth)
170
171 g.vars[v.Name] = &varInfo{
172 nodeName: repName,
173 port: 0,
174 level: 0,
175 }
176
177 return repName, 1
178 }
179}
180
181func (g *CodeGenerator) genAbs(abs lambda.Abs, level int, depth uint64) (string, int) {
182 g.writeComment("Abstraction: λ%s. ...", abs.Arg)
183
184 fanName := g.nextNode("fan")
185 eraName := g.nextNode("era")
186
187 g.writeLine("\t%s := net.NewFan()", fanName)
188 g.writeLine("\t%s := net.NewEraser()", eraName)
189 g.writeLine("\tnet.LinkAt(%s, 0, %s, 2, %d)", eraName, fanName, depth)
190
191 // Save old binding if shadowing
192 oldVar := g.vars[abs.Arg]
193 g.vars[abs.Arg] = &varInfo{
194 nodeName: fanName,
195 port: 2,
196 level: level,
197 }
198
199 // Generate body
200 bodyNode, bodyPort := g.translateTerm(abs.Body, level, depth)
201 g.writeLine("\tnet.LinkAt(%s, 1, %s, %d, %d)", fanName, bodyNode, bodyPort, depth)
202
203 // Restore old binding
204 if oldVar != nil {
205 g.vars[abs.Arg] = oldVar
206 } else {
207 delete(g.vars, abs.Arg)
208 }
209
210 return fanName, 0
211}
212
213func (g *CodeGenerator) genApp(app lambda.App, level int, depth uint64) (string, int) {
214 g.writeComment("Application")
215
216 fanName := g.nextNode("fan")
217 g.writeLine("\t%s := net.NewFan()", fanName)
218
219 // Generate function
220 funNode, funPort := g.translateTerm(app.Fun, level, depth)
221 g.writeLine("\tnet.LinkAt(%s, 0, %s, %d, %d)", fanName, funNode, funPort, depth)
222
223 // Generate argument (level + 1)
224 argNode, argPort := g.translateTerm(app.Arg, level+1, depth+1)
225 g.writeLine("\tnet.LinkAt(%s, 2, %s, %d, %d)", fanName, argNode, argPort, depth+1)
226
227 return fanName, 1
228}
229
230func (g *CodeGenerator) nextNode(prefix string) string {
231 g.nodeCount++
232 return fmt.Sprintf("%s_%d", prefix, g.nodeCount)
233}
234
235func (g *CodeGenerator) writeLine(format string, args ...interface{}) {
236 g.buf.WriteString(fmt.Sprintf(format, args...))
237 g.buf.WriteString("\n")
238}
239
240func (g *CodeGenerator) writeComment(format string, args ...interface{}) {
241 comment := "\t// " + fmt.Sprintf(format, args...)
242 g.writeLine("%s", comment)
243}