Automation automation automation

Lately the word "automation" has been pounding in my head, left and right. It came first in an enlightening conversation about what makes an enthusiastic Computer Science major. One of the key tenets that many agreed on was "a general interest in automation", which was funny, because, before now, I'd never considered my interest to be about automation... Sure there's robots, and AI, and OOP concepts-- but I've never thought of it as automation, even in my theory course, where I can't say a sentence doesn't contain the word "automata" in some form or another (make a Regex statement for that, why don't you!).

The wound opened further when reading Turing's defense of the ACE project, when Womersley brought proposed the project. One of the questions regarding the project's difference from other machines of that time was "What if the machine was given a series thought to converge, but actually diverged?". Without going into too much detail, Turing replied that it was the controller's responsibility to create a protocol to follow if this were the case. He added, somewhat sarcastically, that he hoped that the operator would be familiar enough with series to understand that this may occur.

He went on to say that the big draw of this machine was its automation, in that the role of the "human" computer could finally be significantly reduced, if not removed altogether, as the machines at the time still required a significant amount of human interaction through testing, verification, the like. It was thought that ACE would require only a few of the higher scientific staff to handle it, and allow the National Physical Laboratory to do away with the rest of the lower "human" computer staff. That's right, the replacement of almost an entire department through the massive reduction of man-hours, all made possible with automation.

I faced a similar issue today. After a bit of a "false alarm" in terms of correct Enigma machine outputs, I went to begin adding manual ring settings, when I found that not all of my inputs were working (...wait for it). I was a bit devastated. After some mucking about, I picked up my pen, and resolved that I would write down what all of the intended outputs should be, and compare them to outputs as they changed. However, before I put the pen to paper, I realized there was a better way. I decided to make my own testing suite in prolog, building an "equals" predicate, and a predicate that evaluated the equality of each item in a list, outputting 1's if they were correct with the inputs, and 0's if they were not. I also displayed the initial alphabet, my enigma results, as well as the correct enigma results.

some boo-boos... but why?

This allowed to drastically reduce the amount of "eyeballing" needed to just stepping through the troubled letters to see exactly what was wrong... An ironic scenario, because, as it turns out, I had written down my B reflector incorrectly! What are the odds! I fixed it, and finally got back all ones. :)

Highlighted reflector plate, corrected outputs.

The experience allowed me to learn something very important about automation:
It comes down to the fact that, a little time spent in automation can save you days of man hours, whereas you are doomed to repeat long hours "eyeballing"-- time spent that can also be in error. Reduce the eyeballing to a minimum and let the machinery do the rest for you! If there's five minutes reviewing large data sets, that adds up to an hour after only twelve runs.

Week 2: Putting together a basic M3 Enigma Machine in Prolog

Using what little built in features GNU Prolog has, by the beginning of this week I was able to compile all that I need to begin work on the actual encryption process. Here's a small list of some of the predicates I implemented. I'm not sitting in front of my programming pc at the moment so these may not all be 100% accurate.

• len(List,Length), returns the length of the list.
• indexFromChar(List,Char,Index), returns the index of a char in a list.
• CharFromIndex(List,Char,Index), returns the Char of a index in a list.
• turn(List,NList), "turns" a list (Tail+Head).
• turnN(List,Times,NList), turns the list as many times as you'd like.
• sswap(List,Char1,Char2,NList), replaces the first instance of Char1 with Char2.
• dswap(List,Char1,Char2,NList), replaces both first instances of Char1 and Char2.
• plugboard(Alphabet, Lol, Plugboard), generates a plugboard from pairs in Lol.
• transition(List1,List2,I,O), finds the index of I in List2, returns the Char as O. 

I'm sure most Prolog vets would scoff at my work, but I particularly proud of dswap and sswap, which both saw use in the plugboard function. I've seen in a Tower of Hanoi demonstration by my mate Kyle Godbey that Prolog has a (relatively) small stack (because it does like a million things!), so my concentration became to reduce as many calls to the accumulative dswap as possible. I accomplished this by considering the fact that I'll working with lists that contain one of each character-- rearrangements of the alphabet. I made the predicate follow suite by having it "abandon ship" so to speak once it's swapped two chars to reduce calls to the same function. Even more fun is that dswap knows to call an sswap with the proper parameters in order to complete the remaining swap.

