dino-lang / dino

The programming language DINO
GNU General Public License v2.0
71 stars 5 forks source link

Programming language Dino and its implementation

Develepment version of future release 0.98

Vladimir Makarov, vmakarov@gcc.gnu.org

Apr 2, 2016

Description Layout


Some history

The first taste of Dino

      var i, prime, k, count = 0, SieveSize = 8191, flags = [SieveSize : 1];
      for (i = 0; i < SieveSize; i++)
        if (flags[i]) {
          prime = i + i + 3;
          k = i + prime;
          for (;;) {
            if (k >= SieveSize)
              break;
            flags[k] = 0;
            k += prime;
          }
          count++;
        }
      putln (count);

DINO as a scripting language


Arrays and Tables


Array Slices

      var i, prime, count = 0, SieveSize = 8191, flags = [SieveSize : 1];
      for (i = 0; i < SieveSize; i++)
        if (flags[i]) {
          prime = i + i + 3;
          flags[i + prime:SieveSize:prime] = 0;
          count++;
        }
      putln (count);

Functions

      fun even;
      fun odd  (i) {i == 0 ? 0 : even (i - 1);}
      fun even (i) {i == 0 ? 1 : odd (i - 1);}
      putln (odd (1_000_000));
      filter (fun (a) {a > 0;}, v);
      fold (fun (a, b) {a * b;}, v, 1);
      fun incr (base) {fun (incr) {base + incr;}}

Threads

      fiber t (n) {for (var i = 0; i < n; i++) putln (i);}
      t(100); // the following code don't wait for t finish
      for (var i = 0; i < 1000; i++) putln (“main”, i);
      wait (cond) [stmt];

Object orientation

          class num (i) {fun print {put (i);}}
          class binop (l, r) { fun print_op;
            fun print {l.print(); print_op (); r.print ();}
          }
          class add (l, r) {
            use binop former l, r later print_op;
            fun print_op {put (“ + “);}
          }

Object orientation -- continuation


Object orientation -- continuation

      isa (add, binop);
      isa (add (num (1), num (2)), binop);
      obj int_pair {
        val min = 0, max = 10;
      }

Object orientation -- continuation

      obj sorts {
        var compare_fun;
        fun quick_sort (...) {...}
        fun heap_sort (...) {...}
      }
      ...
      sorts.fft (...);
      expose sorts.quick_sort;
      quick_sort (...);
      expose sorts.quick_sort (asort);
      asort (...);
      expose sorts.*;
      compare_fun = ...; quick_sort (...); heap_sort (...);

Standard spaces


Pattern matching


Pattern matching -- pmatch statement

    pmatch (v) {
      case [...]: putln ("array"); continue;
      case [a, ...]: if (a == 0) break; putln ("array with non-zero 1st element");
      case node (v) if v != 0: putln ("object of class node with nozero parameter");
      case _: putln ("any but array");
    }

Example: classes and functions with pattern matching

      class tree {}
      class leaf (i) {use tree;}
      class node (l, r) {use tree;}
      fun exists_leaf (test, t) {
        pmatch (t) {
          case leaf (v): return test (v);
          case node (l, r):
            return exists_leaf (test, l) || exists_leaf (test, r);
        }
      }
      fun has_odd_leaf (t) {
        exists_leaf (fun (n) {type (n) == int && n % 2 == 1;}, t);
      }

Regular expression matching -- rmatch statement

    rmatch (str) {
      case "[a-zA-Z]+": putln ("word starting at ", m[0]);
      case "[0-9]+": putln ("number starting at ", m[0]);
      case _: putln ("anything else, m is undefined");
    }

Exception handling

            class my_except (msg) {use except;}
            throw my_except ("my special exceptions");

