GitHub - simonl/Lambda-Compiler: A toy compiler for the untyped lambda calculus (2011)

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 6 Commits
Web		Web
BMI$1.class		BMI$1.class
BMI$Unit.class		BMI$Unit.class
BMI$Units.class		BMI$Units.class
BMI.class		BMI.class
BMI.java		BMI.java
Check.hs		Check.hs
Cleaner.hs		Cleaner.hs
CleanerClos.hs		CleanerClos.hs
CleanerRepr.hs		CleanerRepr.hs
Closures.hs		Closures.hs
ExprFold.hs		ExprFold.hs
Expressions.hs		Expressions.hs
FOmega.hs		FOmega.hs
Infix.hs		Infix.hs
Lexer.hs		Lexer.hs
Lisp.hs		Lisp.hs
Main.hs		Main.hs
Main2.hs		Main2.hs
Parser.hs		Parser.hs
README		README
Regexp.hs		Regexp.hs
Repl.hs		Repl.hs
SharedArrayTests$1.class		SharedArrayTests$1.class
SharedArrayTests$2.class		SharedArrayTests$2.class
SharedArrayTests$Array.class		SharedArrayTests$Array.class
SharedArrayTests$Func.class		SharedArrayTests$Func.class
SharedArrayTests$LentArray.class		SharedArrayTests$LentArray.class
SharedArrayTests$Ref.class		SharedArrayTests$Ref.class
SharedArrayTests$SharedArray.class		SharedArrayTests$SharedArray.class
SharedArrayTests.class		SharedArrayTests.class
SharedArrayTests.java		SharedArrayTests.java
Simple.hs		Simple.hs
Thunkify.hs		Thunkify.hs
Typed.hs		Typed.hs
Uniques.hs		Uniques.hs
Web.hs		Web.hs
Web.py		Web.py
defs.sysf		defs.sysf
gui.py		gui.py
index.html		index.html
index.shtml		index.shtml
program.fo		program.fo
shtml.hs		shtml.hs

Repository files navigation

A toy compiler for the untyped lambda calculus

To do:
	- Test the generated assembly!!!
	- Carry types through
	- Do tail calls properly
	- Separate into files
	- Merge AST data types

Examples:

the Y combinator:
	
	\f. (\x.x x) (\y.f (y y))

I first add explicit thunks:

	\f. (\x. x () x) (\() y. f () (\(). (y () y)))

The continuation passing transform then sequentializes the operations:

	(){
		return: (f){
			x = (){
				return: (y){
					forced_f = f()
					thunk = (){
						forced_y = y()
						return: forced_y(y)
					}
					return: forced_f(thunk)
				}
			}
			forced_x = x()
			return: forced_x(x)
		}
	}

and then it is closure converted, with global labels.
Also, tuples are initialized in many steps through mutation,
here's just a smal portion:

	x_code: (env, y) {
		f = env[1]
		code = f[0]
		forced_f = code(f)
		thunk = 2[]
		thunk[0] := thunk_code
		thunk[1] := y
		code = forced_f[0]
		return: code(forced_f, thunk)
	}

and the corresponding assembly:

	x_code:
	subl $8, %esp
	movl %eax, 0(%esp)
	movl %ebx, 4(%esp)
	movl 0(%esp), %eax
	movl 4(%eax), %eax
	subl $4, %esp
	movl %eax, 0(%esp)
	movl 0(%esp), %eax
	movl 0(%eax), %eax
	subl $4, %esp
	movl %eax, 0(%esp)
	movl 4(%esp), %eax
	movl 0(%esp), %edi
	call *%edi
	subl $4, %esp
	movl %eax, 0(%esp)
	movl $2, %eax
	call __malloc__
	subl $4, %esp
	movl %eax, 0(%esp)
	movl 0(%esp), %eax
	movl $thunk_code, %ebx
	movl %ebx, 0(%eax)
	movl 0(%esp), %eax
	movl 20(%esp), %ebx
	movl %ebx, 4(%eax)
	movl 4(%esp), %eax
	movl 0(%eax), %eax
	subl $4, %esp
	movl %eax, 0(%esp)
	movl 8(%esp), %eax
	movl 4(%esp), %ebx
	movl 0(%esp), %edi
	call *%edi
	addl $28, %esp
	ret