I was speaking with a friend the other day and we were talking about the interaction of effects and how to explain them.

One informal way to explain some additions to languages are that they are scale down localized structured versions of features that were largely available for the whole program. Let me explain: Did you start programming with an imperative language with global variables? (There is one called C that affected the minds of many people.) When you switch to an object oriented language, someone might have explained to you that there is no longer any need for real global variables. You may make these wannabe globals members of a class. You can turn methods that need the globals into members of that class as well. So they are global as far as the methods in question go, but they are not truly global.

In much the same way, we can explain yield. Programming languages have always had input and output operators - scanf-printf, gets-puts etc. However these operators are global with respect to your program. When you execute a printf, it is the output of the whole program, not of any one part of it. Yield on the other hand can be thought of as a localized input output operator. You can yield values from one part of the program to another part of the program. You get input from one part of the program. A method that yields is a packaged up opaque entity, a little sub-program, that communicates using yield with its consuming-context, the rest of the program.

We can explain exceptions in this way as well. In the absence of exceptions when there was a fault, the whole program would come down. It would core dump, modulo global error handlers. The whole machine does not come down, just the program that faults does. The environment that hosts the program may realize that there is a fault and do something about it. Its much the same with exceptions, but with the difference that only a part of the program "core dumps". Its a localized failure of the program that the environment (the rest of the program) can handle (or not handle, thereby making it a global failure).

So can you play this game or any other global program features, turning them into powerful localized structured operators?

An odd idea from a few days ago:

I watched this video a while back, this is Richard Feynman giving a lecture about discovering laws in physics -

He is talking about laws in physics. (the underlying Philosophy of Science that Feynman describes here is due to Karl Popper)

What Feynman is describing seems fundamentally different from what we do in the formal sciences like math/logic/cs. In the later we usually choose an axiom set that we believe to be right, based on our aesthetics, and then go on to prove other things that are right wrt our axioms.  Only things that are provable are taken to right and things that are right are irrefutably so. The system is inconsistent if we deduce False from the rules that we have. Inconsistent systems are not interesting. All formal methods work like this, in spirit - they keep track of what is right.

In what Feynman is describing, they don’t have a formal notion of right. They have a notion of what is wrong and as long as something cannot be constructively (by experiment) shown to be wrong, they can temporarily accept it to be not-wrong. If you look at this as a formal system, this is one where “what is not wrong yet” is known instead of what is right. Something is not wrong because 1) We don’t know a proof by which we can construct F from it or 2) Given our current inference rules there is no proof for it. But, we may add a new inference rule to the system in the future which may invalidate the belief that something is not wrong. It’s a feels like the opposite of what we do with logics.

Imagine a formal system or a model of computation based on notion like this. We are, in a fundamental sense, giving up the notion of consistency and completeness when we do this. I wonder if there exists a computational model that corresponds to such a “co-logic” of the sort they use in the *real* sciences. Such a system, in spirit, might be able to deal with partially correct data, incorrect assumptions etc. in a natural way. Absolutely correct data (or properties about the data) would be the exception.

(I wonder what this implies for the incompleteness theorem and such. I have been told that the "co-logic" I refer to here is actually co-induction. I see some similarities there, but I am not sure if its exactly that. )

A Tutorial on (Co)Algebras and (Co)Induction - Jacobs, Rutten

A Tutorial on Co-induction and Functional Programming

Being at Indiana University, which is an old time Scheme hub, every now and then I am exposed to some of the turmoil in Scheme community over the new Scheme standard, R6RS. Essentially the community is having a hard time agreeing on what should be in the new standard. There are some very smart, very accomplished, very opinionated people who belong to this community and the language spec is a bit of a battle ground, from what I hear. (As are all language specs... some battles, I suspect, lack the intellectual quality of this one)

I am not very much of a Schemer myself, I sometimes indulge the language on a need basis. I hear from some my more intensely-Scheme-happy friends about some of the latest news at Scheme-spec land. One of the names that was mentioned in recent times is that of Will Clinger. Apparently, Will Clinger set into motion some of the discussion that formed the origins of the new standard, called R6RS (that is short for Revision-6 of the Report on Scheme - or something approximately like that). Over the years the formalization of R6RS has had its ups and downs. Of the many differences of opinion on the standard, some resulted in the formation of a group that decided to create an alternate standard. This group is called SchemePunks, apparently headed by Will Clinger himself (*). While this is mostly hearsay, it seemed amusing none the less. I also, sort of, like Scheme - so I listen in when one of these conversations come up.

Today I was searching for something and I came across the SchemePunks webpage/wiki. I didn't realize they had a webpage. Better yet no one told me that it written in excellent Hitchiker style! I read this and burst out laughing - what a way to motivate a language standard! I don't know any of the design decisions they have made, but the introduction here is sheer genius. Despite not being a Schemer, I am almost tempted to join in. :)

From the SchemePunks webpage:

On 29 August 2007, the Revised Revised Revised Revised Revised Revised Report on Scheme was ratified by the Steering Committee. This has made a lot of people quite angry and has been widely regarded as a bad move.

Many programmers believe that it was created by some sort of community process, though the Jatravartid people of Viltvodle VI believe that the entire Standard was in fact sneezed out of the nose of a being called the Great Green Arkleseizure. This theory is not widely accepted outside Viltvodle VI, and so, standards being the puzzling documents that they are, other standards are being designed. And this wiki, which is called SchemePunks, is definitely not part of the Scheme Underground, even if it is, which it isn't.

Which is very odd, because without that fairly simple piece of knowledge, nothing that is written on here could possibly make the slightest bit of sense. We hope to develop an alternative specification for the Family of Programming Languages known as Scheme. Watch this space.

Being somewhat bowled over, I had to look for the man - William Clinger, Professor of Computer Science, Northeastern U.
http://www.ccs.neu.edu/home/will/Personal/western1.jpg

:)

I wish more languages where designed in H2G2 spirit. Aah!

From his webpage:
http://www.ccs.neu.edu/home/will/R6RS/essay.txt

More than twenty years have passed since I wrote this [1]:

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

I have to say, I am compelled to agree, though I wonder how of it applies to the Scheme of today. The essay is worth a read, even if you are not a Schemer. You can skip over the Scheme specific parts and just look at the language design philosophy.

I get irritated because too many people in the "computing" business don't understand the word "lambda". Its just irritating because at the heart of it, its just a simple fundamental idea, like the notion of natural numbers or counting. So just spend a few minutes, understand what it means and stay educated. In a few years (if not already), almost every language is going to expose something like a lambda to its programmers. So just pick up the idea ok?

This is a working description, it wont make you an expert on the Lambda Calculus. It might give you some intuitions about it though. Lets get started.

So assuming you are familiar with a C-like language, how do you write a function that takes an integer and returns it?

int foo(int x) {
    return x;
}

Now lets look at what this is saying, it says there is a function called foo, it takes an int which it names x and it returns an int. the body of the function has a single statement called return x. Great! Now, this function is a very famous one and is called the identity function (usually goes by the nick-name id). Also when we talk about functional programming we dont really care very much for the C-style types. So let's rename the function and drop the types.

id(x) {
      return x;
}

Don't worry too much about the types. Typed functional languages usually have a different notion of types from the C like languages. The types will come back, but in a bigger and better form. We however wont discuss any type theory in this article.

So now, what it is saying? It says here is a function called id, it takes some value that it calls x and it returns x. Ok, now lets take a look at this closely. In the syntax that we have here, the name of the function is part of the syntax. We would like to say - here is a function and then assign it the name id. So that we are able to look at the function and its name as two different things. Lets do that by introducing the keyword called "function". Javascript, for example, has such a keyword.

id = function(x) {
      return x;
}

