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;
  }