reduce lambda claculus with aws step functions
ce63fc5a — Kevin Downey 2 years ago
thats not right
37cb0f3b — Kevin Downey 3 years ago
print out input for step function
12d9c9a9 — Kevin Downey 3 years ago


browse  log 



You can also use your local clone with git send-email.

#Lions for Lambdas


Compiling call by need lambda calculus programs into ski combinator terms and writing amazon step functions to interpret ski combinator terms.


Print out a definition of a aws step function for interpreting a ski combinator term. This machine may be buggy. I am kind of scared to run it.

clj -X com.manigfeald.step/definition :print true | jq

Run a lambda calculus program locally, using the same machine specification used to generate the aws step function

clj -X com.manigfeald.program/run-program < foo.lion

Print out the ski combinator term for a program. Uses one of the bracket abstraction algorithms from http://okmij.org/ftp/tagless-final/ski.pdf (the worst one, haven't been able to wrap my head around the iterations on it)

clj -X com.manigfeald.program/compile-program :print true< foo.lion

Print out the parse tree of a program. Programs are parsed using parser combinators. The parse tree is a map of definitions to lambda terms.

clj -X com.manigfeald.program/parse-program :print true< foo.lion


For years now I've admired amazon step functions. I think they are really neat. But I have never gotten to use them in earnest.

I think one of the interesting things about them is how they obviously try and limit what you can do computationally. And this makes sense, they are intended to be a sort of bomb proof glue code. Limitting what the code can do makes it easier to plan for and handle different error conditions.

But they are built around a finite state machines, which are already very powerful computationally. Combined with the limitted json array manipulation functions, you can create stacks, and once you have two stacks you can compute all compuatable functions. There are still all kinds of other problems, the limit of the number of steps a machine can execute, the limit on the input size, etc. The code only understands ski terms, so even once you get it hooked to IO, you can only exchange ski terms with it, which is weird as hell.

I've also had this vague notion, The Very Large Lisp Machine, for a while. Bascially thinking about how do you build a virtual machine that "runs on a cloud" instead of running on a computer. And this is like one or two ??? steps in a list from that.

I have been reading the Compiling a Lisp series of blog posts, but yearned for something less introductory. Wandering around the web I stumbled on to https://crypto.stanford.edu/~blynn/compiler/ which is fantastic.


In the future I have day dreams of using step functions built in support for other aws services (like sqs) to do something like CSP or π-calculus.