This is a bug fix for typefuck - credit due to Kai Meder for pointing it out.
I'd forgotten to add a change that I made in development to the gunzip that I put online, so the example didn't work.
Cheers Kai!
typefuck-0.0.2
24 November 2009
16 November 2009
Typefuck
Ah, so lovely to see you again, gentle readers. It's been a long time - and I have no explanations for my absence - but you must forgive me - after all, long does the mind dwell on mysteries, and long can mysteries dwell unseen.
But worry not, gentle readers, for I have a gift for you. As you know I have a fondness for implementing programming languages - it makes me think of kittens, polymorphic types and lockers full of stolen credit cards.
Enough to bring a nostalgic tear to anyone's eye.
Especially those who value esoteric knowledge.
Secrets await you, fair soul, who may read this code and wonder how much I had to drink.
Brainfuck implemented within the Haskell type checker
WTF:
Typefuck is a brainfuck which runs within the Haskell type checker - that is, prior to compilation. If a rationale is to be sought, it is as another proof that the GHC type checker is turing complete.
Here are the type level commands
-- | Add +
data A = A
deriving Show
-- | Minus -
data M = M
deriving Show
-- | Right >
data R = R
deriving Show
-- | Left <
data L = L
deriving Show
-- | Iterate [ ]
data I bf = I bf
deriving Show
-- | Put .
data P = P
deriving Show
-- | Get ,
data G = G
deriving Show
So the simple brainfuck program: ,>,[-<+>]<.
(which adds two numbers)
is equivalent to the Haskell type
type Add =
Cons G
(Cons R
(Cons G
(Cons (I (Cons M
(Cons L
(Cons A
(Cons R Nil)))))
(Cons L
(Cons P Nil
)))))
Use the Brainfuck type to evaluate.
The first type parameter represents the program, while the second represents the input.
Input and output are represented as Cons-ed linked lists of unary integers, constructed from Succ, Zero, and Neg (for negative integers)
Assert that the function 'show_type' has this type to show a value level solution for the problem (though all working is done within the type checker)
Example:
spoon@utensil:~/Desktop$ ghci
GHCi, version 6.10.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :m +Typefuck
Prelude Typefuck> show_type :: Brainfuck Add (Cons (Succ (Succ (Succ Zero))) (Cons (Succ (Succ Zero)) Nil))
Loading package syb ... linking ... done.
Loading package base-3.0.3.1 ... linking ... done.
Loading package typefuck-0.0.1 ... linking ... done.
Cons (Succ (Succ (Succ (Succ (Succ Zero))))) Nil
But worry not, gentle readers, for I have a gift for you. As you know I have a fondness for implementing programming languages - it makes me think of kittens, polymorphic types and lockers full of stolen credit cards.
Enough to bring a nostalgic tear to anyone's eye.
Especially those who value esoteric knowledge.
Secrets await you, fair soul, who may read this code and wonder how much I had to drink.
Brainfuck implemented within the Haskell type checker
WTF:
Typefuck is a brainfuck which runs within the Haskell type checker - that is, prior to compilation. If a rationale is to be sought, it is as another proof that the GHC type checker is turing complete.
Here are the type level commands
-- | Add +
data A = A
deriving Show
-- | Minus -
data M = M
deriving Show
-- | Right >
data R = R
deriving Show
-- | Left <
data L = L
deriving Show
-- | Iterate [ ]
data I bf = I bf
deriving Show
-- | Put .
data P = P
deriving Show
-- | Get ,
data G = G
deriving Show
So the simple brainfuck program: ,>,[-<+>]<.
(which adds two numbers)
is equivalent to the Haskell type
type Add =
Cons G
(Cons R
(Cons G
(Cons (I (Cons M
(Cons L
(Cons A
(Cons R Nil)))))
(Cons L
(Cons P Nil
)))))
Use the Brainfuck type to evaluate.
The first type parameter represents the program, while the second represents the input.
Input and output are represented as Cons-ed linked lists of unary integers, constructed from Succ, Zero, and Neg (for negative integers)
Assert that the function 'show_type' has this type to show a value level solution for the problem (though all working is done within the type checker)
Example:
spoon@utensil:~/Desktop$ ghci
GHCi, version 6.10.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :m +Typefuck
Prelude Typefuck> show_type :: Brainfuck Add (Cons (Succ (Succ (Succ Zero))) (Cons (Succ (Succ Zero)) Nil))
Loading package syb ... linking ... done.
Loading package base-3.0.3.1 ... linking ... done.
Loading package typefuck-0.0.1 ... linking ... done.
Cons (Succ (Succ (Succ (Succ (Succ Zero))))) Nil
15 October 2009
Metal music
Sometimes I write metal music and record my creations. This is one of those times!
I thought human implantation would be a brutal topic for a metal song, so I wrote one.
wetware
lyrics
I love my cry-baby wah wah pedal. Also thanks to the audacity and hydrogen teams. Go go GNU power!
Enjoy :)
EDIT: This song has been described as a coming together of Ian Curtis, Killing Joke, Machine Head, Muse and the Pet Shop Boys. Is this complimentary?
Anyway, this mix is intended for big bass systems or good head-phones. I mix not the bass for shitty laptop speakers.
It's quite strange I find actually - if the bass is loud it sounds great on laptops, but overwhelming on stereos. So for more macho systems, the song needs to be more of a pussy as regards bass. I'm sure there's a paradox in there somewhere.
I thought human implantation would be a brutal topic for a metal song, so I wrote one.
wetware
lyrics
I love my cry-baby wah wah pedal. Also thanks to the audacity and hydrogen teams. Go go GNU power!
Enjoy :)
EDIT: This song has been described as a coming together of Ian Curtis, Killing Joke, Machine Head, Muse and the Pet Shop Boys. Is this complimentary?
Anyway, this mix is intended for big bass systems or good head-phones. I mix not the bass for shitty laptop speakers.
It's quite strange I find actually - if the bass is loud it sounds great on laptops, but overwhelming on stereos. So for more macho systems, the song needs to be more of a pussy as regards bass. I'm sure there's a paradox in there somewhere.
8 October 2009
Jason Wright
Jason died last week. We used to hang out in Garmouth and Lhanbryde. He was a really cool person, was excellent company, and a really funny chap. He used to roll really long cigarettes; that made me laugh. He liked computers and he was a funky drummer and guitarist. We made some music once, I still have a cd. I haven't seen him in a long time but I will still miss him. So funkiness to you, Jason and goodbye.
6 October 2009
Wooo
Delve type checked a simple polymorphic function today -
Polymorphism in Delve is similar to polymorphism in an untyped language like ruby.
In Ruby, you can define a method which takes an object and accesses one of its members - even if no such object is in scope.
In Delve, such a function can be defined, but constraints are imposed on its arguments. They must possess that member for the type checker to accept the program.
This approach differs fundamentally with Haskell. With Haskell, the function writer must be responsible for writing code that uses a given type class, or function - it must be defined.
In Delve all the responsibility is on the function caller, who must ensure his arguments have the appropriate type. It's strongly typed ruby/python/smalltalk :)
I've been ranting about it for a while, but now it's really happening! Wooo!
Actually I feel really unproductive. Since August, I've written 6.3K lines of code for the Delve VM and compiler. The last week I was off to Aberdeen, and now it's just testing, testing, testing. I'm confirming it works, and fixing little bits when I need to, but I haven't written more than 100 lines in the past two weeks.
Must work more...
Polymorphism in Delve is similar to polymorphism in an untyped language like ruby.
In Ruby, you can define a method which takes an object and accesses one of its members - even if no such object is in scope.
In Delve, such a function can be defined, but constraints are imposed on its arguments. They must possess that member for the type checker to accept the program.
This approach differs fundamentally with Haskell. With Haskell, the function writer must be responsible for writing code that uses a given type class, or function - it must be defined.
In Delve all the responsibility is on the function caller, who must ensure his arguments have the appropriate type. It's strongly typed ruby/python/smalltalk :)
I've been ranting about it for a while, but now it's really happening! Wooo!
Actually I feel really unproductive. Since August, I've written 6.3K lines of code for the Delve VM and compiler. The last week I was off to Aberdeen, and now it's just testing, testing, testing. I'm confirming it works, and fixing little bits when I need to, but I haven't written more than 100 lines in the past two weeks.
Must work more...
hashing within a range
It is trivial to define a function which given a range of numbers R and the number of bits in the hash B, produces a hashing algorithm to hash strings which have a length within R into a hash of size B.
Here is such a trivial function, in pseudocode*:
make_hash( R , B ) =
// the longest possible string as input
Longest = max( R )
// if the number of bits is greater or equal to the number of bits in the string
if B >= Longest * 7 then
// Compute a hash from the given hash H and the string with first character C, and rest S
hash( H , C : S) =
// Shift H 7 bits to the left
Shifted_H = H << 7
// recurse, ORing C with the shifted hash
hash( S , Shifted_H | C )
hash( H , _ ) = H
// Use curried application to give an initial hash of 0
return hash( 0 )
What would be nice would be a hashing function which is optimal like this, for values within the range - but when a string has a length that is not in the range, the algorithm has a chance of producing a non unique hash for it. The further the length of the string is from the range, the lesser the chance of the algorithm producing unique hash, given the string.
I theorize that it is possible for strings of lengths beyond the range to have a unique hash, in some situations, and not in others. To take a simple example, in the range [ 1 .. B / 7 ], any value not in the range cannot have a unique hash - there are not enough bits! However in the range [ 1 .. ( B - 1 ) / 7 ] with there are some bits left over, so it is possible.
* That's some weird pseudo-code. Uppercase variables like Erlang? Bitwise operators like C? Guards like Haskell? Curried function application? Someone implement it!
Here is such a trivial function, in pseudocode*:
make_hash( R , B ) =
// the longest possible string as input
Longest = max( R )
// if the number of bits is greater or equal to the number of bits in the string
if B >= Longest * 7 then
// Compute a hash from the given hash H and the string with first character C, and rest S
hash( H , C : S) =
// Shift H 7 bits to the left
Shifted_H = H << 7
// recurse, ORing C with the shifted hash
hash( S , Shifted_H | C )
hash( H , _ ) = H
// Use curried application to give an initial hash of 0
return hash( 0 )
What would be nice would be a hashing function which is optimal like this, for values within the range - but when a string has a length that is not in the range, the algorithm has a chance of producing a non unique hash for it. The further the length of the string is from the range, the lesser the chance of the algorithm producing unique hash, given the string.
I theorize that it is possible for strings of lengths beyond the range to have a unique hash, in some situations, and not in others. To take a simple example, in the range [ 1 .. B / 7 ], any value not in the range cannot have a unique hash - there are not enough bits! However in the range [ 1 .. ( B - 1 ) / 7 ] with there are some bits left over, so it is possible.
* That's some weird pseudo-code. Uppercase variables like Erlang? Bitwise operators like C? Guards like Haskell? Curried function application? Someone implement it!
5 October 2009
Hash (algorithms, not the sticky kind)
Consider Dan Bernstein's hashing algorithm:
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c;
return hash;
}
(I've yanked this from U of York's CS pages)
I've often wondered about this algorithm. It always striked me as strange as to why it shifts left by 5, rather than 8. I reckon the overlapping allows longer strings to be hashed, at the expense of uniqueness. This would also be why the hash is added to its shifted sibling.
However I randomly generated some input strings and hashed each one with this Haskell program, to see how many of the resultant hashes would collide. The answers surprise me:
import Data.Bits
import Foreign.C.Types
import Data.List
chr :: CULong -> Char
chr = toEnum . fromEnum
ord :: Char -> CULong
ord = toEnum . fromEnum
bhash :: String -> CULong
bhash = bhash' 5381
where
bhash' hs ( c : s ) = ord c + bhash' ((hs `shiftL` 5) + hs) s
bhash' hs _ = hs
collide :: CULong -> IO ( )
collide n =
let l = map bhash $ mk_syms n
cols = length l - ( length $ nub l )
in print $ "There were " ++ show cols ++ " collisions"
mk_syms :: CULong -> [ String ]
mk_syms n = map mk_unique_sym [ 0 .. n ]
mk_unique_sym :: CULong -> String
mk_unique_sym = mk_unique_sym' [ ]
mk_unique_sym' :: String -> CULong -> String
mk_unique_sym' acc w =
if w >= 26
then
mk_unique_sym' ( c8 : acc ) $ ( w `div` 26 ) - 1
else ( chr $ 97 + w ) : acc
where
c8 :: Char
c8 = chr $ ( w `mod` 26 ) + 97
GHCi, version 6.10.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( dan_hash.hs, interpreted )
Ok, modules loaded: Main.
*Main> collide 100
"There were 48 collisions"
*Main> collide 1000
"There were 888 collisions"
*Main> collide 10000
"There were 9861 collisions"
*Main> collide 100000
"There were 99769 collisions"
I'm assuming the high number of collisions are a property of my mechanical input, though its not surprising that the number of collisions increase as the input grows.
Tomorrow I think I might feed the words from the aligned hansards into it, to see if human speech fares better.
PS mk_unique_sym is what the Delve compiler uses to make unique names for new variables in intermediate code phase.
Also - the type checker has type checked a couple of expressions. I'm very happy - a full release should be soon :)
And then its time to rewrite the VM.... the work goes on.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c;
return hash;
}
(I've yanked this from U of York's CS pages)
I've often wondered about this algorithm. It always striked me as strange as to why it shifts left by 5, rather than 8. I reckon the overlapping allows longer strings to be hashed, at the expense of uniqueness. This would also be why the hash is added to its shifted sibling.
However I randomly generated some input strings and hashed each one with this Haskell program, to see how many of the resultant hashes would collide. The answers surprise me:
import Data.Bits
import Foreign.C.Types
import Data.List
chr :: CULong -> Char
chr = toEnum . fromEnum
ord :: Char -> CULong
ord = toEnum . fromEnum
bhash :: String -> CULong
bhash = bhash' 5381
where
bhash' hs ( c : s ) = ord c + bhash' ((hs `shiftL` 5) + hs) s
bhash' hs _ = hs
collide :: CULong -> IO ( )
collide n =
let l = map bhash $ mk_syms n
cols = length l - ( length $ nub l )
in print $ "There were " ++ show cols ++ " collisions"
mk_syms :: CULong -> [ String ]
mk_syms n = map mk_unique_sym [ 0 .. n ]
mk_unique_sym :: CULong -> String
mk_unique_sym = mk_unique_sym' [ ]
mk_unique_sym' :: String -> CULong -> String
mk_unique_sym' acc w =
if w >= 26
then
mk_unique_sym' ( c8 : acc ) $ ( w `div` 26 ) - 1
else ( chr $ 97 + w ) : acc
where
c8 :: Char
c8 = chr $ ( w `mod` 26 ) + 97
GHCi, version 6.10.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( dan_hash.hs, interpreted )
Ok, modules loaded: Main.
*Main> collide 100
"There were 48 collisions"
*Main> collide 1000
"There were 888 collisions"
*Main> collide 10000
"There were 9861 collisions"
*Main> collide 100000
"There were 99769 collisions"
I'm assuming the high number of collisions are a property of my mechanical input, though its not surprising that the number of collisions increase as the input grows.
Tomorrow I think I might feed the words from the aligned hansards into it, to see if human speech fares better.
PS mk_unique_sym is what the Delve compiler uses to make unique names for new variables in intermediate code phase.
Also - the type checker has type checked a couple of expressions. I'm very happy - a full release should be soon :)
And then its time to rewrite the VM.... the work goes on.
3 October 2009
distraction
My my, I've rather been distracted from this whole computer world. I blame my University course and life in general. Have at you, life!
However, I now have a small break - it's quite amusing because I don't think anyone else has a holiday at this time of year. So to everyone else - na na na na naaa na.
Have at you, everyone else.
I'm really embarressed - I've had the amusing complaint that my tagsoup parser handles not some of the xml data types, like our happy friend Mr CDATA. I've never actually used the thing - it was a half baked solution to the problem of gathering links in shpider. Sorry Mister! I'll fix it (soon).
I trekked up to Aberdeen a couple of times in the last few weeks. Lizzie has been transfered into second year Geography, which is good. However she lives in Hillhead which is amusing.
Our sleep was interrupted one night by the tumultuous yobbery of three freshers chanting xenophobic English football songs. They were followed closely by a throng of international students, whom they had apparently befriend. Weird as hell. Also, not a good demonstration of adapting to survive, on the part of the English football fans, considering their proximity to Tillydrone and other lovely places to live.
Delve delve delve. I've neglected you so! But really, it'll get done. Sooo many bugs, so many tests to pass.
But I've sworn to make the next release coherent - so I'd rather get it done properly, and let it take a while.
I visited Rory's flat while at Aberdeen, where I'd left my copy of the dragon book - so I starded reading the section on code generation and runtime systems again. I've concluded that it won't be so difficult to compile Delve into machine code.
However, due to the support for continuations, a lot of data, is going to have to go on the heap rather than stack - I don't want to have to make deep stack copies all the time.
However, I now have a small break - it's quite amusing because I don't think anyone else has a holiday at this time of year. So to everyone else - na na na na naaa na.
Have at you, everyone else.
I'm really embarressed - I've had the amusing complaint that my tagsoup parser handles not some of the xml data types, like our happy friend Mr CDATA. I've never actually used the thing - it was a half baked solution to the problem of gathering links in shpider. Sorry Mister! I'll fix it (soon).
I trekked up to Aberdeen a couple of times in the last few weeks. Lizzie has been transfered into second year Geography, which is good. However she lives in Hillhead which is amusing.
Our sleep was interrupted one night by the tumultuous yobbery of three freshers chanting xenophobic English football songs. They were followed closely by a throng of international students, whom they had apparently befriend. Weird as hell. Also, not a good demonstration of adapting to survive, on the part of the English football fans, considering their proximity to Tillydrone and other lovely places to live.
Delve delve delve. I've neglected you so! But really, it'll get done. Sooo many bugs, so many tests to pass.
But I've sworn to make the next release coherent - so I'd rather get it done properly, and let it take a while.
I visited Rory's flat while at Aberdeen, where I'd left my copy of the dragon book - so I starded reading the section on code generation and runtime systems again. I've concluded that it won't be so difficult to compile Delve into machine code.
However, due to the support for continuations, a lot of data, is going to have to go on the heap rather than stack - I don't want to have to make deep stack copies all the time.
14 September 2009
Delve a little late
The next release of Delve, with type checker and bug fixes is gonna be maybe another week away - development is going very well and smoothly, but I've decided to create a cool program I've been thinking about for a while -
See, in a pen and paper RPG, if the players decide to completely ignore the intended quest, for some reason and hang around in a bar instead, the dungeon master (DM) must be able to improvise, either to push them on to the intended quest, or instead to facilitate their mucking around, perhaps by creating a new quest.
This is something you can never have with World of Warcraft or Fallout or any computerized RPG game - well, something you can never have without a lot of artificial intelligence research.
So I want to develop a computer aided rpg system which allows for the flexibility of pen and paper RPGs as well as the complex rules and speed of a computer system. I'm gonna call it C.A.R.P, or just carp, because it's less of a pain to write that way.
There are some computer aided rpgs around - notably OpenRPG and RPG virtual table-top, but carp will differ from them.
I feel virtual table-top is, from the DM's perspective, too text based. It covers many things with documents which would be better written as scripts. Improvisation takes place entirely within a chat window - and then the benefits of programmatic game-play is lost . We can do better than this!
For instance, the player should have a panel of buttons which correspond to 'obvious actions' - stuff like the classic "GO NORTH", "CLIMB UP THE ROPE", "SHOOT THE KOBOLDS WITH YOUR GRENADE LAUNCHER". These are obviously dependent on your location, the current item you have equipped - this is dependent on the game rules, which is dependent on the DM.
Therefore, the DM needs to be able to add widgets to the player's GUIs at his whim. The game needs a scripting system, then, which is powerful enough to give the DM this control.
Also the computer should be able to generate appropriate adversities for the players to fight at any point, this would require statistical analysis, but that's ok.
Of course, a chat window is mandatory for information.
Erlang is a good choice for development language - because it can evaluate itself as a script and can send data around networks and has really good control over its own processes.
The power of erlang is such that its easy(ish) to imagine a player using an item in the game world which would cause a whole new game window to open, containing a whole new copy of carp - but one that exists literally inside the players universe - like in the xkcd comic.
Features, with the more important features ( those I'm going to implement first ) closer to the top:
GUI
Network support - can be played over the internet
Run-time scripting so the DM can improvise when needed
Game rules and content, built using the run time scripting mentioned above
Hot-seat mode - so more than one player can share a computer
Support for a mix hot-seat and network play - so say four people can play together with only 3
Tools for statistical analysis of various things in the game - so for instance the DM can generate appropriate adversities for the players
Features carp will not have:
animation
on-screen maps (print em or draw em, so your players can write on em)
grilled chicken
Also Lizzie notes that I've sunk to new levels of geekiness.
See, in a pen and paper RPG, if the players decide to completely ignore the intended quest, for some reason and hang around in a bar instead, the dungeon master (DM) must be able to improvise, either to push them on to the intended quest, or instead to facilitate their mucking around, perhaps by creating a new quest.
This is something you can never have with World of Warcraft or Fallout or any computerized RPG game - well, something you can never have without a lot of artificial intelligence research.
So I want to develop a computer aided rpg system which allows for the flexibility of pen and paper RPGs as well as the complex rules and speed of a computer system. I'm gonna call it C.A.R.P, or just carp, because it's less of a pain to write that way.
There are some computer aided rpgs around - notably OpenRPG and RPG virtual table-top, but carp will differ from them.
I feel virtual table-top is, from the DM's perspective, too text based. It covers many things with documents which would be better written as scripts. Improvisation takes place entirely within a chat window - and then the benefits of programmatic game-play is lost . We can do better than this!
For instance, the player should have a panel of buttons which correspond to 'obvious actions' - stuff like the classic "GO NORTH", "CLIMB UP THE ROPE", "SHOOT THE KOBOLDS WITH YOUR GRENADE LAUNCHER". These are obviously dependent on your location, the current item you have equipped - this is dependent on the game rules, which is dependent on the DM.
Therefore, the DM needs to be able to add widgets to the player's GUIs at his whim. The game needs a scripting system, then, which is powerful enough to give the DM this control.
Also the computer should be able to generate appropriate adversities for the players to fight at any point, this would require statistical analysis, but that's ok.
Of course, a chat window is mandatory for information.
Erlang is a good choice for development language - because it can evaluate itself as a script and can send data around networks and has really good control over its own processes.
The power of erlang is such that its easy(ish) to imagine a player using an item in the game world which would cause a whole new game window to open, containing a whole new copy of carp - but one that exists literally inside the players universe - like in the xkcd comic.
Features, with the more important features ( those I'm going to implement first ) closer to the top:
GUI
Network support - can be played over the internet
Run-time scripting so the DM can improvise when needed
Game rules and content, built using the run time scripting mentioned above
Hot-seat mode - so more than one player can share a computer
Support for a mix hot-seat and network play - so say four people can play together with only 3
Tools for statistical analysis of various things in the game - so for instance the DM can generate appropriate adversities for the players
Features carp will not have:
animation
on-screen maps (print em or draw em, so your players can write on em)
grilled chicken
Also Lizzie notes that I've sunk to new levels of geekiness.
11 September 2009
sXe analysis
Lepht got me thinking about the straight edge (also known as sXe).
I think the most interesting thing about sxers is the phenomenon that they form a community at all. It is like a monastery, where every member must abstain - and also partake in cabal approved recreation - that is the dancing you will see if you go to a hardcore gig.
But, as is asked in the faq "Why do you need a label to be poison free?". The answers presented do not satisfy me.
The first: "this label help keep us together and stay strong."
So you're weak? That interesting - so a sxer might rely on other sxers to help them fight their own cravings for drugs and drink. It worries me that a person who doesn't drink or smoke can be so terrified of ruining their life through excess that they need a support group.
The second answer satisfies me even less: "the label shows you're actually serious about what you're saying and that you're not making any exceptions"
In what way does a label show that you're serious? You could be lying and just saying you're sxe! The only way for a person to know you're serious is a close study of your behaviour over a long period of time. This answer is, to quote Dr. Sheldon Cooper, demonstrably fallacious.
The author goes on to admit that the sXe is corrupted by hypocracy, but is an ideal to be aspired to. Since others can corrupt the ideal through corrupting their own bodies, and can do this without your knowledge, how then can a person reasonably trust those who share their community? They cannot.
The commitment must be taken on word of mouth. Now I'm moving beyond the world of logical analysis, which is my tool since I have no subjects to interview, but my hypothesis would be that commitment is viewed as the cool factor of a real sXe community - a community which, through members lapsing and then getting control back, over time fades into grey like an animation reel of black then white, rather than the dichotomy of abstinence and corruption.
I think the most interesting thing about sxers is the phenomenon that they form a community at all. It is like a monastery, where every member must abstain - and also partake in cabal approved recreation - that is the dancing you will see if you go to a hardcore gig.
But, as is asked in the faq "Why do you need a label to be poison free?". The answers presented do not satisfy me.
The first: "this label help keep us together and stay strong."
So you're weak? That interesting - so a sxer might rely on other sxers to help them fight their own cravings for drugs and drink. It worries me that a person who doesn't drink or smoke can be so terrified of ruining their life through excess that they need a support group.
The second answer satisfies me even less: "the label shows you're actually serious about what you're saying and that you're not making any exceptions"
In what way does a label show that you're serious? You could be lying and just saying you're sxe! The only way for a person to know you're serious is a close study of your behaviour over a long period of time. This answer is, to quote Dr. Sheldon Cooper, demonstrably fallacious.
The author goes on to admit that the sXe is corrupted by hypocracy, but is an ideal to be aspired to. Since others can corrupt the ideal through corrupting their own bodies, and can do this without your knowledge, how then can a person reasonably trust those who share their community? They cannot.
The commitment must be taken on word of mouth. Now I'm moving beyond the world of logical analysis, which is my tool since I have no subjects to interview, but my hypothesis would be that commitment is viewed as the cool factor of a real sXe community - a community which, through members lapsing and then getting control back, over time fades into grey like an animation reel of black then white, rather than the dichotomy of abstinence and corruption.
Government sentimentality
I protested against the Iraq war in Glasgow because I hate the pain and the fear and blood that I knew would come with it; it sickens me! But all this posturing sickens me further.
I'm so sick of the platitudes voiced by the media and our weak government that I worry that I'm turning into a right wing, highly opinionated, weirdy-beardy geezer.
Are people really shocked that the CIA torture people? Have we run out news? Perhaps people will next complain that the army kill people! Really, how are they going to get answers out of prisoners? Play the enemy limp bizkit until they bleed from the eyes? Ahh but see, they're the not the 'enemy' because this isn't a war - they're evil criminals who are facing justice. Oh pleeeeese.
On the subject of evil criminal prisoners: if people are worried about terrorism, why are they upset about the more peaceful relationship we can have with Libya, now that Megrahi has been transfered? Surely with peace, the threat they pose to us is diminished.
Of course, lots of MPs and the US also are making a big stink - hang on a minute - these people are so upset, they would rather irritate a developed foreign power, than transfer a man from a jail here to a jail there. This is the sort of idiocy which leads to war. Of course, it's okay if you're the US 'cus you can just bomb them again if you get really pissed off.
In this case, those who hold the moral high-ground and are not prepared to compromise are the dangerous ones. Don't they realize the other side think that they have the high-ground too? Will they instead fight over that ethereal hillock?
Since we're talking about hypocrisy and deliberately aggravating other nations, western policy on Iran needs a mention. In fact, I'd say it takes the biscuit. Now I really don't like the stuff their regime does. But why, when you consider other weird/aggressive countries (I'm looking at you, China, Russia, Pakistan and the good ol' U. S. of A. ) do we have such a strong stance against Iran? Why do we try to interfere with their nuclear program and lay sanctions against them and not China?
It's because they're weak. Our leaders want them to stay weak so they do not threaten us. It's the truth, but it's the scary truth no-one is ready for, and no-one wants to admit.
Who're the nasty scary countries again?
The question is: Why do these powerful men who invaded Iraq and Afghanistan shy away from the war and bloodshed and pain, and hide behind a false chivalry? Have they learned nothing from Caesar and Ghengis Khan? Khan achieved not great moral victories but lasting prosperity and safety for his people!
Also, to perform this false crusade they had to lie to their own people - about having a moral right to fight against some 'axis of evil'. I think some of the people who are now upset bit the doctrine a little hard, and did not fully comprehend the consequences of a war. To these people I recommend spending some time looking at bombs, bullets and their local hospital's casualty ward.
And about the possibility of Cameron being in charge of the next righteous crusade - now this is subjective - however well he might run things, I wouldn't trust him standing next to me with a pistol in his pocket. He's just some geezer - the sort of people I trust with guns are military types who know what they're for and understand their safe operation and maintenance.
Did you know the UK has no launch codes for its nuclear weapons? The submarine captains are in absolute control over world destruction - but no one is worried. It seems that warriors can be trusted to keep the peace - while politicians arguing amongst themselves spread deceit and death.
Have a swell day!
I'm so sick of the platitudes voiced by the media and our weak government that I worry that I'm turning into a right wing, highly opinionated, weirdy-beardy geezer.
Are people really shocked that the CIA torture people? Have we run out news? Perhaps people will next complain that the army kill people! Really, how are they going to get answers out of prisoners? Play the enemy limp bizkit until they bleed from the eyes? Ahh but see, they're the not the 'enemy' because this isn't a war - they're evil criminals who are facing justice. Oh pleeeeese.
On the subject of evil criminal prisoners: if people are worried about terrorism, why are they upset about the more peaceful relationship we can have with Libya, now that Megrahi has been transfered? Surely with peace, the threat they pose to us is diminished.
Of course, lots of MPs and the US also are making a big stink - hang on a minute - these people are so upset, they would rather irritate a developed foreign power, than transfer a man from a jail here to a jail there. This is the sort of idiocy which leads to war. Of course, it's okay if you're the US 'cus you can just bomb them again if you get really pissed off.
In this case, those who hold the moral high-ground and are not prepared to compromise are the dangerous ones. Don't they realize the other side think that they have the high-ground too? Will they instead fight over that ethereal hillock?
Since we're talking about hypocrisy and deliberately aggravating other nations, western policy on Iran needs a mention. In fact, I'd say it takes the biscuit. Now I really don't like the stuff their regime does. But why, when you consider other weird/aggressive countries (I'm looking at you, China, Russia, Pakistan and the good ol' U. S. of A. ) do we have such a strong stance against Iran? Why do we try to interfere with their nuclear program and lay sanctions against them and not China?
It's because they're weak. Our leaders want them to stay weak so they do not threaten us. It's the truth, but it's the scary truth no-one is ready for, and no-one wants to admit.
Who're the nasty scary countries again?
The question is: Why do these powerful men who invaded Iraq and Afghanistan shy away from the war and bloodshed and pain, and hide behind a false chivalry? Have they learned nothing from Caesar and Ghengis Khan? Khan achieved not great moral victories but lasting prosperity and safety for his people!
Also, to perform this false crusade they had to lie to their own people - about having a moral right to fight against some 'axis of evil'. I think some of the people who are now upset bit the doctrine a little hard, and did not fully comprehend the consequences of a war. To these people I recommend spending some time looking at bombs, bullets and their local hospital's casualty ward.
And about the possibility of Cameron being in charge of the next righteous crusade - now this is subjective - however well he might run things, I wouldn't trust him standing next to me with a pistol in his pocket. He's just some geezer - the sort of people I trust with guns are military types who know what they're for and understand their safe operation and maintenance.
Did you know the UK has no launch codes for its nuclear weapons? The submarine captains are in absolute control over world destruction - but no one is worried. It seems that warriors can be trusted to keep the peace - while politicians arguing amongst themselves spread deceit and death.
Have a swell day!
9 September 2009
Things wot I dun wrong, or how I learned to love compiler development
The Delve typechecker is nearly done, a patch should be pushed by the end of the week. It infers interfaces of objects instead of their concrete types, and so it acts like a strongly typed Smalltalk or Ruby, which was the plan.
Anyone who has looked at the Delve repository might have been struck by the absence of automatic unit testing available. This won't be a problem for the typechecker - I can think up loads of expressions which should typecheck, and loads which shouldn't - then I simply have to look at the results. The rest of the compiler/VM is not so simple.
For instance, how is one to automatically check that tail-call optimization is working properly? We can look at the internals of the virtual machine, but this is a bad idea - I initially debugged the virtual machine with unit tests written in the target VM language - which can take a hundred lines to do something that takes a few in the source language Delve. Since the machine is very fluid, every time I get a better idea then the machine changes. Having hundreds of lines of test code which have to change when the machine changes is too much work, especially considering I'm the only person currently hacking on Delve :)
To solve this problem, I'm gonna add unit tests for tail recursion, coroutines using continuations, mutually recursive routines which I can be sure allocate a large, fixed quantity of memory every recursion. Then I'd like to use POSIX resource management to see if the limit is exceeded.
However, this is POSIX only, and will also require statistical analysis to ensure it works correctly across many systems.
I need a better plan... :)
Also I had made a bit of a silly mistake. See, the way the Delve in the public repository works is:
String is parsed into Core
Core is VARAPPED into VarCore - a version of core without nested expressions - temporary variables overcome this.
VarCore is RESOLVED into LocalCore - like var core, but local variables are associated with a stack index - since the VM records a stack of local scopes, it's better to pre-compute which local scope is associated with each variable.
LocalCore is then compiled into VM code.
However, I realized that the RESOLUTION into local core should occur before type checking, and also since VARAPPING a legal program should result in another legal program, that type checking should occur before VARAPP.
Soo the process is now
String is parsed into Core
Core is RESOLVED into LocalCore
LocalCore is type-checked.
LocalCore is VARAPPED into VarCore
VarCore is compiled to DCode.
This is requiring much of the compiler to be changed to support different data-types - an advantage of the small codebase (only now 6.2KSLOC) is that this should only really take an hour or three. Of course, this is poor software engineering - several solutions spring to mind:
I was tempted to define an abstract form of core, AbstractCore, which would have kind * -> *. So it would be AbstractCore md, where md is associated MetaData. Compilation would proceed by transforming the metadata.
This has the disadvantage of errors like nested expression occuring in the syntax tree after the varapp phase not being caught at compile time - I would have to check they would be caught at run time.
Or I could associate each element in the tree with an integer, and just have an IntMap which maps the integer to associated MetaData. I think this would be easier to manage - since the metadata would be separated from the Tree.
This still suffers from that disadvantage.
However, if the various syntax trees are queried through a type-class, then they could be used independently. Also, this could return various elements in a type-safe manner, for instance, before the VarApp phase, there could be a type class instance for function application, which with multiple parameters would associate the application with arbitrary, possibly nested expressions. The instance used in the VarApp phase would associate the application with variables only.
This bit of randomness has turned into an idea! I think I will try this. Firstly, I'm just gonna get it working again, though, in the old and simple style - changing it to support new abstract types is going to a be a little bit more work than simply renaming a few things, which is all I have to do now.
Anyone who has looked at the Delve repository might have been struck by the absence of automatic unit testing available. This won't be a problem for the typechecker - I can think up loads of expressions which should typecheck, and loads which shouldn't - then I simply have to look at the results. The rest of the compiler/VM is not so simple.
For instance, how is one to automatically check that tail-call optimization is working properly? We can look at the internals of the virtual machine, but this is a bad idea - I initially debugged the virtual machine with unit tests written in the target VM language - which can take a hundred lines to do something that takes a few in the source language Delve. Since the machine is very fluid, every time I get a better idea then the machine changes. Having hundreds of lines of test code which have to change when the machine changes is too much work, especially considering I'm the only person currently hacking on Delve :)
To solve this problem, I'm gonna add unit tests for tail recursion, coroutines using continuations, mutually recursive routines which I can be sure allocate a large, fixed quantity of memory every recursion. Then I'd like to use POSIX resource management to see if the limit is exceeded.
However, this is POSIX only, and will also require statistical analysis to ensure it works correctly across many systems.
I need a better plan... :)
Also I had made a bit of a silly mistake. See, the way the Delve in the public repository works is:
String is parsed into Core
Core is VARAPPED into VarCore - a version of core without nested expressions - temporary variables overcome this.
VarCore is RESOLVED into LocalCore - like var core, but local variables are associated with a stack index - since the VM records a stack of local scopes, it's better to pre-compute which local scope is associated with each variable.
LocalCore is then compiled into VM code.
However, I realized that the RESOLUTION into local core should occur before type checking, and also since VARAPPING a legal program should result in another legal program, that type checking should occur before VARAPP.
Soo the process is now
String is parsed into Core
Core is RESOLVED into LocalCore
LocalCore is type-checked.
LocalCore is VARAPPED into VarCore
VarCore is compiled to DCode.
This is requiring much of the compiler to be changed to support different data-types - an advantage of the small codebase (only now 6.2KSLOC) is that this should only really take an hour or three. Of course, this is poor software engineering - several solutions spring to mind:
I was tempted to define an abstract form of core, AbstractCore, which would have kind * -> *. So it would be AbstractCore md, where md is associated MetaData. Compilation would proceed by transforming the metadata.
This has the disadvantage of errors like nested expression occuring in the syntax tree after the varapp phase not being caught at compile time - I would have to check they would be caught at run time.
Or I could associate each element in the tree with an integer, and just have an IntMap which maps the integer to associated MetaData. I think this would be easier to manage - since the metadata would be separated from the Tree.
This still suffers from that disadvantage.
However, if the various syntax trees are queried through a type-class, then they could be used independently. Also, this could return various elements in a type-safe manner, for instance, before the VarApp phase, there could be a type class instance for function application, which with multiple parameters would associate the application with arbitrary, possibly nested expressions. The instance used in the VarApp phase would associate the application with variables only.
This bit of randomness has turned into an idea! I think I will try this. Firstly, I'm just gonna get it working again, though, in the old and simple style - changing it to support new abstract types is going to a be a little bit more work than simply renaming a few things, which is all I have to do now.
28 August 2009
Doing and being
I've been reading Sartre's Being and Nothingness again - it's very interesting!
I read it last year, but since then, all the ideas have become muddled in my mind - also I have a tendency to jump back and forth between the concepts I am struggling with, rather than read linearly and absorb at the author's intended pace, so I'm attempting to give it a much fuller read this time.
I just really want to share how cool I think this book is! Occasionally I get stuck and have to draw out his arguments in predicate logic. Thinking about it, it would be cool to encode his ontology into prolog maybe - then you could question details of his thought directly. Also to retrieve quotations.
Occasionally I find myself in bad faith - I work a lot sometimes to create cool things - and I feel that somehow that makes me cooler, but this is bad faith because I am seeking to escape what I am to be what I am not, and simultaneously to escape what I am not to be what I am.
So cheers to Sartre for letting me figure that one out :)
I read it last year, but since then, all the ideas have become muddled in my mind - also I have a tendency to jump back and forth between the concepts I am struggling with, rather than read linearly and absorb at the author's intended pace, so I'm attempting to give it a much fuller read this time.
I just really want to share how cool I think this book is! Occasionally I get stuck and have to draw out his arguments in predicate logic. Thinking about it, it would be cool to encode his ontology into prolog maybe - then you could question details of his thought directly. Also to retrieve quotations.
Occasionally I find myself in bad faith - I work a lot sometimes to create cool things - and I feel that somehow that makes me cooler, but this is bad faith because I am seeking to escape what I am to be what I am not, and simultaneously to escape what I am not to be what I am.
So cheers to Sartre for letting me figure that one out :)
26 August 2009
pointless
This post is a literate haskell file.
I like the pointless style of programming - that is, functions do not mention the variables they act upon explicitly. While this is very common and cool, it's also a source of amusement - occasionally I find myself distract from a project by a need/desire/delusional whim to re-write various functions as pointless as possible. So here is a little one, it's nothing special.
> import Control.Arrow
> por1 :: (b -> Bool) -> (b -> Bool) -> b -> Bool
> por1 = curry $ curry $ uncurry (||) . (uncurry $ uncurry (&&&))
That is, por is a function which takes two predicates and input -
each predicate is from a polymorphic type b to a boolean
Apply both the predicates to the input, producing two boolean valies
Apply "Or" to these values to return one result.
There are automated tools to do this sort of obsfucation with haskell but I find my brain boils attempting to hack out this sort of "write-only" code. (this is a good thing)
Here is what the pointfree took makes of a pointful version* of the above:
> por2 = ((uncurry (||) .) .) . flip (&&&)
I like that, though the flip, in this case, is semantically irrelevant.
More about the pointless style
also comparison to unix pipelines
The question is: how to implement uncurry in bash? Next post, possibly. Hobgoblin has had the better of me tonight! :)
* the pointful version:
> por3 p q = uncurry (||) . (q &&& p)
I like the pointless style of programming - that is, functions do not mention the variables they act upon explicitly. While this is very common and cool, it's also a source of amusement - occasionally I find myself distract from a project by a need/desire/delusional whim to re-write various functions as pointless as possible. So here is a little one, it's nothing special.
> import Control.Arrow
> por1 :: (b -> Bool) -> (b -> Bool) -> b -> Bool
> por1 = curry $ curry $ uncurry (||) . (uncurry $ uncurry (&&&))
That is, por is a function which takes two predicates and input -
each predicate is from a polymorphic type b to a boolean
Apply both the predicates to the input, producing two boolean valies
Apply "Or" to these values to return one result.
There are automated tools to do this sort of obsfucation with haskell but I find my brain boils attempting to hack out this sort of "write-only" code. (this is a good thing)
Here is what the pointfree took makes of a pointful version* of the above:
> por2 = ((uncurry (||) .) .) . flip (&&&)
I like that, though the flip, in this case, is semantically irrelevant.
More about the pointless style
also comparison to unix pipelines
The question is: how to implement uncurry in bash? Next post, possibly. Hobgoblin has had the better of me tonight! :)
* the pointful version:
> por3 p q = uncurry (||) . (q &&& p)
22 August 2009
Delve tutorial
It occured to me that readers would be unable to decipher the last post without reading the tutorial, so I'll link that here:
Tutorial on the untyped delve core
Tutorial on the untyped delve core
21 August 2009
The Delve Type System
(EDIT: bogus logic fixed)
I've been working on the type system for Delve. Here lie the innovative features of the language.
It would be nice to infer the interface of objects, rather than an exact name. This is a much more Smalltalkish approach - an untyped language considers only the interface - the names are irrelevant. Consider this example: ( Warning, I haven't actually tested the examples - it's of little importance to the thought really )
In Haskell, consider the silly ADT
data Tree = Branch { tree :: Tree }
And the Haskell function, bound to the variable f:
let f = \ b -> tree b
Now say we have a Delve object corrosponding to the Tree adt.
(: Tree (Object.new))
(: Tree.tree
(me ()
(self)))
See here * for an example which constructs a class using the meta-object model.
And the corresponding Delve function, bound to the variable f:
(: f (fu (b) ((b.tree))))
Now with Haskell, the type checker will say: what is the type of 'tree'? It's 'Tree -> Tree'. Therefore f is of type 'Tree -> Tree'
Now what I'm trying to do with Delve is for Delve to say "b is a new mutant object of which I know nothing. However, it must have the method tree. Therefore, the type of f is 'Mutant with method tree, where tree is of type a -> a'
I think that's pretty cool.
To get this magic to work however, I have given Delve four type constructs. Firstly to explain the key concepts of unification and domination.
In Delve, a type is unified with another type if one type can be used in the place of another. This is a separate notion from equality - equality is a subset of unification.
Domination is where one type, (a type which is more concretely defined) actually replaces the other type in the type system. What seems to the type-checker as an initially polymorphic variable can be dominated into becoming a concrete variable in this manner.
So this is a first attempt at describing the various types.
An object: an object is a value of indisputable type.
For unification with another type, the two types must be objects, the objects must have the same name, and the types of both objects members must all be the same ( recursively considering these types ).
A mutant: a mutant is a value of disputable type.
A mutant can be unified with another mutant if the members of the first mutant are a subset of the second mutant of the same name - in that they set of the names of the first mutant is a subset of the second, all also that each of the intersection of the two sets of members unify.
A mutant also unifies with an object, if the above restrictions are met, but an object will dominate a mutant - that is, an object can be used as a function argument where a mutant is expected, but if an object is assigned to a mutant variable - the variable will become an object.
Mutants which unify can be merged, by safely putting the member types of both mutants into one new mutant. The changes must be propagated to any mutants which unified with the old type.
A function: Delve is strict and does not support curried function application, therefore a function can be simply represented by a list of types.
A function unifies with another function only if each of their types unify.
A polymorph: a polymorph will unify with any type, will be dominated by any other type.
The types arranged then in order of concreteness
Object, Function
Mutant
Polymorph
Now for an example, back back to our function:
(: f (fu (b) ((b.tree))))
The type checker will then type check this as follows – try to imagine you are the Delve type checker – this will be your thought process.
A function will be assigned to the variable f.
f will have the type of this function.
Since this function has one argument, the initial type which we will consider will be “Polymorph called a → Polymorph called b” (to use a Haskelly sort of notification”
So open a new scope, and let b be a new polymorph called a.
Now look at the code for this function.
A member of b, called tree, is being called.
So the type of b might be a “Mutant with with a member tree, where tree is a Polymorph called x”
This is ok, because this new type unifies with b's old type, since everything unifies with a polymorph.
Also, this type dominates b's old type. So b's new type is “Mutant with member tree, where tree is a Polymorph called x”
Tree is called of b, which is a polymoph called x.
So the return type of this function is a polymorph called x.
So the type of this function is 'Mutant with member tree, where tree is a polymorph called x → x'
So the type of f is 'Mutant with member tree, where tree is a polymorph called x → x'
Which is what we want. I think this is cool – but it has some problems. First, the rules for assignment and application will be formalized – this is useful – also it reveals the problems.
Assignment – assignment assigns a result to a variable. Assignment is correct if the type of the result unifies with the type of the variable. The type of the variable is always dominated by the type of the result. This means a polymorphic variable will be erased if say, an object is assigned to its place.
Application – actual arguments are applied to a function. The types of the functions formal arguments have already been decided and are not changed in a global sense.. The types of the actual arguments must unify with the types of the formal arguments. However, if the type of an actual argument dominates a polymorphic type in the formal arguments, all occurrences of the polymorphic type in the resultant type (local to this computation) are changed into the dominating type.
Say for our example, where f is 'Mutant with member tree, where tree is a polymorph called x → x'
If f is applied to a “Mutant with a member tree, where tree is of type Tree”, then locally, the type of f will become “Mutant with a member tree, where tree is of type Tree → Tree”. The result will then be of type “Tree”. However, when f is next used, its type will still be 'Mutant with member tree, where tree is a polymorph called x → x'.
Member lookup – looking up a member of a polymorph dominates the polymorph with a mutant type which possesses this member, and gives the member a new polymorphic type. Looking up a member of a mutant succeeds with the unification of the mutant with a new mutant as before. Looking up the member of an object succeeds if the object has this member. The resultant type, ie, the type of the member lookup, is the type of the member, once the appropriate unification (and perhaps domination ) has been applied.
Function creation – polymorphic arguments are introduced to represent each formal argument. Each formal argument is then dominated by the statements making up the body of the function. The return type is the type of the last statement in the function's body.
Method creation – same as function creation – exception the method imposes domination on the “self” - it can be only be assigned to an object, or within the local scope of that object, where the object unifies with this self.
*Delve has no class macro yet, so here is code which manipulates the meta-object model, allowing for the silly Tree class.
(: Tree (Object.new))
(: Tree.instance_methods (Object.new))
(: Tree.instance_methods.tree
(me ()
((Tree.new))))
(: Tree.new
(me ()
((: instance (Object.new))
(: instance.class self))))
Either that or just use an object
Hmm, I must write a HTML pretty printer for delve...
I've been working on the type system for Delve. Here lie the innovative features of the language.
It would be nice to infer the interface of objects, rather than an exact name. This is a much more Smalltalkish approach - an untyped language considers only the interface - the names are irrelevant. Consider this example: ( Warning, I haven't actually tested the examples - it's of little importance to the thought really )
In Haskell, consider the silly ADT
data Tree = Branch { tree :: Tree }
And the Haskell function, bound to the variable f:
let f = \ b -> tree b
Now say we have a Delve object corrosponding to the Tree adt.
(: Tree (Object.new))
(: Tree.tree
(me ()
(self)))
See here * for an example which constructs a class using the meta-object model.
And the corresponding Delve function, bound to the variable f:
(: f (fu (b) ((b.tree))))
Now with Haskell, the type checker will say: what is the type of 'tree'? It's 'Tree -> Tree'. Therefore f is of type 'Tree -> Tree'
Now what I'm trying to do with Delve is for Delve to say "b is a new mutant object of which I know nothing. However, it must have the method tree. Therefore, the type of f is 'Mutant with method tree, where tree is of type a -> a'
I think that's pretty cool.
To get this magic to work however, I have given Delve four type constructs. Firstly to explain the key concepts of unification and domination.
In Delve, a type is unified with another type if one type can be used in the place of another. This is a separate notion from equality - equality is a subset of unification.
Domination is where one type, (a type which is more concretely defined) actually replaces the other type in the type system. What seems to the type-checker as an initially polymorphic variable can be dominated into becoming a concrete variable in this manner.
So this is a first attempt at describing the various types.
An object: an object is a value of indisputable type.
For unification with another type, the two types must be objects, the objects must have the same name, and the types of both objects members must all be the same ( recursively considering these types ).
A mutant: a mutant is a value of disputable type.
A mutant can be unified with another mutant if the members of the first mutant are a subset of the second mutant of the same name - in that they set of the names of the first mutant is a subset of the second, all also that each of the intersection of the two sets of members unify.
A mutant also unifies with an object, if the above restrictions are met, but an object will dominate a mutant - that is, an object can be used as a function argument where a mutant is expected, but if an object is assigned to a mutant variable - the variable will become an object.
Mutants which unify can be merged, by safely putting the member types of both mutants into one new mutant. The changes must be propagated to any mutants which unified with the old type.
A function: Delve is strict and does not support curried function application, therefore a function can be simply represented by a list of types.
A function unifies with another function only if each of their types unify.
A polymorph: a polymorph will unify with any type, will be dominated by any other type.
The types arranged then in order of concreteness
Object, Function
Mutant
Polymorph
Now for an example, back back to our function:
(: f (fu (b) ((b.tree))))
The type checker will then type check this as follows – try to imagine you are the Delve type checker – this will be your thought process.
A function will be assigned to the variable f.
f will have the type of this function.
Since this function has one argument, the initial type which we will consider will be “Polymorph called a → Polymorph called b” (to use a Haskelly sort of notification”
So open a new scope, and let b be a new polymorph called a.
Now look at the code for this function.
A member of b, called tree, is being called.
So the type of b might be a “Mutant with with a member tree, where tree is a Polymorph called x”
This is ok, because this new type unifies with b's old type, since everything unifies with a polymorph.
Also, this type dominates b's old type. So b's new type is “Mutant with member tree, where tree is a Polymorph called x”
Tree is called of b, which is a polymoph called x.
So the return type of this function is a polymorph called x.
So the type of this function is 'Mutant with member tree, where tree is a polymorph called x → x'
So the type of f is 'Mutant with member tree, where tree is a polymorph called x → x'
Which is what we want. I think this is cool – but it has some problems. First, the rules for assignment and application will be formalized – this is useful – also it reveals the problems.
Assignment – assignment assigns a result to a variable. Assignment is correct if the type of the result unifies with the type of the variable. The type of the variable is always dominated by the type of the result. This means a polymorphic variable will be erased if say, an object is assigned to its place.
Application – actual arguments are applied to a function. The types of the functions formal arguments have already been decided and are not changed in a global sense.. The types of the actual arguments must unify with the types of the formal arguments. However, if the type of an actual argument dominates a polymorphic type in the formal arguments, all occurrences of the polymorphic type in the resultant type (local to this computation) are changed into the dominating type.
Say for our example, where f is 'Mutant with member tree, where tree is a polymorph called x → x'
If f is applied to a “Mutant with a member tree, where tree is of type Tree”, then locally, the type of f will become “Mutant with a member tree, where tree is of type Tree → Tree”. The result will then be of type “Tree”. However, when f is next used, its type will still be 'Mutant with member tree, where tree is a polymorph called x → x'.
Member lookup – looking up a member of a polymorph dominates the polymorph with a mutant type which possesses this member, and gives the member a new polymorphic type. Looking up a member of a mutant succeeds with the unification of the mutant with a new mutant as before. Looking up the member of an object succeeds if the object has this member. The resultant type, ie, the type of the member lookup, is the type of the member, once the appropriate unification (and perhaps domination ) has been applied.
Function creation – polymorphic arguments are introduced to represent each formal argument. Each formal argument is then dominated by the statements making up the body of the function. The return type is the type of the last statement in the function's body.
Method creation – same as function creation – exception the method imposes domination on the “self” - it can be only be assigned to an object, or within the local scope of that object, where the object unifies with this self.
*Delve has no class macro yet, so here is code which manipulates the meta-object model, allowing for the silly Tree class.
(: Tree (Object.new))
(: Tree.instance_methods (Object.new))
(: Tree.instance_methods.tree
(me ()
((Tree.new))))
(: Tree.new
(me ()
((: instance (Object.new))
(: instance.class self))))
Either that or just use an object
Hmm, I must write a HTML pretty printer for delve...
20 August 2009
Writing
I am a semi-being. Not of thought, of drooling adrenaline. I exist for others, and they exist for me, and I see myself through them. But I would exist otherwise, without them but unable to see myself, like a book unwritten, a reality unfurled, a potential undiscovered. And these others, they are books unwritten too, for I cannot see them even now they can see me - but better unwritten, for finality is a tragedy, whether of books or for the dead. And I do hate a morbid party.
Today I saw a brown butterfly against a white wall but for a second it was a white butterfly against a brown wall. I wonder whether I should be taking sanity pills again!
Also I drank beer today, for the first time since the weekend. That was probably the longest I've gone without drink in months.
I started writing a story too. I used to get really flustered with trying to make every paragraph perfect, until I'd re-worked it so much that it was entirely unreadable. I've decided instead to hammer ahead, trying to write something which entertains, rather than worrying about little things like the quality of the prose :)
I'm always amazed by how much shit people talk. Really it's all in the perception. The other day, Lizzie and I were observing the new tap ( we have a new tap ). It is a tubalar breed, and I observed that while dispensing water it wobbles. It was fun watching it wobble. And not only this, it was about as concrete and solid an event as ever has been - it definitely wobbled, there was no question - and it wasn't a bizarre or surprising event. Predictable, deterministic, perfectly causal. Yet it was so funny and trippy and far out. How can such an event occur to two (mostly) sane individuals?
Anyway thinking about such things has prompted this small spate of writing which may continue wearily like the characters within. The other tragic thing, rather than just endings, is that in interesting books, people tend to die, shit, piss, puke ( well those three probably make enjoyable reading ), get raped, burned, stabbed, shot etc. It's such a shame! It's why I like cheesy horror films - mostly you want that sort of shit to happen to the annoying characters contained.
Today I saw a brown butterfly against a white wall but for a second it was a white butterfly against a brown wall. I wonder whether I should be taking sanity pills again!
Also I drank beer today, for the first time since the weekend. That was probably the longest I've gone without drink in months.
I started writing a story too. I used to get really flustered with trying to make every paragraph perfect, until I'd re-worked it so much that it was entirely unreadable. I've decided instead to hammer ahead, trying to write something which entertains, rather than worrying about little things like the quality of the prose :)
I'm always amazed by how much shit people talk. Really it's all in the perception. The other day, Lizzie and I were observing the new tap ( we have a new tap ). It is a tubalar breed, and I observed that while dispensing water it wobbles. It was fun watching it wobble. And not only this, it was about as concrete and solid an event as ever has been - it definitely wobbled, there was no question - and it wasn't a bizarre or surprising event. Predictable, deterministic, perfectly causal. Yet it was so funny and trippy and far out. How can such an event occur to two (mostly) sane individuals?
Anyway thinking about such things has prompted this small spate of writing which may continue wearily like the characters within. The other tragic thing, rather than just endings, is that in interesting books, people tend to die, shit, piss, puke ( well those three probably make enjoyable reading ), get raped, burned, stabbed, shot etc. It's such a shame! It's why I like cheesy horror films - mostly you want that sort of shit to happen to the annoying characters contained.
13 August 2009
Categorical joke
I thought up a joke about category theory,
though it's extremely bad!
There once was a poor endofunctor called Endo. Endo was so poor he
couldn't afford to undertake any more natural transformations, so he had
to borrow money from a loan shark.
But poor old Endo was sooo poor, he couldn't pay the money back! He got
more and more in debt to the loan shark until one day the loan shark
came over to his house to demand his dues.
So the loan-shark banged on the door and shouted "Hey you FUNCTOR! Give
me back my cash!".
"But I can't! I can't give you anything back!", cried the poor
endofunctor, from the upstairs window.
"And why not? You'd better give me the money" the loan shark asked.
"But I can't give you anything" moaned Endo, as he began to weep,
"Because I'm not co-pointed!"
(However, at this point in the joke, the loan shark was no longer needed
so he was garbage collected and Endo lived happily ever after.)
though it's extremely bad!
There once was a poor endofunctor called Endo. Endo was so poor he
couldn't afford to undertake any more natural transformations, so he had
to borrow money from a loan shark.
But poor old Endo was sooo poor, he couldn't pay the money back! He got
more and more in debt to the loan shark until one day the loan shark
came over to his house to demand his dues.
So the loan-shark banged on the door and shouted "Hey you FUNCTOR! Give
me back my cash!".
"But I can't! I can't give you anything back!", cried the poor
endofunctor, from the upstairs window.
"And why not? You'd better give me the money" the loan shark asked.
"But I can't give you anything" moaned Endo, as he began to weep,
"Because I'm not co-pointed!"
(However, at this point in the joke, the loan shark was no longer needed
so he was garbage collected and Endo lived happily ever after.)
11 August 2009
Delve core
(Posted to the Haskell-Cafe mailing list)
Delve is a new programming language intended to bring the benefits of static type checking and functional programming to object-oriented design and development. It is an impure, eager language (Yes I can hear the groans of woe and cries for sanity already!)
Currently Delve supports:
Higher-order functions/first class functions
Anonymous functions
Lexical closures
First class continuations
Tail-call optimization
A meta-object model (classes are objects)
S-Expression based syntax.
Embedded Haskell expressions within Delve.
What it doesn't have:
Lots and lots!
Basically what I have is an de-sugared, untyped core language. An analogy could be made with Haskell core files.
I'm going to be working on the type system for next little while (I have a stack of paper and a pen right here!). Once that is implemented we'll see where to go.
Please see the TUTORIAL file included in the source for a brief outlook on Delve's syntax, semantics and planned type system.
However! If you're looking for a new project, and especially if you are an undergraduate, then I think Delve would be a good choice for these reasons:
It's written in a hybrid of Haskell and itself.
It's currently undergoing active development (by me and some pals). You're not going to be lonely!
It's quite powerful already, without too many lines of code (it's now just about 5.5KLOC - it's no goliath! )
It's a programming language: name a compiler which isn't a cool piece of tech! Ok, maybe you can but still, it's a chance to work on something non-trivial and interesting.
Quite honestly, I'm a bit of a fool - I am a math undergrad! So don't you feel foolish about getting involved if you're not a professorial chap! If you feel like it, get involved in the design, and push me the patches :)
It does require lots of love though! It was all hacked out rather quickly :)
Executables which Delve provides:
edc -- The Elgin Delve Compiler
The Elgin Delve Compiler currently supports two backends - the first to a bytecode format for execution on edvm, and the second is to a Haskell source code representation of Delve bytecode. This allows Haskell to be embedded within Delve, for the express purpose of extending and building edvm. edc is written in Haskell (GHC).
edvm -- The Elgin Delve Virtual Machine
The Elgin Delve Virtual Machine executes Delve bytecode files (.dcode format). Since part of the VM is actually driven by Delve bytecode, edvm can be considered a hybrid of Delve and Haskell (again GHC).
Delve continues the grand tradition of naming compilers after Scottish Cities (no, Elgin does not have a university).
Delve is released under the terms of the GNU GPLv3.
For more information on Delve, check my blog at http://killersmurf.blogspot.com/ and the Delve repository at http://github.com/elginer/Delve/
Delve is a new programming language intended to bring the benefits of static type checking and functional programming to object-oriented design and development. It is an impure, eager language (Yes I can hear the groans of woe and cries for sanity already!)
Currently Delve supports:
Higher-order functions/first class functions
Anonymous functions
Lexical closures
First class continuations
Tail-call optimization
A meta-object model (classes are objects)
S-Expression based syntax.
Embedded Haskell expressions within Delve.
What it doesn't have:
Lots and lots!
Basically what I have is an de-sugared, untyped core language. An analogy could be made with Haskell core files.
I'm going to be working on the type system for next little while (I have a stack of paper and a pen right here!). Once that is implemented we'll see where to go.
Please see the TUTORIAL file included in the source for a brief outlook on Delve's syntax, semantics and planned type system.
However! If you're looking for a new project, and especially if you are an undergraduate, then I think Delve would be a good choice for these reasons:
It's written in a hybrid of Haskell and itself.
It's currently undergoing active development (by me and some pals). You're not going to be lonely!
It's quite powerful already, without too many lines of code (it's now just about 5.5KLOC - it's no goliath! )
It's a programming language: name a compiler which isn't a cool piece of tech! Ok, maybe you can but still, it's a chance to work on something non-trivial and interesting.
Quite honestly, I'm a bit of a fool - I am a math undergrad! So don't you feel foolish about getting involved if you're not a professorial chap! If you feel like it, get involved in the design, and push me the patches :)
It does require lots of love though! It was all hacked out rather quickly :)
Executables which Delve provides:
edc -- The Elgin Delve Compiler
The Elgin Delve Compiler currently supports two backends - the first to a bytecode format for execution on edvm, and the second is to a Haskell source code representation of Delve bytecode. This allows Haskell to be embedded within Delve, for the express purpose of extending and building edvm. edc is written in Haskell (GHC).
edvm -- The Elgin Delve Virtual Machine
The Elgin Delve Virtual Machine executes Delve bytecode files (.dcode format). Since part of the VM is actually driven by Delve bytecode, edvm can be considered a hybrid of Delve and Haskell (again GHC).
Delve continues the grand tradition of naming compilers after Scottish Cities (no, Elgin does not have a university).
Delve is released under the terms of the GNU GPLv3.
For more information on Delve, check my blog at http://killersmurf.blogspot.com/ and the Delve repository at http://github.com/elginer/Delve/
6 August 2009
Maintenance
Today I received two emails. The first one asked for a much needed feature in tagsoup-parsec - allowing user-supplied state, which I added.
However, the other email reported the fact that shpider no longer worked.
Shpider uses curl for a backend. The funny thing about curl is that it only writes cookies to a file when its cleanup function is called, rather than when it recieves them. However, in the original curl-bindings, this function was only called on garbage collection, through a foreign pointer finalizer. This resulted in some weird behaviour, like cookies being written at unexpected times. This is crippling if your program logs in to a website and then expects a cookie to be written to hold the session key.
So I forked the library to work on a solution. The obvious one is to call the finalizer manually, which worked before, but seems to crash now ( new GHC? ), so now I have to handle my own garbage collection, in order to get deterministic behaviour.
I really should put shpider in a git repository, to let others peer at it more effectively.
In other news, I hope in a couple of days I shall be able to publish the first component of a cool new piece of tech.... ooooh, the suspense.
However, the other email reported the fact that shpider no longer worked.
Shpider uses curl for a backend. The funny thing about curl is that it only writes cookies to a file when its cleanup function is called, rather than when it recieves them. However, in the original curl-bindings, this function was only called on garbage collection, through a foreign pointer finalizer. This resulted in some weird behaviour, like cookies being written at unexpected times. This is crippling if your program logs in to a website and then expects a cookie to be written to hold the session key.
So I forked the library to work on a solution. The obvious one is to call the finalizer manually, which worked before, but seems to crash now ( new GHC? ), so now I have to handle my own garbage collection, in order to get deterministic behaviour.
I really should put shpider in a git repository, to let others peer at it more effectively.
In other news, I hope in a couple of days I shall be able to publish the first component of a cool new piece of tech.... ooooh, the suspense.
Subscribe to:
Posts (Atom)