Esoteric Programming Languages

OK, so I learned to code in a Tandy TRS-80's BASIC around 1986 (my father's a natural born geek), then QBASIC, then Pascal, then PBASIC for Parallax's BASIC Stamp II, then Java, and then I met a real programming language: C, then C++, MIPS, s08, and so on.

 

The Tandy TRS-80, the first computer I remember coding for.

Esoteric Programming Languages are PLs made for the amusement of programmers, often intentionally difficult/fun/creepy to read.


Brainfuck
I was completely ignorant of esoteric programming languages until 2002, when I ran into a piece of code that looked something like this:

[-]>[-]++++++++[<++++++++>-]<+++++>[-]>[-]+++++++[<+++++++>-]<---<.>.<--.>.

I decided to read more about it and learned it was brainfuck code. Brainfuck is a programming language designed by Urban Müller with the objective of making the smallest compiler ever. It looks unintelligible and I guess that's part of the joke. But it's not useless: it's actually Turing Complete.

So how do I code in brainfuck?
The programmer's model is a huge byte memory and a pointer. You may modify the pointer but you can never be sure what address it's pointing to because you don't have access to it. This is just what a Turing Machine looks like. That's why it's Turing complete: because it's a Turing Tarpit.
There are only 8 instructions in brainfuck, each represented by a character.
Here they are:


Cmd     Meaning                                  C equivalent
 >  Increment pointer                              p++; 
 <  Decrement pointer                              p--; 
 +  Increment pointed data                         *p++; 
 -  Decrement pointed data                         *p--; 
 [  Jump after matching ']' if pointed data is 0   while(*p){ 
 ]  Go to matching '['                             } 
 ,  Get pointed byte from The input                *p=getchar(); 
 .  Send pointed byte to The output                putchar(*p);

Any other character is ignored and considered a comment (so comments must avoid the valid characters).

Ook!
But it didn't stop there. I then learned there were tons of esoteric programming languages, such as Ook!, which is a parody of brainfuck (If that's possible). Ook! is actually the same as brainfuck, because it's isomorphic to it.
Ook! is supposed to be easily understood by orangutans :) Oh, and there's no need for comments because it's supposed to be clear enough for orangutans. Any character outside the proper Ook! language is a syntax error!
Ook! syntax consists of combinations of the symbols Ook. Ook! and Ook? in pairs, separated by single spaces, which match brainfuck characters. For example, "Ook. Ook?" means '>' and "Ook! Ook?" means '['.

      Quoting Wikipedia:
      "According to its designer, David Morgan-Mar, Ook! was meant to be easy for orangutans
      to read, and to prevent any mention of the word "monkey"".

      Quoting Dave Morgan's Ook! description:
      "Um, that's it. That's the whole language. What do you expect for something usable by
      orang-utans?"

Ok, so this is how you say "hi" in Ook!:
    Ook. Ook? Ook! Ook? Ook! Ook! Ook? Ook! Ook. Ook? Ook! Ook? Ook! Ook! Ook? Ook! Ook? Ook. 
    Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. 
    Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. 
    Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook. 
    Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook! Ook.
Get it? Of course not, you're not an orang-utan.

Visual Brainfuck
So I decided to start working with Borland C++ Builder in 2003 and I decided to make a brainfuck interpreter. I made Visual BF. Here's a screenshot of Visual Brainfuck running the Sierpinski triangle classic BF program.

Visual Brainfuck. Here's a dedicated post on it.

The "About" dialog had special thanks to my then boss for allowing me to be unproductive while learning.

Visual brainfuck had 2 extra tools:

• A brainfuck text encoder, which generates a brainfuck program that prints the entered text.
• An Ook! <-> brainfuck translator.

Whitespace
One esoteric PL that caught my attention is Whitespace. It uses only whitespace characters: tab, new line and space.

