[Haskell-cafe] From function body to DAG and back again?

[Serguey Zefirov]

What you described is a topological sorting - sort nodes by their
dependencies. Inputs do not depend on anything, they may go firist as
their dependence level is 0, outputs depends on intermediate values
and nothing depends on them, they go last.

Sort nodes in graph accoring to their dependence level and output them
as let expressions. There you will have your function definition
decompiled.

2022-12-14 17:59 GMT+03:00, Mario Lang <mlang at blind.guru>:
> Hi.
>
> I have a binary instance for a file format[1] which describes
> a graph of DSP primitives.  This DAG was generated from a function body[2]
> (in another programming language).  I think that language
> can be boiled down to a pure language with let expressions,
> to allow an output to be consumed by several inputs.
> And there the trouble starts.  I am working on this without the usual
> theoretical background.  I am not a PLD student, I am a self-taught Haskell
> fan.
>
> The function body is basically a very neat way to make a DAG readable
> without using visualisation.  Since I am blind, this topic has always
> fascinated me.
>
> Since I have this bidirectional binary instance, and
> Haskell is supposed to be great at writing small languages,
> I wonder what would be required to
> * write a decompiler which would generate a version of the original function
> body
> as a data structure and
> * write a compiler which would translate that data structure back to the
> graph.
>
> This is very much for my own learning experience, especially
> since there is already a Haskell library which implements at least the
> compilation part, and more.  However, I always found it very fascinating
> to try to understand how this translation works, so I'd finally
> like to take a stab at implementing it myself.
>
> I have now searched a day for matching learning material which
> would shed some light on the problem for me, without any great success.
> Most SLC-examples I stumbled across immediately proceed to
> implement an evaluation fucntion, which is not quite what I need.
> For both directions, I need to work out the data structure
> for my small language first, which is where I am stuck.
> I have a feeling the decompiler might be easier to write then
> the compiler.  My intuition says all I need to do is work backwards from
> the last graph node, resolving all inputs until I am done.
> However, I am stuck on the data structure and the compiler part.
>
> Any hints on what could help me to get a better grasp on the problem and
> how to solve it in Haskell are greatly appreciated.
>
>
> [1]
> https://github.com/mlang/sound-supercollider/blob/master/Sound/SuperCollider/SynthDef.hs
>
> [2]
>
> SynthDef(\default, { arg out=0, freq=440, amp=0.1, pan=0, gate=1;
> 	var z = LPF.ar(
> 		Mix.new(
> 			VarSaw.ar(freq + [0, Rand(-0.4,0.0), Rand(0.0,0.4)], 0, 0.3, 0.3)
> 		),
> 		XLine.kr(Rand(4000,5000), Rand(2500,3200), 1)
> 	) * Linen.kr(gate, 0.01, 0.7, 0.3, 2);
> 	OffsetOut.ar(out, Pan2.ar(z, pan, amp));
> }, [\ir]).writeDefFile;
>
> Which translates to the following graph.  The pairs are inputs, pointing
> at the corresponding outputs in the graph, -1 refering to the list of
> constants at the beginning.
>
> defaultSynthDef :: SynthDef
> defaultSynthDef = SynthDef
>   [ GraphDef
>     "default"
>     [-0.4,0.0,0.4,0.3,4000.0,5000.0,2500.0,3200.0,1.0,1.0e-2,0.7,2.0]
>     [0.0,440.0,0.1,0.0,1.0]
>     [("out",0),("freq",1),("amp",2),("pan",3),("gate",4)]
>     [ UGen "Control" Scalar 0 [] [Scalar]
>     , UGen "Control" Control 1 [] [Control,Control,Control,Control]
>     , UGen "VarSaw" Audio 0 [(1,0),(-1,1),(-1,3)] [Audio]
>     , UGen "BinaryOpUGen" Audio 2 [(2,0),(-1,3)] [Audio]
>     , UGen "Linen" Control 0 [(1,3),(-1,9),(-1,10),(-1,3),(-1,11)] [Control]
>     , UGen "Rand" Scalar 0 [(-1,0),(-1,1)] [Scalar]
>     , UGen "BinaryOpUGen" Control 0 [(1,0),(5,0)] [Control]
>     , UGen "VarSaw" Audio 0 [(6,0),(-1,1),(-1,3)] [Audio]
>     , UGen "BinaryOpUGen" Audio 2 [(7,0),(-1,3)] [Audio]
>     , UGen "Rand" Scalar 0 [(-1,1),(-1,2)] [Scalar]
>     , UGen "BinaryOpUGen" Control 0 [(1,0),(9,0)] [Control]
>     , UGen "VarSaw" Audio 0 [(10,0),(-1,1),(-1,3)] [Audio]
>     , UGen "BinaryOpUGen" Audio 2 [(11,0),(-1,3)] [Audio]
>     , UGen "Sum3" Audio 0 [(12,0),(8,0),(3,0)] [Audio]
>     , UGen "Rand" Scalar 0 [(-1,4),(-1,5)] [Scalar]
>     , UGen "Rand" Scalar 0 [(-1,6),(-1,7)] [Scalar]
>     , UGen "XLine" Control 0 [(14,0),(15,0),(-1,8),(-1,1)] [Control]
>     , UGen "LPF" Audio 0 [(13,0),(16,0)] [Audio]
>     , UGen "BinaryOpUGen" Audio 2 [(17,0),(4,0)] [Audio]
>     , UGen "Pan2" Audio 0 [(18,0),(1,2),(1,1)] [Audio,Audio]
>     , UGen "OffsetOut" Audio 0 [(0,0),(19,0),(19,1)] []
>     ]
>     []
>   ]
>
> --
> CYa,
>   ⡍⠁⠗⠊⠕
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.