With all of these helpful predicates I've been carving my way through actually constructing the Enigma machine. I'm trying to keep versatility in mind as I code, but at the same time I'm expected to have this done at the end of three weeks, so I'm trying to follow the model of the M3 Enigma Machine, which is common in many simulations. What I've been doing in order to build my first basic model is constantly referring to these two sites: A great visualization and an in-depth look into how the pieces and parts work. A lot of the diagrams were lifted Dartmouth's awesome and detailed simulator, but this page is helpful with taking you through baby steps. Funny enough, this guide to yet another emulator has been helpful in explaining the hefty German vocabulary for the parts as well as how actual messages should look.  

As far as my current implementation, I'm as far as returning from the reflector plate. The goal is to get all the way home this week, and then next week to incorporate lists, and then incorporate the multi-rotor stepping (the whole Royal Flags Wave Kings Above business). 

Useful Tips From My First Week Of Prolog:

1. Understanding how Prolog works is paradigm. Unlike other procedural languages, Prolog is seeking to set things equal, or unify them. This a much more intelligent behavior that characterizes it as a “fifth-generation language”. The philosophy of the fifth-generation languages is to attempt to “describe” the problem to Prolog as opposed to just writing it out. Take that with a grain of salt though. It will make sense as you develop more and more advanced programs.
   
2. Prolog is pretty bare bones in that you have to write a lot of basic features yourself, and you also have limited tools at your disposal for debugging. One of the tools you need to take advantage of is the trace function. This allows you incite to the complex control flow of Prolog’s stack. However, do not get too caught up in what it’s trying to do, but instead focus on what is being called, and watch diligently for failures.
   
3. When making accumulator-style predicates, try to include an extra argument, as it will make writing a base case a lot easier. Here’s a simple example of an accumulator-style length predicate, len, that calls on a predicate accLen to accomplish the task:
   
   accLen([_|T],A,L)  :-
   Anew  is  A+1,  
   accLen(T,Anew,L).
   accLen([],A,A).    
   len(List,Length)  :-  accLen(List,0,Length).
   
4. If you have a problem where prolog seems to want to “redo” one of your predicates to find another unification, you can use the symbol ! to denote no redos. This will be most helpful in your base case.
   
5. Prolog has a sort of “not” operator, but it can be hard to find in the documentation or in a google search (unless you sold out to SWI-prolog). By using \+ we signify that the predicate is true if it fails.
   
   For example,
   \+ member(x, List).
   
   Is only true if x is not in the list.

Enigma Machine Week 1: Understanding Prolog, working with lists

(This was last week, but I was too busy to write a report)

So the work has began on my Prolog-based Enigma machine has began! Our programming language rotations in my course are roughly three weeks, so I'm doing my best to ration my time appropriately. Most importantly, I used the opportunity over spring break to get familiar with Prolog as a language, and I'm incredibly interested in its unique philosophy as well as its fascinating history.

You see, Prolog is what is considered a "fifth-generation language", a family of languages built around logic and placing constraints on a pre-programmed knowledge base. This can be an initially difficult concept to understand when comparing programming languages, but upon beginning Prolog, you'll see that the language is centered around the idea of "unification", or attempt to unify, or equate two values. This may seem simple, and even limiting, but it grants the programmer many possibilities and approaches that weren't possible with other languages. Unfortunately this comes at the cost of having to think in a completely new way, which will initially require a lot of your time. You'll find yourself 'creeping back' to your procedural ways, but you must resist the call, learning new techniques to satisfy any conditions you need to meet. While it was frustrating, it was such a brand new experience that I found it very satisfying, like some ethereal challenge set before you that you can only use your own wit to solve. I'm considering keeping this language around as a mental workout and for more logic-driven applications.

