(hello

‘world)

A goban with some tsumego.

Been playing Go. Because like the Lisps, it’s a whole lot of neat shit that stems from a simple base. Enough neat shit that, unlike Chess, humans still dominate vs computers by quite a margin. Playing a computer on anything larger than a 9×9 beginner’s board is pretty much universally considered as conductive only to hurting your playing style. With enough horsepower a top professional can be matched on a 9×9. http://senseis.xmp.net/?Fuego :

Fuego was the first computer program that won an official game of 9×9 Go against a 9-Dan professional player. The game against Zhou Junxun took place at theĀ  Human vs. Computer Go Competition at the Fuzz IEEE 2009 conference. The second game was won by Mr. Zhou.

The usual game is played on a 19×19 board. It holds dan ranks on OGS, and there’s some bots running on clusters holding dan ranks on KGS, but they’re never the highest, and ranks on amateur servers mean a great deal less. They’re only relative to the other players on the given server.

And there’s a somewhat slow but alive Go club in Second Life (http://www.notabene-sl.com/slgc/) which seemed a suitable excuse to check out SL, although for general play I prefer KGS (http://www.gokgs.com/).

There’s sometimes classes in the SL club on sundays. The usual teach had other shit to deal with so I volunteered to try to cover it though I’m usually laggy as hell. KGS works fine, including voice, on a dialup connection that hits 3k/s on a good day. But efficiency is an important concept in Go ;).

Since all I can really do teaching wise at my level is run newer folk through Go problems and I’m too laggy to keep setting up the board each time for a new one, I made one up with a few possibilities that I could just throw down and work with in case anyone showed. No one did, Chess is far more popular in SL… as it is in most of the west. But then there’s that saying about cockroaches and humans…

Here’s a shot of it in SL. Note that I’m on a netbook, on a slow connection. SL is probably prettier for most folk. And lest there be any confusion, it’s only the pattern of the stones. The virtual board and stones and such you see are SLGC‘s.

Prael's tutor board

Prael's tutoring goban, v1. Click for full size.

And here it is, in SGF format (which suitably starts with the paren):
(
;
FF[1]
GM[1]
SZ[9]
AP[Jago:Version 5.0]
AB[ga][ib][hc][gc][fc][fb][hd][dg][dh][di][cg][bg][ag][ba][bb][bc][bd][ad][gi][fh][gg][hg][hh][ih][ii][db][dc][dd][de][ee]
AW[he][gd][fd][ec][eb][ed][ge][ha][cf][df][eg][eh][ei][bf][af][ef][cb][cc][cd][be][ae][gf][hf][ig][ff][if][id][ea][ce][ca]
C[Prael's tutor board for SLGC, v1.

Besides 4 or 5 30k-20k problems there's a miai, a couple potential ko's, a potential seki, and an underlying lesson: Both players have 30 moves down, but there's no way for black to win with all of these unsettled groups. With GNU Go 3.8:

$gnugo --score aftermath -l tutor.sgf
0 black (X) move B1
1 white (O) move H8
2 black (X) move A8
3 white (O) move F1
4 black (X) move F3
5 white (O) move PASS
6 black (X) move PASS
White wins by 27.5 points

That is: Black saves lower left, White kills upper right, Black saves upper left, the lower right miai is played out, and the middle black chain is already toast.

Resolve the right 2 groups and play F9 for seki.
Move H5 to J7 for a throw-in to a false eye.
Show what happens if black gets J6 first, "There is death in the hane".
Six in the corner can be quickly tweaked to bulky 5, pyramid 4, bent 3, L shapes...
If the upper right is too hairy it can similarly be simplified with black F9.
There's a few common shapes in here. B1 is sufficient for LL group, but LR needs that H2.
There's also a "dog's head" in the UR group, G9,H7,J8. Note the vital point.
Counting problems may be posed: GnuGo gets the order correct. ]
)

October 30, 2011 Posted by | Life | Leave a comment

Something almost Schemeish in something CLish.

I just wanted to see how much I could bang out in a single night without without referring to any documentation or previous code, and after having not even written anything in Common Lisp in 1.5 or 2 years. If I could have rememberd or bothered to look up more of CL’s standard lib and macros (like… iteration) this probably could have been done in a quarter of the time and space, but that wasn’t the point. Next up would be to implement define and revoke set!’s ability to create vars, making sure they scope correctly, and to add a list of primitives. But it’s time to go home. Maybe I’ll pick it up again tomorrow, maybe I won’t.

