A Journey into λCalculus

I’m playing around in Minetest, and I have an idea. In order to execute this idea, I’m going to need a simple programming language. Asking Google… implementing a simple programming language

7 lines of code, 3 minutes: Implement a programming language from scratch
Sounds good! Ridiculously simple, fast, and gives us a fully usable language. (I would’ve understood brainfuck better..) Let’s see what this language looks like:

(λ v . e)   anonymous function with argument v and returning e
(f v)       call function f with argument v
(λ a . a)   example: identity function (returns its argument)

And the scary one:
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))

Seems okay until I get to understanding that last example. If you’re curious about the steps I went through before I finally figured it out, here are my notes. I’m gonna skip to the good part:

(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))
two identity functions, let's name them I, & remove excess parenthesis
(λ f . (λ x . (f x))) I I
the syntax is still confusing me, let's make an "F" function
F(x) -> return (λ x . (f x))
F I I                          equivalent to ((F I) I)
substituting the function (identity) into our definition gives us
(λ x . (I x))                  which..is actually the same as the identity function
I(I)                           ..it all comes to returning the identity function

λ x . x

Now, at this point I’ve learned a few small tricks for my understanding, as well as how lambda calculus works in general.

Reduction

Solving a lambda calculus program is made of three (or 2.5) steps called reductions:

  • η-conversion (eta): Replace equivalent functions with simpler forms (λ x . f x) -> f
  • β-reduction (beta): Substitution (λ a . a) x -> x (essentially, THIS is solving it)
  • α-conversion (alpha): Rename conflicting names (λ a . a b) (λ a . a) -> (λ a . a b) (λ c . c)

References

This is where my journey ends for now. I started studying lambda calculus because of a desire to implement a simple programming language, but this will likely not satisfy my needs..at least not in this form. Here are additional resources:

Switches Suck

I don’t like switch statements, in any language. They seem unnecessarily verbose and error-prone, in fact I forgot the break statements in my example below on the first draft. Most of the time, you don’t want the fall-through feature, but you have to remember that extra word for each case to prevent that.

switch (n)
{
    case 1:
    // something useful
    break;
    case 2:
    // another useful option
    break;
    default:
    // nothing matched
}

I also really hate the indenting used in most examples (including my own), as it makes it more difficult to visually parse. I prefer to just create an object with keys based on the possible values, and access what you need directly.

-- we're gonna pretend these are useful functions dependent on a star's type..something to do with heat?
local default = {}           -- used for a unique key
local heat = {
  A = function() end,        -- pretend these are full of useful code
  B = function() end,
  G = function() end,        -- and so on
  [default] = function() end -- default which can't be accidentally chosen
}

-- make sure we don't error, and call default if needed
if heat[star.type] then
  heat[star.type]()
else
  heat[default]()
end

Better Fluid Storage

A while back, I posted a prototype fluid storage system with a mechanic for handling breaches in a pressurized system. I thought I’d be clever by storing fluids as a percentage of a defined volume and pressure. For a “simplified” system, it was quite complicated, and fundamentally flawed.

This time, it is straightforward. Keep track of the amounts of each fluid, a total sum, and volume of the container. Pressure is the sum divided by the volume, and the percent of a fluid is its amount divided by the total sum of all fluids.

tank = {
  volume: 200, sum: 300,
  contents: { hydrogen: 200, oxygen: 100 }
}
pressure = tank.sum / tank.volume -- 1.5
percent_hydrogen = tank.contents.hydrogen / tank.sum -- 0.67

Everything needed from a container can be accessed immediately or with a single calculation involving only two variables.

But what about hull breaches?

Fluids vs Mechanical Classes

I realized that I should define fluid containers very narrowly, all they need care about is a small set of numbers, and have a few functions to modify that state. Enter the Breach class.

Breach(fluidA, fluidB, volume)

Specify which fluid containers are interacting and the volume ( I guess technically it should be area) of the breach. Each update cycle moves the pressure difference multiplied by the volume (area) of the breach from the higher pressure container to the lower pressure container.

