Skip to content

Instantly share code, notes, and snippets.

Avatar

Jonathan Harrop jdh30

View GitHub Profile
@jdh30
jdh30 / binarytrees.fs
Created May 9, 2019
Hans Boehm's binary trees benchmark in F#
View binarytrees.fs
[<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
jdh30 / binarytrees.cpp
Created May 9, 2019
Hans Boehm's binary trees benchmark in C++ using the default new+delete
View binarytrees.cpp
#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
jdh30 / gist:438afaed15d3bb7af3bfaedf54c4852b
Created Apr 28, 2019
McCarthy's definition of LISP 1.5 in itself
View gist:438afaed15d3bb7af3bfaedf54c4852b
; 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]];
@jdh30
jdh30 / Eddy.fs
Created Feb 28, 2019
Memory management benchmark - shedding Eddys
View Eddy.fs
(*
This benchmark maintains an array of roots and randomly either pushes
onto them and relinks them or empties them. If I designed it correctly
then this should rapidly create unreachable subgraphs, some of which
are cyclic.
This is a torture test for any kind of reference counting.
*)
type Vertex = { mutable Dst: Vertex }
@jdh30
jdh30 / promptness.fs
Last active Feb 28, 2019
A program for which prompt collection is practically impossible
View promptness.fs
(*
The resizable array xs is required for the first half of the execution of
this "test" function but not the last half. Collecting xs as early as possible
would mean collecting it halfway through the execution of "test" but this
is practically impossible. Doing so in general is equivalent to solving the
halting problem.
*)
let next n =
6364136223846793005UL*n + 1442695040888963407UL
@jdh30
jdh30 / JsonParser.fs
Last active Jun 11, 2021
Simple JSON parser written in F# using active patterns
View JsonParser.fs
type Json =
| Null
| Bool of bool
| Number of float
| String of string
| Array of Json list
| Object of (string * Json) list
type Bracket = Open | Close
@jdh30
jdh30 / ray.jl
Last active Sep 17, 2019
Ray tracer in Julia
View ray.jl
// Translated from the Ray Tracer Language Comparison
// http://www.ffconsultancy.com/languages/ray_tracer/benchmark.html
import Printf
struct Hit
l ::Float64
d ::Array{Float64, 1}
end
@jdh30
jdh30 / Q_rsqrt.fs
Last active Oct 13, 2018
Fast inverse sqrt in F#
View Q_rsqrt.fs
// The famous fast inverse square root approximation from
// Quake ported to F#.
// Note: this algorithm is not fast on modern computers
// and this implementation of it is extremely inefficient:
// for educational purposes only!
open System
let isqrt y =
let x2 = y * 0.5f
@jdh30
jdh30 / Camlp4LikeParser.fs
Created Mar 12, 2018
A parser definition in F# written in the style of a Camlp4 parser
View Camlp4LikeParser.fs
let reint = R(Regex "[0-9]+")
let relident = R(Regex "[a-z][a-zA-Z0-9]*")
let grammar : Grammar<Entry> =
[
Expr,
[ [ S"if"; C Expr; S"then"; C Expr; S"else"; C Expr ], fun [E p; E t; E f] -> E(If(p, t, f))
[ C Expr; S"<="; C Expr ], fun [E e1; E e2] -> E(BinOp(e1, Le, e2))
[ C Expr; S"+"; C Expr ], fun [E e1; E e2] -> E(BinOp(e1, Add, e2))
[ C Expr; S"-"; C Expr ], fun [E e1; E e2] -> E(BinOp(e1, Sub, e2))
@jdh30
jdh30 / SimpleParser1.fs
Created Mar 4, 2018
Port of an camlp4-based inline parser to vanilla ML
View SimpleParser1.fs
// See: https://gist.github.com/jdh30/6130c615b5945fd57fc0ea74fcb87e05
open System.Text.RegularExpressions
type BinOp = Add | Sub | Le
type expr =
| Int of int
| Var of string
| BinOp of expr * BinOp * expr