Closed PossibilityZero closed 5 days ago
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.
Apologies for the essay; this ended up being part debugging-notes, part solution explanation. The short version is that there were three problems:
member
function that only happens with the Source §2 interpreterlist("x")
) that deriv
can't handle.For a final version that works, skip to the bottom.
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
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));
}
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.
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");
The solution to the second problem of 2.58 (Symbolic Differentiation) has several syntax errors that prevent it from executing in the browser:
And after fixing the actual program fails with an error that I haven't debugged yet: