DEV Community: Haile Lagi

It's legos all the way down

Haile Lagi — Fri, 17 Feb 2023 09:46:58 +0000

Introduction

Often as folks who create useful software things we tend to think of ourselves as people who write software for the mythical "user". A "user" clicks a button and
something magical happens. This is commonly reffered to as an abstraction.
Abstractions are all around us in software and clever programmers create good abstractions for other programmers often to manage complexity.

A really common example of this is an Application Programming Interface which allows two "applications" to share useful data with each other over some transport while being platform-agnostic as to how this data is used. Like an API, there are other interesting kinds of abstractions -- let's peel back the abstraction between the language creator and language user by inventing syntax!

This involves a subtle shift in the paradigm used to understand computation, at the core is the idea of viewing computation as data. I would guess for most people,
the typical mental model when reading at first is mostly procedural, a top-down scan with familiarity of syntax and semantics, then another important shift occurs in
understanding runtime execution with the introduction of concurrency and parallelism, here we'll be peeling back at the layer between compile time and runtime.

Compile time occurs when program text is being "parsed and transformed" into many forms all the way to bits and runtime
is when the program is actually executing ie "running", in this paradigm of viewing programs as textual input to other programs and to the program itself while running, is known as metaprogramming.

 This distinction between what is "compile" and "runtime" is
 a useful mental model illustrated here for simplicity, odds
 are what's happening in your favorite language is probably 
 more interesting![11]

Before we begin, a caveat. Although this technique applies broadly to most modern languages -- implementations vary in feature parity, I'll try to primarily include alternate examples with go's reflection and rust's macro system while providing nods to Cpython[1], Ruby MRI[2] and some javascript [3]) but not typescript[4]

Computation is data

Consider for example the humble eval() function:

// javascript
console.log(eval('2 + 2'));

# python
print(eval('2 + 2'))

# ruby
puts eval('2 + 2')

The computation 2 + 2 is represented as data, in this case a string. That's kind of neat isn't it? however we can take this much futher.
If you're interested in further details of what's happening here, checkout crafting interpreters.

Since programming languages contain all sorts of elements like expressions and statements, we need some
way to hold information about what the program or computation is trying to do, this internal representation is most commonly known as an Abstract Syntax Tree.

At the risk of oversimplification, think of an AST as a way to meaningfully represent the textual source of a program that sometimes allows you to do something resembling string interpolation operations on your program's text source.

Prelude, why meta?

To illustrate this concept, lets see how one might add syntax to create a constructor for a dynamic array in elixir.

First, some background. Elixir is a (mostly) functional language with (mostly) immutable datastructures, it doesn't encourage the use of
or provide a dynamic array out of the box like most functional languages, as the implementation of one
requires random access read/write via mutable state. Nor does it have "constructors", a typical pattern is creating structured data returned from
a function and "piping" it through several other functions:

defmodule MyApp.Array do
  alias MyApp.Array

  defstruct field: nil

  def new(options \\ []) do
    %Array{field: options}
  end
end

iex(1)> MyApp.Array.new() |> do_stuff() |> do_other_stuff()

For this example, we're going to piggyback off the rust standard library's Vector by
creating a foreign function interface in elixir and alternatively a data structure implemented in the erlang stdlib in order to re-create something like vec!

As we'll see the "backend" implementation of the data structure is not important, the fact that it's in rust or erlang doesn't matter, what we're focused on is providing an easy to use syntactic abstraction
of a common datastructure.

Here's a simplified version pulled straight from the rust book of vec!:

#[macro_export]
macro_rules! vec {
    ( $( $x:expr ),* ) => {
        {
            let mut temp_vec = Vec::new();
            $(
                temp_vec.push($x);
            )*
            temp_vec
        }
    };
}

Here we see a pattern match ( $( $x:expr ),* ) like our humble eval('2 + 2') instead of representing the computation as a string, it's a tree like data-structure
where we can assert at compile time, if some code looks like what we think it looks like, replace it with what's in the match arm,
a process known as macro expansion.

In elixir, we can write something similar, the pattern match is a three-element style tuple[5]:

{node, execution_context or meta_data, arguments}

Go and ruby share some superficial similarities as their metaprogramming api doesn't give you direct access to the AST. In ruby libraries like RSpec,rails router and erb html templates often use metaprogramming techniques via "monkey patching" -- modifying at runtime various
properties of an object[6] and since in ruby's extremely dynamically typed[7] interpreted world there is no notion of "compile time expansion" instead you have powerful introspection and malleability at runtime giving rise to patterns like hooks[8] to alter nearly almost anything about the language via object properties, syntax or not.

Take this small excerpt[9] from rspec-core of the describe public api:

# @private
def self.expose_example_group_alias(name)
  return if example_group_aliases.include?(name)

  example_group_aliases << name

  (class << RSpec; self; end).__send__(:define_method, name) do |*args, &example_group_block|
    group = RSpec::Core::ExampleGroup.__send__(name, *args, &example_group_block)
    RSpec.world.record(group)
    group
  end

  expose_example_group_alias_globally(name) if exposed_globally?
end

There's alot happening but the important thing to note is RSpec::Core::ExampleGroup is an object that is being modified at the test-runner's runtime which specifies the linguistic structure of the domain's specific language of what describe means.

In go like ruby we have reflection that allows runtime introspection, unlike ruby it is statically typed and compiled. Reflection gives a temporary "escape hatch" out of the rigid type system and allows modification based on dynamic interfaces the most idiomatic example of this I can find are the printing family[10] functions like fmt.Sprintf.

func (p *pp) doPrint(a []any) {
 prevString := false
 for argNum, arg := range a {
  isString := arg != nil && reflect.TypeOf(arg).Kind() == reflect.String
  // Add a space between two non-string arguments.
  if argNum > 0 && !isString && !prevString {
   p.buf.writeByte(' ')
  }
  p.printArg(arg, 'v')
  prevString = isString
 }
}

Building a (Dynamic) Array "constructor" in Elixir

Now, let's get hands on. Everything here lives in a mix project called ExVec and defining the macro's public api:

defmodule ExVec do
  alias ExVec.{Array, Vector}

  defmacro __using__(implementation: impl) do
    quote do
      import unquote(__MODULE__)
      Module.put_attribute(__MODULE__, :implementation, unquote(impl))
    end
  end

  defmacro vec!([_h | _t] = args) do
    quote bind_quoted: [args: args] do
      dispatch_constructor(@implementation, args)
    end
  end

  defmacro vec!({:.., _, [first, last]}) do
    args = Range.new(first, last) |> Enum.to_list()

    quote bind_quoted: [args: args] do
      dispatch_constructor(@implementation, args)
    end
  end

  def dispatch_constructor(impl, args) do
    case impl do
      :rust -> Vector.new(args)
      :erlang -> Array.new(args)
      _ -> raise "invalid constructor type, did you mean :rust?"
    end
  end
end

