Capturing abstractions in Lisp

I was skimming through SICP (after a pause) and I came across the chapter where Streams are discussed.

For those that have experience with JS Promises, Streams can be thought of as Promises. They allow us to make an illusion of infinity, e.g. all positive integers, by deferring evaluation.

For example, to generate all positive integers, we make a pair (1, next_int(1)), and then to evaluate the second member of that pair is (2, next_int(2)) and so on, for the nth number producing a list (1, (2, (…, (n, next_int(n))))) which will do n evaluations.

Here’s an implementation in Scheme that defines cons-stream (which will allow us to produce promises) and uses that to generate all integers infinitely (but not really, since all it does is just defer evaluation).

; delay needs to be a macro in order for the code to work correctly.
; Otherwise the invocation of delay will evaluate all its arguments eagerly.
(define-syntax delay
  (syntax-rules ()
    ((delay a)
     (lambda () a))))
; (defmacro delay (a) `(lambda () ,a))

; similarly for cons-stream
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
      (cons a (delay b)))))
; (defmacro cons-stream (a b) `(cons ,a (delay ,b)))

; force just evaluates
(define (force a) (a))

(define (next-integer x) (cons-stream x (next-integer (+ x 1))))

(define all-positive-integers (next-integer 0))

(define (integer-ref list i)
  (cond ((= i 0) (car list))
    (else (integer-ref (force (cdr list)) (- i 1)))))

; display 100th number:
(integer-ref all-positive-integers 100)

Looks and works pretty good!

Now, we can try doing the same in JS:

function force(x) {
    return x();
}
function cons_stream(a) {
    return function(b, c) {
        // this is delay basically but we can't abstract it in another method
        // since it will evaluate the params, so we need to use scope
        return function() {
            return [a].concat(b(c));
        }
    }
}

function next_integer(x) {
    return cons_stream(x)(next_integer, x+1);
}

function positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    var item;

    // evaluate initially
    list = force(list);

    while (j != 0) {
        // get the last item from the list (promise)
        item = list.pop();

        // append it in its evaluated form
        list = list.concat(force(item));

        j--;
    }

    // exclude last item since it's a new promise
    return list[list.length - 2];
}

var all_positive_integers = positive_integers();

// display 100th number:
console.log(integer_ref(all_positive_integers, 100));

The code is a bit longer, but it works equally good.

In JS we can achieve the same effect that the Lisp macro does by using scopes.

But in my opinion, Lisp’s syntax is more powerful with the ability to not evaluate parameters because it allows us to capture abstractions such as delay, whereas in JS we couldn’t do the same.

Closed-form expression of a recursive function

Let’s suppose, for the funs, that you go to the store and suddenly the manager tells you “For every 2 pieces of milk, you get 1 bonus.”

So you stop and think.
For 2 pieces, you end up having 3.
For 4 pieces, you end up having 2 as a bonus, and another one from that bonus 2 makes 4 + 2 + 1 = 7.
For 8 pieces, you end up having 4 as a bonus, and 2 from the bonus 4 and additional 1 from the bonus 2 makes 8 + 4 + 2 + 1 = 15.
You say, a great deal!

Note here that we don’t discuss the case where you don’t get bonus from the bonuses as that’s not hard to calculate.

Now let’s abstract “For every k pieces, you get 1 bonus” and we can start working our way to a closed-form expression.

This was my first attempt to solve it using recursion:

function calc(n, k) {
    if (n < k) {
        return n;
    }
    return n + calc(n / k, k);
}

Cool, let’s give that a try:

> calc(2, 2)
3
> calc(4, 2)
7
> calc(6, 2)
10.5

Seems to be working as expected.

In understanding what that does, let’s try to expand the first few terms manually.
n + (n/k) + (n/k)/k + ((n/k)/k)/k + … = n + n/k + n/k^2 + n/k^3 + … = s
This will proceed until one of the terms is less than k.
Then I went ahead and created a function that calculates the summation (using n/k as upper bound, which seems to be good enough):