Exception handling -- continuation

            try {
              var ln;
              for (;;) {
                var ln = getln (); putln (ln);
              }
            } catch (eof) { putln ("end of file"); }
            var ln;
            for (; try (ln = getln (), eof);) putln (ln);
            fun {try {ln = getln (); return 1;} catch (eof) {return 0;} ()

Earley parser


Earley parser -- tiny language example

expose yaep.*;
val grammar =
 "TERM ident=301, num=302, if=303, then=304, for=305, do=307, var=308;
  program = program stmt                     # list (0 1)
  stmt = ident '=' expr ';'                  # asgn (0 2)
       | if expr then stmt else stmt         # if (1 3 5)
       | for ident '=' expr expr do stmt     # for (1 3 4 6)
       | '{' program '}'                     # block (1)
       | var ident ';'                       # var (1)
       | error
  expr = expr '+' factor                     # plus (0 2)
  factor = factor '*' term                   # mult (0 2)
  term = ident                               # 0
       | '(' expr ')'                        # 1";
val p = parser ();       // create an Earley parser
p.set_grammar (grammar); // set grammar
fun syntax_error;        // forward decl of syntax error reporting func
val asbtract_tree = p.parse (token_vector, syntax_error);

Implementation -- General Structure

Dino Flow


Implementation -- Byte Code


Implementation -- Byte Code example

      var i, n = 1000;
      for (i = 0; i < n; i++);
      0 block fn="ex.d" ln=1 pos=1 next=730 vars_num=29 tvars_num=3 // ident=
      ...
      372 vdecl fn="ex.d" ln=1 pos=5 ident=i ident_num=268 decl_scope=0 var_num=27
      373 vdecl pos=8 ident=n ident_num=269 decl_scope=0 var_num=28
      ...
      788 ldi fn="ex.d" ln=1 pos=12 op1=28 op2=1000 // 28 <- i1000
      789 ldi ln=2 pos=10 next=791 op1=27 op2=0 // 27 <- i0
      790 btltinc pos=15 next=792 op1=27 binc_inc=1 bcmp_op2=28 bcmp_res=29 pc=790
                                          // goto 790 if 29 <- (27 += i1) cmp 28
      791 btlt pos=15 op1=27 bcmp_op2=28 bcmp_res=29 pc=790 // goto 790 if 29 <- 27 cmp 28
      792 bend pos=17 block=0

Implementation -- BC optimizations

            label: addi op1, op1, i1; lt res, op1, op2; bt res, label =>
            label: addi op1, op1, i1; blt res, op1, op2, label =>
            label: btltinc op1, op2, i2, res, label

Implementation


Implementation -- Continuation

            fun fact (n) !jit {n <=1 ? 1 : n * fact (n - 1);}

Implementation -- Type Inference


Implementation -- Type Inference 2


Implementation -- Type Inference 3


Implementation -- Tools and libraries


Implementation -- Profiling

      ** Calls *** Time **** Name **************************************
        761087     0.43  --  search1: "meteor.d": 229
        561264     0.07  --  ctz: "meteor.d": 28
          1260     0.01  --  GoodPiece: "meteor.d": 37
           ...
                   0.51  --  All Program
      ** Calls *** Time **** Name **************************************
        761087     0.15  --  search1: "meteor.d": 229
           ...
             0     0.00  --  ctz: "meteor.d": 28
           ...
                   0.17  --  All Program

Implementation -- C Interface

      extern v, f ();
      val_t f (int npars, val_t *args);

Implementation -- C Interface 2

      #include d_api.h
      ...
      val_t v;
      ...
      val_t f (int n_pars, val_t *args) {
        ER_node_t first_arg = (ER_node_t) &args[0];
        if (npars == 1 && ER_NODE_MODE (first_arg) == ER_NM_int)
      <do something with integer value> ER_i (first_arg);
    ...
      }

Implementation -- C Interface 3

      %{
        ...
        val_t f (int n_pars, val_t *args) {
          ...
        }
      %}
      extern f ();
      val r = f(10);

Code Metrics

    Totals grouped by language (dominant language first):
    sh:          265452 (54.10%)
    ansic:       194472 (39.64%)
    yacc:         23297 (4.75%)
    cpp:           7403 (1.51%)
    Totals grouped by language (dominant language first):
    sh:          161561 (62.13%)
    ansic:        95124 (36.58%)
    yacc:          3365 (1.29%)

Benchmarking -- Programs


Benchmarking -- Languages and CPUs


Benchmarking -- x86-64

Loop Hash Fact Fib Except Method Object Sieve Sort Stat. Random Thread Start Compile
Dino[^1] 1.0[^2] 1.0 1.0[^3] 1.0[^3] 1.0 1.0 1.0 1.0 1.0[^2] 1.0 1.0[^4] 1.0 1.0 1.0
Dino 19 1.0 13.2 112 1.0 1.0 1.0 1.0 1.4 1.0 3.1 1.0 1.0 1.0
Python 257 2.4 90.4 492 9.7 5.8 4.4 37.9 13.3 2.6 26.9 125 10.9 3.3
Ruby 157 2.2 25.2 142 5.5 1.5 1.4 4.5 4.5 3.5 12.4 43.6 29.4 1.8
PyPy 8.1 0.4 0.4 59 0.4 0.2 0.1 4.5 1.4 1.3 0.9 47.0 22.1 17.8
JS 151 1.4 33.3 211 - - - 5.5 0.6 - 0.5 - 1.1 0.8
Scala 9.6 1.6 2.8 147 60.3 1.2 0.7 2.4 0.7 9.4 1.2 - 352 -[^5]
Ocaml 34.4 1.0 5.2 69 0.3 0.5 0.8 1.8 1.8 3.2 2.2 - 5,3 283

[^1]: Dino best result. [^2]: Dino JIT hint was used. [^3]: Dino pure func hint was used. [^4]: Dino inline hint was used. [^5]: Scala can not even handle 10 times smaller code.


Benchmarking -- AARCH64

Loop Hash Fact Fib Except Method Object Sieve Sort Stat. Random Thread Start Compile
Dino[^1] 1.0[^2] 1.0 1.0[^3] 1.0[^3] 1.0 1.0 1.0 1.0 1.0[^2] 1.0 1.0[^4] 1.0 1.0 1.0
Dino 17.5 1.7 13.1 265 1.0 1.0 1.0 1.0 1.4 1.0 2.2 1.0 1.0 1.0
Python 222 0.5 68.8 1116 12.4 4.7 2.8 40.3 5.3 2.5 15.5 149 246 2.6
Ruby 170 2.8 32.3 542 6.0 1.7 1.4 8.5 3.7 3.8 13.1 118 655 1.6
JS 282 1.4[^6] 31.6 471 - - - 16.2 2.5 - 6.5 - 1.0 0.5
Ocaml 44.7 1.2 5.0 166 0.3 0.5 0.9 2.6 2.1 4.0 3.5 - 82.7 232

[^6]: Non-JIT JS was used as JIT failed.


Benchmarking -- ARM

Loop Hash Fact Fib Except Method Object Sieve Sort Stat. Random Thread Start Compile
Dino[^1] 1.0[^2] 1.0 1.0[^3] 1.0[^3] 1.0 1.0 1.0 1.0 1.0[^2] 1.0 1.0[^4] 1.0 1.0 1.0
Dino 4.2 1.0 18.1 490 1.0 1.0 1.0 1.0 1.8 1.0 2.5 1.0 1.0 1.0
Python 28.2 0.6 4.4 1600 11.7 3.4 5.1 19.3 6.7 2.2 17.5 157 10.9 2.7
Ruby 31.5 2.6 71.2 651 6.3 1.3 1.7 4.8 4.0 3.3 11.3 174 12.7 1.7
PyPy 103 1.4 151 4158 9.9 12.1 7.9 42.1 11.7 5.5 30.4 485 7.2 [^7]
JS 29.8 1.4[^6] 32.2 634 - - - 4.1 0.4 - 0.4 - 1.1 0.7
Scala 7.4 8.2 6.4 2396 6.9 1.2 1.0 5.8 0.7 19 1.2 - 109 [^7]
Ocaml 13.8 1.0 8.8 327 0.4 0.6 1.0 2.5 2.2 3.3 1.7 - 3.0 [^7]

[^7]: PyPy, Scala, and Ocaml failed to compile long code.


Benchmarking - PPC64

Loop Hash Fact Fib Except Method Object Sieve Sort Stat. Random Thread Start Compile
Dino[^1] 1.0[^2] 1.0 1.0[^3] 1.0[^3] 1.0 1.0 1.0 1.0 1.0[^2] 1.0 1.0[^4] 1.0 1.0 1.0
Dino 23.2 1.0 16.2 222 1.0 1.0 1.0 1.0 4.3 1.0 4.4 1.0 1.0 1.0
Python 182 1.5 51.0 965 15.1 3.6 4.1 29.8 7.5 2.0 15.7 160 5.1 5.0
Ruby 17.6 1.7 43.0 390 20.0 1.6 3.1 7.6 4.2 5.2 11.4 62.8 46.1 1.5
JS 27.0 3.0 53.8 453 - - - 14.2 2.8 - 4.6 - 2.7 0.7
Ocaml 33.2 1.8 5.4 133 0.3 0.4 1.5 3.7 2.6 4.8 3.9 - 4.4 360

Implementation - Conclusions


Future directions of research


Dino availability


Dino Building

      <dino-path>/configure --srcidir=<dino-path> --prefix=<install-path>
      <dino-path>/configure --srcidir=<dino-path> --prefix=<install-path> --enable-debug
      make
      make check
      cd DINO; make check
      make install