I've written a new topic index page for my site: Games, simulations, and animations. Except for the note about Tile Game, everything on it is something I've already published.

Condensed list of the contents: Tile Game, Fire Worms, Mouse-maze, 15-puzzle, screen savers, Varychase, Linkage, Bouncyworm, Brownian Tree, pendulum animation.

Has anything been done in logic programming (especially in languages not too far from the classic Prolog) which is analogous to monads and the IO monad in Haskell; that is, providing a means of performing IO or other side-effects which does not have the programmer depend on the evaluation/search order of the language?

In other words, what is to Prolog as Haskell is to ML?

James@Waterpoint (Xplat on Freenode) mentioned an interesting problem: write an elegant point-free expression to compute the diagonal of a list of lists (that is, from [[00, 01, 02, ...], [10, 11, 12, ...], ...] obtain [00, 11, ...]).

His version:

diag = (map head) . (foldr (flip ((flip (:)) . (map tail))) [])

My version, which needs a non-pointfree helper function (but one which others have invented before, and perhaps ought to be in the standard libraries), but has fewer flips:

import Control.Arrow ((***))
import Data.List (unfoldr)

uncons xs = case xs of (x:xs') -> Just (x,xs'); [] -> Nothing
diag = unfoldr (fmap (head *** (map tail)) . uncons)

uncons is sort of the opposite of unfoldr, in that unfoldr uncons = id.

Update: [livejournal.com profile] darius's version, from the comments:

diag = flip (zipWith (!!)) [0..]

I forget why I wrote this Haskell program, but it's cluttering up my do-something-with-this folder, so I’ll just publish it.

-- This program calculates all the ways to combine [1,2,3,4] using + - * / and ^
-- to produce *rational* numbers (i.e. no fractional exponents). (It could be so
-- extended given a data type for algebraic numbers (or by using floats instead
-- of exact rationals, but that would be boring).)
-- Written September 7, 2009.
-- Revised August 25, 2010 to show the expressions which produce the numbers.
-- Revised August 26, 2010 to use Data.List.permutations and a fold in combine.
-- In the unlikely event you actually wants to reuse this code, here's a license
-- statement:
-- Copyright 2009-2010 Kevin Reid, under the terms of the MIT X license
-- found at http://www.opensource.org/licenses/mit-license.html

Code )

I'd include the output here, but that would spam several aggregators, so I'll just show some highlights. The results are listed in increasing numerical order, and only one of the expressions giving each distinct result is shown.

