The Scholar

In Defense of the Hosted Language: Why Golang isn't the Catch-all, End-all

2018-03-17T07:50:00.001-07:00

When I first heard about Golang, I sincerely thought the JVM was obsolete. Its day was past in my head. After all, when I wrote in Go, I felt like I was writing in Java or Python, because it was garbage collected. At the same time, since it was cross-compilable, it was as portable as Java, but I didn't need to install a run time first. As a DevOps engineer, I really saw the benefit. I still do.

But as I have learned, it has its drawbacks. For example, say I want to write a GUI application. With the JVM, I can do all of it in pure Java. (Not that you would want to do this, but bear with me.) But I can't do it in Golang without using CGo. Why? Well, this is because you need to interact with native code to write a GUI because assembly is the language in which computer graphics speak (ish -- I know I'm glossing over details) and that is most easily interfaced with using a native language like C, C++ or Rust. With Java, I can bake that native code into the JVM, then call that native code using Java. With golang, I'm out of luck, precisely because golang is compiled and needs to bring all of its dependencies with it. With the JVM or similar runtimes, you can spend lots of time making sure a runtime compiles correctly on a particular system, then make that runtime widely available. After that, programming for it becomes really easy. I believe this is why Java's JNI is discussed much less (and, me guessing again, is probably used less) than golang's CGo.

Once you use CGo, you lose golang's benefits over java in the first place. In all honesty, I really like having exceptions and generics.

If I'm a DevOps engineer building a cross-platform desktop application, I really like the idea of using Go -- until we talk about CGo. At that point, I'm choosing between packaging a JVM in with my application (think Windows), or I'm compiling on every target OS for all of my libraries. The former is a lot of up-front work, but after that becomes easy; the latter is easier, but with lots of corner cases that will pay dividends in annoying bugs over time.

Even as such an engineer deploying an app to the Kubernetes cluster, CGo means that I have to really make sure I compile for the right version of glibc, which can be tricky and painful. I'd much rather deploy a Java app at that point.

So then I have come to the conclusion that Rich Hickey wasn't wrong: VMs offer some really nice features that you just can't get without them. They do present up-front distribution costs at times; but if you can nail that, your developers can continue to program and be productive, and have a clear, uniform path for getting features into the app without having to worry about the Cgo library land mines. (Full disclosure: I'm a Clojure fan. See what I did there?)

Making Kubernetes Approachable: We Need Strong Distributions

2018-02-22T18:34:00.003-08:00

Linux, in its raw form, is a complicated enough system as to not feel approachable by normal users. A nice distribution of it is easy enough to install and use, sure; but installing Gentoo Linux, for example, is much more difficult. The value of mainstream distributions of Linux such as Ubuntu or CentOS is that they made the installation, use, and upgrade path on a linux system approachable.

They do this in three ways:

1. They make installation of an entire system simple.
2. They make a lot of opinionated design decisions in an effort to make things simple. For example, most Linux distros choose what the init process should be for you (systemd, init, upstart).
3. They provide a clean upgrade path for all parts of the system, from the apps installed on the system down to the barebones part of the system (think linux kernel) through the use of a system package manager.

Now let's take those ideas to the wildly-popular-but-still-emerging technology, Kubernetes. Right now, how approachable is a kubernetes install?

Well, the first point is addressed well enough I think. Quasi-"distributions" such as kubeadm, kubespray and kubeform allow you to install the system simply.

They start to fall short when we get to point #2, though. Kubernetes does not prescribe how to set up DNS inside the cluster, and doesn't prescribe what kind of Ingress should be used. However, in my opinion at least, Kubernetes is most often unusable without these components. Other components that you'll almost always want include network overlay (many use flannel, ipsec, or calico for this). Most Kubernetes distributions supply these needs, but even the bigger ones like Rancher don't supply what should be used as an Ingress. Kubeform, or at least its Roadmap, is getting closer to this.

However, I feel like they all fall short in category #3, making an upgrade smooth by using an explicit system for dependency management. I have just tried upgrading kubernetes in Rancher, it is an absolute breeze compared to others I've seen on the internet; however, you still have to follow its docs to upgrade certain components before other components manually. Other distributions of Kubernetes likewise provide set-by-step docs. If Kubernetes is to really become approachable, this is not enough. I can follow docs to install Gentoo as well, but this is not nearly as approachable as the simple commands ``sudo apt-get update; sudo apt-get dist-upgrade``. There is no explicit dependency management for the entire Kubernetes system. There certainly is no system akin to aptitude or rpm that tracks dependencies for parts of the kubernetes system itself and the apps that run on it alike. The ansible roles and scripts provided by kubespray and kubeforms do not satisfy here. Kubernetes would take a great leap forward if such a system were ever developed.

And before you say "Helm!", helm is simply not built for this.

On Package Manager Architectures, Part I

2017-08-05T13:05:00.003-07:00

I am sort of a package manager junky. I even wrote my own package manager, capable of managing dependencies across programming language boundaries, called Degasolv. During the course of my travels, I've noticed some very significant things about package management architecture.

There are really three different kinds of package managers. Each fundamental type of package manager makes trade-offs. Each type is fairly successful in its own ecosystem. It is instructive to point out the differences.

Here I will treat the two most significant. The third type deserves its own blog post (assuming I get to it). For the curious, it includes ivy and maven, and I will discuss this one later.

The Main Differences

The first type is that of the system package manager. The archetype of this category is YUM, and more recently, DNF. In this model, the following facts are true:

Packages install files into a shared file system, and are shared resources. Only one package of each package name may exist in an installation at any given time. Packages may NOT share ownership of a particular file (RPM is actually pretty strict about this), and generally do not share resources.
Because of this, there must be agreement on package semantics. Since the "libc" package is a shared resource, all packages must agree on what "libc" means. This means that all packages must agree on an acceptable version of libc.
All packages are owned by the system, NOT by other packages. Java apps do not specify how to configure Java, for example. The systems administrator is in charge of configuring the Java package, not other packages that rely on Java.
No domain knowledge exists at the package level of the "type" of thing being installed; all DNF knows about are files. Packages installing a C shared library and packages installing a tomcat service are in some sense created equal.
At at least a theoretical level, circular dependencies are possible. It is possible to resolve the dependency of "a -> b -> a", by installing both "a" and "b".

Contrast this with a manager like NPM. NPM is the archetypal package manager of the second type of package managers, a class which I will call the "hierarchical package managers". Others include GX and Helm. It is very popular, and very different:

All packages are installed relative to the package requiring them. Therefore, packages are not shared resources. Package installations are only used by the package that depends on them. There are no shared resources anywhere (in theory); if A relies on B, it is the only package relying on B. If, for example, package A relies on both B and C, and package B relies on package C, then package B will get its own copy of C installed relative to B and package A will get its own copy of C installed relative to A. A and B do not share C at all.
Because of this, no agreement on package semantics is necessary. A and B in the example above do not need to agree on what "C" means; A can use 2.0 of package C and B can use 1.0 of package C and no one cares.
In this sense, packages are "owned" by parent packages. This can be seen in this category of package manager with the Helm pacakge manager. Values in the sub-packages' values.yaml (the package's configuration file) may be overridden by values in a parent package. Ownership, the sort of "care and feeding" that the depended on package needs to work, is provided by the depending package.
The package manager takes advantage heavily of domain knowledge. It makes assumptions about what is being installed and only makes sense in the context of some programming language or system, such as Javascript in NPM's case or Kubernetes in Helm's case.
Because packages are installed relative to the packages that rely on them, circular dependencies are not possible

On Shared Resources

The most interesting point in the above discussion, in my opinion, is that of whether or not a package is a shared resource. Consider this bug I filed with the Helm chart package manager. In it, I show that although the package manager Helm is of the second type, and therefore assumes that packages (in Helm nomenclature, "charts") are not shared resources, this is not always the case. In the default case, packages create services using names that assume that there exists only one package of a certain name in any given release.

In short, in order for a package manager to be of the second type, and for that to work, packages must truly and in every way must not be shared resources, ever. There are subtle corner cases in every language or system where this is simply not true.

Consider the example of two packages with a "mutual friend" package. In this scenario, Package Alice and Package Ben have a mutual friend, Package Cat. Alice talks to Cat and asks Cat to tell her the right amount of money needed to buy a horse. Alice then asks Ben to buy a horse for her, giving him needed money. Ben then asks Cat if the money given to buy the horse is enough.

The above example is contrived and tells the story of the classic diamond: Package A, which relies on Package B and Package C. Package B also relies on Package C.

Now consider if these packages were NPM packages. Package B's Package C is installed relative to B, and could be at an entirely different version than Package A's Package C. This version difference is perhaps breaking. So, what may end up happening is that Package Alice asks Cat how much money to use for buying a horse, and Cat's methods of figuring out how much money that is may have completely changed between Cat 2.0 and Cat 3.0 . So Alice's Cat 2.0 says she needs $1000, and she gives this to Ben. Ben asks Cat 3.0 if that's enough, but Cat 3.0 says "no". Now Ben gives an error and no one knows why.

This example shows that even though Ben and Alice do not share the same Cat package, they are sharing her as a resource. They rely on her expertise and believe that whatever Cat says is right. Therefore NPM's fundamental assumption that Cat is not a shared resource is violated. The developers of Alice don't talk to Ben's developers, but they're both in the same community and both have been told to use package Cat for all things horse. It's simply the de facto solution in the community.

