making translation from imperative code

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

making translation from imperative code

Michael Mossey
I'm translating a Python program into Haskell, and running into a
problem---a type of code where I don't know how to make the conceptual
shift.

The Python code does a graphical layout of a music score. There is a
loop in which it add items (chords, symbols, text, etc.) one at a time,
moving to the right, until it reaches the end of the line. So in typical
imperative code, we have a bunch of loop state, such as

    - xpos of last chord or symbol placed
    - time of last chord or symbol placed
    - several StaffData objects, each containing the symbols that went
      on that particular staff
    - a cache of miscellaneous information about each symbol for later
      reference

So imperative code is pretty simple: loop, and each time update the
state. Much of this state consists of lists  to which symbols are added
once per loop.

I'm not sure how to conceive of this problem in Haskell. Without using
mutable variables, I would have to "rebuild" the state on each loop. I
can do that, but I don't want to see an ugly proliferation of variables.

I would like to encapsulate the state in a single object so I can pass
it around as a single variable, like

LoopState = LoopState {
      lastXPos :: Int,
      lastTime :: Double,
      staffDataLists :: [ ( String, StaffData ) ],
      chunkCache :: [ ( Double, Chunk ) ]
      }

So lets say I have an instance of this call x. Let's say I want to
create y, by "updating" lastXPos. Do I have to do something like this:

newLastXPos = 25
y = LoopState ( newLastXPos, lastTime x, staffDataLists x,
                 chunkCache x )

Obviously this is verbose compared to an imperative language in which
one would say:
newLastPos = 25
x.setLastXPos( newLastXPos )

I am aware that Haskell provides some mutable structures, but part of
what drew me to Haskell was the benefit of avoiding mutable data
(reducing bugs and making it easier to reason about my program's
behavior). Are there any shortcuts for doing things like the above?

Thanks,
Mike


Reply | Threaded
Open this post in threaded view
|

making translation from imperative code

Magnus Therning
On Tue, Mar 31, 2009 at 1:54 PM, Michael Mossey <[hidden email]> wrote:

> I'm translating a Python program into Haskell, and running into a
> problem---a type of code where I don't know how to make the conceptual
> shift.
>
> The Python code does a graphical layout of a music score. There is a loop in
> which it add items (chords, symbols, text, etc.) one at a time, moving to
> the right, until it reaches the end of the line. So in typical imperative
> code, we have a bunch of loop state, such as
>
> ? - xpos of last chord or symbol placed
> ? - time of last chord or symbol placed
> ? - several StaffData objects, each containing the symbols that went
> ? ? on that particular staff
> ? - a cache of miscellaneous information about each symbol for later
> ? ? reference
>
> So imperative code is pretty simple: loop, and each time update the state.
> Much of this state consists of lists ?to which symbols are added once per
> loop.
>
> I'm not sure how to conceive of this problem in Haskell. Without using
> mutable variables, I would have to "rebuild" the state on each loop. I can
> do that, but I don't want to see an ugly proliferation of variables.
>
> I would like to encapsulate the state in a single object so I can pass it
> around as a single variable, like
>
> LoopState = LoopState {
> ? ? lastXPos :: Int,
> ? ? lastTime :: Double,
> ? ? staffDataLists :: [ ( String, StaffData ) ],
> ? ? chunkCache :: [ ( Double, Chunk ) ]
> ? ? }
>
> So lets say I have an instance of this call x. Let's say I want to create y,
> by "updating" lastXPos. Do I have to do something like this:
>
> newLastXPos = 25
> y = LoopState ( newLastXPos, lastTime x, staffDataLists x,
> ? ? ? ? ? ? ? ?chunkCache x )
>
> Obviously this is verbose compared to an imperative language in which one
> would say:
> newLastPos = 25
> x.setLastXPos( newLastXPos )
>
> I am aware that Haskell provides some mutable structures, but part of what
> drew me to Haskell was the benefit of avoiding mutable data (reducing bugs
> and making it easier to reason about my program's behavior). Are there any
> shortcuts for doing things like the above?

Have you considered the sort of named updates like the following?

  data Foo = Foo { i :: Int, j :: Int } deriving (Show)

Loading that into ghci you can do things like this:

*Foo> let f = Foo 25 25
*Foo> f
Foo {i = 25, j = 25}
*Foo> f { i = 35 }
Foo {i = 35, j = 25}

That might be more to your liking.

/M

--
Magnus Therning                        (OpenPGP: 0xAB4DFBA4)
magnus?therning?org          Jabber: magnus?therning?org
http://therning.org/magnus         identi.ca|twitter: magthe
Reply | Threaded
Open this post in threaded view
|

Re: making translation from imperative code

Heinrich Apfelmus
In reply to this post by Michael Mossey
Michael Mossey wrote:

> I'm translating a Python program into Haskell, and running into a
> problem---a type of code where I don't know how to make the conceptual
> shift.
>
> The Python code does a graphical layout of a music score. There is a
> loop in which it add items (chords, symbols, text, etc.) one at a time,
> moving to the right, until it reaches the end of the line. So in typical
> imperative code, we have a bunch of loop state, such as
>
>    - xpos of last chord or symbol placed
>    - time of last chord or symbol placed
>    - several StaffData objects, each containing the symbols that went
>      on that particular staff
>    - a cache of miscellaneous information about each symbol for later
>      reference
>
> So imperative code is pretty simple: loop, and each time update the
> state. Much of this state consists of lists  to which symbols are added
> once per loop.

Can you elaborate on what exactly the algorithm is doing? Does it just
emit notes/chords/symbols at given positions or does it also try to
arrange them nicely? And most importantly, "where" does it emit them to,
i.e. what's the resulting data structure?

So far, the problem looks like a basic fold to me.


Regards,
apfelmus

--
http://apfelmus.nfshost.com

Reply | Threaded
Open this post in threaded view
|

Re: making translation from imperative code

Michael Mossey


Heinrich Apfelmus wrote:
> Michael Mossey wrote:
>> I'm translating a Python program into Haskell, and running into a
>> problem---a type of code where I don't know how to make the conceptual

...
>
> Can you elaborate on what exactly the algorithm is doing? Does it just
> emit notes/chords/symbols at given positions or does it also try to
> arrange them nicely? And most importantly, "where" does it emit them to,
> i.e. what's the resulting data structure?
>
> So far, the problem looks like a basic fold to me.

Here is some Haskell code that explains the problem in
more detail.

-------------------------------------------------------------
-------------------------------------------------------------
--                 layoutSystem
--------------------------------------------------------------
--------------------------------------------------------------

-- A "system" in musical typesetting terminology is a
-- collection of staves that are all played simultaneously;
-- that is, they are aligned in time and space. This is a
-- simple layout algorithm that uses the concept of
-- "chunk"--- a chunk is a set of events (notes, dynamic
-- changes, etc.) that occur on a subset of the staves, and
-- occur at the same time and therefore need to be aligned
-- vertically. Each item has a width and items must be
-- placed so they don't overlap. (There is no attempt to
-- align them in an aesthetically pleasing way; they simply
-- must not collide.)
--
-- We presume that something called a "score" exists, which
-- is an object representing the underlying music data, from
-- which can be extracted a list of chunks, each
-- associated with the time at which it is played. We
-- don't show the structure of a score here; we just
-- assume that we can operate on a score via two
-- functions:
--
-- A function to grab a chunk:
--   scoreGetChunkData :: Score -> Time -> ChunkData
-- A function to get time of next chunk:
--   scoreNextTime :: Score -> Time -> Time
--
-- This basic structure of this algorithm is a loop with state.
-- Here's the state.
--  'time' :: Double -- is the time of next chunk to layout.
--  'staffLayouts' :: [( String, StaffLayout)] --  is an
--     association list of staff names and StaffLayout
--     objects. Each StaffLayout object accumulates the chunks
--     that belong to that staff.
--  'val' :: Int -- This is the next x-position that is
--                   available for placing a new chunk (this
--                   is an abbreviation for vertical
--                   alignment line).
--  'chunkDataMem' This is a cache or memory of all chunks
--                   we have encountered in this system, for
--                   lookup later.
data SystemLayoutState = SystemLayoutState
   { time                 :: Double,
     staffLayouts         :: [ ( String, StaffLayout ) ],
     val                  :: Int,
     chunkDataMem         :: [ ChunkData ]
   }


