Qi-circuit - A domain specific language to create signal flow graphs

[chansey97]

Hello everyone,

I'm excited to share a package that I've recently developed, built on top of Qi, called Qi-circuit: https://github.com/chansey97/qi-circuit

Qi-circuit a domain-specific language designed for creating stream circuits; in some literature, they are also referred to as signal flow graphs. The main aim of this package is to reveal the connection between Qi and signal flow graphs.

A quick example of calculating the Fibonacci sequence by Qi-circuit.

#lang racket

(require qi)
(require "../qi-circuit-lib/circuit.rkt")

(define zero (stream-cons 0 zero))
(define one (~>> (zero) (c-reg 1)))

(define-flow sf
  (~>> (c-loop (~>> (== _ (c-reg 0))
                    (c-add +)
                    (c-loop (~>> (== _ (c-reg 0)) (c-add +) (-< _ _)))
                    (c-reg 0)
                    (-< _ _)))))

(define fib ((☯ sf) one)) 
(~>> (fib) (stream-take _ 20) stream->list)
;; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

I have written a tutorial about it, including many examples, such as integral, factorial, fibonacci, catalan numbers, and ODE. Each example contains a step-by-step diagram reasoning to transform a general circuit to Qi-circuit.

Give it a try and let me know what you think about. Any insights, suggestions, and criticism are highly appreciated.

Thanks!

[benknoble]

It seems to me that your definition of sf repeats the body a bit?

(define-flow sf
  (~>> (c-loop (~>> (== _ (c-reg 0))
                    (c-add +)
                    (c-loop (~>> (== _ (c-reg 0)) (c-add +) (-< _ _)))
                    (c-reg 0)
                    (-< _ _)))))

I wonder if that was intentional, and if so, why?

[chansey97]

Thanks for your feedback!

What do you mean by " sf repeats the body a bit?" ?

Note that the same stream function can have different circuits, but they are equivalent. For Fibonacci sequence, you might write a different circuit. The circuit in the example uses a general circuit for any rational stream.

More details, see qi-circuit/qi-circuit-examples/fibonacci.md at main · chansey97/qi-circuit · GitHub

[benknoble]

