FAUST

Signal Processing Language

t

Yann Orlarey, Nicolas Scaringella, Dominique Fober,

Stéphane Letz, Etienne Gaudrain, Mathieu Leroi

___

Grame, Centre National de Création Musicale

9 rue du Garet, BP 1185

69202 Lyon Cedex 01, France

The FAUST project

A formal specification language

for real-time signal processing

and sound synthesis

A compiler generating efficient

C/C++ code comparable to

hand-written code

Multiple implementations from

one specification

2

3

1

The FAUST language

an algebraic block diagram language

D

D

D

D

A

B

D

D

D

D

A

B

:

<

Î

,

:

~

Recursive

Parallel

Split

:

<

:

>

Sequence

Merge

FAUST Composition Operators

The FAUST compiler

one specification  multiple implementations

FAUST

Specification

Max/MSP

plugin

VST

plugin

LADSPA

plugin

Jack-GTK

Application

FAUST

compiler

libsndfile

Application

Alsa-GTK

Application

Key elements of the compiler

Block Diagram Algebra

1

Well defined formal semantic

2

Semantic Compilation

3

Symbolic Simplification

4

Maximal Sharing of CSE

5

Type based optimizations

6

SIMD code generation

7

Multiple Targets

8

Part 1

t

Definition of the

Block-Diagram Algebra

The Block Diagram Algebra

Powerful enough to represent

any block diagram

1

Concise and adequate textual

syntax for block diagram

languages

2

Useful to formalize the

semantic of block diagram

languages

3

Suitable for formal manipula-

tions : lambda-calculus, partial

evaluation, compilation...

4

The Block Diagram Algebra

,

Constants

Operators

:

~

!

-

Identity

Recursive Composition

Parallel Composition

Cut

Split Composition

:

<

:

>

Sequence Composition

Merge Composition

Block-diagram Terms

The set D of block diagrams is defined by :

