Syntax programming with lexemes rather than trees?

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

Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hello All

Modern functional programming languages give you algebraic data types
that are mighty convenient for programming with syntax trees. However,
I'm working in a domain (music typesetting) where modelling syntax
with trees can be problematic and I'm wondering whether I should work
at a lower level - essentially a list / stream of lexemes and some
notion of a context stack for processing, tracking when I'm inside a
tuplet and the metrical calculation is scaled, for example.

Does anyone know of any previous work that takes a "lexical" view of
syntax rather than an abstract syntax tree view? Any domain is good -
I can't imagine there's any prior work on music typesetting.

Pointers to papers would be more digestible than code but either is
fine. Similarly, implementation in any functional language is fine.

Thanks

Stephen
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Malcolm Wallace
> I'm working in a domain (music typesetting) where modelling syntax  
> with trees can be problematic and I'm wondering whether I should  
> work at a lower level - essentially a list / stream of lexemes and  
> some notion of a context stack for processing, tracking when I'm  
> inside a tuplet and the metrical calculation is scaled, for example.

It sounds like your domain is generation of syntax, rather than  
parsing.  It also sounds rather similar to the difference between the  
high-level language accepted by a compiler (represented by an AST) and  
the target language produced by a compiler (generally a flat list of  
almost-atomic instructions and labels).  So maybe techniques for  
dealing with low-level assembly-like languages would be worth  
investigating.

Regards,
     Malcolm




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hi Malcolm

Thanks - particularly I don't want to go to an AST because its I'm
finding it too convoluted 'shape wise' - processing beam groups inside
tuplets etc. is a nightmare - music representations have had at least
eight centuries of ad hoc extension.

I know Norman Ramsey and colleagues papers on low-level
representations - I'll give them a re-reading.

Thanks again

Stephen
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Neil Mitchell
Hi Stephen,

It actually sounds like your representation has structure, but you
dislike structure because it's hard to work with. The solution is a
generics library, and I recommend Uniplate:
http://community.haskell.org/~ndm/uniplate

Imagine you have a ridiculously complex AST, with beam groups under
tuplets etc, and you want to delete the first item from every beam
group:

transform f
  where f (Beam (x:xs)) = Beam xs
           f x = x

Uniplate moves through tuplets and any other hierarchical syntax, so
you just specify the transformation. My guess is if you throw away the
structure then you'll need it back for some operations.

Thanks, Neil

2010/3/22 Stephen Tetley <[hidden email]>:

> Hi Malcolm
>
> Thanks - particularly I don't want to go to an AST because its I'm
> finding it too convoluted 'shape wise' - processing beam groups inside
> tuplets etc. is a nightmare - music representations have had at least
> eight centuries of ad hoc extension.
>
> I know Norman Ramsey and colleagues papers on low-level
> representations - I'll give them a re-reading.
>
> Thanks again
>
> Stephen
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hi Neil

Thanks - music has has lots of structure, true, but unfortunately the
structure is often arbitrary, sometimes even conflicting (with respect
to a nested representation).

I've tried various representations: plain algebraic data types, HOAS,
generics with KURE, tagless, attribute grammar with UUAG. From all
this, it turns out that the transformations I want to are pretty
simple:

- 'rename' pitch - two versions - one context free so I can use fmap;
the other context sensitive, so I use stmap - a variation of mapAccumL
coded as a typeclass - its surprising pleasant to use as an
alternative to a state monad when you can live with left-to-right
traversals only:

  class StateMap  f where
    stmap :: (st -> a -> (b, st)) -> st -> f a -> (f b, st)

- 'rename' duration - same thing, two different traversals one context
sensitive, one context free.

- metrical splitting - more complicated - segmenting note lists into
bars and beams groups (which must be communicated to LilyPond and ABC)
somewhat reminiscent of groupBy in Data.List but more involved. I've
rewritten the algorithm about 5 times, each time a slight improvement
though it still isn't pretty (not a big deal, however, so long as it
works).

At the moment I can do quite a lot with what I've got, but its too
unwieldy for real use - recently adding support for above-staff fret
diagrams has caused a lot of duplicated code even though it should be
superficially simple (fret diagrams don't need tuplets or beam groups
in their note list syntax). So I need a more different representation.

Although Malcolm didn't mention it, his message reminded me of
streaming XML processing. I've found a few papers since by Alain
Frisch, Keisuke Nakano and colleagues that cast streaming in a
functional light, so I'll see how far I can get with a similar
approach.

Thanks again

Stephen
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Syntax programming with lexemes rather than trees?

Max Rabkin-2
In reply to this post by Neil Mitchell
[Sorry for the accidental off-list reply, Neil]

