Summary of Lambda Calculus in a Can using Arduino
LambdaCan packs a Lambda Calculus reducer onto an Arduino Diecimila and mounts it inside a cough drop can, creating a USB-connectable microcontroller interpreter for lambda expressions. The project includes software to build and upload to the board, mechanical steps to mount the board in the can with epoxy putty, and instructions for interacting via a serial terminal or running a POSIX build on a host.
Parts used in the LambdaCan:
- Arduino Diecimila board (Atmel ATmega168)
- Cough drop can (metal can)
- Epoxy putty
- Small plastic bag (to protect the board during epoxy placement)
- Spray paint
- USB cable
- GNU/Linux PC (for building/uploading and interacting) or POSIX-capable host
You can get soup in a can. You can get bread in a can (*). Now the long wait is over! You can finally get Lambda Calculus in a can.
Project LambdaCan is an amusing exercise in absurdity. It implements a reducer (interpreter) for the Lambda Calculus, a formal system (programming language) developed by Alonzo Church in the 1930’s to attack the deepest mathematical problem of the day. This was the Entscheidungsproblem, the question of whether or not there exists an algorithm capable of deciding the truth or falsehood of all statements in mathematics.
Project LambdaCan takes this tool for exploring the most profound mathematical problems and implements it on a microcontroller better suited to the most mundane of tasks, like running a vending machine or microwave oven. And it sticks the microcontroller in a can that you can connect to your PC using a USB cable.
Of course, the extreme overhead involved in supporting the painfully abstract Lambda Calculus notation makes LambdaCan struggle to compute arithmetic as simple as 11 + 12 = 23. The microcontroller would perform much better if programmed in its native language. Furthermore, the very idea of plugging a LambdaCan coprocessor into a typical PC to perform computations is absurd since the PC could undoubtedly handle much larger computations faster on its own.
But… hey, it’s Lambda Calculus in a can!
Build your own LambdaCan
LambdaCan is essentially an Arduino Diecimila board mounted in a cough drop can using epoxy putty. The Diecimila board uses an Atmel ATmega168 microcontroller with 16KB of flash RAM and 1KB of SRAM. It is a favorite of the microcontroller hacking community with plenty of Free software support available online. Here are the steps:
- Download the LambdaCan software here. Follow the instructions in the tarball to build it and upload it to the Diecimila board.
- Cut a hole in the can for the Diecimila’s USB connector to poke through.
- Put the Diecimila board in a small plastic bag. Cover the bottom edges of the can with epoxy putty. While the putty is still soft, mash the plastic-wrapped Diecimila board into it until the board is in position with its USB connector poking out of the hole in the can. The plastic bag will keep the sticky epoxy off of your board. Remove the board and let the epoxy putty harden. Discard the plastic bag.
- Spraypaint the can. Let it dry.
- Put the Diecimila board into the can. The hardened expoy putty should ensure that it remains in the proper position. Close can. Done!
FYI:
- You can open the can if you need to hit the board’s reset button.
- Since we used the epoxy putty only to harden into a shape to accept the board and not to glue the board in place, if you want you can remove the board and use it for something else later.
Using LambdaCan
To use LambdaCan, boot your favorite GNU/Linux machine and then plug LambdaCan in to a free USB port. Run
screen /dev/ttyUSB0 9600
in a shell to interact with LambdaCan. Alternately, the instructions included with the source can tell you how to build a POSIX version of the software that you can run in a shell without needing the LambdaCan hardware.
The syntax of the Lambda Calculus is very simple: it has variables like x and functions like (\x.x). This function, for example, takes one argument x and returns the value of that argument—it’s the identity function. In Church’s original syntax, the \ would be a lambda. The period is a little syntactic sugar to make the function more readable by visually separating parameters from body. The Lambda Calculus also includes applications of functions. For example, ((\x.x) A) applies the above identity function to the argument A. Reducing expressions, at least in the simplest cases, amounts to syntactically substituting arguments for formal parameters in function bodies, like so:
For more detail: Lambda Calculus in a Can using Arduino
- What is LambdaCan?
LambdaCan is a project that implements a Lambda Calculus reducer on an Arduino Diecimila mounted inside a cough drop can, accessible over USB. - What microcontroller board is used in LambdaCan?
The project uses an Arduino Diecimila board with an Atmel ATmega168 microcontroller. - How do you build and upload the software to LambdaCan?
Download the LambdaCan software tarball and follow the included build and upload instructions to program the Diecimila board. - How is the Diecimila mounted inside the can?
Cut a hole for the USB connector, line the can bottom with epoxy putty, press the plastic-wrapped board into the putty until positioned, let the putty harden, remove the bag, then insert the board so the USB connector protrudes. - Can the board be removed from the can later?
Yes; the epoxy putty is shaped to accept the board rather than glued to it, so the board can be removed for other use. - How do you interact with LambdaCan from a host machine?
On GNU/Linux, plug LambdaCan into USB and run screen /dev/ttyUSB0 9600 to interact; a POSIX version of the software can also be built to run without hardware. - Does LambdaCan perform arithmetic efficiently?
No; due to Lambda Calculus overhead on a small microcontroller, it struggles with simple arithmetic and is more of an amusing exercise than a practical coprocessor. - Can you open the can to access the reset button?
Yes; the can can be opened if you need to press the board's reset button.
