TICS

What is the result of evaluating the following expression in Scheme?

If you answered 27, then think again. In actuality, this question does not make any sense, or partially at least. In Scheme, as well as in other programming languages, an expression is evaluated with respect to an environment that assigns values to its variables. In our example, this includes a and *.

But, what is an environment? There are several ways to explain and represent those, but let’s focus on the functional approach. Say is the finite set of all Scheme symbols, and is the set of all Scheme values, then an environment is a function:

That is, given a symbol that represents a variable, env returns a value for that variable. In an environment env₁ where the symbol x is associated or bound to the value 10, the straightforward expression:

is further evaluated to (+ env₁(x) 4), that is 14. Such an environment can be easily represented with a diagram:

Here, env_empty represents a function that returns an unspecified value, or rather, more commonly, raises an error for any symbol in the input. On top of that, env₁ simply augments env_empty with a new association or binding for x. Such extension implies the existence of another function:

extend_env takes an environment, symbols and values for some , and returns an environment that augments the initial with the new bindings. Environments are constructed by starting with env_empty, and repeatedly extending it with extend_env. In diagrams like the one above, the vertical arrows, created by the application of extend_env, relate an environment with its enclosing environment.

Note that, by definition of a function, a symbol cannot be bound to more than one value. This is quite interesting, for it is usual to extend an environment by including bindings for new and existing symbols. To illustrate this, if we want to extend env₁ with new bindings for y and z, we would have:

With this new environment env₂, the previous example expression is evaluated to (+ env₂(x) 4), which is still 14. The procedure works as follows:

• Starting from env₂(x), we look up the first binding for the symbol x in the sequence of frames (the colored boxes containing the associations).
• We eventually find a value for x or reach env_empty and get a nasty error. In the latter, we would say that x is unbound in env₂.

Now, we extend env₂ with a new binding for x:

In this last environment configuration, our expression is evaluated to (+ env₃(x) 4), but now the result is 23, not 14. We consciously shadowed the previous binding for x in env₁, retrieving 19 instead of 10.

Therefore, in our initial example:

If we evaluate it in an environment that shadows the symbol * to return (λ (x y) (+ ( * x y) 4)), then the result would be 31, not 27. Such is the importance of environments.

In a forthcoming article, we shall explain how this concept of environment can be used to implement lexical scoping through the creation of closures.

If you ever read Structure and Interpretation of Computer Programs, you will recall learning about nondeterministic computing, which is a fancy name for backtracking techniques. In section 4.3.2, there are a couple of typical problems for which these techniques are appropriate, the first being the resolution of logic puzzles, and the second a minimal implementation of a natural language parser. Let’s focus on the former. Years ago I remember solving a fun riddle written by Albert Einstein -don’t fret, nothing related to physics-, which I will show below, in case it doesn’t ring a bell. But first of all, I encourage anyone to try to solve it using only its logic skills, since it is a very rewarding experience, especially when its creator declared that “98% of the world population would not be able to solve it” (Image source: Public Domain)

The Riddle

1. In a town, there are five houses, each painted with a different color.
2. In every house leaves a person of different nationality.
3. Each homeowner drink a different beverage, smokes a different brand of cigar, and owns a different type of pet.

The Question

Who owns the fishes?

Hints

1. The Brit lives in a red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The Green house is next to, and on the left of the White house.
5. The owner of the Green house drinks coffee.
6. The person who smokes Pall Mall rears birds.
7. The owner of the Yellow house smokes Dunhill.
8. The man living in the center house drinks milk.
9. The Norwegian lives in the first house.
10. The man who smokes Blends lives next to the one who keeps cats.
11. The man who keeps horses lives next to the man who smokes Dunhill.
12. The man who smokes Blue Master drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blends has a neighbor who drinks water.

This seemed a bit of neat problem to solve using the material explained in the book, just for fun. We will use both helper procedures defined in the text:

and

Also, the houses will be abstracted using a constructor and several selector procedures. The constructor simply glues together the information related to a house:

The selectors are responsible for the extraction of the information of a house we are interested on:

Every house, in order to be eligible for a solution, must fulfill a set of rules as described in the hints list above, namely:

In addition, some of the rules are applicable only to the whole set of houses, for instance the positioning of the neighbors. To enforce those rules, the following helper procedure is defined:

index-of returns the number of the house whose value matches the argument. For example, (index-of ‘beer beverage-of the-houses) will return the number of the house in which the guy who drinks beer lives. This procedure is used by the actual procedure that deals with global restrictions:

Finally, the main procedure that implements the nondeterministic search:

This procedure might seem threatening, but it is quite easy to follow. For each generated house, we require that:

1. It complies with the rules enforced by the procedure required-rules.
2. Its items are different than those of the previous houses.

After the fifth house is generated, we apply require-global-rules to filter the final solutions that are returned as a value of einsteins-riddle.

Solving the Riddle

When we pass the expression (einsteins-riddle) to the underlying nondeterministic interpreter, the final and unique solution is computed and returned:

Or more viewable:

I wonder if this qualifies this program as part of that 2% the world population able to solve the Einstein’s Riddle…

Just to keep this pseudo-code handy, in case I need it in the future. My co-workers and I decided to replace our implementation of the Warshall’s Algorithm, which has O(n^3) temporal complexity, by a slightly more complicated one that will require O(n). This will make heavy use of memoization (aka tabulation), a well-known technique that allows us to maintain, in a table, values that were computed previously.

The algorithm

• Every item has an associated id.
• An item is a successor and an ancestor of itself.
• successors, ancestors, and status are global tables, indexed by item ID.
• status is initialized with all the nodes UNVISITED.
• The method resolve should be called per item.

successors < - [][]
ancestors <- [][]
status <- [][]

resolve(item : Item) : list of ID
  id <- item.id
  if status[id] is UNVISITED
    my_successors <- []
    status[id] <- VISITING
    for every successor in item.successors do
      successor_status <- status[successor.id]
      if successor_status is VISITING
        raise error "Circular dependency"
      end
      if successor_status is UNVISITED
        my_successors.add(resolve(successor))
      end
      if successor_status is VISITED
        my_successors.add(successors[successor.id])
      end
    end
    my_successors.add(id)  ;successor of itself

    for every successor in my_successors do
      successors[id].add(successor)
      ancestors[successor.id].add(id)
    end
    status[id] <- VISITED
  end
  return successors[id]
end

Results

• This algorithm loops over all the graph nodes, calculating its successors recursively.
• If a node has been already marked as visited, it returns the memoized value for its successors.
• The cycles in the graph dependency are detected.
• The current node being visited will be an ancestor of each of its successors.

Example

After processing the dependency graph with the algorithm, we end up having:

successors[A] -> [A, C, D, E, F, G, H]
successors[B] -> [B, C, D, E, F, G, H]
successors[C] -> [C, D, E, F, G, H]
successors[D] -> [D, F]
successors[E] -> [E, G, H]
successors[F] -> [F]
successors[G] -> [G]
successors[H] -> [H]

ancestors[A] -> [A]
ancestors[B] -> [B]
ancestors[C] -> [A, B, C]
ancestors[D] -> [D, A, B, C]
ancestors[E] -> [E, A, B, C]
ancestors[F] -> [F, D, A, B, C]
ancestors[G] -> [G, E, A, B, C]
ancestors[H] -> [H, A, B, C, E]

Yesterday, I gave at work a swift introduction to the JMM. Here.

Say we need to swap the values of two variables, a and b. This is a classic problem in programming and it can be accomplished in a few ways.

Using a temporary variable

This is the straightforward method; just use a temporary variable to avoid losing one of the variable values:

Accumulating one of the values

Use one of the variables to temporarily keep track of both variable values:

Using Exclusive-OR (XOR)

The exclusive-or binary operator takes two bits and returns 1 only if both values differ, 0 if equal:

The bitwise exclusive-or operator (^) will apply the exclusive-or operation on every pair of bits of the inputs.

   01100110
^  01011110
   --------
   00111000

Three interesting properties, given A, B = {0, 1}:

1. A XOR 0 = A (i.e. A XOR 0 returns A whatever A)
2. A XOR 1 = ~A (i.e. A XOR 1 returns A flipped)
3. (A XOR B) XOR B = A

The third property requires further explanation. On the one hand, if B is 0 then, by 1), applying XOR B twice to A returns A itself. On the other, if B is 1 then we are flipping A twice by 2), which winds up returning A itself.

We base our last method of swapping two (integer) variables on those three properties:

More formally, the computation:

is equivalent to:

At this point, B has the original value of A, therefore:

This last method is the most performant among them all.

Question

Now that we have sifted through these three methods of swapping two variables, question: which is the main advantage of the first over the others?