Musings of a Software Designer.

[Kranar]

I figured I needed an place online to write out my myriad of thoughts regarding computer science and the art of software design in general. May be of little or no relevance to anyone here and may downright be boring at times, and that's a-okay with me, but what better place to write out and gather my thoughts than the forums I help administrate.

[Kranar]

If there's one thing that I admire most about the major scientific and mathematical discoveries of the 20th century, it's how humble they are. Compare the last century to say... the Scientific Revolution. Mathematicians and scientists had opened up an entire treasure chest of physical and mathematic laws, and they were certainly convinced that these laws were absolute in their truth. According to the likes of Isaac Newton, Karl Gauss and the other great minds of the classical era, the universe could be entirely described by adhering to a few simple laws and rules. Their acheivements can not be understated and the relevance of their work is just as influential today as it was 100s of years ago. What is remarkable about the 20th century is just how quickly the methods of the times past were abandoned to make way for a new era of uncertainty.

Take mathematics for instance. There was little doubt in the minds of mathematicians in the 19th century that all there was to know about mathematics would be unified under one single infallible system. Of course many to this day still do regard mathematics as being a rigid, indisputible field. The drive to capture math as a whole and then dissect it had reached its peak with mathematicians such as Russell and Whitehead publishing the beast that is Principia Mathematica. It was only shortly after that their dream has crumbled and Kurt Godel, one of the greatest logicians to ever live, illustrated the impossibility of fully comprehending mathematics or logic itself by any finite means.

It was a century that saw Albert Einstein, a man who changed how it is we think of space and time and a man so determined to unify the laws that governed nature, watch as his ideal of a grand unified theory fall before the mysterious and peculiar quantum mechanics.

And finally, it was a century where people convinced that computers could at least in theory be able to mechanically solve any problem, come to terms with the fact that computers are also restricted in their capabilities.

Whereas the classical era was about what human beings could know and come to understand about the universe... the modern era focused on what science and mathematics are unable to teach us about the universe. That math is subject to just as much uncertainty, fuzziness, and imprecision as art. That science is full of incredibly strange and even contradictory natural phenomenon. That computation can never compare itself to the ingenuity held by our imaginations.

Where does that leave us today? Perhaps the greatest marvel to come out of the last 100 years, and also the one least known, is Information Theory. What is so special about Information Theory is how in such a subtle way, it combines all the ideas of computation, science, and mathematics. It is my firm belief that the greatest advancements that await us in this century will be a direct result of the application of Information Theory.

Information theory, spawned by Claude Shannon in 1948, was at the time nothing more than an attempt to transmit signals efficiently over a physical medium, such as a telephone cable. But what makes it so great is that for the first time in human history, someone was able to take such an abstract and formless concept, and quantify it. Information theory is a way to measure, in precise terms, just how much information content there exists in a pattern of symbols.

It's remarkable... for example, one can take a newspaper, a novel, or heck, even take this very blog, and actually quantify into a single number just how much information it contains. Furthermore, by measuring how much information is contained in a pattern, and then measuring how many symbols are being used in a pattern, one can determine how much redundancy there is in the pattern.

The implications of this have been well understood for practical purposes. For example, anytime you listen to an MP3 or watch a movie on your computer, information theory was right at the core of making sure that the sound file or video file contained only as many symbols (binary digits) as is needed to communicate the content of the sounds or images. It's only recently, however, that information theory has begun to play a major role in mathematics, and theoretical science.

Now that scientists and mathematicians have matured to acknowledging that there are limits to what we can know, information theory has played an influential role in quantifying whether the solution to a problem is knowable or not. If one seeks to determine if the solution to a problem can be solved more efficiently, one can simply ask "Is the amount of information contained in this problem less than the amount of information contained in this solution to the problem."

Since information is at the core of every single problem or idea, any single problem or idea can be rephrased so as to analyze its information content. It's because of this, that information theory will prove to be very powerful tool this century. Now that we have a better grasp of what's knowable and what is not, what is needed is a way to understand the very root of knowledge itself and to study it in its most purest of forms: raw information.

[Sean of the Thread]

http://www.clicksmilies.com/s0105/ernaehrung/food-smiley-007.gif

[Kranar]

Software design is a pretty strange thing when you think of it. You know what it is you want the computer to do, you can describe it to yourself and to your friends, but it becomes such a difficult and sometimes frustrating task to properly tell that same thing to a computer. Granted some of the difficulty is a result of the vagueries of normal conversation, but that's mostly a minor problem.

The biggest problem with software design today is the lack of an appropriate means of communication between a human being and a computer. The most popular languages available to us today are C++, Java, and Python. These languages are all just minor variations of one another, and as such they all suffer from the same fundamental flaw, they lack a level of expressiveness and flexibility that human beings desire when they talk to one another.

Think of writing an essay... does it ever occur to you while writing one how restrictive the English language is? Do you ever write an essay, stop, and think to yourself, "Oh darn, I can't quite explain this concept elegantly in English. If only I could write it in Russian, or Japanese, or Arabic I would be able to clearly say what it is I want."

Assuming you were an incredibly fluent speaker of every human language, it's highly unlikely you would find that some things are easier to express in one language while being incredibly difficult in another. Yet, software designers face this problem all the time, trying to find just the right language they need to get the computer to do the task they want it to.
The root of problem is largely historical. During the 50s, the sole task of a computer was to take a mathematical formula, and calculate a precise and correct answer to it. Essentially a computer was just a really big calculator that engineers could use to find solutions to their highly complicated equations. This was a very complicated and infinitely frustrating task as the only way to communicate to a computer back then was by punching holes into a card, with the pattern of holes determining what equation to calculate. To simplify this task, the very first high-level programming language was developed, FORTRAN (Formula Translator). Boy did it make life easier... for the first time in computing history, someone could input to the computer an equation like:

x^2 + 5x + 6 = 0

And the computer would almost instantaneously solve it. Life was good for the engineers, they had a great tool at their disposal to do all the mechanical work for them while they focused on the design.

Surely, while one can appreciate the power FORTRAN has for solving equations, one can only imagine how difficult it would be to express the game of Chess, Gemstone IV, or even The World of Warcraft as a series of equations. And so for the next 50 years, all software designers have done with respect to the design of computer languages was to add new constructs, new features to the language. Basically taking FORTAN, a special purpose language, and adding a new feature to it that makes it easier to do some other specific task, and adding a new feature later on, and so on so forth...
This, in my opinion, has proven to be a flawed approach in the pursuit of a general purpose computer language. C++, Java, and Python are not general purpose languages, they are just examples of languages that have many purposes that are of practical importance today. This has held back the potential that computers can have since before the use of a computer can expand to new, uncharted territory, these languages have to be updated with new features to accomodate the new problems that are faced. Of course it would be a miracle if human beings could come up with a genuinely general purpose language that would allow humans to easily communicate with a computer after only 50 years, but we will be far from such an ideal language if we continue down the same path we've been on.

The best path we have towards the ideal language is one that was also discovered 50 years ago, but unfortunately was almost all but abandoned shortly after. That path begins with a language called Lisp, and its other dialect, Scheme. Perhaps I will go into detail as to why these two languages lay the true foundation for an ideal language, but that will have to wait for another day.

[Celephais]

I was reading a Microsoft blog that had a very similar theme to it, I really wish I could find it now to reference but I believed it stemmed off a discussion on the new LINQ technology for the next VS release (at the time it was for VB9 but it has been extended, and more elegantly so, to C#).

found it! http://blogs.msdn.com/mattwar/archive/2005/10/09/479008.aspx

It's about how languages will eventually look like the way Yoda talks. Some other intresting links off that blog too.

Anyway, they're definatly moving towards less machine languages. With VS2k5 it's perfectly possible for someone with very minimal programming skills to create powerful apps using just the designer.

[Kranar]

I'm guilty myself of following down the road of the traditional C/C++/Java route.

A couple of years ago I wrote a language called UltraTech which I used after my increasing frustration with Java. Java is a language whose philosophy is that if a feature can in anyway introduce a risk, eliminate it. I always felt like I was confined to a very tiny space when programming in Java, as if Java was telling me how I should be programming whereas I feel I should be the one telling the computer how to program.

Some people argue that it's a good thing for a language to restrict the programmer because it reduces the possibility of bugs... and while I could go into a long debate about it, suffice it to say, I am not one of those people.

So anyhow, I wrote the thing, and I was very satisfied with it, but then C# comes along and implements all the features UltraTech has and a whole boatload of new ones, which discouraged me from using it or improving it any further and so I just went back to programming in C++.

C# is a great improvement over Java no doubt, but ultimately it's just Java/C++ with features X, Y, Z added to it.

I'm currently working on a new language called Maylee which I intend to be a drastically new approach to programming than the popular languages that exist today. Basically I feel that the guys who came up with Lisp/Scheme had it right from the getgo and if those two languages had been the focus of programming over the past 50 years instead of FORTRAN, we would be much further ahead as to what a computer is capable of doing.

My goal with Maylee is to take what I find makes Lisp/Scheme so powerful and modernize the syntax to something more familiar to todays programmers. The idea is to basically remove every single feature that comes packaged with C++, C# so on so forth... and instead provide a facility which allows programmers to define their own features.

No if statement, no while loop, no for loop or any of that... instead one really powerful expressive system from which a programmer can define their own if statement, their own looping mechanism, any feature they want.

[Kranar]

I am a great admirer of Douglas Hofstadter, author of “Godel, Escher, Bach” and indeed that book, along with “The Mind’s I” are among two of my favorites. These are both books that have been some of the most influential and most inspiring in my overall understanding of nature itself, and yet I was never able to agree with Hofstadter’s premise on the nature of consciousness.

You see, Hofstadter is a functionalist; in simple terms, that means that he believes that the nature of consciousness is strictly the act of carrying out an algorithm regardless of the physical makeup of the action. That’s a fairly technical description and so the following illustration should help to better clarify what it is a functionalist believes.

As you likely know, your brain is made up of trillions of atoms; furthermore, the atoms that make up your brain today are not the exact same atoms that made up your brain even 2 minutes ago, a very small number of them will be replaced or swapped out by other identical atoms. Most people, however, would agree that they are the same “consciousness” now as they were 2 minutes ago, despite the fact that their physical composition has changed. Indeed, over the course of no more than 7 years, ones entire brain will consist of entirely different atoms, despite the fact that one would nevertheless argue that they are the same consciousness. Thus consciousness, it is argued, has nothing to do with physical composition.

The atoms of a human brain and of the nervous system in general are organized into cells called neurons, and these are the most fundamental cells responsible for transmitting information around your body. Neurons transmit information such as pain, vision, hearing and all other senses to your brain; furthermore neurons transmit information from one part of your brain to another.


Now assume that a Bob was selected for a long term experiment where the first phase of this experiment was to just replace a single neuron in his brain with a very tiny mechanical unit, like a silicon chip. The unit would act in a manner indistinguishable from that of the original the neuron, but the unit was instead created inside of a laboratory by a team of scientists rather than from naturally occurring biological means. The functionalist would argue that in the same way atoms in the brain get replaced by new indistinguishable atoms all the time without any change of consciousness occurring, no change of consciousness would occur at all by replacing a biological neuron with a mechanical neuron. That is, so long as the mechanical neuron can carry out its action in the same manner that the biological neuron can, no change in consciousness occurs.

Alright, so let’s say that after 7 years, all of Bob’s biological neurons had somehow been replaced by mechanical neurons. The argument is that even though Bob is now composed entirely of silicon chips, he will nevertheless be conscious, and that in fact his consciousness is the same Bob today as it was 7 years ago.

The absurdity of functionalism occurs when lifting the restriction, as we have imposed on ourselves, of limiting consciousness to the confines of a human brain. As is pointed out in the famous thought experiment by Ned Block, neurons are incredibly simple cells to understand, there is nothing magical or mysterious about an individual neuron. The description of how any individual neuron behaves and interacts can be described entirely in less than a single page. Since it is believed that the human brain has about 1 billion neurons, and the population of China is roughly equal to 1 billion, let’s assume that instead of replacing all of Bob’s neurons with silicon replicas, we just create a copy of Bob’s neurons one by one, by writing out the description of each individual neuron on a sheet of paper, and giving that sheet of paper to a single Chinese inhabitant. After 7 years, every citizen of China will have a piece of paper describing some very simple rules and instructions that correspond exactly to a single neuron in Bob’s brain.

Is China now conscious? Is China now Bob? What is the difference between replacing all of Bob’s neurons with silicon chips, and replacing all of Bob’s neurons (or in our case duplicating them) with the citizens of China?
Visualizing this reminds me of the Matrix Revolution’s when Neo confronts Deus Ex Machina. The consciousness behind Deus Ex Machina is the all powerful Architect, and to manifest himself physically outside of the Matrix he simply brings together an entire swarm of Sentinel’s to form a face, where each Sentinel acts as a tiny cell of Machina’s being. The concept works elegantly for the movie, but in reality there seems to be something rather dogmatic about the assertion that since all of China is carrying out the actions performed by Bob’s brain, that somehow China is a conscious being.


I do not mean to trivialize functionalism, on the contrary it is certainly difficult to argue that if one replaces biological neurons with something artificial, that the artificial being will not act and behave as the original. The argument against functionalism is that this artificial being would lack the comprehension of its actions, in much the same manner that a chess playing program lacks any sort of understanding of what it’s doing even though it might end up defeating a human Grandmaster chess player. Functionalism can not account for what I believe is the most crucial aspect of consciousness; that is the self-awareness component. Deep Blue, the IBM computer mainframe that defeated International Grandmaster Gary Kasparov at chess, while perhaps very similar in behavior and in action to Gary Kasparov at chess, lacks the self-awareness of its own actions.

Self-awareness is, in fact, what put an end to the ideal that the foundation of mathematics could be put on a solid footing. As Kurt Godel showed, whenever a system even so much as hints at the possibility of a self-referential theorem, that system is subject to either inconsistencies, a property most dreaded by mathematicians, or incompleteness, a property which denies any sense of complete satisfaction to mathematicians. And yet we, as conscious beings, allow for and even ourselves make self-referential statements constantly without breaking down. The fact that we can accommodate this should suggest that our consciousness is performing something that can not be replicated functionally. It is thus the breakdown that occurs when self-reference is introduced into a mathematical or computational system that I feel makes both of these fields unsuited to understanding consciousness. We may, and in fact I firmly believe will, manage to construct artificial beings that can very accurately mimic the actions of actual biological entities, yet I maintain that actually getting these entities to become conscious and actually aware of their own existence to be a feat wholly impossible using mathematical or computational methods.
http://photos1.blogger.com/blogger/1955/2530/400/matrix6.0.jpg (http://photos1.blogger.com/blogger/1955/2530/1600/matrix6.0.jpg)

[Kranar]

Amongst all computer scientists who take a philosophical approach to the subject, there comes a time when a personal visit the mystical realm known as the Mandelbrot set is in order. The hope here is simply to reveal that mathematics and computer science is far from being about the dry and technical aspects that people often confuse it for, and instead show that the technical aspect is merely a means to an end, the end being a better understanding and appreciation for what it is we can know and understand about the world we live in.

The Mandelbrot set is an example of a structure that can be defined mathematically, but whose complexity and nature is such that it can not be understood using any sort of computational means. It is a prime example of how there exist incredibly strange and mysterious forms in mathematics for which we can never fully comprehend or explain using algorithms, computers, or any other kind of computation, and yet we can define it in such simple and elementary terms.

Now the notion that there exists truths that can be not explained mathematically has been understood since the 1930s, when Kurt Godel published his famous Incompleteness Theorem, and then later on Alan Turing showed how computers are also limited in what they can accomplish.

Both of those proofs were symbolic, involving rigorous equations and theorems and axioms. The Mandelbrot set is beautiful because it's an actual colourful picture. It expresses the notion in an artistic and aesthetically pleasing manner that the universe contains secrets for which we have no means of understanding using math or science.

So what is this... Mandelbrot set exactly? Some have described it as a beetle, others have said it resembles a tropical island, and yes, one individual has described it to me as an oversized ass. Don't be too intimidated by the following mathematical definition, but if you find you are, simply ignore this next section and explore the Mandelbrot set yourself in what follows.

Pick a number, any number... let's call it c. Now consider the following sequence of equations:

c
c^2 + c
(c^2 + c)^2 + c
((c^2 + c)^2 + c^2)^2 + c
(((c^2 + c)^2 + c^2)^2 + c)^2 + c

Notice the pattern? You start with the simple equation c, and then you derive the next equation in the sequence by taking the previous one, squaring it, and adding c to it.

So as an example, if we let c = 1, then it's pretty clear that this sequence of equations diverges, that is, if you keep calculating this sequence of equations, it keeps getting bigger and bigger without settling on any single number. If on the other hand, you let c = 0, you notice that this equation converges, infact it, it converges to 0.

The Mandelbrot set is the collection of all values of c such that the sequence of equations converges. So the number 0 is a member of the set, whereas the number 1 is not. It is such a simple definition and yet it has a structure so complex that it escapes any attempt at being understood.

The best that we can do is approximate how it looks like, and in fact we can understand in full how the interior of the structure looks like, the problem comes when we try to explore the very edges of the structure, the corners. The closer you zoom in on any corner, the more and more complex the structure becomes.

But now that you've made it this far, it's best to have a look at what the Mandelbrot set "looks" like:

http://forum.gsplayers.com/kranar/mandel1.jpg


That's a look at the set as a whole, without zooming in on any of it, a beetle? An island? An... ass? You decide for yourself. As you can see, it's made up of some bulbs, and then some "antennas" which reach away from the bulbs. It's these antennas where a lot of the complexity of the set occurs, and infact if you zoom in on one of these antennas you get the following:

http://forum.gsplayers.com/kranar/mandel2.jpg


That strange looking beetle reappears and this time with an even greater complexity! The set is made up of little copies of itself, and zooming in on it even more one gets:

http://forum.gsplayers.com/kranar/mandel3.jpg


This is some sort of incredible spiral, and strangely enough the spiral is actually made up of infinitely many copies of the so called "beetle." Where does this spiral lead to? What is at the centre of this spiral?

Unfortunately, this is just one mystery that will forever remain a secret. The closer you zoom in on the spiral, the more complicated the pattern gets, and you realize that you're no where closer to the centre of the spiral than you were just a couple of zooms ago.

The Mandelbrot set simply refuses to allow itself to be fully comprehended. It is an example of what exists outside the boundary of human comprehension and how this outside world is vastly rich and infinitely beautiful.

I have included as part of this entry a program I quickly wrote up that allows you to explore this set for yourself. Left click zooms in, right click zooms out. There are many such programs that exist on the internet for exploring this beautiful structure, enjoy!

[Aithzar]

Had a professor introduce me to this a few years ago, still amazes me.

Aith/Russell

[Stanley Burrell]

Kranar's fifth post in this thread.

I have a lurking suspicion that you wouldn't be too huge a fan of Lüger's automaton.

Is this your thesis?

[Kranar]

My posts are mostly rambles and curiosities that I find pertain to software engineering and computer science.

My experience when talking about computers to various people is that they think computers are about knowing technical mumbo jumbo and getting caught up in these details. Even worse is when people start programming this way or learn how to program from this perspective. Quite likely my next ramble will be on that subject, so that will have to wait. Anyhow, knowing technical stuff is decent I suppose, and sometimes important, but honestly the beauty behind this is the art that's hidden deep and beyond the technicalities. The Mandelbrot set is one instance of this I find interesting and accessible to the general public.

Anyone can understand the construction of the Mandelbrot set, if you can't understand it from my post, then it's a result of my failure to do a good job of explaining it as opposed to your failure to understand it. And yet, to understand its construction is to understand some of the hidden beauty in math.

Too many people see math and computers as technical and shy away from it. Indeed if math and computers were just about the technicalities, then I'd be right there with them in regarding them as merely superficial subject matters with next to no virtuous qualities.

That's really all I hope anyone gets out of anything I say.

[Kranar]

So I wanted to take some time to describe a project of my own. This entry will be of little to no interest except to those who either want to learn about programming or want to see an example of a language far different from what is currently considered popular. The project is the Maylee Programming Platform.

Thankfully Microsoft has expressed its interest in my language and my job this summer with them will be working on Maylee, a dream come true for me. The status of the project is a finished compiler, I am now working on an assembler, a runtime environment, and finally an IDE for the language. My hope is to have many of these components finished by the end of the summer and available on www.maylee.org (http://www.maylee.org).

To get a good understanding of Maylee, it might be best to unlearn everything you know about programming and start fresh. Maylee is unlike the existing popular languages, it is a language, that while inspired by Lisp and Scheme, is designed from the very ground up and meant to provide a wholly new and unique way of approaching and thinking about software design.

Maylee code is made up of statements, where every single statement is itself made up of statements and thus takes the form:

(statement_1 statement_2 ... statement_N)

In this sense, Maylee code is all recursive with some built in statements which provide a basis.

The philosophy behind Maylee is to have as few built in statements as possible, in fact, the only built in statements should be ones that are absolutely neccessary to express an idea in an elegant manner. Taking a look at some of these built in statements we have:

Variable declarations
---------------------
Variables are a way to keep track of data, you specify the type of data you wish to keep track of, and then provide a name to reference that data later on. A variable is simply a placeholder for information you wish to make use of or manipulate.

Examples of variable declarations are as follows:



// declares an integer variable named x, with no initial value
(int x)

// declares a boolean variable named y, with an initial value of true
(bool y true)



Functions
---------
Functions in Maylee are a special kind of variable. Whereas typical variables refer to values and information, a function in Maylee refers to an action that you wish to perform. A function takes in information, performs some action, and then returns a value upon completion.

Here is an example of a function type:

(int x int y) -> int

The above refers to a type of function that takes in two integers, named x and y and then returns an integer upon completion. An example of such a function would be addition and we can declare it in Maylee as follows:



// declares the function add, which takes two ints and returns an int
((int x int y) -> int add)


Let's assume the existence of the following function:

((int l) -> void printLine)

This defines a function which takes an int parameter l, but since it -> void, it does not return anything. This function will be used to print a single number out to the monitor.

Compositions
------------
Now that we have functions, we need a way to be able to invoke that function. The role of a composition is to do just that. A composition takes as its parameters first a function, and then information to provide to the function. Using add as an example it would look as follows:



// add the numbers 5 and 6 together
(add 5 6)

// add 6 and 7, then add 8 and 9, then add the result of both of them together
(add (add 6 7) (add 8 9))


Begin
-----
Begin statements are a way to combine multiple statements together into one block. A begin always evaluates to the very last statement executed.
Example:



(begin
(int x 5)
(int y 10)
(add x y))


In the above case, we create a variable x, with value 5, and variable y with value 10, then add the two variables together. Since the last statement of the begin is (add x y), the begin statement evaluates to it as well.

Example:



(printLine (begin
(int x 1)
(int y 2)
(add x y)))

Output:
3


If statement
------------
If statements are not actually built into Maylee, but for the sake of simplicity assume the existence of the following statement, which we will learn how to construct in just a moment. An if statement is a series of conditions and consequences, the consequences get evaluated if the condition is true, as an example:



(if
(x < 10)
(printLine "x is less than 10")
(x < 20)
(printLine "x is less than 20")
else
(printLine "x is greater than or equal to 20"))


Syntax
------
This is where the real power and elegence of Maylee begins to take off. The previous statements, with the exception of begin, are all basic things you'd find in any other language. What syntax allows you to do is create your own statements.

One such statement commonly used in other languages is a loop. You would like to repeat some code over and over again while some condition is true. In Maylee, you can create such a loop using syntax as follows:



(syntax (while) // we have to declare "while" to be a keyword

// define the pattern to use for our while loop
( (while (bool condition) body)

// define what to rewrite the above pattern into
(if
condition
(begin
body
(while condition body)))))


Notice how the definition is recursive! Maylee embraces recursive definitions and the compiler has many sophisticated techniques for recognizing recursive forms, analyzing them and then speeding them up.

Now that we have introduced into Maylee the ability to loop and we can use it as follows:



(int i 0)
(while (i < 4)
(begin
(printLine i)
(i = (i + 1))))

Output:
0
1
2
3


We can build upon our while loop, introducing a counter loop:



(syntax (for = to) // a bunch of keywords our pattern will use

// the pattern
((for (identifier i) = (int lower) to (int upper) body)

// the rewrite rule
(begin
(int i lower)
(while (i <= upper)
(begin
body
(i = (i + 1)))))


Now we can rewrite the previous example as follows:



(for i = 0 to 3
(printLine i))

Output:
0
1
2
3


This just touches the surface of the types of structures one can create in Maylee. The whole point is that if you notice you're doing something repeatedly while programming, then consider analyzing the structure and pattern of your code, and abstract it away as a syntactic form. This way you can make use of the idea without having to type so much code, which can lead to errors and frustrations. Object-oriented programming, template meta-programming, aspect-oriented programming, you name it, all of these can be defined in an elegent manner using Maylee syntactic forms. So instead of having to wait for the next version of C# or Java or God knows what other language to implement a feature you wish existed, you can just create and implement that feature yourself in a way that is most comfortable for you to use.

Suggestions and questions are always welcome!

[peam]

/swings from tree
//picks lice from packmate's hair
///gets eaten by crocodile, while trying to get a drink of water

[HarmNone]

This looks fascinating, Kranar. It's really cool that Microsoft has taken an interest in it, as well. Something like this might well keep people like myself from going into a self-induced coma at the very thought of programming anything! ;)

[Latrinsorm]

(syntax (for = to) // a bunch of keywords our pattern will use

// the pattern
((for (identifier i) = (int lower) to (int upper) body)

How does the thing know to recognize the (for = to) part but not the numbers one would have in there? By which I mean, how does it get (for = to) from (for x = 2 to 3)? Does it really check for the pattern?

[Kranar]

Yep, the program does pattern matching.

You basically provide a pattern for Maylee to match, and what Maylee should rewrite that pattern into. Then every single time you use that pattern, Maylee will recognize it and rewrite it until it becomes one of the built in patterns.

So the built in statement for adding two numbers is:

(add x y)

But most people probably prefer writing it like x + y. So you just tell Maylee...



(syntax (+)

// the pattern
(((int left) + (int right))

// the rewrite rule
(add left right)))


Now every time Maylee comes across something like:

(x + y)

It rewrites it into:

(add x y)

The two become identical.

The patterns I provided as examples are just very simple examples of commonly used things. There are very extensive pattern matching rules you can define to simplify what would otherwise be very cumbersome tasks.

[Kranar]

Heck, you can even write syntax rules to make writing syntax rules easier. Consider the following rule which will make an infix version of an operator.



(syntax (infix)
((infix (identifier symbol) ((int left int right) -> int operation))

(syntax (symbol)
(((int left) symbol (int right))
(operation left right)))))


It's a syntax rule that creates a syntax rule. Now you can do stuff like this:

(infix + add)
(infix - sub)
(infix * mul)
(infix / div)

And with these 4 statements you have infix versions of all your arithemtic operations, so you can do (a / b), or (a * b) or (a - b), or even make up some of your own like:

(infix # somewhackoperation)

(a # b)


Maylee is all about defining patterns that you commonly use when you program, and packaging them into concepts that you can use over and over again in a very easy manner.

[Kranar]

After years of programming, my dream has finally come true. I am now a Microsoft employee. My first day of work as a Software Design Engineer has been great. After the new employee orientation I went to meet my team of developers who were having their weekly meeting at a brewery. I introduced myself and we quickly jumped into discussing software architecture and the state of various projects. All this while enjoying a very large meal at MS's expense. One of the odd curiosities about orientation is that in the MS book, it states that not only is it against policy to take pictures of the interior of any MS building for security purposes, but it is also against policy to take a picture of Bill Gate's parking spot!

The first thing that strikes you about the Microsoft campus is how large and beautiful it is. It's 48 buildings surrounded by trees and full of rich gardens and futuristic building architecture. Where ever you are on campus, you can see people working outdoors in the fresh air on their laptops, or discussing projects in small groups, or even playing soccer, volleyball or frisbee on the large playing field. It's a very vibrant work environment where people are constantly keeping themselves active.

The work environment here is also much different than the traditional 9-5 approach. For one, there is no work schedule, you have a set of tasks and a deadline for them that you and the lead architect agree upon, the rest is up to you. The MS campus is intended to be more of a resource than it is a workplace. You can attend seminars/presentations on new products, go to the MS Research Department and attend very interesting lectures there, try out new gadgets and technology, or be involved in many of the other activities scheduled throughout the day. It's exactly how I pictured a major technology based company should be.

Work was fun as well. I got to my own office and saw a new computer, monitor and a bunch of computer accessories all still in its box sitting on my desk. Microsoft has a culture of using its own products before releasing them to the public, so we all work using Windows Vista, Office 2007, Visual Studio 2008, and also use the upcoming version of Internet Explorer. To familiarize myself with the project I'll be working on, I was asked to fish around for bugs and fix them. When a Microsoft product crashes, there is an option to send an error report of the crash to Microsoft. Much to my surprise, these reports actually DO get sent to Microsoft and get entered into a massive database. I searched for bug reports pertaining to my project and began working on fixing them. As of earlier today I can proudly say I have fixed my first bug for Microsoft. And then of course there was another one I had to fix... and then another one.

I am working with the dynamic languages team. Our job is to extend .NET to make it an appealing platform for dynamic programming languages such as Python, Ruby, and Lisp. Microsoft's first dynamic language to run on this will be Python and that is what I am assigned to work on. Once I've familiarized myself with the codebase, ie. fixed enough bugs, my task will be strictly to focus on language optimizations, basically making sure that programs made in Python run as fast as possible. Once this project is done and is released, the languages team has invited me to give a presentation of my programming language, Maylee. I am rather excited about that and about the overall experience Microsoft has to offer. It's taken a real long time to get here, but definitely well worth the work and wait.

[HarmNone]

That sounds absolutely wonderful, Kranar; not to mention stimulating! I'm really very happy for you. :)

[AnticorRifling]

Kranar that's freaking awesome bro. Hopefully this does well for you. I've got some very important questions which I will now ask.

Are you still lifting weights as we discussed offline?

If I provided math problem to you pertaining to something very important (gear itemization in WoW) would you provide educated feedback from a numbers stand point?

I must have missed this thread before but I read through the entire thing, it was good to have something to pass the time here at work (job II). It's making me reconsider what I'm doing in the work force as I currently lack any form of real passion for what I do (more hardware/troubleshooting/making dumb people feel undumb). Maybe I just need to nut up and join the Police Force, I mull this thought over every three or four months... Rambling, the bastard love child of a second job, forgive me.

[Back]

Well done. Any place that has meetings taking place in a brewery is golden.

[Artha]

Netting a microsoft job isn't an easy accomplishment from what I hear. Grats, man.

[Snapp]

Wow, sounds nice Kranar. Congrats, you earned it.

[Stanley Burrell]

Very nicely done :thumbup:

You sir, have gone quite a long way from Gorilla and Nibbles.

Stanley Burrell.

[Skirmisher]

My goodness.

I guess there is a golden few companies that have that kind of oppotunities Kranar and you made it happen for yourself.

It truly does sound like the kind of environment that lends itself to aiding the creative minds working there.

Congratulations, to you and Microsoft because they are lucky to have you.

[Kranar]

Well, it's official. I got my letter of acceptance to work for Google this summer as a Software Engineer Intern. Knowing that Google gets 1.2 million applications per year and only accepts 2000, I feel kind of special. Now my only worry is being able to get a work-visa for the summer, but I'm hopeful that won't be a problem.

I decided to apply to Google as a spur of the moment kind of thing about 2 months ago when a friend of mine threw out the idea. I rarely ever used a Google product (I'm more of a Yahoo guy), but I heard many good things about Google's work environment, mostly that all Engineers are allowed to spend 20-30% of their work week on personal projects. So, I figured what the hey, I got nothing to lose by trying. About a month later, after I pretty much forgot about the ordeal, I get an e-mail asking me to schedule a 4 hour phone interview (3 interviews each lasting an hour to an hour and a half).

The interviews were very indepth, much more than Microsoft's interviews (and I thought those were pretty intense). I was asked to write several algorithms on the spot that covered areas such as data compression, pattern matching, and search/optimization, as well as general level questions involving how to handle database systems that measure in the terabytes.

A lot of the questions threw me off as they seemed really random, and there was often a feeling of akwardness as I scrambled to write down a solution on my pad of paper. All the while I would be thinking outloud to myself spouting jibberish until I had a coherent enough solution to explain. At the end of the interviews I felt pretty exhausted and just relieved it was all over with.

Well, alas, after a week I get a phone call from a recruiter telling me not only was Google interested in giving me a summer internship offer, but that two of the people I interviewed with actually got into a mini-scuffle over who I would be working with. Yesterday, the official contract came in for me to sign and Fed-Ex back to Google effectively sealing the deal.

All in all I'm actually happy and looking forward to working there this summer. It should be an interesting contrast working for Google as opposed to Microsoft and greatly diversify my work experience. The pay is actually significantly better than Microsoft's and as an added bonus, Google is ranked the best company to work for according to Fortune Magazine, whereas Microsoft is ranked 50th:

http://money.cnn.com/magazines/fortune/bestcompanies/2007

[HarmNone]

I'd read some really good things about Google with regard to their work environment. They're very highly thought of in that regard. It's wonderful that you've got the internship, and it should be a great experience for you! Congratulations! :)

[crazymage]

Nice.

[Back]

Well done. Coincidentally, someone I work with left our company for a gig at Google. You are going to be in good company. Literally and figuratively.

[Skirmisher]

Wow, yes Google has been written about quite a bit just recently as being a top company to work for.

Yet another feather in your cap Kranar. As you said they get inundated with applications and to be chosen speaks volumes.

Congratulations!

[Snapp]

Wow.. congrats Kranar.

[Stanley Burrell]

All your search engines R belong to Kranar.

[Artha]

Well, it's official. I got my letter of acceptance to work for Google this summer as a Software Engineer Intern.
Oh my God.

I've seen the Google hiring videos, I've told friends of mine how awesome it would be to work there.

Keep on living the dream, eh.

[Soulpieced]

I also work for a Forbes top 100 company. There is definitely a big difference from my previous employer. Bottom line though, you have to make your career for yourself, but having an employer that looks out for its employees is a big plus.

[Kranar]

I officially made Maylee an open-source project available on SourceForge and I am now looking at writing some documentation for it.

The thing of course is that I feel Maylee is fundamentally different from most other programming languages like Python/Java/C#, languages that I used to be fond of but have now begun to think of more as babysitters that have emerged as a result of marketing/business factors than engineering/mathematical reasons. My language shares its roots with Lisp/Scheme, two languages that for many political reasons are under used/valued.

My documentation is meant to be both a philosophical examination of programming languages in general as well as a very fundamental introduction to Maylee, period. I am posting this initial draft of an informal introduction to Maylee which I plan to expand upon in the future.

It is long, and it is meant to really be a ground-up and basic/fundamental approach to programming.



Introducing Maylee
------------------
The best way to understand Maylee is to first forget everything you know about programming. This will not only be a difficult task for veteran programmers familiar with the advanced techniques used in languages such as Java or C++, but it could also be difficult for beginning programmers who might have some notions of what programming should be like. My intention is mostly to examine the purpose and role of a language and illustrate how Maylee satisfies this role.
Typically when one thinks about a programming language, one thinks of it as a means of instructing a computer to perform some task. Of course this is definitely one use of a language, however, in understanding Maylee we will do our best to avoid thinking about computers period and only refer to them when neccessary. In actuality, programming languages actually predate the existence of physical computers entirely.

Part I - Primitives
-------------------
One major use of language, period, is to convey knowledge. It's one thing to have some idea in the back of your mind, and it's quite another to explain that idea so that others can understand it. As such, ultimately the goal of Maylee will be to express knowledge as well, in such a way that it is unambiguous, flexible, and simple. As such we look at the primitive pieces of knowledge that can be expressed using Maylee. First we look at the most primitive pieces of knowledge that can be expressed in Maylee:



true
false


Pretty basic and well boring... but it's a starting point. Two simple words for expressing truthhood or falsehood, the type of data this expresses is refered to as 'bool'. Well Maylee also has as primitives other forms of data such as integer numbers (refered to as 'int'): -2, -1, 0, 1 2 etc... And furthermore it has decimal numbers available as primitives such as 1.23, 3.14159, so on so forth, these are refered to as 'double'. While there are some other forms of primitive data, we will focus on these three for now: bool, int, double.

The next type of primitive statement is the ability to associate a value with a name so that the name can be used interchangably with the value. We can do this as follows:



(define x true)
(define y 3.1415)


Now anytime we refer to the name x, we're actually referring to the bool value 'true', and similarly when referring to the name y we're referring to the double value '3.1415'.

Alright, we now have data and can give names to this data... still boring though. In order for this data, and for these names to be of any interesting use, we need ways of creating new data from existing data. To acheive this Maylee also has a series of primitive instructions as follows:



(asm add x y) // gives the sum of x and y
(asm sub x y) // gives the difference of x and y
(asm mul x y) // gives the product of x and y
(asm div x y) // gives the quotient divides x and y
(asm lt x y) // gives 'true' only if x is less than y
(asm lteq x y) // gives 'true' only if x is less than or equal to y
(asm eq x y) // gives 'true' only if x is equal to y
(asm gteq x y) // gives 'true' only if x is greater than or equal to y
(asm gt x y) // gives 'true' only if x is greater than y
(asm not x) // if x is 'true' gives 'false', and vice-versa


Technically there are several other primitive instructions, but these will not be of concern to us yet. Now we're actually getting somewhere though, we have primitive data, we have a way of naming data, and we have operations we can perform on data, so as an example we can now express the following in Maylee:



(define PI 3.1415)
(asm mul PI PI)


This program evaluates to PI squared, yet another simple calculation. For our purposes we will consider only this data, naming capacity and instructions as the primitive elements of our language. These are the building blocks for all that we will express in Maylee, the atoms of the knowledge from which we will compose even more complex knowledge. Thus we will need a means of combining these primitive elements into more complex elements and we will learn just how to do so in the next section.

Part II - Abstraction
---------------------

The second component to Maylee is how to take primitive knowledge and combine it into more complex knowledge. However, in order to keep working in our language maintainable and easy to understand, we need to be able to hide the complexity somehow. This is the idea behind abstraction, it allows us to take some complex structure, and treat it as though it were primitive, not having to worry about its inner workings. An abstraction is typically thought of as a black box, you put some data into the black box, it does its thing magically, and you get out a result.
In Maylee, the most primitive form of abstraction is through the use of lambda expressions. A lambda expression allows us to refer to a process without actually carrying it out, furthermore a lambda expression allows us to generalize a process to many different types of inputs. The syntax of a lambda expression to square a number is as follows:



(lambda (int x) -> int
(asm mul x x))


What this says is, we want to create a black box such that when you put in some int data called x (remeber an int is an integer number), you get out x * x. Remember, we are not actually computing x * x, instead we are describing the process behind computing it. So we can give this process a name as follows:



(define square
(lambda (int x) -> int
(asm mul x x)))


Just as before, we are naming square to be the process behind taking a number and squaring it. If we want to actually make use of the black box, actually use the lambda expression to compute something, we do it as follows:



(square 5)


That would square the number 5, and now we can square PI as we did before by writing the following:



(square PI)


Notice how to make use of this black box, we don't need to know anything about how it works... we just give it a number, it does some magic, and we get out a number. It's as if square was a primitive instruction built into Maylee.
Indeed, we will consider another blackbox which is slightly different from the above, it's as follows:



(if c a b)


This blackbox expects three pieces of data as inputs, a bool c, and two arbitrary values a and b. If c is 'true', then it returns a, and if c is 'false', it returns b.



(if true 5 6) // evaluates to 5
(if false 10 20) // evaluates to 20


Armed with primitive data and the ability to construct these blackboxes we will now look at an actually interesting use of this.

Part III - Putting This Together
--------------------------------
Let's make use of what we know to compute something that would not trivially be computable by a human being, that being square roots. Earlier we took numbers and we squared them, so we will now examine the inverse of that operation, if given a number x, how do we find a number y such that y * y = x?

A classical way of doing this is described in plain English as follows and dates back to the Babylonians:



1) Guess the square root of x.
2) If the guess is good enough, then return the guess.
3) If the guess is not good enough, then take the average of the guess with x / guess.
4) Repeat this until the guess is good enough.


Alright, let's see if we can translate this into Maylee.
Our method requires that we know when our guess is good enough, so we need to describe this process in Maylee. Let's say we want our answer to be within 0.0001 of the true value. One way to test if our guess is good enough is to check if guess * guess - x is within the acceptable precision. If it is then we return it.



(define good-enough?
(lambda (double guess) -> bool
(define precision 0.0001)
(asm lteq (absolute (asm sub (square guess) x)) precision)))


This procedure requires that we define absolute, and we do so as follows:



(define absolute
(lambda (double v) -> double
(if (asm lt v 0) (asm mul -1 v) v)))


This says if v is less than 0, then return (-1 * v), otherwise return v.

Now we implement step 3 in Maylee... this requires us to be able to take an average:



(define average
(lambda (double a double b) -> double
(asm div (asm add a b) 2)))


Simple stuff, the average of a and b is (a + b) / 2. This allows us to implement step 3 as follows:



(define improve-guess
(lambda (double guess) -> double
(average guess (asm div x guess))))


Finally step 4 says to keep repeating this process until we get a result that we are satisfied with:



(define try-guessing
(lambda (double initial) -> double
(if (good-enough? initial) initial (try-guessing (improve-guess initial)))))


All we're doing is starting with a guess, if it's good enough then return it, if it isn't good enough, then we return the result of making an improved guess.

Now we take all of these components together and combine them to create a massive black-box:



(define square-root
(lambda (double x) -> double

(define absolute
(lambda (double v) -> double
(if (asm lt v 0) (asm mul -1 v) v)))

(define good-enough?
(lambda (double guess) -> bool
(define precision 0.0001)
(asm lteq (absolute (asm sub (square guess) x)) precision)))

(define improve-guess
(lambda (double guess) -> double
(average guess (asm div x guess))))

(define try-guessing
(lambda (double initial) -> double
(if (good-enough? initial) initial (try-guessing (improve-guess initial)))))


(try-guessing 1.0)))


Voila, we have our massive black box which is itself made up of black boxes, it starts by guessing the number 1 for the square root of x and continues guessing over and over until it gets an accurate enough result. You put in an number x, and you get the square root of x. You can use this black box as follows:



(define sqrt2 (square-root 2))
(define sqrt3 (square-root 3))
(define sum (asm add sqrt2 sqrt3))


Notice that using the square-root is very simple, even though the process involved in calculating it is much more complex. But because we have the power of abstraction through the use of lambda expressions, we can hide this complexity, and indeed, it is this ability to hide complexity that will make Maylee a powerful language.


Conclusion
----------
As we continue to learn about Maylee, we will learn how to abstract not only actions/processes, as we did with square-root using lambda expressions, but ultimately we will learn a very powerful abstraction which allows us to abstract Maylee itself so that we can extend Maylee in incredibly powerful ways. In fact, we will learn how to extend it in arbitrary ways so that we can use Maylee to describe other languages and make use of those languages as though it was built into Maylee itself. These languages can be simple languages such as arithmetic, allowing us to express equations without the often cumbersome use of (asm mul x y) ..., or other languages such as HTML, SQL-databases, and technically we could even express a language like C.

The power behind a language is three-fold; it must have a set of primitives that really are basic, like Lego blocks, it must have ways of taking these basic blocks and combining them together into complex structures, and finally it must allow you to take these complex structures, and allow you to eliminate the details and complexity behind them so that they can be used as though they were primitives built into the language. So far we have only seen a glimpse of Maylee, but eventually we will dive deeper into the language to expose all three of these concepts to illustrate the profound power a language like Maylee offers to those who are willing to learn it.

[Back]

blah blah blah Maylee open source documentation blah blah blah

If you want a logo, brand treatment, documentation layout pdf and web page for Maylee I’d be happy to take a shot at it.

[Kranar]

Oh I'd definitely love that.

I have something up at www.maylee.org (http://www.maylee.org) but I am totally open to having it redone.

[Back]

Oh I'd definitely love that.

I have something up at www.maylee.org (http://www.maylee.org) but I am totally open to having it redone.

The template you have the site on is already nice and clean. The top banner could use some work though. I’ll PM about it.

One other thing... I was able to access some site editing pages on your site. Might want to look into that.

[Sean of the Thread]

I gotta say so far Maylee looks pretty kick ass.

[Latrinsorm]

it does its thing magicallyIt's about time someone made a magical programming language. I'm gonna lambda myself up some 2d40 lightning bolts.

In seriousness, I don't follow how Maylee is essentially different from (for instance) C++, recognizing that I'm not a huge programming guy. I assume this is in the whole abstracting other languages thing?

[Kranar]

You ought not be a huge programming guy to understand Maylee, in fact, people who are huge programming guys in the popular, traditional sense, will likely have a very hard time understanding Maylee. That's why we have Java/C# and all these babysitter languages that try and hold your hand while programming rather than allow you to think freely.

Alright, let's see something that Maylee can do that can not be done in a language like C++/Java. Let's look at an example inspired from calculus. Calculus is very much a language, it has some funky notation involving limits, integrals, and derivatives, and so what we will do is introduce some calculus into Maylee.

Let's introduce the notion of a limit: Since we are restricted to text, we have to find some textual way of expressing taking a limit:

Let's use notation as follows.



(limit h => L f)


To mean, the limit as h goes to L of some expression f. Keep in mind, if you find some better, more convenient notation for taking a limit, by all means use it instead.



// define syntax for taking a limit
(syntax (limit =>) // we introduce the symbols/words 'limit' and '=>'
// we define a pattern we want Maylee to match
((limit [identifier h] => [double L] [expression f])

// we now describe the process of taking a limit
(begin
(define dx 0.000000001)
(define h (L + dx))
f)))


(syntax ...) is the way that Maylee allows you to abstract itself. Lambda's allow you to only abstract a process, syntax allows you to abstract Maylee! A limit isn't quite a process, it doesn't merely take in a value and produce a value, it's a more sophisticated construct and so we need a more powerful form of abstraction to capture it. What's important is that syntax is the most powerful form of abstraction possible in the sense that anything that can possibly be abstracted can be done using Maylee's (syntax ...) feature. This is why we can describe C++/C#/Java if we really wanted to, we could imbed these languages within Maylee using syntax... but we really should only use it when absolutely neccessary so as to not abuse this powerful feature.

But that's it, we can now do stuff like this:



(limit x => 2 (x * x))


And it will give us 4.

Now as you know, calculus uses limits mostly to take derivatives. So let us now introduce derivatives into our language. A derivative, is a function, which takes as input a function, and returns a new function. As an example:

d x^2 / dx = 2 * x.

So if we give our derivative function the function x^2, we should get out of it a function 2 * x. Recall the derivative of a function f is as follows:

df/dx = (limit h => 0 [f(x + h) - f(x)] / h)

For us, this means we need to construct a blackbox so that when you put into it a blackbox, you get out a blackbox... A blackbox for us, and functions in general, can be represented by lambda expressions. Hah... try doing this in C/C++, passing in a function and getting out a new function... but we will do it in Maylee.

Let's do this...



// define d/dx to be a function that takes as a parameter
// a function f, and returns a function as its result
(define d/dx
(lambda ((double) -> double f) -> (double) -> double

// this is a function within a function which we will return
(lambda (double x) -> double

// definition of a derivative
(limit h => 0 ((f (x + h)) - (f x)) / h))))


Done... Now perhaps the details of how I implemented it don't make sense, or looking at the code it isn't immediately obvious how it works... who cares? It's now a blackbox named d/dx, so you can use it freely without understanding it. Let's use this beast... recall we can define squaring as follows:



(define square
(lambda (double x) -> double
(x * x)))


Now we can take the derivative of this function as follows:



(define d-square (d/dx square))


And we can use it as follows:



(d-square 5)


Which would evaluate to 10. We can take double derivatives like this:



(define d-d-square (d/dx (d/dx square)))
(d-d-square 10)


Now assume someone gave us the sine function from trigonometry... someone constructed a blackbox for computing sine...

Using this blackbox, and using the derivative we just defined... we can define cosine as follows:



(define cos (d/dx sin))
(cos 3.1415)


You get get cosine virtually for free since we have sin and derivatives, you don't need to know anything about how to calculate cosine other than it's the derivative of sine, and you get it. That's power for you... Similarly you can define a computation for taking integrals and then you have all the power of calculus available to you within Maylee.

C/Java/C# all these languages don't let you do this, instead they provide you with a very huge library and massive set of primitives, and they keep bloating the language with more and more features which means more crap you have to memorize and more technicalities you have to keep track of. They don't provide you with powerful forms of abstraction that allow you to extend the language yourself, to create primitives of your own. As such, ultimately you're limited to being able to program only what the people at Sun Microsystems or Microsoft or whatever other company made the language intended for you to program, and nothing more...

Maylee, on the other hand is the opposite, it comes with very few primitives, very small and simple set of building blocks, but it allows you to combine these blocks in anyway you so please. Then when you've come up with something cool and neat, you can abstract away the details of its use so that it's as if it was built into the language from the beginning.

[Latrinsorm]

Ah yes, that is quite impressive. Well done!

[AestheticDeath]

I got lost.. Maybe someday I'll learn this type of stuff.

[Artha]

I've always wondered, Kranar, how one goes about coding a programming language. Do you use something like C to do it, because that seems like it would be dumbly complicated, or do you use something like Assembly? That seems like it would be inordinately limiting.

[Kranar]

I used to wonder the exact same thing... it blew my mind that you actually would write programming languages using a programming language. Still does in some ways...

The first step to writing a programming language is understanding the theory behind formal languages. These topics include automata theory, Turing machines and computability/complexity theory.

Then the second step is code generation, which involves knowledge of stuff like computer organization, assembly language, operating systems, and a lot of technical mumbo jumbo. Reading through Intel's IA/x86 reference manual was a nightmare, but is definitely crucial to creating an efficient language.

Basically you write a program that takes text as input (for Maylee this is done in TokenStream.cpp). Then you interpret this text it using the concepts you learned from language theory (this is done mostly by Statement.cpp), the end result is a syntax-tree, it's a tree data structure which is the logical representation of your language. Then you pass the tree structure to the code generator, and your code generator travels through your tree piece by piece spitting out assembly language code (done in ByteCodeGenerator.cpp).

You can actually see the source code for Maylee, it's open source and the code can be viewed via a web-browser at:


http://maylee.cvs.sourceforge.net/maylee/Maylee/


To give you an idea... there's roughly 250 files worth of source code comprising around 25,000-30,000 lines of code, so it's not a small trivial task. There are many components to the language, there's the compiler itself which is written entirely in C++, this takes in Maylee source code and generates an executable file. Then there's the Maylee runtime, which is coded in a combination of C and assembler. Then there's the testing platform which is in C++, there are libraries for things like input and output and operating system calls, some math functions and other stuff which is written in C.

What I want to focus on now is the documentation which is proving to be incredibly difficult. I'm finding a lot of inspiration watching the MIT lecture series on computer science, which talk a lot about Lisp/Scheme and so I am trying to relate what they discuss to Maylee. Apart from documentation, the testing platform needs some work, I am not a fan of doing testing and I also find it to be distracting, but it is definitely a critical part of the development process.

[Kranar]

So I've entered a rock paper scissors programming tournament.

To the winner of the tournament $500 and there are also secondary prizes for things like performance, and other technical feats. The tournament is basically your algorithm plays RPS against an opponent 100000 times and you win if your algorithm has a win percentage of atleast 66%, since otherwise you might have just gotten lucky. The win should be decisive.

It turns out there is quite a bit more to this game than meets the eye. The optimal strategy is technically to go random each and every chance, the problem of course is that by going random you can only tie. So if you're random and you guy up against someone who always picks rock, the best you'll do is tie against him, whereas a clever algorithm would be able to pick up on the fact that an opponent is biased towards rock and would then be biased towards paper.

As such, while random is optimal, it assumes all other opponents are rational and thus would go random as well, resulting in ties for everyone. The key to this tournament will thus be to write a program that can find flaws in its opponents and exploit those flaws.

So... how to approach this? Well my strategy can be broken down into two components. The first component is an evolutionary strategy. In just the same way that Darwin's theory of evolution, survival of the fittest, has resulted in pretty sophisticated living organisms, I am going to assume that survival of the fittest can result in sophisticated rock, paper, scissors playing programs.

The way it works is, I randomly generate 100s of thousands of rock paper scissors players. One such player will be the guy who always pick rock, another will be some other guy who plays a more sophisticated strategy, all these guys are randomly generated, but because I am generating sooooo many of them, you're bound to generate a few who are pretty clever and can track patterns and exploit flaws in the opponent.

So once all these guys are generated, I have them duke it out in a round robin tournament. At the end of the round robin tournament the bottom 10 percent of players get the boot, and the remainder of the players randomly merge together. The merge is done in such a way that if opponents A and B merge to form opponent C, then C can on average defeat both A and B...

Then this continues again, another round robin occurs with the remaining mutated population, and the bottom 10 percent are thrown out, until finally there is just one guy left.

But of course, I must take it one step further... which brings us to the second portion of my algorithm, the meta-strategy.

The premise of the meta-strategy is to assume that regardless of how clever I am, my opponent will somehow find a way to catch onto my strategy. As such, if my algorithm notices that it's lost 5 games in a row, or if it's lost 15 out of 20 games, then my algorithm creates a meta strategy which is designed to defeat the original strategy.

How this works is... if I've lost 5 in a row or 15/20, then obviously my opponent somehow cracked my strategy, which we will call S0. So my algorithm generates strategy S1, and what S1 does is run S0, if S0 picks paper, then since my opponent has cracked S0, my opponent is most likely going to pick scissors, so S1 picks rocks to beat scissors.

If my opponent catches onto S1, then my algorithm generates S2, and this continues indefinitely...

Hopefully the end result is an infallible rock paper scissors playing monster.

Mostly I'm typing this because I'm waiting for the evolutionary process to finish. It's going to take an expected 5-6 hours for all the randomly generated algorithms to duke it all out until one winner emerges.

I tested it earlier last night with a very small population of 200 and the result was semi-decent. He was smart enough to always go paper if I always went rock, and he could detect and crush cycles of 2 moves, like rock/paper/rock/paper ... but anything more than 2 and it was clear he was unable to pick up on it.

Hopefully with this random population of 600,000 the winner will be smart enough to detect cycles of 50-60 moves, be able to notice biases and other clever things, but only time will tell...

[Kranar]

"All that we see or seem is but a dream within a dream."
- Edgar Allan Poe


My latest entry concerns a principle which I find is vaguely known by many one way or another but not really understood or appreciated fully. What I intend to describe in this entry is a consequence of the most important physical theory of the 20th century, that being Heisenberg's Uncertain Principle. It is not an understatement to state that this principle really opens your eyes as to the nature of our existence and its implication on how it is we experience the universe we live in. What we observe with our 5 senses really is nothing more than an illusion, a gross over-simplification designed by our brains to make sense of the world as much as possible when in reality something far stranger and mysterious is going on behind the scenes.

I am motivated to write this after having a discussion on this issue where I felt some of the fundamental ideas behind the uncertainty principle were not well understood. It's not unusual that I find people confuse the uncertainty principle for being some philosophy or idea that says that when we observe something, we change the outcome of what we observe in an unpredictable way. This actually is radically different from what the principle states itself, although I can understand why people would make this mistake.

Unfortunately to really understand why this is can't just be laid out all in laymens terms and it does require having some understanding of the physics behind it. I am virtually baffled as to how to begin approaching this topic, and so perhaps some motivation and would help, let's imagine we're physicists embarking on a new field of study. We'll start with the simple question, is light made up of tiny particles, or is it instead a wave like sound?

Think about what it means to be a particle, usually a particle is some ball of mass that occupies a region of space. A wave, on the other hand is something that sort of vibrates up and down as it travels along a path. When two particles collide they bounce off of one another, whereas when waves collide they just temporarily merge and then travel through one another without a problem. Simple stuff right...

So, in general, how can we determine if light is a wave or a particle? Well how can we determine if any arbitrary entity is a wave or a particle? Let's come up with an experiment, in fact the name of this experiment is the double-slit experiment.

What we will do is have a machine that emits something repetedly over and over again and we will follow the path that it takes as it passes through a barrier with two slits in it.

If what we emit is a wave, then when it hits the barrier two new waves are generated whose origins are the slits, and since we have 2 waves they are free to pass through one another and merge together.

When two waves merge one of two things happens, either the waves cancel one another out and it appears as though the wave disappeared (destructive interference), or the two waves boost one another and you get like a super-wave (constructive interference).

http://www.gsplayers.com/kranar/wave.gif
(example of a single wave splitting into two)

As such, if we emit a wave we expect that when the single wave splits into two waves, that those two waves will sometimes interfere and disappear, or interfere and become a superwave.

However, if I take a pellet gun and start shooting bullets, there's no chance that a bullet will magically split into two identical bullets and either cancel one another out and remerge to create a super bullet. That makes no sense at all and clearly is an absurd notion... a particle can't just split and be at two places at once only to either re-emerge as a super particle, or to just vanish off the face of the earth.

http://www.gsplayers.com/kranar/particle.gif
(example of path of a particle)

So, let's take our experiment and apply it to light, if it's a wave then we will notice the wave of light split into two waves and these two waves will interfere with one another blah blah blah you get the idea... if it's a particle no such weirdness will occur.

Well after conducting this experiment, it turns out we notice that light DOES interfere with one another. Voila, light must thus be a wave and this century old debate is now over...


And now comes the Uncertainty Principle. Without diving too much into the math, it turns out that a physicist by the name of Heisenberg managed to derive, purely mathematically, an equation that relates position and momentum together. The problem is that the equation states that the more you know the position of a particle, the less you can know about its momentum. This equation has nothing to do with the fact that our measuring tools are inprecise, or that when we observe something we change the outcome, it has to do strictly with the definitions of position and of momentum and it is something that is derived entirely mathematically. This is IMPORTANT since many people seem to think that the problem is simply that when you observe something you change the outcome, that couldn't be further from the truth.

Well if this is the case, then something is really wrong here. See it turns out that waves in general have momentum, and if you don't know what momentum is, it doesn't matter, just recognize that light does have such a property. So this uncertainty principle says we can't know both position and momentum accurately, there's some kind of trade-off. Well let's cheat the system. By examining the way that the waves interfere with one another, I can actually determine as accurately as I desire what its momentum will be. To determine what the position of the wave will be, well that can also be done, I will just place a position detector at each slit and wait for the wave to pass through it, when it does I can use the detector to record its precise position. By making better and better position detectors I can also record the position of the wave as accurately as I desire.

So in doing this I will now proceed to cheat the system and measure BOTH the position and momentum of light as it passes through my slit with arbitrary accuracy thus violating this mathematical proof of Heisenberg's.

But alas, something very weird happens when you perform this experiment! Whereas before light behaved as a wave, when you try and measure its position, it now behaves like a particle and so it's not possible to measure its momentum since no interference occurs! What the heck is going on? When light was allowed to pass unobserved, it behaves like a wave, but when you observe it passing, it behaves like a particle.

Okay fine... light is weird, let's ignore it. Let's use our experiment on something we know to be a particle, the good ol electron. An electron is a particle everyone knows that right? It's a particle that orbits a nucleus at the centre of an atom in much the same way that planets orbit the sun. The trusty ol electron surely won't have any crazy behaviour like light does.

But indeed, when you perform this exact same experiment with the electron you will also notice that when you don't observe the electron, it BEHAVES LIKE A WAVE! The electron somehow manages to be in two places at once at the same time! But when you try and observe the path the electron takes, then it behaves like a particle.

That's the weirdness of the uncertainty principle, it's not that if you observe an electron you change its position or you change its momentum, it's that until you actually observe the electron, it doesn't have any actual position or any actual momentum. An objects position or momentum does not exist, period, until something observes it.

Position is just some concept that our brain uses to make sense of the universe, this notion that you're position is way off over there and that my position is over here, and the sun is out some billions of kilometers away are but illusions, they exist only in so far as something is there to observe its existence. But when left alone an object is free to occupy many positions all at once and it will do so and it will interfere with itself sometimes disappearing and producing really weird side effects. In our example I simplified it and told you the electron splits into two, this is technically false, the electron technically is in an infinite number of positions all at once and it isn't until you observe it that you force it to be in one of those infinity of positions. This is why an electron left unobserved produces this wave like behaviour, it is in so many positions at once travelling that it interferes with itself, it bounces off of its own self sometimes disappearing, sometimes reappearing.

But position and momentum aren't the only two physical quantities that are a product of our own observations... quantum mechanics actually has several such pairs, and perhaps the one that might strike you as being the weirdest is that both time and energy are also subject to this same weirdness.

The universe, in reality, is typically denoted by U. The universe we observe, is typically denoted by R. Since R is a simplification of U, there are many possible ways that U can be converted into R so that we human beings can observe it. Because of these many possibilities, physicists have to resort to using probabilistic models of physics to describe the observable universe. They use something known as Schrodinger's equation to describe the behaviour of an object as it exists in the universe U, but there is a special procedure known as the wave-function collapse which describes how to take the universe U and convert it into one of the many possibilities for R. This wave-function collapse occurs when someone tries to observe U and thus make a simplification of it.

And there you have it, the uncertainty principle in as close to laymans terms as I could possibly make it, but also staying true to what the uncertainty principle really says. This really is only touching the surface of course, since now that we know that what we observe is different from what really happens, the question is, how do we reconcile this difference? How do we interpret this result? What are the implications?

While I would love to go in more depth and describe some incredibly mind blowing results that this opens up, I think it would be best for me to get some sleep.

Oh and I should give credit to the diagrams I used, I found them doing a Google search on double-slit experiment, edited them slightly. They originally came from the University of Winnipeg.

[Latrinsorm]

I wonder if I can just make a macro or something to post "Ah yes, that is quite impressive. Well done!" after every awesome Kranar post, because dang. That was quite impressive! Well done.

The best moment in all of physics is definitely when you send one particle (photon or otherwise) through the double slits at a time and get interference patterns.

[Artha]

I <3 Quantum Mechanics

[Kranar]

I find it rather peculiar that in the wake of the massive popularity of poker in the past 5 years that it still remains a game very poorly studied in a rigorous and scientific manner. This despite the fact that poker is a game with many interesting computational and mathematical properties. Searching online for “poker theory” returns sites mostly filled with advertisements and very little in terms of actual science. The only major source of research into the area seems to be from the University of Alberta whose publications on the game have had quite a bit of influence on me recently. What’s worse are the many books on poker that try and teach it in such a superficial manner, mostly by providing situations, giving an appropriate response to that situation, and then inserting a disclaimer that every game is unique and no one strategy fits all. There are well known exceptions, such as Slansky’s The Theory of Poker, but by and large poker is an under studied game.

As a computer scientist myself, I find the game incredibly fascinating and it is my hope to write a solid poker playing algorithm. While I don’t expect to produce a world-class player, I would like for the algorithm to perform reasonably well against players who play online at the lower end tables, such as the $3/$6 tables, and possibly the $5/$10. The poker variant in question is limit hold'em, and the name of my algorithm will be Deep Green, a name I shamelessly borrow from IBM who, as you may well know, developed the Deep Blue chess playing algorithm that defeated the world chess champion Gary Kasparov. Periodically I will write articles in here that discuss my progress and the approach I’m taking towards the development of Deep Green. An article I intend to write shortly will cover a neural network I just finished writing that is trained to find very subtle patterns in people's playing styles. Based on this data it will accurately predict what kind of cards might be held by a player based on their betting actions and the state of the game.

[Asha]

Exciting stuff.