What about pumps? I have those, with a “volume” and a “rate” modifier to allow you to adjust how fast the pump works. Pumps only work in one direction, but have a function to reverse them.

Want only one fluid to go through..say, a filter? Made that as well. Valves, so that you can adjust flow rate, filter-pump combos for pushing just the right amount of one fluid, and one-way valves to allow pressure to escape but not allow any blowback.

The Flaws

  • Once pressure is equalized, contents do not mix between fluids.
  • All fluids have the same density. This probably isn’t that hard to fix, but is unneeded for my purposes.
  • All fluids mix. This may or may not be harder to fix depending on how it is approached.
  • Temperature isn’t simulated at all. I would love to have heat transfer and heat affecting density, but these details are not necessary for my current project.

The Code

As of publishing this article, I don’t have a library to give you, but I will update it as soon as I do release it. For now, here is where I have the beginnings of a library. No matter what, I can promise it will be available by the end of April (or upon request).

Grammar-Based Generation

To me, this is a new form of procedural generation. You declare specific rules for your desired content, and then a generator runs accordingly. I’ve only seen it used for text, but I’m sure the same technique works for anything. The simplest example is picking a random item from a list, and a slightly more complex version shows the power of defining a grammar:

grammar = {
  "first name": "Anna", "Belle", "John"
  "last name": "Brown", "Jameson", "Williams"
  "full name": "{first name} {last name}"
}

G(grammar, "full name") -- ex: Anna Williams

The syntax above is pseudocode for a generator I am working on. I plan to allow the use of a custom seed along with the generator so that you can do things like have uniquely generated people for a population, where only a lookup number needs to be stored (if you wish to remember a specific person).

It gets even more powerful when you make it possible to define multiple versions of the same grammar and use different ones depending on an object’s properties, and allow inline code within the grammars. Here’s an incomplete example based on my continuing efforts to build space games:

{
  "system name": {
    {
      props: { pulsar: true }
      "PSR {random(1000)}"
    }
    {
      props: { pulsar: false }
      "{Greek letter} {Latin name}"
      "{random(100)} {Latin genitive}"
      "{modern constellation} G{random(1000,9999)}.{random(1000,9999)}"
    }
  }
}

For this example, pulsars would get their traditional “PSR ###” names, while non-pulsars would get names based on differing classification methods.

I’m currently thinking about a game based on Aurora, but massively simplified and playable in-browser. Grammar-based content generation would play a very important role in this, from generating system names (as above) to NPC ship design.

References

Resources that helped me recognize the potential of grammars:


(Normally I would like to publish working code along with these posts, or some other form of useful data, but today we’re looking at a work-in-progress idea without even that much concrete form.)

Simplified Fluid Storage System

One of my game ideas involves constructing 2D spaceships, and the concept of a simplified system for storing fuel, oxygen, water – really any kind of fluid mixture – in storage tanks. Along with this, it allows simulating breaches between containers, hard vacuum, and the pressurized areas of the ship itself!

{ -- a rough approximation of Earth's atmosphere
  pressure: 1
  volume: 4.2e12 -- 4.2 billion km^3
  contents: {
    nitrogen: 0.775
    oxygen: 0.21
    argon: 0.01
    co2: 0.005
  }
}

{ -- hard vacuum
  pressure: 0
  volume: math.huge -- infinity
  -- the contents table will end up containing negative infinity of anything that leaks into the vacuum
}

It all comes down to storing a total pressure and volume per container, and a table of contents as percentages of the total mixture. The total amount of mass in the system can be easily calculated (volume * pressure), as can the amount of any item in the system ( volume * pressure * percent).

Breaches are stored as a reference in the container with a higher pressure, and a size value is added to the container with lower pressure (representing the size of the hole between them).

Limitations

  • Everything has the same density and mixes evenly.
  • There are no states of matter, everything is treated as a gas.
  • Attempting to directly modify the amount of a fluid is prone to floating-point errors it seems, while mixing containers via the breach mechanic is working as expected.

The code was written in MoonScript / Lua and is available here.