layoutSystem Double -> Score -> Int -> Config -> SystemLayoutState
layoutSystem firstTime score rightBorder config =
    -- Work is done by helper function layoutSystem',
    -- after giving it the initial state.
    layoutSystem' initialState
          -- Construct initial state.
    where initialState = SystemLayoutState
            { time = firstTime,
              staffLayouts = [],
              val =  getConfig config "prefixWidth",
              storedChunkData = [] }
          -- Define the helper function layoutSystem'
          layoutSystem' :: SystemLayoutState -> SystemLayoutState
          layoutSystem' state =
                -- Get ChunkData from the score at the time
                -- associated with the current state.
            let chunkData = scoreGetChunkData score (time state)
                -- Call 'incorporateChunkData' to try to add
                -- it to the score.  This will return a
                -- tuple, the first member being the status
                -- (True means we can add no more chunks
                -- because we ran out of horizontal space)
                -- and the second is updated state.
                case
                  incorporateChunkData state chunkData rightBorder
                of
                  ( True,  state' ) -> state'
                  ( False, state' ) -> tryAgain state'
          -- We separate the definition of tryAgain just to make
          -- the structure of this whole function a little
          -- clearer. tryAgain asks the score for the next
          -- time at which a chunk exists. In the case there
          -- *are no more* chunks, it terminates the
          -- recursion, while also modifying the state in
          -- some way to communicate that the recursion
          -- terminated *because of running out of chunks*
          -- instead of running out of horizontal
          -- space. Otherwise it calls back to layoutSystem'.
          tryAgain state =
            case scoreNextTime score (time state) of
             -1 -> indicateNoMoreChunks state
              t -> layoutSystem' (setTime state t)
Reply | Threaded
Open this post in threaded view
|

Re: making translation from imperative code

Heinrich Apfelmus
Michael Mossey wrote:

> Heinrich Apfelmus wrote:
>>
>> Can you elaborate on what exactly the algorithm is doing? Does it just
>> emit notes/chords/symbols at given positions or does it also try to
>> arrange them nicely? And most importantly, "where" does it emit them to,
>> i.e. what's the resulting data structure?
>>
>> So far, the problem looks like a basic fold to me.
>
> Here is some Haskell code that explains the problem in
> more detail.
> [...]

Thanks for the elaboration.

I think the code doesn't separate concerns very well; mixing information
about widths and times, page size and the recursion itself into one big
gnarl.

Also, there is one important issue, namely returning a special value
like -1 as error code in

>          tryAgain state =
>            case scoreNextTime score (time state) of
>             -1 -> indicateNoMoreChunks state
>              t -> layoutSystem' (setTime state t)

Don't do this, use  Maybe  instead

    tryAgain state = case scoreNextTime score (time state) of
        Nothing -> indicateNoMoreChunks state
        Just t  -> layoutSystem' (state { time = t })

where  Nothing  indicates failure and  Just  success.


Back to the gnarl in general, I still don't have a good grasp on the
problem domain, which is key to structuring the algorithm. Therefore,
I'll expand on toy model and you tell me how it differs from the real thing.

The model is this: we are given several lists of notes (f.i. a piano
part and a vocal line) where each note is annotated with the time it is
to be played at. We abstract away the fact that we are dealing with
musical notes and simply consider a list of *events*

    type Time     = Integer
    type Events a = [(Time, a)]

with the invariant that the timestamps are (strictly) increasing:

    valid :: Events a -> Bool
    valid xs = all $ zipWith (\(t1,_) (t2,_) -> t1 < t2) xs (drop 1 xs)

Now, the toy task is to merge several lists of similar events into one
big list that is ordered by time as well.

    merge :: [Events a] -> Events [a]

Since some events may now occur simultaneously, the events of the
results are actually lists of "primitive" events.

One possibility for implementing  merge  is to start with a function to
merge two event lists

    merge2 :: Events [a] -> Events [a] -> Events [a]
    merge2 []             ys             = ys
    merge2 xs             []             = xs
    merge2 xs@((tx,x):xt) ys@((ty,y):yt) = case compare tx ty of
          LT -> (tx,x   ) : merge2 xt ys
          EQ -> (tx,x++y) : merge2 xt yt
          GT -> (ty,   y) : merge2 xs yt

and to apply it several times

    merge = foldr merge2 [] . map lift
        where lift = map $ \(t,x) -> (t,[x])


Another possibility is to simply concatenate everything first and then
sort by time

    merge = map (\((t,x):xs) -> (t,x:map snd xs))
          . groupBy ((==) `on` fst)
          . sortBy (comparing fst)
          . concat


The code above can be made more readable by choosing nice names like

   time  = fst
   event = snd

or avoiding pairs altogether and implementing these names as record
fields. Also, the (&&&) combinator from  Control.Arrow  is very handy.

   merge = map (time . head &&& map event)
         . groupBy ((==) `on` time)
         . sortBy  (comparing time)
         . concat


I hope this gives you a few ideas to think about. How does this toy
model differ from the real thing?


Regards,
apfelmus


PS: If some parts of my example code give you trouble, it's probably
fastest to ask around on the #haskell IRC channel.

--
http://apfelmus.nfshost.com

Reply | Threaded
Open this post in threaded view
|

Re: making translation from imperative code

Michael Mossey


Heinrich Apfelmus wrote:

> Michael Mossey wrote:
>> Heinrich Apfelmus wrote:
>>> Can you elaborate on what exactly the algorithm is doing? Does it just
>>> emit notes/chords/symbols at given positions or does it also try to
>>> arrange them nicely? And most importantly, "where" does it emit them to,
>>> i.e. what's the resulting data structure?
>>>
>>> So far, the problem looks like a basic fold to me.
>> Here is some Haskell code that explains the problem in
>> more detail.
>> [...]
>
> Thanks for the elaboration.
>
> I think the code doesn't separate concerns very well; mixing information
> about widths and times, page size and the recursion itself into one big
> gnarl.
>
> Also, there is one important issue, namely returning a special value
> like -1 as error code in
>
>>          tryAgain state =
>>            case scoreNextTime score (time state) of
>>             -1 -> indicateNoMoreChunks state
>>              t -> layoutSystem' (setTime state t)
>
> Don't do this, use  Maybe  instead
>
>     tryAgain state = case scoreNextTime score (time state) of
>         Nothing -> indicateNoMoreChunks state
>         Just t  -> layoutSystem' (state { time = t })
>
> where  Nothing  indicates failure and  Just  success.

Okay, tried to give some more detail. thanks for the interesting code. I will
study it some more. But here's the original task.

{-

A composition consists of several voices or instruments, each indicated
by its own *staff*. Visually, a staff is a layout of items such as
notes, clef signs, and accidentals arranged horizontally from left to
right in increasing time.


A *system* is a set of staves stacked vertically that represent
instruments playing at the same time.

Here is a simple representation of a system, in which the pipe character
represents items. Note that some of the items are aligned vertically
meaning they will play at the same time. At other times, only one
staff contains a sounding item.

staff 1:   |    |  | |
staff 2:     |  |    | |

Next we elaborate this model to show that items have visual width. Here
they are represented by clusters of x's with a pipe in the middle. The pipe
represents the part of the item that needs to be aligned with items on
other staves. For example, in the visual representation of a chord,
the part of the chord called the notehead needs to be aligned with
noteheads on other staves. (A chord includes other symbols, like accidentals
and flags, which get drawn to the right or left of the notehead and don't
need to be aligned vertically with anything else.)


staff 1:  x|x xx|xx        x|x

staff 2:       x|x x|x xxxxx|xxxxx

            a    b   c       d

Here you can see that there is an additional constraint on layout,
which is that items need to have horizontal space around them so they
don't collide. For instance, the very wide item at 'd' (on staff 2) means
that the item on staff 1 at 'd' has to be positioned far to the right
of its previous item.

Note that data exists in two domains: there is data that describes notes;
that is, pitches and timbres and volumes and times and duration. We'll
call this the 'score'. It's the fundamental data. Then there is the
visual *representation* of the score. Here we are concerned only with
creating a visual representation. However, we need to refer to
data in the score.

-}

-- LayoutItem is a visual representation of a note. The center of the note
-- or chord (specifically the part that needs to be aligned vertically)
-- goes at position 'pos', the other variables describe how much the
-- note sticks out to the left, right, top, and bottom. We omit other
-- details about the note.
data LayoutItem = LayoutItem
   { pos :: ( Int, Int ),
     leftWidth, rightWidth, topHeight, bottomHeight :: Int,
     staffId :: String  }
-- ChunkData is 'score' domain data. It represents all notes that start
-- sounding at the same time. It is an association list of staff
-- names to notes. Note that a complete score is essentially a list of
-- chunks in time order.
data ChunkData = ChunkData [ ( String, [ Note ] ) ]
-- We'll just say a note is an int giving its pitch.
type Note = Int
-- A system layout is a set of *staves*. Here, staves are
-- lists of LayoutItem, put into an association list by staff name.
-- There is also a need to make a memo of chunks for future reference.
data SystemLayout = SystemLayout
   { staves :: [ ( String, [ LayoutItem ] ) ],
     chunkMemo :: [ ChunkData ] }
-- This is the loop state. During the loop, 'time' keeps advancing to
-- the time of the next chunk, and 'nextX' keeps advancing to the next
-- vetical alignment location.
data LoopState = LoopState {
     time     :: Double,
     nextX    :: Int }
--- Details of score omitted, but assume it has two key functions.
data Score = Score ...
scoreGetChunkData :: Score -> Time -> ChunkData
scoreNextTime :: Score -> Time -> Maybe Time

-- layoutSystem works as follows: it takes a time to start the layout
-- at, a score, and a maximum paper width, and returns a tuple with the
-- LoopState and SystemLayout at termination.
--
-- The looping happens in the helper function layoutSystem' which
-- has a simple signature: basically all relevant state goes in,
-- and all relevant state comes out. (See signtaure below.)
--
-- incororateChunkData does the main work of looking at all notes
-- in the next chunk and either finguring out how to add them to
-- the staves, or indicating they can't be added without going off
-- the right edge of the paper. It returns
-- a tuple ( Bool, LoopState, SystemLayout ) where the Bool indicates
-- success or failure.
layoutSystem Time -> Score -> Int -> ( LoopState, SystemLayout )
layoutSystem firstTime score maxWidth =
    layoutSystem' initialState initialSystemLayout
    where
      initialState = LoopState { time = firstTime, nextX = 0 }
      initialSystemLayout SystemLayout { staves = [], chunkMem = [] } )

      layoutSystem' :: LoopState -> SystemLayout ->( LoopState, SystemLayout )
      layoutSystem' state slayout =
        let chunkData = scoreGetChunkData score (time state)
        in case incorporateChunkData chunkData state slayout maxWidth of
          ( True,  state', slayout' ) -> layoutSystem' state' slayout'
          ( False, state', slayout') ->
            case scoreNextTime score (time state) of
              Just t -> layoutSystem' state' { time = t } slayout'
              Nothing -> ( state', slayout' )


-- incorporateChunkData is a function that does the work  of looking at
-- all notes
-- in the next chunk and either figuring out how to add them to
-- the staves, or indicating they can't be added without going off
-- the right edge of the paper. It returns
-- a tuple ( Bool, LoopState, SystemLayout ) where the Bool indicates
-- success or failure.

incorporateChunkData :: LoopState -> SystemLayout -> Int ->
                         ( Bool, LoopState, SystemLayout )
incorporateChunkData chunkData state slayout maxWidth =
   let items = makeLayoutItems chunkData
       -- Find new x alignment value, which done by finding how far right
       -- each item needs to go to avoid collision with previous items
       -- For each staff staffId and each item i that needs to be added to
       -- the staff, the question is: how far right does the staff extend,
       -- and how far left does the new item stick out from its central
       -- position? That tells you where the new item needs to go.
       -- (the function rightExtent finds how far right a staff extends),
       -- This process needs to be repeated for all staves, noting the
       -- needed alignment point for each---and then the final determination
       -- is the maximum of all those alignment points.
       alignX = max (map (\i -> let r = rightExtent slayout (staffId i)
                                in r + leftWidth i)
                         items)
       -- Now see if we've run off the right edge of the paper.
       -- Then check how far to the right each item will extend and
       -- compare to maxWidth
       farRight = max ( map (\i -> alignX + rightWidth i) items)
       if farRight < maxWidth
       then let slayout' = addItems slayout items alignX
                state' = state { nextX = alignX + 1 }
            in ( True, state', slayout' )
       else ( False, state, slayout )