Lambda Calculus
Check-in [3a53b7c1a5]
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:getting ready for self-hosting
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:3a53b7c1a5f0d56ad4042707dccf03d9531ab544
User & Date: bill 2012-03-18 06:07:16
Context
2012-03-18
06:08
notes check-in: 49ccfcfe64 user: bill tags: trunk
06:07
getting ready for self-hosting check-in: 3a53b7c1a5 user: bill tags: trunk
03:07
AST code and docs check-in: 8c8c88f6d7 user: bill tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to hl.js.

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
..
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

105

106
107
108
109
110
111
112
113
114
115
116
117
118















































119
120
121

122



123
124



125
126

127
128




129
130

131
132






133
134
135
136
137
138
139
140
141







142
143





144
145










146
147
148

149
150
151












152
153
154
155
156
157
158
159
160
161
162

163
164
165
166
167
168
169
170
171
172
173















174










175

(function(){
    var LC=require('./lc.js')
    var LAZP=require('./lazp.js')
    var astDefs = LAZP.hereDoc(function(){/*
_lit = \x f . f x
_ref = \x f . f x
#lambda func, where func = \var . (body)
_lambda = \f g v . g v (f v)
_apply = \func arg f . f func arg
_prim = \arg rest f . f arg rest -- rest is either a _prim, _lit, or _ref

true = \x y . x

*/})
    var moreDefs = LAZP.hereDoc(function(){/*
t1 = _ref bubba
t2 = _lambda \x ._lit hello
t3 = _lambda \x . _lit true
t4 = _lambda \x . _ref x
t5 = _lambda \x . _lambda \y . _ref x






*/})

    var _refId
    var _litId
    var _lambdaId
    var _applyId
    var _primId
................................................................................
	case _litId: return 'lit'
	case _lambdaId: return 'lambda'
	case _applyId: return 'apply'
	case _primId: return 'prim'
	}
    }
    function resolve(v){return typeof v == 'function' ? v() : v}
    function lFirst(){return function(a) {return a}}
    function first(){return function(a) {return a}}
    function second(){return function(a) {return function(b){return b}}}
    var gen = 0
    function astPrint(ast, res) {
	var isFirst = !res

	if (isFirst) gen = 0
	res = res || []
	switch (ast.lambda && ast.lambda.id) {
	case _refId:
	    res.push('ref ')
	    var val = ast(first)()
	    res.push(val.lambda ? val.lambda.toString() : "{" + val + "}")
	    break
	case _litId:
	    res.push('lit ')
	    var val = ast(first)()

	    res.push(val.lambda ? val.lambda.toString() : "{" + val + "}")
	    break
	case _lambdaId:
	    var v = "VAR" + gen++
	    var vf = function(){return v}

	    res.push('lambda ')
	    res.push(ast(first)(vf))
	    res.push(' . ')
	    astPrint(resolve(ast(second)(vf)), res)
	    break
	case _applyId:
	    res.push('apply ')
	    astPrint(ast(first), res)

	    astPrint(ast(second), res)

	    break
	case _primId:
	    res.push('prim ')
	    astPrint(ast(first), res)
	    break
	default:
	    res.push("WHA???")
//	    res.push(ast().lambda ? ast().lambda.toString() : "{" + ast() + "}")
	    break
	}
	return isFirst && res.join('')
    }
















































    function compile(name, ast, res) {
	var isFirst = !res


	res = res || []



	switch (ast.lambda && ast.lambda.id) {
	case _refId:



	    res.push('ref ')
	    astPrint(ast(first), res)

	    break
	case _litId:




	    res.push('lit ')
	    astPrint(ast(first), res)

	    break
	case _lambdaId:






	    res.push('lambda ')
	    res.push(ast(first))
	    res.push(' . ')
	    astPrint(resolve(ast(second)), res)
	    break
	case _applyId:
	    res.push('apply ')
	    astPrint(ast(first), res)
	    astPrint(ast(second), res)







	    break
	case _primId:





	    res.push('prim ')
	    astPrint(ast(first), res)










	    break
	default:
	    res.push(ast().lambda ? ast().lambda.toString() : "{" + ast() + "}")

	    break
	}
	return isFirst && res.join('')












    }

    LC.loadDefs(astDefs + moreDefs)
    _refId = LC.L.__ref().lambda.body.id
    _litId = LC.L.__lit().lambda.body.id
    _lambdaId = LC.L.__lambda().lambda.body.id
    _applyId = LC.L.__apply().lambda.body.body.id
    _primId = LC.L.__prim().lambda.body.id
    console.log("_lambdaId: " + _lambdaId)
    console.log("t1: " + LC.L._t1())
    console.log("t1.id: " + LC.L._t1().lambda.id)

    console.log("t2: " + LC.L._t2())
    console.log("t2 lambda: " + LC.L._t2().lambda)
    console.log("t2 id: " + LC.L._t2().lambda.id)
    console.log("t2 type: " + astType(LC.L._t2()))
    console.log("t2 var: " + LC.L._t2()(first))
    console.log("t2 body: " + LC.L._t2()(second)().lambda)
    console.log("t2: " + astPrint(LC.L._t2()))
    console.log("t3: " + astPrint(LC.L._t3()))
    console.log("t4: " + astPrint(LC.L._t4()))
    console.log("t5: " + astPrint(LC.L._t5()))
    console.log("internalEval = " + LC.L.internalEval)















    console.log("_lit = " + LC.L.internalEval("__lit"))










})()







