Wednesday, April 4, 2012

Continuations and self-reference

Recently, I've been on a kick looking up info on continuations, delimited and undelimited. Last year, I had gotten into a curious programming "notation" (not so much a language, as the high-brow conception of one), with a bare-bones interpreter written in OCaML. I decided to first, translate the interpreter into Haskell (ironically, the author had originally tried writing it in Haskell, but "got stuck"), then study how it worked, and eventually re-write it "the right way." Since the "notation" uses continuations expressly in its control flow, I thought I should make sure my mental grasp on them was as firm and steady as I could make it, so off to thesis-ville I went.

Once there, I found out, as mentioned, that "continuations" aren't the whole story; there are both delimited and undelimited continuations, and they are different. So I read as much as I could stand on what the difference was, and how said difference made a difference. One of the most surprising places I found information on it was Oleg Kiselyov's okmij.org site - not surprised that it had info, only that I understood it. What surprised me even more, was that (undelimited) continuations, especially Scheme's call/cc (call-with-current-continuation, in Lisp-speak), were so tied in with self-referentiality.

Looking further on the okmij site, I noticed an article on "polyvariadic Y," that is, a fully polymorphic fix-point operator. This is useful, in that it lets you describe the mutual fixed point of a group of expressions. What was a little sad for me, coming to the party so late (the original article was from a mailing list discussion in Oct. 2003), was that I immediately recognized the type used for the poly-Y operator: it was ([[a -> b] -> a -> b] -> [a -> b]) just a less general form of what "we" in the Haskell world (especially those who hang out in #haskell on freenode) call the loeb function: (Functor f) => f (f c -> c) -> f c, in Haskell-speak.

Not terribly mind-blowing, but it just seems that that (loeb) function isn't just entertaining, but is downright useful, as are types themselves. For more information on the loeb function, please check out Academy Award-winning (heh-heh) Dan "sigfpe" Piponi's blog; he does a much better job of setting it up, and showing how it's useful.

On a side note, I think that this usefulness in helping to spot abstract idea tie-ins, is the greatest benefit of using types, although having them define and catch constraints on one's code is also a big plus.

Saturday, April 30, 2011

Limits, colimits, and (a very limited look at) their usefulness in programming

Teacher, author and professor extraordinaire (disclaimer: I'm not being sarcastic, I really highly respect this man) Robert Harper posted a high-flying, chock-full of much more information that was used to write-it article on his blog: The Point of Laziness

In it, he tries to once more expound on why the Haskell programming language is unfit for teaching introductory FP. Once more, he has so much to say on the matter, that he winds up only telling that he has a lot to say. Pretty much, if you understand his arguments, you already know them, but fortunately, there are other readers who comment, and draw out more info to better understand what he is particularly speaking about.

Jeremy Gibbons, in a thankfully reliable style, saved the day, with this lovely sum-up on reddit:
"Due to the way Haskell allows ⊥/'undefined' to inhabit all types, the projection/injection functions that
define how a product/sum type behaves are not sufficient to uniquely identify the value of interest." (my interpretation; please castigate me, and not him.

It's slow-going, but learning is happening...I think.

Wednesday, June 23, 2010

A Half-Minute Introduction to Functional and Object-Oriented Programming

Okay, I'm not going to be quite so ambitious as to explain everything about both paradigms, just one example that highlights what a major difference is and why it exists.

Today's example: "object" state.

Imagine a small Post-It pad as your memory, with, say, a number "2" written on it. In fact, let's be more "ambitious," and imagine a mini-clipboard, with four post-it notes on the back:


"John"                "Smith" 

Yes                   2       

Now, imagine tearing off the "2", writing a "3" on a new note, and sticking the new one in the place of the "2".
To an OOP person, you've just changed the state of an object. To an FP person, you just changed which state the object refers to. The OOP person maintains continuity with the object. The FP person keeps continuity with the values associated with an object. To the OOP person, it's the same object, just with different (new) parts. To the FP person, it's a different object, because it has different (new) parts (it just has the same name as the original object).

It's kind of like marriage: you're still you (OO), you're just now the same as you used to be (F)...

Monday, May 24, 2010

Dabbling in incremental folds



    I was playing around coding up programs for Project Euler, when I noticed that I was 1) using an old stand-by function, to add up the digits in a big number; and 2) I was coding it up in a way that echoes up other functions I’ve done, such as the ever-popular “chunk”; 3) I was not coding it up in the semi-unrolled-in-another-dimension form of “map snd . takeWhile (p.fst) . iterate (\(old, pair) -> (new, different pair) $ start” that I also use for that kind of problem, but in the “let (intermediate, pair) = auxiliaryFunction argument in finalProcessing intermediate (recursiveCallOn pair” format. I asked about it on #haskell - hands down, the best resource for help on all things CS-ish EVAR! - when for some reason my brain zigged instead of zagged, and I recalled my Internet “colleague” (make no dispute: the quotes are there because I have no more qualification to be this man’s colleague than I do Stephen Hawking) Sean Leather. Specifically, his blog post http://splonderzoek.blogspot.com/2009/04/latest-on-incremental-fold-and.html  where he speaks writes some more about incremental folds, and like a corny Windows 7 commercial, it hit me: I’ve been writing (and re-writing) incremental folds!

    I find this to be a big deal, if only because I have finally hit the level where instead of just reading about all of these useful high-brain-power techniques, I have caught myself using one - yes! I may not be the sharpest tool in the shed (see: Cletus), but love it all, I Am Trainable!
So, knowing a good thing when I see one, I immediately...well, I immediately got back to doing the day job that I’m really supposed to do, instead of goofing off, then I spent some time playing around on IRC, but that very day, I went back to re-read about incremental folds, and how what I was doing fit all into it. Chalk one up for goofing around on the Internet!

Saturday, November 21, 2009

Abstractions Always Leak - DUH!

I was lurking in my favorite IRC channel today, and not-so-calmly
read as a fellow user blathered on about wanting to provide useful
exercises to help inculcate a better eye for abstraction. Now, while
as explained in this form, I see no problem with this, one of the
other denizens of the channel raised a minor objection to the idea
as being in a way, the opposite of abstraction, to which the original
fellow replied with how it wasn't, since "abstractions leak." Now,
I know for a fact that this person is miles ahead of me in every
positive way to measure computer skill, and better off in many other
ways not relating directly to said skill (i.e., I'm sure the person is
younger, fitter physically, and likely more handsome than I).
However, there is one place where I have him beat - this is my blog
- and I'm going to unfairly exploit my tiny advantage as far as
possible, starting with reiterating my title:

Abstractions Always Leak - DUH!

First off, I want to make sure I'm being clear: I'm not trying
to insinuate that this fellow is any less knowledgeable than I am;
I think I made it clear that he is miles ahead of me in CS
knowledge, technical ability, scholastic achievement, academic
talent and industrial usefulness. I'm just using his remarks
completely out of context as a means to spout off on a topic
only tangentially relevant to his remarks, and utterly underestimating
his understanding of the topic. Remember, I've already stated:
I'm the dumb one in the line-up. Also, once again: this is my blog.
His is much clearer, relevant, enlightening and fun to read.

Okay, now that I've wasted everyone's time with all of my caveats,
let's go back to my original point: abstractions. They leak. Duh.
To start, abstractions are metaphors. They are encoded means of
make-believe and pretend. They are "what-if" in software form.
As such, they are meant to go so far in the world of "let's pretend",
and no farther. Unfortunately, most of the software industry is
based on folks who don't know what they want in software, and
are at times talented enough to craft some that works well enough
at a task that other people are willing to pay for its use. Part of the
fun of Computer Science (yes, yes, it isn't really about computers
as such, but what can be done with one) is finding out how far we
can push the abstraction and when it "leaks", how does it leak,
and why. The most important part about finding where the leak
begins in that we can put up a nice friendly sign and warn people
"here there be Monsters!", i.e. "Just (Don't) Do It". Those are the
two most important things to know about an abstraction, or
a metaphor in general, how it applies, and how it doesn't. When
you tell someone "it's raining cats and dogs," you have to know
stepping in a poodle is a joke, otherwise it isn't funny, except
to others laughing at you. Even then, it isn't really that funny, 'cause
you'd have to be an alien, or a Turing Test-flunking computer not
to recognize that old joke.

But I digress.

So, I guess there are three main points to a metaphor, what's
the comparison between, how does it hold, and where does it leak.
Then you can figure out how you can rely on it to give you good
answers about the first thing, or on something else entirely that
uses a useful characteristic.

Just watch out for those leaks. You don't want to step in a schnauzer.

Thursday, August 20, 2009

Autodidacts, Stand Up and Cheer!

For reasons unknown, but gratefully accepted, MIT has placed almost all of its curruculua on the Web.

Now, those folks that don't have the smarts - or the fat wallet! - for MIT can see what they're missing. Plus, those who live for self-study and self-improvement can follow along at their leisure!

While I have no solid idea why they did this, I have a glimmer of a possibility: whenever I can afford it, I'm going to give MIT $100 a month. Granted, $1200 a year isn't going to get my name on a building, but I can rest assured that the folks that set up MIT's OCW site aren't going to be moping in their offices after ten years, wondering if they "ever made a difference in the world".

As an online writer I read has also commented, this move will also start to show up all those other colleges, that wish they had the competence to stand in MIT's company.

In the meanwhile, I'm going to see what those smarties in MA are being taught, but without forking over the thousands to feed all of that ivy...

Saturday, April 4, 2009

Pet the Nice Doggerrel

When either I, or one of my HS/college buddies were working our card skills - and big egos - out, we had a little saying, "I'm going down fast, but I'm miles above you." Usually, such boasting would be promptly followed by getting the needed contract exactly, or in my case, more likely, missing said contract by a hand. Anyway, I was "in a mood", so I fleshed out the boast into a little ditty, so for posterity's sake, and your perusal, here it goes:

"I'm going down Fast, but I'm miles above you.
I'm going down Hard, but it's okay, I'm tough.
It's not much comfort that you'll land before me,
It's not much comfort - but it's good enough."