The ex_vec library has two backends ExVec.Array which is a thin wrapper around :array and ExVec.Vector which is a NIF wrapper that leverages rustler's Encoder and Decoder to encode an elixir List as a Vec then implementing interfaces for what an array might look like in elixir by defining:

The Access behaviour
A protocol implementation of Enumerable

By implementing these specifications we can safely use things from stdlib like Enum and even Stream and just like that in any other elixir project
and letting the client choose the backend while keep the macro's syntax:

defmodule MyApp.DoStuff do
  alias ExVec.Vector
  use ExVec, implementation: :rust


  def len do
    # serialised as a rust Vec<i32>
    vec!(1..4) |> Enum.count()
    vec!([1, 2, 3, 4]) |> Enum.count()

    # plain old linked-list
    [1, 2, 3, 4] |> Enum.count()
  end

  def random_access do
    # O(1) read
    my_array = vec!(0..10)
    my_array[5]

     # serialised random write access
    Vector.get_and_update(my_array, 0, fn n -> {n, 42} end)
  end
end

defmodule MyApp.DoOtherStuff do
  use ExVec, implementation: :erlang

  def len do
    # this is an erlang :array!
    vec!([1, 2, 3, 4]) |> Enum.count()
  end
end

unfortunately as of the time of this writing, rustler does not support generic type intefaces so I
guess this is impossible?

#[derive(Debug, NifStruct)]
#[module = "ExVec.Vector"]
pub struct Vector<T> {
   fields: Vec<T>,o
   size: isize
}

Therefore a serious limitation of this toy example is it only works for i32 integers :) I also glossed over some behaviours and protocols with defaults.

You can find the full source for this example here, please let me know if you have a comment, found a bug or typo. Thanks for reading!

References

[1] Python3's excellent ast library: https://docs.python.org/3/library/ast.html

[2] RubyVM::AST : https://ruby-doc.org/core-trunk/RubyVM/AST.html

[3] Javascript(since ECMAScript6): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Reflect

[4] Typescript: https://basarat.gitbook.io/typescript/overview

[4] Go's AST : https://pkg.go.dev/go/ast

[5] Elixir's AST: https://github.com/elixir-lang/elixir/blob/d8f1a5d6b653c14ae44c6eacdbc8e9df7006d284/lib/elixir/pages/syntax-reference.md#the-elixir-ast

[6] The one true (useful) object to rule them all: https://ruby-doc.org/3.2.1/Object.html

[7] Ruby Extensions: https://docs.ruby-lang.org/en/master/extension_rdoc.html#label-Basic+Knowledge

[8] Awesome example of the hook pattern into ruby's object lifecyle: https://github.com/rspec/rspec-core/blob/main/lib/rspec/core/hooks.rb

[9] RSpec public DSL module: https://github.com/rspec/rspec-core/blob/main/lib/rspec/core/dsl.rb

[10] doPrint: https://cs.opensource.google/go/go/+/refs/tags/go1.20:src/fmt/print.go;drc=261fe25c83a94fc3defe064baed3944cd3d16959;l=1204

[11] Just in Time compilation: https://en.wikipedia.org/wiki/Just-in-time_compilation

A peek into the beam

Haile Lagi — Tue, 29 Mar 2022 09:45:58 +0000

A long time ago, you would give a computer an intensive set of instructions - in assembly or something more sane, and it would compute these instructions one by one, but while it did that - it would “freeze up” you could not really do much else with it. At the time, computer hardware was pretty limited, it had a single CPU core (something that executes instruction sets) which did pretty much everything, one by one - computer scientists were not particularly
satisfied with this, and they found a solution.

In essence, execution of two or more computations at the same time is possible - given it is guaranteed that both read data from the same source, but not writing which could lead to inconsistency, commonly known as a data race or race condition. Today our computers have multiple cores - they can do a lot more stuff than they used to, but we need some way to guarantee or make it really hard for this to happen.

The world of concurrency is fascinating, lots of languages design mechanisms around this problem known as concurrency primitives, allowing software creators to fashion applications and software systems that perform much better than their sequential alternative, however we are most interested in a cursory glance into the BEAM (Erlang’s virtual machine). For brief context, a virtual machine is just software - an abstraction over the basic hardware of a computer allowing a layer of execution on top of it. A common example being the Java Virtual Machine (JVM). The elixir/erlang source code is parsed and transformed into a set of intermediary files prefixed with .beam that the virtual machine can understand known as bytecode, via the C programming language. From here it is translated into
assembly/machine instruction bits [1].

source code ---> c interface ---> bytecode

Most of the interesting concurrency primitives that erlang/elixir provide are built on top of the guarantees this virtual machine provides such as immutable state. The single basic unit being a process [2] [3] -
an isolated sequential unit of computation which is managed by a scheduler an important construct.

Note: you may think of a process as a kind of "green thread",
if familiar with the concept. Otherwise thinking of them
as an abstract unit of sequential computation is fine.

Erlang’s scheduler

The scheduler within the BEAM runtime (not an operating system scheduler),
talks to the operating system via threads and manages the how and when of computations (processes - in the vm). It does something called preemptive scheduling which requires making a nuanced trade off - all processes are treated as equal(unless a priority is set) and given a tiny block of time/memory to execute, whether this is enough for a process is irrelevant. It sacrifices the efficient allocation of resources to processes that need it most to make some important guarantees which make fault tolerance possible:

High availability
Isolated failure states

This constant context switching gives guarantees creating a system that is dependable - allowing the creation of processes that inspect others, we can leverage this information to make intelligent deductions about what is happening within the system at runtime and design strategies to deal with and understand crashes and fail states, while also providing concurrent primitives that naturally scale across distributed systems, changing very little about the core system.

A typical illustration of erlang's introspective superpower is :observer which ships by default. Pop :observer.start() into any iex session and watch the magic.

user@my-pc $ iex
iex(1)> :observer.start()

You can see the schedulers at work by spinning up a few short-lived processes which begin their lifetime[4] with about 326 words of memory (approximately 0.65 kilobytes) which can grow on a stack or heap.

Here you have self() as the iex session process, creating another process that it communicates with:

iex(1)> current = self()
iex(2)> child = spawn(fn -> 
  send(current, {
    # new identifier process created by spawn
    self(),
    # any arbitrary sequential computation
    # looping, control flow, anything :O
    1 + 1})
end)

We can then leverage the high level Process library for convenience, to create more processes, thousands or even millions if need be:

child_two = Process.spawn(fn -> 1 + 2 end, [:monitor])
child_three = Process.spawn(fn -> 1 + 3 end, [:monitor])
child_four = Process.spawn(fn -> 1 + 4 end, [:monitor])
child_five = Process.spawn(fn -> 1 + 5 end, [:monitor])

Processes have an identity via their pid, this is how they are aware of one another. The return value of each child
looks a little like this:

# {#PID<0.93.0>, #Reference<0.18808174.1939079169.202418>}