<
|


>
|
>







>
>
>
>
>
>







 







<












|





|






|

|


|

>
|
>







<





>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|


>

>
>
>


>
>
>
|
<
>


>
>
>
>
|
<
>


>
>
>
>
>
>
|
<
|
<


<
|
|
>
>
>
>
>
>
>


>
>
>
>
>
|
<
>
>
>
>
>
>
>
>
>
>


<
>


|
>
>
>
>
>
>
>
>
>
>
>
>











>










|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>

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
..
72
73
74
75
76
77
78

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

187
188
189
190
191
192
193
194

195
196
197
198
199
200
201
202
203
204

205

206
207

208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

225
226
227
228
229
230
231
232
233
234
235
236

237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302

(function(){
    var LC=require('./lc.js')
    var LAZP=require('./lazp.js')
    var astDefs = LAZP.hereDoc(function(){/*
_lit = \x f . f x
_ref = \x f . f x

_lambda = \f g v . g (f v)
_apply = \func arg f . f func arg
_prim = \arg rest f . f arg rest -- rest is either a _prim, _lit, or _ref
# lit is the same def as ref
# apply is the same def as prim
# these are for identification purposes
*/})
    var moreDefs = LAZP.hereDoc(function(){/*
t1 = _ref bubba
t2 = _lambda \x ._lit hello
t3 = _lambda \x . _lit true
t4 = _lambda \x . _ref x
t5 = _lambda \x . _lambda \y . _ref x
t6 = _lambda \x . _lambda \y . _ref y
tlit = _lambda \x . _lambda \f . _apply (_ref f) (_ref x)
tref = _lambda \x . _lambda \f . _apply (_ref f) (_ref x)
tlambda = _lambda \f . _lambda \g . _lambda \v . _apply (_ref g) (_apply (_ref f) (_ref v))
tapply = _lambda \func . _lambda \arg . _lambda \f . _apply (_apply (_ref f) (_ref func)) (_ref arg)
tprim =  _lambda \arg . _lambda \rest . _lambda \f . _apply (_apply (_ref f) (_ref arg)) (_ref rest)
*/})

    var _refId
    var _litId
    var _lambdaId
    var _applyId
    var _primId
................................................................................
	case _litId: return 'lit'
	case _lambdaId: return 'lambda'
	case _applyId: return 'apply'
	case _primId: return 'prim'
	}
    }
    function resolve(v){return typeof v == 'function' ? v() : v}

    function first(){return function(a) {return a}}
    function second(){return function(a) {return function(b){return b}}}
    var gen = 0
    function astPrint(ast, res) {
	var isFirst = !res

	if (isFirst) gen = 0
	res = res || []
	switch (ast.lambda && ast.lambda.id) {
	case _refId:
	    res.push('ref ')
	    var val = ast(first)()
	    res.push(val.lambda ? "WHA?" : val)
	    break
	case _litId:
	    res.push('lit ')
	    var val = ast(first)()

	    res.push(val.lambda ? "{" + val.lambda.toString() + "}" : val)
	    break
	case _lambdaId:
	    var v = "VAR" + gen++
	    var vf = function(){return v}

	    res.push('lambda ')
	    res.push(v)
	    res.push(' . ')
	    astPrint(resolve(ast(first)(vf)), res)
	    break
	case _applyId:
	    res.push('apply (')
	    astPrint(ast(first), res)
	    res.push(') (')
	    astPrint(ast(second)(), res)
	    res.push(')')
	    break
	case _primId:
	    res.push('prim ')
	    astPrint(ast(first), res)
	    break
	default:
	    res.push("WHA???")

	    break
	}
	return isFirst && res.join('')
    }

    function memoize(func) {
	var out = function() {
	    return func.memo || (func.memo = func())
	}

	out.ast = func.ast
	out.value = func.value
	return out
    }

    /**
       A context is program scope
     */
    function createContext() {
	var ctx = (function(){
	    function id(func, id) {
		func.context = C
		func.id = id
		return func
	    }

	    function addAst(ast) {
		if (!ast.id) {
		    C.astsById.push(ast)
		    ast.id = C.astsById.length
		}
		return ast
	    }

	    var C = {
		astsById: [],
		addAst: addAst,
		id: id,
		eval: function(str){return eval(str)},
		subcontext: function(){return function(str){return eval(str)}},
	    }

	    return C
	})()

	ctx.funcId = 0
	return ctx
    }

    var CTX = createContext()

    function ocompile(ast) {return compile(ast, null, null, true)}
    function compile(ast, res, ctx, deref, prim, cont) {
	var isFirst = !res

	if (isFirst) gen = 0
	res = res || []
	ctx = ctx || CTX.subcontext()
	ctx.curLit = 0
	CTX.addAst(ast)
	switch (ast.lambda && ast.lambda.id) {
	case _refId:
	    var val = ast(first)()

	    if (val.lambda) throw new Error("attempt to use lambda as a variable")
	    res.push(val)

	    if (deref) res.push("()")
	    break
	case _litId:
	    var lit = "lit" + ctx.curLit++

	    ctx("var " + lit)
	    ctx("(function(v){" + lit + " = v})")(ast(first)())
	    res.push(lit)

	    if (deref) res.push("()")
	    break
	case _lambdaId:
	    var v = "VAR" + gen++
	    var vf = function(){return v}

	    if (!deref) res.push("(function(){return ")
	    res.push("id(function(" + v + "){return ")
	    compile(resolve(ast(first)(vf)), res, ctx)
	    res.push("}, " + ast.id + ")")

	    if (!deref)	res.push("})")

	    break
	case _applyId:

	    var func = ast(first)
	    var arg = ast(second)()

	    if (!deref) res.push("(function(){return ")
	    compile(func, res, ctx, true)
	    res.push("(")
	    compile(arg, res, ctx)
	    res.push(")")
	    if (!deref)	res.push("})")
	    break
	case _primId:
	    var arg = ast(first)
	    var rest = ast(rest)

	    if (prim) {
		if (cont) {
		    res.push(", ")

		}
		compile(arg, res, ctx, false, true, true, true)
	    } else {
		if (!deref) res.push("(function(){return ")
		compile(arg, res, ctx, true, false)
		res.push("(")
		compile(rest, res, ctx, true, false, true)
		res.push(")")
		if (!deref)	res.push("})")
	    }
	    break
	default:

	    res.push("'WHA???'")
	    break
	}
	return isFirst && [res.join(''), ctx]
    }

    function run(cmp, arg) {
	try {
	    return cmp[1]("(" + cmp[0] + ")")(arg)
	} catch (err) {
	    console.log(err.stack)
	}
    }

    function laz(val) {
	return function(){return val}
    }

    LC.loadDefs(astDefs + moreDefs)
    _refId = LC.L.__ref().lambda.body.id
    _litId = LC.L.__lit().lambda.body.id
    _lambdaId = LC.L.__lambda().lambda.body.id
    _applyId = LC.L.__apply().lambda.body.body.id
    _primId = LC.L.__prim().lambda.body.id
    console.log("_lambdaId: " + _lambdaId)
    console.log("t1: " + LC.L._t1())
    console.log("t1.id: " + LC.L._t1().lambda.id)
    console.log("t1: " + astPrint(LC.L._t1()))
    console.log("t2: " + LC.L._t2())
    console.log("t2 lambda: " + LC.L._t2().lambda)
    console.log("t2 id: " + LC.L._t2().lambda.id)
    console.log("t2 type: " + astType(LC.L._t2()))
    console.log("t2 var: " + LC.L._t2()(first))
    console.log("t2 body: " + LC.L._t2()(second)().lambda)
    console.log("t2: " + astPrint(LC.L._t2()))
    console.log("t3: " + astPrint(LC.L._t3()))
    console.log("t4: " + astPrint(LC.L._t4()))
    console.log("t5: " + astPrint(LC.L._t5()))
    console.log("t6: " + astPrint(LC.L._t6()))
    console.log("compile t1: " + ocompile(LC.L._t1())[0])
    console.log("run t1: " + run(ocompile(LC.L._t1()), null))
    console.log("compile t2: " + ocompile(LC.L._t2())[0])
    console.log("run t2: " + run(ocompile(LC.L._t2()), null))
    console.log("compile t3: " + ocompile(LC.L._t3())[0])
    console.log("run t3 'a' 'b': " + run(ocompile(LC.L._t3()), null))
    console.log("t3 'a' 'b': " + run(ocompile(LC.L._t3()), laz("a"))()(laz("b"))())
    console.log("compile t4: " + ocompile(LC.L._t4())[0])
    console.log("run t4 'a': " + run(ocompile(LC.L._t4()), 'a'))
    console.log("compile t5: " + ocompile(LC.L._t5())[0])
    console.log("run t5 'a' 'b': " + run(ocompile(LC.L._t5()), 'a')('b'))
    console.log("compile t6: " + ocompile(LC.L._t6())[0])
    console.log("run t6 'a' 'b': " + run(ocompile(LC.L._t6()), 'a')('b'))
    console.log("_refId: " + _refId)
    console.log("_ref: " + LC.L.__ref)
    console.log("_litId: " + _litId)
    console.log("_lit: " + LC.L.__lit)
    console.log("_lambdaId: " + _lambdaId)
    console.log("_lambda: " + LC.L.__lambda)
    console.log("_applyId: " + _applyId)
    console.log("_apply: " + LC.L.__apply)
    console.log("_primId: " + _primId)
    console.log("_prim: " + LC.L.__prim)
    console.log("tlit: " + astPrint(LC.L._tlit()))
    console.log("compile tlit: " + ocompile(LC.L._tlit())[0])
    console.log("run tlit: " + run(ocompile(LC.L._tlit()), laz('a'))()(laz(function(x){return "[[" + x() + "]]"}))())
})()