Though contrived, this is a real problem. NPM tried to fix this by introducing "peerDependencies" for those packages where this really matters, and I think this isn't a bad plan. It allows packages to use the hierarchical method of managing dependencies, assuming packages aren't shared resources, for the general case, while allowing them to specify hard requirements when problems arise.

On Ownership

A second fundamental difference between these is ownership. I'm now considering the differences between RPM, a package from the systems family, and Helm charts, packages from the hierarchical family. I do this because charts are unique (as far as I can tell) because you can configure them using their values.yaml file from a parent chart. This means that in some sense depending packages in helm can configure their depended on packages.

Contrast this with RPM. A Java app like Jenkins installed via RPM would never presume to configure Java for you. Things like Java heap size are entirely up to the administrator. A central authority emerges in this model, where the sysadmin or <insert favorite infrastructure-as-code tool here> tool is responsible for configuring the package and making it work.

Which is Better?

I think this boils down to a discussion around where the authority should be. Should packages be made to share resources owned by a central authority (the sysadmin), or should they be given their own sandbox, allowed to use what's in their box with no regard to the needs of other packages?

This has a direct corollary question to human communities and how communication takes place, as it must. Should developer teams coordinate, often centrally? Or, should we try to isolate developer teams so that they do not need to coordinate or communicate?

This question sounds harsh, but do and must ask and answer this question all the time. It is everywhere. This is particularly true in DevOps, which is my profession. Do we make two teams' products share a virtual machine when we deploy their code, or do they get separate VMs? We usually choose the latter isolating them from each other. Do we make two teams' products agree on what version of PostgreSQL to use, though they will use separate databases? Yes; our support contract only supports certain versions of this backing, depended-on service. Both teams depend on the database admins, and the database admins's service won't work with theirs unless certain constraints are met.

So: as a package manager designer, which one do we choose? Do we enforce some coordination between packages? If we do, all packages will agree on semantics (e.g., package "B" will mean the same thing to all depending packages, because it will be the same version). All packages will need some central authority to configure them. If we don't, packages could be allowed to configure sub-packages, depending in turn on configuration given to them. Do we trust package authors to make the right configuration choices? They may be trustworthy, but will have no knowledge of other packages within the same installation. Will this cause problems?

Modeling Recursive Sum Types in C++11 Using boost::variant

2016-06-22T22:13:00.004-07:00

It's been a while. But here's something cool.

I used to love pattern matching with sum types in OCaml in college. But I also love how useful and ubiquitous C++ is. So I wanted pattern matching and sum types, but in C++. Well, people say boost::variant can be used as a sum type. The library boost::variant is fairly ubiquitous, well-maintained, and can even run on C++98, the older C++ standard. I can see how discriminated unions can implement “flat” sum types, but can it be used to implement recursive sum types?

Well, I decided to try it. It turns out, with a bit of scaffolding on my part, I was able to implement a recursive sum type. I tried to model the quintessential recursive type, the natural number, which is either zero or the successor to some other number. The following code shows the results of my efforts.

// sum_type.cpp
#include <iostream>
#include <boost/variant.hpp>
#include <memory>

struct zero {};
class successor;

typedef boost::variant<zero,successor> number;

class successor
{
private:
    std::unique_ptr<const number> num;
public:
    successor() = delete;
    successor(const number& n) : num(new number(n)) {}
    successor(const successor& s) : num(new number(s.n())) {}
    successor(successor&& s) : num(std::move(s.num)) {}

    const number& n() const {
        return *num;
    }
};

struct match_count : public boost::static_visitor<int>
{
    int operator ()(const zero& z) const
    {
        return 0;
    }
    int operator ()(const successor& s) const
    {
        // Do NOT use `return (*this)(s.n()) + 1`
        return boost::apply_visitor(*this, s.n()) + 1;
    }
};

number add(const number& a, const number& b)
{
    /*
     match a with
        0 => b
        S n => S add(n, b)
    */
    struct match_a : public boost::static_visitor
    {
        const number b;
        match_a(const number& b) : b(b) {}
        number operator()(const zero& a) const
        {
            return b;
        }
        number operator()(const successor& a) const
        {
            return successor(add(a.n(), b));
        }
    };
    return  boost::apply_visitor(match_a(b), a);
}

int main() {
    number a = zero();
    number b = successor(a);
    number c = successor(b);
    number d = add(b,c);
    match_count mc;
    int c_count = boost::apply_visitor(mc, c);
    int b_count = boost::apply_visitor(mc, b);
    int a_count = boost::apply_visitor(mc, a);
    int added = boost::apply_visitor(mc, d);
    std::cout << "a is " << a_count << std::endl;
    std::cout << "b is " << b_count << std::endl;
    std::cout << "c is " << c_count << std::endl;
    std::cout << "a + b is " << added << std::endl;
}

Output:

[ djhaskin987@djhaskin987-S301LA:~ ]$ g++ -o sum_type -std=c++11 sum_type.cpp
[ djhaskin987@djhaskin987-S301LA:~ ]$ ./sum_type
a is 0
b is 1
c is 2
a + b is 3

How about that?
I modelled the type as a discriminated union between “zero” and “successor”. Some interesting things I learned when I did this, or at least some things to note:

As long as you manage memory properly in the recursive cases, they work fine as part of the sum type using boost::variant.
It’s okay to have a type with no members (e.g. struct zero {};)
You can define anonymous classes inside function definitions. Here, they aren’t anonymous, but experimentation will show that you can (in C++11).
You can call functions recursively when you define structs inside those functions. That’s nice.
When defining “matching” structs inside functions, try to match variable names with class member names that they are used to construct. This saves time later reasoning about what’s going on.

svopt

2014-12-03T21:12:00.002-08:00

The optimization algorithm “vopt” applied to any optimization problem is simple. I now outline my own version, which I call “s-vopt” because it “swings” from one level of opt local search to another.

Convert your solution representation to a bit array.
Go through each bit, flip it, and see if it improves the solution. If it does, keep the bit flipped and repeat until there are no more bits that can be flipped to reach a local maxima (assuming you’re maximizing a fitness function). You have now reached a local 1-opt maxima.
Now flip each possible pair of bits, flip them, and see if the fitness rating improves. if it does, keep those bits flipped and go to step 2. If all the pairs have been tried without success continue to the next step.
Continue in this fashing, first trying to flip all possible triples, then quadruples, then quintuples, etc. until you want to stop. At each, if an improved solution is found, keep it and go to step 2. if not, continue on the next step.

Happy Mountain Climbing!

"Brent": the Story of the Volunteer Warrior, and The Mayhem That Ensued

2014-02-12T10:20:00.001-08:00

If you haven't read The Phoenix Project, I gotta tell ya, it's a good book (even though there is some language in it, admittedly true to life in many IT organizations). In there is a story of an engineer called Brent. Brent is crucial for most IT operations of any kind. Every thing he knows is in only his head, and documented nowhere. If anything is to get done, Brent needs to be involved.

A real time-bomb situation.

The book goes on to talk about how to diffuse this time bomb, but it doesn't talk about how to prevent it in the first place.

The Perfect Storm for Brent

This happened because of the "Volunteer Viscous Cycle". It happens when the dispatching of problems to engineers to fix them happens on a volunteer basis.

The following diagram shows, in essence, what happens in the volunteer workflow:

This is exactly what creates a Brent: an uncontrolled, volunteer-based dispatch system when problems arise. A team of engineers hesitant to jump in and help, and one volunteer, constitues a perfect storm for new Brents to form.

The New Problem

When a new problem arises -- a bug, a ticket, or an issue, depending on your issue tracking system -- engineers on a team often hesitate to take it, given that they can choose what problems to take and what to fix. They are not hesitant to take the issue because they are lazy or dumb. They are most often well-educated, highly-trained, seasoned engineers; however, new problems, never seen before, still daunt these engineers. Any engineer who takes it will make lots of mistakes, become frustrated, and spend lots of time fixing it. Further, they could use the same time to fix 3 problems that they know how to fix. So, they wait and see if someone else will volunteer to take this particular problem.

Enter Brent, a guy who just wants to get stuff done. He may be highly educated, or he may be just out of high school, but he has drive. He'll volunteer for anything, either because he's just trying to be helpful, or because he's trying to show that he is valuable, or simply because no one else will take the ticket. He's a first-rate volunteer, a real go-getter. And he's about to become a dumping ground for all sorts of problems.

Brent sees that others do not feel comfortable hacking at a problem and helpfully, proudly, or even meekly, volunteers. It takes him a while, but he eventually resolves the issue and everyone's happy.

Brent starts taking on so many of these new issues that people just assume it's "Brent's job" or "Brent's niche" to take on new or unusual tasks, and so come to expect them picking up the slack.

The Returning Bug (Uh-Oh)

Brent eventually takes on enough issues that a few of them reappear, or new issues appear which are related to older ones. This time, something in the server environment changed, which breaks a service that Brent has previously serviced. Everyone instantly sees this server is broken and remembers how hard Brent worked on this problem last time. They think that he'll be able to do it faster than themselves, and so it is assigned to him. He may even volunteer for to take the issue, trying to be helpful. Brent fixes it for the team. He learns even more about the server than he knew from the last time he fixed it. The problem is, others on his team know even less, because they stopped worrying about the server once the issue was given to Brent.

The Silo Effect

A long time passes with this process in place. It is now too difficult for all of Brent's knowledge to be documented. There's simply too much to write it all down, and quite frankly, too many fires that Brent needs to fight. When problems arise that have to do with "Brent" servers, the only one that can fix them is Brent. He is now considered a "crucial resource". It is simply a waste of Brent's valuable time to document issues already fixed, when there are so many current issues that only he can fix. There simply isn't time.

