Program specified GC and memory management in high level languages

I want to have a language where I am able to specify low level aspects of the system (among other things), things like how much stack is allocated and how heap memory management works. I am a programming language dilettante, so I have much to learn.

However I also think functional languages are a good thing, and I don’t want to give up the simplicity of programming it affords. So I had the idea of making constructors and normal function scope syntactic sugar for functions. We need low level memory functions to do these tasks.

So we’d have special functions like


!unsafeAlloc :: Int -> Scope -> Block


!unsafeAddRef :: Block -> Scope -> ()


!unsafeDeref :: Block -> Scope -> ()


Which all programs would be expected to specify, although there will be system calls they can just assign them to if they want.

The ! meaning that garbage collection is not used on this function. Defining constructors would also create a non memory managed variant with the block of memory used for the construction as the last .

So assuming a Data like the archetypal Natural with an S constructor


h = S n

would be syntactic sugar for


h = !S n (!unsafeAlloc (size S) currentScope)


unsafeAlloc should add a reference to the currentScope as well.

Scopes would also be syntactic sugar. They would require setting up the scope object at the beginning of the function and mapping unsafeDeref over all the blocks when the scope was closed. Ordering would be done by means of the scope monad. So something along the lines of

do
currentScope <- newScope;
---- code here---
!fmap (unsafeDeref) currentScope;
destruct currentScope


In fact the memory manager should really be a monad to keep it pure, as all requests might not be granted. However making it all monadic code would restrict the ability to reorder functions for parallel code.

I’m sure that there are probably a few gotchas that I am not seeing and my thinking is still a bit muddled, but that is the core of the idea.

Are there any simple haskell/ML ish languages I could play around with to see how memory management works there?

Unbounded Graphs2

Just a quicky, I found a function that returns nice breadth first orderings of the graphs.

gIterate2 :: (b -> [b]) -> [b] -> [[b]]
gIterate2 f xs = iterate (concat. map f) xs

You can even avoid cycles by making the Data type a tuple with a set and then using a function like the following

take 4 $ gIterate2 (\(x,y) -> if member x y then [] else ((x+1), insert x y):[(x-1, insert x y )]) [(1, empty)]

This gets a list of all the nodes 4 iterations away from the original. It does have some limitations compared to the way I did it yesterday in that it can’t return a different type (due to the use of iterate). You can get around this somewhat by using a tuple again with a dummy return value placed in.

Edit from here for added value.

Now that isn’t very pretty lets define a function noRepeat that you can apply to any function a -> [a] to filter out repeats

noRepeat :: (Ord t) => (t -> [a]) -> (t, Set t) -> [(a, Set t)]
noRepeat f (x,y) = if member x y then [] else zip (f x) (repeat (insert x y))

The basic type is (a -> [a]) -> b -> [b]

Let us call this a function transformer. Now the basic output from that is pretty ugly

take 5 $ gIterate2 (noRepeat (\x -> (x+1):[(x-1)])) [(1, empty)]

[[(1,fromList [])],[(2,fromList [1]),(0,fromList [1])],[(3,fromList [1,2]),(1,fromList [1,2]),(1,fromList [0,1]),(-1,fromList [0,1])],[(4,fromList [1,2,3]),(2,fromList [1,2,3]),(0,fromList [-1,0,1]),(-2,fromList [-1,0,1])],[(5,fromList [1,2,3,4]),(3,fromList [1,2,3,4]),(-1,fromList [-2,-1,0,1]),(-3,fromList [-2,-1,0,1])]]

So what can we do? Well if we map (map fst) on it we can get back just the list of nodes. We’ll call the fst the “detransformer” of noRepeat.

So lets create a data type

data TransTriple m a b = Dere {getInit :: a -> b, getTransform :: (a-> m a) -> (b -> m b), getDetrans:: b -> a}

This defines a way to initialise the change, a way to transform the step function given normally and a way to get back to the original value.

gtransformIter pair f xs = Prelude.map (Prelude.map (getDetrans pair)) $ gIterate2 (getTransform pair$ f) (Prelude.map (getInit pair) xs)

We define a new function to take all of these and apply them properly to gIterate2.

