ADP.Fusion.GAPlike

HINTS for writing your own (Non-) terminals:

• ALWAYS provide types for local functions of mkStream and mkStreamInner. Otherwise stream-fusion gets confused and doesn't optimize. (Observable in core by looking for Left, RIght constructors and SPEC constructors.

The required type classes. Each class does its own thing.

class Build x where

The Build class. Combines the arguments into a stack before they are turned into a stream.

To use, simply write "instance Build MyDataCtor" as we have sensible default instances.

Minimal complete definition

Nothing

Associated Types

type BuildStack x :: *

The stack of arguments we are building.

Methods

build :: x -> BuildStack x

The default is for the left-most element.

Given an element, create the stack.

Instances

Build Empty

Build (RestrictedRegion e)

Build (Chr e)

Build x => Build (x, y)

Build (MTbl c es)

Build (Tbl c es)

Build (BTtbl c t g)

class StreamElement x where

The stream element. Creates a type-level recursive data type containing the extracted arguments.

Associated Types

data StreamElm x :: *

one element of the stream, recursively defined

type StreamTopIdx x :: *

top-most index of the stream -- typically int

type StreamArg x :: *

complete, recursively defined argument of the stream

Methods

getTopIdx :: StreamElm x -> StreamTopIdx x

Given a stream element, we extract the top-most idx

getArg :: StreamElm x -> StreamArg x

extract the recursively defined argument in a well-defined way for apply

Instances

StreamElement Empty

StreamElement None

(Monad m, StreamElement x, TblType c) => StreamElement ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b)))

StreamElement x => StreamElement ((:.) x (RestrictedRegion e))

(StreamElement x, MPrimArrayOps marr DIM2 e, TblType c) => StreamElement ((:.) x (MTbl c (marr s DIM2 e)))

(StreamElement x, PrimArrayOps arr DIM2 e, TblType c) => StreamElement ((:.) x (Tbl c (arr DIM2 e)))

StreamElement x => StreamElement ((:.) x (Chr e))

class StreamConstraint x => MkStream m x where

Given the arguments, creates a stream of StreamElements.

Associated Types

type StreamConstraint x :: Constraint

Methods

mkStream :: StreamConstraint x => x -> (Int, Int) -> Stream m (StreamElm x)

mkStreamInner :: StreamConstraint x => x -> (Int, Int) -> Stream m (StreamElm x)

Instances

Monad m => MkStream m Empty

Monad m => MkStream m None

(Monad m, MkStream m x, StreamElement x, Unbox e, (~) * (StreamTopIdx x) Int, TblType c) => MkStream m ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b)))

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, Unbox e) => MkStream m ((:.) x (RestrictedRegion e))

(Monad m, PrimMonad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, MPrimArrayOps marr DIM2 e, TblType c, (~) * s (PrimState m)) => MkStream m ((:.) x (MTbl c (marr s DIM2 e)))

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, PrimArrayOps arr DIM2 e, TblType c) => MkStream m ((:.) x (Tbl c (arr DIM2 e)))

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, Unbox e) => MkStream m ((:.) x (Chr e))

Terminates the stack of arguments

data None

Very simple data ctor

Constructors

None

Instances

StreamElement None

Monad m => MkStream m None

type StreamConstraint None = ()

data StreamElm None = SeNone !Int

type StreamTopIdx None = Int

type StreamArg None = ArgZ

data ArgZ

For CORE-language, we have our own Arg-terminator

Constructors

ArgZ

Instances

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n) o -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e -> res)

Apply ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d -> res)

Apply ((:.) ((:.) ((:.) ArgZ a) b) c -> res)

Apply ((:.) ((:.) ArgZ a) b -> res)

Apply ((:.) ArgZ a -> res)

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n) o -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m -> n -> o -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m -> n -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i -> res) = a -> b -> c -> d -> e -> f -> g -> h -> i -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h -> res) = a -> b -> c -> d -> e -> f -> g -> h -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g -> res) = a -> b -> c -> d -> e -> f -> g -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f -> res) = a -> b -> c -> d -> e -> f -> res