D ::= b|_|!|(d:d')|(d<:d')|(d:>d')|(d,d')|(d~d')

Where b  B the set of primitives, and d,d'  D

Ins( _ ) = 1

Outs( _ ) = 1

Identity

-

Ins( ! ) = 1

Outs( ! ) = 0

Cut

!

Outs(a) = Ins(b)

Ins( a:b ) = Ins(a)

Outs( a:b ) = Outs(b)

Sequence Composition

:

b

a

b

a

b

a

Outs(a) < Ins(b)

Ins(a:b) = Ins(a)+Ins(b)-Outs(a)

Outs(a:b) = Outs(b)

Outs(a) > Ins(b)

Ins(a:b) = Ins(a)

Outs(a:b) = Outs(b)+Outs(a)-Ins(b)

Split Composition

b

a

:

<

Outs(a)*k = Ins(b)

Ins( a<:b ) = Ins(a)

Outs( a<:b ) = Outs(b)

Merge Composition

:

>

a

b

Outs(a) = k*Ins(b)

Ins( a:>b ) = Ins(a)

Outs( a:>b ) = Outs(b)

Ins( a,b ) = Ins(a)+Ins(b)

Outs( a,b ) = Outs(a)+Outs(b)

Parallel Composition

,

b

a

Outs(a)>=Ins(b) &Ins(a)>=Outs(b)

Ins( a~b ) = Ins(a)-Outs(b)

Outs( a~b ) = Outs(a)

Recursive Composition

~

a

b

Example

a

d

c

e

b

a <: b,c,d :> e

Part 2

t

Denotational Semantics

for Signal Processing

Block-Diagrams

Block-Diagrams as Signal Processors

A

In1

Out2

C

D

B

In2

R1

R1

R1

R1

R1

R2

Out1

R2

-,X,-

A,-,-

:

C,B,!

:

Y,Y

-,D,-

:

-,Y,-

:

:

Etape 4 – agencement des connexions

-

[ _ ] (s) = (s)

S

S

Identity

!

[ ! ] (s) = ()

S

Cut

!

:

[ b ] (t1,...,tj) = (y1,...,ym)

Sequence composition

[ a:b ] (x1,...,xn) = (y1,...,ym)

[ a ] (x1,...,xn) = (t1,...,tj)

b

a

Condition : Outs(a) = Ins(b)

X1

X2

T1

T2

T3

Y1

Y2

:

[ b ] (t1,...,tj,...,t1,...,tj) = (y1,...,ym)

Split composition

[ a<:b ] (x1,...,xn) = (y1,...,ym)

[ a ] (x1,...,xn) = (t1,...,tj)

Condition : Outs(a)*k = Ins(b)

b

a

<

X1

X2

T1

T2

T2

T2

T2

T1

T1

T1

Y1

Y2

Y3

Y4

Y5

Y6

:

[ b ] (r=0..k-1t1+r.j,...,r=0..k-1tj+r.j) = (y1,...,ym)

Merge composition

[ a:>b ] (x1,...,xn) = (y1,...,ym)

[ a] (x1,...,xn) = (t1,...,tk.j)

Condition : Outs(a) = k*Ins(b)

a

b

>

X1

X2

T1

T2

T3

T4

T5

T6

T1+T3+T5

T2+T4+T6

Y1

Y2

,

[ b ] (s1,...,so) = (t1,...,tp)

Parallel composition

[ a,b ] (x1,...,xn,s1,...,so) = (y1,...,ym,t1,...,tp)

[ a] (x1,...,xn) = (y1,...,ym)

b

a

X1

x2

y1

y2

y3

s1

s2

s3

t1

t2

~

[ b ] (y1-1,...,yu-1) = (r1,...,rv)

Recursive composition

[ a~b ] (x1,...,xn) = (y1,...,ym)

[ a] (r1,...,rv,x1,...,xn) = (y1,...,ym)

a

b

y1

y2

y3

y1-1

y2-1

r1

r2

x1

x2

Condition : Outs(a)  Ins(b) and Ins(a)  Outs(b)

Part 3

t

Compilation Process

Semantic Based compilation

Block-diagram

Symbolic propagation based

on the semantic rules

.

.

.

Symbolic

Input Signals

X1

X2

X3

X4

Y1=F1(X1,X2,X3,X4)

Y2=F2(X1,X2,X3,X4)

Y3=F3(X1,X2,X3,X4)

Y4=F4(X1,X2,X3,X4)

Symbolic

Output Signals

What is compiled

Signal

Signal op signal

Mem ( signal )

External function ( signal,...,signal )

Read table ( size, init, rindex)

Write table ( size, init, windex, signal, rindex )

Inputi

Ctrli

Number

op

+

-

*

/

%

&

|

^

<<

>>

<

>

<=

>=

==

!=

Symbolic Signals

Var x

Proji ( signal,...,signal )

Rec x.( signal,...,signal )

Type System

Nature of the signal :

integer or real.

1

Computability of the signal :

compile time, init time, real time

2

Variability of the signal :

constant, control rate, audio rate

3

Scalar or SIMD computation

4

Code Generation

class mydsp : public dsp {

private:

float	fslider0;

public:

virtual int getNumInputs()	{ return 1; }

virtual int getNumOutputs()	{ return 1; }

virtual void init(int samplingRate) {

fslider0 = 0.5;

}

virtual void buildUserInterface(UI* interface) {

interface->openVerticalBox("");

interface->addHorizontalSlider("volume", &fslider0,

0.5, 0.0, 1.0, 0.01);

interface->closeBox();

}

virtual void compute(int count, float** input, float** output) {

float* input0 = input[0];

float* output0 = output[0];

float ftemp0 = fslider0;

for (int i=0; i<count; i++) {

output0[i] = (input0[i] * ftemp0);

}

}

};

Process = *( hslider("volume", 0.5, 0, 1, 0.01) );

Part 4

t

Example : FAUST implementation of the Freeverb

1 – Gain and Wet/Dry controls

Fxctrl(g,w,Fx) = _,_ <: (*(g),*(g) : Fx : *(w),*(w)), *(1-w), *(1-w) :> _,_;

FX

*

*

Gain

*

*

Wet

+

+

*

*

1-Wet

2 – StereoReverb

stereoreverb(fb1,fb2,damp,spread) = + <: monoreverb(fb1,fb2,damp,0),

monoreverb(fb1,fb2,damp,spread);

+

Monoreverb

(fb1,fb2,damp,spread1)

Monoreverb

(fb1,fb2,damp,spread2)

monoreverb(fb1,fb2,damp,spread) =

_ <:	comb(ctL1+spread,fb1,damp),comb(ctL2+spread,fb1,damp),

comb(ctL3+spread,fb1,damp),comb(ctL4+spread,fb1,damp),

comb(ctL5+spread,fb1,damp),comb(ctL6+spread,fb1,damp),

comb(ctL7+spread,fb1,damp),comb(ctL8+spread,fb1,damp)

:>

allpass(atL1+spread,fb2) : allpass(atL2+spread,fb2),

allpass(atL3+spread,fb2) : allpass(atL4+spread,fb2) ;

3 – MonoReverb

comb

comb

comb

comb

comb

comb

comb

comb

+

allpass

allpass

allpass

allpass

4 – Comb filter

Comb(dt,fb,damp) = ( + : delay(8192, dt)) ~ ( *(1-damp) : +~*(damp) : *(fb));

+

*(1-damp)

+

*(damp)

*(fb)

Z-dt

Z-1

Z-1

5 – Allpass filter

allpass(dt,fb) = (_,_ <: (*(fb) : + : delay(8192,dt)), - ) ~ _ : (!,_);

+

-

*(fb)

Z-dt

Z-1

L'exposé est organisé en deux parties. Tout d'abord une présentation de l'algèbre proprement dite.

Comme on va le voir elle est très simple. Elle se base essentiellement sur trois opérations binaires.

Et puis dans la deuxième partie je montrerai comment ce type de representation facilite la définition d'une sémantique dénotationnelle pour des langages de type block-diagram.

L'exposé est organisé en deux parties. Tout d'abord une présentation de l'algèbre proprement dite.

Comme on va le voir elle est très simple. Elle se base essentiellement sur trois opérations binaires.

Et puis dans la deuxième partie je montrerai comment ce type de representation facilite la définition d'une sémantique dénotationnelle pour des langages de type block-diagram.

L'exposé est organisé en deux parties. Tout d'abord une présentation de l'algèbre proprement dite.

Comme on va le voir elle est très simple. Elle se base essentiellement sur trois opérations binaires.

Et puis dans la deuxième partie je montrerai comment ce type de representation facilite la définition d'une sémantique dénotationnelle pour des langages de type block-diagram.

2003-08-02T16:22:49