Category: lisp

Categories
lisp

Fundamentally Lacking

A while’s back I wrote up my experiences of trying to learn Lisp through various books and I got this comment:

If you want to go down the rabbit hole however (and since you asked), here’s my advice: read SICP. If you’ve been programming in Algol-inspired languages for the last 15 years, your head will probably explode. It is worth it. Do the examples. Follow along with the videos: they contain all kinds of little nuggets of wisdom that may take time to sink in.

SICP, I thought, what the hell is that? It transpires that this book is, as they say in colloquial circles, like frikkin’ huge man. Huge in fame (it’s taught in a lot of places that I could only dream of attending when I was as an undergraduate) and, as it turns out, also huge in terms of sheer quantity of information inside it. So I ordered it on Amazon, waited a few weeks for it to arrive and then queued it up on my bookshelf.

About a month ago I started gently plodding my way through it, scratching my head, doing the exercises and all. It really is very good, but I have no idea how I would have done this as an introductory programming course at Uni. Let’s just say the exercises can be a little challenging, to me at least.

The amazing thing is I’ve only really just finished Chapter 1 and I feel like I’ve put my head through a wringer. So I’d really like it if you can come and visit me at the funny farm after I’ve done Chapter 5. Visiting hours are 9-5 and please don’t shout at the other patients it freaks them out. Anyway, today’s mind melt is Exercise 2.5 and it asks us to …

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product (2^a * 3^b). Give the corresponding definitions of the procedures cons, car, and cdr.

Up until now all the really hard problems had ‘Hints:’ in parentheses. That’s usually how I know when I’m going to be screwed. I wrote some numbers down, first on paper then in Egg-Smell but I just couldn’t see how I was going to extract two numbers from the encoding. Then, bizarrely, whilst reading about Church numerals (eek) I discovered that there’s a fundamental theorem of arithmetic that I never knew about. How does that happen? How did something that fundamental escape me all these years? Reading it was like being told by a German co-worker that the only time an apostrophe is appropriate in “it’s” is for a contraction of “it is”. Scheiße.

Not only is there a fundamental theorem but it suggests the answer to Exercise 2.5. Perhaps one day I’ll be able to program & punctuate. One day.

Categories
lisp

Let the Foreigners In!

In Learning Ruby by Extension I claimed that learning a programming by writing extensions was a worthwhile exercise to really get to grips with a language. This is because to write a natural-feel extension you are forced to learn a fair bit about the internals of the language. I was wrong. Well sort of, let me explain.

Last week I bemoaned the poor network programming support in my Common Lisp implementation and so this week I resolved to get my beloved multicast sockets working by breaking the abstraction a little and just implementing the missing socket option call as a foreign function call. I was looking forward to it because I had anticipated that it would teach me something about Lisp. It didn’t. Well at least not in the way I was expecting. Absolutely nothing, and there’s a reason for this.

The foreign function interface for Lisp is at a higher level of abstraction than what I was doing with Ruby or Python. With Python, especially, I was actually creating Python objects and classes within C++ modules that Python would allow me to load as if they were native modules. This meant I had to delve into topics about Python’s garbage collection, threading and more. With Lisp’s CFFI (and all of the other FFI’s I’ve seen so far) things don’t work quite like that because they don’t need to. The language allows for much of the mechanics to be completely abstracted away and become almost transparent to the user. Let’s take a look at this by looking at what I did:


(require 'cffi)
(use-package :cffi)
(defcstruct ip-mreq
  (multiaddr :uint32)
  (interface :uint32))

(defcfun "setsockopt" :int
  (socket :int)
  (level :int)
  (option :int)
  (option-value :pointer)
  (option-length :int))

(defcfun ("inet_addr" inet-addr) :int
  (cp :string))

(defun socket-add-mcast-membership (socket-fd mcast-addr iface-addr)
  (with-foreign-object (mreq 'ip-mreq)
               (setf (foreign-slot-value mreq 'ip-mreq 'multiaddr)
                 (inet-addr mcast-addr)
                     (foreign-slot-value mreq 'ip-mreq 'interface)
                 (inet-addr iface-addr))
               ;; level = 0 = IPPROTO_IP,  option = 12 = IP_ADD_MEMBERSHIP
               (setsockopt socket-fd 0 12 mreq
                   (foreign-type-size 'ip-mreq))))


That's it, no external C modules or makefiles it's all done inside Lisp.    I'd make this a bit cleaner before I incorporated it into my application because I've intentionally cut some corners to show the relative simplicity.   However, it goes to show how easy it is to do.   For example if you look at the inet_addr C function definition it only requires a two-line symbolic-expression to have a callable version inside my program .   Indeed this solution is on about the same level of complexity as defining an entry point in .NET which couldn't really be any simpler.   And like .NET there's no C 'glue' libraries to write because CFFI is doing all the heavy lifting.   All arguments and return values are being marshalled into and out of dynamically allocated intermediate values.    Which is pretty neat because it means all I have to do is concentrate on the abstraction.    Even better is that CFFI allows the partial definition of structures which is great when you have a large and complicated struct which you only care about some of the values for.   But that's another story.


Now if we're going to be fair to Ruby, Ruby actually has two ways to write non-local extensions.   The first is to use the supplied C programming interface, similar (but simpler) to how Python does it.   The second goes a step further and has a gem that allows you to embed inline C directly into the Ruby code.   Although I don't think I could have used it for the tibcorv project (because I needed to support callbacks) that's also pretty impressive.   Having said that Ruby can only achieve that by having access to a C compiler.


At the risk of stating the obvious a simple method for the definition and invocation of foreign functions is a requirement, I think, for any language to become and remain successful.   The easier it is to get the foreigners in the more possibilities you can exploit because there's a C library somewhere for just about any task you can imagine.   However, I qualify my original statement that writing extensions can teach us a lot about a language.    More specifically I now think that writing extensions will teach you a lot about a language only if the level of abstraction  that you have to work at to get the job done forces you to.    And as far as I'm concerned, the more abstract the better.
Categories
lisp

Talking to Donkeys

Too much choice is challenging, to say the least. Well, it is to me anyway. I get hung up on trying to pick the best choice from a huge list of items and end up doing nothing at all. All too often just making a choice, any choice, would be the best idea. However when you’re writing software and trying to pick from an array of available libraries the penalties of a wrong choice can be amplified later. This penalty comes from having to bet early on your chosen horse, but here’s the kicker, you could well have a lot of capital in the race before you realise you backed a donkey.

Donkey

For instance, if you choose the wrong core library for the “Next Big Thing” now, you run the risk of tying yourself to an implementation that might have a flaw in it that you can’t fix because it’s not open source or because you don’t have the resources to undo it. So you have to adopt a work-around. Thankfully, most of the time things don’t turn out so bad. But if I stop talking to the donkeys for a minute and listen very carefully I can hear millions of developers happily using Microsoft’s tools and libraries without a care in the world. They don’t have to think about this sort of problem very often because Microsoft thought about it for them and gave them the library as part of the SDK. Those developers are real happy with what they’ve got and who can blame them, it’s like having an older brother who looks out for you. So what if he steals your lunch money, it’s part of his charm.

I don’t want to bash Microsoft here, by the way, I think they have a massively important role to play and I have to admit that some of the more recent tools they have made have been pretty awesome achievements for a gigadollar-company. It seems obvious, to me at least, that the higher Microsoft raises the bar in terms of tools the better it is for pretty much everyone. But the (real?) world outside of Redmond is a little more confusing, I know from (old) experience that when I want to use a SMTP client in Java I’ve got to go through a process of evaluation. In .NET the client that comes free in System.Net.Mail will do just fine, nothing to add. Sure sometimes .NET will sometimes be found lacking, but I’ve been pretty happy with the standard libraries in .NET so far and it’s only when I want something a little unusual that I need to go elsewhere (except for the annoying lack of a built-in Set class but that’s a different story).

Well all I wanted to do this week on my continuing Lisp learning exercise was send a multicast packet from my Common Lisp project. Guess what, network programming in Common Lisp is simply not possible. Gasp. It seems that the Common Lisp standard was set in 1994 and so predated the massive expansion of the internet. So CL projects like trivial-sockets and usocket have been created as CL vendor neutral APIs. Unfortunately, it seems trivial sockets is abandonware so I guess usockets is the way to go. But then, it seems broadcast networking is still work in progress for usocket so it seems fair to say that Common Lisp network programming for multicast will be some time off. In a platform independent way at least.

Even that’s ok. I don’t mind. I’m not producing any world-changing libraries here. Hell I might even pitch in on the usocket effort to help out. But right now I’m only messing about trying out some ideas to see what might fly, it’s what Lisp is good at after all. So I’m happy to use whatever multicast support SBCL has. Crap. They don’t seem to have implemented all the socket options needed . Then I read this very illuminating 2005 paper that lays the CL network programming problem out beautifully but when you scroll down to the “Proposed Solution” it says:

… To be written

If you stop talking to your own donkeys for a second and listen you might be able to hear me laughing. Very faintly.

Ok, I know what I’ll do. I’ll take a look at what I need to do make a foreign-function interface work. Yeah, that’s good, I’ll do that. Crap. I’ve got to chose between UFFI & CFFI. So I already know that I’m going to have to take a look at both to see what’s going on. A short while later and I’m starting to believe that CFFI is the cleaner of the two but then I stumble upon Verrazano and SWIG and my head starts to spin.

At this point it’s hard to be cross or frustrated about anything. This isn’t really anything that I can really blame CL for, it’s just how it is, if time-travel had of been available when the 1994 ANSI Common Lisp standard had been accepted then I’m sure they would have added a sockets layer. I can’t blame OpenSource because I can’t stop applauding it. I bow down to those people that have sacrificed their own personal time to make my life easier / better. I know that the fact that I have to do a little bit of work in the decision making process should make me happy because I have a choice to begin with. And anyway it’s better than having to do the whole thing from scratch myself.

But here’s the thing. When I stop shouting and beating my donkeys for being a bit lame and look up there’s millions of Microsoft developers cheerfully waving at the crazy guy who talks (and occasionally beats) his donkeys. I know if I was one of them, I’d think I was crazy too.

I think we donkey beaters can turn this around. I still believe that in general what I can hold in my hand for free is far more powerful than anything I can buy. The problem is essentially one of continuing improvement and better communication. All I have to do is stop cursing the donkeys and do something about it.

Categories
lisp

It’s imperative that it’s functional

So last week I mentioned that I’d been practicing my Common Lisp by having a go at some puzzles on Project Euler.

A few days later I got an email asking me about what my experiences of the project were and how far I’d got on the puzzles. Well now I can reveal to all of you the heady extent of my genius. My correspondent also casually dropped in the fact that he was trying to do his puzzles in a functional, rather than imperative, programming style. Oh … yeah, “functional programming” I’d conveniently forgotten about that. I was so busy getting to grips with programming in CL I forgot about the important bit. I guess 15 years bashing your head against C++.Java and C# is going to have some long-term mental health effects.

Losing the plot

Now, my CS class at University (15 years ago) very briefly touched on functional languages so I’m not totally clueless. However, we learnt precious little and there is really no defense for that University to not place a larger emphasis on functional programming. I would argue, now, that it would have been a lot more useful for them to teach us a functional language than what they did teach us, which was: COBOL.

So, given my limited understanding, the point of functional programming is to write programs that behave more like mathematical functions. This has certain consequences since a mathematical function can not have side-effects like printing “Hello, World!” or delivering spam. Which surely is going to disappoint some people.

It is this “dirty” little secret of programming (i.e. that it should probably do something if we’re gonna get paid) that makes pure functional-programming a little less straightforward. Languages like Haskell have monads that address the problem of purity by effectively differentiating the pure from the impure. But I don’t think I’m quite ready to go there just yet. Maybe in another 15 years.

Taking the tablets

Ok, so where was I? Well, I’m going to try to make my code more functional too. Which means a diet of higher order functions and recursion for me. So let’s pick a trivial example and see how we do.

Problem #6 in Project Euler asks us:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

My first solution looked like this:

(defun sum-of-arithmetic-series (n)
  (/ (* n (1+ n)) 2)

(- (expt (sum-of-arithmetic-series 100) 2)
   (loop for i from 1 to 100 sum (expt i 2)))

Which I was proud of because I’d figured out that I could use an equation to solve the first part. This isn’t terribly functional though because the second part uses a loop. So I tried again, this time I thought I could do better. I decided that what I was really doing was summing a series of natural numbers in the range 1..n. I could generalise this into: “apply a function (or the identity) over a series of numbers and sum the results”.

Looking at the problem this way generates an abstraction that did not previously exist in the earlier solution, making it a more general result and increasing the possibility of its reuse (perhaps!):

(defun sum-of-series (n &optional f)
  (let ((n-dash (if (null f) n
		    (funcall f n))))
    (if (= n 1) 1
     (+ n-dash (sum-of-series (1- n) f)))))

CL-USER> (- (expt (sum-of-series 100) 2) 
	    (sum-of-series 100 (lambda (x) (* x x))))
25164150
CL-USER>

Ok, I know it's trivial but it made me feel better. There was only one problem though. When testing this for large n (> 30000) I got stack-overflows. Which surprised me because I was expecting it to be tail recursive and hence a tail-optimization to happen. I tried playing around with the debug settings and trying different variations but no amount of playing could make SBCL do the right-thing and optimize the recursion away.

Guess I need to do some more investigation into functional programming and that's probably an imperative! (groan)

Categories
lisp

Common Lisp and the Towers of Blub

So I’ve been teaching myself Common Lisp. It’s a slow process because I don’t get a lot of time to do it, and also I’m a bit slow. The reason I’ve been teaching myself? Well I’m wholly dissatisfied with C++, Java, C#, and to a much lesser extent Python. I still love C though. She’s my lady. We connect.

The dissatisfaction started after I read Paul Graham’s “Hackers and Painters” book. I wrote about it too. Whilst reading the book I came across this paragraph and identied myself as a card-holding member of team “Blub”:

As long as our hypothetical Blub programmer is looking down the power continuum, he knows he’s looking down. Languages less powerful than Blub are obviously less powerful, because they’re missing some feature he’s used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn’t realize he’s looking up. What he sees are merely weird languages. He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.

Since then I’ve been on a journey. It’s taken me through books, well a book. I’ve discovered that Emacs is like 1 million times more powerful and sexy than her slightly musty smelling older sister Vi, with whom I’ve had an almost 15 year relationship and am trying to get out of my head. :x!

If you don’t believe me about Emacs (and why should you) consider how you’d write a video editing suite in whatever code editor you use or can extend. I already knew long ago that Emacs is at least partly written in Emacs Lisp but I should have guessed that arguably the most productive Common Lisp development environment, or IDE, is also an Emacs extension called SLIME.

Soon after that I discovered some fantastic screencasts in the Ruby On Rails mould for stupid people (like me): SLIME, Hunchentoot, and Selenium. BTW, I know Selenium is not Common Lisp but the screencast presents a Common Lisp binding to the Selenium Remote Control server that makes it possible to use Selenium from Common Lisp as a testing framework.

So it feels like I’ve come along way. But today, your humble programmer-of-Blub discovered something on the HyperSpec that scared me a little. Through the PlanetLisp RSS feed I discovered that I am also really crap at mathematics. I did this by trying some of these puzzles. In attempting to solve puzzle #2 in Lisp I found I needed to brush up on some Lisp basics. After some digging, and through a series of HyperLinks, I ended up here and before that here:


...
;; This illustrates the use of SETQ on a symbol macro.
 (let ((x (list 10 20 30)))
   (symbol-macrolet ((y (car x)) (z (cadr x)))
     (setq y (1+ z) z (1+ y))
     (list x y z)))
=>  ((21 22 30) 21 22)
...

I think I stared at this code snippet for about 2 minutes before it finally made sense when I at last remembered that setf works on a place and not a symbol. Now, I’m guessing an experienced Lisp-er would look at the sample and say ‘so-what’? I’m guessing that non-Lispers would say, anything that looks that complicated must be bad.

And this is when it struck me again. And this time it hurt. I may have lost a little “Blub” to get this far but I still have way much more “Blub” to lose.

Categories
java lisp ruby

Continuations and Exceptions

I very often find myself tripping over ‘old’ ideas in software technology and discovering a rich topic that I had no idea even existed. This weeks elephant in the room is the ‘Continuation’ language/compiler feature.

Let’s take a quick look at a simplified version of an example of a continuation that I found to illustrate the point.


irb(main):041:0> def ab
irb(main):042:1>    puts "a"
irb(main):043:1>    callcc { |continuation| return continuation }
irb(main):044:1>    puts "b"
irb(main):045:1> end
=> nil
irb(main):046:0> x = ab()
a
=> #<Continuation:0xb7c5ee84>
irb(main):047:0> x.call()
b
=> nil

The callcc function accepts a closure as an argument. This closure accepts the ‘continuation’ and we immediately return it from the function. The continuation contains all of the state that got us to the point before we exit, variables, stack-frames, the lot. The key is that the continuation is itself a closure and when it is called the code will continue from the next line. I think it’s easy to see that this feature has pitfalls. It’s like a GOTO but without the benefit of having a line number to lookup! This is because on the outside every continuation looks pretty much the same. But this approach does have arguably real tangible benefits in Web servers like Seaside.

So what?

Well it turns out that exceptions in C++ derivative languages are a stupider half-cousin of continuations called: escape continuations. Thinking about it the similarity is striking and not all that surprising. The reason I say they’re stupid though is because exception objects are not re-entrant in the same way as continuations are, and the context that is captured from the exception is defined by the programmer. However, it’s plain to see that the exception handling we have in most modern programming languages like C++, Java, C#, etc are a diluted form of continuation.

So what?

Well I’m not totally convinced of the practicality of continuations in web programming environments, partly because I’m a bit old-school when it comes to performance and those languages that have web-frameworks and support continuations (Smalltalk, Ruby, PHP) are slow-as-molasses. The other reason I’m not keen on the idea of continuations is the practicality of working with them, i.e. they are a variation on the GOTO in that it’s very hard to follow the flow of the program by just looking at it and reading it. But I know that one day I will discover the need to make sparing use of a continuation and be glad that I knew that I could do it.

If the truth is ever told, I think exceptions suffer from the curse of the GOTO as well. And I think the reason for that is partly because the exception mechanism as implemented in Java, C# and C++ is a teensy bit broken. The reason, again, is that the flow of control jumps up the stack to a potentially unknown place. I say unknown because if you write a library that throws an exception and after you release it you change the contract of how that exception is thrown, well then you’re in trouble.

Trouble, that’s what

The catching of exceptions is based on type, and inheritance rules apply, so the inheritance hierarchy of the exception classes you use affects the flow of control. This is clearly the intention since you use the type to differentiate a NullArgumentException and a NullPointerException and how you deal with these will probably require different code. However, if the handling code was the same well then I why couldn’t I catch the base class instead and have one code-block? This is the temptation and the danger because if someone else decides to rejig the exception hierarchy you might not catch the exception you want. Worse still, you might end up catching exceptions you don’t expect and providing incorrect handling code for them.

So what?

Well like Peter Parker says:

Whatever life holds in store for me, I will never forget these words: “With great power comes great responsibility.” This is my gift, my curse. Who am I? I’m Spider-man.

And whilst we may not be Spidey we need to recognize the gifts and curses that 50 years of programming languages has given us … oh, and we should take note about the power/responsibility thing too …

Categories
article lisp

Paul Graham wants me to think he is mad.

Paul's book I’ve been reading Paul Graham’s Hackers and Painters. Published in 2004, it only just found its way off of my reading shelf and into my brain. This Amazon reviewer really sums up the book nicely although I mildly disagree with some of the statements.

Most of the book is a long-winded lecture about how great Lisp is, and about how that is the language of the cool, smart people.

There is very little about painting, it is only briefly mentioned in the beginning.

The first chapter is quite good, then it gets more preaching and more dull rapidly.

Mr Graham is obviously a smart guy and a capable writer. The fact that he was part of a dot-com start up that actually succeeded seems to have gone to his head though. Somehow the fact that he was in the right place with the right idea at the right time enables him to declare Lisp as the uber language, and everybody who doesn’t see that is a dullard?

The title suggests a book which is whimisical and fun. This book is a preachy diatribe by a pompous hacker who things he has the proper world-view for everyone.
— Kevin Stokes

But to give Paul his due he covers some excellent topics. One of the most intriguing ones is the third chapter about thinking the un-thinkable. The suggestion is that by thinking the un-thinkable you will enter a new head-space where perhaps you can make a concerted difference to yourself or others. When I read it, I thought: “I like this idea, I might try it out”. A few more chapters passed and he is talking about Lisp (which I will return to shortly) and I’m thinking: “I’m bored. Where’s my unthinkable thought got to?”. I thought really hard and I got one: “Paul Graham is mad”. Plain and simple. As instructed by Mr Graham I started to explore this idea right away to test its validity.

  • If Paul had a mania what would it be?
  • Where should we look for manifestations of this mania?
  • Will trying out Lisp make me as mad as I perceive all the other people that use it to be?
  • Am I mad and if I am would I be able to answer this question?

And I came to the conclusion that Paul Graham is not mad. Sorry folks. It’s just not true. However, the majority of his un-thinkable ideas (at least in this book) all seem to originate from a single perspective point (you get these in art too I understand!) that choosing Lisp allowed him and his colleagues at Viaweb to produce something others could not. Which is in itself a remarkable statement if it is as true as he suggests. So I thought I’d have another try at Lisp. I tried it once before and wasn’t totally turned off by the idea I just never really got going.

Now don’t get me wrong. I’ll not be trying it just yet. This is just a warning you understand, especially since I wouldn’t want Paul to think that he’d succesfully goaded me into it when he said:

… but I don’t expect to change anyone’s mind (about Lisp) over the age of 25 …

I reserve the right to not let Paul Graham into my head and eat my brain. It’s mine and I’m keeping it mine until I decide otherwise.

One of the cricisms of Lisp is that it doesn’t have very good library support. A little investigation into Unit testing frameworks and MySQL wrappers seemed to bear out what the Reddit development team are saying.

What makes Lisp so much greater (it seems) is that data and program are inter-changeable in as much as you can treat pieces of program like they’re data and vice-versa. And it’s difficult to conceive of a programming language that has the two concepts so fully inter-twined. Reflection is a way of achieving it but in my view reflection is evil because it makes compiler optimisations and function call traceability harder. These two arguments don’t apply to Lisp so Lisp wins again. It is partly because Lisp has all those brackets that it is so powerful.

And so we link into another one of Paul’s un-thinkable ideas which is to design the programming language of the future. His belief is that by imagining what we will want we can make this language today. Anyone can do it. And probably either has or will, we just don’t know it yet. He believes that this language will be optionally OO, with very few axioms, and support something like macros. Smells like Lisp to me. Change the meat on the barbecue Paul.

I refuse to believe that Lisp is the future. It would be quite extraordinary and quite exciting if it were to become so, but my crystal ball says no-way padre. But it is one of the languages in the evolution of languages that has played a significant role. And I do believe it has more to offer. Its time will come again and some spark will incorporate the final pieces of high-hanging Lisp fruit into the language of tomorrow.

It’s just that we’ll be able to do it without having a permanant speech impediment. Thhhorry Paul.