Note: The actual pid and reference will be different on your machine).

When the scheduler(on one core) sees these concurrent tasks, it allocates some time and memory at runtime to child and lets it run for a bit, if the process does not finish(an infinite loop for example), the scheduler moves on to child_two and so on, checking up on each process, computing a bit. Processes are namespaced in a local registry for a single node. Scheduling across multiple nodes works the same way, only you'd need a different way to manage the global name space of running processes.

Note: There are likely many scheduler threads coordinating
on this activity on a single core, and at least one per
operating system process. Further details are subject to
which version of Erlang/OTP you're running and the implementation has varied significantly over the years and may change.

High availability and isolated failure states are achieved via messages propagated through a web of processes. Leading to interesting high level abstractions such as supervisors and agents for handling local inter process state.

It's all about tradeoffs

Elixir provides a beautiful modern language that allows you to leverage the amazing ecosystem and novel concurrency ideas built into erlang, offering you the tools to create and design highly fault-tolerant, self-healing systems, sometimes at the cost of absolute runtime performance. You can see this with need to replicate data structures and performing computationally intensive tasks that would make sense to be processed sequentially. Do not despair however, you can carefully poke a hole into the runtime through the C interface via Native Implementation Functions, whether in C++ or perhaps rust via rustler. Or outsource this kind of heavy-lifting if required to a service in a different language. Let's explore at a high level the conceptual
underpinnings of relatively more popular languages and how they stack up against the BEAM's approach.

Actor Model vs Single Thread(multithreading) (Ruby, Javascript and Python)

Ruby, Javascript and Python all have different concurrent models and implementations, however they share some important
similarities at a high enough level they can be grouped together. Ruby(MRI), CPython and Javascript's v8 runtime(node.js) are all single threaded. Concurrency is achieved via a single Process(operating system) which has one large "main" thread(where the runtime is loaded) which creates smaller threads of execution within a single context(system resources - memory etc).

Note: You can in-fact create analogous threads of execution
beyond what is given but doing so is expensive and tricky.

Node.js in particular was especially optimised with this design early on. The limitations here are somewhat obvious, utilising a multicore architecture is incredibly difficult and burdens the application developer with the nuances of lower level details you'll simply not interface with in erlang/elixir. Ruby and Python historically however needed a mechanism called a Global Interpreter Lock(GIL) to enforce/sync the runtime and make a data race impossible. This is often called a mutual exclusion lock and the algorithm is plenty fascinating and deserving of its own article.

The primitives given are fairly similar - ruby gives you a Thread class and Fibre to create worker threads, node gives you access to the main libuv[11] managed Process and one for when you're creating worker threads.

To utilise any form of thread parallel execution python provides a library interface, ruby core has been experimenting with and recently released an actor model inspired mechanism called Ractor.

In practice, when creating say a web server with these languages an Event Loop[9][10][11][12] handles the heavy lifting within the main thread, resources are simply not shared and asynchronous failures caught with lots and lots of defensive programming.

Actor Model vs Communicating sequential processes (goroutines)

In some ways erlang and go share some features of their concurrent model - both leveraging the symmetric multiprocessing [8] architecture with the key difference eloquently expressed by a deceptively simple philosophy:

Do not communicate by sharing memory;
instead, share memory by communicating

Goroutines are analogous to "processes" being a lightweight "unit" of computation, however they have no identity(pid). This isolation ensures the only way data moves is through a "channel", a departure from the concept of a mailbox that keeps track of immutable internal state, a channel serves the purpose of message passing between anonymous routines.

By opening a channel to some forgotten computation you can peek its state and enforce synchronisation.

Resources are shared with carefully crafted rules. The analog of a supervisor being a "monitor goroutine". The sole writer of data in any cluster of spawned processes. This too is a form of message passing, just implemented with a kind of artificial immutability for workers. Runtime failures (panics) are rarer in go, and instead errors treated as values passed between goroutines. If panicked routines crash they inform the main go thread and the whole thing carries along swimmingly.

Reasoning about concurrency systems is somewhat trickier here but allows for performance fine-tuning if you can enforce mutual exclusion between goroutines. This freedom does come seemingly at a cost[6] which it seems all
languages that do not enforce immutable data structures and performance fine-tuning an exception rather than the norm,
but of course it all depends on context and use case.

Thanks to Ayomide and Daniel for reviewing early drafts of this article.

References

[1] fxn(medium): https://medium.com/@fxn/how-does-elixir-compile-execute-code-c1b36c9ec8cf

[2] green threads(wikipedia): https://en.wikipedia.org/wiki/Green_threads

[3] Joe Armstrong(twitter): https://twitter.com/joeerl/status/1010485913393254401

[4] Erlang documentation: https://www.erlang.org/doc/reference_manual/processes.html

[5] Erlang documentation: https://www.erlang.org/doc/efficiency_guide/processes.html

[6] go reference: https://go.dev/ref/mem

[7] stackoverflow: https://stackoverflow.com/questions/2708033/technically-why-are-processes-in-erlang-more-efficient-than-os-threads

[8] symmetric multiprocessing: https://en.wikipedia.org/wiki/Symmetric_multiprocessing

[9] node event loop: https://nodejs.org/en/docs/guides/event-loop-timers-and-nexttick/

[10] asyncio: https://docs.python.org/3/library/asyncio.html

[11] node io: https://github.com/libuv/libuv

[12] RoR documentation: https://guides.rubyonrails.org/threading_and_code_execution.html

Break your next server.

Haile Lagi — Sat, 24 Oct 2020 15:03:16 +0000

Your friendly neighborhood aspiring junior dev's guide to understanding the philosophy of fault tolerance in servers. A series of rants and odd thoughts.

I want to propose something, break your next server, on purpose. Nope that title isn't clickbait, but I hope you spare me a few moments to explain. Runtime errors are the last thing you want to happen in your code right? Especially if it's running in "production", but you know... I don't know.

I'd like to think in general software development, stuff goes wrong more than it goes right. I always wonder what happens in real software teams? how do they respond to minor and major corruptions in their systems? Servers break all the time. For lots of unusual reasons, especially in production. The world is a messy place, unpredictable and I have yet to find any real world service that hasn't experienced some sort of outage at some point in time. Sometimes? These are entirely unpredictable, novel problems that require novel solutions. There's no magic server that can guarantee 100% uptime(depends on what you define as "uptime", more on that later). Stuff happens, security vulnerabilities, scaling issues, dependencies on external services break, and so on. Things my inexperienced mind cannot begin to fathom.

Yet? sometimes, these errors aren't so unimaginable. A database query fails? oops! An external api endpoint gets stressed? (*cough graphQL) and the guys on the other side get a weird aws email? 😦, something gets deprecated somewhere and you forgot?

Okay, that's the problem what's the solution? Let's explore some common approaches before we know what exactly is going wrong. 😈

Deploy another one! (Modern problems require modern solutions!)

