Multiple syntax errors in solution to 2.58

[PossibilityZero]

The solution to the second problem of 2.58 (Symbolic Differentiation) has several syntax errors that prevent it from executing in the browser:

• Unclosed parentheses on Line 22 (items_after_first)
• Unclosed/redundant parentheses on Line 37 (is_sum)
• Unclosed parentheses on Line 59 (is_product)

And after fixing the actual program fails with an error that I haven't debugged yet:

Line 136: Expected string on right hand side of operation, got number.

[PossibilityZero]

Noticed another problem, this time in the text:

The example given for part 2 is:

list("x", "+", "3", "*", list("x", "+", "y", "+", 2))

The 3 should not have quotation marks, it will be treated as a variable and not a number.

[PossibilityZero]

Apologies for the essay; this ended up being part debugging-notes, part solution explanation. The short version is that there were three problems:

1. Simple syntax errors with unmatched parentheses
2. A problem with the built in member function that only happens with the Source §2 interpreter
3. A logic error in the current solution, where the selectors return single-item lists (eg. list("x")) that deriv can't handle.

For a final version that works, skip to the bottom.

---

Problem 1

We start off with SyntaxError. This is due to several unmatched parentheses.

Here is the currently provided solution, with just the SyntaxErrors fixed (plus one added display_list(exp) call in deriv to assist in debugging):

function is_variable(x) { return is_string(x); }

function is_same_variable(v1, v2) {
    return is_variable(v1) && is_variable(v2) && v1 === v2;
}

function number_equal(exp, num) {
    return is_number(exp) && exp === num;
}

function items_before_first(op, s) {
    return head(s) === op
           ? null
           : pair(head(s),
                  items_before_first(op, tail(s)));
}
function items_after_first(op, s) {
    return head(s) === op
           ? tail(s)
           : items_after_first(op, tail(s));
}
function make_sum(a1, a2) {
    return number_equal(a1, 0)
           ? a2
           : number_equal(a2, 0)
             ?  a1
             : is_number(a1) && is_number(a2)
               ? a1 + a2
               : list(a1, "+", a2);
}
// a sequence of terms and operators is a sum
// if and only if at least one + operator occurs
function is_sum(x) {
    return is_pair(x) &&
           ! is_null(member("+", x));
}
function addend(s) {
    return items_before_first("+", s);
}
function augend(s) {
    return items_after_first("+", s);
}
function make_product(m1, m2) {
    return number_equal(m1, 0) || number_equal(m2, 0)
           ?  0
           : number_equal(m1, 1)
             ? m2
             : number_equal(m2, 1)
               ?  m1
               : is_number(m1) && is_number(m2)
                 ? m1 * m2
                 : list(m1, "*", m2);
}
// a sequence of terms and operators is a product
// if and only if no + operator occurs
function is_product(x) {
    return is_pair(x) && is_null(member("+", x));
}
function multiplier(s) {
    return items_before_first("*", s);
}
function multiplicand(s) {
    return items_after_first("*", s);
}
function deriv(exp, variable) {
    display_list(exp);
    return is_number(exp)
        ? 0
        : is_variable(exp)
          ? (is_same_variable(exp, variable) ? 1 : 0)
          : is_sum(exp)
            ? make_sum(deriv(addend(exp), variable),
                       deriv(augend(exp), variable))
            : is_product(exp)
              ? make_sum(make_product(multiplier(exp),
                             deriv(multiplicand(exp),
                                   variable)),
                         make_product(deriv(multiplier(exp),
                                            variable),
                             multiplicand(exp)))
              : error(exp, "unknown expression type -- deriv");
}

deriv(list("x", "*", 4), "x");

In the browser interpreter, this fails with Line 136: Expected string on right hand side of operation, got number

Problem 2

This took me forever to track down, but I figured out that the problem is in the builtin function member. Basically, when member checks items in a list, it compares the test value to each item. However, because this problem specifically uses Source §2, comparisons between string types and non-string types are disallowed. This is a problem with Source §2 specifically; run the above code in Source §3 or §4 and we actually run into a different error: Line 14: Error: head(xs) expects a pair as argument xs, but encountered null (we'll deal with this separately in the next section).

It appears that the interpreter is locked based on the chapter. To get the desired functionality of checking for "+" in a list, we need a custom implementation of member, which makes type checks first before comparing two values. Because this code only ever checks for the string "+" in this code, this is fairly trivial. Add the following snippet:

function contains_plus(s) {
    return is_null(s)
        ? false
        : is_string(head(s)) && head(s) === "+"
        ? true
        : contains_plus(tail(s));
}

and replace the calls is_null(member("+", x)) in is_sum and is_product as follows:

function is_sum(x) {
    return is_pair(x) && contains_plus(x);
}

function is_product(x) {
    return is_pair(x) && ! contains_plus(x);
}

Running the code, we now get Line 14: Expected number on right hand side of operation, got string. This looks similar, and is indeed the same problem: inside items_before_first (and also items_after_first) we are checking head(s) === op without first confirming that head(s) is a string.

function items_before_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? null
           : pair(head(s),
                  items_before_first(op, tail(s)));
}
function items_after_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? tail(s)
           : items_after_first(op, tail(s));
}

---

Problem 3:

If we run what we've fixed so far in either a local JS environment or either Source §3 or Source §4 on sourceacademy, we get something like this: Line 14: Error: head(xs) expects a pair as argument xs, but encountered null

