The title means "Can we do lambda calculus in computers?" which is obviously yes,considering the reason this forum is here.
But can we use somewhat short and fast machine code to simulate lambda or iota calculus?
I have an idea:A function consists of an argument and an expression.
define parse_stuff(stuff):
if stuff is a function:
report list "lambda" argument body
......
define run_stuff(stuff,scope):
if item 1 of stuff="apply":
report run_stuff(item 3 of item 2 of stuff,list(item 2 of item 2 of stuff,item 3 of stuff) in front of scope)
....
The tricky part would be alpha conversion(i.e naming collisions)
I heard that deBrujin indices would help,but don't know how
To deal with protecting lambda-bound versions of NAME inside the big expression, you have to either avoid making a recursive call to DEEP REPLACE when you find a lambda expression with the same NAME as its argument, or else make sure to do the DEEP REPLACE calls from the inside out, so that when you call it on a big expression, instances of NAME in lambdas inside STUFF have already been turned into a unique ID that isn't NAME.
My approach is(because i either only use SK or only use ι)to use os.urandom to assign names to stuff in combinators since you know where they are.
for example,iota(f)=f(\xyz.xz(yz)(Starling))(\xy.x(Kestrel))
so we can number the variables:iota(0)=0(\123.13(23))(\45.4)
and let stuffNames=map {os.urandom()} over numbers from 0 to 5
That approach wouldn't work on lambda calculus that does not have a fixed number of different functions(i.e a diverse forest)/would work,but poorly as one has to manage a list of random stuffs as hashtable
Think about how you'd do it if you didn't have to worry about the same variable name used twice. You'd just substitute the actual argument for the formal parameter in the body of a lambda when you call it, right? That's what DEEP REPLACE will do.
But you are worried about name clashes. So either you ensure that the inner substitution happens first, in which case by the time you get around to the outer substitution the name doesn't conflict any more, or you write DEEP REPLACE so that if it sees the name you're trying to replace as the formal parameter of a lambda, you just report that lambda unchanged.
I replace the name FOO with the new name FOO-87 because that'll make it easier to debug, :~)
Would this work?(obviously it needs a way to print lambdas,but could this work as core logic?)
(c++ does not have block variables,so i had to use my method)
Also,would there be an easier method of making the Iota function?