Output of Lisp code

[radhakris...@gmail.com]

Hi,

I have converted the Lisp code to haskell. Trying to understand
fully what Lisp does.

What output does the Lisp code produce for an input of [0,0,0,8] for both lists ?

Alternately a brief explanation of the numeric representation created by this Lisp code will also do.

Lisp :

(defvar powers-of-2
(make-array 10
:initial-contents
(cons nil (loop for i below 9 collect (expt 2 i)))))

(defun state-index (X-locations O-locations)
(+ (loop for l in X-locations sum (aref powers-of-2 l))
(* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))

Haskell :

powersof2 :: [Int]
powersof2 = [ 2 ^ i | i <- [0..9]]

stateindex :: [Int] -> [Int] -> Int
stateindex xloc oloc = let powers = powersof2 in
((foldl (+) 0 [ ( powers !!n) | n <- [0..(length xloc - 1)]]) +
( 512 * foldl (+) 0 [ ( powers !!n) | n <- [0..(length oloc - 1)]]))

Thanks,
Mohan

[Madhu]

* radhakris...@gmail.com in article
<a825aac9-e9d5-42db...@googlegroups.com>
Wrote on Wed, 15 Mar 2017 22:55:29 -0700 (PDT):

| I have converted the Lisp code to haskell

Why on earth would you do that?

| Trying to understand fully what Lisp does.

Maybe you should try to understand what problem the lisp code solves in
the first place. To just understand what the lisp code does you just
have to read the lisp code for that.

|
| Alternately a brief explanation of the numeric representation created
| by this Lisp code will also do.
|
| Lisp :
|
| (defvar powers-of-2
| (make-array 10
| :initial-contents
| (cons nil (loop for i below 9 collect (expt 2 i)))))

This looks wrong. The array indices are 0 based and 2^0 = 1. However
this array shows 2^0 = NIL.

* powers-of-2
#(NIL 1 2 4 8 16 32 64 128 256)

Instead you should define this as

(defparameter powers-of-2
(make-array 10 :initial-contents (loop for i below 10 collect (expt 2 i))))

| (defun state-index (X-locations O-locations)
| (+ (loop for l in X-locations sum (aref powers-of-2 l))
| (* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))

obviously this computes \sum_i 2^{x_i} + 512 * \sum_i 2^{o_i}

| What output does the Lisp code produce for an input of [0,0,0,8] for
| both lists ?

I assume this curious sentence actually means: what does the call to

(state-index '(0 0 0 8) '(0 0 0 8))

After my correction to powers-of-2, if you run the code in a lisp
compiler, it produces 132867.

| Haskell
[snip]

I suggest forget about haskell, learn common lisp and develop a sound
aesthetic for lisp. Haskell is no good for a lisp programmer. If you
want to see the detrimental effects of haskell on lisp, look at abolute
abomination of "modern" (ironical) emacs lisp, after "hakelistas" from
the bottomless pit subverted and dominated the development.

[Barry Fishman]

On 2017-03-15 22:55:29 +07, radhakris...@gmail.com wrote:
> I have converted the Lisp code to haskell. Trying to understand
> fully what Lisp does.

Haskell is a functional lazy language with compile time typed variables.
Lisp is the opposite of that. Using Haskell to understand Lisp seems to
be problematic since each usually requires a different approach to
solving a problems, and a direct translation of code is often
inefficient or just broken.

> Alternately a brief explanation of the numeric representation created
> by this Lisp code will also do.
>
> Lisp :
>
> (defvar powers-of-2
> (make-array 10
> :initial-contents
> (cons nil (loop for i below 9 collect (expt 2 i)))))

This really isn't a powers of two function.

In Haskell this is not expressible, since a list can not contain mixed
types. The closest might be:

powersOf2 :: [Maybe Int]
powersOf2 = Nothing : [ Just (2 ^ i) | i <- [0..8]]

Which again really isn't a list of powers of 2, and in Haskell you would
not use a list so you can later index into it to get powers of 2, which
is far more expensive then just computing them, and then you would still
have to process the Maybe. You might try an Array, but I wouldn't.

The proper function was probably (as Madhu said):

(defvar powers-of-2
(make-array 10

:initial-contents (loop for i below 10 collect (expt 2 i))))

which becomes just:

powersOf2 = [ 2^i | i <- (0..9) ]

In the lisp code I would probably do the (expt 2 x) where needed. Or
if optimization was really an issue, maybe something like:

(defmacro pow2 (x) (ash 1 x)

And use as a function.

Now:

> (defun state-index (X-locations O-locations)
> (+ (loop for l in X-locations sum (aref powers-of-2 l))
> (* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))

With the original powers-of-2 function the list '(0 0 0 8) would
fail with the error of trying to compute sum with a value nil.

In Haskell there are no loops, so it isn't directly translatable.
The closest you might get would be:

stateIndex xs os = sum (map (powersOf2 !!) xs)
+ 512 * sum (powersOf2 !!) os)

Which would be horribly inefficient. I would just:

stateIndex xs os = sum (map (2^) xs) + 512 * sum (map (2^) os)

or:

stateIndex xs os = sum2x xs + 512 * sum2x os
where sum2x = sum . map (2^)

Or the lisp:

(defun state-index (x-locations o-locations)
(labels ((sum-expt-2 (locs) (loop for x in locs sum (expt 2 x))))
(+ (sum-expt-2 x-locations) (* 512 (sum-expt-2 o-locations)))))

But as said before, if you are trying to understand Lisp, you need to
learn to think in Lisp, and Haskell is not very helpful since the
semantics of the languages are so different.

--
Barry Fishman

[tar...@google.com]

On Thursday, March 16, 2017 at 6:41:38 AM UTC-7, Barry Fishman wrote:
> On 2017-03-15 22:55:29 +07, radhakris...@gmail.com wrote:
>
> > Alternately a brief explanation of the numeric representation created
> > by this Lisp code will also do.
> >
> > Lisp :
> >
> > (defvar powers-of-2
> > (make-array 10
> > :initial-contents
> > (cons nil (loop for i below 9 collect (expt 2 i)))))
>
> This really isn't a powers of two function.

No, instead it seems to be an array for converting 1-based bit flags into
an integer, given the way state-index is defined below. The NIL in the 0-th
position is just a placeholder.
If one has to work within the constraints of an array that can't handle a
null value, then one could just as easily use 0 or -1 as the 0-th element.
I'm pretty sure that this value is not supposed to be used at all.

> Now:
> > (defun state-index (X-locations O-locations)
> > (+ (loop for l in X-locations sum (aref powers-of-2 l))
> > (* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))
>
> With the original powers-of-2 function the list '(0 0 0 8) would
> fail with the error of trying to compute sum with a value nil.

Which suggests that a zero value in X-locations or O-locations is not
allowed.

To the OP: Are you sure that this is a valid input value?

[Kaz Kylheku]

On 2017-03-16, radhakris...@gmail.com <radhakris...@gmail.com> wrote:
> Hi,
>
> I have converted the Lisp code to haskell. Trying to understand
> fully what Lisp does.

It's crystal obvious to me. It's converting a set of integer indices to a
bitmask, where each index value n becomes a 1 bit at bit position n.

There are two sets: X and O indices. The O indices are displaced by 512
positions not to interfere with the X indices (assuming the X indices
stay in the range 0 to 512).

Also, there seems to be the assumption that indices are unique, which
justifies the use of the + operation to join the bit masks.

Suppose we use an "O displacement" of 16 instead of 512 to keep things
small. Then we can have this example:

X values: '(1 5 9)
O values: '(1 3 7)

When we raise two to the power of each value, we are effectively
shifting 1 to the left that many places:

;; X values
(expt 2 1) <--> (ash 1 1) --> 2 ;; #b10
(expt 2 5) <--> (ash 1 5) --> 32 ;; #b100000
(expt 2 9) <--> (ash 1 9) --> 512 ;; #b1000000000

Add together:
--> 546 ;; #b1000100010


For the O values, we add 16 to each one:

(expt 1 (+ 16 1)) -> #b100000000000000000
(expt 1 (+ 16 3)) -> #b10000000000000000000
(expt 1 (+ 16 7)) -> #b100000000000000000000000

Sum: -> #b100010100000000000000000

> (defvar powers-of-2
> (make-array 10
> :initial-contents
> (cons nil (loop for i below 9 collect (expt 2 i)))))
>
> (defun state-index (X-locations O-locations)
> (+ (loop for l in X-locations sum (aref powers-of-2 l))
> (* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))
>
> Haskell :
>
> powersof2 :: [Int]
> powersof2 = [ 2 ^ i | i <- [0..9]]
>
> stateindex :: [Int] -> [Int] -> Int
> stateindex xloc oloc = let powers = powersof2 in
> ((foldl (+) 0 [ ( powers !!n) | n <- [0..(length xloc - 1)]]) +
> ( 512 * foldl (+) 0 [ ( powers !!n) | n <- [0..(length oloc - 1)]]))

TXR Lisp:

We can just use the built-in mask function, which takes its integer
arguments and constructs a bitmask with those bits set:

1> (mask 0 3)
9
2> (mask 0 1 2 3)
15
3> (logior (mask 1 5 3 6) [apply mask (mapcar (op + 512) '(1 5 7 0))])
21854726925806433272305660747075529187791366287565601205689405153266475369019
88157218705510601205258713475192884397226289161882898347290901268684787991707
754

Shitty implementation in C though. However, nice and clear:

val maskv(struct args *bits)
{
cnum index = 0;
val accum = zero;

while (args_more(bits, index)) {
val num = args_get(bits, &index);
val mask = ash(one, num);
accum = logior(accum, mask);
}

return accum;
}

The efficient thing to do is to find out the highest value in the set of
bits, and then either construct a bignum or fixnum of that size, and flip
the bits in place.

If I do that in the future, people calling mask won't have to rewrite their
code to take advantage of it.

I just haven't had a use case come up where performance of mask was identified
as an issue.

[Barry Fishman]

On 2017-03-16 17:03:40 +00, Kaz Kylheku wrote:
> On 2017-03-16, radhakris...@gmail.com
> <radhakris...@gmail.com> wrote:
>> Hi,
>>
>> I have converted the Lisp code to haskell. Trying to understand
>> fully what Lisp does.
>
> It's crystal obvious to me. It's converting a set of integer indices to a
> bitmask, where each index value n becomes a 1 bit at bit position n.
>
> There are two sets: X and O indices. The O indices are displaced by 512
> positions not to interfere with the X indices (assuming the X indices
> stay in the range 0 to 512).
>
> Also, there seems to be the assumption that indices are unique, which
> justifies the use of the + operation to join the bit masks.

Yes! With bits counted from 1, and only bit values of 1 through 9.
It would probably be clearer if it was done with bit operations:

(defun state-index (x-locations o-locations)
(labels ((mask (locs)
(reduce #'logior (mapcar (lambda (x) (ash 1 (1- x))) locs))))
(logior (mask x-locations) (ash (mask o-locations) 9))))

--
Barry Fishman

[Madhu]

* Barry Fishman <m34lysu...@ecube.ecubist.org> :
Wrote on Thu, 16 Mar 2017 19:41:56 -0400:

| On 2017-03-16 17:03:40 +00, Kaz Kylheku wrote:
|
|> There are two sets: X and O indices. The O indices are displaced by
|> 512 positions not to interfere with the X indices (assuming the X
|> indices stay in the range 0 to 512).

[ To Kaz: The *mask* of the O-indices would seem to be displaced by 512
bits. (The *mask* of the X-indices would be the first 512 bits)
This is not what you were doing in the examples in your post where you
used an offset of 16 bits: you were applying the displacement the
X and O indices themselves! it does not distribute.) ]

|> Also, there seems to be the assumption that indices are unique, which
|> justifies the use of the + operation to join the bit masks.
|
| Yes! With bits counted from 1,

I assume you mean: with X and O indices counted from 1, but this has to
be an stated external requirement on the indices.

| and only bit values of 1 through 9.

I really don't understand this. I'd think the computed index would fit
within 16 bits, the first 8 bits being the mask of the X-indices and
bits 9-16 being the mask of the O-indices...

[the following is in response kaz's message which was snipped in your
article]

|> 1> (mask 0 3)
|> 9
|> 2> (mask 0 1 2 3)
|> 15
|> 3> (logior (mask 1 5 3 6) [apply mask (mapcar (op + 512) '(1 5 7 0))])
|> 21854726925806433272305660747075529187791366287565601205689405153266475369019
|> 88157218705510601205258713475192884397226289161882898347290901268684787991707
|> 754

Aren't the last 3 digits of the result of this computation `818' instead
of `754' ?

But length of the total bitmask is 9+9 and the computed index

In any case I think the computation should actually be:
;(log 512 2) ; 9
(logior (mask '(1 5 3 6)) (ash (mask '(1 5 7 0)) 9))

[Madhu]

* I Wrote on "Fri, 17 Mar 2017 09:48:09 +0530"

| [the following is in response kaz's message which was snipped in your
| article]

| |> 3> (logior (mask 1 5 3 6) [apply mask (mapcar (op + 512) '(1 5 7 0))])
| |> 21854726925806433272305660747075529187791366287565601205689405153266475369019
| |> 88157218705510601205258713475192884397226289161882898347290901268684787991707
| |> 754
|
| Aren't the last 3 digits of the result of this computation `818' instead
| of `754' ?

Sorry 754 is correct. I mistyped the X-indices as (1 5 3 7), instead of
(1 3 5 6) when playing at the repl

| But length of the total bitmask is 9+9 and the computed index

This sentence should have been deleted before sending if I'd proofread
it

[radhakris...@gmail.com]

Clarification. I am working on a Reinforcement Learning problem to learn the subject. It is a branch of Machine Learning. Some people refer to these things as AI.

The Lisp is from the book on the subject by Sutton. I haven't learnt Lisp thoroughly before embarking on this project. Because other languages have bindings for ML frameworks. I use Haskell.

This is the comment from that example. Let me read some of your explanations before asking further.

; The value function will be implemented as a big, mostly empty array. Remember
; that a state is of the form (X-locations O-locations index), where the index
; is an index into the value array. The index is computed from the locations.
; Basically, each side gets a bit for each position. The bit is 1 is that side
; has played there. The index is the integer with those bits on. X gets the
; first (low-order) nine bits, O the second nine. Here is the function that
; computes the indices:


Thanks,
Mohan

[Robert L.]

On 3/16/2017, Madhu wrote:

> | (defvar powers-of-2
> | (make-array 10
> | :initial-contents
> | (cons nil (loop for i below 9 collect (expt 2 i)))))
>
> This looks wrong. The array indices are 0 based and 2^0 = 1. However
> this array shows 2^0 = NIL.
>
> * powers-of-2
> #(NIL 1 2 4 8 16 32 64 128 256)
>
> Instead you should define this as
>
> (defparameter powers-of-2
> (make-array 10 :initial-contents (loop for i below 10 collect (expt 2 i))))
>
>
> | (defun state-index (X-locations O-locations)
> | (+ (loop for l in X-locations sum (aref powers-of-2 l))
> | (* 512 (loop for l in O-locations sum (aref powers-of-2 l)))))
>
> obviously this computes \sum_i 2^{x_i} + 512 * \sum_i 2^{o_i}
>
> | What output does the Lisp code produce for an input of [0,0,0,8] for
> | both lists ?
>
> I assume this curious sentence actually means: what does the call to
>
> (state-index '(0 0 0 8) '(0 0 0 8))
>
> After my correction to powers-of-2, if you run the code in a lisp
> compiler, it produces 132867.

(use (only traversal sum map-n-vector))

(define powers-of-2 (map-n-vector (cut expt 2 <>) 10))

(define (loc->power n) (vector-ref powers-of-2 n))

(define (power-sum locations)
(sum (map loc->power locations)))

(define (state-index X-locations O-locations)
(+ (power-sum X-locations)
(* 512 (power-sum O-locations))))

(state-index '(0 0 0 8) '(0 0 0 8))

===>
132867

>
> | Haskell
> [snip]
>
> I suggest forget about haskell, learn common lisp

No.


Here's what the experts say about CL (COBOL-Like):

"an unwieldy, overweight beast"
"intellectual overload"
"did kill Lisp"
"A monstrosity"
"ignores the basics of language design"
"killed Lisp"
"sucks"
"an aberration"
"the WORST thing that could possibly happen to LISP"
"incomprehensible"
"a nightmare"
"not commercially viable"
"no future"
"a significantly ugly language"
"hacks"
"unfortunate"
"a disaster"
"bad"

In context:


Guy L. Steele, Jr., July 1989:

I think we may usefully compare the approximate number of pages
in the defining standard or draft standard for several
programming languages:

Common Lisp 1000 or more
COBOL 810
ATLAS 790
Fortran 77 430
PL/I 420
BASIC 360
ADA 340
Fortran 8x 300
C 220
Pascal 120
DIBOL 90
Scheme 50


-----


Brooks and Gabriel 1984, "A Critique of Common Lisp":

Every decision of the committee can be locally rationalized
as the right thing. We believe that the sum of these
decisions, however, has produced something greater than its
parts; an unwieldy, overweight beast, with significant costs
(especially on other than micro-codable personal Lisp
engines) in compiler size and speed, in runtime performance,
in programmer overhead needed to produce efficient programs,
and in intellectual overload for a programmer wishing to be
a proficient COMMON LISP programmer.


-----


Bernard Lang:

Common Lisp did kill Lisp. Period. (just languages take a
long time dying ...) It is to Lisp what C++ is to C. A
monstrosity that totally ignores the basics of language
design, simplicity and orthogonality to begin with.


-----

Gilles Kahn:

To this day I have not forgotten that Common Lisp killed
Lisp, and forced us to abandon a perfectly good system,
LeLisp.

-----


Paul Graham, May 2001:

A hacker's language is terse and hackable. Common Lisp is not.

The good news is, it's not Lisp that sucks, but Common Lisp.

Historically, Lisp has been good at letting hackers have their
way. The political correctness of Common Lisp is an aberration.
Early Lisps let you get your hands on everything.

A really good language should be both clean and dirty:
cleanly designed, with a small core of well understood and
highly orthogonal operators, but dirty in the sense that it
lets hackers have their way with it. C is like this. So were
the early Lisps. A real hacker's language will always have a
slightly raffish character.

Organic growth seems to yield better technology and richer
founders than the big bang method. If you look at the
dominant technologies today, you'll find that most of them
grew organically. This pattern doesn't only apply to
companies. You see it in sponsored research too. Multics and
Common Lisp were big-bang projects, and Unix and MacLisp
were organic growth projects.


-----


Dick Gabriel:

Common LISP just was never designed to be a commercially
viable LISP. It was intended to serve as a compromise between
the manufacturers of LISP machines and other vendors of LISP
products. Never did we think of it as an industrial strength
system... So, to the extent that ANSI's ongoing efforts to
standardize on Common LISP exercise some influence over how LISP
is accepted in the world at large, I anticipate a disaster.


-----

Jeffrey M. Jacobs:


I think CL is the WORST thing that could possibly happen to LISP.
In fact, I consider it a language different from "true" LISP.

*****

Common LISP is the PL/I of Lisps. Too big and too
incomprehensible, with no examination of the real world of
software engineering.

... The CL effort resembles a bunch of spoiled children,
each insisting "include my feature or I'll pull out, and
then we'll all go down the tubes". Everybody had vested
interests, both financial and emotional.

CL is a nightmare; it has effectively killed LISP
development in this country. It is not commercially viable
and has virtually no future outside of the traditional
academic/defense/research arena.



-----


Dick Gabriel:

Common Lisp is a significantly ugly language. If Guy and I
had been locked in a room, you can bet it wouldn't have
turned out like that.


-----

Paul Graham:

Do you really think people in 1000 years want to be
constrained by hacks that got put into the foundations of
Common Lisp because a lot of code at Symbolics depended on
it in 1988?


-----

Daniel Weinreb, 24 Feb 2003:

Having separate "value cells" and "function cells" (to use
the "street language" way of saying it) was one of the most
unfortunate issues. We did not want to break pre-existing
programs that had a global variable named "foo" and a global
function named "foo" that were distinct. We at Symbolics
were forced to insist on this, in the face of everyone's
knowing that it was not what we would have done absent
compatibility constraints. It's hard for me to remember all
the specific things like this, but if we had had fewer
compatibility issues, I think it would have come out looking
more like Scheme in general.


-----


Daniel Weinreb, 28 Feb 2003:

Lisp2 means that all kinds of language primitives have to
exist in two versions, or be parameterizable as to whether
they are talking about the value cell or function cell. It
makes the language bigger, and that's bad in and of itself.


-----


Paul Graham:

I consider Loop one of the worst flaws in CL, and an example
to be borne in mind by both macro writers and language designers.


--
I wrote until my fingers were blue, over and over: "Political
Correctness is a religion." I proved it and showed you why it is so
important that Political Correctness is a religion.
--- Bob Whitaker