Diffusion

The Phoenix Project goes into some good detail about how to diffuse this situation. As a recap:

Limit Brent's work-in-process by using the kanban process.
Get engineers shadowing Brent.
Disallow Brent the keyboard. His shadows must do all the work.

Prevention

In order to diffuse Brent, you must put mulitple shadow engineers on him, lest he quit and you end up with "just another Brent". More than one engineer at a time must know how fix any given problem in their space of responsibility, and hopefully in more than their region of responsibility.

A great way to ensure this from the start to institute round-robin assignment of issues to members of the team. Rules:

Issues are assigned to members of a team in a round-robin fashion. This way everyone knows about everything.
If an engineer needs help on an issue from another engineer, he may request that the engineer document the process and then send him a link to the wiki page, but the only the engineer assigned the ticket, issue, task, or subtask must actually do the work. This way, every thing currently worked on is currently documented.

Rule 2 above is especially useful. If the wiki page is unclear, the author must clarify the wiki page so the engineer can do the work. If a particular engineer is called on to write multiple wiki pages, it is probably a sign that he has been a "Brent" in the past and so rule 2 naturally protects against such volunteer warriors. If everyone knows how to fix a particular issue, then the idea is that if a particular engineer needs help on that issue, he can ask the team, or otherwise a more or less random person. The main point is that the author or authors of the wiki page are asked to write it. This principle guards against volunteer warriors.

Rule 1 may seem inefficient, since some engineers naturally find it easier to solve some problems than others. It is not meant to be efficient; rather, it endows resilience to a team. You'll never find an IT team with efficiency problems, but I have yet to find one without resiliency problems. Lots of IT professionals will brag about how many VMs they can manage, or how fast they can fix a problem, but those same IT techs will tell you horror stories about when something went down and Brent was on vacation. IT organizations who follow Rule 1 will find that the tradeoff between efficiency and resiliency is worth it. Bugs will be fixed slower, but they will always be fixable, come rain, shine, or even (gasp!) a sick Brent.

EDIT: An earlier version of this article used "Brett" instead of "Brent". The character in The Phoenix Project is "Brent", so the name "Brett" in this article was changed to match the character, consistent with what I was trying to do on the first draft.

ratpoison and xdotool: How to Move the Mouse by Using the Keyboard in Linux

2014-01-16T18:59:00.001-08:00

We interrupt this blog for an important announcement: With ratpoison, you can use the mouse using keyboard bindings!

For those of you who don't know what ratpoison is, it's a window manager for linux, like fluxbox, GNOME, or KDE. It's designed to be able to work without a mouse (hence the name). Using ratpoison, I have found a way to use the pointer without actually using the mouse.

Here is my .ratpoisonrc file:

startup_message off
set font Mono-10
set bargravity nw
set bgcolor cyan
exec rpws -i
exec /usr/bin/rpws init 4 -k
source .ratpoisonkeys
source .ratpoisonmouse
set winname class

set border 0

And here is my .ratpoisonmouse file:

bind C-j ratclick 1
bind C-k ratclick 2
bind C-l ratclick 3
definekey top M-j ratrelwarp 0 16
definekey top M-k ratrelwarp 0 -16
definekey top M-h ratrelwarp -16 0
definekey top M-l ratrelwarp 16 0
definekey top M-y ratrelwarp -16 -16
definekey top M-u ratrelwarp 16 -16
definekey top M-b ratrelwarp -16 16
definekey top M-n ratrelwarp 16 16

definekey top M-J ratrelwarp 0 256
definekey top M-K ratrelwarp 0 -256
definekey top M-H ratrelwarp -256 0
definekey top M-L ratrelwarp 256 0
definekey top M-Y ratrelwarp -256 -256
definekey top M-U ratrelwarp 256 -256
definekey top M-B ratrelwarp -256 256
definekey top M-N ratrelwarp 256 256

definekey top F10 ratclick 1
definekey top F11 ratclick 2
definekey top F12 ratclick 3
definekey top M-i rathold down 1
definekey top M-o rathold down 2
definekey top M-p rathold down 3
definekey top M-I rathold up 1
definekey top M-O rathold up 2
definekey top M-P rathold up 3

The entries in the above file mean that if I type ALT+H,J,K, or L, I can move the mouse left, down, up or right. F10 clicks on stuff, and F12 right-clicks on stuff. The rest can be extrapolated, I think, by looking at the .ratpoisonmouse file above.

Don't wanna switch to ratpoison? You can do the same thing in any other linux window manager using xdotool. It's a commandline program that lets you move the mouse around, among other things. By binding keystrokes to different xdotool commands, you can get the mouse to move and click.

For example, here is what could be an excerpt from .fluxbox/keys, the fluxbox keybindings file to do move the mouse up, down, left and right as explained above, plus click the mouse:

Mod1 j :Exec "xdotool mousemove_relative -- 0 16"
Mod1 k :Exec "xdotool mousemove_relative -- 0 -16"
Mod1 h :Exec "xdotool mousemove_relative -- -16 0"
Mod1 l :Exec "xdotool mousemove_relative -- 16 0"
F10 :Exec "xdotool click 1"
F11 :Exec "xdotool click 2"
F12 :Exec "xdotool click 3"

Cool, huh?

How to Comply With the NSA While Maintaining Privacy For Your Users

2014-01-16T17:50:00.001-08:00

Silent Circle and Lavabit closed their doors because they didn't wish to give their user data to the NSA. This article describes how a web service can fairly easily store user data so that nobody--not even the hosting web service--could access private user data, except the user to whom the rightfully belongs. This can even be done while complying to the NSA. You can store metadata (the kind of data the NSA cares about) about a user unencrypted while still encrypting the user's address and telephone number fairly easily.

Storing Private Data Securely

First, let's go back in time to the Sony hack. This was especially embarassing to Sony because they stored all their passwords in plain text. For those technically normal people out there, there is a way to create data based on a password called a hash, store that data, and then use that data later to check whether a user entered their password correctly or not by making another hash and check whether it matches the stored hash. It is fairly easy to store password hashes instead of the password itself, and it is far more secure to do so.

Admittedley, it is a little more complicated than that. In order to thwart rainbow tables, web site owners need to store a "salt" (a large random number) for each user and then create a hash based on the salt and the password together. The bottom line, however, is that it is not that difficult to store a password securely.

It is not as easy (if what is explained above can be called easy) to store credit card information and addresses securely, and it is likely that the majority of web site owners don't even try to do so.

So how do you, as a web site owner, keep your users' personal information personal?

Like this: Elliptic Curve Cryptography. Briefly, ECC is a public/private key scheme, meaning you use one "key" (bit of data) to encrypt information and one to decrypt information. Since you don't care who encrypts your data as long as you can decrypt it, you share the "encrypt" key with everyone while keeping the "decrypt" key private, which is where the "public/private" part of the name comes from.

The cool thing is that ECC allows you to encrypt data with very small keys. For example, normally web site traffic using the 'https://' prefix use keys which are between 1024 bytes (characters) and 4096 bytes. Compare that to this string of characters, which is the ECC public key corresponding to one of my (old) passwords:

