(newLISPer)

Balance those parentheses

2010-07-12T22:50:00.000+01:00

I called this site "unbalanced parentheses" not just because the phrase had a Lisp-oriented slant but also because it hinted at a lightweight, off-the-wall attitude to the subject, rather than a serious analytical perspective. I spent all of 10 seconds thinking of the name while staring at a registration form with a mind suddenly gone blank, and it probably wasn't the perfect choice.

Looking at the logs recently, I noticed that some visitors actually appear to be looking for help balancing their unbalanced parentheses! I suspect, though, that they're not newLISPers, and probably not even Lisp users (who presumably don't need much help in that department anyway, and have their own opinions about editing code - see Greg's post for an interesting discussion). It occurred to me to try and write something about the subject. And it's high time I wrote something - anything - for this site.

The parenthesis is normally employed in written language to indicate something less than essential or subordinate - material that can be omitted without major damage to the sentence. In mathematics and programming, though, parentheses are more likely to be used for organizing selected items into groups or larger entities, and also for controlling the order of evaluation. Like legs, or trousers, they nearly always go around in pairs, so that a left, opening, parenthesis should always be accompanied by a matching right, closing, parenthesis following not far behind.

You know all this, of course.

The problems start when you start using lots of pairs of parentheses. Take this piece of simple mathematics:

(a * (b + ((c * d) / e) - f)

As every schoolboy and schoolgirl knows, to check parentheses in your algebra homework, you read from left to right and count out loud, going up one whenever you see an opening parenthesis, and down one for each closing one. Thus the counting for the above expression would sound like this:

"1 a * 2 b + 3 4 c * d 3 / e 2 - f 1"

and, since you started at 0 but ended on 1, you can conclude that your parentheses are unbalanced. Too many lefts, not enough rights, in this case.

Like me, you can probably do a simple example like this without counting, just by looking at it and mentally matching lefts and rights. But you don't want to have to do this for long Lisp expressions, or expressions that span a number of lines. Your preferred text editor should help you match the parentheses - each editor offers a few great tools, but I've found that few offer everything you want.

A little newLISP script can do the job automatically:

(set 'source-code-list (explode (read-file (nth 2 (main-args)))))
(set 'nest -1)
(dolist (i source-code-list)
  (cond
     ((= i "(")     (inc nest)
                    (print "\n" (dup "  " nest) i))
     ((= i ")")     (dec nest)
                    (print i "\n" (dup "  " nest)))
     ((= i "\n")    (print ""))
     (true          (print i))))

which, when given a piece of source code like this:

(define (mandelbrot)
    (for (y -2 2 0.02)
        (for (x -2 2 0.02)
            (inc counter)
            (set 'z (complex x y) 'c 126 'a z)
            (while (and
                     (< (abs (:rad (set 'z (:add (:mul z z) a)))) 2)
                     (> (dec c) 32)))
            (print (char c)))
        (println)))

outputs something like this:

(define 
  (mandelbrot)

  (for 
    (y -2 2 0.02)

    (for 
      (x -2 2 0.02)

      (inc counter)

      (set 'z 
        (complex x y)
       'c 126 'a z)

      (while 
        (and                    
          (< 
            (abs 
              (:rad 
                (set 'z 
                  (:add 
                    (:mul z z)
                   a)
                )
              )
            )
           2)

          (> 
            (dec c)
           32)
        )
      )

      (print 
        (char c)
      )
    )

    (println)
  )
)

It's a curious and spacious layout not to everyone's taste, but the parentheses line up vertically, so it's easy to see what's going on. You can get even closer to the simple counting idea by replacing the parentheses with snazzy Unicode symbols, producing results like this (which won't look right if your browser isn't Unicode-friendly):

➀define 
  ➁mandelbrot❷

  ➁for 
    ➂y -2 2 0.02❸

    ➂for 
      ➃x -2 2 0.02❹

      ➃inc counter❹

      ➃set 'z 
        ➄complex x y❺ 'c 126 'a z❹

      ➃while 
        ➄and

          ➅< 
            ➆abs 
              ➇:rad 
                ➈set 'z 
                  ➉:add 
                    ➊:mul z z➀ a❿❾❽❼ 2❻

          ➅> 
            ➆dec c❼ 32❻❺❹

      ➃print 
        ➄char c❺❹❸

    ➂println❸❷❶

using code like this:

(set 'level 0)

(define (open-list)
  (print "\n" 
    (dup "  " level) 
    (char (+ (int (append "0x" (string 2780)) 0 16) level)))
  (inc level))

(define (close-list)      
  (dec level)      
  (print (char (+ (int (append "0x" (string 2776)) 0 16) level))))

(dolist (c source-code-list)
    (cond
        ((= c "(")  (open-list))
        ((= c ")")  (close-list))
        (true       (print c))))

This technique is useful for analysing big SXML lists, too.

All this is fun, but you might be thinking that there's a much quicker way to simply find out whether the parentheses are balanced. Why not just count them?

(define (parenthesis-count txt)
     (count '("(" ")") (explode txt)))

(if (apply = (set 'r (parenthesis-count test-code)))
             (println "good code! " r)
             (println "bad code!  " r))

which returns something like:

bad code!  (22 23)
; or
good code! (22 22)

The world, or at least your source code, might well be harmonious and balanced when there are equivalent numbers of left and right parentheses.

But... you're too smart to be easily fooled by this glibness. You know better than I do that none of the code written thus far will operate perfectly on itself, let alone on the sort of code that crazy newLISPers can come up with. Obviously, the parentheses inside the strings are going to upset the counting. And when source code is formatted with comments and documentation markup, it's unlikely that these simple tricks are going to give accurate results. I'll have to analyze source code more carefully.

In my view, one of the few features that newLISP currently lacks is the ability to read its own code into its own nested list format. The powerful list referencing functions such as ref-all and set-ref are unable to operate on source code stored in strongly hierarchical lists or S-expressions, simply because there's no obvious way to convert source to that form. I use a temporary work round, in the form of Nestor (a utility that you'll find mentioned on these pages, although the code is unlikely to work on more recent versions on newLISP). Nestor also adds the colours to the source listings you see here, too, by converting raw code into an intermediate form that can then be converted to HTML with lots of CSS SPAN tags to colourize parenthesis-enclosed strings.

Here's what a piece of source code looks like after Nestor's manipulations:

((("open-paren" "(") 
  ("symbol" "define") 
  (("open-paren" "(") 
   ("symbol" "mandelbrot") 
   ("close-paren" ")")) 
  (("open-paren" "(") 
   ("symbol" "for") 
   (("open-paren" "(") 
    ("symbol" "y") 
    ("integer" -2) 
    ("integer" 2) 
    ("float" "0.02") 
    ("close-paren" ")")) 
   ; ...

Now I can ask for all opening parentheses and obtain accurate references to them. I've put the tokenized and deformatted source in `s-list':

(set 'op-refs (ref-all '("open-paren"  "(") s-list))
(set 'cp-refs (ref-all '("close-paren" ")") s-list))

op-refs
;-> 
((0 0) 
 (0 2 0) 
 (0 3 0) 
 (0 3 2 0) 
 (0 3 3 0) 
 (0 3 3 2 0) 
 (0 3 3 3 0) 
 (0 3 3 4 0)
 (0 3 3 4 4 0)
 ;...

cp-refs
;->
((0 2 2) 
 (0 3 2 5) 
 (0 3 3 2 5) 
 (0 3 3 3 3) 
 (0 3 3 4 4 4) 
 (0 3 3 4 11) 
 ;...

The parentheses can now be counted simply and with more confidence, knowing that strings and comments are not going to give false positives:

(length op-refs)
;-> 22
(length cp-refs)
;-> 22

And now it's possible to see each expression separately. I can work through every reference to an open parenthesis, and for each one, chop the end of the address off to get a reference to the expression as a whole:

(dolist (a-ref (sort op-refs (fn (x y) (> (length x) (length y)))))
    (output-code (s-list (chop a-ref))))

;->
(:mul z z)
(:add (:mul z z) a)
(set 'z (:add (:mul z z) a))
(:rad (set 'z (:add (:mul z z) a)))
(abs (:rad (set 'z (:add (:mul z z) a))))
; ...

This particular code sorts the expressions according to their depth (the most deeply nested first) and then displays them. It's kind of like how newLISP evaluates expressions, I fancy. Each of these expressions could be checked for unbalanced parentheses or dubious syntax, too.

Alternatively, it's possible to examine particular constructions occurring in code. For example, I could look at each use of `set', to check for dodgy assignations:

(set 'setrefs (ref-all '("symbol" "set") s-list))
(dolist (setref setrefs)
   (output-code (s-list (chop setref))))

;->
(set 'z (complex x y) 'c 126 'a z)
(set 'z (:add ( :mul z z) a))

I can also chain these types of queries together, or look for one inside another:

(set 'references-to-while 
    (ref '("symbol" "while") s-list match))
(set 'references-to-set 
    (ref '("symbol" "set") (s-list (chop references-to-while)) match))
(output-code 
    (nth (chop (append (chop references-to-while) references-to-set)) s-list))

;->
(set 'z (:add (:mul z z ) a))

However, I think I'm now barking up the wrong tree. It's relatively easy to find out whether your parentheses are balanced - but it can be much harder to notice when one or more of them are in the wrong position. This is, perhaps, a paradoxical result of Lisp's powerful yet simple syntax. Here's a typical example of what I mean:

(define (test a b)
   (let ((c a)
         (d b)
         (result 0))
     (set 'result (+ c d)))
   result)

(test 2 2)

;-> 
nil

I was hoping to see 4, but I see nil instead. The parentheses are balanced, and the syntax is correct. But one of the parentheses is in the wrong place, and I doubt whether any script or tool could easily identify which one or tell you where it should be located. (Perhaps the mistake is too stupid for that!) Can you see the mistake? And can you imagine a tool or editor that could detect or prevent it happening?

newLISP tackles global warming

2010-03-02T21:50:00.000Z

At Armagh Observatory, they've been keeping records of the weather since the late 18th century, and detailed records since 1843. The datasets, which are freely available to all, via their web site, are considered to be high quality and very useful, suffering from few of the problems that bedevil other sets of weather observations. There are hardly any problems with gaps in the records (which would have to be filled in by a technique that scientists call 'sparse data infill' and which I would call 'making stuff up'). There are no nearby airport runways or industrial complexes that could upset the microclimates. And, because the information is published openly, there's little chance that modifications or corrections can be applied without anyone noticing.

Armagh itself is a smallish town in Northern Ireland, less than 1000 miles south of the Arctic Circle although bathed in the warm currents of the Gulf stream. The name is familiar to most UK residents mainly as the place where, during the 1970s and 1980s, it was possible to witness gun, bomb, and grenade attacks in the streets, symptoms of the long-running conflict between Catholic and Protestant extremists. This was the time of "the Troubles", as they became known.

I decided to attempt some simple analysis of one of the sets of weather records that the Armagh Observatory has posted on its website, using newLISP as my magnifying glass and explorer's machete.

I started at http://climate.arm.ac.uk/calibrated/airtemp/index.html, and downloaded the 'corrected daily maximum temperature' file.

(set 'source-file 
    (get-url {http://badc.nerc.ac.uk/browse/badc/armagh/data/air_temperature/corrected_daily_max_temp/tccmax1844-2004.txt}))

I parsed this into separate lines.

(set 'raw-data (parse source-file "\n" 0))

Looking at the result, there are three different types of line to process. After the initial comment lines, there are either year indicators or space-separated lists of values (in degrees Centigrade) for every month for a particular day. For example, the line starting with "1" contains the maximum recorded temperatures for the first of January, February, March, etc. up to and including the first of December. Lines starting with 29 to 31 contain a few odd-looking entries such as "-999" that indicate that there was no such day for certain months.

("Daily maxmimum temperature at Armagh Observatory compiled and calibrated by John Butler and" 
 "Ana Garcia Suarez and Alan Coughlin, Armagh Observatory, August 2003 " 
 "Reference: Meteorological Data recorded at Armagh Observatory: Volume II - Daily, Monthly and" 

" 1844" 
"     1    1.9    6.2    6.8   16.3   19.2   18.7   17.7   16.7   24.8   15.6   10.3    6.6" 
"     2   -0.2    5.1    6.4   12.0   22.7   16.7   16.7   18.8   23.4   16.1    9.2    6.0" 

"    31    5.3 -999.0   13.3 -999.0   20.0 -999.0   15.3   22.3 -999.0   12.6 -999.0    6.3" ...)

To parse the raw data I used the following code:

(let ((year 0) (values '()) (monthly '()))
    (dolist (line raw-data)
      (cond 
        ((and (< (length line) 6) 
                        (>= (int line 0 10) 1844) 
                        (<= (int line 0 10) 2004))
        ; a year start?
            (set 'year (int line 0 10)))
        ; a data row?
        ((nil? (find "[A-Za-z]" line 0))
            (set 'values (map float (parse line)))
            (when values
               (set 'day (first values))
               (push (rest values) monthly -1)
               ; after 31, start a new month
               (when (= day 31) 
                   (push (cons year (transpose monthly)) yearly -1)
                   (set 'monthly nil)))))))

As usual, my code is a quick hack; ungraceful yet yielding a practical solution. It runs just once, because the resulting data are collected in the yearly list, which is then more efficiently accessed when saved in a file and reloaded as needed:

(save {/Users/me/armagh-data.lsp} 'yearly)

; later: 

(load {/Users/me/armagh-data.lsp} 'yearly)

The data list yearly holds all the data in a simple hierarchical list structure. I used the transpose function to 'flip' the monthly data lists as they were being processed, thus converting the unusual "first day of every month" order into what seemed a more reasonable chronological "month by month" sequence. The data is now in the following form:

(
    (1844 
      (1.9 -0.2 6.7 11.1 11.7 8.9 6.1 6.9 10.3 8.2 8.9  ...
      (6.2 5.1 4.8 6.2 6.2 6.2 4.5 4.5 5.2 4.8 6.7 8.4  ...
      (6.8 6.4 8.2 6.6 3.4 5.7 7.9 11.5 10.4 9.3 8.7 6. ...
      (16.3 12 11.2 10.8 10.7 12.1 14 14.6 17.9 15.7 13 ...
      (19.2 22.7 16.8 16 19.9 17.9 17.1 16.9 15.4 14.4  ...
      (18.7 16.7 20.1 20.8 18.6 20.2 19.1 20.1 19.1 18  ...
      (17.7 16.7 19.2 19.3 16.9 16.8 19.2 19.5 18.6 18. ...
      (16.7 18.8 17.2 18.4 19.9 15.3 16.4 16.8 16.8 18. ...
      (24.8 23.4 20.9 21.6 21.4 20.9 20.4 16.9 18.2 15. ...
      (15.6 16.1 17.3 15.1 13.4 13.3 11.8 14.8 14.9 15. ...
      (10.3 9.2 9.4 8.6 9.4 8.3 8.3 9.4 10 9.4 7.3 8.9  ...
      (6.6 6 6.3 5.6 4.2 5.4 6 2.4 3.5 3.7 3.8 3.2 2.1  ...
    (1845 
      (5 5.8 6.7 9.7 10.2 8.3 6.7 7.8 9.4 10.6 6.7 6.1  ...
      (2.6 6.7 9.2 5.9 7.5 4.5 1.7 4.5 7.5 7.3 5.3 9.5  ...
      (9 9 9.2 6.5 4 2.9 5.5 7.9 8.6 9.7 5.7 4.1 1.8 1. ...
      (15.4 12.9 15.9 15.4 9.6 13.4 15.1 11.2 10.1 9.6  ...
      (16 14.4 12.7 12.7 12.7 10.4 10.4 11.8 12.4 13.9  ...
      (19.9 19.7 14.6 15.8 16.3 16 16.1 16 16.6 18 24.2 ...
      (16.1 18.8 14.7 17.9 17.7 18.1 19.6 18.3 16.4 18. ...
      (17.7 17.3 17.8 18.9 19.2 18.7 18.9 19.5 16.7 18. ...
      (17.6 18.8 18.7 18.2 17.2 15.1 16.5 19.1 20.6 18. ...
      (13.6 12.9 13.4 10.4 11.3 13.4 11.8 12 12.3 12.3  ...
      (12.8 11.9 12.6 11.7 13.9 15.1 11.7 10.9 9.7 11 1 ...
      (8.2 5.7 2.6 7.9 6.6 6 7.1 9.9 8.7 10.4 6.6 5.1 6 ...
    (1846

and so on.

To access the data for a specific year, I can use ref:

(define (data-for-year y)
   (let ((year-ref (ref y yearly)))
       (rest (yearly (chop year-ref)))))

such that:

(data-for-year 1845)

returns a list of 12 lists. And to access data for a specific month, I can use this:

(define (data-for-month month-number year-data)
  ; month-number:  Jan = 1, not Jan = 0 :)
   (clean (fn (n) (< n -30)) (year-data (- month-number 1))))

So I can, for example, find data for February 1900 like this:

(data-for-month 2 (data-for-year 1900))
    ;->
(3.4 3.3 2.8 4.4 3.4 3.3 3.9 1.6 4.9 1.1 2.8 2.4 4.1 4.4 7.9 7.7 7.2 6.3 3.8 6.2 5.7 9.9 11.7 12.8 9.3 6.8 5.1 5.6)

The clean function removes those spurious -999s for February 29, February 30, and February 31.

Another simple function:

 (define (average lst)
  (div (apply add lst) (length lst)))

calculates averages, so I can ask for the average (maximum) temperature:

(average (data-for-month 2 (data-for-year 1900)))
 ;-> 5.421428571

To find years with high average maximum temperatures, I can run the following code:

(for (year 1844 2004)
     (set 'year-data (data-for-year year))
     (set 'month-average nil)
     (for (month 1 12)
          (push (average (data-for-month month year-data)) month-average))
     (push (list year (average month-average)) year-average))

(sort year-average (fn (a b) (> (last a) (last b))))

with the following results:

((1959 14.20715118) 
 (1846 14.12936444) 
 (1949 14.11140297) 
 (1921 13.9449232) 
 (1857 13.88233359) 
 (1945 13.87162442) 
 (2003 13.84484575)
 ...

and so on. If you google the year 1846, you'll find references to the typhoid outbreak that followed the long hot summer, which claimed upwards of 30 000 lives. But that summer of 1959 has been described as a 'benchmark' summer; that special kind of warm and dry golden summer that ageing Brits like to look back on nostalgically when faced with another of the wet and miserable days that they usually see so many of in July and August.

A picture is worth a 1000 words

The plain numeric data is interesting, but I like exploring using visual techniques too.

My first attempts at visualizing the data used the HTML5 Canvas, but for this task I ended up switching back to PostScript. Both have their advantages: Canvas can do semi-transparency, but PostScript can't; PostScript can produce PDFs which are high resolution, and easily converted to other formats. Bear with me for a moment while I define a short library of PostScript functions.

(define (ps str)
  (write-line *buffer* str))

(define (render filename)
  (let ((fname (string (env "HOME") "/Desktop/" filename)))
     (write-file fname 
                (string "%!PS-Adobe-3.1" 
                        "\n" 
                        "%%Creator: newLISP " 
                        (sys-info -2) 
                        "\n" 
                        *buffer* 
                        "%%showpage" "\n"))
     ; on MacOS X, this runs the PostScript to PDF converter 
     ; and opens the resulting PDF file in Preview
     (exec (string "open " fname))
     ; on other platforms, the PostScript file needs to be 
     ;converted with, eg, GhostScript...
     ))

(define (ps-prolog)
  (ps (string {%} (date)))
  ; hack for big paper size
  (ps (string {
%%BeginFeature: *PageSize Default
<< /PageSize [ 5000 500 ] /ImagingBBox null >> setpagedevice
%%EndFeature
  }))
  ; default font
  (ps {/Helvetica-Bold findfont 12 scalefont setfont})
  (ps {1 setlinewidth}))

(define (transform-x x)
   (mul x-scale (add x x-offset)))

(define (transform-y y)
   (mul y-scale (add y y-offset)))

(define (line-to x y)
  (ps (format "%f %f lineto\n" (transform-x x) (transform-y y))))

(define (move-to x y)
  (ps (format "%f %f moveto\n" (transform-x x) (transform-y y))))

(define (begin-path)
  (ps (format {newpath })))

(define (fill-path)
  (ps (format {fill })))

(define (stroke-path)
  (ps (format {stroke })))

(define (set-fill-colour r g b) 
  (ps (format {%f %f %f setrgbcolor} r g b)))

(define (set-stroke-colour r g b)
  (ps (format {%f %f %f setrgbcolor} r g b)))

(define (dot x y r)
  (begin-path)
  (ps (format "%f %f %f 0 360 arc " (transform-x x) (transform-y y) r))
  (fill-path))

(define (text x y d)
  (move-to x y)
  (ps (format {(%s) show} (string d))))

I usually just copy and paste these from script to script, adapting them when necessary to the task in hand. There's a hack in the ps-prolog function to force a very wide paper size. This graph is going to be huge - I'm going to attempt to plot every single data point on this graph.

For colours, I define a simple colour map that goes from red to blue:

(define (generate-colour-list)
    (for (i 0 1 0.001)
        (push (list i 0 (sub 1 i)) colour-map -1)))

and a function that takes a temperature value from between -10 and 35 (they're safely below and above the range of values in the dataset) and selects an entry in the colour map. (I shouldn't hard-wire all these values in, should I?!)

(define (colour-for-temp t)
   (colour-map (int (mul (length colour-map) (div (add 10 t) 45)))))

Now I'm ready to initialize:

(define (init)
  (set '*buffer* {})
  (generate-colour-list)
  (ps-prolog)
  (set  'x-offset 10
        'y-offset 25
        'x-scale 4
        'y-scale 6
        'x-step 0.02
        'start-year 1844
        'end-year 2004
        'graph-width 2000
        'graph-height 400))

and - finally - I'm ready to start drawing.

(init)

; legend
(set-fill-colour 0.0 0.0 0.0)
(text 10 44 {Maximum temperatures recorded at Armagh Observatory, Degrees Centigrade})
(text 10 42 {Monthly averages shown as grey circles})
(text 10 40 {Daily maximum temperatures marked as small dots})
(text 10 38 {Records shown in red/blue})

(set-stroke-colour 0.7 0.7 0.7)

; x-axis
(begin-path)
(move-to 0 0)
(line-to graph-width 0)
(stroke-path)

; y-axis
(begin-path)
(move-to 0 -5)
(line-to 0 (- graph-height 30))
(stroke-path)

; y rules 
(for (y -5 35 5)
     (begin-path)
     (set-stroke-colour 0.9 0.9 0.9)
     (move-to 0 y)
     (line-to graph-width y)
     (stroke-path)
     (set-fill-colour 0 0 0)    
     (text -7 y y))

The way I've set this up, I'm actually adding the graph's 'furniture' by specifying vertical coordinates in degrees Celsius! It's weird, but it kind of makes sense to say "I want this line to appear at the -5° line".

The graph is drawn in two passes, partly because there's no other way to get layering. In the first pass, I'm drawing grey circles to indicate the average maximum temperature for each month. In the second pass, I go back and plot each day's value as a dot:

; first pass; draw monthly average maximums as grey dots
(set 'x-pos 0)
(for (year start-year end-year)
      (set 'year-data (data-for-year year))        
      (for (month 1 12)
           (set-fill-colour 0.7 0.7 0.7)
           (set 'monthly-average (average 
                (data-for-month month year-data)))            
           (set 'y-pos monthly-average)
           (dot  x-pos monthly-average 3)
           (inc x-pos (mul x-step (length 
                (data-for-month month year-data)))))
      (inc x-pos x-step))

; second pass; draw daily maximums
(ps {/Helvetica-Bold findfont 15 scalefont setfont})
(set 'x-pos 0 'hottest-day-so-far 25 'coldest-day-so-far 0)
(for (year start-year end-year)
    ; year markings
    (when (= 0 (% year 5)) 
       ; sometimes, 5 yearly ticks
       (set-stroke-colour 0.8 0.8 0.8)
       (begin-path)
       (move-to x-pos -10)
       (line-to x-pos -12)
       (stroke-path)
       ; year: black
       (set-fill-colour 0 0 0)
       (text x-pos -14 year))

    ; always, 1 year ticks
    (set-stroke-colour 0.8 0.8 0.8)
    (begin-path)
    (move-to x-pos -10)
    (line-to x-pos -11)
    (stroke-path)

    ; get data for year
    (set 'year-data (data-for-year year))        
    (for (month 1 12)

         ; every day
         (dolist (daily-temp (data-for-month month year-data))
            (set 'hottest-day-so-far (max hottest-day-so-far daily-temp))
            (set 'coldest-day-so-far (min coldest-day-so-far daily-temp))
            ; lower alpha for this set
            (cond 
                ((= hottest-day-so-far daily-temp) 
                      (set-fill-colour 1 0 0)
                      (dot x-pos daily-temp 3))
                ((= coldest-day-so-far daily-temp)
                      (set-fill-colour 0 0 1)
                      (dot x-pos daily-temp 3))
                (true
                      (apply set-fill-colour (colour-for-temp daily-temp))
                      (dot x-pos daily-temp 0.5)
                      ))
            (inc x-pos x-step)))
    ; next year
    (inc x-pos x-step))

; finish drawing
(ps {showpage})
(render "graph.ps")

The result is a PostScript image that is easily converted to a PDF image by the Mac's pstopdf program (or by GhostScript or Adobe Distiller). The result is too wide for publication in a typical journal, and strains at the edges of typical web pages. But it's easy to explore the PDF image using Preview or Acrobat Reader.

The PDF is here.

One thing I noticed (apart from the apparent lack of much significant change during the period) is that those averages seem oddly unrepresentative of the actual daily weather. There's no disputing the arithmetic (I hope). And yet, for example, look at the summers of 1870 or 1995: daily temperatures look hot, with many above 25°, but the monthly averages appear cooler.

Every picture tells a story

This type of graphic visualization of a dataset is designed to tell a story visually, the story being, presumably, the one told by the surrounding text. However, it's possible for the author to make the storytelling even more effective by tweaking aspects of the presentation. For example, authors can change or move the axes, adjust the horizontal or vertical scales, introduce colours to influence perception, combine two or more datasets as if they were one, start or stop the graphing at a more 'telling' point in the data, or even combine two or more graphs on a single display to imply connections. For more on this fascinating subject, see the books and writings of Edward Tufte.

I don't have a scientific story to tell, here. Rather, I'm telling a meta-story. I've made a number of small mistakes and inappropriate design decisions in this post (some deliberate, or at least, some I'm aware of, others are accidental). But, given the published and freely downloadable weather data, the code listed here, and - of course - the excellent free and open source newLISP language, it should be possible for anyone to retrace my steps, find my mistakes, and present a more credible or compelling view of the same dataset. I like to think that, if I was a scientist, I'd be happy for that to happen. But how many of us are either willing or able to do the same forensic work for other - and probably much more important - graphical visualizations of specific datasets? Currently the world of climate science seems to be in disarray, with allegations of data tampering, fraud, and much else besides. It appears that we should all be a lot more critical of the way information is presented to us.

Addendum

Thanks to Kazimir, this post was mentioned at Hacker News - and this site had 8000+ more page views than usual that day... :) I was pleasantly surprised that quite a few of the commenters seemed to have understood that this wasn't literally an attempt at serious scientific analysis, despite the teasing headline. It was merely an observation or two from a non-scientific layman about the process of drawing pictures and conclusions from sets of numbers, while at the same time exploring some simple graph drawing using newLISP (rather than proprietary software packages such as Excel or Mathematica).

I'm intrigued by the heavy data compression that's going on in much of the graphs I see on the net. A huge amount of juicy data is squeezed until dry enough to be summarized by a single wavy line. In this particular example I tried to avoid dropping any data points, but the resulting graph is, I freely admit, too hard to 'read'. When you're far enough away to see it, you can't see anything worth seeing.

Kazimir also suggested that I add yearly averages. Easy enough to do, although I'm reluctant to cloud the graph with even more information:

And about this 'average' thing: talking about the average temperature for 'a decade' begs the question of why starting with a year ending with 0 is any better than starting with any other number. For example, why not compare the decade 1853-1862 with 1927-1936? And for that matter, why are we using intervals of 10 years, rather than 5 or 14?

But there's an easy way to answer this particular conundrum:

(for (x 3 20)
   (for (y 0 (- (length yearly-averages) 1))     
        (set 's (slice yearly-averages y x))     
        (if (= (length s) x)
            (push (list (first s) (average (map last s))) results))) 
    (println x { } (first  (sort results (fn (a b) (> (last a) (last b))))))
    (set 'results nil))

    3 (2002 13.74500614)
    4 (2001 13.60712154)
    5 (2000 13.58417734)
    6 (1999 13.56492782)
    7 (1998 13.51859569)
    8 (1997 13.53881651)
    9 (1995 13.44358625)
    10 (1995 13.47582925)
    11 (1994 13.41562109)
    12 (1993 13.33442216)
    13 (1992 13.29284527)
    14 (1846 13.32015829)
    15 (1845 13.2821639)
    16 (1989 13.29859146)
    17 (1988 13.28216522)
    18 (1987 13.24236811)
    19 (1986 13.17982611)
    20 (1985 13.13376373)

which tells us that, for this data set at least, the warmest periods between 3 and 13 years long, and between 16 and 20 years long, were all in the late 1980s and 1990s, but the warmest 14 and 15 year long periods were in the 1840s and 1850s. Change the sorting function to <, and the coldest (or, to be more precise, the least warm, on average) periods were all in the late 1890s. Tentatively, I could suggest that - at Armagh - there was a slight dip in average temperatures towards the turn of the 20th century. and that average temperatures now are equalling and surpassing the early Victorian readings by a tenth of a degree or so. But I said I was trying not to do any science here, so that's enough of that.

Tweeting frequency

2010-01-10T18:00:00.000Z

I enjoyed the blog post by taoeffect/itistoday/greg at Tao Effect Blog; a good story, well told, and full of enthusiasm (increasingly a scarce commodity in online communities). I noticed that there was a slight increase in activity in the newLISP corner of the Twitterverse as a result: up from one or two twitters a week to 12 in one day.

I thought it would be nice to graph the tweet frequency. I added a short function to the Dragonfly Twitter module to draw a simple bar chart - see it here. However, I'm not too impressed with the effect. I'm not convinced that the choice of bar graph is correct either.

What I'm looking for is some kind of 'bar code' type of graph, where each vertical line represents a point in time to mark each tweet, and any increase in frequency shows up as a cluster of lines closer together. I don't know what this type of graph is called, or how to produce it using Google's chart API, though. If it's not possible, I'll think about drawing one using the HTML5 Canvas element. Help wanted!

Update: I wrote a new graph plug-in, using the HTML canvas. It looks more like the bar-code thing now. Opera doesn't draw the text, but it's OK in FireFox, Safari, and Chrome.

Seasonal greetings

2009-12-12T09:17:00.000Z

Seasonal greetings from Unbalanced Parentheses Headquarters!

--- (for (i 0 255) (push (list (rand 250) (rand 250) (rand 250) (max 0.3 (random 0 1))) colour-map -1)) (define (greet text x y) (local (colour) (set 'colour (colour-map (rand 100))) (write-buffer page (string (format {a_context.fillStyle = 'rgba(%d, %d, %d, %f)'; } colour) "\n" (format {a_context.font = '%dpx sans-serif'; } (max 10 (rand 24))) "\n" (format {a_context.fillText ('%s', %d, %d); } text x y) "\n" )))) (set 'page {}) (define (make-canvas nm width height) (write-buffer page (format (string (char 60) {canvas id="%s" width="%d" height="%d"} (char 62) (char 60) {/canvas} (char 62)) nm width height))) (seed (date-value)) (set 'width 800 'height 1200) (make-canvas "a" width height) (write-buffer page (string (char 60) {script type="text/javascript" language="javascript" charset="utf-8"} (char 62) {var a_canvas = document.getElementById("a"); } "\n" {var a_context = a_canvas.getContext("2d"); } "\n" {a_context.font = "bold 12px sans-serif"; } "\n" "\n" )) (dotimes (i 200) (greet (amb "Hyvää joulua ja onnellista uutta vuotta" "Joyeux Noël et bonne année" "Fröhliche Weihnachten und ein gutes neues Jahr" "聖誕節同新年快樂" "Nollick Ghennal as Blein Vie Noa" "圣诞节快乐" "Buon Natale e felice anno nuovo" "Veselé vánoce a šťastný nový rok" "God jol og godt nyttår" "Linksmų Kalėdų ir laimingų Naujųjų Metų" "Crăciun fericit şi un An Nou Fericit" "Natale hilare et annum faustum" "Merry Christmas" "Zorionak eta urte berri on" "Gleðileg jól og farsælt nýtt ár" "(println {Happy newLISPing})" "Seasons Greetings" "शुभ क्रिसमस" "Καλά Χριστούγεννα!" "Bonan Kristnaskon kaj feliĉan novan jaron" "Prettige kerstdagen en een Gelukkig Nieuwjaar!" "Sretna Nova godina!" "Rõõmsaid Jõule ja Head Uut Aastat" "Nollaig chridheil agus bliadhna mhath ùr" "Nadolig llawen a blwyddyn newydd dda" "明けましておめでとうございます" "Priecīgus Ziemassvētkus un laimīgu Jauno gadu" "Веселого Різдва і з Новим Роком" "С наступающим Новым Годом") (rand (- width 100)) (rand (+ height 200)))) (write-buffer page (string (char 60) {/script} (char 62))) page ---

This post uses the HTML 5 Canvas, and should work properly on recent standards-compliant browsers such as Safari, Firefox, and Google Chrome. The Opera browser can't handle this, which surprised me. As for Internet Explorer ... I suspect you won't see anything. Also, even if the canvas works well, there's still the problem of all those Unicode fonts. We haven't completely left behind the early days of the web, when every other page had a "Best viewed in browser X" banner.

The image is generated afresh each time you load the page, so the colours and positions of the various greetings are different each time. This is because the image is generated by embedded newLISP code in the HTML database which is evaluated only at browse time. The only tricky part of the operation is to make sure the code survives being translated by Markdown into HTML, then being uploaded via xmlrpc to be stored in the newLISP database ready for being processed by Dragonfly.

If you want a challenge, see how many different languages you can identify (without cheating)!

newLISP Bayesian Comment Spam Killer

2009-11-17T19:35:00.000Z

This post describes the newLISP Bayesian Comment Spam Killer. It won't kill Bayesian comments - although it might - but it tries to kill spam comments on blogs, using Bayesian analysis.

The story starts after the aspiring commenter clicks the Submit button on the comment form, and after the CGI script or web framework has extracted the information from the commenter's posted submission. To makes things easy, here are some declarations that get me quickly to the same position:

(set 'comment-date "20091114T163223Z")
(set 'storyid "projectnestorpart1")
(set 'comment "Very nice site!")
(set 'commentator "svQrVW a href=\"http://asdfhh.com/") 
(set 'commentator-uri "svQrVW a href=\"http://asdfhh.com/") 
(set 'ip-address ("94.102.60.174"))

The first thing to do is to save this information in a file. There are many ways to do this, but I like to save data in newLISP format wherever possible, because it saves time and effort when reading it back in:

; make a suitable path name
(set 'path (string {/Users/me/blog/comments/} 
    story-id "-" comment-date ".txt"))
; save as association list
(set 'comment-list 
     (list
        (list 'comment-date comment-date)
        (list 'storyid storyid) 
        (list 'commentator commentator) 
        (list 'comment comment-text)
        (list 'ip-address ip-list)
        (list 'status "spam")
        (list 'commentator-uri commentator-uri)))             
(save path 'comment-list)

A few weeks after opening a comments form to the intelligent citizens of cyberspace, there will be hundreds of little newLISP files in the directory, containing all kinds of comment. Each file looks something like this:

(set 'Comments:comment-list '(
  (Comments:comment-date "20091114T163223Z") 
  (Comments:storyid "projectnestorpart1") 
  (Comments:comment "svQrVW a href=\"http://asdfhh.com/ etc etc ") 
  (Comments:commentator "svQrVW a href=\"http://asdfhh.com/") 
  (Comments:commentator-uri "svQrVW a href=\"http://asdfhh.com/") 
  (Comments:ip-address ("94.102.60.174")) 
  (Comments:status "spam") 
  ))

I've added a status tag to each one, with the default value of "spam". That means that every comment so far is considered spam. That's not good (although very close to the actual truth), so I must also manually alter any genuine comments and tag them as "approved". That's a vital task, and for a while I did it by hand, until the collection of comments was large enough for me to trust the Bayesian analysis to do it automatically.

Once I've got a reasonable collection of comments, I'm ready to start building the Comment Spam Killer.

(context 'Comments)

A little macro I've been using recently provides a modified append:

(define-macro (extend)
  (setf (eval (args 0)) (append (eval (args 0)) (eval (args 1)))))

This accepts a symbol holding a list, and a list, and adds the elements in the list at the end of the symbol's current elements.

I want somewhere to store the analysis:

(define MAIN:spam-corpus)

This function extracts a list of the words used in all the comments:

(define (build-word-lists dir)
    (dolist (nde (directory dir {^[^.].*txt}))
       (if (directory? (append dir nde))
         ; directory, recurse
         (build-word-lists (append dir nde "/"))
         ; file: read info and make a list of its contents
         (letn  ((file            (string dir nde))
                 (comment-list    (load file))
                 (commentator     (lookup 'commentator comment-list))
                 (comment         (lookup 'comment comment-list))
                 (comment-status  (lookup 'status comment-list))
                 (commentator-ip  (lookup 'ip-address comment-list))
                 (commentator-uri (lookup 'commentator-uri comment-list))
                 (word-list '()))
              (extend word-list (parse commentator       "[^A-Za-z]" 0))
              (extend word-list (parse comment           "[^A-Za-z]" 0))
              (extend word-list (parse commentator-uri   "[^A-Za-z]" 0))
              ; sometimes ip addresses are stored in a list...
              (if (list? commentator-ip)
                  (dolist (i commentator-ip) (extend word-list (list i))))
              (cond
                  ((= comment-status "approved")
                      (extend genuine-comments (clean empty? word-list)))
                  ((= comment-status "spam")
                      (extend spam-comments (clean empty? word-list))))))))

And the two lists can be turned into a Bayesian-ready dictionary with:

(bayes-train spam-comments genuine-comments 'MAIN:spam-corpus)

The resulting spam-corpus is a context that provides two numbers for each word in the comments. Here's an informative extract:

 ;         
 ("prepended" (0 2)) 
 ("prescription" (36 0)) 
 ("present" (0 1)) 
 ("presepe" (3 0)) 
 ("pretty" (0 1)) 
 ("price" (2 0)) 
 ("primari" (3 0)) 
 ("primaria" (6 0)) 
 ("primitive" (0 1)) 
 ("princessdc" (2 0)) 
 ("print" (0 2)) 
 ("printing" (4 0)) 
 ("println" (0 5)) 
 ("prior" (0 1)) 
 ("priors" (0 3)) 
 ;...

The contents of the spam context hold a list of words and the number of times that each word occurs in the first category, the spam comments, or the second category, the genuine comments. The apparent discrepancy between print and printing is easily resolved once you look at the original comments - something to do with custom T-shirt printing, whereas print was twice mentioned in a piece of newLISP code in a comment.

(define (analyse-comment file)
    (letn ((comment-list    (load file))
           (commentator     (lookup 'commentator comment-list))
           (comment         (lookup 'comment comment-list))
           (comment-status  (lookup 'status comment-list))
           (commentator-ip  (lookup 'ip-address comment-list))
           (commentator-uri (lookup 'commentator-uri comment-list))
           (word-list '())
           (spam-comments '())
           (genuine-comments '()))
        (extend word-list (parse commentator       "[^A-Za-z]" 0))
        (extend word-list (parse comment           "[^A-Za-z]" 0))
        (extend word-list (parse commentator-uri   "[^A-Za-z]" 0))
        (if (list? commentator-ip)
            (dolist (i commentator-ip) (extend word-list (list i))))
        (clean empty? word-list)
        (set 'spam-score (bayes-query word-list 'MAIN:spam-corpus))))

which returns a double-valued spam score for each comment. The two numbers are the probabilities that a comment belongs in the first or second category.

It's now easy to decide whether to reject a comment based on the two numbers returned by this function. The example I started with manages to score (1 0), a clear indication that this apparently harmless phrase is, when considered as part of a comment as a whole, usually a comment from a spammer.

If you're wondering where the comments form is on this site - well, there isn't one; I decided against using up disk space storing hundreds of unwanted comments!

Syntax matters

2009-10-21T23:22:00.000+01:00

My fellow newLISP blogger Kazimir observes in his poll analysis that one of the main reasons why people don't use Lisp is the syntax:

Lisp syntax is the most important reason for majority of people who do not use Lisp.

The thing I don't understand, though, is what exactly is wrong with Lisp syntax that makes people avoid the language. Perhaps that's another research opportunity.

Here's a simple scripting problem. Given a text file containing a series of random paragraphs, separated by percent signs, sort them so that they are ordered according to the first significant word in each paragraph. That is, words such as "a" and "the" shouldn't affect the sort order.

Here's one solution:

#!/usr/bin/perl -w

my %sort_buckets;
my %exclusions;

my $file_to_sort = '/path/to/file_to_sort';
my $sorted_file = '/path/to/sorted_file';

while () {
    chomp;
    $exclusions{$_}++;
}

open $in, "<", $file_to_sort
    or die "Can't open file: $!";

$/ = "%\n";

while (<$in>) {
    my $line = $_;
    my @words = split " " => $line;
    my $sort_key = '';
    for (0..$#words) {
        if ($exclusions{lc($words[$_])}) {
            next;
        } else {
            $sort_key = join "" => map { lc($_) } @words[$_..$#words];
            last;
        }
    }
    $sort_buckets{$sort_key} = $line;
}

close $in;

open $out, ">", $sorted_file
    or die "Can't open file: $!";

foreach (sort keys %sort_buckets) {
    print $out $sort_buckets{$_};
}

close $out;

__END__
a
the
this
that
you
when
is
may
be
if
and

I'm not sure I know what's going on there, but it's a typical practical (and probably quick) solution from a Perler. For comparison, here is a newLISP version:

#!/usr/bin/env newlisp

(set 'common-words 
  '("a" "the" "this" "that" "you" "when" "is" "may" "be" "if" "and"))

(define (remove-common text)
    (difference 
       (find-all {[a-zA-Z]+} (lower-case text)) 
        common-words))

(define (compare text1 text2)
    (< (remove-common text1) 
       (remove-common text2)))

(write-file {/path/to/sorted-file.txt}
    (join (sort 
             (parse (read-file {/path/to/file_to_sort.txt}) "%")
             compare)
     "%"))

It's not clear to me why this syntax is considered unappealing, or indeed how it could be improved. I've written about this before, so obviously I haven't sought hard enough for an answer.

Can we measure some aspect of these two files? How about looking at the use of alphabetic characters and parentheses. For the Perl example:

Parentheses: (7 7) Braces: (11 11) Brackets: (2 2) Alphabetic: 403 Non-alphabetic: 642 ratio 0.6277258567

And the newLISP example:

Parentheses: (17 17) Braces: (3 3) Brackets: (1 1) Alphabetic: 256 Non-alphabetic: 168 ratio 1.523809524

The preponderance of the Lisp parentheses is apparent. But otherwise, the Lisp example is plainly much more alphabetic, more readable, more civilized. It's just possible that the non-mathematical syntax, and the lack of familiar and friendly "x = x + 3" forms (as learned by schoolchildren from 10 years and upwards) are enough to disarm and perplex the non-Lisper.

newLISP at Wikibooks: volunteers wanted

2009-09-29T19:09:00.000+01:00

I've moved the Introduction to newLISP over to Wikibooks, and you can find it here:

http://en.wikibooks.org/wiki/Introduction_to_newLISP

You can find a link to the Print version on that page, which gives a complete view of the entire document, suitable for printing to PDF or saving as HTML.

I've never really looked at Wikibooks before, having spent much more time using Wikipedia. Wikibooks is an attempt to build an open-source library of text books. At present there are nearly 40,000 books available to browse or edit, and I've found some quite interesting books there, although there are many others that didn't look interesting (or that needed serious editing).

Although I have a few reservations about the presentation of texts in Wikibooks (I like more control over the visual appearance of documents, and the output conversions could be better), I think the Wikibooks approach is worth trying for this particular document. Like the WIkipedia and Wikibooks themselves, it's an experiment. I'm hoping that the contributions of others in the newLISP and Wikibooks communities will improve the document and make it more useful.

To take part, all you have to do is visit the home page and have a go at editing. One thing that really needs doing at the moment is a general check of anything where my lack of Windows- knowledge was all too obvious.

Updates to nldb

2009-09-12T16:24:00.000+01:00

I've been making some changes to the newLISP database (nldb.lsp), a small set of functions that provide some rudimentary database-like tools for those occasions when even SQLITE is too heavy. I've written about it before - see Simple database in newLISP; it's currently in use as the database engine for this site, although I think engine is probably the wrong word (think rubber band or sail).

The problems started when I tried to store a list in one of the columns. I had decided that, since the data was stored as a newLISP list, it ought to be able to contain nested lists too. Unfortunately, when I tried to store data using lists, some of the functions stopped working; I hadn't even considered the possibility that I might want to do that one day.

And the code was already more complicated than necessary. I was jumping through hoops trying to avoid evaluating column names until the last minute. A re-write revealed that there was a simpler solution (isn't there always?). The original code at the heart of the select-rows function was this:

(if (list? selection-function)
    (dolist (field columns)
        (set-ref-all (expand ''field 'field)
            selection-function
            (row (find field columns)))))
(if (eval selection-function)
    (push row selection -1))

I really didn't like that! It's now:

(if (list? selection-function)
    (dolist (field columns)
        (set 'cell (row (find field columns)))
        (set-ref-all field selection-function
            (if (list? cell) 'cell cell))))
(if (eval selection-function)
    (push row selection -1))

This new syntax allows you to supply the function without having to quote every symbol. For example, here is the new simpler syntax for a simple 'and' query:

(select-rows 'elements '(and (> EarthCrust 1) (< DiscoveryYear 1900)))

It's still necessary to quote the selector function, because it can be evaluated only after the relevant data has been extracted from the data list.

Another example: return a list of names and symbols and discovery dates of all elements discovered on or after 1900, sorted by year:

(select-rows 'elements
'(>= DiscoveryYear 1900)
'(DiscoveryYear Name Symbol)
'DiscoveryYear
(fn (x y) (< x y)))

which returns a list like this:

((1900 "Radon" "Rn")
(1901 "Europium" "Eu")
(1907 "Lutetium" "Lu")
(1913 "Protactinium" "Pa")
(1923 "Hafnium" "Hf")
(1925 "Rhenium" "Re")
(1937 "Technetium" "Tc")
(1939 "Francium" "Fr")
(1940 "Plutonium" "Pu")
(1940 "Neptunium" "Np")
(1940 "Astatine" "At")
; and so on
)

The functions now work with lists in columns. For example, you could add a list field that contains some keywords for each element. To build the list, push symbols onto the list for the selected rows:

(add-columns 'elements '(Keywords) '())

(change-rows 'elements
'(find  Name '("Iron" "Silver" "Gold" "Zinc" "Tin" "Nickel" "Lead"))
'Keywords
'(push 'Metal Keywords))

This adds the keyword Metal to a few of the more obviously metallic elements. Notice that the symbol 'Metal has to be quoted here, as it usually would be in newLISP.

The code lives on the Downloads page. If you need help getting it working, let me know.

End of the rainbow

2009-08-19T18:39:00.000+01:00

If you use Safari, the following code may look intriguingly multi-coloured.

 (define (add-columns table-name new-column-list (value nil))
 ;; @syntax (add-columns table-name new-column-list value)
 ;; Add more columns to table (and every row in table).
 ;; You can provide a default value for them.
 ;; (add-columns 'elements '(Price Postage) 0)
     (letex ((table table-name))
         (let ((columns (first table)))
              ; mustn't duplicate columns
              (if (empty? (intersect new-column-list columns))
                  (setf table
                      (cons (append columns new-column-list)
                          (map  (fn (r) 
                                   (append r (dup value (length new-column-list)))) 
                                (rest table))))))))

Let me know if you can work out what's going on, and what you think.

Creative functions

2009-08-15T22:59:00.000+01:00

There's a small family of newLISP functions that can make new lists and fill them with data. These could be described as creative functions. Let's have a quick look at some of them.

dup is the plain but useful replicator function. It can produce a number of identical copies of an element, and it's handy in a wide variety of situations.

(dup {.} 20)
;-> "...................."

Use an extra true flag to make a list of short strings, rather than a single longer string:

(dup {.} 20 true)
;-> ("." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." "." ".")

You can use dup when formatting text:

(define (space (n 4)) (dup { } n))
(space 20)
;-> "                    "

normal and random are different in action yet - in a way - they both do similar jobs. random creates a list of random numbers, and normal does the same. However, the numbers returned by normal are chosen to match a pre-determined mean and standard deviation.

(normal 4 1.2 10) ; mean 4, and standard deviation 1.2
;-> (1.87421875 4.626953125 4.88359375 1.476953125 1.573046875 2.34765625 
;  5.321875 3.84765625 4.019921875 4.10078125)

(random 0 10 10) 
;-> (1.031711884 1.260753391 4.954440666 7.604752284 9.84751665 
; 9.350039866 6.844450169 3.831883312 7.497708824 3.686635417)

The ten numbers in the first list have a mean value of 4, and a standard deviation of 1.2. These numbers have a normal or Gaussian distribution. The ten numbers in the second list are randomly chosen.

sequence is a simple but smart numerical sequence generator:

(sequence 1 10)
;-> (1 2 3 4 5 6 7 8 9 10)

(sequence 1 10 1.6)
;-> (1 2.6 4.2 5.8 7.4 9)

It's also a good way of generating alphabetic sequences:

(map char (sequence (char "a") (char "z")))
;-> ("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p" "q" 
; "r" "s" "t"  "u" "v" "w" "x" "y" "z")

But probably the most powerful and flexible member of this creative family is series. This has two forms, a simple numerical form that generates a geometric series, and a more general functional form.

(series 1 2 10) ; start at  1, factor 2
;-> (1 2 4 8 16 32 64 128 256 512)

The functional form takes a starting expression, a function that generates the next element from the current one, and the number of elements required.

(series 1 inc 10)
;-> (1 2 3 4 5 6 7 8 9 10)

Here, the function inc is applied repeatedly, first to the starting element, and then to the result of each application, until the required number of elements has been generated. The result here is the same as the sequence call above.

The starting element doesn't have to be a number, it could be any expression. All that's required is for the function to be able to generate the 'next' element in the series given the current element.

(series "123456789" chop 10)
;-> ("123456789" "12345678" "1234567" "123456" "12345" "1234" "123" "12" "1" "")

Our code for generating the alphabet can also be written as follows. An inline anonymous function calculates the next letter given the current one:

(series "a" (fn (n) (char (inc (char n)))) 26) ; alphabet
;-> ("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" 
; "p" "q" "r" "s" "t" "u" "v" "w" "x" "y" "z")

The next element is easily found by incrementing the ASCII code of the current element.

As with many of newLISP's iteration and mapping functions, you can access a counter to find out how far you've got:

(series 1 (fn (f) (* f (+ 2 $idx))) 20)  ; factorials
;-> (1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 
; 6227020800 87178291200 1307674368000 20922789888000 355687428096000 
; 6402373705728000 121645100408832000 2432902008176640000)

$idx returns the 'number' of the current element being calculated. It starts at 0, though, so you might want to move it up a bit, as here.

To add a day - a day's worth of seconds - to a date:

(series (date-value) (curry + 86400) 10)
;-> (1250112127 1250198527 1250284927 1250371327 1250457727 
; 1250544127 1250630527 1250716927 1250803327 1250889727)

Notice that we can't simply say (+ 86400) here, because that evaluates to 86400, which makes newLISP evaluate the expression as a simple numerical series rather than a functional one. By saying (curry + 86400), we're making a new function that adds 86400 to its argument, and it's this function which is applied to each value.

(map date (series (date-value) (curry + 86400) 10))
;-> ("Wed Aug 12 22:22:24 2009" "Thu Aug 13 22:22:24 2009" 
; "Fri Aug 14 22:22:24 2009" "Sat Aug 15 22:22:24 2009" 
; "Sun Aug 16 22:22:24 2009" "Mon Aug 17 22:22:24 2009"
; "Tue Aug 18 22:22:24 2009" "Wed Aug 19 22:22:24 2009" 
; "Thu Aug 20 22:22:24 2009" "Fri Aug 21 22:22:24 2009")

series is versatile enough that it can do the jobs of some of the other creative functions, such as dup:

(dup "fred" 6 true)
;-> ("fred" "fred" "fred" "fred" "fred" "fred")

(series "fred" copy 6)
;-> ("fred" "fred" "fred" "fred" "fred" "fred")

That copy looks at home here, but in fact any function that returns the same element when applied would work just as well:

(series "fred" begin 6)
;-> ("fred" "fred" "fred" "fred" "fred" "fred")

because:

(begin "fred")
;=> "fred"

Also:

(series "fred" string 6)
;-> ("fred" "fred" "fred" "fred" "fred" "fred")

And what about that most famous of numeric sequences, the Fibonacci series? Can series do it? With a little thought, yes:

(set 'p 0)
(series 1 (fn (n) (set 'q (+ n p)) (set 'p n) q) 20)
;-> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

We've had to use temporary variables to store the previous values. In the inline function, notice that the finishing value, fed to the next iteration, is q.

The Lambdalator: RIP

2009-08-08T15:06:00.000+01:00

This week I killed the Lambdalator. The Lambdalator was my experimental public online newLISP terminal that allowed you to access a newLISP interpreter running on my server using just a web browser.

It was an interesting experiment, and I made use of it on more than one occasion myself, while out on the road. (Not enough public computers run newLISP, it seems to me.) Recently, however, the Lambdalator was being visited primarily by just two groups of users: spammers, and a few Common Lisp speakers, with unsatisfactory results for all. Changes to newLISP (which is now at version 10, while the Lambdalator was written for version 9.3), and to my hosting service at NFS (who are going to charge more for dynamic sites) made me decide to kill the site. However, it may return in a future re-incarnation, as may its companion service, Jack the Glypher, which converted text to ASCII art.

I've kept the log files generated by each visitor to the site, which is how I know about the curious two groups that tried it out.

The spammers simply saw an input box and a submit button, and happily wasted their time copying their bizarre web links and trying to evaluate them as newLISP. What they didn't realise was that only they could see the results of their efforts. This is the code that ran when the Evaluate button was clicked:

(if (CGI:get {evaluate})
    (run-evaluator (CGI:get {expression}) (base64-dec (CGI:get {tape}))))

This is the function that evaluated the text:

(define (run-evaluator x tape)
   (unless (empty? x)
     (begin
        (push 
           (string {} 
             (escape-html (fork-eval-string (trim x))) 
             {} 
             "\n" 
             { } 
             x 
             {
}) 
           output)
        (set 'expression x)
        (log-it x))
     ; nothing to do
     (set 'expression {}))
   ; output
   (push tape output -1)
   (set 'output (string (0 2500 output) (if (> (length output) 2500) {...} {}))))

and the hidden field of the form has the following structure:

 type="hidden" name="tape" value= (base64-enc output) "  />

where the encoded output from the evaluation is stored in the form. The effect is like a paper tape: the previous input text is sent back to the browser on the next evaluation. The invisible log file keeps a record on the server, but only the user sees what the result was. Pleasingly, only the spammer sees their own spam, and while they're staring at their own spam they're not spamming other people's blogs.

The visits by Common Lisp speakers are also easy to spot in the logs. Typically they try to outsmart the interpreter, but don't know enough newLISP to do so. Sometimes they can be seen struggling to balance their parentheses without an editor to help them. Typing a few expressions, usually using car and defun, was often all that they tried.

The Lambdalator will return soon. I'm having problems with my HTML POST parameters at the moment, and haven't had enough time or knowledge to solve them!

Enter the Dragon(fly)

2009-08-01T15:27:00.000+01:00

I'm now running this blog on Dragonfly, a cool new newLISP framework written by Marc, using some code by Jeff (and a few minor contributions from me). It's great to have someone else in charge of all that weird web stuff such as CGI headers and .htaccessing URLs for a change. I'm hopeful that I can soon start writing some newLISP again.

I've spent the last week puzzling over a bug in my newLISP XMLRPC server (which is based on Lutz' original XMLRPC code). This is designed to receive a post submitted by a desktop blogging application and enter it into the database. The obvious and visible problem I thought I had was that pre-formatted text (such as a code listing) was being displayed in a web browser on a single line - the linefeeds were being removed somewhere, by something. I examined many different ways of parsing XML, and spent much time replacing carriage returns and newlines, and printing intermediate results to temporary files, but couldn't find anything that could be removing linefeeds. Many days passed...

It turned out that I'd been looking in the wrong places, and had incorrectly diagnosed the problem anyway. Consider this code, which is where the server reads the incoming XML:

(if (not input)
        (print
            "Content-type: text/html\r\n\r\n"
            "newLISP XML-RPC v." version 
            ": not a valid XML-RPC request
")
        (begin
            (while (read-line) (write-buffer input (current-line))) ; <-- -- -
            (process-post input)))

It looks obvious now, but after I modified the code to this:

(if (not input)
    (print
        "Content-type: text/html\r\n\r\n"
        "newLISP XML-RPC v." version 
        ": not a valid XML-RPC request
")
    (begin
        (while (read-line) 
            (write-buffer input (string (current-line) "\n"))) ; <-- --
        (process-post input)))

it all started working correctly. In the entry for read-line, the newLISP manual correctly states:

The line always breaks on a line-feed, which is then swallowed.

In other words, the newlines had been swallowed and thrown away right at the beginning of the script, and I'd noticed it only in the obvious places, where the text is pre-formatted.

Finding the problem can be much harder than finding the solution!

newLISP and TextExpander for Mac

2009-07-04T10:45:00.000+01:00

A mention of TextExpander on Creativityist's excellent blog reminded me that I haven't talked this cool MacOS X utility yet in relation to newLISP. So here's a quick mention.

Perhaps, like me, you write text in many different applications. Sometimes you'll find me in Scrivener, mainly for its awesome long document handling, and other times in ecto, the excellent blog post editor, ideal for WordPress. I also use BBEdit for all kinds of text and code, and VoodooPad, a container for all kinds of notes and stuff. I spend quite a lot of time typing in web pages such as comment boxes and forum pages, and composing email messages, too.

TextExpander works in every application you use on your Mac. The idea is simple: you type in a short abbreviation, and TextExpander expands it into a word or phrase. For example, if I want to insert a date stamp in ISO format into the current document or text area, I just type ,iso and TextExpander replaces it with the current date and time. (It didn't happen just then, obviously - I cheated!) Another example is 'newLISP' - it's so much quicker to type nl than it is to type newLISP, with that Shift key held down for the last four characters. I use various TextExpander snippets when I'm writing newLISP code, such as for writing the shebang line at the beginning of every script: It's much quicker to type nl/ than #!/usr/bin/env newlisp.

There are lots of cool features in TextExpander. For example, you can control where the cursor is positioned in the expanded text - that's great with code templates. You can synchronize multiple machines across the internet, so that you always have access to your snippets, no matter which computer you're using. And you can subscribe to snippet files from an external URL, too - these are updated and maintained by the authors so you can easily benefit from their hard work. For example, there's a large database of commonly mistyped words that will catch and correct those hard-to-spot typos. And for the whimsical, feel free to choose suitable sounds that accompany the expansion of some of your abbreviations (sounds from Myst add magic to even the most mundane memos).

What makes TextExpander particularly powerful, though, is that an abbreviation can run any newLISP script. This means that a short phrase or abbreviation can launch a script and insert its standard output into the current document. There's no restriction on what you can put into the script, but it's logical to generate some useful text using println, and/or use any text on the clipboard as raw input.

(In fact, TextExpander is script-language-agnostic, and lets you use any shell command or AppleScript. You might even be able to run those Common Lisp scripts. But naturally, newLISP is the best choice: quick to start up, fast in operation, and as powerful as you need it to be. Whatever shell script you choose, remember to set the Content Type to shell script and use the shebang line of your choice.)

Here's an example of a newLISP script I use a lot. Suppose I'm writing about a web site, and viewing it in a browser window. I want to insert a link to the site in the document I'm writing. I'm probably using Daring Fireball: Markdown format, so I'll want to insert both the web page title and the URL, the first enclosed in square brackets, the second in parentheses. In the document I type ,s, which runs the following newLISP script:

#!/usr/bin/env newlisp    
(define (get-safari-page-link)
  (exec 
    (format 
      [text]osascript -e 'tell application "Safari" to set urlLink to URL of front document
    return urlLink'[ /text])))

(define (get-safari-page-title)
  (exec 
    (format 
      [text]osascript -e 'tell application "Safari" to set urlTitle to name of front document
    return  urlTitle'[ /text])))

(set  'page-url   (get-safari-page-title) 
      'page-title (get-safari-page-link))

(if-not (empty? page-url)
  (print  "["   (first page-url) 
          "]("  (first page-title) 
          ")")
  (println ""))

Yes, it's a bizarre witches' brew of newLISP and OSAscript, which is AppleScript 'typed' on the command line. I prefer to use osascript to run AppleScript commands, because it's easier to switch between languages as required. Nevertheless, it quickly does the job, inserting details of the frontmost web page into the current document, and it doesn't matter whether I'm writing in Ecto, BBEdit, or Scrivener.

Using the clipboard is currently the only way you can pass information to a script invoked by a shortcut. This is restrictive, I suppose, but it provides useful functionality nevertheless. Here's a script that inserts a version of the text on the clipboard in which some HTML characters have been encoded:

#!/usr/bin/env newlisp

(set 'replacements '(
    ({&}  {&})
    ({>}   {>})
    ({<}   {<})))

(set 'text (exec "pbpaste"))

(dolist (line text)
    (dolist (i replacements)
       (replace (last i) line (first i)))
    (println line))

TextExpander keeps track of how many abbreviations you've used, and has a cute feature that tells you how much time you've saved, based on how many keys you haven't had to press. Apparently I've saved hours of time that I would otherwise have spent typing. In reality, of course, I've probably just spent that time playing with TextExpander...!

Follow this link to find out how you can save 20% off the price of a TextExpander licence, till the end of July 2009.

Mazes

2009-03-30T21:38:00.000+01:00

Here's the first of what might become a series of posts about maze programming and newLISP. I've been fascinated by mazes ever since I was taken to Hampton Court Maze as a kid, and today I still occasionally write some maze-related code when I need a simple project to test out new languages or techniques.

Although I wrote a lot of this code last year (or the year before), I've updated it a bit for newLISP 10, and dusted it off to keep this blog going for a while until I get some time to write some new stuff.

Jumping right in: a Maze context contains the data and functions for a single maze, which is stored as a rectangular grid of squares, of which some can be solid 'walls' and the rest empty. But the maze data is stored in a flat list rather than an array. Yes, I know that arrays can be quicker, but it's often the case that lists are more versatile - more functions work on lists than on arrays - and the performance hit that I'm incurring won't really be an issue for me.

(context 'Maze)
(constant 'wall -2 'empty -1)    
(define M)
(define height)
(define width)
(define maze-length)

(define (make (h 15) (w 15))
  (set 'height h 'width w 'maze-length (* height width))
  (set 'M (dup wall maze-length))
  M)

This function makes a pretty solid mass of walls, with no passages or corridors. Each 'cell' of the maze M can be accessed by a single index number n. Using newLISP's implicit addressing, this is simply (M n).

To make life easy for my code, the maze must be completely surrounded by a solid wall. The following simple functions test a single cell to see if it's on the outside wall:

(define (north-perimeter? n) (= (/ n width) 0))     
(define (south-perimeter? n) (> n (- maze-length width)))
(define (east-perimeter?  n) (= (% n width) (- width 1)))
(define (west-perimeter?  n) (= (% n width) 0))

And this is a useful test: is the cell n on the outside wall?

(define (perimeter? n)
(or 
  (north-perimeter? n) 
  (south-perimeter? n) 
  (east-perimeter? n) 
  (west-perimeter? n)))

Next, to generate a maze. For now, I'm happy to have a simple randomly-generated maze. Later, I'll create mazes with a little more thought. Passages are excavated from the solid maze by the following function:

(define (random-fill)
   (dotimes (i maze-length)
       (and (not (perimeter? i))
            (setf (M i) empty)
            (= (rand 3) 0)      ;  1 in 3
            (setf (M i) wall))))

About 1 in 3 cells are solid, which gives reasonable values. Actually, this isn't a very good function, since it sets every cell to be empty, then sets some of them back to be solid again.

For simple debugging at the terminal, a simple show function is useful.

(define (show (maze M))
(for (n 0 (- maze-length 1))
    (cond  
      ((= (maze n) wall)    (print (char (int "\0x2588"))))
      ((= (maze n) empty)   (print " ")))
    (if (east-perimeter? n) 
        (println))))

That Unicode symbol is useful for printing out solid shapes. The procedure for making a maze is the following sequence of functions:

(make 15 15)
(random-fill)
(show)

███████████████
██   █  ██    █
█  █ █     ████
█ █   █    ████
█ █  █  █    ██
█ █   ███    ██
█  ██  ████ █ █
█ █ █ ██   ██ █
██ █  █ █ █   █
██ █      █ ███
█  █  █  █    █
██   █    █   █
█ █  █  █   █ █
█   █     █ █ █
███████████████

which, although not beautiful, is at least useful. You can generate more appealing graphical displays using any technology you fancy: I've been using the new HTML Canvas module for newLISP to generate output; this is much easier than trying to get OpenGL working properly. (I drew the OpenGL graphics more or less successfully, but was unable to position the eye-point in such a way that I could actually see them.)

This is a useful helper function to find the empty neighbouring cells of a given cell:

(define (empty-neighbours n)
(clean nil? 
  (map (fn (o) 
       (if (= empty (M (- n o)))
           (- n o)))
       (list 1 -1 height (- height)))))

To choose an empty cell at random:

(apply amb (ref-all empty M))
;-> (69)

and to select two empty cells at random:

(set 'start (first (apply amb (ref-all empty M))))
;-> 69
(set 'end   (first (apply amb (ref-all empty M))))
;-> 153

Now we get to the interesting stuff. How can we find out whether there's a path from start to end? There are, of course, many interesting maze-solving algorithms, but I'm quite fond of the following one, which is quick, clever, and a little bit baffling too. I think it's related to an algorithm developed by someone called Bellman, but I've not traced a definitive reference yet. It's a 'tidal flooding' algorithm, and it works as follows.

Before you start, you prepare a list that's the same length as the maze, but empty. This list, the route map, is going to hold the solution. Then, you begin by 'standing' in the finishing cell. You look at each of the neighbouring cells in turn. If a cell is empty, you store its number in the current cell, make a note of how to get over there from where you're standing, and mark it as the current 'frontier' cell. You repeat this process until you're standing in the starting cell, or have looked at every cell. If you've reached the starting cell, you have, in the route map, values for all the cells that have been examined, with instructions (in the form of a number representing how many cells to move) on how to reach the end. It's then easy to extract a solution from this map.

This is the solver function:

(define (flood start finish)
(local (solution current-cell frontier-cell cells route-map)
  (set 'current-cell finish 'frontier-cell finish)
  (set 'route-map (dup nil (length M)))
  (until (or (= current-cell start) (> cells (length M)))
      (inc cells)
      (map (fn (neighbour) 
                (setf (M frontier-cell) neighbour)                  
                (setf (route-map neighbour) (- (- neighbour current-cell)))
                (set 'frontier-cell neighbour))
           (empty-neighbours current-cell))
      (set 'current-cell (M current-cell)))
  (if (= current-cell start)
      route-map)))

Run it thus:

(set 'route-map (flood start end))

If there is a solution, route-map contains a list of offsets for all visited cells. The following image superimposes the contents of this list on the maze: a value of 1 means move one cell to the right, a value of 15 means move down to the next row, and so on.

This solution can be converted into a list of North/South/East/West directions, or a list of cells to follow, by these functions:

(define (get-direction n)
  (cond 
    ((= n 1)  "E") 
    ((> n 1)  "S")
    ((= n -1) "W")
    ((< n -1) "N")))

(define (get-solution route-map start finish)
  (local (current-cell solution)
    (set 'current-cell start)
    (until (= current-cell finish)
         (push 
          (list current-cell 
                (get-direction (route-map current-cell))) solution -1)
         (set 'current-cell  (+ current-cell (route-map current-cell))))
    solution))

The solution then looks like this:

 ((69 "E") 
  (70 "S") 
  (85 "E") 
  (86 "E") 
  (87 "S") 
  (102 "S") 
  (117 "S") 
  (132 "W") 
  (131 "S")  
  (146 "S")  
  ...

and these can be displayed graphically, or written down on a piece of cheese and fed to a maze-solving micromouse.

By colouring the visited cells in blue, you can see the way the search has 'flowed' outward from the green starting point to the red end point, like a wave slowly flooding the maze. It's worth noting that this version of the flooding algorithm doesn't search the entire maze, only as much of the maze as is required. Here are some more examples:

You can see, though, that the algorithm doesn't always find the minimum possible number of cells.

Performance can vary, depending on the configuration of the maze and the chosen start and end points. I'm seeing solutions generated in about 600 microseconds for these simple 15 by 15 mazes, which is OK.

Next time, I'm going to be looking at another way to represent and draw mazes. Well. if I get time, I might!

On my command

2009-02-10T19:46:00.000Z

I don't use the newLISP terminal very much. Most of the time, I use an editor such as BBEdit to write and run newLISP scripts. The terminal interface to newLISP is certainly useful, for testing commands and for debugging, but I don't find it a comfortable environment for writing scripts.

In BBEdit I can define a key combination (such as Command + Return) that evaluates the current selection and inserts the result into the text. I have all the convenience of a handy newLISP terminal in addition to the comforts of a text editor, such as code completion, syntax colouring, parenthesis-balancing, and so on.

Of course, the newLISP terminal isn't meant to be an editor or development environment - you certainly don't want to load one of those every time you want to run a script.

But the terminal is cool in its own way. And, because the philosophy of Lisp is that you can adapt the language to suit your purposes, it's no surprise that the newLISP terminal is adaptable too.

Here's an extract from a editing session using the newLISP terminal to show the sort of thing I mean:

newLISP v.10.0.0 on OSX IPv4 UTF-8, execute 'newlisp -h' for more info.

OK    (define (fred a b c)
1       (if (> a 0)
2            (println (* b c))
2            (println (/ b c))
2        )
1      )

(lambda (a b c) 
 (if (> a 0) 
  (println (* b c)) 
  (println (/ b c))))

OK

First thing to notice are the prompts. The initial OK prompt (makes a change from the ">") changes after the first line of typing to indicate the current nesting level. Also, the [CMD] and [/CMD] tags that you normally have to use to enclose multi-line text input aren't necessary (and don't currently work in this set-up!).

OK    (fred
1     1 2
1     3
1     )
6
6

OK

Just as the if statement was spread over four lines, the (fred 1 2 3) expression sprawls over more lines than necessary.

It's quite easy to make newLISP do this. (It's much harder to make it robust and reliable - I'm not that sort of programmer.) You need to use two built-in newLISP functions: command-event and prompt-event.

Of the two, command-event is the more powerful. You assign a function to command-event, and that function handles all incoming text from the user. You can do what you want with that text, so it's not too difficult to make it build up a multi-line buffer, delaying evaluation until some later stage. And by keeping track of how many parentheses have been typed, and only evaluating the buffer when the nesting level returns to 0, you can get primitive multi-line editing support.

The code to make this happen is this:

(context 'Multiline)

(set 'buffer "" 'nest 0 'indent "    ")

(define (Multiline:Multiline c)
  (dolist (i (explode c))
      (push i buffer -1)
      (cond 
        ((= i "(") (inc nest))
        ((= i ")") (dec nest))
        ((= i "§") (set 'buffer "" 'nest 0))))
  (push " " buffer -1) 
  (when (= nest 0)
        (unless (catch (println (eval-string buffer) "\n") 'error)
                (println "! " error))
        (set 'buffer "" 'nest 0))
  "")

(define (prompt-event-function)
   (if (> nest 0) (string nest (dup " " nest) indent) (string "OK" indent)))

(context MAIN)

(command-event 'Multiline)
(prompt-event  'Multiline:prompt-event-function)

One obvious problem with this simplistic parsing is that parentheses inside strings have to balance:

OK    (set 'x "(
2      this is a string)
1     "
1     )

otherwise you would have to write code that recognises the different types of string and stops counting parentheses while inside them.

The current nesting level is output by the function that prompt-event function calls whenever a prompt is required.

You might have noticed the action in the cond clause on encountering a § character, the section sign. Well, this code was tricky to debug, because every mistake I made meant that I could no longer enter any newLISP commands... I thought an escape hatch would be a useful addition.

Improvements will be most welcome!

About this site

2009-01-30T22:47:00.004Z

This site is dedicated to newLISP, which is a fun, free, easy-to-use Lisp-like scripting language available for most current operating systems. The posts are mainly short articles exploring various aspects of the language, and there are also some occasional attempts at humour and perhaps fun too. I'm not a programmer, so don't expect to see any serious programming voodoo here.

The site is not associated with the developer of newLISP, Lutz Mueller, who can be found at the official newLISP web site.

Go away if...

If you're a fundamentalist Lisp user, a newLISP-hater, or are just not interested in exploring newLISP, then please don't bother to read anything here, and please don't waste your time and mine by complaining about how newLISP isn't a proper Lisp, isn't as good as (insert name of some other Lisp here), doesn't have Feature X or Facility Y, blah blah blah. You are wasting your (presumably) valuable time on a pointless and some would say objectionable activity - go and do something more useful with your time.

If you're a spammer, don't waste your time trying to get your comments published here. All comments are carefully reviewed before being posted, and I'm unlikely to approve yours, obviously. Also, your IP address will be added (possibly more than once) to the banned list, which means that sooner or later you won't be able to load the site at all. It's wasting much more of your time than mine. Again, please find something more useful to do. The world needs improving; try and do something to make it better.

Dragonfly

This site is also a testing ground for newLISP code. It's now powered by the speedy and generally awesome Dragonfly web framework. Before then, it used by my attempt at a 'minimalist' blogging application called The Parenthesis Engine. The Parenthesis Engine was a replacement for the previous newLISP blogging application which used to run this site, which has been mentioned before in these posts as the LambdaPress. The LambdaPress was based on a SQLite database, and is now obsolete. Some of the older posts reference some code excursions that are now meaningless, and not applicable to Dragonfly. Before then, the site was hosted on Blogger, and it's still there, although all the old posts were migrated over.

Downloads

There are a few files on the downloads page that you can have a look at. If you need any help with these, or wish to complain about the coding style, let me know or ask on the forums.

Process Finder Selection: the return of AppleScript (for a few seconds at least)

2009-01-30T22:47:00.003Z

I recently wanted to process a group of files that had been selected in the MacOS X Finder. (This is a Mac-specific post!) Obviously I wanted to do the work with newLISP. Here's a three-step reminder of how to do it.

First, enable the Script icon on the menubar, if it isn't already. (Many people have described how to do this; here's a good one.) The Script Menu shows both global scripts and the scripts that are designed for the application you’re running. Scripts to be run in the Finder should be in /Users/you/Library/Scripts/Applications/Finder/. You don’t have to use a special suffix for the file.

Secondly, save the Finder-related scripts in that folder, and don’t forget to make them executable first! Here's the basic idea:

#!/usr/bin/env newlisp

(set 'applescript 
[text]
set rslt to {}
tell application "Finder"
  set s to selection
  repeat with i in s
    set end of rslt to (POSIX path of (i as alias))
  end repeat
end tell
rslt
[ /text])

(set 'file-list (parse 
   (first 
      (exec (string "osascript -e '" applescript "'" ))) ", "))

(dolist (f file-list)   
  (println f))
; printed output goes to the console

/usr/share/newlisp/guiserver.jar
/usr/share/newlisp/newLISP128.png
/usr/share/newlisp/modules/cgi.lsp
/usr/share/newlisp/util/newlisp.vim

Finally, enjoy working in newLISP rather than AppleScript! :)

Simple database in newLISP

2009-01-30T22:47:00.002Z

As I was updating the sqlite section of the Introduction to newLISP for version 10 last year, I wondered whether it would be easy to write a simple database interface using pure newLISP rather than SQL. This would be useful for those applications where a sqlite or other type of database might be difficult to install, implement, or just larger or more powerful than necessary.

Join me in the following thought experiment to see whether it would work. I'll use the periodic table example again, for this 'elementary' exploration.

We would start by loading the database code as a module:

(load "nldb.nl")

To make it easier to use (since you wouldn't have to keep supplying context prefixes), let's enter the module:

(context nldb)

Like many modern applications, let's assume there's an empty database already there by default, waiting to be filled. So the first real job would be to create a table. We would specify its name, and the names of the columns too:

(create-table 
  'elements 
  '(No AtomicWt Name Symbol MP BP Density EarthCrust DiscoveryYear Group IonEn))

Hopefully that would create a new table called elements, with the columns as shown. The next task would be to add some data. To add a row, you would expect to be able to do something like this:

(add-row 'elements '(1 1.0079 "Hydrogen" "H" -259 -253 0.09 0.14 1776 1 13.5984))

Although, in that form, the data has to be provided in full, in the right order. A refinement might be to be able to type this:

(new-row 'elements '((Name "Unobtainium") (Symbol "Ub")))

where we can assume that any missing or unspecified columns are left undefined.

After using these and similar functions interactively, it would be useful to be able to see what's been done so far. Logically:

tables
;-> (elements)

should return a list of tables, and, to see the columns in a table:

(list-columns 'elements)
;-> (No AtomicWt Name Symbol MP BP Density EarthCrust DiscoveryYear Group IonEn)

To see the whole database, it would be useful to have a command like show:

(show)

for output such as this:

Contents of database db
 1 table: (elements)

 Table:  elements
 Columns (No AtomicWt Name Symbol MP BP Density EarthCrust DiscoveryYear Group IonEn)
 Rows:   
  (1 1.0079 "Hydrogen" "H" -259 -253 0.09 0.14 1776 1 13.5984)
  (2 4.0026 "Helium" "He" -272 -269 0 0 1895 18 24.5874)
  (3 6.941 "Lithium" "Li" 180 1347 0.53 0 1817 1 5.3917)
  ; and so on

When using a database, one of the primary tasks is to select rows in a table. So something like this would be a must-have function:

(select-rows 'elements)

which should return all rows. But you would also expect to be able to specify a filtering function, so that only certain rows would be selected. So, to find elements discovered since 1900:

(select-rows 'elements (where (>= 'DiscoveryYear 1900)))

which should return:

(((No 43) (AtomicWt 98) 
  (Name "Technetium") 
  (Symbol "Tc") 
  (MP 2200) 
  (BP 4877) 
  (Density 11.5) 
  (EarthCrust 0) 
  (DiscoveryYear 1937) 
  (Group 7) 
  (IonEn 7.28)) 
; and so on

and to find common elements (more than 5% of the earth's crust):

(select-rows 'elements (where (>= 'EarthCrust 5)))

which should return:

(((No 8) (AtomicWt 15.9994) 
  (Name "Oxygen") 
  (Symbol "O") 
  (MP -218) 
  (BP -183) 
  (Density 1.43) 
  (EarthCrust 46.71) 
  (DiscoveryYear 1774) 
  (Group 16) 
  (IonEn 13.6181)) 
; and so on

Ideally, the function used to select rows could be any newLISP function that returns true (select) or nil (don't select) based on the contents of each row's column:

(select-rows 'elements (where (find "ium" 'Name)))

(select-rows 'elements (where (starts-with 'Name "C" 0))) ; regular expression

and it should also be easy to specify more than one row-filter function:

(select-rows 'elements 
    (where (and (> 'EarthCrust 5))
                (< 'DiscoveryYear 1900)))

or do set intersections:

(intersect 
    (select-rows 'elements (where (> 'EarthCrust 5)))
    (select-rows 'elements (where (< 'DiscoveryYear 1900))))

It should be possible to display just a few columns of the results:

(select-columns '(Name EarthCrust) 
    (select-rows 'elements))

which should return:

(((Name "Hydrogen") (EarthCrust 0.14)) 
 ((Name "Helium") (EarthCrust 0)) 
 ((Name "Lithium") (EarthCrust 0)) 
 ((Name "Beryllium") (EarthCrust 0))
; and so on

and

(select-columns '(Name Symbol) 
    (select-rows 'elements (fn (row) (find "ium" (lookup 'Name row)))))

which should return:

(((Name "Helium") (Symbol "He")) 
 ((Name "Lithium") (Symbol "Li")) 
 ((Name "Beryllium") (Symbol "Be")) 
 ((Name "Sodium") (Symbol "Na")) 
; and so on

or even:

(map (curry lookup 'Name) 
    (select-rows 'elements (where (starts-with 'Name "A" 0))))

("Aluminum" "Argon" "Arsenic" "Antimony" "Astatine" "Actinium" "Americium")

Once this selection technique works, extending it to delete rows shouldn't be too difficult:

(delete-rows 'elements (where (> 'DiscoveryYear 1945)))

which should delete every element discovered after 1945.

So, how would we change the data in a row? It would make sense if you could pass a selection function to find some rows, and were then able to supply a column name and a modification function that could transform the data in those rows. Something like this, perhaps:

(change-rows 'elements (where (= 'Name "Hydrogen")) 'BP inc)

where the inc function would be applied to the contents of the BP (boiling point) column for all matching rows. The effect of this example would be to increase the value of Hydrogen's boiling point by 1 degree.

And the modification function should be, not just a newLISP primitive, but any function that modifies the current value:

(change-rows 'elements 
  (where (ends-with 'Name "ium")) 
  'DiscoveryYear 
  (fn (x) (setf x -2000)))

There, the anonymous function would set the value of x to -2000, and this function would be applied to the value of the column DiscoveryYear, for all matching (ie ending with "ium") elements.

A useful function to have would be a regular expression search. It could look like this:

(select-columns '(Name) 
  (find-text 'elements "pb" 1))

;-> (((Name "Lead")))

Here, a case-insensitive regex search for "pb", filtered to show only names, would return just a single element:

To sort a table, you'd want to specify the table, the column, and a function:

(sort-table 'elements 'BP >)

This returns the table, after sorting it by each element's boiling point. You should also be able to supply your own sorting function:

(sort-table 'elements 'Name (fn (x y) (< (length x) (length y))))
; returns the table, sorted with the shortest name first

To sort a row, it would be cool if you could apply a sort-rows function to a selection of columns:

(sort-rows 
  (select-columns '(Name Symbol) (select-rows 'elements)) 
  'Name 
  (fn (x y) (> (length x) (length y))))

;-> (((Name "Rutherfordium") (Symbol "Rf")) 
;     ((Name "Praseodymium") (Symbol "Pr")) 
;     ((Name "Protactinium") (Symbol "Pa")) 
; and so on

This example is better, as the whole table isn't sorted, just the extracts are.

There's no reason why we shouldn't be able to add new columns whenever we like:

(add-columns 'elements '(Explosiveness) 0)

Finally, we'd obviously want to save the database:

(save-db "/Users/me/elements.nldb")

That would save just the tables, not the entire nldb context with its functions as well. This way, we could develop the two sides (code and data) separately, even though they both live together when they're active. Loading the database would be a two-stage process. First, load the database module:

(load "nldb.nl")

then load the database:

(load "/Users/me/elements.nldb")

So, what do you think? To me, this first sketch of the 'user interface' didn't look too bad. So I decided to have a go at writing a fully-functional version. In the early stages I was helped by some work done last year by kinghajj on the newLISP forum. I ended up using a bit of his code, but changing the model, making it a bit easier for me to understand. (If you're out there, kinghajj, thanks, and hope you're enjoying your current language!)

I'm going to use this simple database for storing the entries on this blog. Unfortunately I'll have to wait until Nearly Free Speech get round to updating their version of newLISP to version 10, since I've been using some 10-only constructs.

If you'd like to help test out the code, contact me!

Simple database, second attempt

2009-01-30T22:47:00.001Z

Rewriting is part of a writer's job, and with practice it's easy to be ruthless about your previous drafts. This chap has written more about the process than I ever could.

But it's slightly harder for me to be ruthless when editing code, because once I manage to get something working, I'm reluctant to break it just to try and make it better. But I'm slowly getting the hang of this too.

The simple database I started working on recently was OK, but there were things I didn't like about it. Perhaps the main problem area was with the way I switched between a simple list of lists:

((1 1.0079 "Hydrogen" "H" -259 -253 0.09 0.14 1776 1 13.5984) 
 (2 4.0026 "Helium" "He" -272 -269 0 0 1895 18 24.5874) 
 ...

to a list of association lists, where the keys were the 'column' names:

(((No 1) (AtomicWeight 1.0079) (Name "Hydrogen") ... )
 ((No 2) (AtomicWeight 4.0026) (Name "Helium") ... )
 ...

This happened all the time; virtually every function did this conversion process. Before any rows could be selected, the whole table had to be modified, with keys inserted before every value. Not a good idea with large tables!

So I abandoned the association list approach. You don't really have to use lookup, because nth and find can do a similar job, albeit less easily:

(setf (nth (find column-name columns) row) (eval modify-fn))

I had to rewrite many of the functions, too, because now you always have to know the name of the table you're working on (before, you didn't, because the association list's keys were all you needed). It's a little less easy on the eye now, but more powerful. To select rows, you do this:

(select-rows 'elements '(and (> 'EarthCrust 1) (< 'DiscoveryYear 1900)))

which is slightly different to the old way (there's no where any more):

; old version
(select-rows 'elements (where (and (> 'EarthCrust 5)) (< 'DiscoveryYear 1900)))

The select-rows function now also does column filtering and sorting:

(select-rows 
  'elements                               ; table
  '(> 'EarthCrust 1)                      ; selection criterion
  '(Name Symbol)                          ; columns to return
  'Symbol                                 ; column to sort by
  '(fn (x y) (> (length x) (length y)))   ; sort function 
  )

(You can perhaps see why I still think it would be cool to have named parameters...!)

I've also re-written change-rows so that it can access all columns when making a change. The idea here is that you can change a column's value using a newLISP expression that can access information from other columns in that row:

(change-rows          
  'elements                 ; table              
  '(ends-with 'Name "ium")  ; selection criterion        
  'MP                       ; column to modify 
  '(dec 'BP)                ; expression to apply to column        
)

This changes the Melting Point of every "ium" element to be one less than its Boiling Point. (Yes, I noticed that the 'BP is quoted, when it normally wouldn't be, but it's already been replaced by the actual value when the dec function is called.)

So far, it's looking promising, not much slower than a SQLite database, and doing the same job with fewer functions.

If you'd like to see the second attempt, you can find it here, and there's a simple database to practice with here. I'd be very grateful for any improvements you can suggest!

newLISP all of a Twitter

2009-01-30T22:47:00.000Z

I don't quite understand Twitter but I thought I'd see what all the fuss was about by writing a small plugin for the ParenthesisEngine that picks up newLISP-related twitterings. You can see them in the left margin of the web page.

The only tricky thing is making sure that the information from twitter isn't updated five times a minute, which wouldn't be very considerate.

So far, one of the appealing things I've discovered about Twitter is the fact that messages are limited in length to 140 characters or thereabouts. Compulsory brevity has its good points!

Bits and pieces

2009-01-02T09:41:00.000Z

Happy new year!

It's all been a bit quiet round here recently (I write more code these days), but here are a few miscellaneous bits and pieces of newLISP-related stuff.

newLISP version 10 has been released! It's full of cool things, and it's quicker (slightly) than version 9.4.5. It's not 100% compatible with earlier versions, though, so you'd better read the release notes carefully. The transition to version 10 will take some time: this site is (at the time of writing) running on version 9.3, which is two versions ago now. But any transition takes time. Most of the files in downloads have been updated to version 10.

I've switched off comments on this blog. It's a pity, because I found my automatic newLISP real-time Bayesian comment-spam eliminator worked really well (about 99.5% effective). But there are still far too many comment spammers looking for somewhere to practise, and I don't want them to use my disk space or CPU cycles when they do.

Lutz is very kindly hosting the latest iteration of my Introduction to newLISP tutorial. Apart from making changes related to newLISP 10, the only major improvement for this version is the addition of coloured code listings, for which I had to write some translation code: one to display in HTML (the dreaded tag) and one to output text formatted in the TEX-based system I use, called ConTeXt.

For editing newLISP code, I've found myself back with BBEdit, the classic text editor for Macs. I'm finding the current version, 9.1, to be very adaptable. In the screen shot below, I've just typed the letters "wri". The completion/clippings system in BBEdit is suggesting I use one of six functions, and gives me the syntax for each one. If I select one of these, I'll insert the template at the current insertion point - although that requires me to replace the placeholders. It's very useful for those functions for which I can never remember the order, such as starts-with). Setting it up requires a 10-line newLISP script - let me know if you'd like a copy.

Unfortunately, the 2008 newLISP competition didn't really take off. My contribution is on the downloads page - mycroft, a simple newLISP code profiler. The HTML and CSS code took me much longer to figure out than the newLISP code!

Finally, a mention for a really cool MacOS application called Espionage. It's an excellent encryption and security product. I tried it out and the user experience is first class, and the software does a complicated job in real style. I'm hoping to be able to justify buying it (I don't have many secrets...). Oh, Espionage has no relevance for newLISP that I'm aware of, but I think the author has contributed to the newLISP forums, so he's a pretty talented guy!

Spellbound

2008-12-24T22:57:00.000Z

Update I think he's updated his table, and unsorted the results. No problem. :)

I've been enjoying Peter Norvig's article in which he explores ways of writing software to correct typos and spelling mistakes in English text. You can find it here.

His general idea is to deliberately misspell a wrongly-spelled word in all kinds of simple ways, such as transposing two letters, omitting a letter, including an extra letter, and so on. One of the 'misspellings', if found in a suitable dictionary, is quite likely to be the correct spelling of the original word.

Although it's not the primary point of his article, I can't help noticing that he's secretly quite proud of the brevity of his Python script ("So here, in 21 lines of Python 2.5 code, is the complete spelling corrector"), and he included at the end the current score table of the number of lines of code required by different languages

I don't really get this "lines of code" thing. That's partly because I'm more used to talking about brevity in terms of words or characters, rather than lines. A journalist, asked to produce 150 lines of copy, would immediately ask "How many words in a line?'. And in newLISP (and probably many other languages), there's no real restriction on formatting, because white space is provided for the benefit of the human reader or writer rather than for the machine interpreter or compiler. In one sense, all newLISP programs occupy a single line, since a linefeed is just another way for the human writer to format their code and generally has no significance for the interpreter.

Brevity may well be the soul of wit, but it can also be the first step to unreadable code. A better way to compare the brevity of scripts would be to count how many significant keywords were required, or even how many characters were used, excluding identifiers, which you would obviously want to be expressive and informative rather than cryptic, just for the sake of saving a few letters.

Just for fun, though, I couldn't help but take up the implicit challenge of writing a newLISP version of Peter Norvig's Python script, to see if I could get it as concise without being unintelligible or unidiomatic. I don't know any Python at all, but I felt that his script was as compressed as he could make it without cheating (nested loops on the same line, for example), so I felt I could adopt a similar approach for newLISP.

Here's the Python:

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))
alphabet = 'abcdefghijklmnopqrstuvwxyz'
def edits1(word):
    n = len(word)
    return set([word[0:i]+word[i+1:] for i in range(n)] +                     # deletion
               [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
               [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
               [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet])  # insertion
def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
def known(words): return set(w for w in words if w in NWORDS)
def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=lambda w: NWORDS[w])

As far as I can understand the original, here's a version in newLISP:

(bayes-train (map lower-case (parse (read-file {big.dms}) {\W} 0)) 'Lexicon)
(define (edits1 word) 
 (let ((l (length word)) (res '()))
  (for (i 0 (- l 1)) (push (replace (nth i (string word)) (string word) "") res -1))
  (for (i 0 (- l 2)) (push (swap i (+ i 1) (string word)) res -1))
  (for (i 0 (- l 1)) (for (c (char "a") (char "z")) 
    (push (replace (nth i (string word)) (string word) (char c)) res -1)
    (push (replace (nth i (string word)) (string word) (string (char c) (nth i (string word)) )) res -1)))
  res))
(define (edits2 word) (unique (flat (map edits1 (edits1 word)))))
(define (known-edits2 word) (filter (fn (w) (Lexicon w)) (edits2 word)))
(define (known words) (filter (fn (w) (Lexicon w)) words))
(define (correct word)
  (let ((candidates (or (known (list word)) (known (edits1 word)) (known (edits2 word)))))
    (first (sort candidates (fn (w1 w2) (> (Lexicon w1) (Lexicon w2)))))))

And to test it:

(join (map correct (parse "tihs sentnce is ful of inkorrect spelingz")) " ")

;-> this sentence is full of incorrect spelling

(By the way, this newLISP code runs on versions 9.4 and higher, but doesn't run on 9.3.)

If you allow me the single-line function definitions (like his words function), then I reckon newLISP is about 15 non-blank lines of code.

In fact, character and word counts are pretty similar. And I think the Python version of edits1 is neater than mine - I'm struggling with my string indexing at the moment. But newLISP has bayes-train batteries built in, and it doesn't have to import regular expressions or collections. I have no idea whether it runs fast or slow - I don't have the time to optimize size and performance, or to check whether the code is doing what I thought it was.

As I said, it's just for fun, so don't take it seriously, and I won't try to knock Peter's score off the top on his own web page. But, secretly, just between you and me:

Language	Lines of Code	Author (and link to implementation)
newLISP	15	cormullion
Awk	28	Gregory Grefenstette
C	184	Marcelo Toledo
C++	98	Felipe Farinon
C#	22	Lorenzo Stoakes
Clojure	18	Rich Hickey
D	23	Leonardo M
Erlang	87	Federico Feroldi
F#	16	Dejan Jelovic
F#	34	Sebastian G
Groovy	23Rael Cunha
Haskell	24	Grzegorz
Java	36	Rael Cunha
Java	372	Dominik Schulz
Perl	63	riffraff
PHP	68	Felipe Ribeiro
PHP	103	Joe Sanders
Python	21	Peter Norvig
Rebol	133	Cyphre
Ruby	34	Brian Adkins
Scheme	45	Shiro
Scheme	89	Jens Axel

:-)

Project Nestor: part 1

2008-10-25T10:42:00.000+01:00

Most of my newLISP projects are unfinished and nameless, but my current project, still an early prototype, and still far from being finished, has already managed to acquire a name. It's called Nestor. I needed to call it something, and since it deals with nested lists quite a lot, this was the first name that sprang to mind.

For those of you with a classical education, and/or fans of the film Troy, Nestor was the old soldier in Homer's Iliad who advised King Agamemnon of Mycenae. To be honest, though, I was thinking more of Captain Haddock's butler, Nestor, who runs Marlinspike Hall. After some desperate reverse acronymization, I managed to make NESTOR stand for "newLISP Source Translator Or Reducer.

The general aim is to convert newLISP source code into s-expressions, to extend the classic Lisp principle of allowing a rich interplay between code and data. Although newLISP has functions for converting text into code (read-expr), and for evaluating code passed as text data (eval and eval-string), information is lost in the process. And I'm hoping to preserve the two aspects of source code that are usually discarded: the comments and the white space (ie the formatting). Although these are solely for the benefit of the human reader and writer of code, I think they're an important part of the process, and should be treated as such rather than always discarded.

My first attempt at a recursive descent parser for an LL(0) grammar worked OK. In plain English, that simply meant that the read function scanned the source input from left to right, and called itself recursively to look for the next token. On large source files, though (over 3000 lines), it did require a stack larger than the newLISP default of 2800 elements (so it would have to be run with a larger stack setting), and it wasn't very quick either. I found it hard to control the nesting of the output as the various lists within lists were encountered in the source. And recursion, elegant though it undoubtedly is, has always made me scratch my head a little.

For the next version I went for a more iterative approach, and used a plain list as a stack, controlling the nesting by maintaining a stack pointer in a list:

(define (Stack:Stack i)   
  (push i stack sp)
  (setf (sp -1) (+ 1 (sp -1))))

(define (Stack:inc-nest)
  (push 0 sp -1)
  (push '() stack sp)
  (inc 'nest-level))

(define (Stack:dec-nest)
  (pop sp -1)
  (setf (sp -1) (+ 1 (last sp)))
  (dec 'nest-level))

In the Stack default function, which is used to add items to the stack, push is putting an item on the stack at the location determined by the stack pointer sp, which is just a list of index numbers. The nesting can then be easily controlled by adding or removing indices to sp.

The main scanner works its way through the source, and calls the relevant function. For example, an opening parenthesis is easy:

(define (open-paren-token)
  (Stack:inc-nest)
  (Stack (list "open-paren" "(")))

but some of the others are more complicated, such as the number scanner, which is recursive:

(define (read-number-scanner list-so-far)
  (let ((next-char (peek-char)))
    ;; if next-char is a digit then call self recursively
    (if (and (char-numeric? next-char) next-char)
          (read-number-scanner (cons (get-next-char) list-so-far))
          (reverse list-so-far))))

The top-level function, Nestor:read, converts the following newLISP source:

; get stdin POST method parameters if present
;
(set 'inline (read-line))
(if inline 
  (set 'params (get-vars inline)))

to this list:

("comment" "; get stdin POST method parameters if present")
("comment" ";")
  ("open-paren" "(")
  ("symbol" "set")
  ("whitespace" "IA==")
  ("quote" "'")
  ("symbol" "inline")
  ("whitespace" "IA==")
    ("open-paren" "(")
    ("symbol" "read-line")
    ("close-paren" ")")
  ("close-paren" ")")
("whitespace" "Cg==")
  ("open-paren" "(")
  ("symbol" "if")
  ("whitespace" "IA==")
  ("symbol" "inline")
  ("whitespace" "IAoJ")
    ("open-paren" "(")
    ("symbol" "set")
    ("whitespace" "IA==")
    ("quote" "'")
    ("symbol" "params")
    ("whitespace" "IA==")
      ("open-paren" "(")
      ("symbol" "get-vars")
      ("whitespace" "IA==")
      ("symbol" "inline")
      ("close-paren" ")")
    ("close-paren" ")")
  ("close-paren" ")")

It's wordy, isn't it?! Perhaps I'll switch to abbreviations or code numbers one day, but at the moment I find the longer names really useful. And the format isn't going to be used for permanent data storage, just for temporary processing. The whitespace is stored in base64 encoding - again, this may not be the best choice, but for now it works OK.

Now that I've got this newLISP expression, or nl-expression, perhaps the most obvious and important function is the logical inverse of Nestor:read, Nestor:nlx-to-text, which converts the nl-expression back to plain source form. Fortunately it's easy, and a natural application for a recursive function:

(define (nlx-to-text nlxp)
  (dolist (i nlxp)
  (if (atom? (first i))
     (begin
       (cond 
         ((= (first i) "symbol") 
              (write-buffer buff (string (last i))))
         ((= (first i) "open-paren") 
              (write-buffer buff (string  {(})))
         ((= (first i) "close-paren") 
              (write-buffer buff (string  {)})))
         ((= (first i) "whitespace") 
              (dostring (s (base64-dec (last i))) 
                (write-buffer buff (string (char s)))))
      ; and so on with other element types
      ))
     ; not an atom, recurse
     (nlx-to-text i))))

When this completes, the buffer buff should contain the de-nested source code.

When I tested this approach against the official newLISP installation, I was pleasantly surprised that all the modules converted to and from nl-expressions without error. In other words, given some newLISP in source-text:

(= source-text (Nestor:nlx-to-text (Nestor:read source-text)))

usually returns true.

However, there are problems. For one thing, I'm embarassed that the presence of one or more Unicode characters will kill the translator stone dead. I've no idea what the cause is yet, but I hope it's fixable.

There are other things on my to-do list that will be done soon: nested braces in strings, for example. But there are some aspects of the language that I probably won't be able to handle at all. The newLISP interpreter is a strange and powerful beast, and my own scripting is never going to be able to match it:

1.2.3e4e5                          ; three tokens: 1.2 .3e4 e5 ?
(println"hi there")                ; no space?
string}                            ; weird symbol or string typo?
(set '[ you're (not) joking ] 0)   ; wacky symbol names in brackets?

That first one was aptly described as a monster! Does anyone use these newLISP constructions in their code?

The first application for Nestor is to re-introduce the syntax colouring of newLISP source code that appeared about a year ago on this site and disappeared during the revamp in March this year. If you're seeing newLISP code in colour then it's working. More on that another day.

Going API

2008-10-06T00:02:00.000+01:00

I've been playing with the Google chart API, and it's a great way of inserting charts into your web pages. Here, for example, is a pie chart showing the relative sizes of the different directories in this web site:

This chart is generated by Google automatically whenever the page is loaded. Originally it was a live chart, produced by examining the current file system every time the page was loaded, but this made the page take too long to generate... :)

Charts can be generated using this newLISP function:

(define (pie-chart 
  (chs "400x200") 
  (chd "t:60,40") 
  (cht "p3") 
  (chl "Hello|World") 
  (chalt "Sample Google Chart"))
  (format 
    {}
    chs chd cht chl chalt))

which is called like this:

- --(Route.Blog:pie-chart  "600x200" "t:10.79,1.07,42.80,2.15,19.42,3.59,18.70,1.43" "p3" "views|resources|jack-the-glypher|includes|images|dragonfly-framework|downloads|databases") - --

although there shouldn't be spaces between the three "-" signs (see here for details).

This following little bit of code is useful for converting numbers into percentages, because the pie chart expects percentage values by default:

(define (make-percentages)
  (let ((total 0))
     (set 'total (apply add (args)))
     (map (fn (f) (mul 100 (div f total))) (args))))
     
(make-percentages 300 800)
;->(27.27272727 72.72727273)

Reasons to learn newLISP

2008-08-20T18:41:00.000+01:00

It's that time of the year when many people face new academic challenges, so now's a great time to learn newLISP! Here are some - frankly quite biased - suggestions as to why newLISP is a good choice for a first - or second or third - programming language. By the way, most of these suggestions are true of most programming languages.

1 It's easy

newLISP is easy to download, install, and use. For most operating systems you'll find an installer and/or prebuilt versions. You won't have to build, compile, or make the software, and running it is as easy as typing its name.

It's easy to program in, too. The carefully-designed syntax aims for readability and write-ability, without introducing too many special forms and conventions. Obscure function names have been replaced by more English-like ones, and the temptation to make use of every punctuation mark known to humankind has been resisted, for the most part. Although sadly I don't think we'll ever be able to say goodbye regular expressions. And there are some great introductory tutorials too. (I wrote one of them, so I'm biased!)

'easy' isn't always the main reason for doing anything. Sometimes we do things not because they're easy, but because they are hard. Sometimes we have to use things that aren't easy to use to solve hard problems. But easy can be good when you're learning something new. You probably didn't learn to drive a car in a Ferrari...

2 It's small

It would be hard to find a memory card on sale today with a capacity too small to hold newLISP - if you can find a 512KB memory card you'll have plenty of room to spare.

More seriously: it's a compact language that tries to provide everything you need and dispenses with much that you don't. With about 350 functions, it's a reasonably complete basic programmer's toolkit without the complexity and advanced features of the larger languages. You can worry about making it bigger - or moving to a bigger language - later, when (or if) you outgrow it.

Yes, it hasn't got sub-atomic reference de-clustering, quasi-optimal cyclical redundancy, or meta-stable bytecode traversal, to name just a few of the language's most obvious omissions, but there's plenty of useful tools to get you started. (I made those up, by the way, but that doesn't mean that they don't actually exist...)

3 It's fast

newLISP is quick enough for most purposes, so you shouldn't have too many problems with speed. For extra performance you can learn how to link to compiled C libraries, or write assembly code (two things which I've managed to avoid so far). The 50,000 word introduction I mentioned above is translated in about 0.4 seconds, which is too quick for me - better to take 10 seconds so that I can drink some coffee...

4 It's versatile

Use newLISP to explore programming concepts, crunch numbers, write internet applications, analyze text documents, post rubbish to blogs, or compose music. You can learn many different styles of programming in newLISP: casual scripting (my favourite!), imperative programming, functional programming, object-oriented programming, and even a form of macro programming - you'll be working with newLISP for a long time before you've exhausted newLISP's potential and are ready to move on to bigger and more complex languages (if you want to). Instead of just following what other people tell you is the 'right' way, why not try the different styles and make your own mind up?

You don't have to be a mathematician or computer scientist to use newLISP: musician, writer, artist, sysadmin, architect, web developer, surveyor, mathematician, tinker, tailor, soldier, sailor - if your work involves the computer, it could benefit if that computer works harder for you.

This is the sort of newLISP I use all the time:

(set 'dir (real-path))
(dolist (i (directory dir {^[^.]}))
 (set 'item (string dir "/" i))
 (set 'mod-date (date (file-info item 6) 0 "%Y%m%d-%H%M%S"))
 (rename-file item (string dir "/" mod-date i)))

which simply renames files based on their modification dates. But others are into newLISP like this:

 (let ((g (lambda (h) 
          (expand (lambda (n) 
            (let ((f (lambda (f n) 
                    (if (< n 2) 1 (* n (f (- n 1))))))) 
            (f (h h) n))) 'h))))
       ((g g) 10))

which is something to do with the Y function.

5 It's different

newLISP is certainly not your Dad's Lisp, and there's plenty of tutting in some of the online communities who get easily worked up by the different. But perhaps you're ready to find out for yourself what you think is good or bad, and perhaps you like to avoid doing the obvious and predictable. Or at least prove to your own satisfaction that your Dad was right all along.

6 It's friendly

On the newLISP forum, genuine questions usually receive genuine answers. You probably won't encounter the uncompromising attitudes that newcomers to other languages occasionally encounter. You might even get help from Lutz, the language's author.

7 It's not finished

newLISP is still developing. There's room for contributions from you: plenty of investigations and discoveries still to be made, plenty of code and applications still to be written, and many subjects for writing and blogging about. If you want to take an active part in its development, there are plenty of oportunities waiting for you. You might even get your own function included in the next release (but it will have to be a really good idea!). It won't be named after you, though.

8 It's fun

Is programming fun? It's not always fun; sometimes the code doesn't do what you thought you told it to do. But newLISP has got to be fun, because the slogan says it is!

9 It's free

Of course, sometimes the best things in life are free!

Two (or more) challenges for the weekend

2008-08-02T11:04:00.000+01:00

What's the point of the following line at the start of this newLISP blog script?

(if (unless nil nil true) (exit))

See if you can get your comment through the impassable barrier that is the newLISP Bayesian Comment Spam Killer below! (No, it won't kill Bayesian comemnts - although it might - but it tries to kill spam comments using Bayesian analysis.)

Looking for things

2008-07-31T20:36:00.000+01:00

When writing newLISP, it's often useful to find any existing code that uses a particular function or symbol name. I'm a fan of both the Unix find command and the Mac's built-in search tool, Spotlight. The former is all-powerful, but it can be a little tricky to remember all those options. The latter is particularly good for finding text in documents - not just text files - since many developers provide a Spotlight system plug-in for searching their own document types.

Naturally, though, I also use a small newLISP utility alongside these two: its purpose is to look only in places where there are newLISP-related files. I reworked this recently based on some suggestions in the newLISP forum. Here's the code:

#!/usr/bin/env newlisp
(context 'Look4)

(constant 'extensions '("lsp" "txt" "html")) 

(set 'places 
  (list (string (env "HOME") "/projects/lisp")
        (string (env "HOME") "/projects/webapps")
        (string (env "HOME") "/projects/guiapps")
        (string (env "HOME") "/projects/tech-writing")
        "/usr/share/newlisp"))

(define (string-ends-with L str) 
  (exists (fn (x) (ends-with str x)) L))

(define (look-in-file pn)
 (let (contents "" res '())
  (when (string-ends-with extensions pn)
     (set 'file (open pn "r"))
     (while (search file (string "(.*?" Term ".{10,20})") true 1)
        (push $1 res -1))
     (close file)
     (if res (list pn res)))))

(define (Look4:Look4 dir)
   (dolist (nde (directory dir "^[A-z]"))
     (set 'item (append dir "/" nde))
     (if (directory? item)
       (Look4 item)
       (when (set 'r (look-in-file item Term)) (inc 'counter) (push r results)))))

(when (>= (length (main-args)) 2) 
  (set 'Term (main-args 2) 'counter 0)
  (map Look4 places)
  (when results
    (sort results)
    (dolist (r results)
        (println "\n" (r 0) "\n\t\t\t")
        (dolist (e (r 1)) (println "\t" e)))
        (println "Found " counter " occurrences of \"" Term "\"")))

(exit)

You can see that I've hardwired the names of the directories to search in. That's not very flexible, but it may suit your working style.

On the command line, you run the script and supply a string:

$ look4 unless

and you'll see the results in a couple of seconds:

...
/Users/me/projects/lisp/tokenizer.lsp

    (unless txt (exit))

/usr/share/newlisp/guiserver.lsp

;; a Piano instrument unless the function 'gs:mi

/usr/share/newlisp/modules/smtp.lsp

      (unless (and (empty?  user-

/usr/share/newlisp/util/nanorc

color blue "([[:space:]()]|^)(trim|true|true\?|unicode|unify|unique|unless|unpack|until|upper-
...

Found 201 occurrences of "unless"
$

Since the search is a regular expression one, it might be possible to supply a regex-friendly string, if you escape all the regex characters, but I find that I rarely use regular expressions in this type of search. I'm more likely to be asking "Didn't I once write a binary function?".

Character reference

2008-07-25T23:43:00.000+01:00

I was looking through an old (1990!) book on Unicode the other day. I've always been intrigued by the amazing diversity of letter forms that we've created over the last few thousand years. Here are just some of the many wonderful and peculiar characters you'll find tucked away in the Unicode glyph banks:

You'll also find the I Ching, Braille, alchemy, an alphabet funded by George Bernard Shaw, neo-pagan tree language, astrology, dentists, talking leaves, and much more besides.

Most of the technical aspects of Unicode escape me (supplementary planes, normalization, high surrogates, collation?) but it's useful to know the basics of using Unicode in newLISP, particularly now that it's the most popular encoding used on the internet.

newLISP is UTF-8 friendly by default on MacOS X, and UTF-8 versions are available for other platforms too (although I'm not sure whether the default versions are UTF-8). UTF-8 is a variable-length character encoding, which allows characters to use 1, 2, 3 or 4 bytes depending on their Unicode value.

One essential newLISP function for exploring the Unicode character set is char. This takes either a number or a character, and returns the matching character or number:

(char 63498)
""

(char "")
63498

Unicode characters are usually described using hexadecimal, so it's useful to know how to translate between hex and decimal. To convert a decimal integer to a hex string, use format:

(format "%llx" 63498)
"f80a"

To convert a hex string to a decimal integer, pass a hexadecimal string starting with "0x" to int :

(int (string "0x" "f80a"))
63498

When you're writing text, it would be good if you could easily insert these characters as you type. There are useful system tools for doing this (on MacOS X, there's the Character Palette), but for fun I've added the following two functions to the Markdown converter that I use to process my writing:

(define (hex-str-to-unicode-char strng)
   (char (int (string "0x" (1 strng)) 0 16)))

(define (ustring s)
  (replace "U[0-9a-f]{4,}" s (hex-str-to-unicode-char $0) 1))

So now I can type "U" followed by 4 hexadecimal characters, and the appropriate Unicode character is inserted automatically: "U f80a" is converted to "". (I had to insert a space after the U to prevent translation.)

You can happily use Unicode characters anywhere in newLISP code, if your text editor or console is up to the job. And if ustring is available, you can generate them easily too:

(constant (sym (ustring "U 2660")) 4  ; spades
       (sym (ustring "U 2661"))      3  ; hearts
       (sym (ustring "U 2662"))      2  ; diamonds
       (sym (ustring "U 2663"))      1  ; clubs
     )

(symbols)

(! != $ $0 $1 $10 $11 $12 $13 $14 $15 $2 $3 $4 $5 $6 $7 $8 $9 $HOME $args $idx $main-args ...  zero? | ~ ♠ ♡ ♢ ♣)

(println "(> ♢ ♣)? " (> ♢ ♣))
(> ♢ ♣)? true

(println "(> ♡ ♠)? " (> ♡ ♠))
(> ♡ ♠)? nil

Using descriptive Unicode characters for your symbol names could introduce a whole new level of readability to your code!

(constant (global '☼)  MAIN)
(context '☺)

(define (☻ ✄ ☁ ⍾)
   (print ✄ ☁ ⍾))

(define (‽) 
   (println {‽}))

(context ☼)
(set '℥ "what "  'ᴥ "the " 'ᴒ "dickens")
(☺:☻ ℥ ᴥ ᴒ)
(☺:‽)

Appropriately enough, that last function call returns "‽", which is the much-needed interrobang character.

The problem now is to remember all those four digit hexadecimal numbers that identify the Unicode characters. I whipped up a quick Unicode browser in newLISP:

This just shows a page of Unicode characters at a time, and lets you move up and down through the 'pages'. It has some problems when the character code exceeds FFFF - I don't know why‽

This post should display correctly on most modern browsers. If you see lots of boxes rather than characters, then you are using a browser or system that doesn't handle Unicode well. This applies to the iPhone and iPod Touch as well: it appears that Mobile Safari doesn't like Unicode as much as its desktop version. Apple - improve Unicode support please!

googled again

2008-07-13T20:31:00.000+01:00

In the top right corner of this page you'll see a search box. This is a custom Google search engine, and it's currently set to search three newLISP-related sites using Google technology: this one, the main newLISP site at newlisp.org, and the newLISP on Noodles wiki. I didn't want to add anyone else's site without their permission or knowledge, but it's easy to add extra sites, so just let me know if you'd like yours added.

So far I've found it fairly useful, and it's meant that I haven't had to write my own blog search tool yet. However, it's been doing odd things with the HTML display of the page, generating thousands of Javascript errors and doing weird stuff like (apparently) loading the page more than once. Also, it fails to find things that I think it should, so I'm not convinced it's as good as Google engineers apparently think it is.

If anyone is at all knowledgeable about what the custom Google search engine is doing with its HTML, please help! The Google engineers can't be bothered to help anyone use their work it seems, so I'm on my own. Perhaps I'll have to write my own search engine after all...!

Simple help for newLISP

2008-06-27T18:33:00.003+01:00

An interesting discussion about an online help facility for newLISP threw up lots of interesting ideas and useful suggestions. One advantage to not having certain facilities built in is that it gives you scope for making them yourself. This version I threw together is simple enough:

(define (help func-name)
   (if (find func-name "|+*-") (push "\\" func-name))
   (set 'html-text (join (find-all (format {(syntax: \(%s.*?)} func-name) 
      (read-file "/usr/share/doc/newlisp/newlisp_manual.html")) "\n"))
  (println (replace "<.*?>" html-text "" 0))
  (silent))

> (help "date")
syntax: (date)
syntax: (date int-secs [int-offset])
syntax: (date int-secs int-offset str-format)
syntax: (date-value int-year int-month int-day [int-hour int-min int-sec])

The first line of the function was a temporary fix for a puzzling bug, and it also offered a nice surprise. The bug was that it was impossible to get help on functions with names like | or + without listing way too much. I eventually realized (duh) that some newLISP symbols were also significant in regular expressions and needed to be escaped. Because no symbols use the period (.), I hadn't bothered to escape it. But it then becomes a useful option for searching for functions:

> (help "fi.")
syntax: (file-info str_name [int-index])
syntax: (file? str-name)
syntax: (filter exp-predicate exp-list)
syntax: (find exp-key list [func-compare | int-option])
syntax: (find str-key str-data [int-option])
syntax: (find-all str-pattern str-text [expr [int-option]])
syntax: (find-all list-pattern list-lists [expr])
syntax: (find-all expr-key list expr func-compare)
syntax: (first list)
syntax: (first array)
syntax: (first str)

The only thing left to do now is to work out how to avoid using silent. Although I want to suppress the value returned by println, I don't want the prompt to disappear as well. Unfortunately, silent does both. I bet there's a way, though!

Smashing the Atom

2008-06-27T18:33:00.002+01:00

Despite my attempts to get the Atom news feed working for this site, it still doesn't work. I'm not clear what the problem is - something to do with the way the page is served, rather than the syntax or the content. I've been hunting on the web for information about whether to serve pages with "Content-Type: application/atom+xml" headers or not, followed by carriage returns or not, without a lot of success.

I'll have a go at fixing it in the next week.

I was quite pleased that the code to produce the Atom document was only about 45 lines, though.

Edit

I discovered how to make it work: I used a content type of text/xml:

(set '*content-type* "text/xml\n\n")

and claimed that I was generating it using a file called 'atom.cgi', although I'm not.

So now I can put this on my page, apparently:

Two out of three - TicTacToe

2008-06-27T18:33:00.001+01:00

After a mention of TicTacToe in the newLISP forums, I thought I'd take a look at writing a version of what we used to call Noughts and Crosses for myself. Peter posted a link to his excellent version, which plays a perfect game from the command line. So, to be different, I decided to start from the other end and write a GUI version using newLISP-GS.

There are basically three tasks to do: do the basic game mechanics, implement a user interface, and add a dash or two of intelligent strategy.

The game mechanics are simple enough. You need a board:

(set '*grid* (dup nil 9))

and a list of winning positions:

(set '*winning-positions* 
   '((0 1 2) (3 4 5) (6 7 8) (0 3 6) (1 4 7) (2 5 8) (0 4 8) (2 4 6)))

Each move places a 'X or 'O symbol in the grid, using set-nth or nth-set:

(set-nth (*grid* a-move) 'X)

There's also a function to find the moves still available:

(define (available-moves)
  (index nil? *grid*))

and a function to check whether a proposed move is valid:

(define (check-move move)
  (and (<= 0 move 8) (find move (available-moves))))

Here's a function to see if a player has won:

(define (won? player)
   (letn ((player-squares (index (fn (x) (= x player)) *grid*))
          (wins-for-player 
             (map (fn (win) (= win (intersect win player-squares))) *winning-positions*)))
      (if (exists true? wins-for-player)
          (set '*winner* (list player (find true wins-for-player))))))

This uses the intersect function, which I haven't used much before. The idea is that the set of grid squares occupied by a player might equal or contain the set of numbers which constitute a winning position:

(set 'win '(2 5 8))
(intersect '(2 5 8) '(2 3 5 7 8))
;-> (2 5 8)
(= win (intersect win '(2 3 5 7 8)))
;-> true

I wonder if there's a simpler way to see whether '(2 3 5 7 8) contains '(2 5 8)?

Add a game-over? function:

(define (game-over?)
  (or (won? 'X) (won? 'O) (empty? (available-moves))))

and the mechanics are mostly done.

I found the user interface task a bit harder. The problem is that you have to use an event-driven model, but the only event that's going to happen is the user clicking a square to place a 'X. So inside the main loop:

(do-until (game-over?) (gs:check-event 1000000))

everything has to be driven by mouse clicks. I ended up with something like this:

(define (do-human-move move)
  (and (not (game-over?) (= *turn* "human"))
       (check-move move)
       (set-nth (*grid* move) 'X)
       (display)
       (set '*turn* "computer")
       (do-computer-move)
       (display)))

which kind of works - and you can see now why I used set-nth. You might think that nth-set would do the job perfectly, and it does, but it returns the value of the replaced element, which, being nil, finished the and clause too early.

And what about the third task, adding the intelligent strategy? This is certainly the most interesting part of the job, but I haven't had the time to start it yet. I've been testing with the simplest possible strategy:

(define (generate-computer-move)
  (apply amb (available-moves)))

Here, amb has to be applyed to a list; unlike randomize, it takes single arguments rather than a single list.

Perhaps one day I'll get round to starting the third task. If you want to help me, get the file from the downloads page and get coding!

Vacuum-tube Lisp

2008-06-27T18:33:00.000+01:00

I love the idea of a vacuum-tube computer running Lisp. Here's Steve Russell:

I wrote the first implementation of a LISP interpreter on the IBM 704 at MIT in early in 1959.

The 704 family (704, 709, 7090) had "Address" and "Decrement" fields that were 15 bits long in some of the looping instructions. There were also special load and store instructions that moved these 15-bit addresses between memory and the index regiseters ( 3 on the 704, 7 on the others )

We had devised a representation for list structure that took advantage of these instructions.

Because of an unfortunate temporary lapse of inspiration, we couldn't think of any other names for the 2 pointers in a list node than "address" and "decrement", so we called the functions CAR for "Contents of Address of Register" and CDR for "Contents of Decrement of Register".

After several months and giving a few classes in LISP, we realized that "first" and "rest" were better names, and we (John McCarthy, I and some of the rest of the AI Project) tried to get people to use them instead.

Alas, it was too late! We couldn't make it stick at all. So we have CAR and CDR.

Like Steve, I much prefer first and rest to car and cdr. This approach is evident throughout newLISP, which usually leans towards a user-friendly and abbreviation-free approach to function naming.

But, although car and cdr have been uninspired for nearly 50 years, they have survived because they offer an extra geeky ability: you can add more a and d letters between the "c" and "r", to produce functions with even weirder names. So caddr finds the car of the cdr of the cdr; you read from left to right, although the functions are applied from right to left as usual.

To be honest, I don't know how I've managed to write any code at all in newLISP without having this readable and user-friendly syntax at my fingertips. So it's time for newLISP to be 'cdadderized':

(define (car x) (first x))
(define (cdr x) (rest x))

(define (cdadderize x) 
  (inc 'x)
  (set 'results '())
  (until (= x 0)
     (push   (% x 2) results)
     (set 'x (/ x 2)))
  (set 'results (rest results) 'f-name results)
  (map (fn (a b) (replace a results b)) '(0 1) '("(car " "(cdr "))
  (push (string "x"  (dup ")" (length results))) results -1)
  (set 'results (join results))
  (map (fn (a b) (replace a f-name b)) '(0 1) '("a" "d"))
  (letex ((fnm   (sym (string "c" (join f-name) "r")))
          (body results))
    (define (fnm x) (eval-string body))
    fnm))

(for (i 3 1022) (cdadderize i)) ; we did 1 and 2 :)

Not the prettiest code, but let's run it and look at the new functions that have been defined:

(filter (fn (s) 
    (and (starts-with  (name s) "ca|cd" 0) 
         (ends-with (name s) "r"))) 
    (symbols))
;->
(caaaaaaaaaar caaaaaaaaadr caaaaaaaaar caaaaaaaadr caaaaaaaar caaaaaaadar caaaaaaaddr 
caaaaaaadr caaaaaaar caaaaaadaar caaaaaadadr caaaaaadar caaaaaaddar caaaaaadddr 
caaaaaaddr caaaaaadr caaaaaar caaaaadaaar caaaaadaadr caaaaadaar caaaaadadar caaaaadaddr 
caaaaadadr caaaaadar caaaaaddaar caaaaaddadr caaaaaddar caaaaadddar caaaaaddddr 
caaaaadddr caaaaaddr caaaaadr caaaaar caaaadaaaar caaaadaaadr caaaadaaar caaaadaadar 
caaaadaaddr caaaadaadr caaaadaar caaaadadaar caaaadadadr caaaadadar caaaadaddar 
caaaadadddr caaaadaddr caaaadadr caaaadar caaaaddaaar caaaaddaadr caaaaddaar caaaaddadar 
caaaaddaddr caaaaddadr caaaaddar caaaadddaar caaaadddadr caaaadddar caaaaddddar 
caaaadddddr caaaaddddr caaaadddr caaaaddr caaaadr caaaar caaadaaaaar caaadaaaadr 
caaadaaaar caaadaaadar caaadaaaddr caaadaaadr caaadaaar caaadaadaar caaadaadadr 
caaadaadar caaadaaddar caaadaadddr caaadaaddr caaadaadr caaadaar caaadadaaar caaadadaadr 
caaadadaar caaadadadar caaadadaddr caaadadadr caaadadar caaadaddaar caaadaddadr 
caaadaddar caaadadddar caaadaddddr caaadadddr caaadaddr caaadadr caaadar caaaddaaaar 
caaaddaaadr caaaddaaar caaaddaadar caaaddaaddr caaaddaadr caaaddaar caaaddadaar 
caaaddadadr caaaddadar caaaddaddar caaaddadddr caaaddaddr caaaddadr caaaddar caaadddaaar 
caaadddaadr caaadddaar caaadddadar caaadddaddr caaadddadr caaadddar caaaddddaar 
caaaddddadr caaaddddar caaadddddar caaaddddddr caaadddddr caaaddddr caaadddr caaaddr 
caaadr caaar caadaaaaaar caadaaaaadr caadaaaaar caadaaaadar caadaaaaddr caadaaaadr 
caadaaaar caadaaadaar caadaaadadr caadaaadar caadaaaddar caadaaadddr caadaaaddr 
caadaaadr caadaaar caadaadaaar caadaadaadr caadaadaar caadaadadar caadaadaddr caadaadadr 
caadaadar caadaaddaar caadaaddadr caadaaddar caadaadddar caadaaddddr caadaadddr 
caadaaddr caadaadr caadaar caadadaaaar caadadaaadr caadadaaar caadadaadar caadadaaddr 
caadadaadr caadadaar caadadadaar caadadadadr caadadadar caadadaddar caadadadddr 
caadadaddr caadadadr caadadar caadaddaaar caadaddaadr caadaddaar caadaddadar caadaddaddr 
caadaddadr caadaddar caadadddaar caadadddadr caadadddar caadaddddar caadadddddr 
caadaddddr caadadddr caadaddr caadadr caadar caaddaaaaar caaddaaaadr caaddaaaar 
caaddaaadar caaddaaaddr caaddaaadr caaddaaar caaddaadaar caaddaadadr caaddaadar 
caaddaaddar caaddaadddr caaddaaddr caaddaadr caaddaar caaddadaaar caaddadaadr caaddadaar 
caaddadadar caaddadaddr caaddadadr caaddadar caaddaddaar caaddaddadr caaddaddar 
caaddadddar caaddaddddr caaddadddr caaddaddr caaddadr caaddar caadddaaaar caadddaaadr 
caadddaaar caadddaadar caadddaaddr caadddaadr caadddaar caadddadaar caadddadadr 
caadddadar caadddaddar caadddadddr caadddaddr caadddadr caadddar caaddddaaar caaddddaadr 
caaddddaar caaddddadar caaddddaddr caaddddadr caaddddar caadddddaar caadddddadr 
caadddddar caaddddddar caadddddddr caaddddddr caadddddr caaddddr caadddr caaddr 
caadr caar cadaaaaaaar cadaaaaaadr cadaaaaaar cadaaaaadar cadaaaaaddr cadaaaaadr 
cadaaaaar cadaaaadaar cadaaaadadr cadaaaadar cadaaaaddar cadaaaadddr cadaaaaddr 
cadaaaadr cadaaaar cadaaadaaar cadaaadaadr cadaaadaar cadaaadadar cadaaadaddr cadaaadadr 
cadaaadar cadaaaddaar cadaaaddadr cadaaaddar cadaaadddar cadaaaddddr cadaaadddr 
cadaaaddr cadaaadr cadaaar cadaadaaaar cadaadaaadr cadaadaaar cadaadaadar cadaadaaddr 
cadaadaadr cadaadaar cadaadadaar cadaadadadr cadaadadar cadaadaddar cadaadadddr 
cadaadaddr cadaadadr cadaadar cadaaddaaar cadaaddaadr cadaaddaar cadaaddadar cadaaddaddr 
cadaaddadr cadaaddar cadaadddaar cadaadddadr cadaadddar cadaaddddar cadaadddddr 
cadaaddddr cadaadddr cadaaddr cadaadr cadaar cadadaaaaar cadadaaaadr cadadaaaar 
cadadaaadar cadadaaaddr cadadaaadr cadadaaar cadadaadaar cadadaadadr cadadaadar 
cadadaaddar cadadaadddr cadadaaddr cadadaadr cadadaar cadadadaaar cadadadaadr cadadadaar 
cadadadadar cadadadaddr cadadadadr cadadadar cadadaddaar cadadaddadr cadadaddar 
cadadadddar cadadaddddr cadadadddr cadadaddr cadadadr cadadar cadaddaaaar cadaddaaadr 
cadaddaaar cadaddaadar cadaddaaddr cadaddaadr cadaddaar cadaddadaar cadaddadadr 
cadaddadar cadaddaddar cadaddadddr cadaddaddr cadaddadr cadaddar cadadddaaar cadadddaadr 
cadadddaar cadadddadar cadadddaddr cadadddadr cadadddar cadaddddaar cadaddddadr 
cadaddddar cadadddddar cadaddddddr cadadddddr cadaddddr cadadddr cadaddr cadadr 
cadar caddaaaaaar caddaaaaadr caddaaaaar caddaaaadar caddaaaaddr caddaaaadr caddaaaar 
caddaaadaar caddaaadadr caddaaadar caddaaaddar caddaaadddr caddaaaddr caddaaadr 
caddaaar caddaadaaar caddaadaadr caddaadaar caddaadadar caddaadaddr caddaadadr caddaadar 
caddaaddaar caddaaddadr caddaaddar caddaadddar caddaaddddr caddaadddr caddaaddr 
caddaadr caddaar caddadaaaar caddadaaadr caddadaaar caddadaadar caddadaaddr caddadaadr 
caddadaar caddadadaar caddadadadr caddadadar caddadaddar caddadadddr caddadaddr 
caddadadr caddadar caddaddaaar caddaddaadr caddaddaar caddaddadar caddaddaddr caddaddadr 
caddaddar caddadddaar caddadddadr caddadddar caddaddddar caddadddddr caddaddddr 
caddadddr caddaddr caddadr caddar cadddaaaaar cadddaaaadr cadddaaaar cadddaaadar 
cadddaaaddr cadddaaadr cadddaaar cadddaadaar cadddaadadr cadddaadar cadddaaddar 
cadddaadddr cadddaaddr cadddaadr cadddaar cadddadaaar cadddadaadr cadddadaar cadddadadar 
cadddadaddr cadddadadr cadddadar cadddaddaar cadddaddadr cadddaddar cadddadddar 
cadddaddddr cadddadddr cadddaddr cadddadr cadddar caddddaaaar caddddaaadr caddddaaar 
caddddaadar caddddaaddr caddddaadr caddddaar caddddadaar caddddadadr caddddadar 
caddddaddar caddddadddr caddddaddr caddddadr caddddar cadddddaaar cadddddaadr cadddddaar 
cadddddadar cadddddaddr cadddddadr cadddddar caddddddaar caddddddadr caddddddar 
cadddddddar cadddddddddr caddddddddr cadddddddr caddddddr cadddddr caddddr cadddr 
caddr cadr car cdaaaaaaaar cdaaaaaaadr cdaaaaaaar cdaaaaaadar cdaaaaaaddr cdaaaaaadr 
cdaaaaaar cdaaaaadaar cdaaaaadadr cdaaaaadar cdaaaaaddar cdaaaaadddr cdaaaaaddr 
cdaaaaadr cdaaaaar cdaaaadaaar cdaaaadaadr cdaaaadaar cdaaaadadar cdaaaadaddr cdaaaadadr 
cdaaaadar cdaaaaddaar cdaaaaddadr cdaaaaddar cdaaaadddar cdaaaaddddr cdaaaadddr 
cdaaaaddr cdaaaadr cdaaaar cdaaadaaaar cdaaadaaadr cdaaadaaar cdaaadaadar cdaaadaaddr 
cdaaadaadr cdaaadaar cdaaadadaar cdaaadadadr cdaaadadar cdaaadaddar cdaaadadddr 
cdaaadaddr cdaaadadr cdaaadar cdaaaddaaar cdaaaddaadr cdaaaddaar cdaaaddadar cdaaaddaddr 
cdaaaddadr cdaaaddar cdaaadddaar cdaaadddadr cdaaadddar cdaaaddddar cdaaadddddr 
cdaaaddddr cdaaadddr cdaaaddr cdaaadr cdaaar cdaadaaaaar cdaadaaaadr cdaadaaaar 
cdaadaaadar cdaadaaaddr cdaadaaadr cdaadaaar cdaadaadaar cdaadaadadr cdaadaadar 
cdaadaaddar cdaadaadddr cdaadaaddr cdaadaadr cdaadaar cdaadadaaar cdaadadaadr cdaadadaar 
cdaadadadar cdaadadaddr cdaadadadr cdaadadar cdaadaddaar cdaadaddadr cdaadaddar 
cdaadadddar cdaadaddddr cdaadadddr cdaadaddr cdaadadr cdaadar cdaaddaaaar cdaaddaaadr 
cdaaddaaar cdaaddaadar cdaaddaaddr cdaaddaadr cdaaddaar cdaaddadaar cdaaddadadr 
cdaaddadar cdaaddaddar cdaaddadddr cdaaddaddr cdaaddadr cdaaddar cdaadddaaar cdaadddaadr 
cdaadddaar cdaadddadar cdaadddaddr cdaadddadr cdaadddar cdaaddddaar cdaaddddadr 
cdaaddddar cdaadddddar cdaaddddddr cdaadddddr cdaaddddr cdaadddr cdaaddr cdaadr 
cdaar cdadaaaaaar cdadaaaaadr cdadaaaaar cdadaaaadar cdadaaaaddr cdadaaaadr cdadaaaar 
cdadaaadaar cdadaaadadr cdadaaadar cdadaaaddar cdadaaadddr cdadaaaddr cdadaaadr 
cdadaaar cdadaadaaar cdadaadaadr cdadaadaar cdadaadadar cdadaadaddr cdadaadadr cdadaadar 
cdadaaddaar cdadaaddadr cdadaaddar cdadaadddar cdadaaddddr cdadaadddr cdadaaddr 
cdadaadr cdadaar cdadadaaaar cdadadaaadr cdadadaaar cdadadaadar cdadadaaddr cdadadaadr 
cdadadaar cdadadadaar cdadadadadr cdadadadar cdadadaddar cdadadadddr cdadadaddr 
cdadadadr cdadadar cdadaddaaar cdadaddaadr cdadaddaar cdadaddadar cdadaddaddr cdadaddadr 
cdadaddar cdadadddaar cdadadddadr cdadadddar cdadaddddar cdadadddddr cdadaddddr 
cdadadddr cdadaddr cdadadr cdadar cdaddaaaaar cdaddaaaadr cdaddaaaar cdaddaaadar 
cdaddaaaddr cdaddaaadr cdaddaaar cdaddaadaar cdaddaadadr cdaddaadar cdaddaaddar 
cdaddaadddr cdaddaaddr cdaddaadr cdaddaar cdaddadaaar cdaddadaadr cdaddadaar cdaddadadar 
cdaddadaddr cdaddadadr cdaddadar cdaddaddaar cdaddaddadr cdaddaddar cdaddadddar 
cdaddaddddr cdaddadddr cdaddaddr cdaddadr cdaddar cdadddaaaar cdadddaaadr cdadddaaar 
cdadddaadar cdadddaaddr cdadddaadr cdadddaar cdadddadaar cdadddadadr cdadddadar 
cdadddaddar cdadddadddr cdadddaddr cdadddadr cdadddar cdaddddaaar cdaddddaadr cdaddddaar 
cdaddddadar cdaddddaddr cdaddddadr cdaddddar cdadddddaar cdadddddadr cdadddddar 
cdaddddddar cdadddddddr cdaddddddr cdadddddr cdaddddr cdadddr cdaddr cdaderizer 
cdadr cdar cddaaaaaaar cddaaaaaadr cddaaaaaar cddaaaaadar cddaaaaaddr cddaaaaadr 
cddaaaaar cddaaaadaar cddaaaadadr cddaaaadar cddaaaaddar cddaaaadddr cddaaaaddr 
cddaaaadr cddaaaar cddaaadaaar cddaaadaadr cddaaadaar cddaaadadar cddaaadaddr cddaaadadr 
cddaaadar cddaaaddaar cddaaaddadr cddaaaddar cddaaadddar cddaaaddddr cddaaadddr 
cddaaaddr cddaaadr cddaaar cddaadaaaar cddaadaaadr cddaadaaar cddaadaadar cddaadaaddr 
cddaadaadr cddaadaar cddaadadaar cddaadadadr cddaadadar cddaadaddar cddaadadddr 
cddaadaddr cddaadadr cddaadar cddaaddaaar cddaaddaadr cddaaddaar cddaaddadar cddaaddaddr 
cddaaddadr cddaaddar cddaadddaar cddaadddadr cddaadddar cddaaddddar cddaadddddr 
cddaaddddr cddaadddr cddaaddr cddaadr cddaar cddadaaaaar cddadaaaadr cddadaaaar 
cddadaaadar cddadaaaddr cddadaaadr cddadaaar cddadaadaar cddadaadadr cddadaadar 
cddadaaddar cddadaadddr cddadaaddr cddadaadr cddadaar cddadadaaar cddadadaadr cddadadaar 
cddadadadar cddadadaddr cddadadadr cddadadar cddadaddaar cddadaddadr cddadaddar 
cddadadddar cddadaddddr cddadadddr cddadaddr cddadadr cddadar cddaddaaaar cddaddaaadr 
cddaddaaar cddaddaadar cddaddaaddr cddaddaadr cddaddaar cddaddadaar cddaddadadr 
cddaddadar cddaddaddar cddaddadddr cddaddaddr cddaddadr cddaddar cddadddaaar cddadddaadr 
cddadddaar cddadddadar cddadddaddr cddadddadr cddadddar cddaddddaar cddaddddadr 
cddaddddar cddadddddar cddaddddddr cddadddddr cddaddddr cddadddr cddaddr cddadr 
cddar cdddaaaaaar cdddaaaaadr cdddaaaaar cdddaaaadar cdddaaaaddr cdddaaaadr cdddaaaar 
cdddaaadaar cdddaaadadr cdddaaadar cdddaaaddar cdddaaadddr cdddaaaddr cdddaaadr 
cdddaaar cdddaadaaar cdddaadaadr cdddaadaar cdddaadadar cdddaadaddr cdddaadadr cdddaadar 
cdddaaddaar cdddaaddadr cdddaaddar cdddaadddar cdddaaddddr cdddaadddr cdddaaddr 
cdddaadr cdddaar cdddadaaaar cdddadaaadr cdddadaaar cdddadaadar cdddadaaddr cdddadaadr 
cdddadaar cdddadadaar cdddadadadr cdddadadar cdddadaddar cdddadadddr cdddadaddr 
cdddadadr cdddadar cdddaddaaar cdddaddaadr cdddaddaar cdddaddadar cdddaddaddr cdddaddadr 
cdddaddar cdddadddaar cdddadddadr cdddadddar cdddaddddar cdddadddddr cdddaddddr 
cdddadddr cdddaddr cdddadr cdddar cddddaaaaar cddddaaaadr cddddaaaar cddddaaadar 
cddddaaaddr cddddaaadr cddddaaar cddddaadaar cddddaadadr cddddaadar cddddaaddar 
cddddaadddr cddddaaddr cddddaadr cddddaar cddddadaaar cddddadaadr cddddadaar cddddadadar 
cddddadaddr cddddadadr cddddadar cddddaddaar cddddaddadr cddddaddar cddddadddar 
cddddaddddr cddddadddr cddddaddr cddddadr cddddar cdddddaaaar cdddddaaadr cdddddaaar 
cdddddaadar cdddddaaddr cdddddaadr cdddddaar cdddddadaar cdddddadadr cdddddadar 
cdddddaddar cdddddadddr cdddddaddr cdddddadr cdddddar cddddddaaar cddddddaadr cddddddaar 
cddddddadar cddddddaddr cddddddadr cddddddar cdddddddaar cdddddddadr cdddddddar 
cddddddddar cdddddddddr cddddddddr cdddddddr cddddddr cdddddr cddddr cdddr cddr 
cdr)

Some useful tools there - surely some of these functions would be proud to appear in any Common Lisp program? How about the stretch-limo caaaaaaaaar, for one ("My god, it's full of cars")? Then there's cadadar - north of the USA, if you have a cold. A few are useful in other ways, too: cdddddddddr provides excellent tonguing practice for woodwind players, especially the bassoonists among you.

By the way, for compatibility with Common Lisp, it's not necessary to go all the way up 1022. Call (cdadderize 14) to give you:

(caaar caadr caar cadar caddr cadr car cdaar cdadr cdar cddar cdddr cddr cdr)

whereas 30 gives you everything up to cddddr.

To be honest, I can't see myself using these very much. Well, OK: I will never use these. But I like the idea that the ever-adaptable Lisp was once written for vacuum-tubes and can still run like the wind on my iMac.

iTunes covers by newLISP

2008-06-27T18:32:00.003+01:00

The latest iPods and iPhones from Apple share an excellent user interface, but there's one area that I find difficult to use. Ironically, in the case of the iPod at least, it's the main screen you see while music's being played that's the problem. Consider this photograph:

It gives a reasonable impression of what the problems are. Unless your eyesight is good (mine isn't), and the lighting conditions are good (they often aren't), it's hard to read the three lines of text at the top - artist, title, and album. Two of these lines are drawn in grey on a black background. A lower-case 'a' in the chosen font measures just over 1 millimetre, or about 3 points. The large area in the middle of the display can show you the album artwork, but if there's no artwork you see two big quavers on a light grey background. What really needs to be provided is a customizable display, where you can specify what information is shown, and how it's presented. It would be nice if you could ask for a display that contains the main information in a larger font, and easier to read graphics.

But, I hear you say, what's all this got to do with newLISP?

You know the answer.

I couldn't resist trying to persuade iTunes to create substitute album artwork that shows the music's details in larger type as album art when it's downloaded to the iPod... I can use newLISP for most of the work. But, unfortunately, the easiest way to talk to iTunes on MacOS X is by using AppleScript, that quirky and devious language whose syntax was once described as "similar to English spelling - not thoroughly thought through".

So let's get the AppleScript stuff over first. Here's a good place to start: get the current selection from iTunes. The necessary AppleScript can be wrapped up in a newLISP function call:

(define (itunes-get-selection)
    (let ((result (exec 
             (format [text]osascript -s s -e 'tell application "iTunes" to get selection'[ /text]))))
         (set 'result (replace "{|}" (first result) "" 0))
         (parse result ", ")))

iTunes returns the information in an AppleScript list, which is easily changed into a newLISP list. Notice that extra '-s s' option flag in the osascript command. That appears to be significant. The result is a list of wordy track references (WTRs):

("file track id 15639 of user playlist id 13999 of source id 41 of application \"iTunes\"" 
 "file track id 15299 of user playlist id 13999 of source id 41 of application \"iTunes\"")

Given a WTR, it's possible to ask iTunes for more information about a track. As usual, I use the Unlikely Delimiter Ploy (UDP) when obtaining information from iTunes, mainly because iTunes track names can contain virtually any character. I've not yet seen four tildes used before, though, so I'm sticking with them for now:

(define (itunes-get-details-of-track file-track-id)
  (let ((result (exec 
            (format [text]osascript -s s -e 'tell application "iTunes"
              tell %s 
                set d to (name & "~~~~" & artist & "~~~~" & album & "~~~~" & duration & "~~~~" & year & "~~~~" & genre) as text
               end tell
             end tell '[ /text] file-track-id))))
      (when result           
         (set 'result 
             (transpose 
                (list '(track-name artist album duration year genre) 
                (parse (trim (first result) {"} {"}) "~~~~"))))
          result)))

That's such an ugly function! But it works:

((track-name "Maiden Voyage") 
 (artist "Herbie Hancock") 
 (album "An Evening With Herbie Hancock and Chick Corea - In Concert CD2") 
 (duration "810.840026855469") 
 (year "1978") 
 (genre "jazz"))

There's just one more piece of AppleScript required, to change the album artwork. Apple could have made this nice and easy:

set artwork of track to "some-artwork.jpg" -- this doesn't work :)

but they didn't. The required newLISP-wrapped code is this:

(define (itunes-set-data-of-artwork file-track-id)
   (exec (format [text]osascript -s s -e 'tell application "iTunes"
      delete every artwork of %s
      set the_artwork to read file (((path to desktop) as text) & "artwork-canvas.pict") from 513 as picture
      set data of artwork 1 of %s to the_artwork
    end tell'[ /text] file-track-id file-track-id )))

This looks for a graphic in PICT format at ~/Desktop/artwork-canvas.pict, strips the 512 byte header, loads the picture data, and applies the result to the track as album artwork.

I can't persuade newLISP-GS to produce PICT files, but luckily the Mac comes with the sips image processing tool, so converting PNG to PICT is easy.

(define (convert-to-pict file-name)
    (let ((new-file-name (replace {(.*)(\.)(.*$)} (string file-name) (string $1 ".pict") 1)))
          (exec (format "sips -s format pict '%s' --out '%s'"  file-name new-file-name))))

So now I can take off my AppleScripter's hat and switch to newLISP. To produce the graphics, I use a newLISP-GS canvas, after first setting up the graphics system:

(load (append (env "NEWLISPDIR") "/guiserver.lsp"))
(gs:init)
(gs:window 'Artwork 200 200 320 320)  
(gs:canvas 'ArtworkCanvas)
(gs:set-size 'ArtworkCanvas  320 320)
(gs:add-to 'Artwork 'ArtworkCanvas )
(gs:set-background 'ArtworkCanvas gs:gray)
(gs:set-visible 'Artwork true)

and then use commands such as set-font and draw-text to draw some more informative artwork. The main loop is simple enough, in theory at least:

(dolist (track (itunes-get-selection))
  (set 'data (itunes-get-details-of-track track))

  ; start drawing
  (gs:draw-text 'AlbumText (string (lookup 'artist data)) ...

  ; repeat for other information

  ; then:
  (gs:update)  

  (set 'temp-file (string "/Users/me/Desktop/" {artwork-canvas.png}))
  (gs:export temp-file)
  (convert-to-pict temp-file)
  (itunes-set-data-of-artwork track)

  ; delete all text
  (gs:delete-tag 'AlbumText)

  ; and start on the next one
  )

In practice there are various issues to address, such as timing - all these external processes appear to hamper a smoothly flowing script - so some sleep commands have to be added. Also, you might want to waste, I mean, spend more time adjusting the formatting and typography. I like adjusting the point size so that the line of type fits perfectly, and changing the colours to suit the genre. But that's another story!

The making of ... Scene 78

2008-06-27T18:32:00.002+01:00

INT. OFFICE. NIGHT. GEORGE sits at a big desk. A computer screen casts a dull light over a pile of papers.

The phone rings. GEORGE answers.

STEVE: (VOICEOVER) Hey, George, it's Steve. Any progress on the title? Gonna have to move forward on this real quick now.

GEORGE: Nothing yet, Steve. Still working through some suggestions. I got the final draft of the titlemaker code, just running it now.

STEVE: Uh huh, OK. What did you feed into it this time?

GEORGE: Those key words we talked about last week. Changed a few.

STEVE: Right. So, did we get any promising ideas?

GEORGE: Um ... let me see. Bit of problem with memory allocation. Ah yes. How about: "Indiana Jones and the Lost Kingdom of the Crystal Grail."

STEVE: I dunno. Sounds a bit ... er ... country and western.

GEORGE: Know what you mean. So what about "Indiana Jones and the Holy Crystal of the Doom Raiders". OK, don't answer... Try "Indiana Jones and the Doom Skull of the Lost Kingdom"? No? "Indiana Jones and the Lost Legend of the Holy Kingdom"?

STEVE: Yeah, yeah, it's not ... these are just not working for me. Although I like the first four words. They're, you know, strong. Are you sure that code's good, George?

GEORGE: Yup, got it from Hanson, out East. He's usually our number one guy for this kind of thing. Looks OK to me, I think we got the latest version...

Cut to computer screen, which shows the following programming code.

(define (mappend) (apply append (apply map (args))))

(define (remove1 elt lst) 
  (let ((elt-pos (find elt lst))) 
    (if elt-pos (pop lst elt-pos)) 
    lst)) 

(define (k-permutations k multiset) 
  (let ((pivots (unique multiset))) 
    (if (= k 1) 
        (map list pivots) 
        (mappend (lambda (p) 
                 (map (lambda (k-1-perm) (cons p k-1-perm)) 
                      (k-permutations (- k 1) (remove1 p multiset)))) 
               pivots)))) 

(set 'keywords 
  '("Lost" "Skull" "Kingdom" "Raiders" "Ark" "Grail" "Doom" "Legend" "Holy" "Crystal" "Kingdom"))

(map (fn (title) 
   (println  "Indiana Jones and the " 
     (title 0) " " 
     (title 1) " of the " 
     (title 2) " " 
     (title 3))) 
   (k-permutations (length keywords) keywords))

STEVE: Hmm, well it sure isn't doing the business for us yet. Run it some more - we'll just have to keep at it until something good turns up.

GEORGE: OK, Steve. What about "Indiana Jones and the Lost Skull of the Legend Kingdom"?

STEVE: Nah.

GEORGE: Uh, "Indiana Jones and the Grail Ark of the Holy Skull"?

STEVE: Holy skull? Christ, George, I think even Crystal Gayle's better than that.

FADE.

(newLISP) plist

2008-06-27T18:32:00.001+01:00

Seth Dillingham is a unusual guy. As well as - apparently - being able to think in regular expressions, he is also prepared to write something useful for us newLISPers, even though he doesn't use the language himself. If you use BBEdit or TextWrangler, and use newLISP, you'll probably want to get the latest version of his codeless language module for newLISP, which he's updated for the forthcoming (and amazing) newLISP version 9.4.

You can also read about how it's done, too, here.

Thanks, Seth, and good luck with the PMC challenge!

Plug addict

2008-06-27T18:32:00.000+01:00

I'm trying out a very simple plug-in system for the newLISP script (as yet unnamed) that produces this blog. The idea is that you can more easily add or remove features by adding or removing plug-ins, rather than by modifying the main script each time. So far the results are promising.

Each plug-in is just a newLISP context stored in a file, so the first relevant piece of code in the main script is this:

(set 'plug-ins '())
(dolist (i (sort (directory plug-ins-dir "\\.lsp")))
   (load i))

which loads every newLISP file in the plug-ins directory. The code for a plug-in file looks like this:

(context 'Whatever)
; ... function definitions
; and finally:
(push (context) plug-ins -1)
; eof

In the last line the plug-in registers its presence and willingness to participate by appending its name to the master list. The advantage of doing it this way is that you can modify the order in which plug-ins load, and execute, by adjusting the file names, rather than by changing any code. For example, given these plug-ins:

01debug.lsp
10html.lsp
20atom.lsp
30cache.lsp
default.lsp

you can play with the numbers to change the order of execution.

The following macro function in the main script runs through the plug-ins (ie the contexts) in order, executing the same function in each.

(define-macro (call-plug-in-function flag func)
  (catch 
    (dolist (ctxt plug-ins)
      (if (context ctxt func)
          (set 'result (apply (sym func ctxt) (args)))
          (set 'result nil))
      (if (and flag result) 
          (throw result))))
   result)

This tries to call function func in every available context, in the order the files were loaded. There's a flag argument to the macro which is used to specify whether only one plug-in can handle the task or whether all plug-ins can have a shot at the task. The result returned by each function also determines whether subsequent plug-ins can handle the task if for any reason the current plug-in can't cope.

All that's now required is for the tasks to be organized into functions, and for the functions to be passed to call-plug-in-function for evaluation in all contexts.

Here's an example of how it works, for the Atom news-feed plug-in, given the example set of plug-ins shown above. The main script decides that it's time to choose a template:

 (call-plug-in-function true "choose-template")

The call-plug-in-function macro looks for a choose-template function in every context. Only one template set can be chosen, so the true value tells all the plug-ins that the first one to handle it successfully will be the only one to handle it. There's no definition for choose-template in the first plug-in (ie Debug:choose-template doesn't exist), but in the next plug-in there is. However, HTML:choose-template decides that it doesn't want to handle anything to do with Atom, so returns nil. Next, it's the turn of Atom:choose-template, which should be able to complete its tasks successfully and return true:

; in context Atom:
(define (choose-template)
  (cond 
     ((= required-format "atom")
         ;
         ; choose suitable template set
         ;
         true)
    (true
         nil)))

No other plug-ins get the chance of choosing templates now.

Changes to the way Atom-formatted news is generated can be made to the Atom context. The Atom context can be removed altogether without affecting the behaviour of other parts of the application. I could write a different Atom context and try it out by changing the numbers in the filenames.

Notice that I've assumed that the main script provides enough information about the environment and the task in hand for the plug-ins to make intelligent decisions about what to do. I'm also assuming - obviously - that there's no malicious intent or desire to disrupt the whole set-up. It's not a good idea to load any plug-ins from an untrusted source...

It's possible to override built-in behaviour because even the basic tasks are handled by a plug-in file as well. This is loaded last, so it can provide default behaviour to be carried out when none of the other plug-ins have volunteered for tasks.

Some tasks can be handled by a number of different plug-ins one after the other. For example, a 'tidying-up' function is called from the main script with:

(call-plug-in-function nil "tidy-up")

and each plug-in can do some tidying up if necessary.

It's early days yet, but I'm interested to see how many different tasks I can get the plug-ins to handle until I have to make changes to the main script!

C*mments

2008-06-27T18:31:00.002+01:00

I've managed to cobble together a Comments plugin for this site. It's still a work in progress, so I don't expect it to be 100% reliable just yet. If you submit a comment and it doesn't appear (and you don't consider yourself to be a spammer), please email me and I'll investigate!

I was a bit surprised that, after installing the plugin, it took only 25 minutes for the first spammers to arrive and leave their tell-tale pharmacological trail. Google doesn't bother much with this site, but apparently spammers can immediately find any web page with a comments form - presumably they're searching the internet for anything with the word "comments" in? Perhaps I should have called it something different.

As it turned out, it wasn't too bad, because it gave me the chance to test some IP-blacklisting code I put together. This may or may not work, but I needed a bit of genuine spam to test against. I don't need any more, though. :)

I'm trying out a JavaScript utility called WMD. This lets you format your comments in Markdown and see what the results look like before they're submitted. Although there's a development version of Markdown written in newLISP here, I couldn't use this to generate a live preview in a web page - JavaScript still rules the browser.

Dated posts

2008-06-27T18:31:00.001+01:00

You'll sometimes see the date and time presented in this format - 2008-04-19T22:45:33Z. It's the date (year-month-day) followed by a "T", followed by the time (hours:minutes:seconds), followed by a Z, which specifies the Greenwich or UT Time Zone. ('Z' stands for 'Zulu', but that's another, and possibly more interesting, story.) This date-time format conforms to the Atom Date construct, as described in the Atom specification:

A Date construct is an element whose content MUST conform to the "date-time" production in RFC3339. In addition, an uppercase "T" character MUST be used to separate date and time, and an uppercase "Z" character MUST be present in the absence of a numeric time zone offset.
atomDateConstruct =
   atomCommonAttributes,
   xsd:dateTime
Such date values happen to be compatible with the following specifications: ISO.8601.1988, W3C.NOTE-datetime-19980827, and W3C.REC-xmlschema-2-20041028.

and here's ISO 8601:

The following profile of ISO 8601 dates SHOULD be used in new protocols on the Internet. This is specified using the syntax description notation defined in ABNF.


     date-fullyear   = 4DIGIT
     date-month      = 2DIGIT  ; 01-12
     date-mday       = 2DIGIT  ; 01-28, 01-29, 01-30, 01-31 based on
                               ; month/year
     time-hour       = 2DIGIT  ; 00-23
     time-minute     = 2DIGIT  ; 00-59
     time-second     = 2DIGIT  ; 00-58, 00-59, 00-60 based on leap second
                               ; rules
     time-secfrac    = "." 1*DIGIT
     time-numoffset  = ("+" / "-") time-hour ":" time-minute
     time-offset     = "Z" / time-numoffset
    
     partial-time    = time-hour ":" time-minute ":" time-second
                       [time-secfrac]
     full-date       = date-fullyear "-" date-month "-" date-mday
     full-time       = partial-time time-offset
    
     date-time       = full-date "T" full-time

Important stuff!

In newLISP, you can get time in this format by using a suitable time format string with date. For example, the modification time of a file can be presented in RFC3339 date-time format with this:

(set 'modification-date (date file-mod-date 0 "%Y-%m-%dT%H:%M:%SZ"))

where file-mod-date is the file's modification date as a seconds-from-1970 value, obtained like this:

(set 'file-mod-date (file-info file 6))

The previous blogging tool I wrote made extensive use of compressed ISO 8601 identifiers:

20080419224533

which is a 14-digit number or string. It can be used as either:

(set 'p 20080419224533)
(dec 'p)
;-> 20080419224532
(set 'p "20080419224533")
(length p)
;-> 14

I used this both as the unique identifier for a post or blog entry, and as the publication date. To convert these compressed 14 digit ISO date-times (and others) to a newLISP seconds-from-1970 value, you can use parse-date:

(parse-date "20080419224533" "%Y%m%d%H%M%S")
;-> 1208645133

(date (parse-date "20080419224533" "%Y%m%d%H%M%S"))
;-> "Sat Apr 19 23:45:33 2008"

The first problem is that parse-date on MacOS X systems appears to have some flaws. Lutz reckons that libc.dylib on Mac OS X was broken for the strptime() function somewhere between MacOS X 10.4 (Tiger) and 10.5 (Leopard). It was apparently the case that, for some versions of newLISP and MacOS X, the conversion of compressed ISO8601 identifiers didn't work:

(parse-date "20080411234423" "%Y%m%d%H%M%S") 
;-> nil

Suddenly being unable to read date strings without spaces, I spent a few minutes writing a parse-iso-date function:

(define (parse-iso-date s)
 (let ((y (pop s 0 4))
       (m (pop s 0 2))
       (d (pop s 0 2))
       (h (pop s 0 2))
       (mn (pop s 0 2))
       (sec s))
 (parse-date (format "%s %s %s %s %s %s" y m d h mn sec) "%Y %m %d %H %M %S")))

but it doesn't look like the right solution - just reformatting a string so that it has spaces between the components and then using parse-date. And later I found that I was converting between different date formats too often: from compressed ISO to Atom, or from compressed ISO to a familiar local representation, and then back into Atom again.

When you stare at a problem for long enough, you can often see a bigger problem hidden behind it. I started to dislike seeing these IDs. References to stories used to take the form:

index.cgi?post-id=20080411234423

which is computer-friendly but user-hostile, easy enough for a computer to produce but not easy for humans to recognise or decipher. I've typed enough of these in by hand to know that it's surprisingly easy to lose your place in a long string of digits when you're tired or in a hurry. Another problem is updating a post makes these date-based IDs less meaningful - but changing them probably isn't the right solution either.

So, for the current blogging script, I've adopted a different approach. Stories are referred to using more readable URLs - I read that this was A Good Idea. Dates are now a part of the metadata but extracted and displayed when required, with more emphasis on how old something is rather than the exact moment it was written. And hopefully it's no longer necessary to display weird date formats just because they're used internally by the software.

Functions That Use and the Functions That Get Used...

2008-06-27T18:31:00.000+01:00

While writing a function to tell me what functions a function functions with (by this I mean, what functions a function uses to do its thing), it occurred to me that this could be accomplished using newLISP's ability to look within (no wonder newLISP is so enlightened ;-) We could, of course, hand-code one for each function:

> (define (f a b) (+ a  b (- b a)))
(lambda (a b) (+ a  b (- b a)))
> (define (f-uses) '(+ -))
(lambda () '(+ -))
> (f-uses)
(+ -)
> _

But that would add a lot of needless functions to our namespace -- and make competent programmers laugh at us :-)

Better to look at the function itself (the S-expression) and extract all of the function names automatically. But how?

Let's pretend we have no idea how to do this yet and just feel our way along. Of course, I already know how to do this (he says in a voice that betrays his ignorance), so don't you worry about a thing. Everything will be fine (*gulp*).

The best place to start may be by looking at a function's S-expression. A naive attempt might be to just look at the value of a function's name. But first, we need to define a function to look at:

> (define (f a b) (+ a b (- b a)))
(lambda (a b) (+ a b (- b a)))
> f
(lambda (a b) (+ a b (- b a)))
> _

Look, newLISP rewards our naiveté with exactly what we want, matching our mental model of the world! Two things to notice here. The result of define and the value of f are identical, and this result is a lambda (a function without a name).

Now let's begin our dissection of this S-expression to see if we can get at those function names.

> (0 f)
((a b) (+ a b (- b a)))
> (1 f)
((+ a b (- b a)))
> ;; almost there!
> ((1 f) 1)
(+ a b (- b a))
> ;; here we go.
> _

Now we just need to look at the first symbol in each expression (with exceptions) to know which functions this function is using. Before we continue, we'd better get a better grip on our subject.

> (set 'subj ((1 f) 1))
(+ a b (- b a))
> _

To get the first one is easy. Just use first!

> (first subj)
+
> _

If all we were interested in was the first function our function calls, we'd be done. Actually, we want all of the functions, so we must keep going. Iteration seems to be in order. Warning: The next few snippets contain examples of code-groping. Don't try this at work ;-)

(map (fn (ea) (and (list? ea) (first ea))) subj)
(nil nil nil -)
> _

That's almost it. We don't need all those nils, though. Next try.

>(filter (fn (ea) (and (list? ea) (first ea))) subj)
((- b a))
> _

That's not exactly right, either. Maybe we should break this up into finer steps.

> (filter list? subj)
((- b a))
> _

Now we're on to it. If this were a complete example, we would have more than just one expression in our resultant list. Now for the next part:

> (map first (filter list? subj))
(-)
> _

You know what? We're missing something here. A test to see if the first element of the list is a lambda or a primitive. How do we do that? lambda? and primitive?, of course.

> [cmd] 
(filter
    (fn (ea)
        (let (ea (eval ea))
        (or (lambda? ea) (primitive? ea))))
    (map
        first
        (filter list? subj)))
[/cmd]

There we are. We're all done except for the first function in the expression, which we got by applying first. Here we need it consed to the front of our list:

> [cmd] 
(cons
    (first subj)
    (filter
    (fn (ea)
            (let (ea (eval ea))
            (or (lambda? ea) (primitive? ea))))
        (map
            first
            (filter list? subj))))
[/cmd]
(+ -)
> _

Wow. There it is! The functions our subject function calls. But are we really done yet? Done is something that programming never seems to be ;-) Is the first element being tested to see if it's a function? And will it work with deeply nested functions? This is the part where I expect the author to say, "I'll leave that as an excerise for you," probably because he or she is tired of writing ;-) Not me!

First, let's define this as a function.

> [cmd]
(define (uses fname)
    (let (subj ((1 fname) 1))
    (cons
        (first subj)
        (filter
            (fn (ea)
                (let (ea (eval ea))
                (or (lambda? ea) (primitive? ea))))
            (map
                first
                (filter list? subj))))))
[/cmd]
(lambda (fname) 
    (let (subj ((1 fname) 1)) 
    (cons (first subj) (filter (lambda (ea) 
        (let (ea (eval ea)) 
            (or (lambda? ea) (primitive? ea)))) 
        (map first (filter list? subj))))))
> (uses f)
(+ -)
> _

That seems to be working. Let's try this with a deeper function.

> (define (deep-f a b) (+ a (- (* b a) a)))
(lambda (a b) (+ a (- (* b a) a)))
> (uses deep-f)
(+ -)
>

Just as I suspected. Anything deeper than one level, and it's ignored. Where do we go from here? I'll leave that as an exercis . . . just kidding ;-) Maybe we should conclude for today and then we can look forward to Part II of "Functions That Use and the Functions That Get Used by Other Functions"! If you would like to post solutions to the comments section, by all means do. I'll just check them against my already-conceived code (you don't really believe this, do you?), and we can pick the best one. I'm pretty sure mine won't win, though ;-)

m i c h a e l

P.S. If you detect a slight shallowing of the code in these posts, the effect is entirely acknowledged to be true. I'm looking with nostalgia at the days when I could spend an hour or more coding something up in newLISP, and that's a bad sign, indeed.

Comment from don Lucio

Here is a solution using the function 'flat' which makes it easy to acess a deep nested list:

(define (uses fname)
(unique (filter
(fn (s) (primitive? (eval s)))
(flat fname))))

Comment from cormullion

Excellent post! I've always wondered about this area of newLISP!

(The modest note at the end of your post is entirely unjustified!)

Under construction (again)

2008-04-15T12:25:00.000+01:00

This site is being rebuilt, again! Yes, I've written another blogging application in newLISP to generate these pages. It's far from finished yet, but at the moment it's looking quite promising: only about 250 lines of newLISP so far, and I hope to get it down even further.

Unfortunately, there are some features I've yet to get round to doing - the most obvious being the Atom newsfeed. Soon, perhaps.

I don't think I'll be enabling comments again, but the email address should be somewhere on this page so pelase write to me!

I've kept the old articles from the earlier blog here, for posterity, even though some of them are no longer applicable - or just plain wrong.

Links

2008-03-06T22:44:00.000Z

This post contains a link to Adam's newLISP-powered web site (Hi Adam!) and a link to Alessandro's newLISP blog (Ciao!).

ThisService reaches version 2

2007-10-01T18:04:00.000+01:00

The cool utility ThisService from the excellently-named WaffleSoftware has been updated to version 2. It's a clever way of running scripts written in scripting languages - such as newLISP - from the Services menu (the menu that's available in every application, with a few dishonourable exceptions). It's MacOS X specific - there's probably an equivalent on other platforms.

One good addition is that you can now make services that link to scripts stored somewhere sensible on your disk. Before, your script was copied into the service, but now you can keep scripts in their rightful place and yet still use them in the services you create.

To complement this change, there's also a packaging option, so that scripts and services can be merged ready for distribution.

The example scripts provided with this donation-ware application (written in Ruby, Perl, Python, and AppleScript - the four horsemen of Macintosh scripting) all seem to avoid reading line by line from STDIN, instead preferring to read any text input into a variable first. The word 'slurp' is used...

In newLISP, a typical service might look like this. This puts a comment before every line of the selection:

 #!/usr/bin/env newlisp

 (while (read-line) 
   (push (current-line) the-text -1))

 (dolist (line the-text)
   (println {; } line))

 (exit)

As before, there will be the inevitable problems with applications that use "\r" rather than "\n" as line breaks. I think I've bored myself with that before!

Comment from Jesper

As the writer of the Ruby, Perl and AppleScript versions (and, also, of ThisService itself - hello everyone) I just want to defend my usage of slurping. It's really easy - most of the time you want to run the whole input through a filter, and that might not work well with line-by-line or word-by-word or 512-summat-byte-block-by-block.

It will confuse the least amount of people who just want to get stuff done. Peter Hosey wrote the Python scripts completely independently (I said to comment well and keep STDIN/OUT UTF-8 and that was basically it), and he too chose slurping. I'd like to believe that this confirms my suspicions. ;)

Comment from cormullion

Hi! Slurping is cool. And it's what I used too. I just quite like the word, which is much more descriptive than the usual way of describing it!

And ThisService is cool too, Jesper! If I was currently employed, I'd send you some money :-)

Search me

2007-09-27T15:59:00.000+01:00

I've been fixing a few bugs and tweaking bits of the newLISP code that publishes this page - and starting to document it too using newLISPdoc. If I've broken anything, or need to fix something that isn't working properly, please tell me.

I've adjusted the search code a bit, so that searches examine most of the database. I don't think SQLite has a regular expression search tool, but it seems to work OK without one. The text you type in the box is enclosed in percent signs (the SQLite wild card character equivalent to *), so it will find partial matches in most of the fields. You can type another one in the middle of your search text if you want but it's usually not needed.

The single character wild card (the underscore) can be typed into the box to search for any single character. So "l__z" will find posts and comments containing Liszt and Lutz.

It's also possible to search for posts and comments by date. For example:

will find all posts and comments from May 2006 - all posts and comments are stored by their creation date and time. For some while I was puzzled by why the search found other posts from later in the year, until I realised that posts are stored in HTML, so all the links and attributes are searched as well as the text itself. Any link or reference to an earlier post will provide a match for the search, even though nothing is visible.

A local affair

2007-09-26T10:45:00.000+01:00

One minor problem that I encountered when setting up this newLISP-powered site was that, on my own computer, the newLISP binary is installed in /usr/bin/, whereas on the host, it's installed in /usr/local/bin.

To make life easier, you can define a /usr/local/bin/newlisp link on your own system:

 sudo ln -s /usr/local/bin/newlisp /usr/bin/newlisp

and that saves you having to change your newLISP installation when you're testing.

Doing a bit of research it appears that it's considered to be better to install packages like newLISP into /usr/local/bin rather than into the system's own /usr/bin.

Perhaps a future newLISP installer might allow a choice of locations.

Comment from Jeff

You can install it wherever you like if you compile it from the source. Just do ./configure --prefix=/usr/local.

Also, instead of using #!/usr/bin/newlisp or #!/usr/local/bin/newlisp, most modern unixes have env, so you can do #!/usr/bin/env newlisp, which will ask env for the location of newlisp and then use it to execute the file.

Comment from cormullion

Cool - env works. I'll use that to avoid future problems.

What is the LambdaPress?

2007-09-25T19:13:00.000+01:00

This page is produced by something which I've jokingly called (the) LambdaPress, a short newLISP script that generates web pages in a timely fashion. If you're reading this, then the 'LambdaPress' has flexed a few lambdas and shaken a few s-expressions, and managed to output a bit of marked-up text as a result.

It's hard to think of names these days. Many of the basic ones have been taken, and the harder you try, the less pleasing the names become. Being devoid of inspiration, I decided to try something a bit like TypePad, WordPress, MoveableType, with a Lisp-y flavour. Since LambdaPress was an Antegooglewhackblatt at the weekend, I used that as a working term. It will probably change to something more sensible.

I saw this article about writing your own blogging software only after I'd finished an early prototype last week. I think I agree with the basic idea, but of course I had managed to ignore most of the sensible advice and had just hacked my way through to some basic functionality. Some of the features seem too hard to do.

I had originally planned on using the newLISP-wiki for the Blogger replacement. The wiki is a remarkable package, cramming a lot of functionality into a small space. But after playing with it for a while I decided to write something from scratch.

Why? First, and most important, because it's fun to do things in your own way, sometimes. Second, the wiki has more features than I needed just for publishing some text. Third, I wanted to make various small changes to the wiki code, which was both difficult and undesirable. Difficult because I wasn't too sure what was going on, and undesirable because I didn't want to make a degraded copy that couldn't be upgraded when or if a new version was released.

The original idea of the 'LambdaPress' (still in quotes - I'm not convinced about the name) was that the posts could be stored in an SQLite database, and the newLISP code would simply do a few queries and output the results enclosed in a few

s. That way, all sorts of things were easy, and most of the effort would be on the formatting and presentation.

In the end, that's exactly how it worked. My previous blog was exported from Blogger (not that difficult, although it involved changing lots of settings and then changing them back again). It was easily imported into a database, using a short newLISP script, of course. The basic query code was simple too. The difficult bits were:

learning about CGI
getting the CSS styles to look half decent (I haven't even tried looking at the site on Windows yet)
getting the permissions on the hosting computers correct (they're still not right...)
getting the Atom feed to work properly (it's still not working - it keeps saying the posts are new when they're not!)

So this is version 0.0.1, an alpha, a work-in-progress. I hope to put the script in a downloads section soon so that you can suggest improvements.

Atom feed

2007-09-25T16:16:00.000+01:00

I've added an Atom feed for this site. It's a bit of a quick hack (like the rest of this site :-) so please let me know whether it doesn't work for you.

Comment from adamo

It seems that Technorati is not getting it

Comment from cormullion

I'm still trying to find out what Atom is, really. I'm confused by the publishing and updating dates too. (I'm new to this stuff!)

This is still a work in progress!

I don't think I've done anything about Technorati yet.

Moving house...

2007-09-25T01:21:00.000+01:00

... to Unbalanced Parentheses.

Hi again!

2007-09-25T00:59:00.000+01:00

I've moved this blog to a new host. Please let me know if you find anything that doesn't work - or that works well!

Comment from Lutz

Powered by newLISP? is 'lambda Press' based on newlisp-wiki? How did you move the pages from blogspot? Congratulations, it looks nice.

Backup

2007-09-17T16:29:00.000+01:00

Backup

I'm just backing up this blog. Please excuse any disruption.

Comment from test

test

Backup

2007-09-17T13:29:00.000+01:00

I'm just backing up this blog. Please excuse any disruption.

Gotcha

2007-09-14T19:27:00.000+01:00

Those captcha things are everywhere these days. You know, the little pictures of random letters that you have to identify before you can post a comment or display a web page. There's even one on this blog, courtesy of Google/Blogger - if you want to comment on these posts of mine, you'll be expected to identify terribly tortured type and gruesomely garbled glyphs before your thoughts can be published.

I didn't realise that 'CAPTCHA' is an acronym - it stands for Completely Automated Public Turing test to tell Computers and Humans Apart (a struggle, but they made it work, just). It's even been trademarked by Carnegie-Mellon University.

To be honest, I'm not a big fan of the typographical captcha. I can understand their purpose, and they're acceptable as part of the ongoing fight against spammers. But I don't feel good when I'm typing nonsense into little boxes. Letters can be beautiful things that help us communicate, and these captchas are ugly reminders of an ugly reality. The task of responding to a captcha is the McJob of the internet browsing world - a sad and mindless task that it usually isn't worth teaching computers to do.

(It turns out that many of these captchas are now crackable by dumb computers and their clever programmers: see here and here, for example.)

Another problem with captchas is that they're hard for people who have vision problems. It's sad that computers can sometimes solve things that they're not supposed to while humans can't sometimes solve things that they've been made to.

Unfortunately, it's hard to think of anything more pleasant that offers any kind of resistance to automated attacks. Given enough time, most simple text-based captchas can be overcome, particularly if the rewards are sufficient. Some spammers presumably spend days cracking challenging Yahoo and Hotmail captchas so that they can send millions of spam emails from temporary accounts.

But something is better than nothing, and it's fun to try and devise a simple question/answer method that's just challenging enough to deter the idle spammer.

My first attempt, for verifying comments posted to a newLISP wiki, was fun, but probably not very effective as a security measure. Here's the basic idea, with a small sample data set:

(set 'data '(
  ({apple} {pear} {cherry} {mango} {peach} {lime} {strawberry} {kumquat})
  ({onion} {carrot} {potato} {bean} {pepper}  {cucumber})
  ({red} {ultramarine} {pink} {green}  {blue} {turquoise})
  ({bach} {beethoven} {zappa} {liszt} {mozart} {lennon} {brahms})
  ({london} {paris} {chicago} {rome} {athens} {moscow} {beijing})
  ({oxygen} {lead} {plutonium} {calcium} {cobalt} {strontium})
  ({elephant} {mouse} {lion} {toad} {frog} {slug})
  ({ls} {cat} {vi} {ps} {echo} {man} {ed} {diff} {troff})))
(seed (date-value))
(define (generate)
  (map set '(odd-one-list others-list) (randomize data))
  (set 'odd-one (first (randomize odd-one-list)))
  (map set '(other1 other2 other3) (randomize others-list))
  (join (randomize (list odd-one other1 other2 other3) ) { }))

The question is something like "what's the odd one out?", followed by the result of (generate). For example:

  zappa beethoven lennon cobalt

The user then has to type the odd one out before the comment is posted. I liked the strange poetry that this generated:

cat vi oxygen ls
athens moscow lion chicago
rome oxygen lead calcium
lime cherry ultramarine pear
bach ultramarine zappa mozart

and it wouldn't be an unpleasant task to answer such a simple question. I also like the idea that you could adjust the difficulty level by changing the data lists, not just by adding more obscure elements from the periodic table and some more unusual Unix commands, but by adding lists of newLISP functions, or famous brands of whisky. It's tempting, but probably unjustified, to think that spammers are stupid and would have trouble answering questions like these.

A subtle problem to avoid is that some words belong to two categories - cat, for example. But a more serious deficiency is that, if the question is multiple choice, and the n options are easily identified, the spammer has a 1 in n chance of getting the solution just by choosing an answer at random. So it's a good idea to make sure that the right answer isn't on display at all. Finally, though, the most serious drawback is that it would be easy to solve these simple questions by writing a short program, assuming that there's not already an odd-one-out server. (Any takers? - it'd be an interesting task, given that the data lists themselves, and the complete list of categories, would not be immediately apparent to the would-be malefactor and would emerge only after repeated attempts.)

So I've started thinking about alternatives where the answer isn't visible on the web page. No luck yet - arithmetic sequences with the last number missing are a bit dull!

Gotcha

2007-09-14T10:27:00.000+01:00

(It turns out that many of these captchas are now crackable by dumb computers and their clever programmers: see here and here, for example.)

But something is better than nothing, and it's fun to try and devise a simple question/answer method that's just challenging enough to deter the idle spammer.

My first attempt, for verifying comments posted to a newLISP wiki, was fun, but probably not very effective as a security measure. Here's the basic idea, with a small sample data set:

(set 'data '(
  ({apple} {pear} {cherry} {mango} {peach} {lime} {strawberry} {kumquat})
  ({onion} {carrot} {potato} {bean} {pepper}  {cucumber})
  ({red} {ultramarine} {pink} {green}  {blue} {turquoise})
  ({bach} {beethoven} {zappa} {liszt} {mozart} {lennon} {brahms})
  ({london} {paris} {chicago} {rome} {athens} {moscow} {beijing})
  ({oxygen} {lead} {plutonium} {calcium} {cobalt} {strontium})
  ({elephant} {mouse} {lion} {toad} {frog} {slug})
  ({ls} {cat} {vi} {ps} {echo} {man} {ed} {diff} {troff})))
(seed (date-value))
(define (generate)
  (map set '(odd-one-list others-list) (randomize data))
  (set 'odd-one (first (randomize odd-one-list)))
  (map set '(other1 other2 other3) (randomize others-list))
  (join (randomize (list odd-one other1 other2 other3) ) { }))

The question is something like "what's the odd one out?", followed by the result of (generate). For example:

  zappa beethoven lennon cobalt

The user then has to type the odd one out before the comment is posted. I liked the strange poetry that this generated:

cat vi oxygen ls
athens moscow lion chicago
rome oxygen lead calcium
lime cherry ultramarine pear
bach ultramarine zappa mozart

So I've started thinking about alternatives where the answer isn't visible on the web page. No luck yet - arithmetic sequences with the last number missing are a bit dull!

Comment from newdep

What is the capital city of G.B.?
or
1234 * 12345 = 344523445?
or
How many colors do you see here?
or
what is the current GMT?...

its all there to be published... a little
harder to knack..but its saver then whats avialable now...

...intresting topic to think about ;-)
Norman.

(newLISPer)

Balance those parentheses

newLISP tackles global warming

A picture is worth a 1000 words

Every picture tells a story

Addendum

Tweeting frequency

Seasonal greetings

newLISP Bayesian Comment Spam Killer

Syntax matters

newLISP at Wikibooks: volunteers wanted

Updates to nldb

End of the rainbow

Creative functions

The Lambdalator: RIP

Enter the Dragon(fly)

newLISP XML-RPC v." version ": not a valid XML-RPC request

newLISP XML-RPC v." version ": not a valid XML-RPC request

newLISP and TextExpander for Mac

Mazes

On my command

About this site

Go away if...

Dragonfly

Downloads

Process Finder Selection: the return of AppleScript (for a few seconds at least)

Simple database in newLISP

Simple database, second attempt

newLISP all of a Twitter

Bits and pieces

Spellbound

Project Nestor: part 1

Going API

Reasons to learn newLISP

1 It's easy

2 It's small

3 It's fast

4 It's versatile

5 It's different

6 It's friendly

7 It's not finished

8 It's fun

9 It's free

Two (or more) challenges for the weekend

Looking for things

Character reference

googled again

Simple help for newLISP

Smashing the Atom

Edit

Two out of three - TicTacToe

Vacuum-tube Lisp

iTunes covers by newLISP

The making of ... Scene 78

(newLISP) plist

Plug addict

C*mments

Dated posts

Functions That Use and the Functions That Get Used...

Comment from don Lucio

Comment from cormullion

Under construction (again)

Links

ThisService reaches version 2

Comment from Jesper

Comment from cormullion

Search me

A local affair

Comment from Jeff

Comment from cormullion

What is the LambdaPress?

Atom feed

Comment from adamo

Comment from cormullion

Moving house...

Hi again!

Comment from Lutz

Backup

Comment from test

Backup