Apparently there's this fancy stuff they call a container these days. I won't bore you with infrastructure voodoo (I know little about it anyway), or less fancy a simple vcs checkout, let's keep this about systemic approach rather than implementation. These are different things, yes but they can be used(sometimes together or in isolation) to "fix errors". This approach says "oh crap" something broke, let's go back to when it did work. This is great except? Something caused a runtime exception you didn't expect and now you have an unavailable service. So you go off on an adventure, generating bug reports, pouring over log files and finding wtf happened! Sherlock mode activated! While this is happening you try to reboot the entire system with an older (bug free you believe) version. Nothing wrong with this, except? It's not solving the error problem. It's solving a dependency problem, an environment problem... but not necessarily an error problem and it's an approach at too high a level, you believe since the error happened in the programmer's domain? It must have been caused by it. Sometimes this is true, but not always. Sadly this server is too fragile anyway, just one lousy runtime error and everything goes boom?! You don't have to put yourself in that position. Not unnecessarily and without good reason. You should only need to re-deploy when something really important goes wrong. This should be a rare case.

Avoid runtime errors at all costs!

At this point, we're jaded and cynical about I/O. Legend has it? If you wrapped your entire application in a try/except clause it will never fail. You have some input? Don't just sanitize it, you bleach it, add some disinfectant, rub some olive oil on it, cut a chicken's head off and invent scenarios. Likely? unlikely? doesn't matter! try, except, catch, rescue and their siblings are great... to a point. Yet, you can't predict every possible error under the sun. You need to take precaution, yes but you also need to be nimble, adaptable to the strange world of I/O and unpredictable side effects. The limitation of this approach is in the inability to isolate the error in the system, leading to generic uncaught exceptions and more importantly the corruption of state. More on that later. Depending on how this server's engineer intended recovery, it can go from beautifully crafted code to omg wtf is this because of the many paths the program can follow and how it re-converges to stability matters. This depends on skill and experience to execute and is a function of experience(usually) to the kinds of errors that could occur in prod. What if there was another way? Reflecting on experience is indispensable, you cannot substitute it. However, next best you can try to play catch up with a little foresight and study, re-inventing the wheel only when you need to.

To be fore-compiled is to before tested!

There's this thing around the programmatic universe, it's called Test Driven Development. Some people swear by it, some think it's a pain, yet pretty much everyone thinks it's a good idea(except crazy people 😏). On another side of the equation you have static typing. What do these things have in common? They check for the correctness of software before it goes off into the real world(among other things lol). This is awesome, but it doesn't solve our problem still, how software behaves in an environment you do not control. These are lovely additions to controlling the programmer's domain and make sure(to an extent) nothing funny is going on through technology features and development practices.

Embracing failure as an inevitable part of systems(and our lives) by introducing the horsemen of the error apocalypse, Agents, GenServers, Supervisors and Applications.

There's a lovely rhetoric that I think holds true. Fail often, fail fast. Each of these approaches had a little something, a piece of the puzzle, a system design choice and when combined in the right way? they can be powerful tools. Introducing fault tolerance 101 which has a rich history.

Fault tolerance and by extension concurrency are implemented in Elixir using the Actor model. Let's start with the fundamental pieces and eventually how they work together to conceptually create an error tolerant server. You can ignore the code snippets if unfamiliar with the language, they run but are ultimately useless and illustrative. Before we go to the fun useful abstractions? Let's talk about the basics! Processes.

Processes

This one is weird, in that it shares the same name with a system process. Processes in Erlang/Elixir are lightweight spin offs that do stuff concurrently and communicate through messages. Sounds weird? Yup. I don't know much about how this is implemented internally(I'd love a pointer to deep dive resources). See Elixir is a functional language and yunno what that means kids! immutability, so how does concurrency happen? Why do we care? Well everything else is an abstraction built on top of this. You can think of a process like a really really tiny server, with the whole request//response cycle. This is what it looks like.

spawn fn -> "do something" end

Doesn't this remind you of how a telephone line works? Instead of a network you communicate with this lone wolf, through an abstract mailbox that holds messages in queue. Nothing complex here you send stuff and you recieve stuff. The mechanism is somewhat similar to dispatching actions in redux and this isn't a coincidence but a consequence of immutable state. I'll make references to redux, if you don't know it, that's fine. It's not a prerequisite. The high level concept is the main focus.

Agents

Here's where stuff gets interesting, now that we know what processes are, let's discuss something productive. Agents are essentially specialized processes that are used to store app state. If you know what a redux store is? this is a lot like that.
Why is this useful? you have some state that needs to be accessed by different parts of your application and most likely? these are going to be concurrent in different processes, how do you manage state? Agents are your goto solution. That's all it is, a safe space for your immutable state.

{:ok, store} = Agent.start_link fn -> "keep precious data safe" end

It has some useful APIs but we don't care about that right now, only the conceptual understanding of what it is and what it does.

GenServers

Remember the analogy where I said you can think of processes as really really tiny servers? well there's a reason for that. A good mental model of this is anything that happens inside a process is the server and anything outside it? is the client. GenServers sound mystical the first time but it's actually short for a generic server.

defmodule MetalGearSolid do
  use GenServer
  # implement server
  @impl true
  def init(big_boss) do
    {:ok, big_boss}
  end
end

You can think of it as a "process that computes processes". This isn't as complex as it sounds. It just tells stuff what to do, it's like a jerk manager process that bosses around other developer processes...lol you just need to pass callbacks with the functionality you want the abstract generic server to have and you're done! Here's what it looks like.

  @impl true
  def handle_call(:snake, _from, [head | tail]) do
    {:reply, "#{head} becomes venom_snake spoiler!", tail}
  end

It holds application state(using a similar mechanism with agents), manages and monitors processes. You interact with it using sync calls and async casts. There is a little more boilerplate code but we don't care.

# Start the server
{:ok, pid} = GenServer.start_link(MetalGearSolid, [:naked_snake])
# client
GenServer.call(pid, :snake)
#returns ==> :naked_snake becomes venom_snake spoiler!

The official Elixir guide uses this phrase and it stuck with me "GenServer provides industrial strength functionality for building servers". That's an interesting choice of words, as someone who interned at a company that processes millions of dollars worth of product daily? Consider my interest piqued.
Why is this useful though? You see genServers are you bread and butter, this is what in essence computes all your lovely complex computations, network requests, database queries? you name it.

Supervisors(middle management)

We can sorta intuitively understand processes and message passing. We've explored agents a safety net that make sure our state is never corrupted, and generic servers as abstractions that perform collections of necessary async processes... yet how is any of this fault tolerant?

What if we make a database query in a genServer and it fails?
Let's see what we have so far.

Our state isn't corrupted...great! (cause...immutability)
Functionality is isolated, but so what?
Our genServer is gonna start to panic. oh crap what do I do? It knows what's wrong and what is responsible. The process that was supposed to connect to the database failed...but now what?

