June 09, 2006
META Insanity

I'm beginning to wonder if maybe Henry Baker is insane.

The first sentence of his Pragmatic Parsing paper is “Lisp has traditionally been a language that eschews complex syntax.” I would add “So hold on to your hats!”, but maybe I don't read between the lines well.

Look at this example from the paper:

Below is a parser/transformer for Common Lisp real numbers [Steele90,22.1.2].

(deftype sign () '(member #\+ #\-))

(deftype expmarker () '(member #\e #\s #\f #\d #\l #\E #\S #\F #\D #\L))

(defun parse-number (&aux x (is #\+) id (i 0) dd (d 0)
			 fd (f 0) (nf 0) (es #\+) ed (e 0) (m #\e))
  ;;; Parse CL real number according to [Steele90,22.1.2]
  ;;; Return 2 values: the number and a reversed list of lookahead characters.
   [{[@(sign is) !(push is x)] []} ; scan sign.
    $[@(digit id) !(setq x nil i (+ (* i 10) (ctoi id)))]	; integer digits.
    {[!id #\/ !(push #\/ x)	; "/" => ratio.
      $[@(digit dd) !(setq x nil d (+ (* d 10) (ctoi dd)))]]	; denom. digits.
     [{[#\. {!id !(push #\. x)}	; decimal point.
	$[@(digit fd)
	  !(setq x nil nf (1+ nf) f (+ (* f 10) (ctoi fd)))]] ; fract. digits.
      {[{!id !fd} @(expmarker m) !(push m x)	; exp. marker.
	{[@(sign es) !(push es x)] []}	; exponent sign.
	$[@(digit ed) !(setq x nil e (+ (* e 10) (ctoi ed)))]] ; exp. digits.
  (let ((sign (if (eql is #\-) -1 1))
	(ex (if (eql es #\-) (- e) e)))
    (values (cond ((or fd ed) (make-float m sign i f nf ex))	; see [Clinger90]
		  (dd (/ (* sign i) d))
		  (id (* sign i))
		  (t nil))

We first note that this half-page function is only slightly longer than the grammar for numbers given in [Steele90,22.1.2], and is only slightly less readable

That is one META atrocity. Here's the grammar in CLtL to which he's referring, see for yourself:

cltl2 grammar for numbers

If you think that there's a slight difference in readability then something is terribly wrong with you.

What kind of mind would even choose to highlight length and readability in the comparison between the two? The META grammar/parser is 3x as long and is a goddamn mess. Focus on the fact that it's actually executable—that's the big win.

Next: Hey, maybe iterators aren't so bad either...

Posted by jjwiseman at June 09, 2006 11:14 AM

I remember reading this paper and thinking the same thing.

Posted by: Geoff Wozniak on June 9, 2006 02:05 PM

Bwaha. You gotta love the one-letter &aux lambda list parameters.

Posted by: Andreas Fuchs on June 10, 2006 01:51 PM

I had the same reaction as Geoff and you, John. It was interesting to see how much you could actually get Lisp to do in terms of a DSL with non-paren syntax, but I was hard pressed to think it was an example I'd want to follow.

Baker is a pretty smart guy, though, so perhaps this was a moment of temporary insanity?

Posted by: Dave Roberts on June 12, 2006 01:10 PM

Man, what are you people talking about

META is my favorite way to write parsers

(I would not write the one he did, though)

Posted by: dash on June 12, 2006 07:19 PM

Yep, same thoughts here, when I read that paper some years ago. If the META code is considered better, there's something seriously wrong with the metric used.

Posted by: michaelw on June 14, 2006 12:37 PM
Post a comment

Email Address:


Unless you answer this question, your comment will be classified as spam and will not be posted.
(I'll give you a hint: the answer is “lisp”.)


Remember info?