Copperbox revision 522.
Some on the new implementations have now been pieced together.
Tuesday, March 31, 2009
Monday, March 30, 2009
HNotate
Copperbox revision 520.
Disappointingly, now that I'm reviewing HNotate, most of the code seems terribly complex. I was hope that only some of the code was far to complicated.
I've redone the bar splitting and beam grouping algorithms, though they aren't incorporated into the main code yet.
Disappointingly, now that I'm reviewing HNotate, most of the code seems terribly complex. I was hope that only some of the code was far to complicated.
I've redone the bar splitting and beam grouping algorithms, though they aren't incorporated into the main code yet.
Sunday, March 29, 2009
anaMap and accumMapL
There has been a very long thread recently on Haskell-Cafe -
- 'about Haskell code written to be "too smart"':
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058475.html
As the thread was running the idea of partitions (aka takeList) seemed like an unfold to me, though I couldn't work out a nice formulation. Here is the best 'natural' unfold I could get. It's messier than a usual anamorphism because the state has to be doubled - the state is both the list of lengths and the remaining stream:
Prompted by the suggesting that mapAccumL was the natural way to do it, Claus Reinke noted that that the arguments to mapAccumL were the wrong way round:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058689.html
Here is a version accumMapL which puts the state second in the result tuple - which is the way unfoldr (anamorphism) does it:
Since mapAccumL (accumMapL) is like a fusion of map and foldl, it made me wonder what a a combination of map and unfoldr would give me as I was still keen on my anamorphism, maybe anaMap isn't the best name, but I think this function is the analogue:
And here is takeList:
Finally here's the GHC transcript, it passes the Hartman test:
By the way, I do like the 'specs' (aka glasses) combinator to compose a binary function and a ternary one. The function anapart above, used the double composition idiom which now seems very common - here's the line in question:
Here is is with 'specs':
Specs has a nod to ML which uses letter o for function composition, plus the '2 o's' seem like a nice visual pun to suggest doubling going on in the composition:
Of course higher arities can also be accommodated:
etc.
- 'about Haskell code written to be "too smart"':
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058475.html
As the thread was running the idea of partitions (aka takeList) seemed like an unfold to me, though I couldn't work out a nice formulation. Here is the best 'natural' unfold I could get. It's messier than a usual anamorphism because the state has to be doubled - the state is both the list of lengths and the remaining stream:
anapart :: [Int] -> [a] -> [[a]]
anapart = (unfoldr phi .) . (,) where
phi ([],_) = Nothing
phi (i:is,xs) = let (l,r) = splitAt i xs in Just (l,(is,r))
Prompted by the suggesting that mapAccumL was the natural way to do it, Claus Reinke noted that that the arguments to mapAccumL were the wrong way round:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058689.html
Here is a version accumMapL which puts the state second in the result tuple - which is the way unfoldr (anamorphism) does it:
accumMapL :: (a -> st -> (b, st)) -> st -> [a] -> ([b], st)
accumMapL _ s [] = ([],s)
accumMapL f s (x:xs) = (y:ys,s'')
where (y, s') = f x s
(ys,s'') = accumMapL f s' xs
Since mapAccumL (accumMapL) is like a fusion of map and foldl, it made me wonder what a a combination of map and unfoldr would give me as I was still keen on my anamorphism, maybe anaMap isn't the best name, but I think this function is the analogue:
-- anaMap is to unfoldr, what accumMapL is to foldl
-- Note - we can signal exhaustion early by the Maybe type.
anaMap :: (a -> st -> Maybe (b,st)) -> st -> [a] -> ([b],st)
anaMap f s [] = ([],s)
anaMap f s (x:xs) = case (f x s) of
Nothing -> ([],s)
Just (a,st) -> (a:as,st') where (as,st') = anaMap f st xs
And here is takeList:
takeListAM :: [Int] -> [t] -> [[t]]
takeListAM ns xs = fst $ anaMap fn xs ns where
fn _ [] = Nothing
fn i ys = Just $ splitAt i ys
Finally here's the GHC transcript, it passes the Hartman test:
*Main> main
[[1,2,3],[4,5,6,7,8,9,10]]
[[1,2,3],[4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20,21],[22,23,24,25,26,27,28,29,30,31,32,33,34
,35,36]]
1000000
*Main> null $ takeListAM [1] undefined
*** Exception: Prelude.undefined
*Main> takeListAM [0] []
[]
*Main>
By the way, I do like the 'specs' (aka glasses) combinator to compose a binary function and a ternary one. The function anapart above, used the double composition idiom which now seems very common - here's the line in question:
anapart = (unfoldr phi .) . (,) where
...
Here is is with 'specs':
anapart = unfoldr phi `oo` (,) where
...
Specs has a nod to ML which uses letter o for function composition, plus the '2 o's' seem like a nice visual pun to suggest doubling going on in the composition:
oo :: (c -> d) -> (a -> b -> c) -> a -> b -> d
oo f g = (f .) . g
Of course higher arities can also be accommodated:
ooo :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e
ooo f g = ((f .) .) . g
etc.
Saturday, March 28, 2009
HNotate
Copperbox revision 519.
Time for some work on HNotate...
I have a new scheme the uses CPS to build documents and allow the environment to be changed at different levels of nesting. Essentially it is Danvy's printf but with state passed around as an extra argument within the CPS and Doc as the underlying type rather than String. There are two new operations local to go to a new nesting level and update to change the state within the current nesting level.
Time for some work on HNotate...
I have a new scheme the uses CPS to build documents and allow the environment to be changed at different levels of nesting. Essentially it is Danvy's printf but with state passed around as an extra argument within the CPS and Doc as the underlying type rather than String. There are two new operations local to go to a new nesting level and update to change the state within the current nesting level.
Thursday, March 26, 2009
HMinCaml
Copperbox revision 518.
More work on the W algorithm doodle. I think the 'W machine' version works now, but its rather messy.
More work on the W algorithm doodle. I think the 'W machine' version works now, but its rather messy.
Wednesday, March 25, 2009
HMinCaml
Copperbox revision 517.
More type inference doodles, this one inspired by Kuan and MacQueen's paper from ML'07.
More type inference doodles, this one inspired by Kuan and MacQueen's paper from ML'07.
Tuesday, March 24, 2009
HMinCaml
Copperbox revision 516.
More work on type inference, though I'm not getting very far. I've added another doodle that infers a much smaller subset of ML than MinCaml, but this has problems with letrec or maybe app (or maybe both).
More work on type inference, though I'm not getting very far. I've added another doodle that infers a much smaller subset of ML than MinCaml, but this has problems with letrec or maybe app (or maybe both).
Monday, March 23, 2009
HMinCaml
Copperbox revision 515.
I've added a pretty printer for the top-level syntax, so I can check that I'm parsing source files correctly.
I've added a pretty printer for the top-level syntax, so I can check that I'm parsing source files correctly.
Sunday, March 22, 2009
HMinCaml
Copperbox revision 514.
I've put my unification code from the type inference sketch into HMinCaml, though I suspect it will be wiser to translate the original ML code than to do more work integrating my type inference code.
I've put my unification code from the type inference sketch into HMinCaml, though I suspect it will be wiser to translate the original ML code than to do more work integrating my type inference code.
HMinCaml
Copperbox revision 513.
Fixed the bug in the attribute grammar sketch of algorithm W.
Worryingly perhaps, I'm not sure why the solution works. The App node now manually increments the counter of its child node (arg) rather than the its own counter. This pattern was in course notes from Utrecht, so its clearly valid but mysterious to me.
Fixed the bug in the attribute grammar sketch of algorithm W.
Worryingly perhaps, I'm not sure why the solution works. The App node now manually increments the counter of its child node (arg) rather than the its own counter. This pattern was in course notes from Utrecht, so its clearly valid but mysterious to me.
HMinCaml
Copperbox revision 512.
I've added a monadic version of algorithm W which works, but I haven't found the bug in the attribute grammar version. As the monadic version is a direct translation of the attribute grammar, it points to the (implicit) copy rules in the attribute grammar not working the way I expect.
I've added a monadic version of algorithm W which works, but I haven't found the bug in the attribute grammar version. As the monadic version is a direct translation of the attribute grammar, it points to the (implicit) copy rules in the attribute grammar not working the way I expect.
HMinCaml
Copperbox revision 511.
I've implemented a sketch of the type inference algorithm W (a sketch meaning that it isn't integrated with HMinCaml and works on a smaller set of datatypes).
It's largely an attribute grammar version of the code in Martin Grabmuller's "Algorithm W Step by Step", with some modifications so the naming conventions are closer to the presentation in "Generalizing Hindley-Milner Type Inference Algorithms". Unfortunately it seems to have a bug at present, as it fails one of the test cases from "... Step by Step" which it should pass.
I've implemented a sketch of the type inference algorithm W (a sketch meaning that it isn't integrated with HMinCaml and works on a smaller set of datatypes).
It's largely an attribute grammar version of the code in Martin Grabmuller's "Algorithm W Step by Step", with some modifications so the naming conventions are closer to the presentation in "Generalizing Hindley-Milner Type Inference Algorithms". Unfortunately it seems to have a bug at present, as it fails one of the test cases from "... Step by Step" which it should pass.
Friday, March 20, 2009
HMinCaml
Copperbox revision 510.
Major clean up. All the AST refinements are now in their own folder along with attribute grammars for each transformation.
Major clean up. All the AST refinements are now in their own folder along with attribute grammars for each transformation.
Thursday, March 19, 2009
Wednesday, March 18, 2009
HMinCaml
Copperbox revision 507.
HMinCaml now uses UUAG. I've only changed alpha renaming to use UUAG, so converting the work done so far to attribute grammars is going to be challenging, then there are the modules that I hadn't really made a start on.
Maybe I'll regret this, but I hope that once I've written it with an attribute grammar it will be more convenient to then change to the work to a different little language.
HMinCaml now uses UUAG. I've only changed alpha renaming to use UUAG, so converting the work done so far to attribute grammars is going to be challenging, then there are the modules that I hadn't really made a start on.
Maybe I'll regret this, but I hope that once I've written it with an attribute grammar it will be more convenient to then change to the work to a different little language.
Tuesday, March 17, 2009
HMinCaml
Copperbox revision 506.
I've been doodling with the Kure library (Stratego-style travervals). This commit is a alternative version of HMinCaml's free variables module using Kure.
I've been doodling with the Kure library (Stratego-style travervals). This commit is a alternative version of HMinCaml's free variables module using Kure.
Thursday, March 12, 2009
ZBitmap
Copperbox revision 505.
I've added an alternative version of ZBitmap (BmpAdaptor) that just exposes a Chalkboard interface - readBMP and writeBMP.
There is still some problems with array addressing though, that are making it crash. Much as I like Haskell, 2D arrays were never this hard to use effectively in C!
I've added an alternative version of ZBitmap (BmpAdaptor) that just exposes a Chalkboard interface - readBMP and writeBMP.
There is still some problems with array addressing though, that are making it crash. Much as I like Haskell, 2D arrays were never this hard to use effectively in C!
Tuesday, March 10, 2009
ZBitmap
Copperbox revision 504.
ZBitmap now has an adaptor to Andy Gill's ChalkBoard library, it allows ChalkBoard to read and write *.bmp bitmaps.
Example above.
ZBitmap
Copperbox revision 503.
I've implemented the pixel data writing as a array operation rather than a ShowS style bit of function composition. Hopefully this optimizes things if only slightly - I don't envisage using ZBitmap with huge bitmaps where it might make a real difference. The previous solution did seem a bit lacking in style.
I've implemented the pixel data writing as a array operation rather than a ShowS style bit of function composition. Hopefully this optimizes things if only slightly - I don't envisage using ZBitmap with huge bitmaps where it might make a real difference. The previous solution did seem a bit lacking in style.
ZBitmap
Copperbox revision 502.
Writing bitmaps with palettes now seems to work. So that leaves writing arbitrary buffers to do...
Writing bitmaps with palettes now seems to work. So that leaves writing arbitrary buffers to do...
ZBitmap
Copperbox revision 501.
Work towards seeing why writing fails. Bmp headers can now be parsed without their payload, so you can at least look at the headers of invalid files rather than unhelpfully being told a parse error has occured.
Work towards seeing why writing fails. Bmp headers can now be parsed without their payload, so you can at least look at the headers of invalid files rather than unhelpfully being told a parse error has occured.
Monday, March 9, 2009
ZBitmap
Copperbox revision 500!
Writing bmp files is re-enabled, though there is a bug where the output bitmap isn't the same as the input bitmap. As ZBitmap doesn't do any translation it should be. It does seem to work okay for 24 bit colour, but not for other ones.
Also this is just writing bmp files. There is no code yet to enable writing an arbitrary buffer containing bitmap data to a bmp file, which is really the most important bit.
Writing bmp files is re-enabled, though there is a bug where the output bitmap isn't the same as the input bitmap. As ZBitmap doesn't do any translation it should be. It does seem to work okay for 24 bit colour, but not for other ones.
Also this is just writing bmp files. There is no code yet to enable writing an arbitrary buffer containing bitmap data to a bmp file, which is really the most important bit.
ZBitmap
Copperbox revision 499.
Some tidying up before I attempt to re-integrate the WriteBmp module.
Some tidying up before I attempt to re-integrate the WriteBmp module.
Sunday, March 8, 2009
ZBitmap
Copperbox revision 498.
This revision has a new approach to handling index overlays into the array of bitmap data. Different bitmap resolutions have different size requirements for a pixel - for a mono bitmap its a bit, for a 16 bit bitmap it is 3 x 5 bits, etc. I want to keep this data intact rather than marshaling to an unboxed tuples to represent RGB colours, so I need a scheme to allow different indexing according to resolution. Today's code implements a scheme that I hope will be suitable.
This revision has a new approach to handling index overlays into the array of bitmap data. Different bitmap resolutions have different size requirements for a pixel - for a mono bitmap its a bit, for a 16 bit bitmap it is 3 x 5 bits, etc. I want to keep this data intact rather than marshaling to an unboxed tuples to represent RGB colours, so I need a scheme to allow different indexing according to resolution. Today's code implements a scheme that I hope will be suitable.
Thursday, March 5, 2009
Hawa
Copperbox revision 497.
Some prototypes for PostScript output combinators. The (mostly-) typed version TypedPostScript almost has a nice type tracking scheme patterned after Chris Okasaki's postfix combinator paper. Unfortunately PostScript has some operators that do nefarious things to the stack (copy, index, roll, cleartomark) and these will be hard to type without type-level numerals or some more advanced trick. The typed combinators have these operators (so they can generate appropriate PostScript) but they don't track the state change they cause.
The other serious short-coming of the prototypes is that they do nothing about pretty-printing, so the output is just a linear sequence.
Some prototypes for PostScript output combinators. The (mostly-) typed version TypedPostScript almost has a nice type tracking scheme patterned after Chris Okasaki's postfix combinator paper. Unfortunately PostScript has some operators that do nefarious things to the stack (copy, index, roll, cleartomark) and these will be hard to type without type-level numerals or some more advanced trick. The typed combinators have these operators (so they can generate appropriate PostScript) but they don't track the state change they cause.
The other serious short-coming of the prototypes is that they do nothing about pretty-printing, so the output is just a linear sequence.
Wednesday, March 4, 2009
Tuesday, March 3, 2009
HMinCaml
Copperbox revision 495.
All the significant modules are now in place, but a lot of the code is unimplemented. Plus there is quite a bit of code that pretends to be pure, that is due to go in the compiler monad.
All the significant modules are now in place, but a lot of the code is unimplemented. Plus there is quite a bit of code that pretends to be pure, that is due to go in the compiler monad.
Monday, March 2, 2009
HMinCaml
Copperbox revision 491.
I completely overlooked K-normal form yesterday when I was looking at alpha and beta reduction. In K-normal form expressions are represented by an identifier and the identifier is used to index the expression in the map. Alpha-conversion and Beta-reduction modules are now implemented.
I completely overlooked K-normal form yesterday when I was looking at alpha and beta reduction. In K-normal form expressions are represented by an identifier and the identifier is used to index the expression in the map. Alpha-conversion and Beta-reduction modules are now implemented.
Sunday, March 1, 2009
HMinCaml
Copperbox revision 490.
First look at translating the alpha-conversion and beta-reduction modules.
Unfortunately it looks like I need an equivalent of pointer equality, so I'm going to have to do some thinking about this.
First look at translating the alpha-conversion and beta-reduction modules.
Unfortunately it looks like I need an equivalent of pointer equality, so I'm going to have to do some thinking about this.
Subscribe to:
Posts (Atom)
About Me
- Stephen Tetley
- Disambiguating biog as there are a few Stephen Tetley's in the world. I'm neither a cage fighter or yachtsman. I studied Fine Art in the nineties (foundation Bradford 1992, degree Cheltenham 1992 - 95) then Computing part-time at Leeds Met graduating in 2003. I'm the Stephen Tetley on Haskell Cafe and Stackoverflow.