Arithmetic with uLisp & Maximum Cells in Due?

[Aeneas]

Hi @johnsondavies & all others,

I downloaded uLisp Zero and tested it on an Arduino Due. So far, it seems to “kind of work”, but indeed it seems that a lot of stuff is missing. In particular, is there any way to get arithmetic on the Due? I tried using “+” and “=” and “zerop”, but it looks like those functions are not implemented. The language reference shows them listed for “normal” uLisp. Any chance to get a “NORMAL” uLisp on the Due? Or at least a version with arithmetic? - I really picked the Due as a “somewhat more capable” device (more memory, faster) and hoped to make some AI experiment with it and uLisp (instead of C and Uno). :)

Maybe I am missing something, but I did not find a language reference for uLisp Zero, nor a “normal” uLisp for the Due - if the mistake is mine, I beg your apologies. Kindly show me, if possible, where to find them.

Next question: is the cell limit really 8000 - or perhaps 8192 or so? If the due has 96 KB RAM, and once cell takes 4 bytes, shouldn’t the limit even be substantially higher?

From looking at the C source of uLisp zero (which is very tidy, but which I still do not understand), I see basically only list manipulation functions, no arithmetic. I need no strings anyway, but arithmetic would be very nice. Unfortunately, I am not good in C, so I cannot really add these myself. So - what are my options? :) If I have to wait a month or two should you be so kind to be willing to add them (or port “normal” uLisp to the Due), it would be fine, too…

[johnsondavies]

You’re not missing anything - uLisp Zero doesn’t include any arithmetic functions. It’s just that the full version of uLisp hasn’t yet been ported to the Due. I ported uLisp Zero first because it was substantially easier to get it working. Given your encouragement I’ll resume work on porting the full uLisp to the Due, and let you know when I expect to get it done.

As far as the cell limit is concerned, you can increase this by changing the line:

#define WORKSPACESIZE 320

to:

#define WORKSPACESIZE 8000

You could add the arithmetic functions from the full uLisp to uLisp Zero, but it’s probably not worth the effort because the full version should be ready soon. In the meantime I suggest getting hold of one of the boards that’s currently compatible with uLisp:

http://www.ulisp.com/show?3M#recommended-platforms

Anything you develop will be compatible with the Arduino Due version when its ready.

[Aeneas]

Hi @johnsondavies,

I did something a tad unusual - and I will publish it on GitHub, too, after tidying it up a bit, but you may have it already:

I implemented math in uLisp Zero from within Lisp, as far as that was possible for me. Here it is, the four basic computing functions… I am posting it for other desperate souls, and besides, I think it is a nice “heavy test” of your Lisp, as it is quite a collection of interconnected functions. ;) You have an impressive piece of work there as interpreter. (In case you would like to include that with your MIT licensed materials - I clearly consent to that.) Unfortunately, it leaves only just over 4k cells free, i.e. it is fine for the Arduino Due, but not for machines with less RAM. (It also contains a few “not strictly needed” functions, namely vl2 (“or”), aut (“xor”), loe (“lower or equal”), ekl (“equally long”), tkf (“take first n elements of list”), which could be trimmed, too, if desired.

(defvar n0 nil)

(defvar n1 (cons nil n0))

(defvar n2 (cons nil n1))

(defvar n3 (cons nil n2))

(defvar n4 (cons nil n3))

(defvar n5 (cons nil n4))

(defvar n6 (cons nil n5))

(defvar n7 (cons nil n6))

(defvar n8 (cons nil n7))

(defvar n9 (cons nil n8))

(defun nul (x) (eq nil x))

(defun ekv (x y)
  (if (nul x)
    (if (nul y)
      t
      nil)
    (if (symbolp x)
      (if (symbolp y)
        (eq x y)
        nil)
      (if (consp x)
        (if (consp y)
          (if (ekv (car x) (car y))
            (ekv (cdr x) (cdr y))
            nil)
          nil)
        nil))))

(defun et2 (x y)
  (if x
    (if y
      t
      nil)
    nil))

(defun vl2 (x y)
  (if x
    t
    (if y
      t
      nil)))

(defun aut (x y) (et2 (not (et2 x y)) (vl2 x y)))

(defun rer (x y)
  (if (nul x)
    y
    (rer (cdr x) (cons (car x) y))))

(defun rev (x) (rer x nil))

(defun ap2 (x y) (rev (rer y (rev x))))

(defun lon (x y)
  (if (nul x)
    nil
    (if (nul y)
      t
      (lon (cdr x) (cdr y)))))

(defun ls1 (x) (cons x nil))

(defun loe (x y)
  (if (nul y)
    t
    (if (nul x)
      nil
      (loe (cdr x) (cdr y)))))

(defun ekl (x y)
  (if (nul x)
    (if (nul y)
      t
      nil)
    (if (nul y)
      nil
      (ekl (cdr x) (cdr y)))))

(defun san (n l r)
  (if (nul n)
    (cons (rev r) l)
    (if (nul l)
      (quote (nil))
      (san (cdr n) (cdr l) (cons (car l) r)))))

(defun tkf (n l) (car (san n l nil)))

(defun tka (n l) (cdr (san n l nil)))

(defun pic (x)
  (if (nul x)
    (quote ((nil)))
    (if (ekv n9 (car x))
      (cons n0
        (pic (cdr x)))
      (cons
        (cons nil (car x))
        (cdr x)))))

(defun icr (x)
  (if (nul x)
    (quote ((nil)))
    (if (ekv (quote (nil)) x)
      (quote ((nil)))
      (if (eq (quote P) (car x))
        (icr (cdr x))
        (rev (pic (rev x)))))))

(defun rac (c x y r)
  (if (not (nul c))
    (rac nil (pic x) y r)
    (if (et2 (nul x) (nul y))
      r
      (if (nul x)
        (ap2 (rev y) r)
        (if (nul y)
          (ap2 (rev x) r)
          (if (lon (ap2 (car x) (car y))
                   (quote
                     (nil nil nil nil
                     nil nil nil nil nil)))
            (rac t
                 (cdr x)
                 (cdr y)
                 (cons
                   (tka (quote
                          (nil nil nil nil nil
                          nil nil nil nil nil))
                        (ap2 (car x) (car y)))
                   r))
            (rac nil
                 (cdr x)
                 (cdr y)
                 (cons (ap2 (car x) (car y))
                       r))))))))

(defun adp (x y) (rac nil (rev x) (rev y) nil))

(defun pdc (x)
  (if (nul x)
    nil
    (if (ekv x (quote (nil)))
      nil
      (if (ekv n0 (car x))
        (cons n9
          (pdc (cdr x)))
        (cons (cdr (car x))
              (cdr x))))))

(defun rlz (x) (if (nul (car x)) (cdr x) x))

(defun raz (x)
  (if (nul x)
    (quote (nil))
    (if (nul (car x))
      (raz (cdr x))
      x)))

(defun dcr (x)
  (if (nul x)
    nil
    (if (ekv x (quote (nil)))
      (quote (nil))
      (if (ekv x (quote ((nil))))
        (quote (nil))
        (if (ekv (quote P) (car x))
          (dcr (cdr x))
          (rlz (rev (pdc (rev x)))))))))

(defun rsc (c x y r)
  (if (not (nul c))
    (rsc nil (rev (dcr (rev x))) y r)
    (if (et2 (nul x) (nul y))
      r
      (if (nul x)
        nil
        (if (nul y)
          (ap2 (rev x) r)
          (if (lon (car y) (car x))
            (rsc t
                 (cdr x)
                 (cdr y)
                 (cons
                   (tka (car y)
                        (quote
                        (nil nil nil nil nil
                        nil nil nil nil nil)))
                   r))
            (rsc nil
                 (cdr x)
                 (cdr y)
                 (cons (tka (car y) (car x))
                       r))))))))

(defun sbp (x y) (raz (rsc nil (rev x) (rev y) nil)))

(defun cpn (x y)
  (if (et2 (nul x) (nul y))
    (quote (nil))
    (if (nul y)
      t
      (if (nul x)
        nil
        (if (lon x y)
          t
          (if (lon y x)
            nil
            (if (lon (car x) (car y))
              t
              (if (lon (car y) (car x))
                nil
                (cpn (cdr x) (cdr y))))))))))

(defun pa2 (x y)
  (if (nul x)
    y
    (if (nul y)
      x
      (if (et2 (eq (quote P) (car x))
               (eq (quote P) (car y)))
        (cons (quote P) (adp (cdr x) (cdr y)))
        (if (et2 (eq (quote M) (car x))
                 (eq (quote M) (car y)))
          (cons (quote M) (adp (cdr x) (cdr y)))
          (if (et2 (et2 (eq (quote P) (car x))
                        (eq (quote M) (car y)))
                   (cpn (cdr x) (cdr y)))
            (cons (quote P) (sbp (cdr x) (cdr y)))
            (if (et2 (eq (quote P) (car x))
                     (eq (quote M) (car y)))
              (cons (quote M) (sbp (cdr y) (cdr x)))
              (if (et2 (et2 (eq (quote M) (car x))
                            (eq (quote P) (car y)))
                       (cpn (cdr y) (cdr x)))
                (cons (quote P) (sbp (cdr y) (cdr x)))
                (if (et2 (eq (quote M) (car x))
                         (eq (quote P) (car y)))
                  (cons (quote M) (sbp (cdr x) (cdr y)))
                  nil)))))))))

(defun nnn (x)
  (if (not (listp x))
    nil
    (if (nul x)
      t
      (if (nul (car x))
        t
        (if (nul (car (car x)))
          t
          nil)))))

(defun rlp (x)
  (if (nul x)
    nil
    (if (eq (car x) (quote P))
      (cdr x)
      x)))

(defun mad (x y)
  (if (nul x)
    y
    (if (nul y)
      x
      (if (et2 (nnn (car x)) (nnn (car y)))
        (rlp (pa2 (cons (quote P) (raz x))
                  (cons (quote P) (raz y))))
        (if (nnn (car x))
          (rlp (pa2 (cons (quote P) (raz x))
                    (cons (car y) (raz (cdr y)))))
          (if (nnn (car y))
            (rlp (pa2 (cons (car x) (raz (cdr x)))
                      (cons (quote P) (raz y))))
            (rlp (pa2 (cons (car x) (raz (cdr x)))
                      (cons (car y) (raz (cdr y)))))))))))

(defun msu (x y)
  (if (nul y)
    x
    (if (eq (quote M) (car y))
      (mad x (cdr y))
      (if (eq (quote P) (car y))
        (mad x (cons (quote M) (cdr y)))
        (if (nul (car y))
          (mad x (cons (quote M) y))
          (if (nul (car (car y)))
            (mad x (cons (quote M) y))
            nil))))))

(defun pml (x y r)
  (if (nul x)
    r
    (if (nul y)
      r
      (if (ekv x (quote (nil)))
        r
        (if (ekv y (quote (nil)))
          r
          (pml (dcr x) y (mad y r)))))))

(defun mmu (x y)
  (if (et2 (eq (car x) (quote M))
           (eq (car y) (quote M)))
    (pml (cdr x) (cdr y) (quote (nil)))
    (if (eq (car x) (quote M))
      (cons (quote M) (pml (cdr x) y (quote (nil))))
      (if (eq (car y) (quote M))
        (cons (quote M) (pml x (cdr y) (quote (nil))))
        (pml x y (quote (nil)))))))

(defun pdv (x y r)
  (if (nul x)
    r
    (if (ekv x (quote (nil)))
      r
      (if (nul y)
        (quote (nil))
        (if (ekv y (quote (nil)))
          (quote (nil))
          (if (not (cpn x y))
            r
            (pdv (msu x y) y (icr r))))))))

(defun mdv (x y)
  (if (et2 (eq (car x) (quote M))
           (eq (car y) (quote M)))
    (pdv (cdr x) (cdr y) (quote (nil)))
    (if (eq (car x) (quote M))
      (cons (quote M) (pdv (cdr x) y (quote (nil))))
      (if (eq (car y) (quote M))
        (cons (quote M) (pdv x (cdr y) (quote (nil))))
        (pdv x y (quote (nil)))))))

(defun n2m (x)
  (if (nul x)
    nil
    (if (eq (car x) (quote P))
      (cons (quote P)
        (n2m (cdr x)))
    (if (eq (car x) (quote M))
      (cons (quote M)
        (n2m (cdr x)))
    (if (eq (car x) (quote 0))
      (cons n0
        (n2m (cdr x)))
    (if (eq (car x) (quote 1))
      (cons n1
        (n2m (cdr x)))
    (if (eq (car x) (quote 2))
      (cons n2
        (n2m (cdr x)))
    (if (eq (car x) (quote 3))
      (cons n3
        (n2m (cdr x)))
    (if (eq (car x) (quote 4))
      (cons n4
        (n2m (cdr x)))
    (if (eq (car x) (quote 5))
      (cons n5
        (n2m (cdr x)))
    (if (eq (car x) (quote 6))
      (cons n6
        (n2m (cdr x)))
    (if (eq (car x) (quote 7))
      (cons n7
        (n2m (cdr x)))
    (if (eq (car x) (quote 8))
      (cons n8
        (n2m (cdr x)))
    (if (eq (car x) (quote 9))
      (cons n9
        (n2m (cdr x)))))))))))))))))

(defun m2n (x)
    (if (nul x)
    nil
    (if (eq (car x) (quote P))
      (cons (quote P)
        (m2n (cdr x)))
    (if (eq (car x) (quote M))
      (cons (quote M)
        (m2n (cdr x)))
    (if (ekv (car x) n0)
      (cons (quote 0)
        (m2n (cdr x)))
    (if (ekv (car x) n1)
      (cons (quote 1)
        (m2n (cdr x)))
    (if (ekv (car x) n2)
      (cons (quote 2)
        (m2n (cdr x)))
    (if (ekv (car x) n3)
      (cons (quote 3)
        (m2n (cdr x)))
    (if (ekv (car x) n4)
      (cons (quote 4)
        (m2n (cdr x)))
    (if (ekv (car x) n5)
      (cons (quote 5)
        (m2n (cdr x)))
    (if (ekv (car x) n6)
      (cons (quote 6)
        (m2n (cdr x)))
    (if (ekv (car x) n7)
      (cons (quote 7)
        (m2n (cdr x)))
    (if (ekv (car x) n8)
      (cons (quote 8)
        (m2n (cdr x)))
    (if (ekv (car x) n9)
      (cons (quote 9)
        (m2n (cdr x)))))))))))))))))

; P plus, M minus; ulisp zero 1.1 does not accept + and -,
; not even quoted - but principally they could be parsed,
; too.
; symbolic increase of positive number:
(defun sic (x) (m2n (icr (n2m x))))
; (sic (quote (2 4 9 9))) --> (2 5 0 0)

; symbolic decrease of positive number - 0 floor:
(defun sdc (x) (m2n (dcr (n2m x))))

; symbolic addition x + y:
(defun sad (x y) (m2n (mad (n2m x) (n2m y))))
; (sad (quote (M 1)) (quote (M 9 9 9))) --> (M 1 0 0 0)

; symbolic subtraction x - y:
(defun ssu (x y) (m2n (msu (n2m x) (n2m y))))
; (ssu (quote (M 1 2)) (quote (M 9 9 9))) --> (9 8 7)

; symbolic multiplication x * y; takes an eternity:
(defun smu (x y) (m2n (mmu (n2m x) (n2m y))))
; (smu (quote (3 4)) (quote (P 2 1 2))) --> (7 2 0 8)
; i.e. the "plus"-sign is optional, just as in "normal" maths.

; symbolic division x / y, discarding the remainder; takes a TOTAL eternity:
(defun sdv (x y) (m2n (mdv (n2m x) (n2m y))))
; (sdv (quote (2 5 9)) (quote (M 1 2))) --> (M 2 1)

; cells: 4307

Kind regards,

Nino Ivanov

[johnsondavies]

That’s mad but very ingenious!

I’ve defined the code as preformatted text to preserve the Lisp structure. A couple of suggestions:

You might be able to replace the lists of nested if statements with recursive functions. For example, to convert a list of nils to a digit:

(defun ln2 (x y)
  (if (null x) (car y)
    (ln2 (cdr x) (cdr y))))

(defun len (x)
  (ln2 x '(0 1 2 3 4 5 6 7 8 9)))

For example:

>  (len '(nil nil nil nil))
4

And to convert a digit to a list of nils:

(defun li2 (n y)
  (if (eq n (car y))
      nil
    (cons nil (li2 n (cdr y)))))

(defun lis (n) 
  (li2 n '(0 1 2 3 4 5 6 7 8 9)))

For example:

> (lis '8)
(nil nil nil nil nil nil nil nil)

Note, you can replace (quote x) with 'x.

[Aeneas]

Oh, thank you!

These last “parsing” functions really took me a lot of cells, your alternative appears MUCH more compact and faster!