Lisp in Perl

Makes you wonder why you couldn't just write a Lisp that would "compile" to Perl. It would be instructive and fun.

Edit: it's been done in Ruby.

Edit 2: a serendipitous link to the same in Python. Freaky.

What makes Lisp great?

Of all the languages out there, Lisp is the one that seems to have the most proponents who sound believable. Occasionally I think I should learn some of it - then I bounce off what to me are always the stopping points: I have a hard time with the radically different vocabulary, I don't like capital letters, I miss CPAN like childhood innocence, and all this - pathetically - is enough to stop me.

So I decided to check what other people think makes Lisp great, and put that into Class::Declarative if possible. But when you get down to it, Perl already does a lot of what makes Lisp great, it turns out. (The closure epiphany I had in January is what got me started on this path in the first place, after all.)

Paul Graham lists nine new ideas that Lisp embodied: conditionals, first-class functions, recursion, dynamic variables, garbage collection, programs as expressions (i.e. functional programming), a symbol type, a code notation that is a tree of symbols, and the whole language available at all times. Of those, the first three or four are now universal, and the first five unambiguously part of Perl. The sixth is mostly covered by Perl and can be simulated with anonymous subroutines in cases where it's not covered.

That leaves the symbol type, a code notation that is accessible to the program, and the whole language available at all times. I'm not terribly interested in the symbol type, because it's a performance issue (testing for equality using the symbol handles instead of checking string contents); I'm really interested in what makes Lisp more expressive than other languages, at least for those versed in it.

Moving on to several sources, "Lisp is a programmable language", meaning that Lisp can easily write Lisp code in order to provide higher-level semantics for a given domain. I think this is getting closer to the crux of the matter. Due to Lisp's minimal syntax, its control structures are all functions, and so you can easily extend the language to suit your domain. That, plus Lisp's interactive nature - the way a Lisper effectively enters into a dialog with the language while evolving new semantics - make Lisp unique, or at least partly unique. (Here is another good presentation of this notion.)

Python has considerable interactivity, of course, and the introspection that Lispers find so useful. But I've never had much luck with that mode. I find it far more instructive to break things down into unit tests in the CPAN module paradigm, and work out semantics that way - although I can certainly see how an interactive data inspection facility would really speed the process in many cases (actually, it would make some things possible that aren't any other way.)

Perl is supposed to make easy things easy, and hard things possible. An interactive data facility would be a great addition to the language. Well - I suppose the Perl debugger already does this, to a certain extent, but the Perl debugger has always made my brain hurt.

The Lisp macro system and quasiquotation are powerful facilities making it easy to extend the structure of the language; a Lisp macro is a program that writes other programs that perform the ultimate tasks. Class::Declarative is most definitely moving in that direction; my macro system will be equivalent to Lisp's (I think) and nearly as terse as quasiquotation. More on that when I've got something working.

I'm left with the following chief advantages of Lisp: introspection at all levels, and interactivity allowing multiple approaches to new semantics. And I'm forced to admit that at the moment, Class::Declarative is not doing this - but could, if it grows more in the direction of semantic programming.

On paper, I've been exploring some possible approaches to realistic semantic programming; it appears that the key insight is recognition. That is, matching. If I posit a given structure for the world, then allow a matching engine to tell me how the world can be made to match that structure, then I've parsed the world, or recognized some structure in it. That's really what semantics is.

Here's an example. I want to write an invoice. I create an "invoice" structure. The Lexicon looks up what an invoice is, and fills in some structure as follows:

invoice
 customer {{index customer}}
 data items (description, price, unit, subtotal)
 {{.assert count(items) > 0}}
 total "{{select sum(price) from items}}"
 currency "{{index currency default USD}}"
 {{.section comments}}
 comments
    {{@}}
 {{.end}}

This is still pretty crude, but effectively we can scan the template to see whether all the information is available that we need for a full invoice. Some sort of interactive process will allow me to fill in what's missing, and some other specification not shown here will allow the invoice to be stored. That part's probably some sort of workflow environment. Once defined, the invoice can be expressed using a template to produce PDF or a Word file, and attached to an email. These actions are certainly workflow.

The point is that this is semantic programming - I define an invoice, the environment knows what an invoice is, and we interact to define the case. It's fuzzy in my mind, but I'm getting there.

Note that some of the fields in this example (the index fields) are expectations that prevent the object from being fully specified until they are fulfilled. The same applies to the assertion. However, the select field is simply a calculated field that doesn't require - in fact, doesn't support - an interactive assignment of value.

That calculated field gives us something like the capabilities of Excel, by the way. It would be instructive to be able to build a full spreadsheet in a system like this.

Why Perl?

Occasionally I'm beset by the worry that I've chosen Perl as the basis for all this development. Wouldn't some other language be a better choice?

All I can say in my defense is that my brain seems to work better with Perl for some reason. It's not that I've done a great deal of work in Perl - I've written more lines of C and Tcl. It's not that I have no exposure to other languages - I've worked in Python and Scheme. And while I enjoy the joke that Perl is a write-only language as well as the next programmer, still - when I look at my own code written in Perl, I can read it more easily than my own code, let alone that of others, in other languages.

Then there's CPAN. Oh, sure, half the stuff on CPAN is alpha-quality just-off-the-ground stuff, but oddly enough, it's usually enough to get me off the ground on a given project. Then, after I've got something halfway done, I can rewrite the CPAN modules that weren't what I wanted, and get the rest of the way.

At the end of the day, all programming is about semantics. You are taking the inchoate space of possible meaning, and narrowing it down to the meaning that gets you where you want to go. I find it easy to do that in Perl, for whatever reason.

Rebuild complete

I've been doing some kind of neat stuff with unit testing in the Wx::Declarative domain, although timing makes the tests kind of brittle - sometimes you're testing a condition before everything in the tested process has set things up, so you always have to remember to wait a little bit for applications to start, stop, etc. But Wx is working again! So there's that.

And I've been working a little more with it. It occurs to me that you could set up a runtime modification thing using the Wx facilities pretty easily - that and a command line and runtime object editor, and ... you got a lot of what makes Lisp so cool, but in Perl.

Food for thought.

Score one for unit testing

I'll tell you, having extensive unit tests written that the system already passed before this major overhaul makes me ... let's put it this way. It makes it possible to do refactoring like this. I would definitely have lost hope without my unit tests, and this project would be another dead one. Instead, I'm taking the old unit tests, dropping them into the directory, and letting the unit tests quickly and easily find the places in the code that need attention.

I've almost got everything working again. Incroyable!

Parsing works!

OK, so my parsing unit test passes 139 individual tests having to do with all aspects of tokenization, parsing, and building of nodes and nodal structure. I'm independent of Parse::RecDescent and Parse::Indented now, and I'm entirely using Class::Declarative::Parser objects to parse everything.

I still have a little work to adapt the existing classes to their new non-XML::xmlapi existence, but that seems to be going well. So in a couple of days, I guess I'll be starting templates, with a much more satisfactory parse-and-build regime going into the exercise.

Progress!

Milestone: line parser works!

Just to mark the event.

Debugging parsers

This parser subproject is the hardest programming I've done in twenty years. Well, wait - I took Compilers from Kent Dybvig in ... must have been 1995. So fifteen years, anyway, but I don't remember Compilers. That is, I remember Kent, and I remember the class, but I don't really remember the coding. This stuff is stored in a different place in my brain, I think, very intuitive and nonverbal - part of what makes it so exhilarating.

Anyway, debugging recursive descent compilers is hard, because they're declarative in nature. This is actually going to end up being a key insight (no, not hexapodia) - debugging an imperative program is far, far easier than debugging a declarative one, because you can step through what the program is doing. In a declarative program, not only do you not know when or where things are being done, it's exceptionally difficult to interpose a check point.

I wrote a small debug atom for parsers, though - when it's invoked, it always succeeds, consuming nothing, just like \&nothing - but it prints a message.

Using it felt like ... Prolog.

Down the parsing rabbit hole

So I wanted to do parsers, you know, because I'd like to be able to parse SQL statements and stuff? So I got sucked into Chapter 8 of Higher Order Perl, of course, and once I really started getting into it and realizing how much better life would be if I did some stuff different in the basic parser, well, two weeks had passed.

Still not done.

I do have a lot of parser tools done, though.

But my basic approach to parsing nodal structure was naive. First, the idea that a tag will always mean the same throughout the application is naive - a page in a PDF will have to mean something different from a page in a Web site, and yet I still want to use the tag "page" for both meanings.