Changes to lazp.wiki.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
_apply func arg -- function application: func can be any AST function except a _prim  
_prim arg rest -- primitive call: rest is either a _prim, _lit, or _ref  

The AST functions serve as an embedded DSL.
## Examples

eval x = 𝛍x . x  
apply func arg = 𝛍 func arg . _apply[ _lit func, _lit arg]  
compile code-string -- function returning AST  

## Parser macros  

How these work depends on the parser you use, but they run Lazp code at parse-time.  Parser macros can implement things like splicing primitive values into the AST and importing libraries, but the most important thing is that they allow developers to extend the parser.  Parser macros can be activated using a standard parser macro (of course :) ).

## Implementation







|







19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
_apply func arg -- function application: func can be any AST function except a _prim  
_prim arg rest -- primitive call: rest is either a _prim, _lit, or _ref  

The AST functions serve as an embedded DSL.
## Examples

eval x = 𝛍x . x  
apply func arg = 𝛍 func arg . _apply (_lit func) (_lit arg)  
compile code-string -- function returning AST  

## Parser macros  

How these work depends on the parser you use, but they run Lazp code at parse-time.  Parser macros can implement things like splicing primitive values into the AST and importing libraries, but the most important thing is that they allow developers to extend the parser.  Parser macros can be activated using a standard parser macro (of course :) ).