Befunge
Befunge is a programming language that modifies the direction of code execution, by means of four arrow symbols (^,v,<, >). All instructions are stack operations with access to the source code for variables, constants and self-modification.

Here's a "Hello Wolrd" in Befunge:

    >25*"!dlrow ,olleH":v
                     v:,_@
                     >  ^

Here's the explanation of this code.

LOLCODE
And guess what! Lolcat fans are encouraged to code in LOLCODE, a lolcat-syntax-based esoteric programming language. Its keywords are typical words found in lolcat pictures.

Here's a "Hai World" in LOLCODE:

    HAI
    CAN HAS STDIO?
    VISIBLE "HAI WORLD!"
    KTHXBYE

And here's a program that prints a count (called "COUNT!!1"):

    HAI
    CAN HAS STDIO?
    I HAS A VAR
    IM IN YR LOOP
        UP VAR!!1
        VISIBLE VAR
        IZ VAR BIGGER THAN 10? KTHXBYE
    IM OUTTA YR LOOP
    KTHXBYE

So here's a LOLCODE compiler for Parrot.

One-Instruction Set Computer
There's a lot of crazy stuff out there, and there's a computer architecture called a One Instruction Set Computer. Believe it or not, there are actual Turing complete OISCs.

R
This is a programming language intended for Pirates!!!
Hello World in R:

    R!
    Ahoy, mayteys!
    Aye, polly is a parrot that tells the crew what the Captain is thinkin'. Gar.
    Ahoy, polly says, "Hello World!"
    Dead men tell no tales.

Here's the explanation of this code. It's worth reading, trust me.


Chef
Writing this post I learned about Chef, another contribution of Dave Morgan. Chef is a programming language intented to make code look like an actual cooking recipe.

Here's a Hello World in Chef:

     Hello World Souffle.
 
     Ingredients.
     72 g haricot beans
     101 eggs
     108 g lard
     111 cups oil
     32 zucchinis
     119 ml water
     114 g red salmon
     100 g dijon mustard
     33 potatoes
     
     Method.
     Put potatoes into the mixing bowl.
     Put dijon mustard into the mixing bowl.
     Put lard into the mixing bowl.
     Put red salmon into the mixing bowl.
     Put oil into the mixing bowl.
     Put water into the mixing bowl.
     Put zucchinis into the mixing bowl.
     Put oil into the mixing bowl.
     Put lard into the mixing bowl.
     Put lard into the mixing bowl.
     Put eggs into the mixing bowl.
     Put haricot beans into the mixing bowl.
     Liquefy contents of the mixing bowl.
     Pour contents of the mixing bowl into the baking dish.
     
     Serves 1.

So the mixing bowl is the stack and the baking dish is the standard output. Oh, and variables are ingredients and the quantities indicated are their values. n this example, note that their initials suggest the character they contain (e.g.: oil='o', water='w').

I could go on and on, really...
There's a LOT of esoteric programming languages out there (more than 600). Here are some of their names:

• 1337,
• Argh!, Aargh! (these are not pirate programming languages, they look a lot like Befunge), 
• Zombie (by Dave Morgan, for necromancers), 
• AAAAAAAAAAAAAA!!!! (I'm not getting into that), 
• Brainfuck++ ("useful" brainfuck with file system and network support)
• Brainfuck-- (downgrade of brainfuck, with only 5 instructions)
• Whenever (the order of tasks is random).

Go to the Esoteric Programming Language Wiki for more fun!

Flux Capacitors might help prevent pipeline hazards

First off, this is not serious at all. Okay, you've been warned.

Ever wondered about alternative approaches to overcome Pipeline Hazards?

Well, looking at this xkcd schematic I started to wonder about the Flux Capacitor's potential in an actual circuit. I'll tell you what made sense in my head, but first, let me explain the basics. If you already know the basics, you may skip to "Flux Capacitors in Computers".

About Pipelining
It's a way of speeding up code execution by dividing it into several stages that perform sub-tasks simultaneously by means of dedicated hardware for each stage. Four consecutive stages are typically used: Fetching the instruction from memory, Decoding it (identifying the operation), Executing the instruction, and Writing Back the result. This ultimately speeds execution up (ideally in a rate equal to the number of stages in the pipeline). Read more.

Pipelined execution. Numbers shown in the graph are the instructions at the left.

About The Hazards
Hazards are problems related to the use of a pipeline in an instruction execution unit. Two Hazards are considered here:

• Data Hazards: It happens when an instruction needs data that's produced by another instruction that previously entered the pipeline, but hasn't finished yet. For example let's say instruction i writes data into register A, and instruction i+1 (the next one) uses register A as an operand to calculate something else. What happens when instruction i+1 is in the Execute stage and i is in the Write Back stage? The value of register A used by i+1 as an operand will be the original value prior to the execution of instruction i because it's not done yet. This is called a Read After Write (RAW) or true data dependency. This is a problem because the data used by instruction i+1 is outdated. 

Data Hazard between Execute and WriteBack (may happen between other stages)

• Control Hazards: This concerns branches, calls, interrupts, exceptions, resets, etc. When sequential execution must change due to a branch or whenever the next instruction to fetch is not the next stored instruction, the Fetch stage must be aware of the address of the next instruction (branch target, interrupt vector, etc). Furthermore, most branches are conditional, and it's not until the Execute stage that the processor knows whether or not the branch should be taken. This is a problem because when the processor becomes aware of a branch, all of the instructions previously loaded into the pipeline might have to be aborted (execution may have to jump elsewhere). This abort depends on the condition of the branch, which will be known after Decode. If the branch must be taken, the pipeline must be flushed or bubbled (instructions previously entered replaced by NOPs [no operations]). If not, no problem. Flushing/bubbling the pipeline is a problem because it's a waste of time, and the pipeline is supposed to speed things up. 
  
  Control Hazard with bubble

There are many approaches to overcome these hazards, mainly divided in two kinds of strategies: Static and Dynamic. Static approaches are performed by the compiler, conditioning the resulting code (rearranging instructions, loop unrolling, and so on). Dynamic approaches are performed by additional hardware (storing data in temporary registers or keeping a record of previous hazards for prediction).

Read more about pipeline hazards.

About the Flux Capacitor
"The flux capacitor is what makes time travel possible", Doc. Brown.

The Flux capacitor is the Y-shaped device inside the DeLorean Time Machine in the Back to the Future films.
Read more.

Flux Capacitors in Computers
So! Let's consider the unlikely event of an actual Flux Capacitor being invented, tested, manufactured, and even miniaturized to a VLSI level. Not happening, bear with me.

My intention is to get useful data from the pipeline and send it back in time in order to correct the hazards.

In the video above, Doc Brown said that the Flux Capacitor from the DeLorean requires 1.21GW to operate. It was capable of reaching ±30 years of time travel for anything inside the whole DeLorean. So, taken to a very small size, hopefully a MEMS Flux Capacitor requiring a couple of watts to achieve a time travel of no more than ±1 second for a cage of a cubic micron wouldn't be so much to ask (would it?).
Even if the proof of concept for time travel at this level is only able to achieve microseconds for cubic nanometers, this would be good enough because going some clock cycles back in time is all that's needed.

As described in the films, the time machine is only capable of taking objects back (or forth) in time, when they are somehow attached to the flux capacitor inside a stainless steel body. So our little (tiny) time machine would be a stainless steel cage containing a miniaturized Flux Capacitor, a time-traveling register, some status and control registers and a charge pump to initiate time travel by providing the required power for the Flux Capacitor to start "Fluxing" (lol).

Time Traveling Register Module (TTRM) Block Diagram

The amount of time to go back must be written to the TTRMSC register (SC=Status and Control). Some clock cycles must be allowed for the charge pump to operate. The amount of clock cycles required is irrelevant as the register will leave this timeline anyway. The future of this timeline is of no interest anymore.

So, Data Hazards won't be a problem anymore with something like the following arrangement, which is some kind of actual Register Forwarding:

Register LookAhead (RLA) Block Diagram

Thus, when a RAW data dependency is detected, the "GO!" signal stores the present WriteBack data into the Time Traveling Register, and activates the Charge Pump to start Time Travel a few (previously configured) clock cycles back in time. In the past, the "Incoming" signal replaces one operand of the ALU with the future data, eliminating the dependency setbacks.


On the other hand, Control Hazards could be taken care of nicely with a similar technique:

Branch LookAhead (BLA) Block Diagram

If a branch should be taken, the "GO!" signal loads the target address into the TTRM. In the past, the "Incoming" signal sets the Program Counter to the Target Address so the correct instruction fetch is made.

After the target address is sent back in time, actually loading the target to the program counter in this timeline wouldn't be completely necessary, as time travel would take care of that, correcting the events in the universe of interest (the one in the past). Watch a cool video about time travel here.

This brings up some questions that must have lots of discussion already: What happens to all the split universes generated by each time travel? Is there such thing as Universe Leaking? Is a free(Universe) function reasonable?

Considering all the split universes generated by this technique, it's important to point out that it will only be always useful for one and only one universe. All other universes will experience the hazards. (?) Oh well. 


That's all. I hope I'm not losing my mind.

Make It Challenge at FTF 2011

I got an invitation to attend the Freescale Technology Forum 2011 at San Antonio, as an educator from Galileo University in Guatemala.
Freescale has lots of cool stuff at FTF every year, such as technical sessions, workshops and very nice receptions with demos at their technology lab.

One of the activities I never miss at FTF is their on-site Design Challenge. I got the first place on the "Can Your Badge Do This?" Design Challenge at FTF2008, and later the third place on a second online version of the same challenge.


The Challenge
So FTF2011's design challenge was called the "Make It" Challenge, and it had two tracks: The Tower System Track and the Robot Track. I decided to go for the Robot approach.

We got this very cool FSLBOT kit, which is a biped robot with gooddies such as 12 touch sensor contacts (placed in the shape of a cartoon head), a freaky face made of LEDs on the touch-sensing head, 8 servo-ready connectors, an Xtrinsic sensor port, etc. Plus, Freescale provided lots of stuff to help us get our designs up and running: A dedicated lab with soldering irons and tools, geek snacks, a HUGE box full of batteries, and two very important elements: A large supply of VEX parts, and an Xtrinsic sensor kit with an accelerometer and a magnetometer.

FSLBOT

The challenge was simple: Make a cool robot to impress the judges with the provided tools and any extra hardware you have in Two Days. The only requirement was to use the FSLBOT's controller, the Tower System Mechatronics Board.

The judges were:   

1. Joe Grand (host), president of Grand Idea Studio, Inc. He was one of the inventors on Discovery Channel's "Prototype This" show. He's a Hacker-RockStar: he's Kingpin from the l0pht!!!!!!!!! :OOOOOO w00t!!!!
2. Heather Knight, Social Robotocist and founder of Marilyn Monrobot Labs. She was one of the kenote speakers at FTF2011, a true geek (meant as a compliment). She was part of the team of engineers behind the "This too shall pass" video, by OK Go.
3. Anton Olsen, Master Geek at Innovation First, Inc. ( VEX Robotics ), Contributor at GeekDad.com, and Blogger at AntonOlsen.com

We had two programming language choices: C and RobotSee. Working in C ultimately meant an autonomous, powerful, but time-consuming robot for me (given the short deadline), while RobotSee meant a PC-dependent, basic, but fast-development robot. That's why I chose RobotSee (My heart still belongs to C).

The RobotSee IDE was made by Eric Gregori for the FSLBOT's controller, the Tower System Mechatronics Board. RobotSee looks a lot like a mix of BASIC and C. I found it very easy to learn and definitely suitable for my situation.

My Entry
I didn't want to make a biped as the suggested FSLBOT, because I couldn't come up with something unique for such robot (I imagined lots of dancing robots at the judging). I wanted to make a wheeled rover so much, but when I got to grab VEX parts from the stack, all the DC motors were gone! Then I started to panic, but considering alternatives for DC motor locomotion, I decided to think outside the box and use something I once told my students to do, with no clue on the implementation.

My general idea was to make a Servo-Only rover. So I came up with this robot that paddles his way fordward using four non-driven wheels, a rubber paddle and two servos: one for paddling and one for lifting the paddle so it can move back.

My paddling robot

So how does it turn left or right? I came up with a cool suspension system that most likely already has a name and evolution. Anyway, my robot has two servos acting together to achieve two states:

1. The servos lift most of the structure at one end, causing the four non-driven wheels to make contact with the floor, supporting the robot. By the way, did I mention this is a carpet robot? It had to be, since I didn't get rubber wheels at the giveaway either, so I used actual shameless gears as wheels.
2. The servos lift the wheels at their other end. This causes a horizontal stand  (made from a large gear) to make contact with the floor (carpet). This gear is very special because it's driven by a fifth servo. This allows the robot to turn exactly the angle it's supposed to (provided you have a rubber band around it for friction).

Take a look at this suspension system:

The ServoBot's Suspension System

At the last minute I decided to make the demo using the touch-sensing face. So I made the robot take a step forward when you touch his eyes (yes, his eyes), turn left when you touch his left ear, and turn right when you touch his right ear. I did this in order to use as much hardware as possible. Judges like that.

Since I expected the robot to look like a paddling boatman, I intended to name it Charon.
The robot's movement ended up looking quite funny. After lots of coffee, it looked to me like the robot was proud to manage without DC motors. That's why I called it DC-Motor-Less, Yet Proud ServoBot.

So here's a video of my experience at the Make It Challenge:

I had a lot of fun participating in this challenge and I encourage everyone to put yourselves to the test on similar events. Chances are, you'll have fun too.

Although I didn't expect to win anything, I finally got the second prize. I know the judges liked my project despite being useless, because it was geeky and for most of it's features I had to wing it. Here's my robot with my prizes back home :)

My Robot and Prizes (Note the juicy debit card with the name "Especially for you")

Difficulties
I did have a lot of setbacks while making this robot such as availability of the right parts, time, etc (I had to attend several sessions and workshops during the conference, plus I had to eat and sleep!). My wife was very supportive, though :)

I also received tough news about 2 hours before judging: RobotSee wasn't yet ready to drive more than 4 servos, although the board has 8 servo connectors. I asked Eric Gregori if there was an easy way of driving more servos through RobotSee, but the answer was no. I intended to quit using one of the servos, the one that lifts the paddle, and came up with a mechanical one-way rubber wheel at the end of the paddle.
Once the panic was gone, a much simpler solution came to me: The two servos that lift the robot can be driven by the same signal, seen as one big logical servo in my code. So I got to use both servos. The attempt for a one-way wheel mechanism is still visible in the paddle. I left this rubber wheel static in the end.

The slippery gears I misused to support the robot were also a lot of trouble. That's why I limited my robot to the realm of carpets. I used a rubber band that came with a Freescale T-Shirt to wrap around the turning gear for friction. Take a look:

Rubber band and one-way wheel 

I must admit that during the thinking part of the challenge, I was facing the biggest obstacle of all: Myself. Since I don't have as much experience in mechanics as I do in electronics, I felt very challenged and didn't believe in myself, but then I said "Shame on you, Robotics Teacher!", and then I got to work.

If you're interested in the code, you can download it from here. The mechanics might get tricky :/ Contact me if you're interested.