But secondly, I realized that I couldn't rely on runtime objects to determine parsing structures, and that rankled.

So I'm going to do things differently now, and in a much more flexible manner. I'm removing the dependency on Parse::RecursiveDescent, and I'm making Class::Declarative::Node a primary class instead of using XML::xmlapi (snif).

Each top-level tag will be parsed minimally into a line and a body, and the first word in the line will determine its semantics, as now. But those semantics will already be able to determine the parsing of all lines indented under that tag! In other words, if it wants to use a different parser, it can. If templates should be expressed, they will be. I'm halfway leaning towards everything always being a template, actually.

This scheme, though, allows me to vary the semantics of inner tags, so if I want to use a radically different syntax to express parser rules, for instance, I can, without a lot of twisting or tweaking.

More on this when it firms up. But there will be recursive-descent parser support built right into Class::Declarative from the get-go. If the strength of Lisp is that it has no syntax, let the strength of Declarative be that it has all syntaxes.

Code generation

Ran across a fascinating book online: "Code Generation in Action", by Jack Herrington. Turns out that code generation is something of a concept nowadays, in several different domains. Maybe I'm not so crazy.

The code generation in the Class::Declarative framework is all in Class::Declarative::Semantics::Code, which seems reasonable. It could doubtlessly be extended in some way - I'd particularly be interested in a way of defining new code generators in a plugin manner. Not sure how best to organize that.

Mapping

Consider this. A macro expression is a one-way street; given a macro instance, the macro engine expresses it as more ramified code, possibly affected by the environment, or parameters.

A more powerful macro engine could define a mapping between two structures, whereby a change in either could be reflected as a change in the other. For example, a mapping between the graphical boxes on a diagram and the underlying database could be set up that could modify the screen when the database was changed, and write (the significant) changes to the database when the screen image was manipulated.

This would be the equivalent of a mapping in cognitive science, the syntactic/semantic mapping we use to talk about how language expresses concepts. Or the same as the analogies Douglas Hofstadter uses to talk about ... everything.

A mapping in a declarative tree would look superficially a lot like an XSLT program. The only difference is that a mapping would remember where its results were, and could act as the trigger described above.

Another example: we've already got magic variables that look to a GUI field, for example, for reading and writing. An explicit mapping structure could define that in the language instead of just in the code; we could define this sort of mapping in our programs. This could be used to set up Excel-like functions in a spreadsheet. Or not in a spreadsheet if you don't like grids - just set up a dataflow program. (TODO: think about that a little more.)

So the to-do list for macros is:

• !tag defines a one-way map to a virtual tag. It expresses in place during built, and stops.
• !!tag defines an active one-way map; it expresses in place, but rebuilds whenever one of its parameters is changed (or potentially does; we could probably specify some active and some one-time parameters somehow).
• An explicit macro or template tag could also match specific parts of the tree, specify assertions about its structure that must be met, and coordinate expression in multiple points.
• A mapping would define that in two directions in some as-yet-unspecified manner.

The basic ones are going to be necessary to make PDF::Declarative make any sense for real-world use, because they allow us to specify a PDF structure that is parameterizable, say, with variable text. Then we can use PDF::Declarative to build a template that can be used again and again (e.g. as an invoice template, etc.) Do that, and my test case will be complete: I want to use PDF::Declarative to generate my translation invoices.

PDF::Declarative

The PDF::Declarative class being a wrapper around PDF::API2 (at least currently), I went looking for good examples, and found a fantastic tutorial by Rick Measham. It took some work and some extra functionality added to Class::Declarative (which was of course the point), but I can now generate a PDF equivalent to his tutorial example using PDF::Declarative. This is the code, somewhat abridged, because it contains the text for the PDF:

use Class::Declarative qw(PDF::Declarative);

pdf (displaytitle, encoding=latin1) "mynewpdf.pdf"
 author    "Michael Roberts"
 title     "PDF::Declarative Example 1"
 subject   "Building PDFs with explicitly placed elements"
 keywords  "Declarative PDF generation"
 mediabox  "105mm x 148mm"
 #bleedbox "5mm, 5mm, 100mm, 143 mm"
 cropbox   "7.5mm 7.5mm 97.5 mm 140.5mm"
 #artbox   "10mm, 10mm, 95mm, 138mm"

 page
    graphic blue_box
       fill (darkblue)
       rect "5mm, 125mm, 95mm, 18mm"
    graphic red_line
       stroke (red)
       move "5mm, 125mm"
       line "100mm, 125mm"
    text heading (flow=no, x=95mm, y=131mm, align=right, color=white, font=helvetica, bold, fontsize=18pt)
       Using PDF::Declarative
    graphic background
       stroke (lightgrey)
       circle "20mm, 45mm, 45mm"
       circle "18mm, 48mm, 43mm"
       circle "19mm, 40mm, 46mm"
    box left_column (border) "10mm, 121mm, 41mm, 111mm"
       text (lead=7pt, parspace=0, align=justify, color=black, font=times, fontsize=6)
          Perci ent ulluptat vel eum zzriure feuguero core consenis adignim...

       text (align=center, font=helvetica, bold, fontsize=6pt, color=blue)
          Enim eugiamc ommodolor sendre feum zzrit at. Ut prat. Ut lum quisi.
     
       text (align=right, font=times, color=black, fontsize=6pt)
          It augait ate magniametum irit, venim doloreet augiamet...
     
    graphic
       image "54mm, 66mm, 41mm, 55mm"
          jpeg "Portrait.jpg"

    box right_column (border, dash=2 2 1 2, color=blue) "54mm, 64mm, 41mm, 54mm"
       text (lead=7pt, parspace=0pt, align=justify, indent=5pt, fontsize=6pt, bullet=B7)
          Orpero do odipit ercilis ad er augait ing ex elit autatio....

Well, one correction: I haven't implemented bullet points yet.

Again: the above is a complete Perl program, and it generates a valid PDF file with justified text in columnar boxes. With a few extensions to the existing code, I think it's going to be just about time to release it into the wild, my first semantic module to qualify.

Current calendar time invested: 11 days. I think about a month would be necessary to do PDFs right - probably far more to do them right, but "good enough" in a month is pretty fast work. Fast enough I haven't lost interest before finishing something useful.

PDF::Declarative

Man, I started PDF::Declarative two days ago, and nearly have something that can do the PDFs I want. Turns out text layout is hard - who knew? But building declarative wrappers for new domains is relatively easy, given good example code.

So I'm really quite happy about the declarative framework; it's making me a faster, better, more productive programmer, and that's all I really need it to do.

An interesting semantic domain at some point would be the generation of new semantic domains... Speeding up the process of speeding up the process should, um, speed up the process.

Dialogs, fields, and magic variables

So I've obviously been spending too much time with this, but I added magic variables to Class::Declarative today, and used them for text controls in Wx.

A magic variable is one for which a handler is registered with the context. When we read or write that variable in the context, our handler is called. That means that code can get or write field contents just by referring to the field as the variable it's tied to - and you tie a field to a variable just by naming it.

So the wxPerl dialogs.pl sample is this code:

#!/usr/bin/perl
#############################################################################
## Name:        samples/dialog/dialog.pl
## Purpose:     Dialog wxPerl sample
## Author:      Mattia Barbon
## Modified by:
## Created:     12/11/2000
## RCS-ID:      $Id: dialog.pl,v 1.4 2004/10/19 20:28:13 mbarbon Exp $
## Copyright:   (c) 2000 Mattia Barbon
## Licence:     This program is free software; you can redistribute it and/or
##              modify it under the same terms as Perl itself
#############################################################################

use Wx;

package MyApp;

use strict;
use vars qw(@ISA);

@ISA=qw(Wx::App);

use Wx qw(wxDefaultSize wxDefaultPosition);

sub OnInit {
  my( $this ) = @_;

  my( $dialog ) = MyDialog->new( "wxPerl dialog sample",
                                 wxDefaultPosition,
                               );

  $this->SetTopWindow( $dialog );

  $dialog->Show( 1 );

  1;
}

package MyDialog;

use strict;
use vars qw(@ISA);

@ISA=qw(Wx::Dialog);

use Wx::Event qw(EVT_CLOSE EVT_BUTTON);
use Wx qw(wxDefaultSize wxDefaultValidator);

sub new {
  my( $class ) = shift;
  my( $this ) = $class->SUPER::new( undef, -1, $_[0], $_[1], [250, 110] );

  # $this->SetIcon( Wx::GetWxPerlIcon() );

  my( $ct ) = $this->{CELSIUS} =
    Wx::TextCtrl->new( $this, -1, '0', [20, 20], [100, -1] );
  my( $cb ) = Wx::Button->new( $this, -1, 'Celsius', [130, 20] );
  my( $ft ) = $this->{FAHRENHEIT} = 
    Wx::TextCtrl->new( $this, -1, '32', [20, 50], [100, -1] );
  my( $fb ) = Wx::Button->new( $this, -1, 'Fahrenheit', [130, 50] );

  EVT_BUTTON( $this, $cb, \&CelsiusToFahrenheit );
  EVT_BUTTON( $this, $fb, \&FahrenheitToCelsius );

  EVT_CLOSE( $this, \&OnClose );

  $this;
}

sub CelsiusToFahrenheit {
  my( $this, $event ) = @_;

  $this->{FAHRENHEIT}->SetValue( ( $this->{CELSIUS}->GetValue() / 
                                   100.0 ) * 180 + 32 );
}

sub FahrenheitToCelsius {
  my( $this, $event ) = @_;

  $this->{CELSIUS}->SetValue( ( ( $this->{FAHRENHEIT}->GetValue()-32 ) / 
                                180.0 ) * 100 );
}

sub OnClose {
  my( $this, $event ) = @_;

  $this->Destroy();
}

package main;

my( $app ) = MyApp->new();

$app->MainLoop();

# Local variables: #
# mode: cperl #
# End: #

In the Wx::Declarative framework, that becomes this:

use Class::Declarative qw(Wx::Declarative);

dialog (xsize=250, ysize=110) "Wx::Declarative dialog sample"
   field celsius (size=100, x=20, y=20) "0"
   button celsius (x=130, y=20) "Celsius" { $^fahrenheit = ($^celsius / 100.0) * 180 + 32; }
   field fahrenheit (size=100, x=20, y=50) "32"
   button fahrenheit (x=130, y=50) "Fahrenheit" { $^celsius = (($^fahrenheit - 32) / 180.0) * 100; }

And it works, as of right now.

Wx::Declarative back where I was

Well, I've successfully factored the Class::Declarative out of Wx::DefinedUI (which is dead, long may it live) and I'm back to having all the stuff work that I had working last week. (!)

Going forward should be way easier now, and the hard stuff is factored out and unit tested so I can't break it as easily, but I feel oddly as though nothing had happened for a week. Except, of course, Class::Declarative is on CPAN now, which is very cool indeed.

So this is what works: code/closures, events (those are the core semantics), buttons, menus, message boxes (hardcoded text only), frames, sizers, dialogs. Next up is the status bar. Then I set out into serious wilderness by subclassing a window for the frame's client. Yikes!

Some thoughts circling back to semantic programming now

OK. So this declarative style of programming can be seen as the systematic laying out of the semantic structure of the program at the same time we are building the code. I'm a little worried that this structure is still very thin (that is, the extremely complex ramifications of meaning that come along with human understanding of a program are missing in this structure), but it's still a beginning.

Let's consider this: we could see the Class::Declarative structure as a sort of prototype. But knowing sufficient amounts of semantics for any given class, we could take a working structure and "compile" it into a pure-Perl structure that doesn't depend on Class::Declarative at all. In fact, we could compile it into any language for which we knew how to express the semantics of the structure.

This is important. This is what we will end up doing much, much farther down the road.

As a more proximate goal, this is what I was fumbling towards in January. I read January's posts and they seem sort of naive. I think that bodes well.

Let's posit a set of semantics that talks about databases, PHP code, Web pages, and AJAX. That's what sproggler is talking about. This declarative-plus-semantic framework would be the backbone of that system, and it could express itself using templates of some kind.

These templates are symbolic units. Remember symbolic units? They connect semantic units (the nodes in a Class::Declarative structure) with syntactic units (the pieces of code we compile), and they are mediated by templates of varying degrees of abstraction. So at some point in the very near future, we're going to want to think hard about them.

Parse::Indented on CPAN

Bit by bit, I'm establishing a useful toolset here.

I've been spending too much time today in organizing the unit tests for Class::Declarative. Test-driving programming has a higher initial threshold, but once you get the framework all set up, it really starts to take shape.