type Fun ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e -> res) = a -> b -> c -> d -> e -> res

type Fun ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d -> res) = a -> b -> c -> d -> res

type Fun ((:.) ((:.) ((:.) ArgZ a) b) c -> res) = a -> b -> c -> res

type Fun ((:.) ((:.) ArgZ a) b -> res) = a -> b -> res

type Fun ((:.) ArgZ a -> res) = a -> res

A single character terminal. Using unboxed vector to hold the input. Note

data Chr e

Constructors

Chr !(Vector e)

Instances

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, Unbox e) => MkStream m ((:.) x (Chr e))

Build (Chr e)

StreamElement x => StreamElement ((:.) x (Chr e))

type BuildStack (Chr e) = (:.) None (Chr e)

type StreamConstraint ((:.) x (Chr e)) = ()

data StreamElm ((:.) x (Chr e)) = SeChr !(StreamElm x) !Int !e

type StreamTopIdx ((:.) x (Chr e)) = Int

type StreamArg ((:.) x (Chr e)) = (:.) (StreamArg x) e

Empty and non-empty tables.

data E

empty subwords allowed

Instances

TblType E

data N

only non-empty subwords

Instances

TblType N

class TransToN t where

Associated Types

type TransTo t :: *

Methods

transToN :: t -> TransTo t

Instances

TransToN (MTbl c es)

TransToN (Tbl c es)

TransToN (BTtbl c t g)

class TblType tt where

Used by the instances below for index calculations.

Methods

initDeltaIdx :: tt -> Int

Instances

TblType N

TblType E

Immutable tables

data Tbl c es

Constructors

Tbl !es

Instances

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, PrimArrayOps arr DIM2 e, TblType c) => MkStream m ((:.) x (Tbl c (arr DIM2 e)))

TransToN (Tbl c es)

(StreamElement x, PrimArrayOps arr DIM2 e, TblType c) => StreamElement ((:.) x (Tbl c (arr DIM2 e)))

Build (Tbl c es)

type TransTo (Tbl c es) = Tbl N es

type StreamConstraint ((:.) x (Tbl c (arr DIM2 e))) = ()

data StreamElm ((:.) x (Tbl c (arr DIM2 e))) = SeTbl !(StreamElm x) !Int !e

type StreamTopIdx ((:.) x (Tbl c (arr DIM2 e))) = Int

type StreamArg ((:.) x (Tbl c (arr DIM2 e))) = (:.) (StreamArg x) e

type BuildStack (Tbl c es) = (:.) None (Tbl c es)

Mutable tables in some monad.

data MTbl c es

Constructors

MTbl !es

Instances

(Monad m, PrimMonad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, MPrimArrayOps marr DIM2 e, TblType c, (~) * s (PrimState m)) => MkStream m ((:.) x (MTbl c (marr s DIM2 e)))

TransToN (MTbl c es)

(StreamElement x, MPrimArrayOps marr DIM2 e, TblType c) => StreamElement ((:.) x (MTbl c (marr s DIM2 e)))

Build (MTbl c es)

type TransTo (MTbl c es) = MTbl N es

type StreamConstraint ((:.) x (MTbl c (marr s DIM2 e))) = ()

data StreamElm ((:.) x (MTbl c (marr s DIM2 e))) = SeMTbl !(StreamElm x) !Int !e

type StreamTopIdx ((:.) x (MTbl c (marr s DIM2 e))) = Int

type StreamArg ((:.) x (MTbl c (marr s DIM2 e))) = (:.) (StreamArg x) e

type BuildStack (MTbl c es) = (:.) None (MTbl c es)

mtblN :: es -> MTbl N es

mtblE :: es -> MTbl E es

Some convenience functions.

tNtoE :: Tbl N x -> Tbl E x

tEtoN :: Tbl E x -> Tbl N x

Parses an empty subword.

data Empty

The empty subword. Can not be part of a more complex RHS for obvious reasons: "S -> E S" doesn't make sense. Used in some grammars as the base case.

