Pass a function to mealy machine

[Mahshid Shahmohammadian]

Hi, 

Not sure if this was asked before, but suppose we have designed the transfer function of a mealy machine and a specific portion of it is generic and we want to get a function of type say (a -> Int -> a) to be called for that portion. In my mind, I just pass this function as a part of the states such as:

( (s , (a -> Int -> a)) -> i -> ((s , (a -> Int -> a), o)) --> the type of transfer function for mealy

And then when I call mealy I can define my function as a state. As an example:

hsSerial = mealy handshakeSerial ((16,0, 0,True) , \x i -> x+1 )

This does not reach a normal form, I was wondering why this happens, and what ways do you recommend to fix it?

The error I get from vhdl generation:

GHC: Parsing and optimising modules took: 0.925s
GHC: Loading external modules from interface files took: 0.000s
GHC: Parsing annotations took: 0.002s
Clash: Parsing and compiling primitives took 0.139s
GHC+Clash: Loading modules cumulatively took 1.348s
Clash: Compiling Example.HandshakeRV.topEntity
Clash.Normalize.Transformations(493): InlineNonRep: c$Example.HandshakeRV.hsSerial_ds[785] already inlined 50 times in:
Example.HandshakeRV.hsSerial[779]. The type of the subject is:

  GHC.Tuple.(,)[3746994889972252676]
    (GHC.Tuple.(,)[3746994889972252676]
       (GHC.Tuple.(,,,)[3746994889972252680]
          GHC.Types.Int[3674937295934324766]
          (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
          GHC.Types.Int[3674937295934324766]
          GHC.Types.Bool[3674937295934324744])
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16
       -> GHC.Types.Int[3674937295934324766]
       -> Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16))
    (GHC.Tuple.(,,)[3746994889972252678]
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
       GHC.Types.Bool[3674937295934324744]
       GHC.Types.Bool[3674937295934324744])

Function Example.HandshakeRV.hsSerial[779] will not reach a normal form and compilation
might fail.

Run with '-fclash-inline-limit=N' to increase the inline limit to N.
Clash.Normalize.Transformations(493): InlineNonRep: c$Example.HandshakeRV.hsSerial_ds[785] already inlined 50 times in:
Example.HandshakeRV.hsSerial[779]. The type of the subject is:

  GHC.Tuple.(,)[3746994889972252676]
    (GHC.Tuple.(,)[3746994889972252676]
       (GHC.Tuple.(,,,)[3746994889972252680]
          GHC.Types.Int[3674937295934324766]
          (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
          GHC.Types.Int[3674937295934324766]
          GHC.Types.Bool[3674937295934324744])
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16
       -> GHC.Types.Int[3674937295934324766]
       -> Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16))
    (GHC.Tuple.(,,)[3746994889972252678]
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
       GHC.Types.Bool[3674937295934324744]
       GHC.Types.Bool[3674937295934324744])

Function Example.HandshakeRV.hsSerial[779] will not reach a normal form and compilation
might fail.

Run with '-fclash-inline-limit=N' to increase the inline limit to N.
Clash.Normalize.Transformations(493): InlineNonRep: c$Example.HandshakeRV.hsSerial_ds[785] already inlined 50 times in:
Example.HandshakeRV.hsSerial[779]. The type of the subject is:

  GHC.Tuple.(,)[3746994889972252676]
    (GHC.Tuple.(,)[3746994889972252676]
       (GHC.Tuple.(,,,)[3746994889972252680]
          GHC.Types.Int[3674937295934324766]
          (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
          GHC.Types.Int[3674937295934324766]
          GHC.Types.Bool[3674937295934324744])
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16
       -> GHC.Types.Int[3674937295934324766]
       -> Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16))
    (GHC.Tuple.(,,)[3746994889972252678]
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
       GHC.Types.Bool[3674937295934324744]
       GHC.Types.Bool[3674937295934324744])

Function Example.HandshakeRV.hsSerial[779] will not reach a normal form and compilation
might fail.

Run with '-fclash-inline-limit=N' to increase the inline limit to N.
Clash.Normalize.Transformations(493): InlineNonRep: c$Example.HandshakeRV.hsSerial_ds[785] already inlined 50 times in:
Example.HandshakeRV.hsSerial[779]. The type of the subject is:

  GHC.Tuple.(,)[3746994889972252676]
    (GHC.Tuple.(,)[3746994889972252676]
       (GHC.Tuple.(,,,)[3746994889972252680]
          GHC.Types.Int[3674937295934324766]
          (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
          GHC.Types.Int[3674937295934324766]
          GHC.Types.Bool[3674937295934324744])
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16
       -> GHC.Types.Int[3674937295934324766]
       -> Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16))
    (GHC.Tuple.(,,)[3746994889972252678]
       (Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16)
       GHC.Types.Bool[3674937295934324744]
       GHC.Types.Bool[3674937295934324744])

Function Example.HandshakeRV.hsSerial[779] will not reach a normal form and compilation
might fail.

Run with '-fclash-inline-limit=N' to increase the inline limit to N.
Clash: Normalization took 4.346s

<no location info>: error:
    
    Clash.Netlist(332): Can't translate non-tycon type: Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16
    -> GHC.Types.Int[3674937295934324766]
    -> Clash.Sized.Internal.Signed.Signed[8214565720323786519] 16

Thanks,

Mahshid

[Christiaan Baaij]

Hi Mahshid,

Sorry, it's currently not possible to have a function as part of the "state", i.e. something that will be stored in a register.

If the function remains constant for every mealy machine, then instead of writing:

handshakeSerial :: (s, a -> Int -> a) -> i -> ((s, a -> Int -> a), o)

hsSerial = mealy handshakeSerial ((16,0, 0,True) , \x i -> x+1)

you can write:

handshakeSerial ::  (a -> Int -> a) -> s -> i -> (s, o)

hsSerial = mealy (handshakeSerial (\x i -> x+1)) (16,0, 0,True)

Now, the function (\x i -> x + 1) isn't "stored" as part of the "state".

In case you're interested why your original code doesn't currently work:

The Clash compiler only does a technique called "specialization", where basically:

1. for every applied higher-order function 'f' with applied functional argument 'g': "f g";

2. We create a new function `f1` that has the body of `f`, \x -> e, where every occurance of `x` in `e` is substituted by `g`:  e[x := g]

3. We then replace "f g" by `f1`

We cannot do this for things like `register`, which is used inside `mealy`, because it is a primitive (just one of the reasons actually).

Clash would be able to compile it if it supported a technique called "defunctionalization" where higher-order arguments are translated to ADTs,

and applications of higher-order arguments are translated to application of a function called "eval" on the translated higher-order argument.

e.g. in the above example of `f` and `g` we would get:

data Functions = GFun

eval GFun = \y -> e1

f = \x -> e [x := eval x]

f GFun

Since Clash is a whole-program compiler, for most cases, direct specialisation and defunctionalization achieve the same thing.

So we never took the time to implement defunctionalization as well.

You have discovered a case where automatic defunctionalization would have paid off.

On the other hand... as a work-around you could do the above transformation manually if you really need to "store" functional values.

One of the reason why we haven't invested a lot of time in defunctionalization is there are some tricky corner-cases where we need to think on how to solve them.

For example, someone might think it's a good idea to describe an accumulator like:

transfer g x = ((+ x) . g), g x)

