[racket] Rosetta Sokoban Solution

From: Sean Kanaley (skanaley at gmail.com)
Date: Mon Jun 10 13:49:33 EDT 2013

Firstly, do you suggest I remove the comments, in which case use more 
blank lines or not?  I don't mind, and only added them mainly in the 
hopes it would be helpful to readers as the purpose of Rosetta is to 
educate.  But I agree that it also kind of thickens the code.

As for Pico being less thick, this is entirely true.  Off the top of my 
head, I suspect it has largely to do with PicoLisp's single data 
structure and use of properly lists.  I had originally directly 
translated the PicoLisp code and came up with a comparable solution.  
Then I replaced (cdars) and such with proper struct references, 
requiring the corresponding lines of define-match or match-let.  Because 
these are found in lists, it requires additional cons of the car of the 
cdr of the struct-x of the car type statements where Pico just uses 
cdadadr.  Which one is better is an open question to me.  What you lose 
in abstraction you gain in concision.  After all, we use car instead of 
first, and why?  car is shorter.  It may happen to mean the first 
element, but it actually means the car of a pair, and it fortunately 
happens that lists are made of these pairs, so luckily the car for lists 
/happens/ to be the same as the car for pairs, which is an 
implementation detail that every Scheme luckily shares (maybe it's 
explicitly in the standard, but it's still in some sense a mistake of 
relying on an implementation in the purest sense, at least within the 
scheme itself).

Also, for some reason Racket doesn't return values from mutations. Why 
on earth (set! x 3) is void instead of 3 is a mystery, but it leads to 
things like:

(define-match (x ...) (heap-min heap))

and, in addition to verbose naming:

(vector-set! v i 4)

which should ideally be:

(vec! v i 3)

Things that take 1 line tend to take 2-3 lines.  The best example is:

(unless (idx '*Hist (sort (copy *Boxes)) T)

where idx goes through *Hist (a list) and, due to the #t flag at the 
end, adds the sorted list of boxes if it's not found.  The overall 
purpose is it saves the current state to avoid duplicate searches. The 
key is that, in addition to mutating history, it also /returns/ 
something.  If the element was added, it returns either the element or 
the list (I forget, but it's non-#f is the point).  So this one line 
continues the search by determining if the new state was added to the 
history or not, based on whether it was already in the history.  Since I 
have to extract the minimum of a heap and then mutate the heap, not only 
do I need at least 2 expressions to accomplish that, but in general, 
this kind of pattern can take /three/ expressions.  One to bind the 
result before it's deleted forever, one to delete it, then the 
expression that uses it!  It might not be usable directly in the first 
line since it might recurse with what should have been the deleted 
version of the structure.  So one might have to save the result, mutate, 
and /then/ recurse!

Pico also has property lists, so instead of vector-ref'ing everything, 
the 'val of a symbol is obtained (e.g. a box on a goal is the box with a 
goalified 'val property).  Property access function is a single 
character ":" when referencing the anaphoric This.  Pico has constructs 
like "make" which sets up a list building environment where things can 
be added on the left and right sides of a list, and then automatically 
returns the list.  And since all list functions can be run within make, 
it is immensely powerful, essentially allowing arbitrary construction of 
the primary data structure of the language, which, unlike most "real" 
schemes, actually uses them directly for interpretation.  One can thus 
build "macros" out of expressions using the normal library functions, 
instead of require-for-syntax functions that require fancy 300 
character-length macro machinery like 
define-syntax-transformer-for-syntax-parameterization to produce (I do 
apologize for being harsh, but I like Racket and these things sadden me).

Finally, and this is more of a useless criticism since the language is 
so far developed in this direction, so I apologize, but while it's nice 
to have for, for/list, for*/list, for*/fold, match, define-match, 
match-let, let-values-define-match*, match-let-define-values*/fold/for 
(exaggerating), what tends to happen is there's a huge mess of 
overlapping constructs, and a large amount of (at least for me) 
programmer time wasted in deciding and refactoring between nestings of 
let -> define -> cond -> or -> if vs. match-let -> if -> match -> cond 
-> for/fold -> not -> and -> named let (or whatever).  In PicoLisp, one 
simply calls a function on what must be a list, the function names are 
short, and there are a huge number of library functions.  There is 
almost no decision to be made!  You are processing a list, and you need 
to do something, so you use the corresponding library function.  
PicoLisp comes built in with anaphoric stuff as well.  I had to use my 
custom awhen to bind @ where that is often bound for free in Pico, not 
requiring a special conditional with binding (and not requiring 
define-syntax-parameter and syntax-parameterize and 
make-transformer-syntax-binding-case-rules to implement it...). Pico 
consistently has the shorter/shortest solutions and in all my tests, has 
excellent run time performance.  I dare say it's a "better" language and 
it would be, in my opinion, for the reasons I just gave.

My intent wasn't to start some kind of flame war here.  I do like 
Racket, it's teaching languages, the assocated HTDP1&2, the associated 
universe/image library (I used that to do Galton Box on Rosetta), and 
the fact that it's very standardized and comes with decent OpenGL 
bindings that I'm using to make a 3d game that I shall one day post.  
But if I had to choose which language seems to actually produce better 
code, I would have to side with PicoLisp. Just beware dynamic scope.

On 06/10/2013 12:42 PM, Matthias Felleisen wrote:
> Thank you for this effort.
> This is not a criticism of your code but I will say that Racket code looks dense and overbearing compared to PicoLisp, Python, and Tcl. Hmph.
> On Jun 10, 2013, at 12:34 PM, Sean Kanaley wrote:
>> The rather empty page on Sokoban now has a Racket solution.  The creator is proud to announce it's the fastest solution (though a couple didn't give run times) at ~0.1 seconds.  My thanks to Ryan Culpepper for making the binary heap that made this possible.
>> http://rosettacode.org/wiki/Sokoban#Racket
>> Also, Racket is one short of Python in popularity.  If someone could do two more we'll defeat those lazy Python programmers, probably with less work!
>> ____________________
>> Racket Users list:
>> http://lists.racket-lang.org/users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130610/9b5df27d/attachment-0001.html>

Posted on the users mailing list.