grim.go

/*
    Graph Reduction Machine, or GRiM.
    
    Makes it possible to implement lazy language above golang in a dumb an simple (but messy) way.
    
    The idea is a follows:
        
        Lazy program is like a makefile - its a tree (DAG) of dependent computations.
        You can freely replace each function call with its body, provided you put the arguments in places.
        And you can replace any expression with its result - nothing will change.
        
        So, our reducer will traverse the tree, just doing these replacements, until it runs out of graph nodes.
        (This doesn't mean that the result itself won't contain any Nodes, though)
*/

package main

import (
    "fmt"
    "reflect"
)

type Anything interface{}

/*
    Represents pure lazy value. Will return it on calling it.Reduce()
 */
type Node struct {
    Reduce Reducer
}

type Reducer func() Anything

/*
    Reduces a value until result itself is not a Node.
 */
func (node Node) GetValue() Anything {
    for {
        switch res := node.Reduce().(type) {
        // if reduces to (res Node), node can be replaced by res
        // because purity!
        case Node:
            node.Reduce = res.Reduce
            continue

        // otherwise, node is equivalent to one just returning its value
        default:
            node.Reduce = func() Anything {
                return res
            }
            return res
        }
    }
}

/*
    Reduce a node to int or panic.
 */
func (node Node) GetInt() int {
    switch res := node.GetValue().(type) {
    case int:
        return res

    default:
        panic("Not an int: " + fmt.Sprint(reflect.TypeOf(res)))
    }
}

func (node Node) GetString() string {
    switch res := node.GetValue().(type) {
    case string:
        return res

    default:
        panic("Not a string: " + fmt.Sprint(reflect.TypeOf(res)))
    }
}

func (node Node) GetBoolean() bool {
    switch res := node.GetValue().(type) {
    case bool:
        return res

    default:
        panic("Not an boolean: " + fmt.Sprint(reflect.TypeOf(res)))
    }
}

/*
    Reduce a node to 1-ary function or panic.
 */
func (node Node) Call(a Node) Node {
    switch res := node.GetValue().(type) {
    case func(a Node) Node:
        return res(a)

    default:
        panic("Not an func(a Node, b Node) Node: " + fmt.Sprint(reflect.TypeOf(res)))
    }
}

/*
    Reduce a node to 2-ary function or panic.
 */
func (node Node) Call2(a Node, b Node) Node {
    switch res := node.GetValue().(type) {
    case func(a Node, b Node) Node:
        return res(a, b)

    default:
        panic("Not an func(a Node, b Node) Node: " + fmt.Sprint(reflect.TypeOf(res)))
    }
}

/*
    Make a node from anything.
 */
func Now(a Anything) Node {
    return Node {
        func() Anything {
            return a
        },
    }
}

/*
    Make a node from delayed expression (will be invoked once).
 */
func Later(a func() Anything) Node {
    return Node { a }
}

/*
    Structure to test compilability of cyclic structures.
 */
type Push struct {
    Head Anything
    Tail Anything
}

type Nil struct {}

/*
    List of all numbers starting fron n.

    numbers-from (n) = Push(n, numbers-from(n + 1))
 */
func NumbersFrom(n int) Node {
    return Now(Push {
        Head: Now(n),
        Tail: Later(func() Anything {
            return NumbersFrom(n + 1)
        }),
    })
}

/*
    Accumulate list with some reducer.

    type List = Push(x, xs) | Nil

    reduce-list(zero, add) = loop
      where
        loop = function
            | Push(x, xs) -> add(x, loop(xs))
            | Nil         -> zero
 */
func ReduceList() Node {
    return Now(func(zero Node, add Node) Node {
        var loop func(Node) Node
        loop = func (list Node) Node {
            switch l := list.GetValue().(type) {
            case Push:
                return Later(func () Anything {
                    return add.Call2(Now(l.Head), loop(Now(l.Tail)))
                })

            case Nil:
                return zero

            default:
                panic("Neither Push or Nil: " + fmt.Sprint(reflect.TypeOf(l)))
            }
        }
        return Now(loop)
    })
}

/*
    Take at least n elements from a list.
    Works for infinite lists, too.

    take-while (pred) =
        reduce-list(Nil, (x, xs) -> if
            | pred(x) -> Push(x, xs)
            | else    -> Nil
        )
 */
func TakeWhile() Node {
    return Now(func(predicate Node) Node {
        return ReduceList().Call2(Now(Nil{}), Now(func(x Node, xs Node) Node {
            if predicate.Call(x).GetBoolean() {
                return Now(Push { x, xs })
            } else {
                return Now(Nil{})
            }
        }))
    })
}

/*
    Operator <.

    less-than(a)(b) = b < a
 */
func LessThan() Node {
    return Now(func(a Node) Node {
        return Now(func (b Node) Node {
            return Now(b.GetInt() < a.GetInt())
        })
    })
}

/*
    list-to-string = reduce-list("", (x, xs) -> x + " :: " + xs)
 */
func ListToString() Node {
    return ReduceList().Call2(Now("[]"), Now(func(x Node, xs Node) Node {
        return Now(fmt.Sprint(x.GetValue()) + " :: " + fmt.Sprint(xs.GetValue()))
    }))
 }

/*
    length-list = reduce-list(0, (x, xs) -> 1 + xs)
 */
func LengthList() Node {
    return ReduceList().Call2(Now(0), Now(func(x Node, xs Node) Node {
        return Now(1 + xs.GetInt())
    }))
 }

/*
    Dire shit.
 */
func main() {
    add := Now(func(a Node, b Node) Node {
        return Now(a.GetInt() + b.GetInt())
    })
    i := Now(int(1))
    j := add.Call2(i, i)
    print("Seems ok: " + fmt.Sprint(j.GetValue()) + "\n")

    // list = numbers-from(0)
    list := NumbersFrom(0)

    // ten = take-while(less-than(10), list)
    ten  := TakeWhile().Call(LessThan().Call(Now(10))).Call(list)

    // str = list-to-string(ten)
    str  := ListToString().Call(ten)
    print(str.GetString())
    print("\n")

    // len = length-list(ten)
    len  := LengthList().Call(ten)
    print(len.GetInt())
    print("\n")
}