Running it locally with Node to get a proper stack trace:

% node debug.js
list("x", "*", 4)
list(4)
.../node_modules/sicp/dist/stdlib/list.js:35
        throw new Error('head(xs) expects a pair as argument xs, but encountered ' + (0, stringify_1.stringify)(xs));
              ^

Error: head(xs) expects a pair as argument xs, but encountered null
    at head (.../node_modules/sicp/dist/stdlib/list.js:35:15)
    at items_before_first (.../debug.js:18:12)
    at items_before_first (.../debug.js:21:19)
    at multiplier (.../debug.js:66:12)
    at deriv (.../debug.js:81:39)
    at deriv (.../debug.js:82:30)
    at .../debug.js:90:1
    at ModuleJob.run (node:internal/modules/esm/module_job:197:25)
    at async Promise.all (index 0)
    at async ESMLoader.import (node:internal/modules/esm/loader:337:24)

We can see from the debug output that the last call to deriv() was with exp=list(4). This is what caused the error, as list(4) (in Pair notation: (4, null)) is an invalid input as the deriv() function is currently written.

There are actually two ways of looking at the problem. One is that deriv should handle single-term lists, as algebraically it's just the equivalent of having a parentheses around some term.

This could be done relatively simply by adding a check at the beginning:

function deriv(exp, variable) {
    return is_pair(exp) && length(exp) === 1    // check if the expression is a list of length 1
           ? deriv(head(exp), variable)
           : is_number(exp)
...

However, the problems in this chapter all give the constraint that deriv should not be modified. Seeing as deriv is directly lifted from the Lisp version, I think it's okay to adhere to this constraint.

We take the second approach to the problem: our predicates, selectors, and constructors should never return inputs to deriv that would cause it to fail. For this case specifically, this means that they must not return single-term lists.

make_sum and make_product already this by explicitly only returning multi-term lists or literals. However in the current implementation, the selectors addend, augend, multiplier, and multiplicand return a slice of a list, which can be a single item long.

Here is my proposed fix: add a new function simplify_unary_list which takes a term and, if it is a single-term list, returns just the term. This will act as a filter for all the selectors, and ensure that deriv does not receive input that it cannot handle.

function simplify_unary_list(s) {
  return is_pair(s) && is_null(tail(s))
      ? head(s)
      : s;
}

function addend(s) {
    return simplify_unary_list(items_before_first("+", s));
}
function augend(s) {
    return simplify_unary_list(items_after_first("+", s));
}
function multiplier(s) {
    return simplify_unary_list(items_before_first("*", s));
}
function multiplicand(s) {
    return simplify_unary_list(items_after_first("*", s));
}

Finally, running this with Source §2, it works as expected.

Summary

Here is the final version; it can be copy / pasted and executed in the Source Academy Source §2 interpreter. I've tested it with more complex inputs as well, and as far as I can tell it's a robust solution.

// SICP JS 2.3.2

function is_variable(x) { return is_string(x); }

function is_same_variable(v1, v2) {
    return is_variable(v1) && is_variable(v2) && v1 === v2;
}

function number_equal(exp, num) {
    return is_number(exp) && exp === num;
}

function items_before_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? null
           : pair(head(s),
                  items_before_first(op, tail(s)));
}
function items_after_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? tail(s)
           : items_after_first(op, tail(s));
}
function simplify_unary_list(s) {
  return is_pair(s) && is_null(tail(s))
      ? head(s)
      : s;
}
function contains_plus(s) {
    return is_null(s)
        ? false
        : is_string(head(s)) && head(s) === "+"
        ? true
        : contains_plus(tail(s));
}
function make_sum(a1, a2) {
    return number_equal(a1, 0)
           ? a2
           : number_equal(a2, 0)
             ?  a1
             : is_number(a1) && is_number(a2)
               ? a1 + a2
               : list(a1, "+", a2);
}
// a sequence of terms and operators is a sum
// if and only if at least one + operator occurs
function is_sum(x) {
    return is_pair(x) && contains_plus(x);
}
function addend(s) {
    return simplify_unary_list(items_before_first("+", s));
}
function augend(s) {
    return simplify_unary_list(items_after_first("+", s));
}
function make_product(m1, m2) {
    return number_equal(m1, 0) || number_equal(m2, 0)
           ?  0
           : number_equal(m1, 1)
             ? m2
             : number_equal(m2, 1)
               ?  m1
               : is_number(m1) && is_number(m2)
                 ? m1 * m2
                 : list(m1, "*", m2);
}
// a sequence of terms and operators is a product
// if and only if no + operator occurs
function is_product(x) {
    return is_pair(x) && ! contains_plus(x);
}
function multiplier(s) {
    return simplify_unary_list(items_before_first("*", s));
}
function multiplicand(s) {
    return simplify_unary_list(items_after_first("*", s));
}
function deriv(exp, variable) {
    return is_number(exp)
        ? 0
        : is_variable(exp)
          ? (is_same_variable(exp, variable) ? 1 : 0)
          : is_sum(exp)
            ? make_sum(deriv(addend(exp), variable),
                       deriv(augend(exp), variable))
            : is_product(exp)
              ? make_sum(make_product(multiplier(exp),
                             deriv(multiplicand(exp),
                                   variable)),
                         make_product(deriv(multiplier(exp),
                                            variable),
                             multiplicand(exp)))
              : error(exp, "unknown expression type -- deriv");
}

deriv(list("x", "*", 4), "x");