accumulator = mealy transfer id

where standard defunctionalization would result in a recursive "Functions" ADT, where recursive ADTs can't be translated to a circuit at this time time.

(clash-prelude's recursive Vec and RTree ADTs have special handling inside the Clash compiler at this time).

So for now, the specialization technique is all the Clash compiler will do for you.

Cheers,

Christiaan

--
You received this message because you are subscribed to the Google Groups "Clash - Hardware Description Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clash-languag...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/clash-language/402a44fc-a999-4c9a-99cf-9915a9f1ed41n%40googlegroups.com.

[peter.t...@gmail.com]

That means you get your own on-the-fly interpreter inside the mealy machine, and your state contains the _description_ "\x -> x+1" (but not as a string, as an "ADT"), and that is executed by the built-in interpreter as a program on an argument as needed.

At least I think that's what that meant  .. :-)

That could be very efficient because the interpreter doesn't have to be very general, it just has to deal with the functions/programs you plan on possibly giving it. But how would it know what you plan on? Types, I suppose.

I have noticed that one can automatically build mealy machines to execute any (recursive) functional program efficiently (so long as it works in a bounded stack). One just calls every subexpression an instruction/phrase  of an abstract grammar/ADT element. Then one defines what the mealy machine should do to results on a stack of arithmetic results when it sees that subexpression, as well as what it should do to a stack of other subexpressions to evaluate. That's probably called "PostScript" at home. Or "Ponder". The point is that the language/ADT to be interpreted by the interpreter is defined by the function you started with and its definition, not by everything in the language THAT lives in. It's much smaller. For a +1 or -1 it just needs in principle to  spot the difference between wishes for + and wishes for -.

Peter

[Mahshid Shahmohammadian]

Thank you Christiaan and Peter for your thorough responses. That was very useful.

Mahshid