(1 - (2 ^ (3 ^ 4))) = -2417851639229258349412351
(1 - (2 ^ (4 ^ 3))) = -18446744073709551615
(1 - (3 ^ (2 ^ 4))) = -43046720
(1 - (4 ^ (3 ^ 2))) = -262143
(1 - (4 ^ (2 ^ 3))) = -65535
...all integers...
((1 - (2 ^ 4)) * 3) = -45
(((1 / 2) - 4) ^ 3) = -343/8
((1 - (3 ^ 4)) / 2) = -40
(1 - ((3 ^ 4) / 2)) = -79/2
(1 - ((3 ^ 2) * 4)) = -35
...various short fractions...
(1 / (2 - (3 ^ 4))) = -1/79
(((1 + 2) - 3) * 4) = 0
(1 / (2 ^ (3 ^ 4))) = 1/2417851639229258349412352
(2 ^ (1 - (3 ^ 4))) = 1/1208925819614629174706176
(1 / (2 ^ (4 ^ 3))) = 1/18446744073709551616
(2 ^ (1 - (4 ^ 3))) = 1/9223372036854775808
(2 ^ ((1 - 4) ^ 3)) = 1/134217728
...various short fractions...
(((3 ^ 2) + 1) ^ 4) = 10000      (the longest string of zeros produced)
...all integers...
(2 ^ (3 ^ (1 + 4))) = 14134776518227074636666380005943348126619871175004951664972849610340958208
(2 ^ ((1 + 3) ^ 4)) = 115792089237316195423570985008687907853269984665640564039457584007913129639936
Tried 23090 formulas, got 554 unique results.
import Char
import Debug.Trace
import System.Environment
import Control.Monad.Fix

  By Kevin Reid, 2008-06-15

  This is an implementation of the virtual machine described at 
  <http://www.hacker.org/hvm/>. It was designed to fit into a single IRC line
  so that its definition could be put into lambdabot
  <http://www.haskell.org/haskellwiki/Lambdabot>, and its inspiration and
  creation was documented at <http://swhack.com/logs/2008-06-15>.

  Haskell source not in HTML: <http://switchb.org/kpreid/2008/Hvm.hs>
  Non-blog location: <http://switchb.org/kpreid/2008/Hvm.html>

  Explanation of variables:

    r = VM execution function of call stack, memory, instruction pointer, and 
        operand stack
    c = call stack
    m = memory
    i = instruction pointer
    j = instruction pointer plus one
    o = operand stack

    a = arithmetic handler
    h = proceed with instruction pointer and operation stack modification
    g = proceed with operand stack modification

    z:x = one value popped from operand stack
    z:w:e = two values popped from operand stack
    k:l = one value popped from call stack

    d, t: slice lists using z as length

  To make it fit in IRC, discard comments, imports, and "main", replace 
  all line breaks with semicolons as appropriate, and discard the ' ' and _ 
  cases (i.e. the interpreter will not support whitespace or report invalid 
    perl -0777 -pe 's/\A.*(?=^s)//ms; s/\s*main .*//; s/--.*$//mg;
                    s/\n */;/g; s/[;\s]*(where|let)[;\s]*/$1 /g;
                    s/;'\'' '\''->g o;_->error\$show\(p!!i\)//;'

s p=r[](fix(0:))0[]
   r c m i o=--trace (show (m,i,(if length p<=i then '!' else p !! i),(reverse o),c)) $
     let a(&)=g$w&z:e
         h=r c m
         g=h j
         t=take z
      in case(p++"!")!!i of
         'p'->show z++g x
         'P'->chr(mod z 128):g x
         d|isDigit d->g$ord d-48:o
         '/'->a div
         '?'->h(i+case w of 0->z;_->1)e
         'c'->r(j:c)m z x
         '$'->r l m k o
         '>'->r c(t m++w:d m)j e
         'v'->g$x!!z:t x++d x
         'd'->g x
         ' '->g o

main = do [p] <- getArgs; putStrLn $ s p

I was working on some automated document generation, building the process, revising the input document, and checking the results, and got tired enough of typing "make output/foo.txt && open output/foo.txt" and then going back and editing that line when I wanted to check the PDF version etc. that I wrote a tool which I hope will have more general application as well. I called it “maken”:

# Make files and view the results.
make "$@" && open "$@"

Or it could be generalized into being a combinator, running any two commands, rather than just make and open, specified as the first two arguments:

"$ca" "$@" && "$cb" "$@"

(Which, for the Haskell folks, should be called &&&, except that that would be annoying to enter in the shell.)

Re: Zippers

Thursday, May 29th, 2008 22:18

For those wondering about the problem I was trying to solve with a zipper: After all the advice and some consideration, I decided to go with “option #2”: a whole-tree processing step which adds equal labels to corresponding variable uses and bindings. I’ve implemented all of the analysis I described in the original post using this system.

(However, the code isn't quite finished (as I discovered some problems with a different aspect of it) so it's not in any public repository yet.)

It occurs to me that there is a similarity between a zipper and the combination of an expression and an environment, as for evaluation. I've got a problem that seems almost solvable by use of this, and I would especially like to hear Planet Haskell readers' thoughts on the matter.

(The expressions given here are in E syntax.)

For example, let's start with the expression

  def x := 74
  x + 1

For those unfamiliar with E, the tree this expression parses into has structure like this (ignoring some extra features and names):

  sequence(define(var("x"), literal(74)),
           call(var("x"), "add", literal(1)))

If we move “down” zipperwise into the second subexpression of the sequence, then we get the expressionx + 1” with the contextdef x := 74 before this in a sequence”. Similarly, an interpreter uses an intermediate result of “x + 1”, “x is bound to 74”.

With a slightly extended context, I'm trying to use this to express program analysis in an auditor. The zipper context now tracks a small amount of information about variables, as well as the enclosing expressions.

The first problem is to determine that all occurrences of a given variable are used in a particular fashion: e.g. for f, permitting “f(1)” but not “f("foo")” or “somethingElse(f)” (where the third case would permit f to be used arbitrarily since the auditor doesn't get to see somethingElse’s code). This is easily accomplished by walking the entire expression looking for occurrences of var("f"), and walking “up” from each of those occurrences to check that the enclosing expressions form a permitted usage.

The second problem is to determine that the variable in a particular position is a free variable, and that its guard is of a particular form. This can be done by extending the context objects to record what variable names are bound by any expression preceding the current location (that is not inside its own block); thus walking up the contexts to the top-level determines whether the variable is free.

The third problem, I'm not sure what to do about. I have a situation roughly like this:

  def foo {
    method a() {
      def bar {
        method b() { foo }
         method("a", object(var("bar"), 
                            method("b", var("foo")))))

As part of the first problem, I have found the object “bar”; I then walk upward to determine that it is generated by a method of the object “foo”. (There are additional constraints on the structure that I haven't mentioned.) I need to determine that the reference to “foo” in “b” is in fact to the outer object, and not to some other intervening lexical binding.

I've thought of two possible solutions so far:

  1. Starting from method("a", ...), scan its children for occurrences of var("foo") and reject any which bind it. This would reject more than it needs to.
  2. Switch to a pre-processing stage (instead of the incremental operation of a zipper) to assign an identity (or a mutable analysis-information field, equivalently) to each variable binding and all of its uses, and add upward references (like in the zipper) to each node; this would make the is-this-foo-that-foo test a simple comparison.

At the moment, the second option seems attractive; tying uses to definitions of variables in a generic fashion should be useful for other types of analysis. And since this is strictly analysis, not transformation, I don't need the modify-without-mutation function of a zipper. The only reason I haven't done that yet is I think zippers are neat (and there might be other uses for an established zipper over E ASTs).

What do you think I should do?


Tuesday, August 28th, 2007 17:50

This is a somewhat odd cellular automaton implementation in Haskell. It encodes the shape of the world, and the stepping rule, in the data structure. Briefly:

data Cell v n = Cell {
  value     :: v,
  neighbors :: n (Cell v n),
  future    :: Cell v n }

-- Build a cell and its chain of futures, given its rule, similar neighbors,
-- and initial value.
mkCell :: Functor n => (v -> n v -> v) -> v -> n (Cell v n) -> Cell v n
mkCell rule val nei = initial
  where initial = Cell val nei (calcFuture initial)
        calcFuture c = c'
          where c' = Cell (rule (value c) (fmap value (neighbors c)))
                          (fmap future (neighbors c))
                          (calcFuture c')

data Moore c = Moore c c c c c c c c

-- Conway's Life
evalLife :: Bool -> Moore Bool -> Bool
evalLife v n = f v (sumN fromEnum n)
  where f _    3 = True
        f True 2 = True
        f _    _ = False

The remainder of the code is routines for setting up worlds and displaying them.

I've updated my quines page with a new Haskell quine and tags indicating whether the quine is for a REPL or writes output itself.

On Sunday, I was reading about arrows in Haskell, and I noticed that these diagrams of the primitive arrow functions looked rather like diagrams of data flow in concatenative (stack-based) languages.

This suggested that they might be related, or transformable.

(IRC log of the early discussion)

I have now found that simple concatenative code is quite easily expressed with arrows, but there are apparent limitations depending on the value representation.

  • If you use tuples (i.e. (a, (b, ()))), then the standard arrow combinators can be used for some nice definitions (e.g. call and m1_0 in the code below), and you automatically get Haskell's static typing for stack elements, but recursion and general quotation calling is not possible because the entire "stack", even the items not touched by the current "word", needs a specific type. I'd think this could be solved by existential types but I haven't seen a way to do so yet.
  • If you use lists (i.e. a : b : []), then general calls and recursion are possible, but the stack is homogeneous, and the type system can't see anything interesting about words' stack usage.

Below are my (rather disorganized) experiments so far. If you see a way to remove the restrictions of the tuple version, please let me know!

Concat.hs )

I wanted a little bit of assistance with a tile-flipping puzzle, so I wrote this little bit of almost-Haskell code.

let zero = replicate 4 $ replicate 4 $ False
let gshow g = putStrLn $ unlines [[if v then '#' else '.' | v <- r] | r <- g]
let flips = [(-1,0),(0,0),(1,0),(0,-1),(0,1)]
let gflip (x,y) g = [ [ ((vi-x,ri-y) `elem` flips) /= v | (v,vi) <- zip r [0..]] | (r,ri) <- zip g [0..]]
let grid l = foldr gflip zero l

It doesn't compute solutions given a puzzle; rather, it shows the result of a series of flips.

Prelude> gshow $ grid [(1,1)]

Prelude> gshow $ grid [(2,0),(1,2),(2,3)]

I tried a version using 2-dimensional arrays instead of lists, but gshow and gflip turned out uglier than they already are. Suggestions welcome.