What if you just need to try again? Maybe wait a little longer? Well now you need middle management, a faithful servant that will be there for you and observe what happens to your beautiful code and carries on your will when you can't.

children = [
  %{
    id: MetalGearSolid,
    start: {MetalGearSolid, :start_link, [[:naked_snake]]}
  }
]
# Make sure metalgear doesn't destroy the world
# here's the awesome strategy you apply
{:ok, pid} = Supervisor.start_link(children, strategy: :one_for_one)

Putting the pieces together as Applications

I've said a lot of stuff, all that was to prepare your mind. We can now talk about the zen of Erlang (you should really check out that article btw! it's really funny and imo communicates the point of this post). The philosophy of fault tolerance(OTP) is built on structures of processes, isolated pieces of functionality talking to each other, to make bigger "units". Sometimes? This functionality is linked other times? Our system can live without the database query knowledge of a user's favorite cat, this is how robustness is created. By identify mission critical parts of our system? We can protect them, even in the face of failing little bits and design strategies to cope.

The programmer becomes the ultimate creative ninja.

We display our cool coding skills proudly in the world of I/O. Unafraid of what could go wrong because we know something probably will! Our strategies of recovery are a game, we can trace error points, cast out unnecessary operations, skip some? Restart entire groups of dependent process... the possibilities are endless! If you're wrong? then the supervision tree will continue to run with less and less functionality until the errors propagate far enough into the system(now you have something to worry about and can apply strategy one!!!) and even here you have time to figure out what is going horribly wrong, and more often than not? You probably should never have shipped that.

Applications are such large units of functionality in a larger system. Take a phoenix server, it's an application, the database query interface is child of the parent process, even the endpoints are children, what happens when part of the functionality stops? Internally? The server will try to recover how I tell it to, using telemetry to report what happened, all the while still performing other functions It's a thing of true beauty! The error(s) caused by any module are independent of any other part of the system.

In summary, agents store state, supervisors are co-ordinators, while genServers are executors and together they make up an application(which could also exist with them though). There are other interesting abstractions such as Tasks,Registry and Dynamic Supervisors the world of OTP is fascinating.

GOTCHAS

Okay, you've read all about fault tolerance and how this can probably help you. The question remains... do you really need it? This is about an approach to solving software problems, you don't need Elixir/Erlang for this. An honorable mention is this implementation in javascript of a supervision tree. In fact, I'd go as far as to agree that functional programming doesn't necessarily mean good software either!. However Elixir/Erlang are extremely good tools optimised for not just dynamically handling errors in production but more importantly handling lots of persistent concurrent connections up to two million apparently!. This isn't just fluff either, the whatsapp team achieved similar results in production way back in 2012 with Erlang and discord seems to love the language. These features are baked into the core language and ecosystem because it optimizes for them, it's easy to fall into the pit of success and program with these things first and foremost in mind. Many programmers and companies use many different programming languages with differing paradigms and practices, whether this is the right choice isn't simple. Isn't that what's fun about engineering? Software or not. Almost every cool decision is lowkey a constrained optimization problem.