;Copyright (c) 2011 Matthew A. Martin (matt.a.martin@gmail.com)
;
;Permission is hereby granted, free of charge, to any person
;obtaining a copy of this software and associated documentation
;files (the "Software"), to deal in the Software without
;restriction, including without limitation the rights to use,
;copy, modify, merge, publish, distribute, sublicense, and/or sell
;copies of the Software, and to permit persons to whom the
;Software is furnished to do so, subject to the following
;conditions:
;
;The above copyright notice and this permission notice shall be
;included in all copies or substantial portions of the Software.
;
;THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
;EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
;OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
;NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
;HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
;WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
;FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
;OTHER DEALINGS IN THE SOFTWARE.
;;;;
; A scheme-flavored interpreter in a subset of Common Lisp.

(defconstant empty-stack nil)
(defconstant empty-frame nil)

;CL-USER> (frame (list 'a 'b 'c) (list 1 2 3) (frame (list 'd 'e 'f) (list 4 5 6) empty-frame))
;((A . 1) (B . 2) (C . 3) (D . 4) (E . 5) (F . 6))
(defun frame (vars vals frame)
  (if (null vars) frame
      (cons (cons (first vars) (first vals))
	    (frame (rest vars) (rest vals) frame))))

;CL-USER> (stack (frame (list 'a 'b 'c) (list 1 2 3) (frame (list 'd 'e 'f) (list 4 5 6) empty-frame)) empty-stack)
;(((A . 1) (B . 2) (C . 3) (D . 4) (E . 5) (F . 6)))
;CL-USER> (stack (frame (list 'a 'b 'c) (list 1 2 3) empty-frame) (stack (frame (list 'd 'e 'f) (list 4 5 6) empty-frame) empty-stack))
;(((A . 1) (B . 2) (C . 3)) ((D . 4) (E . 5) (F . 6)))
(defun stack (frame stack)
  (cons frame stack))

;CL-USER> (lookup-frame 'b (frame (list 'a 'b 'c) (list 1 2 3) empty-frame))
;(B . 2)
;CL-USER> (lookup-frame 'd (frame (list 'a 'b 'c) (list 1 2 3) empty-frame))
;NIL
(defun lookup-frame (var frame)
  (if (null frame) nil
      (if (eq var (first (first frame)))
          (first frame)
          (lookup-frame var (rest frame)))))

;CL-USER> (lookup 'a (stack (frame (list 'a 'b) (list 1 2) empty-frame) (stack (frame (list 'c) (list 3) empty-frame) empty-stack)))
;(A . 1)
;CL-USER> (lookup 'b (stack (frame (list 'a 'b) (list 1 2) empty-frame) (stack (frame (list 'c) (list 3) empty-frame) empty-stack)))
;(B . 2)
;CL-USER> (lookup 'c (stack (frame (list 'a 'b) (list 1 2) empty-frame) (stack (frame (list 'c) (list 3) empty-frame) empty-stack)))
;(C . 3)
;CL-USER> (lookup 'd (stack (frame (list 'a 'b) (list 1 2) empty-frame) (stack (frame (list 'c) (list 3) empty-frame) empty-stack)))
;NIL
(defun lookup (var stack)
  (if (null stack) nil
      (let ((varp (lookup-frame var (first stack))))
        (if varp varp
            (lookup var (rest stack))))))

(defun value (x)
  (rest x))

(defun update (var val stack)
  (let ((varp (lookup var stack)))
    (if varp 
	(rplacd varp val)
	(rplaca stack (frame (list var)
			     (list val)
			     (first stack)))))) ; Exploiting (first nil) => nil here

;;; From here on, nothing should care that envs/stacks and frames are lists.