Constructors

Empty

Instances

StreamElement Empty

Build Empty

Monad m => MkStream m Empty

type StreamConstraint Empty = ()

data StreamElm Empty = SeEmpty !Int

type StreamTopIdx Empty = Int

type StreamArg Empty = (:.) ArgZ ()

type BuildStack Empty = Empty

Parsing subwords with restriced size. Both min- and max-size are given

data RestrictedRegion e

Constructors

RRegion !Int !Int !(Vector e)

Instances

(Monad m, MkStream m x, StreamElement x, (~) * (StreamTopIdx x) Int, Unbox e) => MkStream m ((:.) x (RestrictedRegion e))

Build (RestrictedRegion e)

StreamElement x => StreamElement ((:.) x (RestrictedRegion e))

type BuildStack (RestrictedRegion e) = (:.) None (RestrictedRegion e)

type StreamConstraint ((:.) x (RestrictedRegion e)) = ()

data StreamElm ((:.) x (RestrictedRegion e)) = SeResRegion !(StreamElm x) !Int (Vector e)

type StreamTopIdx ((:.) x (RestrictedRegion e)) = Int

type StreamArg ((:.) x (RestrictedRegion e)) = (:.) (StreamArg x) (Vector e)

Backtracking tables.

data BTtbl c t g

The backtracking table 'BTtbl" captures a DP table and the function used to fill it.

Constructors

BTtbl t g

Instances

(Monad m, MkStream m x, StreamElement x, Unbox e, (~) * (StreamTopIdx x) Int, TblType c) => MkStream m ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b)))

(Monad m, StreamElement x, TblType c) => StreamElement ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b)))

TransToN (BTtbl c t g)

Build (BTtbl c t g)

type StreamConstraint ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b))) = ()

data StreamElm ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b))) = SeBTtbl !(StreamElm x) !Int !e (m (Stream m b))

type StreamTopIdx ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b))) = Int

type StreamArg ((:.) x (BTtbl c (Arr0 DIM2 e) (BTfun m b))) = (:.) (StreamArg x) (e, m (Stream m b))

type TransTo (BTtbl c t g) = BTtbl N t g

type BuildStack (BTtbl c t g) = (:.) None (BTtbl c t g)

bttblN :: t -> g -> BTtbl N t g

bttblE :: t -> g -> BTtbl E t g

type BTfun m b = (Int, Int) -> m (Stream m b)

The backtracking function, given our index pair, return a stream of backtracked results. (Return as in we are in a monad).

TODO Should this be "(Int,Int) -> m (SM.Stream Id b)" or are there cases where we'd like to have monadic effects on the "b"s?

Build complex stacks

combinators

(<<<) :: (Build x, StreamElement (BuildStack x), MkStream m (BuildStack x), Apply (StreamArg (BuildStack x) -> b), Monad m) => Fun (StreamArg (BuildStack x) -> b) -> x -> (Int, Int) -> Stream m b infixl 8

(|||) :: Monad m => (t -> Stream m a) -> (t -> Stream m a) -> t -> Stream m a infixl 7

(...) :: (t1 -> s) -> (s -> t) -> t1 -> t infixl 6

(..@) :: (t1 -> s) -> (t1 -> s -> t) -> t1 -> t infixl 6

(~~) :: a -> b -> (a, b) infixl 9

(%) :: a -> b -> (a, b) infixl 9

Apply function f in '(<<<)'

class Apply x where

Associated Types

type Fun x :: *

Methods

apply :: Fun x -> x

Instances

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n) o -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m) n -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l) m -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k) l -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j) k -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i) j -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h) i -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g) h -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f) g -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e) f -> res)

Apply ((:.) ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d) e -> res)

Apply ((:.) ((:.) ((:.) ((:.) ArgZ a) b) c) d -> res)

Apply ((:.) ((:.) ((:.) ArgZ a) b) c -> res)

Apply ((:.) ((:.) ArgZ a) b -> res)

Apply ((:.) ArgZ a -> res)