Lambda Calculus
Check-in [5de740a47d]
Not logged in

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

Overview
Comment:changed AST to be LC-based (not cons-based)
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:5de740a47d7120e454d24311141e830c986df5ec
User & Date: bill 2012-03-17 22:55:14
Context
2012-03-18
03:07
AST code and docs check-in: 8c8c88f6d7 user: bill tags: trunk
2012-03-17
22:55
changed AST to be LC-based (not cons-based) check-in: 5de740a47d user: bill tags: trunk
2012-03-16
14:40
fixed lc.js and lcvm.js so they would load in stricter browsers check-in: cba31deacb user: bill tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Added hl.js.





























































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
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
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
/*
Copyright (C) 2012, Bill Burdick, Tiny Concepts: http://tinyconcepts.com/fs.pl/lambda.fsl

(licensed with ZLIB license)

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.

3. This notice may not be removed or altered from any source distribution.
*/

/*
High level representation of Lambda Calculus AST

Represent ASTs as LC cons-lists
*/

(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 v (f v)
_apply = \func arg f . f func arg
_prim = \name f . f name
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

    function isRef(f) {return f.lambda.id == _refId}
    function isLit(f) {return f.lambda.id == _litId}
    function isLambda(f) {return f.lambda.id == _lambdaId}
    function isApply(f) {return f.lambda.id == _applyId}
    function isPrim(f) {return f.lambda.id == _primId}
    function astType(f) {
	switch (f.lambda.id) {
	case _refId: return 'ref'
	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"))
})()

Changes to lazp.wiki.

11
12
13
14
15
16
17
18
19

20
21
22
23


24
25
26
27
28
29
30

Template Haskell demonstrates a perceived need for macros, even in a lazy language, like Haskell.  Macros expose the Lazp code-generator to developers which helps with creating external DSLs, among other things. Eval, which takes an AST as an argument, is the identity macro and the Lazp compiler can be exposed as a macro.

## Standard Functions

_lit v -- AST literal value  
_ref v -- AST variable reference  
_apply[ func, arg, arg, arg] -- AST function application (uses , and ] for varargs)  
_lambda var body -- AST lambda binding  

_macro var body -- AST macro binding  
_prim name -- AST primitive call  
cons head tail  
nil head tail -- normally, this is curried as just “nil”  


string head tail -- a string  
int head tail -- identify an int value  

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

function  







<

>




>
>







11
12
13
14
15
16
17

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Template Haskell demonstrates a perceived need for macros, even in a lazy language, like Haskell.  Macros expose the Lazp code-generator to developers which helps with creating external DSLs, among other things. Eval, which takes an AST as an argument, is the identity macro and the Lazp compiler can be exposed as a macro.

## Standard Functions

_lit v -- AST literal value  
_ref v -- AST variable reference  

_lambda var body -- AST lambda binding  
_apply[ func, arg, arg, arg] -- AST function application (uses , and ] for varargs)  
_macro var body -- AST macro binding  
_prim name -- AST primitive call  
cons head tail  
nil head tail -- normally, this is curried as just “nil”  
head list -- return the head of a list  
tail list -- return the tail of a list  
string head tail -- a string  
int head tail -- identify an int value  

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

function  

Changes to lc.js.

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
...
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
...
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
...
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
...
588
589
590
591
592
593
594







595
596
597
598
599
600
601
...
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
...
906
907
908
909
910
911
912

913






914
915
916
917
918
919
920
921
922
function lindex(list, element, i) {
    return list == null ? -1 : list.car == element ? i : lindex(list.cdr, element, i + 1)
}

