New beta 2 release of ARM uLisp for feedback

#1

I’ve released an updated version of the beta release of ARM uLisp, adding a few features to the first beta release. For details of the features in the first beta see: New beta version of ARM uLisp with new features for feedback.

Get the new release from GitHub here: uLisp ARM Beta.

The main new features are:

• More helpful error messages from format; for example
``````> (format t "The result is ~a ~q" 42)
The result is 42
"The result is ~a ~q"
^
Error: 'format' invalid directive
``````
• The ability to predefine a one-dimensional or two-dimensional array; for example:
``````> (defvar a #2a((1 2 3) (4 5 6)))
a

> a
#2A((1 2 3) (4 5 6))
``````

Sudoku solver

Here’s an amusing sudoku solver that I’ve been using as a benchmark; it demonstrates the new array and format features. It is based on a program by Daniele Mazzocchio of Kernel Panic: Sudokiller.lisp.

First you define the problem, using 0 for empty cells. This is one designed by Dr Arto Inkala of Finland, said to be the world’s hardest sudoku!

``````(defvar board
#2a((0 0 5 3 0 0 0 0 0)
(8 0 0 0 0 0 0 2 0)
(0 7 0 0 1 0 5 0 0)
(4 0 0 0 0 5 3 0 0)
(0 1 0 0 7 0 0 0 6)
(0 0 3 2 0 0 0 8 0)
(0 6 0 5 0 0 0 0 9)
(0 0 4 0 0 0 0 3 0)
(0 0 0 0 0 9 7 0 0)))
``````

Note that the program fills in the array as it solves the sudoku, so if you want to run it again you need to reinitialise the array.

Here’s the program:

``````(defun guess (index)
(let ((row (truncate index 9))
(col (mod index 9)))
(cond
((or (>= row 9) (>= col 9)) t)
((plusp (aref board row col)) (guess (1+ index)))
(t
(dotimes (i 9 (fail row col))
(when (check (1+ i) row col)
(setf (aref board row col) (1+ i))
(when (guess (1+ index)) (return t))))))))

(defun fail (row col)
(setf (aref board row col) 0)
nil)
``````

The guess routine calls check to check that the number is the current cell obeys the sudoku rules:

``````(defun check (num row col)
(let ((r (* (truncate row 3) 3))
(c (* (truncate col 3) 3)))
(dotimes (i 9 t)
(when (or (= num (aref board row i))
(= num (aref board i col))
(= num (aref board (+ r (mod i 3))
(+ c (truncate i 3)))))
(return nil)))))
``````

Finally, print-board uses format statements to print the solution in a readable layout:

``````(defun print-board ()
(dotimes (r 9)
(if (zerop (mod r 3))
(format t "~%+---+---+---+---+---+---+---+---+---+~%|")
(format t "~%+           +           +           +~%|"))
(dotimes (c 9)
(if (= 2 (mod c 3))
(format t " ~a |" (aref board r c))
(format t " ~a  " (aref board r c)))))
(format t "~%+---+---+---+---+---+---+---+---+---+~%~%"))
``````

To run the program call (solve):

``````(defun solve ()
(if (guess 0) (print-board)
``````

The program prints out the solution; for example here’s the solution to a different sudoku, in case you want to try solving the world’s hardest sudoku by hand before running the program.

``````> (solve)

+---+---+---+---+---+---+---+---+---+
| 9   6   3 | 1   7   4 | 2   5   8 |
+           +           +           +
| 1   7   8 | 3   2   5 | 6   4   9 |
+           +           +           +
| 2   5   4 | 6   8   9 | 7   3   1 |
+---+---+---+---+---+---+---+---+---+
| 8   2   1 | 4   3   7 | 5   9   6 |
+           +           +           +
| 4   9   6 | 8   5   2 | 3   1   7 |
+           +           +           +
| 7   3   5 | 9   6   1 | 8   2   4 |
+---+---+---+---+---+---+---+---+---+
| 5   8   9 | 7   1   3 | 4   6   2 |
+           +           +           +
| 3   1   7 | 2   4   6 | 9   8   5 |
+           +           +           +
| 6   4   2 | 5   9   8 | 1   7   3 |
+---+---+---+---+---+---+---+---+---+
``````

On an ATSAMD51-based Adafruit PyBadge the world’s hardest sudoku takes approximately 2.5 minutes to solve.

Here’s the whole sudoku program in a single file: Sudoku solver program.

#2

(Way below) I think I discovered a bug.

This works as expected - one CAN make a four-dimensional array by combining two 2D-arrays:
(make-array '(3 2) :initial-element (make-array '(3 2) :initial-element 0))
–>
#2A((#2A((0 0) (0 0) (0 0)) #2A((0 0) (0 0) (0 0))) (#2A((0 0) (0 0) (0 0)) #2A((0 0) (0 0) (0 0))) (#2A((0 0) (0 0) (0 0)) #2A((0 0) (0 0) (0 0))))

and so does (make-array '(3 2) :initial-element (make-array '(2 3) :initial-element 0))