Ok. Now lets make one more simplification. Lets say that the language is a little like Ruby or so where that last statement in a functions body is its return value. Did you get that? That means that we no longer need the keyword return. We can simply make the last statement x and by that we know that the return value from the function will be x.

id = function(x) {
      x;
}

Great, lets rewrite this a bit:

id = function(x) { x; }

Now for one more simplification (really C like languages are so complex!) - lets assume that we can write only one statement inside each function. Just one. If that's the case it can be much like a if with just one statement - we don't need the curly braces anymore. We also don't really need the semicolon.

id = function(x) x

Great! Congratulations ladies an gentlemen, you are looking at a lambda. Simply rename the keyword function and call it lambda and we are all set.

id = lambda(x) x

If we drop the name assignment and look at it we have:

lambda(x) x

This is a function that has no name. It take one argument and return it. Various functional languages use slightly different syntax for writing out their lambdas. The lambda calculus, the underlying calculus of these systems, usually uses a \ instead of the verbose name lambda. It also uses a dot to separate the arguments from the body of the function. A little like this:

\x.x

The functional language Haskell uses an arrow to separate the body from the arguments.

\x->x

The language(s) ML, OCaml, SML, (maybe F#) etc. use the name fun to stand for lambda.

fun x -> x

The language Scheme uses the name lambda and lots of parenthesis.

(lambda (x) x)

Ruby lets you write something very similar to a lambda like this:

lambda {|x| x}

Most of these languages give you some mechanism by which you can give a name to your lambdas (otherwise most of the time you are a little hard pressed to refer to them).

Haskell

id = \x -> x

ML

let id = fun x -> x

Scheme

(define id (lambda (x) x))

There are some alternate syntaxes for writing named lambdas in most languages:

Haskell

id x = x

ML

let id x = x

Scheme

(define (id x) x)

So what is a lambda? It is usually a name used to define a function. The function is a value that can be assigned to a variable name. Just like any other value in your language.

A lambda is an abstraction form. Normally in a program you can read the value of a variable to which you have not assigned a value. In other words is you write (x + 1), it does not have any meaning if x has not been assigned a value already. One way to look at what lambda says is that it abstracts the value of the x. So \x.(x+1) means - give me a value for x and then I will give you the value for x+1. The value of x is abstracted in the body of the lambda. This description comes very close to our informal notion of a function in a C like language.

The lambda calculus usually allows only for lambdas that take one argument. Hence to write functions that take multiple arguments we nest lambdas. We write \x.(\y.(x+y)) for a function that adds two numbers. Most functional languages support multi-argument lambdas. In Haskell this would be \x y -> (x+y).

So what's the big deal? Nothing much and quiet a lot. Nothing much because the notion of functional abstraction is something we learn from high-school math which we port over to programming languages. This is an old and familiar notion.

That said, in the functional programming community, it has long been realized (it is a large community with varying beliefs, secret cults, traditions and practices) that lambdas are the only abstraction form required for a lot of things.  One can do away with loops and conditionals (if, switch) and assignments and numbers and object oriented programming and pretty much everything you can think of (and some things you cant) - they can all be encoded using lambdas. Hence lambdas form a sort of foundational building block for a large number of programming paradigms. At the heart of all of this is the notion of a function - hence the name functional programming.

This is a great slide deck from Benjamin Pierce, Professor Computer Science at UPenn, that shows what the world of programming languages research is doing especially in the context of types.

http://www.cis.upenn.edu/~bcpierce/papers/tng-lics2003-slides.pdf

Also from Pierce is a really good introduction (the best I have found to date) about polymorphic lambda calculi and actually programming in some of those languages. This describes the hierarchy starting with the simply typed lambda calculus (F1) and describes F2, F3, etc and Fw (F-omega). He also talks about encodings of various sorts of types and a whole lot of neat stuff. All of that written in a very readable fashion. I spent my weekend on this and it was time well spent.

http://www.cis.upenn.edu/~bcpierce/papers/leap.pdf

(For some reason this pdf seems to be back to front, but its just fine when printed)

Pierce's webpage is a gold mine of information for the PL student, including neat things like a 'Great Works in Programming Languages' list. He is also a pretty good photographer. I did see him in person when I was at MSRC in summer of 2006. I believe he was visiting those days. I now regret not having walked up to him and saying hi.

"Can you recommend any C++ books?"
"I don't recommend C++."

Afterwards I reluctantly come up with some names. I beginning to notice that I eventually end up mentioning the Scott Meyers "Effective C++" books. The last time I did this I started to wonder why I say this?

When I first read "Effective C++" I was horrified. If I derived any pleasure out of it, it was comparable to the morbid curiosity of going to witness an execution (I probably would not do that though, if I ever got such a chance. I don't have the stomach for it). Back to C++ - Firstly there was no way I was going remember all of that. Secondly I felt deeply uncomfortable. In time I realized that the whole book was written in the style of demonstrating "effective" usages of C++, while what it truly was is a careful documentation of the flaws of the language. Every chapter in that book talks of a language flaw in excruciating detail and how to live with it. That book should have been called "Defective C++".

Then there was "More Effective C++" which essentially did more of the same.  Here is what the language does, here is what you think it would do, here is what you'd like it to do and you put these together and it blows up in your face. In time, my intellectual immune system kicked in and started erasing most of my memories about all this.

So why do I recommend the "Defective" and "More Defective" books? My first recommendation would be to get out of the situation, don't deal with the language if that's possible. If not, and you intend to get it to serve you (instead of the converse) you need to quickly understand that most of the abstractions it provides are leaky. There are hardly any non-leaky abstractions that C++-land provides. (Some people associate this behavior with some notion of "freedom" - I trust evolution will take of those folk.)

So if your abstractions are leaky, in that they are going to have strange interactions with each other under-the-hood, then you should quickly start developing an understanding of what happens under the abstractions you are given. Your effectiveness as a developer becomes proportional to your understanding of what happens under the surface. Hence the "defective" C++ books are a useful read.

Today Aziz mailed me a build of his Ikarus compiler for Windows. Though I don't have much to do with software as such these days, I was excited. Ikarus is Aziz's Scheme Compiler. I use Petite Chez Scheme on my machine. Petite  is Kent Dybvig's Scheme interpreter, part of the Chez Scheme compiler system. I don't have Chez Scheme itself because it sells, I am told, for several thousands of dollars and hence I cant afford it. I expect Ikarus to be comparable to full Chez in many ways and surpass most other Scheme systems out there.

What Aziz sent me was a zip file that extracted to a 128k exe and 4mb "boot" file. He says the boot file says the same between windows, linux and mac. The bootstrap executable changes. This is amusing because the "boot" file is actually the compiler binary. It contains the compiled x86 code.  He able to get away with this because he only relies on the OS to load his little bootstrap exe. After that point he simply allocates memory pages from the OS and relies on the OS for almost nothing that he can do himself. So the exe loads the boot file into memory which then acts as its own loader, sets up its own stack, lays out its own code and data areas, does its own GC and such.

Of course, all of this is written in Scheme itself. There is probably a small C file somewhere that acts as the main() and the initial call into some ASM code that transfers control to Scheme. Fun fun.

I have talked to Aziz about many parts of this system and almost always the design has seemed to be of very high quality. His management of code objects, the runtime stack, continuations and on and on. The system has a large part of R6RS implemented and is already a superset of R5RS as far as I understand. Depending on how the development process stabilizes (after all, this is all one persons implementation), I might move over Ikarus altogether and maybe use it exclusively. 

I was attending a talk by Andrew Kennedy today when I heard that Rotor 2.0 has been released. So it has the Shared Source version of the cool new C# compiler and such. Fun Fun.

Download