# 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 {
helper(tail(rem),
front_ptr));
}
}

if (is_empty_list(xs)) {
return [];
} else {
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) ||
set_tail(ys, mergeB(xs, tail(ys)));
return ys;
} else if (is_empty_list(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) {
}, 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() {
});

// 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 sieve(stream_filter(function() {
}, 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 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(
function() {
return interleave(
stream_map(function(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)) +
denoms);
}
}


### Power set

function power_set(xs) {
if (is_empty_list(xs)) {
return list([]);
} else {
// Either you pick the number,
// or you don't

}
}


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


Icon by Laymik from The Noun Project. Website built with ♥ with Org-mode, Hugo, and Netlify.