Anyway, Class::Declarative is parsing properly now; you'd think this would already work, but I spent some time generalizing the semantic framework to make it easy to build new semantic domains. I think this is really going to pay off in the medium term.

Class::Declarative

I'm splitting the declarative-programming part out of Wx::DefinedUI. There are just so many areas I can think of where the declarative paradigm will be so useful!

Data declaration (tables and so forth). Testing! Other messaging frameworks like POE or Moose. And, yeah, semantic programming.

I've literally been thinking about this in one form or another for over twenty years. This is the first time I can see an actual way to get it implemented, dammit, so I can use it.

Anyway, refactoring the code is cleaning it up a lot. I always get the feeling if I just refactored enough everything would be a one-liner.

Closures in Perl

So I've been getting deeper into Perl lately. I wrote a little IRC bot class (Bot::NotSoBasicBot) and during the course of that, found myself writing an event queue that took anonymous subroutines to be run at a scheduled time. Only after doing that did I realize that anonymous subroutines in Perl are closures.

That was something of an epiphany. I took a Scheme class from Dybvig, sure. So I had been exposed to the concept of closures. But not until now did I really comprehend them or really realize what they're for.

Now I'm realizing that Perl is a much, much more powerful language than I ever gave it credit for. As I get deeper into Wx::DefinedUI, I'm pushing my own envelope, building code generators and all kinds of things. I feel as though this programming hiatus of the past few years really allowed me to approach the topic with a fresh eye.

Wx::DefinedUI

For quite some time (like, years) I've toyed with the possibility of defining GUIs under wxWidgets (in Perl, Wx, or in Python, wxPython) by using a sort of pseudocode decorated with actual code to execute the meat of the program. This year, the Muse has accepted my application, and I've started on Wx::DefinedUI in Perl.

To do this, I first managed to get past the hump that's always stopped me in the past: syntax. Bear with me, this is important.

See, whenever I start brainstorming about a new way to reorganize programming, I first scratch out a bunch of data structures in pseudocode, then I realize it's hard to implement that stuff. Then I run aground. For I while I thought XML would help, but no, XML is also too hard to type. This is what killed MagnifiCat, it's what killed the semantic programming of last year (earlier posts on this blog), and it's what killed the Web programming framework I started over the holidays.

But early this year, I got back to Wx. And I looked at the structure of one of the demo programs, and it looks like this:

use Wx::DefinedUI qw(-filter);

dialog (resize) "Wx::BoxSizer"
size (box, v):
  size (box, h) [1, GROW]:
     button (id=OK) [0, ALL, 10] "Close window"
     button [0, 0] "Button 2"
     button [0, TOP BOTTOM, 5] "Button 3"
  space [10, 10, 0, GROW]
  size (box, h) [1, GROW]:
     button [1, ALL, 5] "Button 1"
     space [1, 30, 1, 0, 0]
     button [1, GROW ALL, 5] "Button 2"
     size (static, v) [2, GROW] "Wx::StaticBoxSizer":
        button [1, GROW ALL, 5] "Button 3"
        button [1, GROW ALL, 5] "Button 4"

That's it. Granted, that code doesn't do anything, it just demonstrates the use of box sizers, but there are two points I want to make about it.

First, it provides a detailed, extremely readable, and yet still parseable, overview of the application. If we provided IDs for all those buttons and wrote code to be called on click, we'd have a real application, and one that we could understand with no further ado.

Second - and this is important - as of yesterday, it works. I decided to go ahead and tackle the parsing problem. I looked up Parse::RecDescent and found it good - but then I went ahead and polished up my old XML::xmlapi as a structure manipulation module I can work quickly with, and wrote Parse::RecDescent::Simple to allow parsing of each of those lines. That stuff's already on CPAN, because it's working and stable to the point I need right now.

For parsing of the indentation, I've written part of Parse::Indented. It's not on CPAN yet, because I still want to add a feature allowing embedding of Perl code into my tree. Maybe tomorrow.

The crucial point here is this: I have a parsing framework that lets me use pseudocode to define things, things that will then run. Next step: use that very parsing framework to get back to the Web application framework and semantic programming. It should be easy!

Here's another point, by the bye: publishing early and often keeps the momentum going. I've published five modules to CPAN in the last week. It's heady stuff.