On Tue, Mar 23, 2010 at 10:43 PM, Neil Mitchell <[hidden email]> wrote:
> It actually sounds like your representation has structure, but you
> dislike structure because it's hard to work with.

It seems to me like the data has structure, but that data is not
treelike! Is a performance a collection of measures or a collection of
instruments? A tree-like structure makes you choose, but in truth it
is both. I'm not sure I've seen a good solution to this kind of
problem in FP.

--Max
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hi Max

LilyPond has already answer this one (and ABC can't handle it) -
scores are collections of instrument parts and parts themselves are
made of measures. In practice, I do all assembly at the score/part
level with untyped pretty printing combinators, trying for a typed
representation would be too restrictive - LilyPond has a very large
LaTeX style syntax for assembling scores.

Best wishes

Stephen

On 24 March 2010 11:25, Max Rabkin <[hidden email]> wrote:
[Snip]
> Is a performance a collection of measures or a collection of
> instruments? A tree-like structure makes you choose, but in truth it
> is both. I'm not sure I've seen a good solution to this kind of
> problem in FP.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Yitzchak Gale
Stephen Tetley wrote:
> LilyPond has already answer this one...
> trying for a typed
> representation would be too restrictive - LilyPond has a very large
> LaTeX style syntax for assembling scores.

I find LilyPond's very monolithic very stateful representation
to be ugly and awkward. It clearly misses out most of the
underlying structure - and in correspondence with the authors on
the mailing list there, it is clear that they are aware of this.
They chose a certain representation philosophy based on a
weird ad hoc blend of Scheme and LaTeX, and they are sticking
with it to the bitter end only because it's far too late to turn back.

Don't get me wrong - I love LilyPond, it is an absolutely fantastic
piece of software. But the kinds of kluges and backflips that you
need to get even simple things done sometimes is staggering.

Example: when you write a simple lead sheet with named
chords, you'll always want to use "chordChanges" mode. But
then, if the first chord in the second ending of a volta repeat is
the same as the last chord in the first ending, it will be omitted.
Because after all, the whole piece is just a linear stream of
tokens with no structure. With work you can get the chord to
print, but what a mess. And then if you want to change something,
you have to undo the whole mess and do it again.

You are absolutely right that the structure of music representation
is not simple at all. But it is there. Please don't give up.

Regards,
Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hi Yitzchak

Thanks for the encouragement. Funnily enough its been the working with
'repeat' syntax that has tipped the current revision of my code from
being "workable, somewhat ad-hoc, polish-able later" into "horrible -
too complex, needs a simpler foundation." As for programming to
LilyPond from Haskell, with the latest revision I've managed entirely
with the stmap class I posted above (and its pathological extension to
a 3 parameter functor - trifunctor?). There isn't a monad in sight in
currently.

While the results are disappointing at the moment, the domain has been
fruitful for cultivating some exotic functional codes: families of
unfold functions extending the skipping unfold at the heart of the
stream fusion paper [1]; traversals that separate shape from contents
[2] and more.

Best wishes

Stephen


[1] http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf

further elaborated by Jeremy Gibbons:
http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/adt.pdf

[2] http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/iterator-msfp.pdf
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Henning Thielemann-4
In reply to this post by Stephen Tetley-2
Stephen Tetley schrieb:

> Hello All
>
> Modern functional programming languages give you algebraic data types
> that are mighty convenient for programming with syntax trees. However,
> I'm working in a domain (music typesetting) where modelling syntax
> with trees can be problematic and I'm wondering whether I should work
> at a lower level - essentially a list / stream of lexemes and some
> notion of a context stack for processing, tracking when I'm inside a
> tuplet and the metrical calculation is scaled, for example.
>
> Does anyone know of any previous work that takes a "lexical" view of
> syntax rather than an abstract syntax tree view? Any domain is good -
> I can't imagine there's any prior work on music typesetting.
>
> Pointers to papers would be more digestible than code but either is
> fine. Similarly, implementation in any functional language is fine.
>  
There was some unpublished work to emit Lilypond code for Haskore songs.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Syntax programming with lexemes rather than trees?

Stephen Tetley-2
Hi Henning

Thanks - yes, there is a report by Matt Munz, a student of Paul Hudak's.

Last year I tried to get my library to work with Haskore, but Haskore
has numerical durations - for scores you need symbolic ones, and its a
lot of work deriving symbolic durations from numeric ones. There are
few other problems such as they way Haskore handles overlays that
don't lend well to score output, at least not for LilyPond (originally
Haskore worked with the Lisp score system CNM I believe).

There's an example here of how far I got with Haskore - I don't think
Chick Corea's publishers will be getting in touch...

http://www.flickr.com/photos/44929957@N03/

Best wishes

Stephen
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe