Jethro's Braindump

Programming Methodology

Source Specification

Predefined in global env: undefined, NaN, Infinity

fn description
Math.* Functions dealing with Math. (eg. Math.pow, Math.sqrt, Math.E, Math.PI)
parseInt(string) Takes a string and parses it into an integer.
equal(x,y) Returns true if x and y have the same structure, and the nodes are all identical. false otherwise.
is_number(x) Returns true if x is a number, false otherwise.

List

fn description I/R Time Space
is_pair(x) Returns true if x is a pair, false otherwise.
is_list(x) Returns true if x is a pair, false otherwise.
is_empty_list(x) Returns true if x is an empty list, false otherwise.
pair(x,y) Returns a pair of x and y.
head(p) Returns the head of a pair.
tail(p) Returns the tail of a pair.
set_head(p, n) Sets the head of pair p to n.
set_tail(p, n) Sets the tail of pair p to n.
list(x1,x2,...,xn) Returns a list of n elements. O(n) O(n)
length(xs) Returns the length of the list xs. I O(n) O(1)
map(f,xs) Returns a list with each element having f applied to it. R O(n) O(n)
build_list(n,f) Make a list of elements with unary function f applied to numbers 0 to n-1. R O(n) O(n)
for_each(f,xs) map, but use only for side effects. Returns true. I O(n) O(1)
list_to_string(xs) Returns string representation of list xs.
reverse(xs) Returns list xs in reverse order. I O(n) O(n)
append(xs,ys) Returns a list with list ys appended to list xs. R O(n) O(n)
member(x, xs) Returns first postfix sublist whose head is identical to x. I O(n) O(1)
remove(x, xs) Returns a list by removing the first item identical to x. R O(n) O(n)
remove_all(x,xs) Returns a list by removing all elements identical to x. R O(n) O(n)
filter(pred,xs) Returns a list containing only elements in xs for which pred returns true. R O(n) O(n)
enum_list(start,end) enum_list(0, 4) becomes [0, [1, [2, [3, [4, []]]]]]. R O(n) O(n)
list_ref(xs, n) Returns the element in xs at position n. I O(n) O(1)
accumulate(op, initial, xs) op(x1, op(x2, op(x3, ... op(xn, initial)))). R O(n) O(n)

Stream

fn description Lazy?
stream_tail(s) returns result of applying nullary function at tail. Y
is_stream(s) returns true if s is a stream, false otherwise. N
stream(x1,x2,...,xn) Returns a stream with n elements. N
list_to_stream(xs) Transforms a list into a stream. Y
stream_to_list(s) Transform a stream into a list. N
stream_length(s) Returns the length of the stream s. N
stream_map(f,s) Returns a stream from stream s by element-wise application of f. Y
build_stream(n,f) Makes a stream of n elements, by applying the unary function f to numbers 0 to n-1. Y
stream_for_each(f,s) Applies f to every element of the stream s, and returns true. N
stream_reverse(s) Returns a finite stream s in reverse order. N
stream_append(xs,ys) Returns a stream that results from appending ys to xs. Y
stream_member(x,s) Returns first postfix substream whose head is identical to x. P
stream_remove(x,s) Returns a stream that results from removing the first element identical to x from stream s. Y
stream_remove_all(x,s) Returns a stream that results from removing all elements identical to x from stream s. Y
stream_filter(pred,s) Returns a stream that contains only elements which return true on unary predicate pred. Y
enum_stream(start,end) Similar to enum_list. Y
integers_from(n) Constructs an infinite stream of integers starting at n. Y
eval_stream(s,n) Constructs a list of the first n elements of s. P
stream_ref(s,n) Returns the element of stream s at position n. P

Metacircular

fn description
evaluate(stmt,env) Classifies stmt and directs the evaluation. Handles primitive forms, special forms and combinations.
apply(fun, args) Primitive functions: calls apply_primitive_function. Compound functions: sequentially eval exps in new env created.
lookup_variable_value(var,env) returns value bound to the symbol var, or signals an error if unbound.
define_variable(var,value,env) adds to the first frame of env a binding of var to value.
extend_environment(variables,values,base_env) returns a new environment, with a new frame extended from base_env, with the corresponding variables and values.
set_variable_value(var,value,env) changes the binding of var in env to value, signals error if unbound.

Mutations

    function mutable_reverse(xs) {
      function helper(prev,xs) {
        return prev;
      } else {
        var rest = tail(xs);
        set_tail(xs, prev);
        return helper(xs,rest);
      }

      return helper([],xs);
    }

    function mutable_reverse(xs) {
      if (is_empty_list(xs) ||
          is_empty_list(tail(xs))) {
        return xs;
      } else {
        var temp = mutable_reverse(tail(xs));
        set_tail(tail(xs), xs);
        set_tail(xs,[]);
        return temp;
      }
    }
function make_circular_copy(xs) {
  function helper(rem, front_ptr) {
    if (is_empty_list(rem)) {
      return front_ptr;
    } else {
      return pair(head(rem), helper(tail(rem), front_ptr));
    }
  }

  if (is_empty_list(xs)) {
    return [];
  } else {
    var ys = pair(head(xs), []);
    set_tail(y, helper(tail(xs), ys));
    return ys;
  }
}
function mergeB(xs, ys) {
  if (is_empty_list(xs) && is_empty_list(ys)) {
    return [];
  } else if (is_empty_list(xs) || head(xs) <= head(ys)) {
    set_tail(ys, mergeB(xs, tail(ys)));
    return ys;
  } else if (is_empty_list(ys) || head(xs) >= head(ys)) {
    set_tail(xs, mergeB(tail(xs), ys));
    return xs;
  }
}

Permutations and Combinations

permutations

function permutations(xs) {
  if (is_empty_list(xs)) {
    return list([]);
  } else {
    return accumulate(
      function (e, acc) {
        return append(
          map(function (x) {
            return pair(e, x);
          }, permutations(remove(e, xs))),
          acc
        );
      },
      [],
      xs
    );
  }
}

n_permutations

function n_permutations(xs, n) {
  if (n === 0) {
    return list([]);
  } else {
    return accumulate(
      function (e, acc) {
        return append(
          map(function (x) {
            return pair(e, x);
          }, n_permutations(remove(e, xs), n - 1)),
          acc
        );
      },
      [],
      xs
    );
  }
}

n_combinations

function n_combinations(xs, n) {
  if (n === 0) {
    return list([]);
  } else if (is_empty_list(xs)) {
    return [];
  } else {
    return append(
      map(function (e) {
        return pair(head(xs), e);
      }, n_combinations(tail(xs), n - 1)),
      n_combinations(tail(xs), n)
    );
  }
}

OOP

function Vector2D(x, y) {
  this.x = x;
  this.y = y;
}

Vector2D.prototype.length = function () {
  return Math.sqrt(this.x * this.x + this.y * this.y);
};

function Thrust(x, y, tag) {
  Vector2D.call(this, x, y);
  this.tag = tag;
}

Thrust.Inherits(Vector2D);

Streams

Recursively defined streams

  function fibgen(a,b) {
    return pair(a,b function() {
      return fibgen(b, a+b);
    });
  }

  var ones = pair(1, function() {
    return ones;
  });

  var integers = pair(1, function() {
    return add_streams(integers, ones);
  });

  // Visualization:
  ones:     1 1 1 1 1 1
  integers:   1 2 3 4 5
  ---------------------
  integers: 1 2 3 4 5 6

Stream of primes

function sieve(s) {
  return pair(head(s), function () {
    return sieve(
      stream_filter(function () {
        return !is_divisible(x, head(s));
      }, stream_tail(s))
    );
  });
}

var primes = sieve(integers_from(2));

Iterations with streams

function improve_guess(guess, x) {
  return average(guess, x / guess);
}