Prolog has an interesting history as well, being, in my opinion, brought into a world that was not yet ready for it in the 1980's. This was the time when computer technology was really beginning to explode, and we began to get really ambitious. Artificial Intelligence started becoming a mainstream source of fiction, and robot partners to help us fight crime seemed like the future reality, not unlike flying cars in the fifties. That being the situation, many started pumping all sorts of cash into technologies like Prolog. In particular, there was a fascinating 10 year long endeavor in Japan to build a powerful computer to take the throne from the west, known as Fifth Generation. It had a budget of over 400 million dollars and was constructed almost exclusively in Prolog. Sadly, the project was largely considered a failure, other than the fact that it helped foster a generation of Japanese computer scientists. The archives are still available, though the English translation leaves much to be desired.

While the future of Prolog is uncertain, I feel that the computational climate of today is much more hospitable to the Prolog philosophy than the 1980's. We live in an era where Artificial Intelligence courses are readily available, and staples of AI like neural networks are becoming more engrained in our curriculums and hobbies. I can't speak for everyone, but I would enjoy seeing the practical side of Prolog in the context of AI, and see where it could go with today's technology.

While this writing wasn't too helpful for approaching Prolog, I'll include my tips for the course, as well as insight into the predicates and rules I've developed. I apologize ahead of time for my misuse of Prolog terms!

Finishing up with Monty Hall

I've managed to break down my extensive Monty Hall algorithm to just twenty lines of code (though, in Racket, that concept is abstract...), one struct and five functions. It also runs incredibly faster, processing 100,000,000 entries in a little bit less than time than it took the original to process 100,000. This was all possible through some heavy reductions, followed by a clever leap of faith.

As I was building this second implementation, I sought to reduce the 'Gameshow' to just being a list of six-- the first three representing the player/host's choice, and then the second three representing the doors. This would make it all one structure. This would vastly improve the time it would take to generate the sample set-- or at least I thought. As I started working on the host-reveal function for the second time, I simply could not find a smooth way to claw through every possible case-- this is due to the fact they're we're altering the player/host's choice list, while cycling through the door list. This involves several arguments, because you need to maintain the original door list, and be prepared to return the altered player choice list at point-- meaning you'll need to append to the end the original player choice (after you sub in the added -1). This is all quite dynamic for something iterating through a pair of lists, so I became a bit skeptical that this was the best way handle it... worse yet, was the fact that these would all need to be placed into a list of 'revealed gameshows' and then evaluated. Yikes.

So then, the idea became to have simultaneous creation and evaluation. It seemed like a sort of lofty goal, but then after some thought I came to an interesting conclusion about the Monty Hall Problem, which helped my perception in implementation and may help yours in understanding how it comes out to 1/3 odds.

The Take Home

I remember that list-ref returns a given item in the list, according to an index. This is something you almost never do with a random variable, but this time it worked just the way I wanted it to. If you substitute in 1-3 into a list of doors, it represents player's choice. So, if the value returned is a 1, this means the player correctly chose the car, if not, then they did not choose the car.

It seems like common sense, but it illuminates one of the important principles of thinking through the Monty Hall problem: You're going to win (...either by staying or switching). You see, as I work through this model, I completely disregard the host's choice.  After all, the final Monty Hall proposition is that you either chose the car, and would win by staying, or you didn't choose the car, and would win by switching. And from the outset, with three possible choices, you're more likely from the outset to have chosen a goat. All that has changed here is that host has revealed one of the possible choices, and made it a binary affair, reiterating that you win either by staying or by switching.

Now with this assumption all we need to operate is a random door list, and a boolean evaluation of whether our random choice into the list brings back a car. If it does, that's one for staying. If it doesn't, that's one for switching.

And with that, we just need a number of times to perform this operation. No structs or lists involved. Sure, I used a 'collection' struct, but it can also be done with two ints.

If you interested for the differences line by line, check out this site, which compares two files and returns the differences. As always, the code is always available in my Github.

At this point, I think I can call this one closed. I imagine there's a few more tweaks that could be made, but this function as it is would be great for any project using this data. :)