## Implementation

Changes to lc.js.

246
247
248
249
250
251
252
253

254
255
256
257
258
259
260
...
914
915
916
917
918
919
920

921
922
923
924
925
926
927
    return l
}
function elements(l, first, nosubs) {
    return isNil(l) ? '' : ((first ? '' : ', ') + pretty(Lhead(l), nosubs) + elements(Ltail(l), false, nosubs))
}
function constructEnv(src) {
    if (!L || src) {
	var env = ['(function(){\nL.internalEval = function(expr){return eval(expr)}\n']


	for (var i = 0; i < order.length; i++) {
	    if (order[i].name != "") {
		env.push('\n// ' + order[i].name + ' = ' + order[i].expr.format(true, true))
		if (order[i].usesFree) env.push('//WARNING, line ' + line + ': uses free variables: ' + order[i].usesFree)
	    }
	    env.push('LC.code[order[' + i + '].name] = order[' + i + '].code = ' + order[i].src)
................................................................................
    index: index,
    getLambda: getLambda,
    isIOMonad: isIOMonad,
    stepIO: stepIO,
    isNil: isNil,
    getAllCmds: null,
    value: value,

}

    function exp(key, value) {
	if (typeof exports != 'undefined') {
	    exports[key] = value
	}
    }







|
>







 







>







246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
...
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
    return l
}
function elements(l, first, nosubs) {
    return isNil(l) ? '' : ((first ? '' : ', ') + pretty(Lhead(l), nosubs) + elements(Ltail(l), false, nosubs))
}
function constructEnv(src) {
    if (!L || src) {
	// evalFactory creates a name space for compiling
	var env = ['(function(){\nL.evalFactory = function(){return function(expr){return eval(expr)}}\n']

	for (var i = 0; i < order.length; i++) {
	    if (order[i].name != "") {
		env.push('\n// ' + order[i].name + ' = ' + order[i].expr.format(true, true))
		if (order[i].usesFree) env.push('//WARNING, line ' + line + ': uses free variables: ' + order[i].usesFree)
	    }
	    env.push('LC.code[order[' + i + '].name] = order[' + i + '].code = ' + order[i].src)
................................................................................
    index: index,
    getLambda: getLambda,
    isIOMonad: isIOMonad,
    stepIO: stepIO,
    isNil: isNil,
    getAllCmds: null,
    value: value,
    memoize: memoize,
}

    function exp(key, value) {
	if (typeof exports != 'undefined') {
	    exports[key] = value
	}
    }