/* This function represents the following summation
n/k
Σ n/k^i
i=0

*/
function calc2(n, k) {
    var sum = 0;
    var i;

    for (i = 0; i < n / k; i++) {
        sum += n / Math.pow(k, i);
    }

    return sum;
}

The next thing I did was run a delta check on various ranges to calculate abs(calc – calc2). It was 0.00015 after a few iterations, so seems good.
Now if we multiply s by (k – 1) we get s(k – 1) = nk – n + n – (n/k) + (n/k) + … which follows that s = nk/(k – 1). Note that I used infinity as the upper bound, as in the long run this wouldn’t matter much. It might be a little off for the first values, but eventually it should converge.

function calc3(n, k) {
    return n * k / (k - 1);
}

One thing to note is that the lesser k, the better. Otherwise, the limit as k -> Infinity is equal to just n.
If we now instantiate k to 2, we get n * 2, which means that you pay the milk at 50% discount (in the long run), which is a really good thing!

JavaScript Patterns overview

Chapter 1

Discusses the following types of patterns:

– Design patterns: singleton, factory, decorator
– Coding patterns: js related
– Antipatterns

Maintainable code is one that:

– Is readable
– Is consistent
– Is predictable
– Looks as if it was written by the same person
– Is documented

One of the general rules in the Gang of Four book says, “Prefer object composition to class inheritance.”. This means that if you can create objects out of available pieces you have lying around, this is a much better approach than creating long parent-child inheritance chains and classifications. In JavaScript it’s easy to follow this advice-simply because there are no classes and object composition is what you do anyway.

Antipattern: do not use. right-to-left evaluation

function foo() {
var a = b = 0;
// ...
}

Antipattern: implied global

function sum(x, y) {
result = x + y;  // The rule of thumb is to always declare variables using var
return result;
}

Antipattern: the first alert will say “undefined” because myname is considered declared as a local variable to the function.

myname = "global"; // global variable
function func() {
alert(myname); // "undefined"
var myname = "local";
alert(myname); // "local"
} func();

Antipattern: don’t augment prototypes because Object.prototype.hasOwnProperty doesn’t show prototype defs, only own

if (typeof Object.protoype.myMethod !== "function") {
Object.protoype.myMethod = function () {
// implementation...
};
}

In the following example, eval() can access and modify a variable in its outer scope, whereas Function cannot (also note that using Function or new Function is identical):