function sqrt_iter(guess, x) {
  if (good_enough(guess, x)) {
    return guess;
  } else {
    return sqrt_iter(improve(guess, x), x);
  }
}

function sqrt(x) {
  return sqrt_iter(1.0, x);
}

function sqrt_stream(x) {
  var guesses = pair(1, function () {
    return stream_map(function (guess) {
      return improve(guess, x);
    }, guesses);
  });

  return guesses;
}

Interleave

function interleave(s1, s2) {
  return pair(head(s1), function () {
    return pair(head(s2), function () {
      return interleave(stream_tail(s1), stream_tail(s2));
    });
  });
}

Cartesian Product

function pairs(s1, s2) {
  if (is_empty_list(s1) || is_empty_list(s2)) {
    return [];
  } else {
    return pair(pair(head(s1), head(s2)), function () {
      return interleave(
        stream_map(function (x) {
          return pair(head(s1), x);
        }, stream_tail(s2)),
        pairs(stream_tail(s1), s2)
      );
    });
  }
}

Misc

Towers of Hanoi

function hanoi(disks, source, dest, aux) {
  if (disks === 0) {
    return [];
  } else {
    hanoi(disks - 1, source, aux, dest);
    display("Move disk from " + source + " to " + dest);
    hanoi(disks - 1, aux, dest, source);
  }
}

Count Change

// denoms is a list of coin denominations:
// eg. list(50,20,10,5)
function count_change(amt, denoms) {
  if (is_empty_list(denoms) || amt < 0) {
    return 0;
  } else if (amt === 0) {
    return 1;
  } else {
    return (
      count_change(amt, tail(denoms)) + count_change(amt - head(denoms), denoms)
    );
  }
}

Power set

function power_set(xs) {
  if (is_empty_list(xs)) {
    return list([]);
  } else {
    // Either you pick the number,
    // or you don't
    var without_head = power_set(tail(xs));
    var use_head = map(function (l) {
      return pair(head(xs), l);
    }, without_head);

    return append(use_head, without_head);
  }
}

Memoization

function memo_fib(n) {
  var res = {};
  res[1] = 0;
  res[2] = 1;
  function fib(n) {
    if (res[n] !== undefined) {
      return res[n];
    } else {
      res[n] = fib(n - 2) + fib(n - 1);
      return res[n];
    }
  }

  return fib(n);
}

Environment Model

function make_withdraw(balance) {
  return function (amount) {
    if (balance >= amount) {
      balance = balance - amount;
      return balance;
    } else {
      return "Insufficient Funds";
    }
  };
}
// Pic 1
var w = make_withdraw(100); // Pic 2
w(50); // Pic 3
// Pic 4

Metacircular Interpreter

Reverse Application Order

  function list_of_values(exps.env) {
    if (no_operands(exps)) {
      return [];
    } else {
      var r = list_of_values(rest_operands(exps),
                             env);
      return pair(evaluate(first_operand(exps),
                           env),
                  r);
    }
  }

Thunking

function list_of_values(exps, env) {
  if (no_operands(exps)) {
    return [];
  } else {
    return pair(
      make_thunk(first_operand(exps), env),
      list_of_values(rest_operands(exps), env)
    );
  }
}

function make_thunk(expr, env) {
  return {
    tag: "thunk",
    expression: expr,
    environment: env,
  };
}

function force(v) {
  if (is_thunk(v)) {
    return force(evaluate(thunk_expression(v), thunk_environment(v)));
  } else {
    return v;
  }
}

function lookup_variable_value(variable, env) {
  function env_loop(env) {
    if (is_empty_environment(env)) {
      error("Unbound Variable");
    } else if (has_binding_in_frame(variable, first_frame(env))) {
      var val = force(first_frame(env)[variable]);
      first_frame(env)[variable] = val;
      return val;
    } else {
      return env_loop(enclosing_environment(env));
    }
  }

  var val = env_loop(env);
  return val;
}