Welcome to the Tsonnet series!
In the previous post, cram tests were introduced:
Ready to add some math to our language? Let's dive into binary operations!
Adding arithmetic operations
Let's implement binary operations. More specifically, arithmetic operations.
Here's the sample file and the test:
diff --git a/samples/binary_operations.jsonnet b/samples/binary_operations.jsonnet
new file mode 100644
index 0000000..69fb074
--- /dev/null
+++ b/samples/binary_operations.jsonnet
@@ -0,0 +1 @@
+1 + 2 * 3 / 4 + 6 / 5 + 41
diff --git a/test/cram/binary_operations.t b/test/cram/binary_operations.t
new file mode 100644
index 0000000..3e075a5
--- /dev/null
+++ b/test/cram/binary_operations.t
@@ -0,0 +1,2 @@
+ $ tsonnet ../../samples/binary_operations.jsonnet
+ 44.7
If we run Jsonnet against the sample, the output will be:
$ jsonnet samples/binary_operations.jsonnet
44.700000000000003
You might be wondering why we got that funky 44.700000000000003 result. Well, here's a fun fact about computers -- they store decimal numbers in binary floating-point representation (typically IEEE 754). Some decimal numbers cannot be represented exactly in binary floating-point, leading to small rounding errors.
This isn't unique to Jsonnet -- many programming languages will have the same underlying behavior, though some may hide it by defaulting to a different display format that rounds the number for display purposes.
The AST expr now needs to accommodate a binary operation. It's composed of a binary operation and the left and right expressions:
diff --git a/lib/ast.ml b/lib/ast.ml
index 4ceb13d..326c6db 100644
--- a/lib/ast.ml
+++ b/lib/ast.ml
@@ -1,3 +1,9 @@
+type bin_op =
+ | Add
+ | Subtract
+ | Multiply
+ | Divide
+
type expr =
| Int of int
| Float of float
@@ -6,3 +12,4 @@ type expr =
| String of string
| Array of expr list
| Object of (string * expr) list
+ | BinOp of bin_op * expr * expr
Having the left and right nodes as expr allows it to nest multiple operations easily:
The AST for the operations 1 + 2 * 3 will look like this:
BinOp(Add)
/ \
Int(1) BinOp(Multiply)
/ \
Int(2) Int(3)
The lexing of arithmetic tokens is straightforwardly simple:
diff --git a/lib/lexer.mll b/lib/lexer.mll
index 585673b..cc77e85 100644
--- a/lib/lexer.mll
+++ b/lib/lexer.mll
@@ -30,6 +30,10 @@ rule read =
| '}' { RIGHT_CURLY_BRACKET }
| ',' { COMMA }
| ':' { COLON }
+ | '+' { ADD }
+ | '-' { SUBTRACT }
+ | '*' { MULTIPLY }
+ | '/' { DIVIDE }
| _ { raise (SyntaxError ("Unexpected char: " ^ Lexing.lexeme lexbuf)) }
| eof { EOF }
and read_string buf =
The parsing is where the mathematical semantics come in:
diff --git a/lib/parser.mly b/lib/parser.mly
index 2396dfe..7d6ea28 100644
--- a/lib/parser.mly
+++ b/lib/parser.mly
@@ -13,6 +13,9 @@
%token LEFT_CURLY_BRACKET
%token RIGHT_CURLY_BRACKET
%token COLON
+%token ADD SUBTRACT MULTIPLY DIVIDE
+%left ADD SUBTRACT
+%left MULTIPLY DIVIDE
%token EOF
%start <Ast.expr> prog
@@ -31,6 +34,10 @@ expr:
| s = STRING { String s }
| LEFT_SQR_BRACKET; values = list_fields; RIGHT_SQR_BRACKET { Array values }
| LEFT_CURLY_BRACKET; attrs = obj_fields; RIGHT_CURLY_BRACKET { Object attrs }
+ | e1 = expr; ADD; e2 = expr { BinOp (Add, e1, e2) }
+ | e1 = expr; SUBTRACT; e2 = expr { BinOp (Subtract, e1, e2) }
+ | e1 = expr; MULTIPLY; e2 = expr { BinOp (Multiply, e1, e2) }
+ | e1 = expr; DIVIDE; e2 = expr { BinOp (Divide, e1, e2) }
;
list_fields:
In the parser, we should specify that all arithmetic operations are left associative, but also that multiplication and division take precedence over addition and subtraction. In Menhir, tokens declared later have higher precedence than those declared earlier. This matches arithmetic rules where 1 + 2 * 3 is interpreted as 1 + (2 * 3).
Now that we can parse our operations, let's make them actually do something!
When it comes to the interpreter, it is about to increase in complexity:
diff --git a/lib/tsonnet.ml b/lib/tsonnet.ml
index 98ac680..69858a3 100644
--- a/lib/tsonnet.ml
+++ b/lib/tsonnet.ml
@@ -20,3 +20,31 @@ let rec print = function
Printf.sprintf "{%s}" (
String.concat ", " (List.map print_key_val attrs)
)
+ | _ -> failwith "not implemented"
+
+let interpret_bin_op op n1 n2 =
+ let float_op =
+ match op with
+ | Add -> (+.)
+ | Subtract -> (-.)
+ | Multiply -> ( *. )
+ | Divide -> (/.)
+ in match (n1, n2) with
+ | Int i1, Int i2 -> Float (float_op (Float.of_int i1) (Float.of_int i2))
+ | Float f1, Float f2 -> Float (float_op f1 f2)
+ | Float f1, Int e2 -> Float (float_op f1 (Float.of_int e2))
+ | Int e1, Float f2 -> Float (float_op (Float.of_int e1) f2)
+ | _ -> failwith "invalid operation"
+
+(** [interpret expr] interprets the intermediate AST [expr] into an AST. *)
+let rec interpret (e: expr) : expr =
+ match e with
+ | Null | Bool _ | String _ | Int _ | Float _ | Array _ | Object _ -> e
+ | BinOp (op, e1, e2) ->
+ let n1, n2 = interpret e1, interpret e2
+ in interpret_bin_op op n1 n2
+
+let run (s: string) : expr =
+ let ast = parse s in
+ let evaluated_ast = interpret ast in
+ evaluated_ast
In OCaml, integers and floats are not interchangeable types and due to that we have different arithmetic operators for them. Integers use the regular operator symbols as we know, but float equivalents are: +., -., *., and /.. This helps the compiler to optimize code and forces the programmers to always be aware of the numerical types they are manipulating. Even though it has its technical merits, it can become annoying quickly in a JS-like language, where the expectations are rather different.
To alleviate the annoyance, I'm cutting a corner and converting integers to float when doing arithmetic operations. Shouldn't be a big deal considering that, when doing division operations, we will invariably end up with a fractional number.
We can abstract integers and floats as numbers, to better represent the JSON abstraction. However, I'm postponing this to the next step. For now, the interpret_bin_op function is good enough.
So far, so good:
$ dune exec -- tsonnet samples/binary_operations.jsonnet
44.7
Wrapping up
Arithmetic operations are simple and straightforward binary operations to implement.
The interpret_bin_op function is ugly, I must admit. Wrapping Int and Float in a Number type may give us a better interface to parse Jsonnet code. Next time, we'll clean up that messy interpret_bin_op function by introducing a proper Number type. This won't just make our code cleaner -- it'll also set us up for the type checker I'm building towards!
See you in the next post!
Thanks for reading Bit Maybe Wise! Subscribe to receive news about Tsonnet.
Photo by Crissy Jarvis on Unsplash
Top comments (0)