This document outlines writing Alucard, every expression written here is valid alucard, feel free to type along with the document into the Alucard REPL or a file that you can send over!
New concepts are introduced and iterated upon in later sections.
The file is a fully loadable version of this document
;; This is a comment!
;; All what you are about to see are valid expressions to writeThese are all valid numbers
12
3
4
4294967296This is how we make a constant declaration
(deflex important 5
"This is a very important value!")
;; we can use the value by just saying
important
;; In fact we can use many different symbols in our names
(deflex 『perectly-valid』 3
"This is a perfeclty-valid symbol!")
『perectly-valid』
(deflex √4 2)
√4Alucard supports full unicode in the names as the last few examples show. In fact most symbols are valid in identifiers, however the following have special meaning and thus can't be used in names
- ()
- '
- `
- ,
This section is for those who are curious about what these symbols mean. It is not necessary to know for the operation of Alucard.
() is function application, and thus we can't name symbols with it.
(+ 1 2 3 4)'unevaluated-symbol!
`also-unevaluatedThus ` and ' freeze values, but ` allows some extra behavior, with
,
(deflex evaluated 5)
`,evaluated
`(+ ,evaluated 10)Notice when we type this into the read eval print loop we get back out
(+ 5 10)!
That's because , undos the effect of '.
Lastly, one should avoid | in names
if one ran the last section then
|EVALUATED|should give back 5. This is because of how symbols are read, they
are case insensitive, thus
evaluated
Evaluated
EVALUATEDare all the same symbol, go and type it. |symbol| lets one make a
symbol case insensitive.
# also has a special meaning along with '. It is responsible for
turning a function symbol into a variable. More on that in the
integration section.
Symbols are typically written in dash-case. To illustrate our point
we will write some examples. We will use ' to just print back the
symbols given instead of getting the symbol value.
'normal-naming
'this-is-dash-case-reads-kind-nice!We were already writing expressions before with our numbers and symbols, but lets write some more complex expressions.
(+ 1 2)
(+ 1 2 3 4 5 6 7)
;; (+ 1 2 3 4 5 6 7)
;; ^ ^ ^
;; | | arguments |
;; |
;; The functionThe () here means begin a function call, with the first item between
the () standing for the function, and the rest of the contents
considered the arguments. We will often refer to the arguments like
"the first argument", to illustrate the point the following list will
make it more clear.
-
Expression: (+ 1 2 3 4 5 6 7)
-
The first argument = 1
-
The second argument = 2
-
The third argument = 3
-
The fourth argument = 4
-
The fifth argument = 5
-
The sixth argument = 6
-
The seventh argument = 7
One thing we'll notice if we run this expression is that we get a funky return value like
#<#<REFERENCE +> 1 2 3 #<#<REFERENCE *> 1 2 3>>, this is because
there does not exist a circuit interpreter to evaluate alucard
expressions as of yet, and so we return the intermediate
representation in the alucard language. However, don't let this
discourage you from experimenting with sending values to the REPL.
In many cases of doing basic arithmetic over constants we actually want to use normal addition, rather than the constraint version. We can do this by calling into the host language's (more on this later!) function.
;; Here we shoud get back 10!
(cl:+ 1 2 3 4)
;; 8 here!
(cl:+ 1 2 3 (cl:* 1 2))
(deflex vector-size 16
"The size of the vector for our blake2s compression function")
(deflex work-vector (cl:/ vector-size 2)
"work-vector-split")More examples on this integration later on.
Since Alucard compiles to vamp-ir, a zksnark system over plonkup, we can define custom gates. We can think of a gate as a function that takes and returns alucard values.
(defcircuit my-constraint-gate ((public input field)
(private secret-1 field)
(private secret-2 field)
(output bool))
(= input
(+ (* (exp secret-1 2)
5)
(* secret-2 7)
5)))Let us break down this example:
defcircuit declares that we wish to make a new gate. The first
argument to defcircuit is the name, which in this case is
my-constraint-gate.
My-constraint-gate acts like any of the + and * primitives we
were using earlier.
The second argument
((public input field)
(private secret-1 field)
(private secret-2 field)
(output bool))is the parameter list and output type declaration to
my-constraint-gate.
A good way to view the parameter declaration is as follows:
(privacy wire-name type)
where
privacycan either bepublicorprivate.wire-namecan be any valid identifiertypeis any defined type.
In our example, the input wires are input, secret-1, and
secret-2. With the two secrets being private.
The last piece of information is the return type in (output bool). any valid type can be used in place of bool.
The rest of the arguments (arguments after the second) are the body of the circuit. We can put any expression in the body. Thus the entire file outside of circuit declarations are fair game!
In this case we've placed the equation
input = = secret-1^2 * 5 + secret-2 * 7 + 5
where the input is constrained to be eual to the equation on the right. In alucard syntax we could have written this like
'(= input (+ (* (exp secret-1 2) 5) (* secret-2 7) 5))
;; Forming this much shorter Statement!
(defcircuit my-constraint-gate-again! ((public input field)
(private secret-1 field)
(private secret-2 field)
(output bool))
(= input (+ (* (exp secret-1 2) 5) (* secret-2 7) 5)))We can call our custom circuit much like we've been calling + and
*.
(my-constraint-gate 234 (exp 2 31) (* 5 27))
(defcircuit constrain-square ((public input field)
(private sec1 field)
(private sec2 field)
(output bool))
(and (my-constraint-gate input sec1 sec2)
(my-constraint-gate input sec1 (exp sec2 2)))) ; sec2^2 = sec2!If you've been following with editor integration, you should be able
to jump to the definition of my-constraint-gate and any value used
with the exception of local variables.
Alucard gives a way to name intermediate wires. This is useful when we
don't want to repeat ourselves. Let us rewrite constrain-square
using this mechanism
(defcircuit constrain-square% ((public input field)
(private sec1 field)
(private sec2 field)
(output bool))
(def ((constraint-1 (my-constraint-gate input sec1 sec2))
(constraint-2 (my-constraint-gate input sec1 (exp sec2 2))))
(and constraint-1 constraint-2)))We can see it with def, def can be viewed like
'(def ((local₁ value₁)
…
(localₙ valueₙ))
expression-with-local₁
…
expression-with-localₙ)where we bind each local to each value, along with a body where
the locals are lexically scoped over.
Looking at our actual example we've created some amount of repetition
(my-constraint-gate input sec1 some-sec2-expr).
Alucard itself can't really abstract this out, as it requires writing
a local function (closure) that has input and sec1 in
scope. However since Alucard is a DSL in CL, we can call into the
language to get rid of this pattern!
(defcircuit constrain-square%% ((public input field)
(private sec1 field)
(private sec2 field)
(output bool))
;; flet makes a normal function that will not show up in the
;; circuit!
(flet ((call-constraint (var-secret)
(my-constraint-gate input sec1 var-secret)))
(and (call-constraint sec2)
(call-constraint (exp sec2 2)))))Here we used flet which in Common lisp simply makes a function. In
our case we create the function call-constraint which takes the
argument var-secret and outputs the my-constraint-gate call that
we wanted to remove. Thus, constrain-square%% generates exactly the
same circuit as constrain-square!
The one caveat is that we can not return call-constraint, however
that is more due to the alucard language having no closure mechanism.
We will see more of the interplay between alucard and common lisp (hereby known as lisp) in a later section. For now we can view it as a relationship where repeat expressions in alucard can be abstracted away by lisp itself.
The last major building block of the current alucard version is the ability to define custom data types.
A good first example is the point type
(deftype point ()
(x field)
(y field))here we created the type point with a x and y field. Amusingly
enough the types of the record fields are themselves fields.
We can make a point like so
;; make a point with the x value being 3 and y value being 5.
(point :x 3 :y 5)We can access the fields of the record like so
(defcircuit point-constraint ((public point point)
(private var field)
(output bool))
(= var (+ (x point) (y point))))
(x (point :x 3 :y 5))The fields can be accessed by calling the field as a function on the
point itself.
It would be remiss not to note that functions, variables, and types all live in different namespaces.
This means the following example is completely fine and valid
(defcircuit make-point ((public pub-point point)
(private sec-point point)
(output point))
(def ((x (x pub-point))
(y (y pub-point)))
(point :x (+ x (x sec-point))
:y (+ y (y sec-point)))))notice how we have the local variable x and the function x which
grabs the x field off of the given point.
This concept also extends to types this is why in the
point-constraint example we are able to call a value of type
point, point.
Now it is time to talk about the common lisp (hereby known as lisp) integration with alucard. This is the feature with elevates alucard from being a low level language into a decently expressive language.
A good point to look at for integration, is that since alucard is just lisp syntax, we invoke lisp functions the same way as we've been seeing alucard functions execute!
That then begs the following questions:
- 『When is the lisp integration useful?』
- 『What are examples of lisp functions that are common in Alucard?』
- 『What are the limitations/barriers of this integration?』
The first question is answered by how we've used lisp integration in this syntax tutorial so far. Basically the lisp language is useful when there is a problem we can't elegantly solve with top level gates, local variable binding, nor structs.
This can range from:
- Repeat local patterns
- Wanting to derive constants
- Wanting to write the same pattern of code on
ndifferent wires.
The list can go on adinfinitium.
In this tutorial alone we've seen the first two bullet points be used.
As for the second question, we see the use of abstractions from lisp like:
deflexflet- constant numerical operations
- high level iterators
Yes, the deflex we've seen at the start of the tutorial is in fact
just a normal CL lexical variable definition.
The only point not shown off yet is the high level iterators point,
and so let us show off this feature!
We want to write a circuit which takes 4 point's. and computes some
constraint over them. We can break these points down into pairs, with
the first of the pair being the x-y plane the values represent, and
the second pair being a 2-d time point in which we represent time as a
two-dimensional value.
Thus we shall make the nested point. So that we only deal with two
arguments.
(deftype nested ()
(plane point)
(time point))(defcircuit constrain ((public nest-pub nested)
(private nest-priv nested)
(output bool))
(def ((plane (plane nest-pub))
(time (time nest-pub))
(plane-priv (plane nest-priv))
(time-priv (time nest-priv)))
(= 0
(+ (* (x plane)
(y plane))
(* (x time)
(y time))
(* (x time-priv)
(y time-priv))
(* (x plane-priv)
(y plane-priv))))))We can see that in our constrain circuit we wish to multiple the x-y
coordinates together, and adding them all together should equal zero.
We've already seen some techniques which can help the verbosity of this code.
(defcircuit constrain-2 ((public nest-pub nested)
(private nest-priv nested)
(output bool))
(flet ((multiply-points (point)
(* (x point)
(y point))))
(def ((plane (plane nest-pub))
(time (time nest-pub))
(plane-priv (plane nest-priv))
(time-priv (time nest-priv)))
(= 0
(+ (multiply-points plane)
(multiply-points time)
(multiply-points plane-priv)
(multiply-points time-priv))))))This is better, but we still see the huge pattern of calling the same function 4 times in a row. Thus we can golf this even further with a few high level iteration abstractions in lisp.
(defcircuit constrain-3 ((public nest-pub nested)
(private nest-priv nested)
(output bool))
(= 0 (apply #'+
(mapcar (lambda (point)
(* (x point)
(y point)))
(list (plane nest-pub)
(time nest-pub)
(plane nest-priv)
(time nest-priv))))))Here we used quite a few functions from CL. I should explain them all in full.
list simply puts the items into a list
;; make a list of 1 through 5!
(list 1 2 3 4 5)So we put all our wires into a list
'(list (plane nest-pub)
(time nest-pub)
(plane nest-priv)
(time nest-priv))Next, we use the function mapcar. We know this function from other
languages under the name map. In an invocation like, (map f list),
map applies f to every element in the list.
In this case we are applying lambda. Lambda is just a function with
no name, we could have just as easily said
(defcircuit constrain-4 ((public nest-pub nested)
(private nest-priv nested)
(output bool))
(labels ((multiply-points (point)
(* (x point)
(y point))))
(= 0 (apply #'+
(mapcar #'multiply-points
(list (plane nest-pub)
(time nest-pub)
(plane nest-priv)
(time nest-priv)))))))replacing the lambda with multiply-points. Note that we use
#'multiply-points as since functions and variables are in different
namespaces the language needs to know we are talking about the
function multiply-points.
Lastly we call (apply #'+ ...) on our list. All apply does is call
the given function on the given list, to illustrate the point, let us
write some examples
(apply #'cl:+ (list 1 2 3 4 5))
;; we get back 15.
(apply #'cl:* (list 1 2 3 4 5))
;; we get back 120.
;; we've practically made factorial!A good way to visualize it is to just move the ()'s over a bit
(apply #'cl:+ (list 1 2 3 4 5))
;; ==> (cl:+ 1 2 3 4 5)
(apply #'cl:* (list 1 2 3 4 5))
;; ===> (cl:* 1 2 3 4 )With these functions down, we can see how we got from constrain-2 to
constrain-3.
It is somewhat questionable if there is a huge readability boon
between constrain-2 vs constrain-3. with that said, when more
complex patterns show up in code, techniques like this can help you
reduce the complexity of your alucard code quite a bit.
In the future, when alucard has an array type, operations like map
which takes a function will be provided by easy to write lisp
functions rather than directly in alucard!
We shall end this interactive tutorial by telling you about various useful standard library functions.
NOTE we don't actually have this list compiled yet!
Happy hacking!