;; Helper for evaluate.
;CL-USER> (defvar tststk (stack (frame (list 'a 'b) (list 1 2) empty-frame) (stack (frame (list 'c) (list 3) empty-frame) empty-stack)))
;TSTSTK
;CL-USER> (lookup-list (list 'a 'b 'c) tststk)
;(1 2 3)
;CL-USER> (lookup-list (list 'a 'b 'd 'c) tststk)
;(1 2 NIL 3)
(defun lookup-list (varlst stack)
  (if (null varlst) nil
      (cons (let ((varp (lookup (first varlst) stack)))
	      (if varp (value varp) varp))
	    (lookup-list (rest varlst) stack))))

;; Helper for evaluate.
(defun constant (x)
  (if (or (eq x t) (eq x nil) (numberp x))
      t
      nil))

;; Helper for evaluate.
;CL-USER> (func '((a b c) foo))
;(FN (A B C) (BEGIN FOO))
(defun func (args)
  (list 'fn ; tag 
	(first args) ; arg names 
	(cons 'begin ; implicit begin/progn
	      (rest args)))) ; fn body

;CL-USER> (fn-args (func '((a b c) foo)))
;(A B C)
(defun fn-args (x) (second x))

;CL-USER> (fn-body (func '((a b c) foo)))
;(BEGIN FOO)
(defun fn-body (x) (third x))

;; Helper for evaluate.
(defun eval-list (exps env)
  (if (null exps) nil
      (cons (evaluate (first exps) env)
	    (eval-list (rest exps) env))))

;; Helper for applier
(defun primitive? (x)
  (eq (first x) 'prim))
;; Helper for applier
(defun func? (x)
  (eq (first x) 'fn))

;CL-USER> (evaluate t tststk)
;T
;CL-USER> (evaluate '(if t b (quote bar)) tststk)
;2
;CL-USER> (evaluate '(if nil b (quote foo)) tststk)
;FOO
;CL-USER>  (evaluate '(begin 1 2 3 (eq? 2 2)) tststk)
;T
;CL-USER>  (evaluate '(set! a 4) tststk)
;(A . 4)
;CL-USER> tststk
;(((A . 4) (B . 2)) ((C . 3)))
;CL-USER>  (evaluate '(set! d 4) tststk)
;(((D . 4) (A . 4) (B . 2)) ((C . 3)))
;CL-USER> tststk
;(((D . 4) (A . 4) (B . 2)) ((C . 3)))
;CL-USER>  (evaluate '(set! a 5) tststk)
;(A . 5)
;CL-USER> tststk
;(((D . 4) (A . 5) (B . 2)) ((C . 3)))
;CL-USER>  (evaluate '(set! a b) tststk)
;(A . 2)
;CL-USER> tststk
;(((D . 4) (A . 2) (B . 2)) ((C . 3)))
;CL-USER>  (evaluate '(set! b 5) tststk)
;(B . 5)
;CL-USER> tststk
;(((D . 4) (A . 2) (B . 5)) ((C . 3)))
;CL-USER> (evaluate '(begin (set! foo (lambda (x) x)) (foo 1)) tststk)
;1
;CL-USER> (evaluate '(begin (set! bar (lambda (x) x)) (bar d)) tststk)
;4
;CL-USER> tststk
;(((BAR FN (X) (BEGIN X)) (FOO FN (X) (BEGIN X)) (D . 4) (A . 2) (B . 5)) ((C . 3)))
(defun evaluate (exp env)
  (cond
    ((constant exp) exp)
    ((symbolp exp) (rest (lookup exp env)))
    (t
     (let ((fn (first exp))
	   (args (rest exp)))
       (cond
	 ;; Special forms.
	 ((eq fn 'quote) (first args))
	 ((eq fn 'eq?) (eq (evaluate (first args) env) (evaluate (second args) env)))
	 ((eq fn 'if)
	  (let ((result (evaluate (first args) env)))
	    (if result
		(evaluate (second args) env)
		(evaluate (third args) env))))
	 ((eq fn 'lambda) (func args))
	 ((eq fn 'set!) ; or define
	  (update (first args) (evaluate (second args) env) env))
	 ((eq fn 'begin)
	  (if (eq 1 (length args))
	      (evaluate (first args) env)
	      ;; Borrow CL's progn here assuming it's iterative.
	      (progn (evaluate (first args) env)
		     (evaluate (cons 'begin (rest args)) env))))
	 (t (applier (evaluate fn env) (eval-list args env) env))))))) ; strict
	  
(defun applier (fn args env)
  (cond
    ((primitive? fn) (apply (second fn) args))
    ((func? fn) 
     (evaluate (fn-body fn)
	       (stack (frame (fn-args fn) args empty-frame)
		      env)))
    (t barf))) ; Shouldn't get here.

January 16, 2011 Posted by | Common Lisp, Programming, Scheme | Leave a comment

Happy new year!

Yeah, it’s a few days late. Oh well.

Havn’t really done shit as far as code lately other than work on reinventing yet another lists library for C to better grok the relation of lisp and implementation, and some playing around with hash tables.

In other news, I’ve got a temp blog running here.

Dude makes vids on Baguazhang, folks write about working with ‘em. I’ve already got gigs of vids and an entire shelf of books on such matter, but what the hell, I won’t turn down basically free shit.

Other than that, life’s a haze of eggnog between shifts at work.

January 4, 2011 Posted by | Life, Meta | Leave a comment

One more time!

Now we’re getting ugly. Hmmmmmm.

(define (onemoretime fails? lst func)
  
  ;; acc is usually the result of the
  ;; "reduce so far", here it is the
  ;; last pair in newlst. cur is
  ;; current item of consideration
  ;; in the original list. 
  (define (foo acc cur)
    ;; func should return a new
    ;; pair, which gets tacked
    ;; onto the end of newlst.
    (set-cdr! acc (func cur))
    ;; Have lfold push the new
    ;; pair into acc next
    ;; time it loops.
    (rest acc))

  (define (bar acc cur)
    ;; Here, func is allowed to 
    ;; return #f signalling to 
    ;; leave acc alone.
    (let ((tst (func cur)))
      (if tst
	  (begin (set-cdr! acc tst)
		 (rest acc))
	  acc)))

  ;; Grab pointer to first cons.
  ;; Contents of car will be dropped.
  ;; Contents of cdr will be clobbered. 
  (let ((newlst (list #f))) 
    (lfold (if fails? bar foo)
	   newlst ; Accumulator
	   lst) ; list we're deriving from
    (rest newlst))) ; car is trash, see above.

Examples so far:

(define (append hd tl)
  (onemoretime #f hd (lambda (nxt) 
                                   (cons nxt tl))))

(define (map func lst)
  (onemoretime #f lst (lambda (nxt) 
                                   (list (func nxt)))))

(define (filter pred? lst)
  (onemoretime #t lst (lambda (nxt)
			           (if (pred? nxt)
			               (list nxt)
			               #f))))

August 5, 2010 Posted by | Programming, Scheme | Leave a comment

Update to my toy.

Function may return #f rather than cons, which will leave the list it’s building as is. Was needed for filter. Also slows it down a great deal. :[

(define (stillhasnoname lst func)
  ;; Grab pointer to first cons.
  ;; Contents of car will be dropped.
  ;; Contents of cdr will be clobbered. 
  (let ((newlst (list #f))) 
    ;; acc is usually the result of the
    ;; "reduce so far", here it is the
    ;; last pair in newlst. cur is
    ;; current item of consideration
    ;; in the original list. 
    (lfold (lambda (acc cur)
	     ;; func should return either 
	     ;; a new pair to be tacked 
	     ;; onto the end of newlst,
	     ;; or #f which will leave
	     ;; acc as-is. 
	     (let ((tst (func cur)))
	       (if tst
		   (begin (set-cdr! acc tst)
			  (rest acc))
		   acc)))
           newlst ; Accumulator
           lst) ; list we're deriving from
    (rest newlst))) ; car is trash, see above.

August 5, 2010 Posted by | Programming, Scheme | Leave a comment

In case I want to grok this in 6 months.

(define (whatdoicallthis lst func)
  ;; Grab pointer to first cons.
  ;; Contents of car will be dropped.
  ;; Contents of cdr will be clobbered. 
  (let ((newlst (list #t))) 
    ;; acc is usually the result of the
    ;; "reduce so far", here it is the
    ;; last pair in newlis. cur is
    ;; current item of consideration
    ;; in the original list. 
    (lfold (lambda (acc cur)
	     ;; func should return a new
	     ;; pair, which gets tacked 
	     ;; onto the end of newlst.
	     (set-cdr! acc (func cur))
	     ;; Have lfold push the new
	     ;; pair into acc next
	     ;; time it loops.
	     (rest acc))
	   newlst ; Accumulator
	   lst) ; list we're deriving from
    (rest newlst))) ; car is trash, see above.

(define (append hd tl)
  (whatdoicallthis hd (lambda (nxt) 
			(cons nxt tl))))

(define (map func lst)
  (whatdoicallthis lst (lambda (nxt) 
			 (list (func nxt)))))

August 1, 2010 Posted by | Programming, Scheme | Leave a comment

Woo!

Got it.

(define (whatdoicallthis lst func)
(let ((newlst (list list)))
(lfold (lambda (hd tl)
(set-cdr! hd (func tl))
(rest hd))
newlst
lst)
(rest newlst)))

(define (append hd tl)
(whatdoicallthis hd (lambda (nxt) (cons nxt tl))))

(define (map func lst)
(whatdoicallthis lst (lambda (nxt) (list (func nxt)))))

August 1, 2010 Posted by | Programming, Scheme, Uncategorized | Leave a comment

A step closer…

(define (append hd tl)
(let ((newlst (list list)))
(lfold (lambda (hd nxt)
(set-cdr! hd (cons nxt tl))
(rest hd))
newlst
hd)
(rest newlst)))

August 1, 2010 Posted by | Programming, Scheme | Leave a comment

No dice.

It seems like there ought to be a simple way to generalize something here, but I’ve been awake for over 24 hours and if I drink more coffee I’ll never get to sleep before tomorrow’s shift. Shit.

Least I have something to look forward to tomorr… tonight.

July 31, 2010 Posted by | Uncategorized | Leave a comment

More dicking around. Stack friendly map.


(define (map func lst)
(if (null? lst) lst
(let ((newlis (list (func (first lst)))))
(let loop ((cur newlis) (lst (rest lst)))
(if (null? lst) newlis
(begin (set-cdr! cur (list (func (first lst))))
(loop (rest cur) (rest lst))))))))

Was trying to implement map with left fold. Wound up with this. The right fold implemention easily blows the stack in guile 1.8. Scheme48 copes perfectly well… with no perceptible difference in speed (which was basically instant) even with a 20k element list. Nice.

This works in both, though. I still have an hour to kill… hmm.

July 31, 2010 Posted by | Programming, Scheme | Leave a comment

Follow

Get every new post delivered to your Inbox.