function loadDefs(defs) {
    var d = defs.split('\n')

    LC.exprs = exprs = {}
    LC.code = {}
    LC.lambdas = lambdas = {}
    LC.hashed = hashed = {}
    LC.order = order = []
    funcCount = 1
    LC.L = L = null
    line = 1
    for (var index in d) {
	evalLine(d[index].trim(), true)
	line++
    }
    constructEnv()
    findCons();
................................................................................
	if (!noRebuild) {
	    for (var i = 0; i < order.length; i++) {
		if (order[i].name == name) {
		    order.splice(i, 1)
		}
	    }
	}
	LC.L = L = null
	order.push(expr)
	var hk = expr.expr.hashKey()
	if (!hashed[hk]) hashed[hk] = expr
	exprs[name] = expr
	return true
    } else {
	runExpr(txt.trim())
	return false
    }
}
function findCons() {
    if (L._cons) {
	lconsId = L._cons().lambda.body.body.id
	LC.lnil = lnil = L._nil().lambda
	Lnil = L._nil
	lnilId = LC.lnil.id
	Lhead = lcode2('head')
	Ltail = lcode2('tail')
	Lappend = lcode2('append')
    }
    if (LC.L._makeIO) {
	ioMonadId = LC.L._makeIO().lambda.body.id
	alertCmdId = LC.L._alertCmd().lambda.body.id
	promptCmdId = LC.L._promptCmd().lambda.body.id
	returnCmdId = LC.L._returnCmd().lambda.body.id
	bindCmdId = LC.L._bindCmd().lambda.body.id
	getCmds = lcode2('getCmds')
	LC.getAllCmds = getAllCmds = lcode2('getAllCmds')
	getCmdVal = lcode2('getCmdVal')
	getBindAction = lcode2('getBindAction')
	Ldl = lcode2('dl')
	LdlList = lcode2('dlList')
	LdlAppend = lcode2('dlAppend')
    }
}
................................................................................
}
function runExpr(str) {
	var expr = parse(str)

	expr && runCode(expr, constructEnv('function() {\nreturn ' + expr.ret([]).join("") + '\n}'))
}
function runCode(expr, code) {
	var res

	LC.historyExprs[historyCount] = expr
	try {
		constructEnv()
		history[historyCount] = res = code()
	} catch (err) {
		res = "Error: " + err.message
	}
	LC.lastResult = res
	LC.resultCode(expr, res, historyCount)
	historyCount++
	LC.L = L = null
}
//function getCommands(io) {
//    return getCmds(io)(Lnil)
//}
function stepIO(commands, lastRet) {
    for (;;) {
	if (isNil(commands)) {
................................................................................
    }
    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(){\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)
			if (order[i].name != "") {
				env.push("var " + order[i].cname + ' = ' + 'order[' + i + '].code')
				env.push("L." + order[i].cname + " = " + order[i].cname)
			}
		}
		for (var i = 0; i < history.length; i++) {
			env.push("var _" + charCodes['$'] + i + " = function(){return history[" + i + "]}")
		}
		if (history.length > 0) {
			env.push("var _" + charCodes['$'] + " = function(){return history[" + (history.length - 1) + "]}")
		}
		if (src) {
			env.push('return (' + src + ')')
		}
		env.push('\n})()')
		LC.L = L = {}
		var res
		try {
			res = eval(env.join("\n"))
		} catch (err) {
			res = "ERROR: " + err.message
		}
		return res
	}
}
function addToken(tok, group) {
	var pat = ''

	tokens[tok] = group
	tokenPat = null
}
................................................................................
	return func.memo || (func.memo = func())
    }

    out.lambda = func.lambda
    out.value = func.value
    return out
}








function setLambda(func, id, value) {
    func.lambda = lambdas[id]
    func.value = value
    return func
}

................................................................................
	return stream
    },
    isBound: function() {return !this.free || exprs[this.name] || this.name == "$" || (this.name.match('^\\$[0-9]+$') && Number(this.name.substring(1)) < history.length)},
    pass: function(stream, prefix) {
	if (this.isBound()) {
	    stream.push(pfx(prefix), this.cname)
	} else {
	    stream.push("(function(){return ", this.valueFunc(), "})")
	}
	return stream
    },
    isPrimitive: function() {return String(this.name).match(/^#(lazy|strict)$/)},
    apply: function(stream, prefix) {return this.ret(stream, prefix)},
    format: function() {return this.name},
    propagateTransform: function(transformer) {return this},
................................................................................
    cons: cons,
    index: index,
    getLambda: getLambda,
    isIOMonad: isIOMonad,
    stepIO: stepIO,
    isNil: isNil,
    getAllCmds: null,

}







if (typeof exports != 'undefined') {
    for (i in LC) {
	exports[i] = LC[i]
    }
}

return LC
})()







|
|
|
|
|

|







 







|













|













|







 







|

|
|
|
|
|
|
|
|
|
|
|







 







|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|







 







>
>
>
>
>
>
>







 







|







 







>

>
>
>
>
>
>









79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
...
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
...
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
...
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
...
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
...
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
...
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
function lindex(list, element, i) {
    return list == null ? -1 : list.car == element ? i : lindex(list.cdr, element, i + 1)
}

