epistemologic

Amit Rathore’s blog about software development and project management

Archive for the 'lambda' Category


More on Lisp syntax, and language extensions

Posted by Amit Rathore on February 16, 2007

Following my recent post on the topic, I thought of one more thing that the syntax of Lisp allows you to do. Being homoiconic, and the fact that code manipulation is so simple (it’s all lists), layering on “language extensions” becomes possible. For example, if Betty Programmer realizes that OO is a great way to design and write code but that Lisp by itself doesn’t provide an OO facility (there are no “class” constructs, no inheritance etc.) - she doesn’t need to despair.

She can write code to add an OOP system to the language. Yes, this means Lisp really blurs the distinction between the language designer and the programmer. In other words, while it’s fairly obvious that Lisp is very well suited to writing DSLs, it is also possible to fundamentally extend the language as well - like adding an OO system, or pattern-matching, or logic-programming (ala Prolog).

Now, obviously, I’m not proficient enough yet to do anything of this sort. But, as I said before, it is my intention to learn :)

Lisp. A language where being meta is something worth thinking about.

Posted in code, lambda, languages, lisp, meta | 3 Comments »

Lisp syntax, and when code is data

Posted by Amit Rathore on February 14, 2007

Like I said earlier, my friend Ravi introduced me to Lisp several years ago, but it has taken me many years to really want to learn it well enough. I’ll write about my reasons in another post. In any event, at the beginning of this year, I started to pick it up again, promising myself that I’d be serious. This time. So far so good.

I think I’ve started to grok one of the core ideas of Lisp. I had always read that the syntax of Lisp was one of its strengths. And I had always struggled with that idea, knowing it was important, yet was quite unable to really put my finger on it. I think I’m closer to it today.

If you had to create a programming language to write programs that wrote programs (as in, say DSLs) - what design choices would you make?

For one thing, you’d have to be able to generate and manipulate (walk parse-trees, compare and transform nodes etc.) code as though it were just another data-structure. Right? OK, so the code that was being generated would look like and behave like data.

You would then create an EVAL function that could run the generated code. Maybe your generated code would in turn produce generated code, so to keep things easy and simple, your language syntax would be the same as that of the generated language. In other words, you’d end up with a homoiconic programming language. Finally, you would bootstrap your language processor and arrive at your final metacircular evaluator.

To recap, this language would have syntax that looked and behaved like data and because of it could generate and manipulate that data, which itself could be code. What would this data structure look like? One obvious choice for this is a tree (because of parse-trees). If you think about it, XML is just like a tree. But it’s kludgey. What we want is something like XML but without all the cruft. For example -


<program>
	<function name=\"add_to_stock\">
		<param name=\"counter\" />
			<call_function name=\"increment\">
				<argument value=\"counter\"/>
			</call_function>
	</function>

	<function name=\"remove_from_stock\">
		<param name=\"item\"/>
			<call_function  name=\"decrement_from_stock_file\">
				<argument value=\"item\"/>
			</call_function>
	</funtion>
</program>

The syntax is truly disgusting, but useful - especially if you need to programmatically generate it. Let’s now try to make it easier for humans, too. I’m going to remove the ‘program’ tag, because all this stuff is code. I’m going to then change from XML tags to simple ‘(’ and ‘)’ without the names - and make an assumption - the first word that appears is always a function call. Except for define - which I’ll use to denote a definition for a function. I’ll also lose the XML attribute names, assuming that words that follow the function name are always parameters (unless it’s a code block itself - which would get evaluated first). So, we’re left with -




(define (add_to_stock counter)
    (increment counter))

 (define (remove_from_stock item)
    (decrement_from_stock_file item))



Where does this leave us?

It’s the same exact XML syntax, but it’s just a bit modified and has a few rules thrown in. Importantly, it’s still as easy to generate as XML. It’s just a list of lists of words. As in, a unit of code in this format would always start and end with parenthesis, and they would enclose either a bunch of zero or more symbols, or other lists.

In fact, a language that was good at list processing and had an eval function would probably do a really good job with this stuff!

Posted in code, lambda, languages, lisp, meta | 2 Comments »

Beyond objects - I

Posted by Amit Rathore on February 9, 2007

… It’s in words that the magic is–Abracadabra, Open Sesame, and the rest–but the magic words in one story aren’t magical in the next. The real magic is to understand which words work, and when, and for what; the trick is to learn the trick.
… And those words are made from the letters of our alphabet: a couple-dozen squiggles we can draw with the pen. This is the key! And the treasure, too, if we can only get our hands on it! It’s as if–as if the key to the treasure is the treasure!

John Barth, Chimera

It’s a copy of a quotation that appears in The Structure and Interpretation of Programs. It speaks to the fact that if you know the name of something, as in a way to refer to it, then you have control over it. Like functions or closures for instance. If you can refer to it by name, you can tell it to someone else. Or pass it to another function. You can remember the name, so you can speak it when you’re ready. When the context is right. Like when all the variables, objects, and functions have aligned.

The idea of metalinguistic abstraction is a fundamental one. It’s a bottom-up way of thinking about your problem-space, and figuring out primitives and operations on those primitives. Rather than trying to build a system that satisfies a particular set of constraints in the given problem-space, the idea is to build a way to express more complex concepts using those very primitives and operations. That way, changes to the system can be made by changing higher level constructs - and going further down the layered stack of abstractions as needed, depending on how fundamental the changes are. This way, changes (or any new set of constraints) can be handled in a more clean and elegant fashion, and the entire system benefits automatically by a change made at a lower level.

If this sounds like building what these days is called a domain-specific language (DSL), then sure, but it is not a new way of doing things. It is however, possible to do a lot of this stuff easier in “enterprise-type” scenarios, because of a larger acceptance of more dynamic languages. Like Ruby, for example. It isn’t particularly easy to write software this way - it involves a change in the way most of us were taught programming. Everything is not imperative any more, code doesn’t have to be “written” before it runs, lines between data and code begin to blur. On that last point, what is a closure? Is it data or is it a procedure? It’s sometimes one, sometimes the other, and occasionally both, and indeed, sometimes it is neither. Here’s an example -


def create_coord(x, y)
Proc.new { |selector|
if selector == :x
x
elsif selector == :y
y
end
}
end

c = create_coord 10, 20
puts “X is ” + c.call(:x).to_s
puts “Y is ” + c.call(:y).to_s

So, the question here is, what is c? Is it data? Or is it code, that does something? Here, c is an object that represents a cartesian coordinate, but without any explicit data elements like variables or attributes… so, what is it?

Note - This is Ruby code, but a different language, (like Lua, for example, that has syntactic sugar for things like keys on a hash table) could make it unnecessary for the call(:symbol) syntax and instead, just calling x and y would translate it to a call on the object with the given method name.

The point, however, is that there are more ways to think about abstraction than just OO, and to paraphrase Paul Graham, some of them can transcend objects. The bottom-up approach itself can be implemented using plain objects and OO thinking, but there are other ways which can make for some powerful expressablilty. The code above approaches functional programming, and I’m interested in scaling that model to build large systems from pure or near-pure functional constructs. I’m nowhere close to being proficient in writing software this way, but it is my intention to learn.

Posted in code, design, lambda, lisp, meta | 2 Comments »