### Wow... Visi works

Well, it's been a month since I announced the whole Visi thing.  When I announces, I had a barely functional type checker and inferencer and a barely functional expression evaluator.

That's all changed in the last month.  As I've gotten my Haskell Foo on and gone with an existing implementation of Hindley-Milner type checking rather than trying to write my own from first principals, I've made a ton of progress with the Visi language.

For example, Visi can implement Factorial:

fact n = if n == 0 then 1 else n * fact n - 1
res = fact 10 //  testResults [("res", DoubleValue 3628800)] . checkResults)

The above code is taken right out of the Visi test suite.  Parsing, type checking, and computation works

Visi supports inner functions.  Rather than having an explicit "let" in the Visi syntax, you can define a local function 'fact' is referenced inside the 'f' function.  The local 'fact' function is passed, partially applied, to the 'app' function and correctly applied:

fact n = n & \"hello\" {-  propper scoping this fact is not the inner fact -}
f n = {- Test partially applied functions -}
fact n = if n == 0 then 1 else n * fact(n - 1)
app n fact
app v f = f v
res = f 8 // testResults [("res", DoubleValue 40320.0)] . checkResults)

Local functions close over scope.  For example, 'f' returns a local function that takes two parameters and references the 'b' variable and computes the product of the three variables.  The 'q' function applies 'f' to 8 and 'z' applies 'f' to 10.  WIth these functions, we can apply or partially apply the functions:

f b = {- test that the function closes over local scope -}
timesb n m = n * b * m
timesb
app v f = f v
q = f 8
z = f 10
res = (app 9 (app 8 q)) - ((z 8 9) + (z 1 1)) // testResults [("res", DoubleValue (-154))] . checkResults)

Note, too, the clean syntax.  No line-end characters.  No "let" keyword (although variable shadowing is possible and not yet flagged as an error).

So, check out the tests to get a better sense of both the Visi language and the test harness that I'm using for Test Driven Development.

### Mmm... sweet tasty state monads

One of the really challenging things about Haskell is the lack of state... or more specifically, the lack of global state.

In Scala there are a ton of places you can put state (stuff that's mutated across method invocations.)  You can use globals, thread-local variables (something that Lift makes heavy use of), and instance variables.  Here are some examples:

Global:

object MyState {
private var cnt = 0

def inc = synchronized {cnt += 1}
def dec = synchronized {cnt -= 1}
def getCnt = synchronized {cnt}
}

Instance variables are pretty much the same, except you have to pass the instance around:

class MyState {
private var cnt = 0

def inc = synchronized {cnt += 1}
def dec = synchronized {cnt -= 1}
def getCnt = synchronized {cnt}
}

In Haskell, there's no mutability, so if you have a reference to a chunk of data, the data will never change.  In order to change the state, you must create a new instance, but any holder of the old reference see the old data.  In general, this is a GoodThing™ because you don't have to worry about state changing out from under you, but it makes accumulating state pretty difficult.  For example, if we want to count the number of hellos and goodbyes and accumulate the names of the people who said Hello or Goodbye, it's easy to do:

val state = new MyState

val greeters = List(("David", "Hello"), ("Archer", "Woof"), ("Annette", "Bye")).flatMap {
case (name, "Hello") => state.inc ; List(name)
case (name, "Bye") => state.dec ; List(name)
case _ => Nil
}

At the end of the above execution, we have a list of people who have made greetings and the side effect of updating the state object with the net Hello/Bye count.

In Haskell, without the State monad, we'd have to accumulate both the count and the names and then fold across them:

list = [("David", "Hello"), ("Archer", "Woof"), ("Annette", "Bye")]

gTest (name, "Hello") = (1, [name])
gTest (name, "Bye") = (-1, [name])
gTest _ = (0, [])

acc = map gTest list

sumIt (i1, n1) (i2, n2) = (i1 + i2, n1 ++ n2)

summed = foldr1 sumIt acc

As the state that we carry around becomes more complex, it.  Further, having to fold our result in sumIt is counterintuitive.  We've already done the calculation, why do we have to fold the pairs into the final result?

There's a simpler way to carry state around in Haskell.  Here's an example:

-- the stateful test
sTest v =
do
i <- get -- get the current state
case v of
-- update the state and then return the value
(name, "Hello") -> put (i + 1) >> return [name]
(name, "Bye") -> put (i - 1) >> return [name]
_ -> return []

sAcc = (mapM sTest list)

sSummed = mapFst concat \$ runState sAcc 0

In the above code, we're separating the state from the core name calculation.  The get function get the state into the variable i.  Depending on the greeting, we increment, decrement or ignore the state.

Now, the thing that confused me for years about the State monad was where "get" was getting from and where "put" was putting it.  Well, it's like this, the State Monad is actually some accumulated functions that are "played" by the runState function.  sAcc function returns a bunch of functions.  The runState function takes that function and a seed value (in this case, 0), and plays the function to get the resulting information and the resulting state.

The State Monad makes stuff like parsing and keeping state while parsing (e.g., the current count of AST elements we've encountered) is very powerful and makes Haskell code that is in effect imperative a lot easier to write.

I recently tried to implement Hindley-Milner type inferencing without the State Monad and the code was nasty and complex with lots of state being returned all over the place (see https://github.com/visi-lang/visi/commit/cfe7d6fe5a6b25795a1c32ab2f18cfcbad1f9b54#diff-1 and all the atv, atv', etc. state) and then https://github.com/visi-lang/visi/blob/b8f06c73f66596af8333ab09d9528bada068a188/core/src/Visi/Typer.hs  Note that all the state stuff is handled in the State Monad rather than cluttering up the logic of the code.  I've come to really like the State Monad a lot... it makes me feel somewhat imperative while being functional. ;-)