a `comp` b = Dere (\x -> getInit a $ getInit b$ x ) (\x -> getTransform a $ getTransform b$ x ) (\x -> getDetrans b $ getDetrans a $ x)

Why do we do this? So we can compose them together. `comp` acts as (.) but for all the functions in the right order. It is not very pretty at the moment.

So let us define a couple of transformer triples.

noRepeat f (x,y) = if member x y then [] else zip (f x) (repeat (insert x y))

stopWhen cond f x = if cond x then [] else f x

noRepeatTriple = Dere (\x -> (x, empty)) (noRepeat) fst

notFiveTriple = Dere id (stopWhen(==5)) id

So you can now call something like

gtransformIter (noRepeatTriple `comp` notFiveTriple) (\x -> (x+1):[(x-1)]) [1]

And it spit out a pure list of numbers, ignoring any branches that get to 5 or any that start to cycle.

I’ll try and do a simple game search next time using this framework.

Unbounded Graphs 1

I’m probably reinventing the wheel here, but I haven’t come across this elsewhere.

I came across an idea whilst working on Traces, unbounded graphs (I could say infinite, but I am something of a constructionist).

An unbounded graph is a graph defined by a function

adjacentNodes :: a -> [a]

The function adjacentNodes could for example create every possible legal game move from the current position, run every possible lsystem rule on the string or find all legal one step permutations of Trace (some of these generate Trees but the method I am applying here is fairly universal). There is also scope for creating strings out of grammars in general.

So lets say you want to find out a property of your graph. Whether in a Trace a certain substring can occur, for example. Or whether there is a strategy to guarantee a win in a small game.

To generate every node in the unbounded graph you just generate a list of those nodes and append a list of those nodes with iterate applied recursively. Warning unbounded lists created! Also code not thoroughly tested.

> import Data.List as List
> import Data.Set as Set
> import Data.Monoid
> gIterate :: (a -> [a]) -> a -> [a]
> gIterate nextNodes start = nextList ++  (List.concat $ List.map (gIterate (nextNodes)) nextList)
>                               where nextList = nextNodes start

You can get back to iterate simply by doing

 take 10 (mIterate (\a -> [a]) '!')

iterate is just creating a unbounded graph where there is only one possible adjacent node! Now iterating through a graph with mulitple options is a bot more interesting then the flat graphs done by iterate. So you might choose to ignore some edges, for example those you have visited before.

