Prolog Enigma Machine FINALE

It has arrived!

The plugboard turned out to be a pretty easy addition, so I went ahead and cleaned up the code and submitted it to Github.  One version is completely condensened and lacks comments for your convenience. Feel free to fork me, adding new models or visualizations.

Prolog Enigma Machine Week 3: Finishing Touches

Prolog says Yes.

As you may have noticed on my twitter, my M3 Enigma Machine is really coming together! This is the product of a lot of refining of the primary enigma predicate, which consists of all of transitions from rotor to rotor. While this model is static, I feel that this code could easily be adapted to fit the different rotors. While you're at it, you should also make me a GUI like the amazing one I used for reference. (:

In terms of completeness though, I'm currently ready for the presentation, but I still need to add the plugboard. The good news is, that compared to the rotors, this is an easy task... especially considering I already wrote the predicate! It takes in the original alphabet, a list of pairs, and returns an exchanged alphabet, like this:

alphabet(A),

plugGen(A,[[a,c],[b,f]]).

Would yield

A=[a,b,c,d,e,f]

O=[c,f,a,d,e,b]

 

As it turns out, the professor is giving us another week to work on this so I'm going to take it easy, and just get that plugboard implemented that day. For now enjoy pics of success IO that you can replicate yourself in any other emulator!
 

 

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!

Spring Break Project: Enigma machine

You may remember that a while back, I went on an indefinite hiatus due to the pressures of balancing classwork, projects and professional stuff. In light of that trying time, I've convinced myself that I should attempt to pair my projects with my classwork where it's applicable in order to stay afloat. That being said, my next project in Programming Languages will be in Prolog. I've only seen a few samples of Prolog code in action, it seems to be driven largely by logic. Of course everyone says this, but I always thought every programming language was driven by logic! Anyways, the kind of logic Prolog operates on seems to be more like Syllogism in Philosophy. For example:

• All men are mortal
• Socrates is a man
• Therefore Socrates is mortal.

 After a quick google search, I can see that this is also represented in Prolog, which the following:

• All dogs are canines
• All canines are mammals

?- deduction(all(dogs, canines), all(canines, mammals), C).
 
{C = some(mammals, dogs)}
{C = all(dogs, mammals)}
{C = some(dogs, mammals)}

• Therefore: Some mammals are dogs, all dogs are mammals, and some dogs are mammals.

Nice.  So the next is, what do I think I'm going to do in this language? I was thinking about making an Enigma Machine in Prolog. Honestly, I'd rather write a program that generates Engima Machines (for an alphabet of any size, with any number of customized rotors, etc...) BUT, I don't want to get too ambitious. At the end of the day I'd rather be a guy who does more than he says. However, in light of my recent passion for Scheme/Racket, I think I might save the generator for that language. We'll see how it goes. I think the outline will look much like this:

• Create a simple Enigma machine for 3 letters, then 4 (three rotors, odd and even reflector plates) in Racket.
  
• Create an Enigma machine for all 26 letters of the alphabet in Racket. Then in Prolog.
  
• Then, if time permits, work on an Enigma generator in Racket.

This way my assignment is covered, and I can also hone my functional programming skills some more. I'll be sure to update my github as I make progress.