function loadDefs(defs) {
    var d = defs.split('\n')

    exp("exprs", LC.exprs = exprs = {})
    exp("code", LC.code = {})
    exp("lambdas", LC.lambdas = lambdas = {})
    exp("hashed", LC.hashed = hashed = {})
    exp("order", LC.order = order = [])
    funcCount = 1
    exp("L", LC.L = L = null)
    line = 1
    for (var index in d) {
	evalLine(d[index].trim(), true)
	line++
    }
    constructEnv()
    findCons();
................................................................................
	if (!noRebuild) {
	    for (var i = 0; i < order.length; i++) {
		if (order[i].name == name) {
		    order.splice(i, 1)
		}
	    }
	}
	exp("L", LC.L = L = null)
	order.push(expr)
	var hk = expr.expr.hashKey()
	if (!hashed[hk]) hashed[hk] = expr
	exprs[name] = expr
	return true
    } else {
	runExpr(txt.trim())
	return false
    }
}
function findCons() {
    if (L._cons) {
	lconsId = L._cons().lambda.body.body.id
	exp("lnil", LC.lnil = lnil = L._nil().lambda)
	Lnil = L._nil
	lnilId = LC.lnil.id
	Lhead = lcode2('head')
	Ltail = lcode2('tail')
	Lappend = lcode2('append')
    }
    if (LC.L._makeIO) {
	ioMonadId = LC.L._makeIO().lambda.body.id
	alertCmdId = LC.L._alertCmd().lambda.body.id
	promptCmdId = LC.L._promptCmd().lambda.body.id
	returnCmdId = LC.L._returnCmd().lambda.body.id
	bindCmdId = LC.L._bindCmd().lambda.body.id
	getCmds = lcode2('getCmds')
	exp("getAllCmds", LC.getAllCmds = getAllCmds = lcode2('getAllCmds'))
	getCmdVal = lcode2('getCmdVal')
	getBindAction = lcode2('getBindAction')
	Ldl = lcode2('dl')
	LdlList = lcode2('dlList')
	LdlAppend = lcode2('dlAppend')
    }
}
................................................................................
}
function runExpr(str) {
	var expr = parse(str)

	expr && runCode(expr, constructEnv('function() {\nreturn ' + expr.ret([]).join("") + '\n}'))
}
function runCode(expr, code) {
    var res

    LC.historyExprs[historyCount] = expr
    try {
	constructEnv()
	history[historyCount] = res = code()
    } catch (err) {
	res = "Error: " + err.message
    }
    exp("lastResult", LC.lastResult = res)
    LC.resultCode(expr, res, historyCount)
    historyCount++
    exp("L", LC.L = L = null)
}
//function getCommands(io) {
//    return getCmds(io)(Lnil)
//}
function stepIO(commands, lastRet) {
    for (;;) {
	if (isNil(commands)) {
................................................................................
    }
    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)
	    if (order[i].name != "") {
		env.push("var " + order[i].cname + ' = ' + 'order[' + i + '].code')
		env.push("L." + order[i].cname + " = " + order[i].cname)
	    }
	}
	for (var i = 0; i < history.length; i++) {
	    env.push("var _" + charCodes['$'] + i + " = function(){return history[" + i + "]}")
	}
	if (history.length > 0) {
	    env.push("var _" + charCodes['$'] + " = function(){return history[" + (history.length - 1) + "]}")
	}
	if (src) {
	    env.push('return (' + src + ')')
	}
	env.push('\n})()')
	exp("L", LC.L = L = {})
	var res
	try {
	    res = eval(env.join("\n"))
	} catch (err) {
	    res = "ERROR: " + err.message
	}
	return res
    }
}
function addToken(tok, group) {
	var pat = ''

	tokens[tok] = group
	tokenPat = null
}
................................................................................
	return func.memo || (func.memo = func())
    }

    out.lambda = func.lambda
    out.value = func.value
    return out
}

function createValue(val) {
    var func = function(){return val}

    func.value = true
    return func
}

function setLambda(func, id, value) {
    func.lambda = lambdas[id]
    func.value = value
    return func
}

................................................................................
	return stream
    },
    isBound: function() {return !this.free || exprs[this.name] || this.name == "$" || (this.name.match('^\\$[0-9]+$') && Number(this.name.substring(1)) < history.length)},
    pass: function(stream, prefix) {
	if (this.isBound()) {
	    stream.push(pfx(prefix), this.cname)
	} else {
	    stream.push("createValue(", this.valueFunc(), ")")
	}
	return stream
    },
    isPrimitive: function() {return String(this.name).match(/^#(lazy|strict)$/)},
    apply: function(stream, prefix) {return this.ret(stream, prefix)},
    format: function() {return this.name},
    propagateTransform: function(transformer) {return this},
................................................................................
    cons: cons,
    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
	}
    }

if (typeof exports != 'undefined') {
    for (i in LC) {
	exports[i] = LC[i]
    }
}

return LC
})()

Changes to lcvm.js.

758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
	CTX_PARENT: CTX_PARENT,
	CTX_RESULT: CTX_RESULT,
	CTX_BINDING: CTX_BINDING,
	addFunc: addFunc,
	getExpr: getExpr,
	getEntry: getEntry,
    }



    if (typeof exports != 'undefined') {
	for (i in obj) {
	    exports[i] = obj[i]
	}
    }
    return obj
})()







<
<








758
759
760
761
762
763
764


765
766
767
768
769
770
771
772
	CTX_PARENT: CTX_PARENT,
	CTX_RESULT: CTX_RESULT,
	CTX_BINDING: CTX_BINDING,
	addFunc: addFunc,
	getExpr: getExpr,
	getEntry: getEntry,
    }



    if (typeof exports != 'undefined') {
	for (i in obj) {
	    exports[i] = obj[i]
	}
    }
    return obj
})()