> gIterateNoCycles :: (Ord a, Eq a) => (a -> [a]) -> Set a -> a -> [a]
> gIterateNoCycles nextNodes visited start = nextList ++  (List.concat $ List.map (gIterateNoCycles (nextNodes) visited') nextList)
>                                         where nextList = List.filter (\a -> member a visited) $ nextNodes start
>                                               visited' = Set.insert start visited  

Or those that fail some predicate, a heuristic or the end of the game.

> gFilteredIterate :: (Ord a, Eq a) => (a -> [a]) -> (a -> Bool) -> a -> [a]
> gFilteredIterate nextNodes filt start = nextList ++  (List.concat $ List.map (gFilteredIterate (nextNodes) filt) nextList)
>                                         where nextList = List.filter (filt) $ nextNodes start
> 

However all this (++) is not always ideal, lets generalise it somewhat.

> gfoldMap :: Monoid b => (a -> [a]) -> (a -> b) -> a -> b
> gfoldMap nextNodes transform start = mconcat (List.map (transform) (nextList)) `mappend` (mconcat $ List.map (gfoldMap (nextNodes) (transform)) nextList)
> where nextList = nextNodes start

This allows you to use the Any monoid if you just want to find if one of the Nodes satisfies a predicate, or the First monoid to look for one value. However it does mean that you can no longer specify how far to search with the (take n) trick, unless you specify transform to be something that returns a list. So you would probably want to use one of the variants above, or specify a number to go with it.

Why I am building what I am building

There are a number of things that aren’t quite right with computer systems today that can’t be fixed by throwing more processing power into the machine or creating a new language built upon the current foundations.

These are problems to do with the maintenance of the system, updating it and keeping it virus free. These problems can be seen starkly when looking at autonomous systems, that don’t have programmers/engineers dedicated to improving the system. I consider fixing these problems as a precursor project to getting flexible, adaptable AIs.

The problems stem from the fact that computers were invented by mathematicians, and them considering computers as abstract computational machines guided by the benevolent programmer. Which is not a good abstraction for todays world with fairly widespread malware, with the computers looked after by people fairly ignorant of its inner workings (or just time constrained).

So something needs to change, and I think at a fairly fundamental level. But revolution is hard, so it should be done right to minimize the number of times revolution has to occur.

These problems boil down to one major point: A programs ability to acquire resources should be aligned with its usefulness. A virus is negatively useful and should get no resources (no memory/processing time), a scheduler is useful so should be get some resources, if a better scheduler comes into a computer system it should also be able to acquire resources.

By resources I mean things like the following:

Memory Usage – Both Heap and Stack. A good program should be able to ask for and get what it needs. Also memory bandwidth shouldn’t be able to be monopolized for free.
Harddisk Usage/Memory bandwidth.
System Resources – E.g Things like threads IDs if they are a limited resource.
Interrupts – Which programs should get activated when a timer or input interrupt goes off.
Controlling Network/video/sound.

This all sounds like a welter of variety. So to try and make things uniform in the way in posix that everything is a file, every resource in my system is a sort of capability. A capability in my system can be thought of as an unforgeable/unalterable/revocable pointer.

So for example if a process got control of an interrupt it would be given a special executable capability, that when called would take a capability in a register as a the capability to call when the interrupt fired. Programs are given capabilities for memory chunks as well, which they can assign to be used as stack or used as heap.

Now I haven’t explained how the system get the capabilities. Just assume for a moment it is a form of agoric bidding.

The answer to the question why I am building anything at all, is that I want to understand what a human brain is (so computational systems that are self-maintaining are important to build and understand), and I want to make the cost of living cheaper.

Traces – less ordered strings (part 1)

I decided to read about Traces. I’m going to tell you I learnt to try and cement the ideas in my mind.

First off, strings have two more monoid natures! It is on the removal of the first occurrence of string a from string b from the left or right. Both the monoid natures have the empty string as the mempty.

So remR "cabcabac" "ab" would be “cabcac” whereas remL "cabcabac" "ab" would be “ccabac”. Removal of a string that isn’t contained leads to no change. This is called the quotient monoid I think, I still don’t have the terminology down.

Traces are strings when you don’t care about some ordering in them. Something like the following untested bit of code

class (ListLike a, Enum a, Bounded a, Eq a) =>Trace a where
   swappablePairs :: Set (a,a)
   swappablePairs = difference (cross [minBound..maxBound] [minBound..maxBound])  unswappablePairs
   unswappablePairs :: Set (a,a)
   unswappablePairs = difference (cross [minBound..maxBound] [minBound..maxBound])  swappablePairs
   traceEq :: Trace a  -> Trace a -> Bool

Note when I say (a,c) is swappable I also mean (c,a) is swappable.

So an example of a trace applied somewhat to seeing what a processor is doing. Lets say we have two cores that share a bit of memory they are working on. The symbols a and b represent each process acting on the shared memory, also (a,b) and (b,a) is swappable. So let us define another pair of operations that represent the cores handing off to each other c is core 1 handing to core 2 and d is core 2 to core 1. So (a,c) is unswappable as you can’t move operations before or after blocking and so is (b,d). (c,d) is also unswappable. e is nothing interesting going on and is swapabble with anything.

So a trace “aeeeeb” should be traceEq to “eeeeab” that is both cores writing to shared memory with no hand off, which is bad. “aaeeceeebbbeeda” is traceEq to “eeeeeacbda”, which is fine as there are the proper hand offs between ‘a’s and ‘b’s. This doesn’t seem so useful at the moment, although I think things get more interesting when you have two different bits of shared memory that can interleave.

The way I’m guessing it is used in process calculi is that you generate grammars for the processes and then see if the space of all possible strings on the language contains sequences traceEq to things you don’t want e.g. a and b next door to each others or an infinite sequence of hand offs with no processing. Quite how to do that I am unsure….

Are they useful for what I want to do? Possibly, I think I will give people the option of specifying a writer or something similar to go a long and build up traces or something, by processing the current Vrrm state and assigning it a symbol. Ideally there should be some way of discovering the grammar as well… though I am not sure how to do this, although it might be easy(ish) if the symbol assignment process doesn’t hide state.

Next time I’ll try to implement instances of traceEq, and make sure my implementation of Trace is actually sane.

Struggling with the type system

As you can read from my previous blog I want to make VrrmDiffLists monoids.

However it would also make sense to make them lists. Lists already have a monoid instance (++) and (mempty), and you can’t currently give them a new one. So what to do?

You can newtype them, but then you are always wrapping and unwrapping the values to do things with them. Which is less than ideal. Strictly speaking the lists are still lists, and you should be able to do listy things with them.

With the Num wrappers like Sum and Product things aren’t too bad as Num is a typeclass and you can just instantiate it easily or automatically derive it. Lists aren’t currently typeclasses, and while they have been made you still can’t use the common list operators on them, or use them in places where people have defined their libraries to use lists.

So the other option is to rework monoids so I can keep lists as lists.

This is my current way forward. The monoid nature data class is supposed to indicate monoidness of a class (although it could quite easily be a type (a, a->a->a) and use snd and fst to get at the members of the tuple). A DMonoid is a way of typeclassing a new class so you can still use all the monoids stuff. Ideally we would go back and change such things as Writers/Foldables to use monoid natures instead of relying on dmonoids.

data MonoidOver a = MO { getMempty :: a, getMappend :: a->a->a }
class  DMonoid a  where
    defaultMonoidOver :: MonoidOver a 

instance (DMonoid a) => Monoid a where
   mempty = getMempty defaultMonoidOver
   mappend = getMappend defaultMonoidOver

dmconcat dm = foldr (getMappend dm) (getMempty dm)

This kinda works, but I tried to implement a monad instance of a derived Writer, and got stuck trying to get mempty.

So this isn’t an elegant solution worth investing time in. Do we need a change to the type system? I’m sure such things have been proposed before. I’ll sketch my idea and I’ll call it Aspects. Defined when you instantiate something using // or other symbol. So

instance (Num//Sum a) => Monoid a where
     mappend  = (+)
     mempty = 0

or

instance Monoid [a]//Diff where
  mappend = MergeDiffs
  mempty  = []

[a]//Diff would type check differently to [a], but functions are automatically polymorphic over both if they accept [a]. Also you need a default instance of the typeclass you want to aspect over. Converting between aspects seems like something ugly unless you perhaps require classes to have aspects to implement something similar to the toInteger. fromIntegral trick. Or more precisely deconstruct itself then reconstruct it.

I'll have a look how feasible this is to implement something like this somehow, but it seems likely I will just wrap/unwrap my strings for now. *

Thanks go out to #haskell quicksilver, dmwit and others that answer my questions.

Todo for next time

Read trace monoids, something useful if I want to represent execution of a system that can go multiple ways I think, which might be nice to get down...

* It turns out that you can do something like this by instantiating things in a module and then importing that seperately, qualified by how you import.

EDSL for Debugging in haskell and diffs

So I’m going to do an embedded domain specific language in haskell. Mainly so I don’t have to go through all the bother of building all the interpreter plumbing.

So what will it look like roughly? As I am interested in figuring out what is going on in the virtual machine, I’ll need lots of information about how it changes. This lead me to think that a very useful idea would be the patch. So you could run the VM for number of steps and get back a list of the changes. Merge them into one and save it to disk so you can quickly get back to this state, or save every step. You could have it return a tuple of the operations and arguments ran and the diffs, and because of laziness you could select the one you want. So you could do stats on the ops ran as well.

So the main useful function would be something like…

runVrrm :: Vrrm -> n -> (Vrrm, [Instuction], [VrrmDiffList])

This would apply a diff to the vrrm state and get the new state. Hopefully you should also be able to do it backwards to turn back time.

applyDiffFor:: VrrmDiff -> Maybe Vrrm -> Maybe Vrrm
applyDiffBack:: VrrmDiff -> Maybe Vrrm -> Maybe Vrrm

It would have to be Maybe, because if you apply diff to a machine state of a different memory size or variant of the architecture would barf and return Nothing.

You could apply them with folds

foldr (applyForwardDiff) (Just startstate) diffList

Although most likely you’d want to strictly merge them into one before doing this as the temp vrrmstates would be very big.

Getting categorical

Making a VrrmDiffList a monoid seems like a good idea, basically it allows you to merge them together. As well as function that takes two diffs and composes them together you need a value that makes no difference what it is composed with. This shouldn’t be too hard.

Also I’ll note at this point that a partially applied applyDiffFor or back on a diff is an arrow, and can be used as such. Something theoretically interesting, but I am not quite sure how to use it at the moment.

I’m also interested in the symmetries implicit in the diffs implying some form of group-ness. That you can negate diff should imply some more stuff, but it is not quite a group because negate a `mappend` a = mempty. Although it could do, you would lose the information about values had changed.

A brief example how it might work to give you a flavour.

Let us say that the whole of the state is one array. A diff would be something like

newtype VrrmDiff = Diff { getStart :: Int , getLength::Int , getChangeList :: [(Int, Int)]}

The change list would assume the first Int was the original value and the second the changed value. Now you could compose the diffs in such a way that if the original value and changed value where the same it would be removed. This would make it a group.

Both VrrmDiff 0 0 [] and VrrmDiff 0 1 [(1,1)] would have the same affect on an array *, that being nothing.

* Note arrays are different from lists in haskell, I’ll use to indicate an array.

DSL for reverse engineering

The first thing I am going to do is develop an interpreter/debugger for the arch in haskell.

I am currently looking at making a domain specific language to control the debugger. The reason why the debugger has to be some complex is that you will want to figure out what is going on inside the system as it grows and changes.

I will be looking at Eresi for inspiration. Although I will need to add new primitives to it as well.

Why I’m not working on Opencog

There is some overlap between what I am doing and what opencog, at least in that it wants to be an OS for AI and that the architecture I am making should be useful for implementing AI (among other things).

Also it has a form of agorics for attention allocation, and wants to be able to do build new mind agents ( roughly programs) from atoms (data), that is be self-programmable.

So from a high level view it seems to tick lots of the boxes, so why am I not on board? Because it doesn’t focus on these things and take them seriously in the design. Reading the README for the cogserver dir there still isn’t a scheduler, and things still have to poll for IO rather than have interrupts.

Now this will be fixed at some point no doubt it will get a scheduler, but it probably won’t be fixed to the way I want to go. This comes down to me wanting the scheduler to be alterable. The choice of scheduler is important, it is something we allow to vary in our current computer systems. I have a vision where the scheduler specializes to the tasks assigned to it.

Now it is not strictly necessary (that is you can compute the same things with a half decent general scheduler) but I think it makes a neater conceptual abstraction, adding a simple layer to a von Neumann machine. It also allows the system to modify itself to protect itself from (unintentional as well as intentional) Denial of Resources attacks from the programs it runs. This factor can be crucial in how useful a system is in the real world.

This brings me to another philosophical difference I have with opencog, I assume all programs are potentially malicious or just full of errors that can cause DoR attacks. This I think is necessary when working with systems that are experimentally self-programmable. And experimental self-programmability is necessary for interesting self-programmability as far as I can see.

Haskell VMonoids

I’ll occasionally post stuff about haskell on this blog as it is my language of choice, and I am still learning it.

I’ve come across something lacking in monoid, it occured to me when I was trying to think of a nice way to solve the problem of taking a list of bounds and getting a bound that encompassed them all.

E.g.
[(1,3), (51 , 60) , (12, 55)] –> (1,60)

Now it would be nice just to mconcat them. However there isn’t a value for mempty, at least not one I can see. You can define a function for mappend.

mappend a b = (x,y)
             where x = min (fst a) (fst b)
                   y = max (snd a) (snd b)

There are many values for mempty that would work for this example, anything between (1,1) and (60,60).

So you can imagine a variant of monoid with different type class.

class VMonoid a where
  mvempty :: a - > a
  mvappend :: a -> a -> a

mvconcat :: [a] -> a
mvconcat xall@(x:xs) = foldr mappend (mvempty x) xall

The rules that mvempty must follow would be something like the following

(mvempty x) ‘mvappend‘ x = x
x ‘mvappend‘ (mvempty x) = x

Is this an interesting pattern or not worthwhile? Note code is untested and may be buggy…