(function () {
var local = 1;
eval("local = 3; console.log(local)"); // logs 3
console.log(local); // logs 3 }());
(function () {
var local = 1;
Function("console.log(typeof local);")(); // logs undefined }());

warning: unexpected return value. need return and { to be on the same line. This behavior can cause troubles when a function returns an object literal and the opening brace is on the next line:

function func() {
return
{
name: "Batman"
};
}

For your constructors, you can use upper camel case, as in MyConstructor(), and for function and method names, you can use lower camel case, as in myFunction(), calculateArea() and getFirstName(). And what about variables that are not functions? Developers commonly use lower camel case for variable names, but another good idea is to use all lowercase words delimited by an underscore: for example, first_name, favorite_bands, and old_company_name.

Chapter 2

Don’t use new Object(); – use the simpler and reliable object literal instead (var x = { ... }).

When you invoke the constructor function with new, the following happens inside the function:

1. An empty object is created and referenced by this variable, inheriting the prototype of the function.
2. Properties and methods are added to the object referenced by this.
3. The newly created object referenced by this is returned at the end implicitly (if no other object was returned explicitly).

var Person = function (name) {
// create a new object
// using the object literal
// var this = {}; i.e. Object.create(Person.prototype);

// add properties and methods this.name = name;
this.say = function () {
return "I am " + this.name; };
// return this;
};

var Objectmaker = function () {
// this `name` property will be ignored
// because the constructor
// decides to return another object instead this.name = "This is it";
// creating and returning a new object
var that = {};
that.name = "And that's that";
return that;
};
// test
var o = new Objectmaker();
console.log(o.name); // "And that's that"

As can you see, you have the freedom to return any object in your constructors, as long as it’s an object. Attempting to return something that’s not an object (like a string or a boolean false, for example) will not cause an error but will simply be ignored, and the object referenced by this will be returned instead.

Chapter 3

> var a = function() { }
undefined
> a.name
''
> var a = function a() { }
undefined
> a.name
'a'
>

Chapter 4

Dependencies, this has faster resolution

var event = YAHOO.util.Event, dom = YAHOO.util.Dom;

The solution to this unexpected behavior is to be careful not to pass references to objects and arrays you want to keep private. One way to achieve this is to have getSpecs() return a new object containing only some of the data that could be interesting to the consumer of the object. This is also known as Principle of Least Authority (POLA), which states that you should never give more than needed. In this case, if the consumer of Gadget is interested whether the gadget fits a certain box, it needs only the dimensions. So instead of giving out everything, you can create getDimensions(), which returns a new object containing only width and height. You may not need to implement getSpecs() at all.

Another approach, when you need to pass all the data, is to create a copy of the specs object, using a general-purpose object-cloning function. The next chapter offers two such functions-one is called extend() and does a shallow copy of the given object (copies only the top-level parameters). The other one is called extendDeep(), which does a deep copy, recursively copying all properties and their nested properties.

var myobj = (function () { // private members
var name = "my, oh my";
// implement the public part return {
getName: function () {
return name; }
}; }());
myobj.getName(); // "my, oh my"

This example is also the bare bones of what is known as “module pattern,” which we examine in just a bit.

One drawback of the private members when used with constructors is that they are recreated every time the constructor is invoked to create a new object. This is actually a problem with any members you add to this inside of constructors. To avoid the duplication of effort and save memory, you can add common properties and methods to the prototype property of the constructor. This way the common parts are shared among all the instances created with the same constructor.

Gadget.prototype = (function () { // private member
var browser = "Mobile Webkit"; // public prototype members return {
getBrowser: function () {
return browser; }
}; }());

The module pattern is a combination of several patterns described so far in the book, namely:

– Namespaces
– Immediate functions
– Private and privileged members
– Declaring dependencies

var x = function(arg) {
if (!(this instanceof x)) {
console.log('Not a singleton, using constructor `' + arg + '`');
return new x(arg);
}
this.moo = arg;
}
var myobj1 = new x('using new');
var myobj2 = x('without new');
console.log(myobj1);
console.log(myobj2);

// constructor
var Gadget = function () {};
// a static method
Gadget.isShiny = function () { return "you bet"; };
// a normal method added to the prototype
Gadget.prototype.setPrice = function (price) { this.price = price; };
The static isShiny() is invoked directly on the constructor, whereas the regular method needs an instance:
// calling a static method
Gadget.isShiny(); // "you bet"
// creating an instance and calling a method
var iphone = new Gadget(); iphone.setPrice(500);

Sometimes it could be convenient to have the static methods working with an instance too. This is easy to achieve by simply adding a new method to the prototype, which serves as a facade pointing to the original static method:

Gadget.prototype.isShiny = Gadget.isShiny;
iphone.isShiny(); // "you bet"

In such cases you need to be careful if you use this inside the static method. When you do Gadget.isShiny() then this inside isShiny() will refer to the Gadget constructor function. If you do iphone.isShiny() then this will point to iphone.

var Gadget = (function () {
// static variable/property
var counter = 0;
// returning the new implementation // of the constructor
return function () { console.log(counter += 1); };
}()); // execute immediately

Chapter 5

Classical Pattern #1-The Default Pattern (prototype chain inheritance)

function inherit(C, P) {
C.prototype = new P();
}
var x = function() {}
var y = function() {}
y.prototype.a = b;
inherit(x, y);

lookup: x -> y -> y.prototype. Object #3 doesn’t have such a method, so it looks up to #2 via the prototype chain. Object #2 doesn’t have it either, so it follows the chain up to #1, which does happen to have it. One drawback of this pattern is that you inherit both own properties added to this and prototype properties. Most of the time you don’t want the own properties, because they are likely to be specific to one instance and not reusable.

Classical Pattern #2-Rent-a-Constructor

function Child(a, c, b, d) {
Parent.apply(this, arguments);
}

This way you can only inherit properties added to this inside the parent constructor. You don’t inherit members that were added to the prototype. But nothing from the prototype gets inherited.

Classical Pattern #3-Rent and Set Prototype

function Child(a, c, b, d) {
Parent.apply(this, arguments);
}
Child.prototype = new Parent();

A drawback is that the parent constructor is called twice, so it could be inefficient. At the end, the own properties (such as name in our case) get inherited twice.

Classical Pattern #4-Share the Prototype

Unlike the previous classical inheritance pattern, which required two calls to the parent constructor, the next pattern doesn’t involve calling the parent constructor at all. The rule of thumb was that reusable members should go to the prototype and not this. Therefore for inheritance purposes, anything worth inheriting should be in the prototype. So you can just set the child’s prototype to be the same as the parent’s prototype:

function inherit(C, P) {
C.prototype = P.prototype;
}

However if one child or grandchild somewhere down the inheritance chain modifies the prototype, it affects all parents and grandparents.

Classical Pattern #5-A Temporary Constructor

The next pattern solves the same-prototype problem by breaking the direct link between parent’s and child’s prototype while at the same time benefiting from the prototype chain. This pattern has a behaviour slightly different from the default pattern (classical pattern #1) because here the child only inherits properties of the prototype.

function inherit(C, P) {
var F = function () {};
F.prototype = P.prototype;
C.prototype = new F();
C.uber = P.prototype; // Store the super class
C.prototype.constructor = C; // If you don't reset the pointer to the constructor, then all children objects will report that Parent() was their constructor
}

A common optimization of the Holy Grail pattern is to avoid creating the temporary (proxy) constructor every time you need inheritance.

var inherit = (function () {
var F = function () {};
return function (C, P) {
F.prototype = P.prototype;
C.prototype = new F();
C.uber = P.prototype;
C.prototype.constructor = C;
}
}());

function f() {
var args = [].slice.call(arguments, 1, 3);
return args;
}
// example
f(1, 2, 3, 4, 5, 6); // returns [2,3]

function bind(o, m) {
return function () {
return m.apply(o, [].slice.call(arguments));
};
}

Chapter 6

function Universe() {
// do we have an existing instance?
if (typeof Universe.instance === "object") {
return Universe.instance;
}
// proceed as normal
this.start_time = 0; this.bang = "Big";
// cache
Universe.instance = this;
// implicit return:
return this;
}

Another way to do the class-like singleton is to use a closure to protect the single instance. You can implement this by using the private static member pattern discussed in Chapter 5. The secret sauce here is to rewrite the constructor:

function Universe() {
// the cached instance
var instance = this;
// proceed as normal
this.start_time = 0; this.bang = "Big";
// rewrite the constructor
Universe = function () {
return instance;
};
}

Patterns

Singleton

Creating only one object of a “class.” We looked at several approaches if you want to substitute the idea of a class with a constructor function and preserve the Java-like syntax. Otherwise, technically all objects in JavaScript are singletons. And also sometimes developers would say “singleton,” meaning objects created with the module pattern.

Factory

A method that creates objects of type specified as a string at runtime.

Iterator

Providing an API to loop over and navigate around a complex custom data structure.

Decorator

Tweaking objects at runtime by adding functionality from predefined decorator objects.

Strategy

Keeping the same interface while selecting the best strategy to handle the specific task (context).

Facade

Providing a more convenient API by wrapping common (or poorly designed) methods into a new one.

Proxy

Wrapping an object to control the access to it, with the goal of avoiding expensive operations by either grouping them together or performing them only when really necessary.

Mediator

Promoting loose coupling by having your objects not “talk” to each other directly but only though a mediator object.

Observer

Loose coupling by creating “observable” objects that notify all their observers when an interesting event occurs (also called subscriber/publisher or “custom events”).

Elegance of mathematical definitions

As I was working my way through “How To Prove It” by Daniel Velleman, I came across this definition in section 4.4 Ordering Relations:

Definition 4.4.4. Suppose R is a partial order on a set A, B A, and b B. Then b is called an R-smallest element of B (or just a smallest element if R is clear from the context) if x B(bRx). It is called an R-minimal element (or just a minimal element) if ¬∃x B(x Rb x ̸= b). 

The definition for R-smallest element was intuitive to me, all it says is that for all x in B, b <= x, i.e. b is smaller than any element in B given all of them are comparable.

The definition for R-minimal was a little trickier to me. Later in the book it’s shown that it’s equivalent to x B(x Rb x = bwhich is a bit easier to grasp, but still was not intuitive to me.

So the R-minimal is similar to R-smallest one, with the difference that it only applies to comparable elements, and uses xRb instead of bRx.

Given my programming background, I tried to come up with a more intuitive definition:
…b is called an R-minimal element if:
∀x, y ∈ B:
1. b R x (b <= x)
2. y R x (y <= x)
3. b R y or y R b (b <= y or y <= b, i.e. b and y are comparable)
Imply
b R y (b <= y)
This says that for any elements x and y, b will always be lower than those, given they are comparable.

This definition, although a bit larger than the original (elegant) one, made things clearer for me. But how can I verify if this definition is really equivalent to the original one? I tried to come up with a proof and had amnn from #haskell freenode to verify it for me (thanks!). Here’s the proof:

I. b is R-minimal if ∀x ∈ B: x R b → x = b
II. b is R-minimal if ∀x, y ∈ B: b R x ∧ y R x ∧ (b R y ∨ y R b) → b R y
R partial order: reflexive, antisymmetric, transitive.

Prove (or disprove) that I ↔ II.

(→): Suppose ∀x ∈ B: x R b → x = b.
Further suppose that y, z are arbitrary in B: b R y ∧ z R y ∧ (b R z ∨ z R b).
Prove that b R z.

Proof:
Case b R z: Holds trivially.
Case z R b: z = b → b R z.

(←): Suppose ∀x, y ∈ B: b R x ∧ y R x ∧ (b R y ∨ y R b) -> b R y.
Further suppose z is arbitrary in B: z R b.
Prove that z = b.

Proof:
Using universal instantiation, let x = b, y = z: b R b ∧ (z R b ∨ b R z) → b R z.
So given R is partial order (reflexive) we have b R b and we also have z R b from the givens.
With this, we can conclude b R z.
So since R is a partial order and thus antisymmetric,
from b R z and z R b we can conclude that b = z.

After spending some more time on thinking about the original definition, it is quite simple actually, because all it says that nothing is smaller than b. This definition is elegant in my opinion, because it “says” so much stuff with a few simple symbols. It is what inspired me to write this post.

Programming using logic assistants

What does a mathematician do? They play with theorems.

What does a smart mathematician do? Knows the theorems, but not necessarily remembers and knows all of them on top of their head. In fact, that’s probably impossible. They use proof assistants or logic programming languages.

I think a similar conclusion can be drawn for programmers.

At my current job, I get to work with different parts of a complex system constantly. I cannot and it is not expected from me to remember all the parts or decisions for the system, so often we need input from either Architecture or Product Managers. This is where communication jumps. We use JIRA/HipChat and other tools to ease our communication.

But I was thinking, what if we could use logic programming languages as our personal assistants to draw conclusions about decisions of the system’s behaviour?

Consider a complex system S, together with parts P = {P_1, P_2, ..., P_n}. Consider all possible inputs as I = {I_1, I_2, ..., I_n}. Each part might need different inputs. So we can state that f : P \to I. Consider we’re working on part P_k. So f(P_k) is the set of inputs needed for that part specifically, i.e. f(P_k) is a subset of I. All of the values in f(P_k) are unknown. But at some point in time, you get to know their values. And at this point is where you bring a decision.

We can take Prolog as an example. We start with an initial knowledge base, which probably explains some of the values of f(P_k), and as we get more and more input, we keep improving the knowledge until the point f(P_k) = \emptyset , i.e. no further input is required to bring a decision.

This is good because you get to re-use the knowledge base in the future, and also every time f(P_k) gets an update you can bring the conclusions based on that without going through recalling all the details, which saves a lot of time.

Most of the tasks are tiny and “easy” to go and evaluate the logic for through your mind, but once you get a lot of tasks you can’t remember every tiny detail about each one of them. This is what computers are for. 🙂