The pattern (~>> (== _ (c-reg 0) (c-add +) (-< _ _)) looks nested
within itself a bit, modulo an extra (c-reg 0) and placement of
threading.

[chansey97]

This is c-loop construct.

The (~>> (== _ (c-reg 0) (c-add +) (-< _ _)) is the sf in c-loop (blue dashed rectange), so it has two inputs and two outputs.

Maybe I misunderstood your question.

[chansey97]

I deleted the previous reply, which is a bit confusing; here is the updated answer.

For Fibonacci sequence, its generating function is F = \frac{X}{1 - X - X^2}.

We can derive the recursive equation F = X + F X + F X^2 from it.

One way to solve the recursive equation is to use stream algorithms, i.e.

(define F (stream-cons 0 (stream-cons 1 (map + F (stream-rest F)))))
(~>> (F) (stream-take _ 20) stream->list)
;; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

However, the recursive equation can also be represented as circuits.

For example,

It's obvious that it has two loops. However, there are many ways for solving the same recursive equation; this is just one of them. i.e. F = (X + F X) + F X^2.

As follows are other possible implementations:

F = (X + F X^2) + F X

F = (F X + F X^2) + X

F = (1 + F X + F) X

F = X + F (X + X^2)

Look the last one, which has only one loop. We can use the circuit as a template to create Qi-circuit.

(define fib
  (~>> (one)
       (c-reg 0)
       (c-loop (~>> (== _ (~>> (-< (c-reg 0) (~>> (c-reg 0) (c-reg 0))) (c-add +)))
                    (c-add +)
                    (-< _ _)))))

(~>> (fib) (stream-take _ 20) stream->list)
;; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

This answer your question "why there are two loops".

---

BTW, in the latest Qi-circuit, I added a new form c-loop-gen.

It can output signals without any input. Now, there's no longer to use a dummy input (such as zero) and >2 as was required previously.

The Fibonacci sequence can also be defined as follows:

F = (F + (FX + 1)) X

(define fib
  (~>> ()
       (c-loop-gen (~>> (c-reg 0) (-< _ (c-reg 1)) (c-add +) (-< _ _)))
       (c-reg 0)
       ))

(~>> (fib) (stream-take _ 20) stream->list)
;; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

This circuit seems more readable.

[robby]

All the talk of circuits and streams reminds me of the Lustre programming language. Do you guys know it? Here's how to implement fib in it:

node fib () returns (f: int);
let 
  f = 1 -> pre(f + (0 -> pre f));
tel

Here's a transcript of what running this in lv6 looks like:

$  lv6 -cc -2c -n fib fib.lus
W: fib_fib_loop.c has been generated.
W: fib_fib.h has been generated.
W: fib_fib.c has been generated.
+ '[' -z ']'
+ C_COMPILER=gcc
+ '[' -z ']'
+ MAIN_FILE=fib_fib_loop.c
+ gcc -o fib.exec lustre_consts.c fib_fib.c fib_fib_loop_io.c fib_fib_loop.c
fib_fib_loop.c:11:48: warning: passing arguments to 'fib_fib_ctx_new_ctx' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
    fib_fib_ctx_type* ctx = fib_fib_ctx_new_ctx(NULL);
                                               ^
1 warning generated.
sys call: 'sh fib.sh'

$  ./fib.exec 
#inputs 
#outputs "f":int
#step 1 
1
#step 2 
1
#step 3 
2
#step 4 
3
#step 5 
5
#step 6 
8
#step 7 
13
#step 8 
21
#step 9 
34
#step 10 
55
#step 11 
89
#step 12 
144

[chansey97]

Thank you for telling me the Lustre language. I read some articles online about Lustre, and it's very cool!

Inspired by Lustre , I added two new forms to Qi-circuit.

They correspond to -> and if then else in Lustre.

Now we can create more interesting circuits.

For example, the bistable switch:

(define (bistable-switch on off)
  (~>> (on off)
       ▽
       (c-loop (~>> (== △ (~>> (-< (gen false) (c-reg 0)) c-->))
                    (c-switch (% 3> _)
                              [_ (~>> 2> NOT)]
                              [else 1>])
                    (-< _ _)
                    ))))

In Lustre, it would be write

node Switch(on,off: bool) returns (s: bool);
let s = if(false -> pre s) then not off else on; tel

Qi-circuit seems more cumbersome than Lustre.

BTW, do you think Lustre is readable? or some one has to draw out the diagram for understanding? Qi-circuit at least maintains the shape of the circuit.

[chansey97]

Next task is adding Lustre's Clock to Qi-circuit.

But before that, I have to think about the issue of modularity. Currently Qi-circuit seems not suitable for modularization (e.g. the ODE example) because Qi is strict in Racket:

Note that this example also shows that you cannot treat integral as an independent component, because (c-reg y0) must be on the leftmost side of sf in the c-loop or c-loop-gen.

In other words, you often have to slide the c-reg to the left.

I haven't tried the same example with Arrow in Haskell, but it might be related. Naively use #lang lazy with list doesn't work at the moment, I have not explored deeply though.

Anyone has idea about it?

Thanks.

[robby]

@chansey97

BTW, do you think Lustre is readable? or some one has to draw out the diagram for understanding? Qi-circuit at least maintains the shape of the circuit.

I know only very little about Lustre. It is a storied programming language, however, dating back to the 1980s and with a lot of very serious people using it for safety-critical things and studying its properties and making it more and more robust. There is an annual meeting called Synchron where many of the people who go work full-time on Lustre and related things. I don't know if it has an industrial community, tho. That's an academic community. I'm guessing that they would welcome a presentation on your work if you can manage a trip to Europe and are intersted in talking with them. (I don't know an online way to connect to that community, however.)