Feeds:
Posts
Comments

Posts Tagged ‘syntax’

This is part 3 in my terse hashes in emacs lisp series

Since emacs 23.2 was released the hash creation part of my _h macro is now obsolete. (or maybe not – perhaps allowing nested braces would make usage cleaner at the cost of significant complexity)? However, I suspect that is only one part of what would make emacs lisp nested data structures pleasant to use.

The other piece of the puzzle is dereferencing.

We don’t need a macro to implement the set and get functionality that _h includes so far. It was only required to prevent the braces from being evaluated.

Previously I mentioned extending the _h macro to allow for easier, or at least terser, nested hash dereferencing. The syntax I suggested would still need a macro. And I might as well leave the braces hash creation. It is unlikely my firm will upgrade to 23.2 in the next few months.

Given this nested %hash

(defvar %hash)
(setq %hash (_h { 1 2
                  'h (_h { 3 4
                           5 6
                           'h2 (_h { 1 2
                                     3 [5 6 7]
                                     'vh (vector (_h { 1 2 })
                                                 (_h { 3 4 }))
                                   })
                         })
                }))

I want (_h %hash -> 'h 'h2 'vh [1] 3) to return 4.

(It might be nice to add a nested assignment such as

(_h %hash -> 'h 'h2 'vh [1] 3 := "hello")

but the dereference will do for now.)

(defsubst h/vref (num)
  (cons 'vecpos num))

(defmacro _h (arg1 arg2 &rest args)
  (declare (indent defun))
  (cond ((eq arg1 '{) ...)
        ((eq arg2 '->)
         (let (str new-args)
           (dolist (elem args)
             (setq str (prin1-to-string elem))
             (if (string-match "\\[\\([0-9]+\\)\\]" str)
                 (let ((pair (h/vref (string-to-number
                                      (match-string 1 str)))))
                   (push (cons 'quote (list pair)) new-args))
               (push elem new-args)))
           (setq new-args (reverse new-args))
           `(h/get-value (quote, arg1) ,arg1 ,@new-args)))
        ((null args) ...)
        (t ...)))

That might be a little over the top, but it demonstrates that the macro facility does pretty much have access to the full power of the language.

The new functionality relies on a helper function, h/get-value.

(defun h/get-value (var-name variable &rest args)
  (let (retval param previous-param)
    (when (<= (length args) 0)
      (error "(_h %s -> ...) was not passed any arguments" var-name))
    (setq retval variable)
    (while args
      (setq param (pop args))
      (cond ((and (consp param) (eq 'vecpos (car param)))
             (let ((ref (cdr param)))
               (setq param (intern (concat "[" (number-to-string ref) "]")))
               (if (vectorp retval)
                   (setq retval (aref retval ref))
                 (error "%s not a vector @ %s (%s)"
                        var-name param previous-param))))
            ((hash-table-p retval)
             (setq retval (gethash param retval 'missing-key))
             (when (eq retval 'missing-key)
               (error "Can't find nested hash value %s in %s (%s)"
                      param var-name previous-param)))
            (t (error "value %s returned for param %s is not a hash in %s"
                      retval previous-param var-name)))
      (setq previous-param param))
    retval))

(macroexpand '(_h %hash -> 'h 'h2 'vh [0]))
--> (h/get-value (quote %hash) %hash (quote h) (quote h2) (quote vh) (quote (vecpos . 0)))

The problem with extending syntax like that is what if we want to use a variable to reference the vector rather than hardcoding a value like [0]. The obvious solution doesn’t work.

(defvar test-var)
(setq test-var 1)

(defsubst vec-ref (num)
  (intern (concat "[" (number-to-string num) "]")))

(_h %hash -> 'h 'h2 'vh (vec-ref test-var))

Debugger entered--Lisp error: (error "value [#<hash-table 'eql nil 1/65 0x1438680> #<hash-table 'eql nil 1/65 0x1438200>] returned for param vh is not a hash in %hash")
  signal(error ("value [#<hash-table 'eql nil 1/65 0x1438680> #<hash-table 'eql nil 1/65 0x1438200>] returned for param vh is not a hash in %hash"))

(the error message indicates there is a problem with h/get-value too but no time to fix before we went to press)

It is easier to go down to the next level – the code that the macro generates. The following performs as required.

(_h %hash -> 'h 'h2 'vh (h/vref test-var) 3)

Hopefully I didn’t offend too many senses of aesthetics there.


For reference, the full _h

(defmacro _h (arg1 arg2 &rest args)
  (cond ((eq arg1 '{)
         ;; check for empty case
         (if (eq arg2 '})
             (make-hash-table)
           ;; (_h { k1 v1 k2 v2 ... })
           (let ((rest (cons arg2 args))
                 elem tmp)
             (while (not (null rest))
               (setq elem (pop rest))
               (when (not (or (eq elem '}) (eq elem '=>)))
                 (push elem tmp)))
             (setq tmp (reverse tmp))
             `(literal-hash ,@tmp))))
        ((eq arg2 '->)
         (let (str new-args)
           (dolist (elem args)
             (setq str (prin1-to-string elem))
             (if (string-match "\\[\\([0-9]+\\)\\]" str)
                 (let ((pair (h/vref (string-to-number
                                      (match-string 1 str)))))
                   (push (cons 'quote (list pair)) new-args))
               (push elem new-args)))
           (setq new-args (reverse new-args))
           `(h/get-value (quote, arg1) ,arg1 ,@new-args)))
        ((null args)
         `(gethash ,arg2 ,arg1))
        (t (let ((val (car args)))
             `(puthash ,arg2 ,val ,arg1)))))

Read Full Post »

This is part 1 in my terse hashes in emacs lisp series

One thing I really love about Perl is the easy and natural syntax for deeply nested data structures. I can make a hash of lists of hashes without a second thought.

(Okay, okay, Ruby and Python are equally good or even slightly better here, but I’m thinking about in comparison with emacs lisp, and C++ and Java…)

my $data = {
    list1 => [
        { x => 'y' },
        { a => 'b' },
        # etc ...
    ],
    # etc ...
}

In contrast, the syntax for dealing with hashes in emacs lisp is extremely verbose. Not only that, but for me, the arguments are the wrong way round. In object based programming, the object is always the first argument.

(make-hash-table)
(puthash <key> <value> <hash-table>)

When I came across the Clojure syntax for hash sets using #{ ... } I thought what a good idea. Unfortunately, emacs lisp doesn’t have reader macros. Let’s see what happens when I try it with a function.

(defun hash-set (opening-brace &rest args)
  nil)

(hash-set { 1 2 3 4 })

The result tells us that emacs is trying to evaluate the value of { as a variable before passing it to the function.

Debugger entered--Lisp error: (void-variable {)
  (hash-set { 1 2 3 4 })
  eval((hash-set { 1 2 3 4 }))
...

Fortunately, in emacs lisp, we can delay the evaluation of the arguments using a macro. I use the same macro to make setting and retrieving individual hash values easy too.

(defun literal-hash (&rest args)
  (let ((hash (make-hash-table)))
    (while args
      (let* ((key (pop args))
             (val (pop args)))
        (puthash key val hash)))
    hash))

(defmacro _h (arg1 arg2 &rest args)
  (cond ((eq arg1 '{)
         ;; check for empty case
         (if (eq arg2 '})
             (make-hash-table)
           ;; (_h { k1 v1 k2 v2 ... })
           (let ((rest (cons arg2 args))
                 elem tmp)
             (while (not (null rest))
               (setq elem (pop rest))
               (when (not (or (eq elem '}) (eq elem '=>)))
                 (push elem tmp)))
             (setq tmp (reverse tmp))
             `(literal-hash ,@tmp))))
        ((null args)
         `(gethash ,arg2 ,arg1))
        (t (let ((val (car args)))
             `(puthash ,arg2 ,val ,arg1)))))

Even nested hashes work nicely (I might be betraying my perl biases here!)

(defvar %hash (_h { 1 2 3 (_h { 1 2 3 4 } )))
(_h (_h %hash 3) 1) ;; ==> 2

Okay, retrieval is a little awkward, but I could add some more syntax to _h to make the following work.

(_h %hash -> 3 1)

That is left as an exercise for the reader.

Update: Hi atomicrabbit, I couldn’t figure out how to do the syntax highlighting in the comment so I have included my reply below.

I didn’t know about the #s(make-hash ...), so that looks pretty cool. I found a mention in the Elisp Cookbook. I couldn’t get it to work though unfortunately. Any ideas?

(emacs-version)
;; "GNU Emacs 23.0.60.1 (i386-mingw-nt6.0.6000)
;;  of 2009-01-12 on LENNART-69DE564 (patched)"
(read (prin1-to-string (make-hash-table)))
(read "#s(hash-table data ('key1 'val1 'key2 'val2))")
Debugger entered--Lisp error: (invalid-read-syntax "#")
  read("#<hash-table 'eql nil 0/65 0x143c880>")
Debugger entered--Lisp error: (invalid-read-syntax "#")
  read("#s(hash-table data ('key1 'val1 'key2 'val2))")

Read Full Post »

Okay, this post is going to be quite long. I’m going to start with a basic problem I was solving in emacs lisp. From there I’ll segue into thinking about looping syntax and finally I’ll do a bit of benchmarking as I’ve got the code already and people seem to like that (the scheme, ocaml, c++ speed comparison is by far the most popular post on this blog followed by this).


Futzing around with Project Euler is something I do for fun. Most recently I was looking at problem 73 – count the reduced proper fractions with a denominator less than or equal to 10,000 between 1/3 and 1/2.

Emacs Lisp Solution

Emacs Lisp is usually my default language for doing this kind of thing as I’m already in my text editor and there is a REPL to experiment with.

First of all, it is clear that I’m going to need a function to calculate the greatest common divisor. I found an imperative Pascal implementation of Euclid’s algorithm here. A brief aside – I searched for Pascal deliberately as I generally find it very clear. Does anyone else do that?

(defun gcd (a b)
  (while (not (= b 0))
    (let ((tmp b))
      (setq b (% a b))
      (setq a tmp)))
  a)

Thinking ahead, I’ll probably know what the gcd is before we call make-fraction as only fractions with a gcd of 1 will be actually counted amongst the solutions. I’ve therefore made gcd an optional parameter as a nod to efficiency.

(defsubst make-fraction (num denom &optional gcd)
  (unless gcd (setq gcd (gcd num denom)))
  (cons (/ num gcd) (/ denom gcd)))

I like the flexibility that lisp-like languages give you to name your functions too.

(defsubst more-than-1/3 (frac)
  (let ((num (car frac))
        (denom (cdr frac)))
    (> (* num 3) denom)))

(defsubst less-than-1/2 (frac)
  (let ((num (car frac))
        (denom (cdr frac)))
    (< (* num 2) denom)))

(defsubst within-range (frac)
  (and (more-than-1/3 frac) (less-than-1/2 frac)))

We only check fractions between 1/3 and 1/2 as to do all fractions with a denominator <= 10,000 would take far too long.

(defun solve-it (max-denom)
  (insert (format-time-string "\n\nStarted at: %H:%M:%S\n\n"))
  (let (num denom frac max gcd solutions)
    (setq solutions 0)
    (setq denom 2)
    (while (<= denom max-denom)
      (setq num (/ denom 3))
      (setq max (1+ (/ denom 2)))
      (while (<= num max)
        (setq gcd (gcd num denom))
        (when (= gcd 1)
          (setq frac (make-fraction num denom gcd))
          (when (within-range frac)
            ;; (insert (format "%s\n" frac))
            (incf solutions)))
        (incf num))
      (incf denom)
      (when (= (% denom 50) 0)
        (insert (format "Denom: %d Solutions: %d\n" denom solutions)))
      (sit-for 0))
    (insert (format "\n%d solutions\n" solutions))
    (insert (format-time-string "Finished at: %H:%M:%S\n"))))

After I wrote this, I realised I didn’t need to construct and destruct my fraction type so simplified to the following:

(defun solve-it (max-denom)
  (insert (format-time-string "\n\nStarted at: %H:%M:%S\n"))
  (let (num denom frac max solutions)
    (setq solutions 0)
    (setq denom 5)
    (while (<= denom max-denom)
      (setq num (1+ (/ denom 3)))
      (setq max (/ denom 2))
      (while (<= num max)
        (when (= (gcd num denom) 1)
          (incf solutions))
        (incf num))
      (incf denom))
    (insert (format "%d solutions\n" solutions))
    (insert (format-time-string "Finished at: %H:%M:%S\n"))))

(solve-it 10000)

;; Started at: 22:14:35
;; 5066251 solutions
;; Finished at: 22:15:45

70 seconds. Okay.

The most annoying thing is the primitive looping constructs. while is the basic and obvious built-in. It also has a slew of macros beginning with doXXX including dotimes and dolist not to mention the mighty common lisp loop macro.

I don’t know loop (but I’m going to learn it), but after messing about with do* for a few minutes, I realised it wasn’t the looping construct for me.

(do* ((i 5 (if (> j 10) (+ i 1) i))
      (j (+ i 1) (if (> j 10) (+ i 1) (+ j 1))))
    ((> i 10))
  (insert (format "[%d %d]" i j)))

Yuck.

Now, the great thing about lisp is supposed to be that if you don’t like the syntax you can add your own with macros. Unfortunately, I haven’t got around to that yet as a bunch of people have already designed most of the syntax I like.

Scheme Solution

When I read some of the earlier posts on this blog, it seems that scheme has got some nice generator syntax (aka eager comprehensions) for handling nested loops.

There are a nice set of posts on eager comprehensions here.

I took print-ln from the portable scheme post and gcd from SICP.

#lang scheme/base

(require srfi/42)

(define (print-ln . args)
  (for-each display args)
  (newline)
  (flush-output))

(define (gcd a b)
  (if (= b 0) a
      (gcd b (remainder a b))))

(define (solve-it max-denom)
  (sum-ec (:range denom 2 (+ max-denom 1))
          (:range num (+ (floor (/ denom 3)) 1) (ceiling (/ denom 2)))
          (if (= (gcd num denom) 1) 1 0)))

(print-ln "There are " (solve-it 10000) " solutions")

Yikes, mzscheme is much quicker than emacs-lisp. That surprised me. A factor of 10 I would have expected, a factor of 50 not so much.

$ time mzscheme frac.scm
There are XXX solutions

real    0m1.413s
user    0m1.404s
sys     0m0.004s

Perl Solution

use strict;
use warnings;

use POSIX qw(floor ceil);

sub gcd
{
    my ($n1, $n2) = @_;
    until ($n2 == 0) {
        my $tmp = $n2;
        $n2 = $n1 % $n2;
        $n1 = $tmp;
    }
    return $n1;
}

The nested loop actually looks okay to me in perl although not as nice as the srfi-42 eager comprehensions.

sub solve_it
{
    my $max_denom = $_[0];
    my $solutions = 0;
    foreach my $denom (5..$max_denom) {
        my $max = ceil($denom / 2) - 1;
        foreach my $num ((1 + floor($denom / 3))..$max) {
            if (gcd($num, $denom) == 1) {
                ++$solutions;
            }
        }
    }
    return $solutions;
}

printf "There are %d solutions\n", solve_it(10000);

The performance of my perl is pretty bad too.

$ time perl frac.pl
There are XXX solutions

real    0m47.026s
user    0m46.963s
sys     0m0.008s

Ocaml Solution

let rec gcd a b =
  if b = 0 then a
  else gcd b (a mod b);;

let solve_it max_denom =
  let rec loop num denom solutions =
    if denom > max_denom then solutions
    else if num >= (denom/2+1) then
      loop ((denom+1)/3+1) (denom+1) solutions
    else begin
      if gcd num denom = 1 then begin
        (* Printf.printf "%d/%d\n" num denom; *)
        loop (num+1) denom (solutions+1)
      end else
        loop (num+1) denom solutions
    end
  in
    loop ((5/3)+1) 5 0;;

Printf.printf "There are %d solutions\n" (solve_it 1000);;

Oh dear, I seem to have an awful accent when programming ocaml. I’ll need to work on that.

$ time ./a.out
There are XXX solutions

real    0m1.071s
user    0m1.060s
sys     0m0.004s

So, Conclusions

For this particular task (looping and integer math) Emacs Lisp is slow, but not that slow compared with another scripting language. I really like the scheme looping constructs and mzscheme is surprisingly quick (again, just for this tiny thing), not too far from the ocaml – although again I should emphasise that the ocaml is a terrible hack. And finally, I need to learn how to use loop properly.

All comments welcome.

Read Full Post »

Follow

Get every new post delivered to your Inbox.