# Lambda calculus from Bounded Storage Machines?

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

Sure, just make a block

and then you can

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.

Oh.ok(pretends to understand)

When do you use deep replace uniquify?

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

Yeah that'll work.

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, :~)

Oh.Now I know.Nice!

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?

Yeah, don't use random numbers! :~)

Oh ok,but I mean how can I sqeeze the Iota function so that it doesn't have that much nested object references

TBH I can't make any sense of that part of your code. Everything is done with small integers, no abstract data type or anything.

?
I did define an abstract type

There's all that stuff about a.b.c.d=foo[3].

Oh so do you mean that without using abstract types I can remove the nested object references?

No, I mean I just saw that and got dizzy so I have no idea what your code does. Sorry...

You're welcome