Do you want to learn a new language and ecosystem? and dive into a completely new paradigm (assuming you're coming from a multi-paradigm or object oriented approach) It is an investment to think about.
Does your system really need high availability? Which is to say is robustness an important feature you're optimising for?
Do you need distributed computing?
Do you intend on having A LOT of clients that do stuff at the same time? (A chat app is a good example - see discord and whatsapp case studies)
Do you have an existing codebase? (Is the ROI of migrating really worth it?)
Can you find good people who use this? (Not really the most popular language out there and the disadvantages that come with that)
Are you a junior? Or an aspiring junior like myself optimising for a job? Well... imo you're out of luck with Erlang/Elixir. Sad fact is whatever few jobs that are available? Are probably beyond your experience level :( sorry.

Many many more questions remain to be answered for your particular use case. However, despite these things, I believe this is an excellent introduction and learning experience, to a fundamentally different approach to solving software problems using functional programming and understanding a curious model for achieving concurrency.

Going Forward

I'm looking to explore interesting technology. Stuff that's awesome because it's awesome. I have my eye out on Julia and it's uses for my research project(if schools ever resume :( ) and Go for making tools. Got resource recommendations? not necessarily limited to languages, I'd love to hear them(web and scientific domains mostly!)
I'm looking for really nice medium to large open source projects or fun hacks that are friendly. I have a lot of free time I'd like to spend hacking at stuff that will be useful to people and while trying to do this on my own is fine, it has limitations.
Thank you for your time. I'm open to feedback whether in the form of criticisms, improvements or simply conversation, here on dev or anywhere you can find me on the internet :)

The weight of choice is heavy

Haile Lagi — Mon, 31 Aug 2020 18:46:19 +0000

A humble aspiring junior dev's guide to probabilistic thought. A series of rants and odd thoughts.

What are the odds? I've spent quite a few hours invested in implementing a seemingly innocent feature of a game I'm currently working on as part of my learning in the world of functional programming with Elixir. I won't bore you with the details, I haven't even finished making the game, the prelude to discovering this problem is an innocent one. It's a terminal dungeon crawling game, where you venture into dark rooms in search of treasure and an eventual (hopeful) exit.

If you know anything about me? I loooovvveee games and RPGs especially JRPGs, I love-hate dungeon crawling and puzzles so much so that I write about it [NSFW!] so I've been having fun making this and curious about how all the gears fit, it is especially interesting to note how this relates to the modelling and simulation of objective functions something I'm quite interested in!!! Let's dive in and explore!

The probability of choosing a room is controlled by a call to Enum.random(iterable) which selects a random element from the iterable, using Erlang's internal pseudo-random generation algorithm. At this point in time, only three rooms existed (a room leading to the exit, A room full of monsters and another room full of monsters.)
Therefore it's safe to assume the mathematical probability of finding any room is P(1/3). This isn't so great is it? You could just start the game and one-third of the time, without experiencing even a single battle :( Oh I know the author suggests... let's add different probabilities to the rooms, such that rooms with battles appear more likely and rooms with an exit less likely. Okay... so I tried it, after the first hour or so I came up with a satisfactory(to me I thought) solution. This is it. I first added a probability key, with a value of an array of atoms to the struct.

defmodule DungeonCrawl.Room do
  @moduledoc """
  data structure representing a "room"
  a room has "actions" borrowed
  """
  alias DungeonCrawl.Room, as: Room
  alias DungeonCrawl.Room.Triggers, as: Triggers
  import DungeonCrawl.Room.Action

  defstruct name: nil, description: nil, actions: [], trigger: nil, probability: nil

  def all,
    do: [
      %Room{
        name: :exit,
        description: "You can see a small light from a crack in the walls",
        actions: [forward()],
        trigger: Triggers.Exit,
        probability: [:exit]
      },
    %Room{
        name: :goblin,
        description: "You can see an enemy blocking your path",
        actions: [forward()],
        trigger: Triggers.Enemy,
        probability: [:goblin, :goblin, :goblin, :goblin, :goblin]
      },
    %Room{
        name: :ogre,
        description: "Something moves around in the dark, what do you do?",
        actions: [forward()],
        trigger: Triggers.Enemy,
        probability: [:ogre, :ogre, :ogre]
      },
    ]
end

At once you can probably see the naiveness of this solution. What computed the algorithm is this

 defp bias_probability(rooms) do
    rooms
    |> Enum.map(fn room -> room.probability end)
    |> Enum.reduce(fn room, acc -> room ++ acc end)
    |> Enum.random()
  end

and finally now that I know the biased random outcome-

    rooms
    |> Enum.find(fn room -> room.name == bias_probability(rooms) end)

Technically? This is a mathematically correct solution. It will compute a random value with a biased probability of P(0.1, 0.5, 0.3). I felt happy with myself, turned off my laptop and went to sleep! That was that! Or so I thought.

See there are two fundamental flaws of this approach:

I'm hard coding the probabilities, although modifying the probability of a room is possible, it will result in boiler plate code and unnecessary list traversal
The algorithm is not performant(in space complexity) atoms are not garbage collected in Elixir, and it would be unwise to arbitrarily create them on a whim! suppose I had a thousand rooms in the future for example

Sure enough, extra feature requirements came, the addition of a "difficulty level" that will bias this probability dynamically. So.. began my search, with a renewed courage to try mathematical problems I tweaked and tweaked, no luck. I asked my friends in engineering from school no luck! and then sure enough, a friend of mine with superior googling skill found a long lost blog post from 2017. This is what really helped me, without it I was lost in meaningless scribbles of probability theory and conditional problems. If you're interested in learning more about implementing a weighted probability algorithm please check out David Hills's blog it's really detailed and well done! I'll focus on implementing two algorithmic approaches I learned and adapting it to the context of this game. The linear search and one of the alias algorithms.

Probabilities can be unfair!

Linear scan the O(kay) method

O(n) runtime

A lovely idea is to search the linked list for an index value based on probable outcomes, wish I thought of this!! This will work by generating a random number between 0 - 1 and multiply that by the total probability distribution(For my use case, I'm assuming the list is sorted), then traverse the probability distribution subtracting each probability from the random probability, if it goes below zero? We've exhausted the probability distribution and found the index we need. Lovely solution. This works because we mathematically assume random.random() will generate a perfectly random number(spoiler it doesn't, but we don't care). If the probability is really low? It will hit the lowest index less often, and if the probability is high? It will hit that index more often. Run the code below to get a sense of it if you like.

import random

def weighted_random(weights):
    """
    INPUT probabilities - [0.2, 0.3, 0.5]
    OUTPUT index of random_weight - [0, 1, 2]
    """
    remaining_distance = random.random() * sum(weights)
    # probability distribution sample size * random integer
    for (i, weight) in enumerate(weights):
        # [{0, 0.2}, {1, 0.3}, {2, 0.5}]
        remaining_distance -= weights[i]
        #print("debug", remaining_distance)
        if remaining_distance < 0:
            return i

# Repeat the experiment to observe bias factor
for e in range(10):
  print(f"exp trial{e}",weighted_random([0.2, 0.3, 0.5]))

This seems really cool doesn't it? I can represent the P(n) of my game as floats and dynamically update them, keeping the purity of the function. A quick and dirty Elixir version of this looks like

defmodule Prob do
  def bias_probability(weights) do
    # [i[0] P=0.2, i[1] P=0.5 , i[2] P=0.3] s.s = 3
    # P(n) = distribution sample len bias * random() - P[i] < 0
    len = Enum.count(weights)
    # could increase range for greater float precision as you like
    distance = Enum.random(1..99)/100 * Enum.sum(weights)
    # bias factor
    enumerated_list = Enum.zip(0..len, weights)

    Enum.reduce_while(enumerated_list, distance, fn (_weight = {i, w}, acc) ->
      if (acc - w) > 0, do: {:cont, acc - w}, else: {:halt, i}
    end)
  end
end

IO.inspect Prob.bias_probability([0.2, 0.3, 0.5])

and then to find the biased index.

    rooms
    |> Enum.map(fn room -> room.probability end)
    |> Enum.fetch(bias_probability(rooms))

but now that I've gone through the trouble of investigating weighted probability, I don't wanna settle for a linear search. Might as well make the game with the fastest possible approach. Let's go back in history, and take a look at one of the alias algorithms.

Aliasing(Vose) the O yes! method

O(n) alias table prep + O(1) lookup

This one is a bit tricky to understand at first. If you're interested in a much more technical deep dive into the various approaches for solving this problem, please check out this article by Keith Schwarz it's dense, comprehensive and technical. Onto aliasing!

The idea is honestly very clever! and in my opinion counter-intuitive, which is what makes it's constant-time runtime lookup so impressive. Let's take a step back, before diving in. An alias is like a nickname we give to stuff right? You have a friend called Samuel, and you call him Sam. His name isn't Sam and he hates that nickname, but alas, it stuck... poor Samuel, but if you see his face anywhere you know Sam is Samuel because you're such good friends. The alias method is a lot like this in principle. You have a biased probability weight distribution and it approaches some limit and that limit can be used to generate a custom distribution. Let's talk about Sam for a bit.

See Sam's nickname is called an alias table and your friendship(how you know Sam is Samuel) is the algorithm. Now that we have some hint as to what we're doing, here's the python implementation with my comments from Bruce Hill's blog. Scan through it, maybe run it if you're adventurous. We'll break it down step by step next. (If you're familiar with Java check out Keith Schwarz's implementation instead

def prepare_aliased_randomizer(weights):
    N = len(weights) # limit
    avg = sum(weights)/N # alias partition

    aliases = [(1, None)] * N
    # [(1, None), (1, None), (1, None)] --> alias table

    # Bucketting (pseudo quick sort like behaviour*)
    # weight/avg < | > avg
    # smalls are partial alias fits
    # bigs fits and remainder thrown to smalls

    smalls = ((i, w/avg) for (i, w) in enumerate(weights) if w < avg)
    bigs = ((i, w/avg) for (i, w) in enumerate(weights) if w >= avg)

    # [(0, 0.6), (1, 0.9)] --> small weight avgs
    # [(2, 1.5)] --> big weight avgs
    #cycle through small and big partition generator
    small, big = next(smalls, None), next(bigs, None)

    # if elems are not exhauted kindly loop
    while big and small:
        # put the partial elem in aliases
        aliases[small[0]] = (small[1], big[0])
        print("alias lookup table transformation", aliases)

        # big = i of big , weight_b - (1 - weight_s)
        # big = (0, (1.5 - (1 - 0.6))
        big = (big[0], big[1] - (1-small[1]))
        if big[1] < 1:
            print("large weight is < 1 skip", aliases)
            small = big
            big = next(bigs, None)
        else:
            small = next(smalls, None)

    print("alias table generated", aliases)
    # SELECTION STAGE
    def weighted_random():
        r = random.random() * N
        i = int(r)
        # choose a random probability
        # from the alias table
        (odds, alias) = aliases[i]
        print("what are the odds of", r)
        # return the larger probability if
        # it's odds are higher else
        # return the smaller probability index
        return alias if (r-i) > odds else i

    return weighted_random()

# single trial selection
print(f"experiment trial", prepare_aliased_randomizer([ 0.2, 0.3, 0.]))

# Repeat the experiment to observe bias factor
for e in range(10):
  print(f"experiment trial", prepare_aliased_randomizer([0.2, 0.3, 0.5]))

PHEWW!!!!!!! there's alot going on. Let's break it down. There are two major steps, once you understand how the table is generated(that's most of the work) the lookup naturally follows.

This paragraph is interesting but ultimately a digression, you can choose to skip over it!
How exactly does a computer remember who Sam is? Well computers are a little like the human brain, people have complex organic circuitry of neurons that consolidate sensory observation and from that recognizes patterns and form "thoughts", the only difference is we have to tell the computer what pattern it should follow and it doesn't necessary form a thought, simply a result, and we do not need such instructions?(dna? nope, it's a philosophical question of not only intelligence but implicitly will :) does existence precede essence? I like to think so. Shameless plug, @ me on twitter if you're interested in this topic).

Table generation

To create the table, the original weight distribution is sliced into pieces(partitions)! Quite literally! Suppose we know how many weights we need, in this case 3, that's the limit. To find P(0.2, 0.3, 0.5) We create an empty alias, with a data structure, with the exact same length [partition, partition, partition] and a probability [partition, partition, partition]. Each partition will contain exactly P(1/3). Here's the interesting part, we then scale the probabilities to the factor of our limit and separate it into chunks less than 1 and greater than or equal to 1. Why?

Here is the rationale:

If the weight fraction is greater than one or equal to it, it will fill a single alias partition(fit exactly if equal else) with some change! which will be sent to an empty partition.
If the weight is less than one, then it will be smaller than the allocated partition and it will be expecting a buddy :)

Each partition, will hold a new distribution perfectly and why this is mathematically correct.. is kinda funny tbh. I won't discuss the formal proof, but the idea is that at any point in time, the sum of the elements in the distribution is always proportionate to the original weight.

defmodule Probability do
  def bias_probability(weights) do
    # Initialization
    n = Enum.count(weights)
    prepare_alias_table(weights, n)
  end

  defp prepare_alias_table(weights, n) do
    alias_table = Enum.map(1..n, fn _ -> {0, nil} end)
    prob = Enum.map(1..n, fn _ -> nil end)

    # create work lists
    scaled_weight = scale_probability(weights, n)
    small =
      scaled_weight
      |> Enum.filter(fn {_, w} -> w < 1 end)

    large =
      scaled_weight
      |> Enum.filter(fn {_, w} -> w >= 1 end)

    # recursively create table (TCO optimized)
    transform_alias(small, large, alias_table, prob)
  end

  # Base case when small and large are empty
  defp transform_alias([], [], _, prob), do: prob

  defp transform_alias(small = [], [_g = {i, _} | tail], alias_table, prob) do
    # Remove the first element from large call it g, Set prob[g] = 1
    transform_alias(
      small,
      tail,
      alias_table,
      List.replace_at(prob, i, 1)
    )
  end

  defp transform_alias([_l = {i, _} | tail], large = [], alias_table, prob) do
    # (clause will trigger due to numerical instability)
    # Remove the first element from Small, call it l
    transform_alias(
      tail,
      large,
      alias_table,
      List.replace_at(prob, i, 1)
    )
  end

  defp transform_alias(
         [{index_l, weight_l} | tail_s],
         [_g = {index_g, weight_g} | tail_l],
         alias_table,
         prob
       ) do
    # Remove the first element from small call it l
    # Remove the first element from large call it g
    # Pg := (pg + pl) - 1 (numerical stability :) )
    new_weight_g = (weight_g + weight_l) - 1

    # if Pg < 1 add g to small
    if new_weight_g < 1 do
      transform_alias(
        [{index_g, new_weight_g} | tail_s],
        tail_l,
        List.replace_at(alias_table, index_l, weight_g),
        List.replace_at(prob, index_l, weight_l)
      )

      # else Pg >= 1 add g to large
    else
      transform_alias(
        tail_s,
        [{index_g, new_weight_g} | tail_l],
        List.replace_at(alias_table, index_l, weight_g),
        List.replace_at(prob, index_l, weight_l)
      )
    end
  end
  # HELPER
  defp scale_probability(probs, n) do
    0..n
    |> Enum.zip(probs)
    |> Stream.map(fn {i, w} -> {i, w * n} end)
  end
end

Now that we can generate an alias table, this implementation will also include a local cache using Erlang Term Storage to hold the alias table inside another table! lol throughout the lifecycle of the application once it has begun to run. I'm assuming once a difficulty level is selected random rooms need to be populated but the probability of that room occuring needs to be computed once.

  def bias_probability(weights) do
    # Initialization
    # does the probability exist in memory?
    current_probability = try do
      [weights: cached_probs] = :ets.lookup(:weight_probability, :weights)
      cached_probs
    rescue
      ArgumentError -> cache(weights)
    end

    current_probability
    #|> weighted_random # to be implemented next
  end

  defp cache(weights) do
    n = Enum.count(weights)
    :ets.new(:weight_probability, [:duplicate_bag, :private, :named_table])
    :ets.insert(:weight_probability, {:weights, prepare_alias_table(weights, n)})
    [weights: cached_probs] = :ets.lookup(:weight_probability, :weights)
    cached_probs
  end

Look up

Finally we can generate a random probability and select an index to return from it!

  # GENERATION
  defp weighted_random(aliased_table, n) do
    # Generate a fair random distro in a range
    # from n and call it i.
    r = Enum.random(0..1000)/1000 * n
    # random choice P(1/3)
    i = floor(r) # 0, 1 , 2

    prob = aliased_table

    {:ok, odd} = Enum.fetch(prob, i)

    # partial fit
    if (r - i) > (odd) do
      # which piece of what goes where
      bias = prob
      |> Enum.with_index()
      |> Stream.filter(fn {p, _} -> p == 1 end)
      |> Enum.random()

      {_, i} = bias

      i
    else
       i
    end
  end

Here's the whole implementation in a Github gist

GOTCHAS

There are quite a few waiting for you if you desire to copy/paste this implementation, for example I ignored float point precision(somewhat) instead I could have chosen to seed the values and my probabilities are always weight fractions of 1, or the implicit assumption of never returning 0, or 1 weights in the linear search. Please read the more indepth blogs, they're invaluable. For my use case though, it could probably scale to thousands of rooms effortlessly 😄 Thanks for reading!!! I'm always looking for feedback, have a suggestion? found a bug? Know an interesting algorithm? Maybe you just wanna leave kind words, I'm always happy to converse :)

Schrödinger, cats and boxes.

Haile Lagi — Sun, 26 Jul 2020 17:20:14 +0000

A humble aspiring junior dev's guide to programmatic thought. A series of rants and odd thoughts.

“And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.”
Genesis 1:2

If functional programming were a cat? It'd be a black cat. Cats are a lot like functional programming, herein referred affectionately to as fp. It's really more scared of you than you are of it. You see? it's always trying to find compile time guarantees and predictable data flow. It's a fragile thing this paradigm, it can't handle the real world of I/O on its own. It needs help from you the programmer and it begs you not to be stupid.

Unlike their very flexible abstract brother in arms? Objects? They take abstraction and flip it on its head. Gone is the natural(familiarity bias) view of the programmatic universe, enters this dystopia! Filled with processes that lead to processes. I no longer see a Tree surrounded with air, I see photosynthesis!. The complexity of fp is meant to simplify programming not obscure it. It's scared of mutations! who wants to be a powerless human? among X-men? with the ability to simply create new data structures at will. They are more like a logicians wet dream. Pretty premises coming in to be analyzed with a scalpel of wit, to its rational valid conclusion.

Once upon a time, long ago a man asked himself? What is a thing? Then the woes of all programmers began

Let's leave programming for a little while. Follow Alice down this rabbit hole, I promise we will return. For now let's say hi to Oxford philosopher William of Occam, and the modal theory. Not Model theory as is traditionally done. You see I am not passionate about mathematics, I tolerate its method for utility. Another noteworthy person of stature was Peter Abelard. There was a problem plaguing people in the middle Ages(pun intended) it was a problem of stuff. Nope not conspicuous consumption you of the bourgeois class :) What are stuff anyway?

But first another digression from this digression! Forgive me! But we are looking back into history in the wrong order, and for good reason as you'll come to understand, I hope. Let's pay our respect to the mathematicians before we cast their headache inducing notations ad nauseam aside. To the original gangster himself, Wilhelm Leibniz.

Yup that one, the calculus guy that ruined my engineering education(let's forget that other alchemist for now he isn't important). Curse these polyglot achievers, mere mortals like myself struggle in one field but calculus was not mathematical enquiry. Or at least it was not created to be "just" math. It was a pure expression of holy abstraction, to cut down any and all in every field(arguably it has somewhat achieved its intended goal). It is strange the first time you see it. dy/dx. Oh the PTSD this symbol brings back but that is what it is a symbol. A representation of the rate of change of relative quantities? Oh hush now, this has nothing to do with programming you complain! But it has everything to do with it. The pieces will align, eventually. I hope as I learn, I write and hope I do not err in communication.

You see? It is the fault of these men. Men like Goedel, Russel, Venn and Boole among others. They cursed us with genius and forgot to dumb it down. Before we return to modal theory let's dive into languages and symbols for a bit without going into too much overwhelming detail? This is what your everyday programmer does. A little if here, a little false there. Some iteration there to be sure, a little recursion here poof!!! you have yourself magic! But it wasn't always so. See there was a problem Leibniz attended to. When we speak or write we do so by conveying thoughts that have cognitive meaning or emotive meaning. Emotive statements tend to make a value claim here and there you know them, politics, morality, ethics, those tricky things. Logicians don't like those. They like statements that can be evaluated.

The sky is black.

You can notice certain features - It's unambiguous and specific, the premise holds the subject "sky" and adds an adjective(attribute or qualifier) that makes a proposition. It gives you something to think about doesn't it? Suddenly you think of empirical research to support or dispute this. It makes a claim that can be true or false but never both nor neither.

Easy to reason about no? Now imagine "sky" was data. Could be an array of integers, could be a string of unicode characters. Let's add an attribute to it. Let's call it "black" or "green". Ahhh!!!! now you see it yes? Sky is an object. This is the object oriented approach but remember here? in a functional universe there are no objects like Leibniz let's think of it as dy/dx lol. Think of it like a process. A transformation of data that may or may not be true. All of a sudden you're asking is_black(The sky).

WTFFFFF!!!

I said. Where is the sky coming from? is_black don't give AF. It only knows how to be black. The qualifier does not belong to the object, if you really think about it? It makes sense. Lot's of things can be black, you can have a black car or black shoes. Black can be a property yes! but it can also be a thing in and of itself.

Remember modal theory? Let me hint at it. Here it has become relevant but its proper introduction is still further ahead. How do we define an object? and how does it come to possess attributes? What is sky? is it the clouds, the air? The sum of its parts? Perhaps. Let's look at "black" it seems to belong to some kind of category? Yes? It is a color after all but if it's a color Then what is a color?

Such interesting questions oh such interesting questions. Just begging for intellectual attention :sigh: but I'm getting way ahead of myself. Let's pause for a moment, let me sip my entropying coffee.

Let's return to the familiar world of languages and symbols and introduce something foreign and scary, logical operators!!

[(R ⊃ T) v (S ⊃ U)] • [(W ≡ X) v (Y ≡ Z)]

Logicians and mathematicians use these sorts of languages. Scary isn't it? Looking at complex symbols and notations that are apparently meaningful but only to the initiated. It is reminiscent of a regular expression. This a symbolic expression of a premise. Albeit more complex than The sky is black but it's still the same fundamentally. Here we introduce something called a compound statement. You can think of it as a bunch of functions communication with each other(notice the parallel with fp? ). Let's break down the cryptic and make it bare.

The ~ means negation similar to the programming equivalent of not or !
The • means conjunction it is basically and or &&
The v is called a wedge it's means disjunction aka or or ||
The ⊃ is a horseshoe lol cute isn't it? it means implication in programming speak it's if(true) do: ...
Lastly the ≡ is a triple bar unceremoniously. You must know this from mathematics? yes it's equivalence. Verbosely called "if and only if" In programming lingo === or any operation that performs deep equality of type and value. The letters are expressions.

Can you notice something wonderful?

It maps almost identically 1:1 to a programming language that is turing complete. It is just one kind of a formal language expression, like NaCl or dy/dx these languages aren't like the natural language. They've done away with so much of it with their perfect rules that make them easier to reason about and as always what happens when I/O comes into play? What happens when we need to create useful ideas with this tiny vocabulary of notations and make ACTUALLY useful software that expresses ideas? That is what we are, the human component. The interface between not man, but ideas and computers.

What happens when the boundary of a program extends you? It gets messy. Problems. Problems and more problems. Programs create safeguards to protect you try except catch rescue and what not, this is where functional programming shines. It reduces complexity by offering a stream of ideas. Returning thought not to it's messy philosophical origin of a universal object but the even more odd idea of a deterministic mechanical process. :)