!Dw3K-efjB6S1A%a[Qc4jp?XOxC[XnY+6;@Zfc)ba,7^7O#6Oi(]^Q@@wSkg6h)M(]XX6?6ptt

The above string of characters is longer than a sentence, perhaps, but nowhere near the 1024 character essay. And the private key is simply as long as...say... a password. Let me state that again: the actual data used to decrypt user info under the ECC scheme IS that user's password. It now is possible, then, for a user to decrypt their data by typing in their password upon login to the web site. Further, since it is possible for a web site owner to not store a user's password (only its hash), not even the web site owner can decrypt private user data. The owner could then keep valuable meta data, such as log in and link-clicking history, while keeping data about the user which is doing the clicking private.

Here is what to do as a website owner to store user data securely.

Store the user's salt.
Store the hash of the user's password+salt. This allows you to securely check to see whether a user entered the right password on login
Store the user's username in plain text. While unfortunate, you need to store the username in plain text so that you can look up that user's data in the database. It is then incumbent on the user to use a private username, say "superSquirrel", instead of "Daniel.Haskin".
Upon registration of a user, generate and store that user's public key based on the the password they provide. (Don't worry; it is usually intractably difficult to get a user's password based on their public key.)
Use that public key to encrypt the rest of the user's data housed within the database.
When a user logs in to the web site:

The web site uses the username to look up the database entry.
The password is verified using the salt and hash.
The password is used to decrypt the user data.
The unencrypted user data can then be used while the user is logged in, but it is never recorded anywhere by the web site.
On log out (or the closing of the user session), the data is again encrypted and stored in the database.

If a hacker should hack into a web service which implements the above, the hacker cannot access anything of value (at least, anything of value to a thief). Each user entry is secured separately, so that even if the hacker had enough computing power to crack an ECC key (no mean feat), it would only yield one user entry per cracked key. There would simply not be enough time or resources to crack the entire database, even if the cracker were the federal government.

This plan would allow any web service using it to happily comply with the NSA and give them all the information about all the web service's users. This is because personal user data would be encrypted with a key that the web service doesn't have --- the user password. The web service would still store metadata unencrypted and then link it with the encrypted user data. That way, web service could still use the metadata for targeted marketing and data mining. It also means the NSA can then analyze the metadata. This gives them enough information to fight terrorism while also guaranteeing the privacy of individuals. In our example, they they don't know who user "#1acd3fr3" is; however, if their software flags that user as a terrorist, they can get a legal warrant asking a judge if they can go after the information for that username based on other means of investigation. But even if the NSA asked a web service owner who a particular user was, the owner would not be able to tell them, because they wouldn't have access to that information. Thus, the NSA can still do their jobs, and the web service can still use customer data to make more money, but sensitive user data can still be protected from hackers and "bad apples".

Tools of the Trade

Any database software vendor, such as Percona or Oracle, can get you the underlying database software needed. As for the encryption itself, a free and open-source implementation of ECC that I've come to know and love is called seccure. Some quick scripting to complete the algorithm that I have herein outlined should get any one seriously committed to user privacy well on their way to protecting their users' private data.

Dragon NaturallySpeaking, Vimperator, and Emacs

2013-12-30T06:50:00.002-08:00

My wife got me Dragon NaturallySpeaking for Christmas. It's been fun learning how to use it, but it's been frustrating learning how to browse the Internet with it. I ended up saying a lot of hotkeys while working with Firefox, such as "press ctrl+k" and "press ctrl+pgdn".

Then I discovered Vocola, which allows you to define your own custom voice commands. That, together with Vimperator, which I have already been using, it is now a breeze to use Dragon to browse.

I just installed Vocola according to the directions found here.

Here is my .vimperatorrc file:

set hintchars='0123456789'
inoremap <C-a> <Ins><C-a><Ins>
map J gT
map K gt
highlight Hint font-size:200%;color:white;background-color:red;padding:2px;

Simply put this file in your home directory. If you are using a Windows operating system, this is something like c:\Users\djhaskin987.

Then, with Vocola installed, use Dragon NaturallySpeaking to open Firefox, and say "edit voice commands", and paste the following:

 # Voice commands for firefox
visit <_anything> = {Esc}":open $1";
close tab = {Esc}d;
open tab <_anything> = {Esc}":tabopen $1";
follow <_anything> = {Esc} f $1;
follow tab <_anything> = {Esc} F $1;
next doc = {Esc} J;
previous doc = {Esc} K;
back = {Esc} H ;

Viola! Easy browsing by speech. Just say "follow ", or just "follow" and then say the number that pops up next to the link. To open a webpage, just say "visit" followed by the address. Vimperator will give you a menu of options. A couple of "press tab" and "press enter" commands later and you're in business.

I also plan to use Vocola and Dragon NaturallySpeaking to improve my programming by defining some voice commands for Emacs, sort of like Tavis Rudd, only Vocola is way easier to define voice commands with than Python.

Here is my Vocola file so far for Emacs:

# Voice commands for emacs
<number> := 1..99;
open file = {Ctrl+x}{Ctrl+f};
boom = {Enter};
undo = {Ctrl+Shift+_};
die = {Alt+Backspace};
back = {Backspace};
whack = \;
um = {Alt+b};
curly = "{";
close curly = "}";
paren = "(";
all in = ")";
the <_anything> = $1;
start = {Ctrl+a};
end = {Ctrl+e};
camelize <_anything> = {Alt+x} camelize {Enter} $1 {Enter};
left = {Ctrl+b};
<number> up = {Ctrl+u} $1 {Ctrl+p};
<number> down = {Ctrl+u} $1 {Ctrl+n};
<number> left = {Ctrl+u} $1 {Ctrl+b};
right = {Ctrl+f};
up = {Ctrl+p};
down = {Ctrl+n};
go = {Alt+f};
scroll down = {Ctrl+v};
scroll up = {Ctrl+v};
cut = {Ctrl+k};
yank = {Ctrl+y};
nay = {Alt+y};

The function "camelize" is an emacs lisp interactive function which takes a phrase like "the grand old duke of york" and turns it into "theGrandOldDukeOfYork", kind of like what is found in the emacs wiki, but changing from space separated instead of underscore separated, and making the function interactive as well.

I hope to also use Emacs templating like Tavis Rudd does in his video to make functions and classes by speech easier in Emacs.

EDIT: I'm putting my vocola files for easy browsing and programming by voice in a git repository. Pull requests wecome!

Mancakes

2013-12-19T09:25:00.001-08:00

What do you want? I dabble.

I have this amazing pancake recipe I made up.

I take this from the original "German Pancake" recipe my wife found, but that was baked in the oven. This is in a pan.

It's called a Mancake rather than a pancake for the following reasons:

It has tons of eggs (protein) in it
It is dead simple -- only requires a 1/2 cup size measuring cup and a teaspoon. (For those of you who subscribe to the metric system, a 1/2 cup is 120ml and a teaspoon is 5ml).
The recipe serves one (1) hungry person (likely, therefore, a man).

Here it is:

1/2 cup milk
1/2 cup (whole wheat pastry) flour
2 eggs
4 teaspoons (olive) oil (20ml, or 1/12 cup)
1 teaspoon baking powder, or 1 teaspoon baking soda and 2 teaspoons (apple cider) vinegar
1 pinch salt

Combine ingredients in a slightly-larger-than-normal bowl using an ordinary fork. Pre-heat your (electric) stove to a "6" (just past medium heat) while your skillet is on that stove. Pour 1/2 cup of batter onto the skillet. When there are a bunch of bubbles on the mancake, place your spatula under the right half of the large mancake and flip (or, for lefties, the left half of the mancake). Wait one minute, then take out of the pan and repeat. Makes 3 mancakes. Serves one. Enjoy.

Moving On

2013-12-16T09:56:00.000-08:00

So I could put another post on here about the genetic algorithm, but everything I wanted to say on the subject has been said about that particular algorithm.

Rest assured, I have many more ideas about optimization algorithms. But let me tell you -- it's getting frustrating. A lot of my ideas about new algorithms for optimization include this RankedSet idea... and it doesn't exist in standard libraries.

Michał Marczyk made one for Clojure called avl.clj (great job, Michał!), and AVL tree implementation of what I call the RankedSet, but the genetic algorithm as below described (and other algorithms bouncing around in my head) need faster insertions/deletions and virtually no lookup. That is precisely what red-black trees are better at over AVL trees. I need a red-black tree based implementation.

So I decided to learn how to make one.

I am currently going through Chris Oksasaki's "Purely Functional Data Structures". (Even just reading the first chapter, you can tell Rich Hickey idolizes the guy, and for good reason.) For those who don't know, this is a seminal work on how to design your own rock-star data structures. A quote from the first chapter:

Rather than attempting to catalog efficient data structures for every purpose (a hopeless task!), we instead concentrate on a handful of general techniques for designing efficient functional data structures...Once you understand the techniques involved, you can easily adapt existing data structures to your particular needs, or even design new data structures from scratch. (p. 4)

I am even learning OCaml so that I can go through it better (most of the examples in his book are in standard ML, which is to OCaml as C is to C++, as far as I can tell).

Hopefully at some point into it I'll be able to make a RankedSet, share the implementation, and keep writing about awesome algorithms.

The New Genetic Aglorithm: What Makes It New

2013-09-03T20:42:00.003-07:00

In the last post of my 'New Genetic Algorithm' posts, I talked about the RankedSet, which is the backbone of the algorithm, and what makes the algorithm fast. In this post, I'll talk about what makes the algorithm easy to use.

Keeping it Simple

Nobody likes using a tool with a bunch of dials and switches on it. Would you rather use a drill with five dials on it with labels on those dials that look like they have made-up words on it? And you're thinking, "I just want to drill a hole!"

You are not alone. Most people, when faced with using something like a drill, or washing machine, or algorithm, would much rather use an 'on' switch than anything else.

The thing is, most genetic algorithms that I've come across have five dials on it, which all need to be set properly in order for the algorithm to work:

The fitness function
When to stop
What the kill-off rate will be
What the mutation rate will be
The size of the initial population

I believe that the genetic algorithm is only used, either in heavy industry, or academia, precisely because it has five dials and switches. One almost needs an algorithm to solve the problem of how to set these "dials"!

So, a major goal of this new genetic algorithm is to take the algorithm to the masses. It asks the question: "What would a normal person care about?"

A normal person would care about the first two things in the above list:

the fitness function and
when to stop.

A "fitness function" is a set of instructions given to the algorithm to score the solutions it finds. To stick with our previous post's example, the "solutions" represent which strategy to employ in getting food for my family on the way home from work: Do I get takeout? Do I get fast food? Do I go home and cook something? etc. It's easy to tell an algorithm "I want food quickly, and I'm willing to spend a little to get good food, too." A statement like this is, in essence, the "fitness function". With this fitness function, the genetic algorithm would score 'getting takeout' high, and 'cooking at home' low. The fitness function is both easy to understand and essential for the algorithm to work, we'll probably keep this as an input to the algorithm as it is.

The question of "when to stop" is also relatively straight forward to answer for the user of the algorithm, but hard for the algorithm itself to answer. Something like "stop when you can't find anything better" or "keep improving your solution until 7am tomorrow" is both an easy and a relative piece of information for a user to give the algorithm, while it is hard for the algorithm to guess at when to stop. See, the genetic algorithm can just keep. on. going. It will find try to find better and better solutions until you tell it to stop. This makes sense. There are a million ways, for example, to get food at the end of a work day. However, I usually know as a user when I want to stop looking for a better solutions. Telling the algorithm when to stop is telling the algorithm when the solution it's trying to find is "good enough". Therefore, this parameter also makes sense for the user to provide.

It's the other three that can be thorns in a user's side. There is no intuition that can help the user determine what 'kill-off rate', 'mutation rate', or 'population size'. These three parameters need to be set and set well, but the only way a user would know how to set them is trial and error. The New Genetic Algorithm is cool, not only because of its back-end efficiency, but its front-end user friendliness: it knows how to set those three parameters for you.

Setting The Parameters

Kill-Off Rate

Most genetic algorithms will ask you to specify a kill-off rate: a percentage of your population which should be killed off at every step of the algorithm (each "season", if you will). It asks the question: at each iteration, how many of the "weak" of the population should die? This rate also dictates the number of new solutions created at each step, since in general the algorithm should deal with a fixed population size.

So what should our algorithm choose as its kill-off rate? 5%? 10%? 2%? All of these choices seem so arbitrary. There really isn't a choice I have found that makes more sense than the others. Too many killed off, means you won't get as good of results as you could have. Too few, and it will take a while to get there.

It should be stated here that kill-off rate is kind of related to something which in other algorithms is called "learning rate". The higher the kill-off rate, the faster the solutions will improve; however, the slower the kill-off rate, the better the results will ultimately be, even if it takes a while to get there. The kill-off rate represents the 'price/quality' tradeoff: more quality = more time = smaller kill-off rate; less quality = faster running = greater kill-off rate. What would be really cool is if the algorithm could choose the kill-off rate based on how much time it was given to run (when to stop). That way the user only need specify when to stop and the algorithm knows how long to run.
In that light, and for reasons that will become clear later on in this series, I simply chose to kill of one (1) solution per step. This essentially means that the population size ultimately decides this kill-off rate. If I have 100 solutions in my population, that means the kill-off rate is 1%. If I have only 10, it means my kill-off rate is 10%. This may seem like a bad thing, but what it does is that it allows us to choose kill-off rate based on population size. In other words, by making kill-off rate dependent on population size, we can control how fast the algorithm learns by only regulating one variable (the size of the population). This makes thinking about how to tell the algorithm how fast or slow to learn much easier. It also makes the single step of the algorithm very fast and gives it more predictable results.

Mutation Rate

A small word should be put here about how creation of new solutions in the population works.

Mutation relies on the fact that, all bit strings of length n specify a solution. It flips one of its bits at random. The genetic algorithm doesn't see the solution for a solution; rather, it just sees a bunch of 1's and 0's. This is consistent with nature. Nature doesn't see a bacteria for what it is; it just sees a bunch of DNA. The 1's and 0's are the solution's "DNA". Thus by flipping one of the random bits in the solution, we mutate the solution.

There is a small amount of math involved here, but not bad; just enough to keep things interesting.
We want to choose a mutation rate (the percentage of the population getting this random bit flipped) intelligently. The new algorithm is herein designed to choose it to maximize the diversity of the population.

Here in our new algorithm, we want a highly diverse population. If you have many solutions that are roughly the same, what is the benefit of a population at all?

A Side Note About How We Create New Solutions

In the new algorithm, we will use single crossover to create a new solution. There are lots of ways to create new solutions, but as we intimated in the beginning, we like to keep things simple in this new algorithm. This just means we pick a random number between 0 and n (the size of the solutions -- the number of bits they contain). Call that number p. The first p bits come from the first p bits of one solution (the "mom") and the rest of the bits come from the other solution (the "dad").

Who shall we chose to make new solutions? the two best, or part of the 'party' of the elite of the population? Perhaps we could, but here in our new algorithm, let's keep things simple. We will simply take two random solutions from the population and pair them up to create a new solution.

Why This is Important to Choosing Mutation Rate

Now let's reiterate our problem. We need to choose mutation rate to maximize diversity of the population. In order to ascertain diversity, we need a population sample.

But we just chose two solutions at random to create a new solution. Why don't we just use the two solutions we just chose as a small "sample" of the population of solutions? That way, we only need to retrieve two solutions per iteration, kill one off, create one, and possibly mutate one. Genious! then the iterations can be done very fast.

How do we determine if the population is "diverse"? Simple: we count up how many bits at each position from 1 to n in the bit strings of the mom and dad solutions are the same. The more that are the same, the more "the same" the population is and the more it is due for a mutation. Then, if we do decide to mutate a solution, we will simply mutate one of the solutions and re-insert it back into our population.

We will use this formula to determine the probability of whether we should mutate one of the parents:

P(m) = 4*(1/2*k/n - 1/2)^2

Where P(m) is the probability that we should mutate one of the solutions, n is the number of bit positions for solutions, and k is the number of bit positions where both parents share the same value.

This is a nice, easy-to-compute, bowl-shaped function that actually looks a lot like the information entropy function for two values. That's math-speak for "it worky."

Think about it -- If about half the bits are the same, which you would expect that from two random solutions, the probability of mutation is small, since the two solutions are expected to look pretty different from each other -- around half their positions are different. The closer k/n gets to 1 or 0, though, that value goes to 1, or 100%, meaning that one of them really should be mutated, since each solution looks too much like the other, or that they look like polar opposites, both types of which we would not expect in a more diverse population.

After we have computed P(m), then we just get a random number between 0 and 1. Call it r. If r < P(m), then we mutate one of the new solutions and re-introduce it to the population. If it isn't, we simply put both parents back un-mutated.

There! we have chosen a good method for choosing mutation rate dynamically. It is chosen at each iteration, is easy to compute, and makes sense for the goal.

Population Size

As New Genetic Algorithm designers, it's our job to figure out how best to determine population size. This is the size of the RankedSet discussed in the last post of the number of "indigenous" solutions that we'll keep around. We need a base population if we want to kill some off and create more and still have the genetic algorithm to work. So how do we choose population size?

Remember earlier, when I said that by determining population size and keeping the kill-off rate at one solution, we determine the 'learning rate'? When we have a small population size, say 10, the learning rate/kill off rate is 1 / 10 = 10%. This means the algorithm will improve fast, but also plateu fast.

Why don't we just wait for it to plateu at some improvement level, then when it does, we increase the size of the population? By doing so, we decrease the learning rate, allowing the algorithm to find an even better solution, even if more slowly.

To keep things simple, let's just say this: We'll start off at a population size of 16. When we find that no more "improvement" is to be found within the population, we double population size and continue iterating. We keep doing this until we are supposed to stop, which is something that the user supplies!

Simple, easy, intuitive, and easy to implement. These are the goals of the new genetic algorithm.

The RankedSet: Optimization's Best Friend

2013-07-05T19:16:00.003-07:00

This post is the second post about the 'New Genetic Algorithm' that I posted about previously.

What We Need

See, when you're running the genetic algorithm -- that nifty way to solve problems by computer -- you need to store different solutions to the same problem. For example, suppose I need dinner for my family tonight. Do I cook at home, grab some fast food, or buy a TV dinner at the local grocery market? These are different solutions to the same problem: my family needs food.

While the genetic algorithm (any genetic algorithm, including this new one) is running, it needs to maintain a "population" of such solutions. It keeps around, say, 100 solutions, kills off some, and adds new ones, but it always stores so many solutions (e.g. 100) at all times. In my new genetic algorithm, it will be important for reasons explained in a later post for the algorithm to be able to figure out the rank of each solution. Rather than knowing how much better one solution is from another, I feel it is important only to tell which solution is better than the other. When we make a buying decision, it does not matter if one option is a little bit better or way better, we usually just take the better option. This idea is important, and in the algorithm it will become important to be able to find a solution within the "population" and be able also to delete it based on its rank. I need to be able to say to the data structure, "give me the 45th best solution" and out it pops. I also need to be able to say, "kill off the 32nd solution". So, in order to store the population so that I can easily find, delete (kill off), insert (introduce) a solution into my population, the question is: what is the best way to store my population in a computer?

It turns out, there really isn't a data structure in any standard library I've found that can do the job. By the way, for those purist logicians who are craving a formal specification of what 'the job' is, sink your teeth into this:

The data structure needs to store information about each solution. If this is the 'bring home the bacon' example, it needs to store stuff like 'store location', 'what to buy', etc.
The data structure needs to store information about the rank (e.g., best, second-best, 43rd-best) of each solution.
The data structure needs to have efficient retrieval, deletion, and insertion. It needs to be able to delete a solution given its rank, and retrieve a solution given its rank.

Fanfare, Please: Enter the RankedSet

Why We Like It

The RankedSet will solve the problems I have stated above. You can store a solution to a problem in it, you can tell the set how great the solution is, and it will assign ranks for you based on how good each solution is. It provides retrieval and deletion based on rank and all retrieval, deletion, and insertion runs in logarhmic time. For those non-nerds out there, that means it does what we want it to, and it does it at speeds that take the cake.

Here's how it works: when we insert a solution into the set, we give it two values: how good the solution is, which we will call the index, and then the information about the solution itself, which we will call the payload. Since we'll rank the solutions in the set based on the first value, it needs to be a number -- a score, or perhaps in some cases, a monetary amount, etc. The payload can be anything we want, but in this case it is information about the different solution that we will put here.

How It Works

But how does it work, you say. That's the juicy part, right?

Computer Scientists know that what I am about to describe, is, basically, a Binary Search Tree, or BST. Each solution has at most two "children" solutions--one with a greater index than itself, and one with a smaller index.

With each solution is stored three things:

The solution information itself.
How "good" the solution is.
How many other solutions are "downstream", or, how many "descendants" the solution has (including itself).

It's number 3 in the above list that's the interesting bit. every other part of the description of how the solutions are stored is just a regular ol' BST, easily found in most any standard library in most any computer language. But no BST I've ever found has #3 in the above list stored in it, and so cannot function as a RankedSet.

Note that the value for #3 can never be empty. If there is a solution stored with no "children" solutions, #3 value is just "1", since it is the number of solutions that are descended from a node, including itself.

If every solution in the tree stores #3, then it becomes easy for the BST to look up a solution based on rank. Say that I need the 13th best solution in the BST. I ask the "root" node (the very first solution, with no parents and all children) to give me the 13th best. It asks the 'greater' of its children how many children it has. Say that number is 10. To few. It asks its lesser child again how many children that it has, which might be 20. So, it tells its lesser child to find the 2nd best solution in its family (13 minus the 10 best on the greater side, take away the root node itself, which leaves 2). If that sound hokey to you, then just trust me: it works, and it's fast.

Further explanation would boggle the mind of those of my non-egg-head readers, and is not necessary for those already familiar with binary search trees. Suffice it to say that caching the number of descendants of a solution, including the solution itself, allows us to find and delete solutions based on rank.

So What's It All Mean?

It means that we can now construct an algorithm that does not have to concern itself with how great a solution is, only if it is the best one. At the same time, it also means that the algorithm only has to know how good a solution is when it is inserted into the population, and from then on it need only talk about weeding out solutions that are weak, like the 75th best solution, and promoting the strong ones, like the 2nd solution. It means that it can talk about the rank of those solutions without ever actually retrieving them until it is time to kill the weak and create the strong. This makes our algorithm really fast and very effective.

Up Next

In the next post I will talk about how the algorithm uses the RankedSet, how it chooses how many weak to kill off and spawn, how it chooses how many solutions to mutate, and how easy those choices make it for programmers to use the new genetic algorithm to solve the next big problems.

A New Genetic Algorithm

2013-05-20T09:23:00.002-07:00

I have recently been fascinated with the genetic algorithm, which is a method that allows you to solve pretty much any big problem via computer, like finding the most nutritional, affordable lunches for a week for your kids, or what's the best NFL schedule (funny that these problems are provably equivalent).

The idea is simple. generate a bunch of mediocre solutions, kill off (eliminate) the weak ones, use the stronger ones to sire more solutions, mutate a gene (aspect) of some solution or other just to shake things up, and repeat.

The problem is all of the different ways to do it. Should we mutate 5% of the solutions, or 10%? How many solutions should we kill off at a time? How many should we make? There are alot of design decisions to make when using this algorithm.

And then there's efficiency to think about. How should the solutions be represented (e.g., what stats should be encoded)? What data structures should be used? What complexity class is acceptable (has to do with how much time the program takes to run)? These questions may sound unimportant from a business perspective, but it's the difference in an app between 'wow, that was zippy' and 'that sure took a long time to load'.

The 'data structure/data representation' question is particularly important because not only does it deal with how fast the program runs, but how maintable the code base will be in the future. When, as a programmer, I code up a solution to a problem, it is very difficult to change the way the data is represented and stored in the future.

I have given all these problems some thought, and I have come up with (I believe) a very good solution. The data representation is versatile. The data structure is maintainable, efficient, and convenient. Best of all, I have found a convenient way to get rid of all those parameters (i.e., I have adequately answered all of the 'how/what' questions about the algorithm, listed above).

I will post a series of articles detailing what I did to create a genetic algorithm which needs only be given a fitness function and the size of the population of solutions -- nothing else. It is fast, usable in a highly varied number of fields, and its operation is intuitive.

My first post will deal with the data structure / data representation problem. My second will deal with removing the how-many-to-kill-off/how-many-to-reproduce/how-many-to-mutate problem. My third post will tie it all together. Let me know in the comments below to join the conversation and let me know how I'm doing as I go. I will try to answer any questions given.

2/3 Swing Follow-up

2012-04-18T17:43:00.000-07:00

So the algorithm I spoke of in my last post is actually very similar to an algorithm known as v-opt. The difference between 2/3 swing and v-opt is that in v-opt, before ensuring that the solution is an n-opt minima, first ensures that it is also a k-minima for all k < n. So then, the solution is guaranteed to be gets to a 2-opt minima, then a 3-opt minima, and stops, whereas mine swings back and forth. This difference is further seen when 4-opt is introduced. Then, v-opt would find a 2-opt minima, then a three-opt minima, then ensure it is at a two-opt minima again, then ensure it is in a three-opt minima again, etc. Finally, when both 2-opt and 3-opt minima is found, it ensures it is in a four-opt minima, then a two-opt minima, then a three-opt minima, then a two-opt minima again, until it is in both 2- and 3-opt minimas before it checks for 4-opt minima, etc. I know, kinda confusing.
Mine just ensures it's in a 2-opt minima, and goes round-robin instead of making sure the solution is a minima of all opt's below the current one (both 2- and 3- opt before we ensure 4-optimality). It just goes round and round - 2-opt, then 3-, then 4-, then 2-, then 3-, then 4-,... I found this approach did alot better than conventional v-opt as I understand it.
That may have been a little confusing, but I wanted to make sure I tied in my own research with what's already out there.

The TSP Refinement Solution, Continued: 2/3 Swing

2012-02-28T07:43:00.003-08:00

The work on the algorithm I spoke of in my last post bore fruit! It works very well and uses perhaps previously-unbeknownst-insight. The outline of the finished product I lay before you now.

The attached contains the empirical data I gathered about how well my algorithm works.

I received some surprises, and other things did not surprise me. I guessed my algorithm would perform somewhere around O[(n^3)log(n)], and as you can see by the graph, it is quite possible that it did. I was surprised to find, however, that the relationship between how well the greedy algorithm did versus how well my solver did (I call it the "2/3 swing" algorithm) was linear - about 1.3x better than greedy. Perhaps this is because I started out with greedy and can only get so far refining any given solution. Perhaps if I started out with a closer approximation, I might get closer to optimality.

You see, the way my algorithm works is that it takes an initial arbitrary solution - in the case of the data provided, the algorithm started out with a random greedy solution - and, essentially, then gets into a 2-opt local minima. But the insight I gained in creating this algorithm is that a 2-opt local minima is not necessarily a 3-opt local minima. In fact, it rarely is. This is like multi-dimensional gradient descent - as there is rarely a minima across all dimensions in gradient descent, so there is rarely a minima across all opt's. At least, that is the idea of the algorithm.

Here's another clincher: getting into a 2-opt minima for assymetric, incomplete graphs (TSP city maps) has roughly the same complexity as getting into a 3-opt minima, since a linearly-large portion of the path must be reversed for each check to see if the change is an improvement. This makes a thorough 2-opt check, whose search space is in O(n^2), take O(n^3) time. To find a 3-opt local minima, the search space is in O(n^3) and the check is in O(1), so finding a local 2-opt minima, then trying to find a local 3-opt minima, doesn't cost much more by way of complexity, residing only in a constant factor increase in time.

The way that this algorithm gets itself into O(n^3*log(n)) time (or O(n^3.22), if the graph's regression line is to be believed) is by continually "swinging" back and forth between using 2-opt and 3-opt to find the next minima, so that a series of operations in O(n^3) time is looped over a few times. Between using 2-opt and 3-opt, city swapping is employed (taking two arbitrary cities on the best route so far and switching their places as far as order of visitation if such a switch improves the route's score) so as to "mix the bag" between swings. This operation is a small subset of 4-opt, and because it is only in O(n^2) it does not hurt complexity much. Additionaly, since this algorithm works on asymmetric city maps, a reversal of the direction of the route is checked to see if it improves the score on each "swing". This check is linear in time and also does not greatly affect the complexity of the algorithm. Thus the algorithm follows:

best route so far = (initial-approximation-solution)
best cost = infinity
while best cost > best route so far's cost
best cost = best route so far's cost
reverse best route so far if that improves it's score
best route so far = (next 2-opt local minima)
best route so far = (next swap-cities local minima)
best route so far = (next 3-opt local minima)
best route so far = (next swap-cities local minima)
return best route so far

As I cannot post the original data, I will only post the graphs. Original data upon request.

Technical Data:
Platform used: C# on .NET 4, running on an Acer Aspire One 532 netbook
Initial solution (used in refinement): random greedy
City Map: Assymetric, Incomplete

Acknowledgements:
I used the C# TSP Framework provided by the CS department of Brigham Young University.
Code was used in studying this problem which was written by Jimmy Hales (see previous post), although all the code used in the 2/3 swing algorithm is original to the author of this post. Dr. Tony Martinez of Brigham Young University served as adviser during my study of this algorithm, and thanks to him I continued to work on it.

An Idea for the Refinement of a TSP Solution

2012-01-04T19:37:00.000-08:00

Although I found through experiment that my probabilistic approach to finding a good TSP solution didn't work so well, I did manage to find a polynomial time algorithm that can take an arbitrary solution to the Traveling Salesperson Problem (TSP) and refine it to the optimal solution (with what I have tested so far). I do not know if this polynomial refinement-to-optimality is possible for solutions bigger than 20, as the exponential branch-and-bound solver at my disposal can't do very much given the hardware I have on which to run it.

Now, I think what I have found here MIGHT be awesome.

At any rate, I can explain what it does.

First, we assume an asymmetric directed graph of cites, wherein not every possible edge exists -- i.e. The number of edges in the graph |E| < |V|^2, where |V| is the number of vertices (cities) in the graph (map of cities). For simplicity, if an edge does not exist from one city to another, the reverse edge also does not exist. It can be quickly checked that this problem is still NP-Complete.

We may take this graph to be a map of roads between cities, and the weights on the edges (roads) to be a score of them based on the distance between the cities and the elevation difference between the cities, i.e. if one city is higher in elevation than another, the edge going from the higher to the lower is going to be scored lower than the edge which goes from the lower to the higher, because it is easier to go downhill. Looking at such a real map of cities and creating a graph from it, by scoring the edges as above, we find a distinct pattern in the optimal solution to the traveling salesman tour of the cities considered:

In some sense, the solution forms a "polygon" in the sense that no loops are created. So, this:

would be a better solution than this:

Provided we are looking at the "actual" city map, this is a fairly good heuristic for "goodness" of a solution, if not a requirement for optimality. Looking at the actual city map is important because the actual euclidean distance between cities is taken into account in the scoring of edges, and so these "twists" show up on the actual map, whereas if we just have the graph information, this intuition would not make sense since placement of the node on paper of the equivalent graph has nothing to do with the edge weight. Again, it should be noted that the graph (city map) upon which we consider is asymetric and incomplete, and so is still worthy of discussion.

To further shed light on this discussion, it will be assumed that the optimal tour through a given number of cities will be represented by a list of cities, with the order that the city appears in the list being the order of its visitation on the TSP tour. I now take from an excerpt of an email I sent to my CS professor Dr. Tony Martinez on the subject.

To refine a given approximate solution, I observed (as explained above) that approximate solutions often have "twists" in them - that is, they were not polygons since their vertices crossed. So I take the solution and try untwisting any arbitrary segment of the solution (that is, reversing that segment - e.g. take the segment # 2, 3, 4, 1, 5 and change it to # 5, 1, 4, 3, 2) and see if that operation improves the score. If it does, I return the improved route, else I return the route the untwisting method was given. [author's comment: if done properly, this part of the algorithm can be done in O(n^2) time.]
Now (empirically) I have observed that the approximate solution is now a polygon (no twists). But it may not be the "right" polygon. To try a different polygon, I simply take an arbitrary subsegment of the solution and splice it into a different part of the whole solution. Example: If we have a solution of Cities # 2, 4, 7, 5, 8, 1, we take an arbitrary sub segment of cities # 4, 7, 5 and try the solution where they are inserted in between 8 and 1 to produce # 2, 8, 4, 7, 5, 1. I try all such possible splice combinations, and see if they improve the score, returning any improvements. This search space, though it be search by brute force, is only O(n^3) large (what's more, being a brute force search, this and other improvement spaces given below can be searched in parallel). I find (again, empirically with our CS312 TSP [Framework] code) that this operation changes the "polygon" to a more optimal one.Finally, for sugar, I take this new and improved solution and select two arbitrary cities along its path and swap them, so that a tour which was city # 2, 3, 8, 7, 1, 4 becomes # 2, 1, 8, 7, 3, 4 if we swap the cities 1 and 3, thus changing the order in which they are visited.
I repeat these three steps - untwisting, segment swapping, and city swapping - for as long as they "help", or as long as any one of them return an improved solution. I find that the number of repetitions is usually small - 3 or 4 times for 50 cities (when it is given a best-of-greedy initial approximate solution, which is an algorithm in O(n^2) time). [author's comment: these were my results when, instead of stopping during untwisting/segment splicing/city swapping at the first improvement found, I tried all available twists/splices/swaps at one time and used the best of those. The results might be higher if the suggested stop-at-first-improvement approach is taken.]
For 20 Cities, I have verified that it spits out the optimal solution over and over again, and in much faster time than branch and bound. I do not have the resources to try for the optimal solution for more than 20 cities using C# code on my laptop [which is a netbook. Details: Acer AspireOne 532h, 2GB RAM, 1.66 GHz processor, running C# .NET executable under Windows 7 Starter].

Thus, I believe this whole algorithm runs in O(N^4) time, which is certainly not exponential. The inner loop (untwisting, splicing, swapping) can be done in O(N^3) time and O(N) space, and it is entirely possible that in fact this algorithm is in O(n^3*log N) time, more empirical study needs to be done to decide if that is indeed the case. While largely untested for bigger N, in the tests I have run it finds the optimal solution every time for city maps with city counts < 20. I know, it's not a big number, but this may still be a very good refinement of a given solution, if not a way to find the optimal solution.

I wonder if anyone could try this method of solution refinement and corroborate my results. Thank you all so much for your comments. I hope someone can further this effort by trying this refinement solution out themselves and comparing their results to known optimal solutions of the graphs upon which they are testing this refinement solution.

Acknowledgments: The code for the Branch-and-Bound solver I used is authored by Jimmy Hales. The C# framework out of which I performed the empirical tests was given to me by the CS Department of Brigham Young University as part of a class assignment for CS312, mentioned in the above letter excerpt as the CS312 TSP (Framework) code.

Update on the Probabilistic TSP Algorithm

2012-01-04T17:57:00.000-08:00

Basically?

It failed. Miserably. If we rated the edges based on what I said below, it may have even given us the worst possible path (a great achievement if it were so!) and if we took the edge weights into account in the ratings, the algorithm pretty much spat out roughly what a greedy solution would have anyway. However, I am glad to have done it. It gave me a lot to think about with the Traveling Salesperson problem.

An Idea for a Probabilistic Approximation of the Solution to the Travelling Salesman Problem

2011-11-22T06:05:00.000-08:00

In one of my classes here at Brigham Young, our group has been asked to come up with a unique idea for getting a good approximation to an optimal tour in the traveling salesman problem. Here's the idea I came up with.

I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?

The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).

Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.

We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.

All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.

We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!

I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!

.vimrc Goodies: Literal Lambda

2011-11-15T06:20:00.000-08:00

I recently took to programming in racket after starting to take a class from Jay McCarthy (twitter: @jeapostrophe). Racket is a scheme-based language constructed specifically with industrial use in mind, which means it is based on some pretty solid theory while also posessing, like perl and php, a package management system (PLaneT), a JIT compiler, and other goodies that make it a great language to use in the real world.

This language, along with perl (given that 'use lambda' is invoked), allows the programmer to insert an acutal unicode lambda instead of the keyword 'lambda'. DrRacket, racket's native IDE, allows you to insert this character by pressing 'CTRL+\' . After looking at this page and others, I found I could do this in vim, too.

I put the following lines in my .vimrc file (this same entry worked in my _vimrc file, for the windows version, as well):

if has("multi_byte")
if &termencoding == ""
let &termencoding = &encoding
endif
set encoding=utf-8
setglobal fileencoding=utf-8
"setglobal bomb
set fileencodings=ucs-bom,utf-8,latin1
endif

map! ^\ ^Qu03bb

I inserted the special characters '^\' (CTRL-\) and ^Q (CTRL-Q) by using the normal vim way: in insert mode, type CTRL-V, then whatever control character you need to. For example, I inserted '^\' by typing CTRL-V, CTRL-\. For CTRL-Q, it was trickier. CTRL-Q is usually a specially bound command, so in order to insert it I had to use its octal number ordinal: CTRL-V, 017, were the keys I typed to insert that character.

Now whenever I'm editing a file, I type CTRL-\ and out pops a bonefied lambda!

Best Combo for Facebook, Twitter, and Chat

2011-04-03T10:58:00.000-07:00

As cool as TweetDeck is, have you ever looked at its privacy policy? yeck. many other similiar applications have similiar disclaimers in their privacy policies or ads all over the place. For windows users, there is a solution.

For chat: Pidgin. Being open source, their's no ads and you're not selling your soul to use it. It works well, and with virtually any protocol (facebook, google, AIM, ...)

For Twitter/Facebook/Digg/RSS/Etc. feeds: MahTweets. It is open source, using Microsoft's new Open Source license. Its interface is clean, it is customizable, and it is a CLIENT. it is not something you need to open your browser to use.

I've been looking for a pair of applications like this for a while. I hope others find this useful.

Fuzzy Logic III: Proof Construction

2011-04-03T10:24:00.000-07:00

For those burning with questions on how to actually write a fuzzy logic proof. Even though the law of contradiction doesn't generally hold falor fuzzy logic, the normal rules of fuzzy logic do, with some extended functionality to deal with uncertainty.

I will write about some of the basic rules of natural deduction here. from there, It should be readily seen how the rest of the rules follow.

Before I move forward, it should be noted that last time, we worked with two different systems of logic: minimization (a & b = min(a,b)) and additive (a & b = max(0, x + y - 1) ) with negation being the operation (1-a) and with DeMorgan's Law adopted as an axiom.

Since the things I am about to write about apply to all fuzzy logics, I shall refer to the function which evaluates the certainty of a disjunction based on the certainties of the disjuncts as d(x,y). Therefore, for minimization logic, d(x,y) = max(x,y) (see previous post for more details). The same goes for the function which evaluates the certainty of a conjunct of, say, x and y based on the certainties of x and y themselves. Such a function (which evaluates the certainty of a conjunct) is here written as c(x,y).

Writing Convention

In this document, I will format my proofs as follows:

assertion

certainty

justification

So therefore, with fuzzy logic proofs we deal with three columns.

As an example:

1. P     50%     Premise

2. Q     80%     Premise

3. R     30%     Premise

Conjunction (Combination)

In Fuzzy Logic, Conjunction (P , Q |= P & Q) works quite the same as conventional logic, with the extension that the attached conjunct is simply the same as c(x,y) for the logic with which we are dealing.

Example (taken from the example under "Writing Convention":)

1. P 50% Premise

2. Q 70% Premise

3. P&Q 50% 1,2, Conjunction (using minimization logic)

===

3. p&Q 20% 1,2, Conjunction (using additive logic)

Disjunction (Addition)

The same goes for dysjunction as for conjunction, namely, given p and q, p | q can be attached with the certainty given by d(p,q). P|Q above would therefore take on the values 70% and 100%, respectively.

When adding any old proposition, say p, one which we are not given the certainty value of, we write , if the proposition to which one attaches p has a certainty of 30%, for example.

Modus Ponens

As I said in my last post, we are not guarunteed the law of contradiction. In conventional logi c, it is sufficient to use Contradiction along with Conditional Exchange () and Conjunction to derive Modus Ponens. This is not the case in fuzzy logic; however, we can use the definition of d(x,y) and c(x,y) to make some significant inferences. In this example I will use additive logic, but it should easily be seen how to generalise this approach to any fuzzy logic.

We have:

1. P 43% Premise
2. P -> Q 83% Premise

And so we want to derive Q. we plug P's certainty value in for the formula we use for computing the certainty of disjunction:

d((1-p),q) = .83
d((1-.43),q) = .83

We now substitute the particulars of d(x,y). In our case, this is min(1,x+y):

min(1,1-.43+q) = .83
min(1,.57+q) = .83

It should be clear now that since .83 is less than 1, we know that min(1,.57+q) = .57+q. And so

.57+q = .83
q = .26 .

We can now attach Q to our proof above with certainty 26% under additive logic.

What if P -> Q's value is 1 in this case? We find Q's certainty to be the least certainty that would give 1, adding 'greater than or equal to' next to it:

1. P       83%    Premise
2. P -> Q 100%   Premise
3. Q 83%    min(1,.27+q) = 1 :. smallest q = .83 .

That's how it works: we use the formulas for d(x,y) and what we know about the certainty of the conditional and the antecedent, we can derive the certainty of the consequent.

Conditional Proof

How do we create conditionals? Easy. Simply assume p to some certainty, derive q to some certainty, and then infer p -> q and assign a certainty value of d(1-p,q).

For example, under minimisation logic:

1. P 37%      Assumption
   .
   .
   .
17. Q 75%
19. P -> Q      75%

Contradiction

Although the law of contradiction does not apply in general, it applies at the "end points". In other words, if one can derive p with 100% certainty, and also ~q to 100% certainty, its conjuction will (by definition) have 100% certainty, and one can obtain 0% certainty (100% certainty of the negation) and use this and conditional proof to prove something via reductio ad absurdum.

Conclusion

This work was not intended as a comprehensive treatise on fuzzy logic inference rules, but hopefully I have provided in it a good feel for how it works. Enjoy!

Fuzzy Logic Proofs II: Systems of Logic

2011-03-21T10:40:00.000-07:00

In this post I will discuss how fuzzy logic works as opposed to conventional logic. This will lay groundwork for our discussion of fuzzy logic proofs later. Remember, the motivation for looking at such kinds of proofs is that it provides us with a means of dealing with uncertainty. Perhaps there are other motivations, but I will not mention them here.

I assume basic knowledge of first order logic (and, or, not, only if, ...) and pretty much nothing else. Don't worry, I won't get all academic on you. We'll save that for papers and articles.

Now there's a lot of theory and academic mumbo jumbo surrounding fuzzy logic, but practically speaking anyone can do it. A "fuzzy logic system" basically describes how to deal with "a & b (a AND b)", "a | b (a OR b)", and "~a (NOT a)" when we are, say, only 80% certain a is true and 50% certain b is true. There are two common ways of doing so that I will discuss here.

Defining the last operation mentioned above is the easiest. no matter what kind of logic we use, "~a", the logical complement of a, is always going to be "1-a". This makes sense if look at conventional logic, taking 1 to be "True" and 0 to be "False":

Fuzzy Logic: Conservative Flavor

The first is the most common. For "a & b", where a=.5 (50% certain) and b=.8 (80% certain) it says this: "Well, we know that a is 50% true, and b is more than 50% true, so we are at least 50% certain that the whole statement 'a & b' is true." This conservative attitude contributes to its popularity, and the fact that we take the smallest certainty value to be the value of the whole statement gives it a name: minimization fuzzy logic. So the certainty of the expression "a & b" is the smallest of the two between a and b. You may note that this works for conventional logic:

as for "a | b", we use DeMorgan's Law to define the meaning of disjunction. As "a | b" is equivalent to "~(~a & ~b)", we can just use subtraction and "min" to find out our OR operation. It turns out that the certainty of the statement "a | b" turns out to be the greatest value between a and b. This matches our conservative intuition: "We know a 50% true and b is 80% true, so 'a | b' must be at least 80% true." This is again confirmed by using our conventional "absolute truth" model:

Furthermore, with this (and many other) systems of fuzzy logic, the conventional laws of association, commutation, and transititivity still apply, as well as our faithful friend, DeMorgan's Laws.

Although not generally true of fuzzy logic (though totally true in conventional logic), minimization logic follows the law of idempotence; in other words,

Fuzzy Logic: Liberal Flavor

No pun intended, by the way, in the naming of these flavors. They're both important for our purposes, and the usefulness and limits of each will be demonstrated.

All the cool stuff except idempotence (association, commutation, transitivity, etc.) apply to this logic as well, including the fact that this kind of logic works with conventional logic (it works using only the values 0 and 1).

The next flavor of logic is actually defined, not by its conjunction operation (AND), but by its disjunction (OR). For example, let's say that we know x is 40% true and y is 30%. To figure out how to assign a certainty value to the phrase 'x | y', we simply add their certainties together; therefore, 'x | y' has a certainty value of 70%.

Wait! what if y was 70% certain? then 'x | y' would be 110% certain!?!?

Nah. We'll just say that if the certainty of x and y sum to more than 1 (or just barely made it to one), the couple has "made the cut" and we say that their combined certainties are more than enough to make us certain that 'x | y' is absolutely true. therefore, If the certainty of x and y are 40% and 80%, 'x | y' is still 1. That's why this logic system is referred to as bounded addition. We see that this flavor of logic is quite liberal - It takes the certainty of BOTH values into the value of the whole.

Using DeMorgan's Laws, we use NOT and OR to find AND. Conjuction (AND) here has the same kind of "make the cut" attitude: "If x and y's certainties sum to more than one, it's significant. Otherwise, we really can't say much about the certainty of 'x & y' as a statement." In other words: take the certainties of x and y, subtract 1, and you have the value of 'x & y'. Again the question arises, "What if x and y are at 0%?" The answer is in the same spirit as last time. if x+y-1 is less than 0, we'll just interpret that as we are so uncertain of x and y that we have more than enough reason simply to assign the certainty of truth for 'x & y' to be false.

This is also called Łukasiewicz (Loo-KAH-she-vich) logic, after the polish philosopher who first invented fuzzy logic. Yes, ladies and gentlemen - additive logic was the first fuzzy logic out there, invented near the turn of the 20th century.

This logic is cool over other logics because unlike most other logics, Łukasiewicz logic obeys contradiction and excluded middle laws:
"a & ~a"=0%, "a | ~a"=100%.

What? MOST fuzzy logic doesn't obey contradiction? How can people use minimization logic without it? How can MODUS PONENS even work without it?

Oh, but it can. I'll show you how next time. (I said in my first post that I'd save that stuff for my third post, not my second, but I think I'll just jump to the good stuff.)

Fuzzy Logical Proofs

2011-03-18T12:33:00.000-07:00

Many decent EE Professors will tell you that Fuzzy Logic is used quite a bit in fuzzy control. For those of you who don't know what that is, congratulations; you're a member of normal society. We will not dwell on that here. Instead, we will focus these Fuzzy Logic energies into logical proofs.

For those logicians out there familiar with normal two-column proofs, such as fitch-style natural deduction proofs or similiar, you will find this somewhat familiar. The difference between fuzzy proofs and conventional proofs is that fuzzy proofs provides us a mechanism to deal with uncertainty.

In conventional First Order Logic, we may for any given statement assign a truth value out of the set of two truth values, True and False. In Fuzzy Logic, there is a "spectrum of truth" wherein a statement can be "20% True" and "80% False". Another (more intuitionistic) interpretation of such a value in terms of using it to form a proof is that we are 20% certain that value A is true. Thus fuzzy proofs allow us to use premises with varying degrees of certainty, and in a chosen interpretation allow us to prove results, perhaps even with higher degrees of certainty than our premises. (Side note: those of you familiar with Zadeh's work may cringe at this, but I will explain what I mean when we get there.)

This post starts a series of blog posts which I will publish on the subject of Fuzzy Proofs as I understand them. Please feel free to make comments and give criticisms for my arguments.

In the first post we will define what "fuzzy logic" herein means, and explore the possibilities of the different logical systems at our disposal, and why we may or may not choose them for our proof or to solve a specific problem. Feedback will be requested here. This is a domain which I am trying to understand better even now.

In the second post we will define what an "interpretation" is, or in other words, we will define how to translate our mathy proof back into english so that it may be used to make decisions, as all useful proofs must ultimately provide use for this end.

In the last post, we will walk through a sample fuzzy logic proof. I will comment on its usefulness, its form, and its weaknesses.

From what I can understand, this field has only been explored by few scholars, most deeming it of little use. But I find it relevant here to examine G. H. Hardy, who said "I have never done anything useful," thinking number theory to be an unimportant part of mathematics. Without him, RSA would not be where it is today. (re-quoted from Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, p. 41.)