EDIT: OK, I messed up the syntax, so this is actually more my fault than make-arrays - 3d-array-structures as arrays-of-arrays ARE ENTIRELY possible:

(make-array '4 :initial-element (make-array '(3 2) :initial-element 'A))
–>
#(#2A((a a) (a a) (a a)) #2A((a a) (a a) (a a)) #2A((a a) (a a) (a a)) #2A((a a) (a a) (a a)))

(make-array '(4 3) :initial-element (make-array '2 :initial-element 'A))
–>
#2A((#(a a) #(a a) #(a a)) (#(a a) #(a a) #(a a)) (#(a a) #(a a) #(a a)) (#(a a) #(a a) #(a a)))

As to 3D-structures, one can actually use a mix of array and list, too:
(make-array '(3 2) :initial-element (list 'A 'B 'C))
–>
#2A(((a b c) (a b c)) ((a b c) (a b c)) ((a b c) (a b c)))

The non-uniform access to arrays, i.e. that one-dimensional just use the dimension as an argument, e.g. '4, whereas two-dimensional use a list of dimensions, e.g. '(3 2), at first distracted me… actually, given that one can make any array also like this:

(make-array '4 :initial-element (make-array '3 :initial-element (make-array '2 :initial-element 'A)))
–>
#(#(#(a a) #(a a) #(a a)) #(#(a a) #(a a) #(a a)) #(#(a a) #(a a) #(a a)) #(#(a a) #(a a) #(a a)))

… one actually have an uniform array accessor style at all times, with n dimensions.

Now come a few errors which are a GOOD thing - just for the sake of completeness that I tested this:

car & cdr indeed do not work:

(car (make-array '(3 2) :initial-element 0))
Error: Can’t take car: #2A((0 0) (0 0) (0 0))

(cdr (make-array '(3 2) :initial-element 0))
Error: Can’t take cdr: #2A((0 0) (0 0) (0 0))

aref does not work on lists:

(aref '(A B C) 2)
Error: ‘aref’ first argument is not an array: (a b c)

(aref (make-array '(3 2) :initial-element 0) 1 1)
0

(aref (make-array '(3 2) :initial-element 0) 1 1)
0 - which is OK, and:
(aref (make-array '(3 2) :initial-element 0) 1)
Error: ‘aref’ array needs two subscripts

On to other things: setq no more works to “initialise” a variable, one HAS TO defvar before using it, but OK, that is recommended CL practice anyway:
(setq Y 2)
–>
Error: unknown variable: y

An equality-test works:

(eq (aref (make-array '(3 2) :initial-element 'A) 1 2) (aref (make-array '(3 2) :initial-element 'A) 2 1))
–>
t

Now, a little weirdness - this gives me obviously an array of 3 x 2:
(make-array '(3 2) :initial-element 'A)
–>
#2A((a a) (a a) (a a))

… whose first element is (0 0):
(aref (make-array '(3 2) :initial-element 'A) 0 0)
–>
a

… and if I push the boundary, it tells me I am overdoing it:
(aref (make-array '(3 2) :initial-element 'A) 3 2)
–>
Error: ‘aref’ index out of range

… and indeed it does still check the first dimension alone:
(aref (make-array '(3 2) :initial-element 'A) 3 0)
–>
Error: ‘aref’ index out of range

… but apparently it does NOT check the second dimension:
(aref (make-array '(3 2) :initial-element 'A) 0 2)
–>
a

… not even if I go out of bound:
(aref (make-array '(3 2) :initial-element 'A) 0 4)
–>
a

… and this seems to turn off detection of negative indices in the FIRST dimension, too:
(aref (make-array '(3 2) :initial-element 'A) -1 4)
–>
a

… which it otherwise detects nicely:
(aref (make-array '(3 2) :initial-element 'A) -1 -1)
–>
Error: ‘aref’ index out of range
(aref (make-array '(3 2) :initial-element 'A) 0 -1)
–>
Error: ‘aref’ index out of range
(aref (make-array '(3 2) :initial-element 'A) -1 1)
–>
Error: ‘aref’ index out of range
(aref (make-array '(3 2) :initial-element 'A) -1 -1)
–>
Error: ‘aref’ index out of range

Now, on to other topics. This is GOOD:
(setf 'X (aref (make-array '(3 2) :initial-element 'A)))
Error: ‘setf’ illegal place

This WORKS, and so does setf:
(setq X (aref (make-array '(3 2) :initial-element 'A) 1 1))

This works, too:
(setq X (make-array '(3 2) :initial-element 'A))

This works as well:
(setf (aref X 1 1) 'B)
–>
b

X
–>
#2A((a a) (a b) (a a))

And so does this:
(aref (make-array '(3 2) :initial-element 'A) 1 1)
–>
a

EDIT: and so does this:
(setf (aref (make-array '(3 2) :initial-element 'A) 1 1) 'B)
–>
b

OK, ENDING this particular test - so the kind reader can rely that not something will change again…

#3

And I just tested loop-returns, and they seem to operate ok:

(make-array (let ((x '()) (y 3)) (progn (loop (setq x (cons y x)) (cond ((zerop y) (return (reverse (cddr x))))) (decf y)))) :initial-element (progn (let ((x '()) (y 3)) (loop (setq x (cons y x)) (cond ((zerop y) (return (cdr (reverse x))))) (decf y)))))

as well as

(make-array (let ((x '()) (y 3)) (loop (setq x (cons y x)) (cond ((zerop y) (return (reverse (cddr x))))) (decf y))) :initial-element (let ((x '()) (y 3)) (loop (setq x (cons y x)) (cond ((zerop y) (return (cdr (reverse x))))) (decf y))))

both give

#2A(((2 1 0) (2 1 0)) ((2 1 0) (2 1 0)) ((2 1 0) (2 1 0)))

#4

Thanks for the feedback! I’ll check them out.

#5

Is disabling the gc for each run of the REPL intentional?

#6

No, thanks for spotting it, that was a mistake (done during debugging). I’ll fix it for release.

#7

No, you did find a bug; this should work:

``````> (make-array '(2))
Error: 'make-array' argument is not an integer: nil
``````

It should be the same as:

``````(make-array 2)
``````

Another bug - thanks.

By the way, another way to create arrays of more than two dimensions is to manage the index calculation yourself. For example, to make a 10x10x10 array:

``````(defvar myarray (make-array (* 10 10 10) :initial-element 0))
``````

Then define this index function:

``````(defun ix (x y z) (+ (* x 100) (* y 10) z))
``````

Then, to set element (2, 3, 4) do:

``````(setf (aref myarray (ix 2 3 4)) 42)
``````

or to get the value of element (2, 3, 4) do:

``````(aref myarray (ix 2 3 4))
``````

Thanks for the bugs!

#8

That is s’pose to be the hardest Sudoku puzzle?
It was one of the easiest ones I’ve solved in the past
few weeks.

#9

I’ve uploaded a new version of the ARM 3.2 Beta to GitHub. It fixes the two array bugs that @Aeneas reported, and a gc bug that @odin reported: uLisp ARM Beta.

#10

Incidentally, is there a particular reason the beta is in a distinct repository and with a different filename? It seems like the more sensible thing would be a branch in the main repository.

#11

You’re probably right - I was planning to delete the repository when the full version is released.

#12

I have a copy of sorts; I’ve been copying the files over to a branch in my repository in order to keep the immediates code in sync with the betas.

#13

First of all, let me THANK YOU, David, for the index function you exemplified - it is of course a lot saner and much more “like a computer handles linear memory” than that rube-goldberg-“array” I came up with. :)

I think I got one more “bug” (which only triggers if one behaves like a moron), and a more serious bug with (load-image):

(make-array '(2))
–>
#(nil nil)

• whereby '(2) is synonymous to '2 and 2.

By the way, (make-array -2) DOES actually create an array, just it is #(). This further has interesting implications:

(make-array '(2 -2) :initial-element 'A)
–>
#2A(() ())

(make-array '(-2 -2) :initial-element 'A)
–>
#2A()

(make-array '(-2 2) :initial-element 'A)
–>
#2A()

(make-array '(0 0) :initial-element 'A)
–>
#2A()
(This is really the only “non-idiot”-case I came up with - it is not entirely unimaginable that someone could ever want a 2d-empty-array.)

NOW, THE BUG: if you give at the terminal “#2A(() ())”, it accepts it, and for #2A() it throws, “Error: initial contents not 2d array”.

I know, “playing idiot with the constraints” is something which in a microcontroller environment is just something that cannot be entirely cushioned, so I understand that such “errors” can only be handled within reasonable measure - and could be just left unhandled, too.

Other than this, it actually looks VERY nice.

(print #( ) and (print #) ) work correctly

Regarding the line editor, Ctrl-M for Enter and Ctrl-H for Backspace work just nicely.

This: (aref (make-array '(3 2) :initial-element 'A) -1 4)
… nicely throws me an out of range error, and I also seemed to get all other out-of-range-errors nicely.

Now, on to the second bug: to test space, you, David, had once told me to use this procedure:

``````(defvar *big* nil)

(defun make (n) (setq *big* nil) (dotimes (x n) (push x *big*)))

(defun test (n)
(mapc #'(lambda (x) (unless (= x (- n 1)) (print x)) (decf n)) *big*)
nil)

(make 14000)

(test 14000)

(save-image)
``````

RESET

``````(load-image)

(test 14000)
``````

The thing is, after I enter (load-image) it ( = Grand Central M4) hangs. The line editor was enabled, but not the VT100 terminal. This was done using the internal memory, not an SD-card.

#14

That was intentional - would you expect something different?

By the way, (make-array -2) DOES actually create an array, just it is #().

That should cause an error.

for #2A() it throws, “Error: initial contents not 2d array”.

I think that’s OK, because it should be #2a(())

The second bug … The thing is, after I enter (load-image) it ( = Grand Central M4) hangs. The line editor was enabled, but not the VT100 terminal. This was done using the internal memory, not an SD-card.

Yes, I confirm I get the same problem. I’ll investigate - thanks!

#15

Oh, no, I did not expect anything different for '(2), '2 and 2, I just confirmed that it works! And yes, I totally agree with #2a(()), too! :)

#16

Thanks - just checking!

#17

There’s a new beta that fixes the problem @Aeneas found that large images may get corrupted when saved with save-image:

Also gives an error for negative array dimensions!

Regards,
David

#18

Thank you so very kindly for the quick adjustment! - I have merely two remarks:

I.

(eq #() #()) --> nil
(eq #2A(()) #2A(())) --> nil

Now, SBCL does that, too, BUT SBCL can also do (equalp #() #()) --> T

How is one supposed to check for an empty array? (Because if you aref it, you will get an error.)

II.

We are still getting #2A()-type replies. SBCL gives me them, too, but also accepts #2A() as input, whereas ulisp replies “Error: initial contents not 2d array”.

I am wondering shouldn’t the system rather: (i) either accept its own output and (ii) alternatively, if the output is inadmissible, produce an error. #() and #(()) are accepted just fine, so is #2A(()), but not #2A().

(make-array 0) --> #()
the empty array - of one dimension, with no content - OK

(make-array 1) --> #(nil)
the empty array - of one dimension, with one element, namely nil - OK

(make-array '(1 1)) --> #2A((nil))
a two-dimensional array, with just one element, namely nil - OK

(make-array '(1 0)) --> #2A(())
a two-dimensional-array, with no element - OK, and SBCL has it, too…

…but then this should produce #2A(()), after all, it would be symmetric to having the
respectively other dimension nuked:

(make-array '(0 1)) --> #2A()
SBCL replies with the same, but is also ready to accept #2A() as input.

And, finally, we have this questionable thing - SBCL behaves the same:
(make-array '(0 0)) --> #2A()

Again, “philosophically”, I think you were right that #2A(()) should be the answer - #2A(()) means “I am showing you the two dimensions, just there is nothing IN these dimensions”, and that is its real difference to the variant (make-array '(1 1)) --> #2A((nil)), which really says, “I have ONE element, and it is nil”. The real problem of a (1 0) or (0 1) test is that this is a “two-dimensional space where just ONE dimension has any extent”, and this is somewhat hard to comprehend, because then it should really be a one-dimensional array to begin with.

Anyway, if you disregard my ramblings, your system is behaving just akin to “traditional” CL, except that it then should accept #2A() as input as well.

Other than that, the other things appear to work just fine! :)

#19

Yes, you’re right, because at present it’s inconsistent:

``````> (make-array '(0 0))
#2A()

> #2a()
Error: initial contents not 2d array
``````

#20

Also, have you noticed that in Common Lisp:

``````CL-USER > (make-array '(0 0))
#2A()

CL-USER > (make-array '(0 1))
#2A()
``````

Weird! (Added - oh yes I see you mentioned that).