jdh30

Creating a new term-rewrite language

This article walks through the design and implementation of a simple but remarkably powerful new programming language that uses term rewriting as an evaluation model and, consequently, is well suited to computer algebra.

The term rewriter

We begin with the definition of an expression type Expr:

  type Expr =
    | Int of System.Numerics.BigInteger

jdh30

let mutable globalException : System.Exception = null // Compiler generated

let myGlobal =
  if isNull globalException then                      // Compiler generated
    try                                               // Compiler generated
      System.IO.File.ReadAllText "DoesNotExist.txt"
    with e ->                                         // Compiler generated
      globalException <- e                            // Compiler generated
      Unchecked.defaultof<_>                          // Compiler generated
  else Unchecked.defaultof<_>                         // Compiler generated

jdh30

open System.Windows

let goldenRatio = (1.0 + sqrt 5.0) / 2.0

let newBrush =
  let mutable hue = 0.0
  fun () ->
    hue <- hue + System.Math.PI / goldenRatio
    let s x = byte(255.0 * x)
    let c x = 0.5 * (cos x + 1.0)

jdh30

do
  use listener = new System.Net.HttpListener()
  listener.Prefixes.Add "http://localhost:8080/"
  listener.Start()
  while true do
    let context = listener.GetContext()
    async { use input = context.Request.InputStream
            use output = context.Response.OutputStream
            input.CopyTo output }
    |> Async.Start

jdh30

//
// async_tcp_echo_server.cpp
// ~~~~~~~~~~~~~~~~~~~~~~~~~
//
// Copyright (c) 2003-2012 Christopher M. Kohlhoff (chris at kohlhoff dot com)
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//

jdh30

#include "stdafx.h"

#include <windows.h>
#include <regex>
#include <vector>
#include <string>
#include <fstream>
#include <cstdio>
#include <codecvt>

jdh30

open System.Text.RegularExpressions
let str = System.IO.File.ReadAllText "C:\\Users\\Jon\\Documents\\pg10.txt"
let re = System.IO.File.ReadAllText "C:\\Users\\Jon\\Documents\\re.txt"
for _ in 1..3 do
  let timer = System.Diagnostics.Stopwatch.StartNew()
  let re = Regex(re, RegexOptions.Compiled)
  let res = Array.Parallel.init 4 (fun _ -> re.Split str |> Seq.sumBy (fun m -> m.Length))
  printfn "%A %fs" res timer.Elapsed.TotalSeconds

jdh30

[<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
type Tree = Empty | Node of Tree * Tree

let rec make depth =
  if depth=0 then Empty else Node(make (depth-1), make (depth-1))

let rec check = function
  | Empty -> 1
  | Node(l, r) -> 1 + check l + check r

jdh30

#include <algorithm>
#include <iostream>
#include <chrono>

struct Node {
	Node *l, *r;
	Node() : l(0), r(0) {}
	Node(Node* l2, Node* r2) : l(l2), r(r2) {}
	~Node() { delete l; delete r; }
	int check() const {

jdh30

; 20LOC to define a useful language
; However, no strings, IO, closure semantics or GC.

apply[fn;x;a] =
     [atom[fn] -> [eq[fn;CAR] -> caar[x];
                   eq[fn;CDR] -> cdar[x];
                   eq[fn;CONS] -> cons[car[x];cadr[x]];
                   eq[fn;ATOM] -> atom[car[x]];
                   eq[fn;EQ] -> eq[car[x];cadr[x]];
                   T -> apply[eval[fn;a];x;a]];