Stepper: head/tail applied to non-pair crash the stepper

[mug1wara26]

js-slang/docs/lib/list.js

Lines 240 to 248 in 56d8d6b

	function append(xs, ys) {
	return $append(xs, ys, xs => xs);
	}
	function $append(xs, ys, cont) {
	return is_null(xs)
	? cont(ys)
	: $append(tail(xs), ys, zs => cont(pair(head(xs), zs)));
	}

The append function does not type check if the input list is even a list, when I run the following line of code on source academy:

append(1, 1);

An error from the tail function is thrown
Line 121: Error: tail(xs) expects a pair as argument xs, but encountered 1
This is because in lists.ts,

js-slang/src/stdlib/list.ts

Lines 48 to 54 in 56d8d6b

	export function tail(xs: any) {
	if (is_pair(xs)) {
	return xs[1]
	} else {
	throw new Error('tail(xs) expects a pair as argument xs, but encountered ' + stringify(xs))
	}
	}

tail checks if the input is a pair, since 1 is not a pair, an error is thrown. The append function should also check if the input is a list, and throw an error if not, to prevent confusion. Furthermore when the code is run in the stepper, it crashes.

e.explain is not a function

61881/t.parseError/<@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:65:19233
61881/t.parseError@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:65:19068
g@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:2:66025
vo@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1855344
xc@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1914997
Al@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1904105
yl@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1904033
vl@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1903894
ol@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1900674
ll@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1901065
Ui@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1841655
34463/il/<@https://sourceacademy.nus.edu.sg/static/js/main.977a6c4b.js:124:1898607

Another issue is that the append function also does not check if the second parameter is a list, it simply replaces the null at the end of a list with the second parameter, thus append(list(1), 1) returns pair(1,1).

Since this is being written in typescript, why isnt type checking done in the function definition in the first place?

[martin-henz]

It is legit for append to call tail if the argument structure is not null. The functions head and tail is designed to give a nice error if the argument is not a pair, and OP gives the implementation of tail. With a bit of programming experience using lists, the programmer quickly learns that the error "head/tail(xs) expects a pair as argument xs" results from using something that is not a list in a place where lists are expected.

Of course the stepper must not crash, so that's a problem in the stepper that we need to fix. Minimal example to crash the stepper:

head(0);

[martin-henz]

Regarding the question:

Another issue is that the append function also does not check if the second parameter is a list, it simply replaces the null at the end of a list with the second parameter, thus append(list(1), 1) returns pair(1,1).

Since this is being written in typescript, why isnt type checking done in the function definition in the first place?

The reason is that the runtime for checking if a value is a list has an order of growth Theta(n) where n is the length of a list. Note that SICP JS is written using JavaScript, not TypeScript. Generally, we don't check the types of arguments in SICP JS for the sake of simplicity of the resulting programs. Yes, the append function will produce something that is not a list if the first argument is a list and the second argument is not a list. We accept this as an unintended consequence of the way append works.

[mug1wara26]

It is legit for append to call tail if the argument structure is not null. The functions head and tail is designed to give a nice error if the argument is not a pair, and OP gives the implementation of tail. With a bit of programming experience using lists, the programmer quickly learns that the error "head/tail(xs) expects a pair as argument xs" results from using something that is not a list in a place where lists are expected.

Sure with some experience with this language, it can be clear that somewhere in the code I am using list functions on non list data types, but that is not immediately obvious when someone first encounters the issue like I did yesterday. The first response is immediate confusion over why a random line not in the program is producing this issue, which is not ideal.

Secondly even if a programmer knows that they are accidentally introducing non list values to a list function, it may not be clear which line is producing this error and why. This can be troublesome in large programs or when using recursive functions and some cases are not properly taken care of, the other bug that tail(1) crashes the stepper makes this even harder to figure out.

I think that the append function should at least catch the error thrown by the tail function and throw it back so that the error message is more clear. Or it can check if the input is a number, which should be O(1).

[mug1wara26]

Also its not just programs that error like head(0) that causes the stepper to crash, I was playing with an iterative version of tree_sum which does not error and it still crashes the stepper with the same error message

function tree_sum(tree) {
    function iter(sub_tree, stack, sum) {
        if (is_null(sub_tree)) {
            if (is_null(stack)) {
                return sum;
            }
            else {
                return iter(head(stack), tail(stack), sum);
            }
        }
        else {
            if (is_number(sub_tree)) {
                return iter(null, stack, sum + sub_tree);
            }
            else {
                return iter(head(sub_tree), pair(tail(sub_tree), stack), sum);
            }
        }
    }
    
    return iter(null, tree, 0);
}

tree_sum(list(1));

I could investigate what exactly causes the error later on

[martin-henz]

It is legit for append to call tail if the argument structure is not null. The functions head and tail is designed to give a nice error if the argument is not a pair, and OP gives the implementation of tail. With a bit of programming experience using lists, the programmer quickly learns that the error "head/tail(xs) expects a pair as argument xs" results from using something that is not a list in a place where lists are expected.

Sure with some experience with this language, it can be clear that somewhere in the code I am using list functions on non list data types, but that is not immediately obvious when someone first encounters the issue like I did yesterday. The first response is immediate confusion over why a random line not in the program is producing this issue, which is not ideal.

Secondly even if a programmer knows that they are accidentally introducing non list values to a list function, it may not be clear which line is producing this error and why. This can be troublesome in large programs or when using recursive functions and some cases are not properly taken care of, the other bug that tail(1) crashes the stepper makes this even harder to figure out.

I think that the append function should at least catch the error thrown by the tail function and throw it back so that the error message is more clear. Or it can check if the input is a number, which should be O(1).

I agree with you wholeheartedly. I think starting with a typed language such as TypeScript would solve the problem. SICP JS follows SICP in its use of an untyped (better: dynamically typed) language.

There we have a dilemma: Do we complicate all our functions to make sure they are applied only to data of the right type, or do we assume that the given arguments have the right type. We follow SICP by choosing the latter.

[martin-henz]

Fixed by #1719