Grandmaster chess and Shen

[Antti Ylikoski]

This is a piece of wisdom about programming, that I have learned with
the Shen system.

One of the world chess masters (IIRC he was Robert Fischer) has said:

"If you discover a good more: Don't play it!"
Find a better one."

I have learned that this wisdom also applies to programming.

In authoring the multilever perceptron error backpropagation
algorithm, I needed the (butlast ...) Common LISP function in Shen.

Evidently, writing a (butlast ...) with Shen is an easy task.  It is
one!  But, the first version that I wrote was as follows:


------------------------------------------------------------


(define butlast
    { (list A) --> (list A) }
    [] -> []
    Lst ->
        (let L (length Lst)
        BL (- L 1)
        (first-items Lst BL)))


(define first-items
    { (list A) --> number --> (list A) }
    [] N -> []
    Lst N ->
        (first-items-h Lst N 1))


(define first-items-h
    { (list A) --> number --> number --> (list A) }
    Lst N Counter -> [] where (< N Counter)
    Lst N Counter -> [(head Lst)] where (= N Counter)
    Lst N Counter -> [ (head Lst) |
                       (first-items-h (tail Lst)
                                    N
                    (+ 1 Counter)) ])

------------------------------------------------------------

This definitely works, but it also definitely is not elegant!

I decided that I indeed must make something better.  Some thinking
resulted in the below mentioned (butlast ...) in Shen:


------------------------------------------------------------

\\ AJY 2016-07-02


(define butlast
    { (list A) --> (list A) }
    [] -> []
    Lst -> [] where (= (length Lst) 1)
    [H | T] -> [H] where (= (length T) 1)
    [H | T] -> [H | (butlast T)])


------------------------------------------------------------

Yes indeed: some thinking may very well lead to very much better code,
in the wisdom of Robert Fischer above.

Someone asked one of the international chess grandmasters, how that
person had learned to play chess so very well.

The grandmaster answered: I have studied the masters, not the lesser
players.

I like British computer science.

yours, A. J. Y.
HELSINKI
Finland, the E.U.

[Mark Tarver]

(define butlast

  {(list A) --> (list A)}

  [] -> []

  [_] -> []

  [X | Y] -> [X | (butlast Y)])

  

is probably the simplest def.

Mark

[fuzzy wozzy]

(define butlast
    L -> (reverse (tl (reverse L))))

this avoids going into stack overflow when (length L) > 70000

[Antti Ylikoski]

That was very smart from fuzzy wozzy's part.

With types:

----------------------------------------

(define butlast
    { (list A) --> (list A) }

    L -> (reverse (tail (reverse L))))

---------------------------------------

I almost hope that this perceptron program of mine were not proprietary -- so that I could get flashes of intellect
such as that, for my program!

And yes, there was a VERY annoying typo in that entry: it should have been:

"I like THE British computer science."

I was too tired ........

A. J. Y.

[fuzzy wozzy]

it depends on what you need for your program,
consing an answer straightforward can cause a stack overflow,
even for a simple list of iteration from 0 to 70000,
for more complex lists, it would take less than that to have stack overflow,

the reverse/tl/reverse is so fast that it takes less than 2 seconds to remove
the last item of a list whose length is 10 million.

[fuzzy wozzy]

if you use "tail" instead of "tl", then "[] -> []" needs to be included,
otherwise you get an error message,

(butlast [])
tail expects a non-empty list

[Mark Tarver]

Actually checking BUTLAST in CL it has an optional parameter that is set AFAIK to 1.   To encode this in Shen you need a macro.

Mark

On Saturday, July 2, 2016 at 6:44:25 PM UTC+1, Antti Ylikoski wrote:

[Willi Riha]

Mark's version of the butlast function is not tail-recursive. Here is the obvious tail-recursive version

(define butlast

  {(list A) --> (list A)}

   [] -> []

   X -> (butlast-h X []))

(define butlast-h

  {(list A) --> (list A) --> (list A)}

   [_] B -> B

   [X | Y] B -> (butlast-h Y (append B [X])))

The generalisation of butlast with an extra parameter is often known as the "drop" function, i.e (BUTLAST {1 2 3 4 5] 3) is [1 2] 

meaning, you drop the last 3 items.

There is also a function (not in CL), known as "take" where (take X K) takes the first K elements of X, and hence drops the last N - K elements,

where N is the length of the X.

Here is a (tail-recursive) Shen implementation :

(define take

  {(list A) --> number --> (list A)}

   _ K -> [] where (<= K 0)

   X K -> (take-h X K []))

(define take-h

  {(list A) --> number --> (list A) --> (list A)}

   [] _ B -> B

   X 0 B -> B

   [X | Y] K B -> (take-h Y (- K 1) (append B [X])))

The drop function becomes

(define drop

  {(list A) --> number --> (list A)}

   X K -> (take X (- (length X) K)))

I do not know if it is possible to implement "drop" without determining the length of the list, or using "reverse" twice.

 

On Saturday, July 2, 2016 at 6:44:25 PM UTC+1, Antti Ylikoski wrote:

[fuzzy wozzy]

\*
(drop 3 [1 2 3 4 5])
[4 5]

(drop1 3 [1 2 3 4 5])
[1 2]
*\

(define drop
    0 L -> L
    N L -> (drop (- N 1) (tl L)))

(define drop1
    N L -> (drop1x N (reverse L)))

(define drop1x
    0 L -> (reverse L)
    N L -> (drop1x (- N 1) (tl L)))

[fuzzy wozzy]

\* (drop2 3 [1 2 3 4 5]) = [1 2] *\

(define drop2
    N L -> (reverse (drop N (reverse L))))