And anyone who seriously considers teaching a first language that students can't use in a data structures and algorithms course (without having to learn a second language) isn't worth paying much attention to.
Why? Both colleges I've been to had their DSA courses after at least two intro courses, and in a different language than the intro courses.
What is so inherently contemptible about this?
I still don't really have an answer to my question, though. What makes using a different language such a poor choice in this context?
Okay, now that is contemptible. And you didn't address my question: Were your proofs about actual programs, or merely about informal algorithm descriptions?
> What makes using a different language such a poor choice in this context?
The fact you would waste too much time teaching a second language at a sufficiently rigorous level to write proofs about programs written in it.
There is no need for anything more than a loosely agreed upon pseudo code for for the proofs though, actually many proofs can be made without any code.
> So you want a language that makes it possible for students to prove things about programs written in it, without hand-waving away large parts of its semantics
You can write proofs in any language. I'm not convinced that using a language that is easy to automatically prove correctness of is useful for learning proofs. If anything it's the perfect opportunity for syntax and semantics to blind the student to the fundamental assumptions and arguments that allow them to understand and write proofs.
The proofs have to be related to the code. Otherwise, you're just inviting sloppiness and hand-waving.
> I'm not convinced that using a language that is easy to automatically prove correctness of is useful for learning proofs.
I'm talking about writing proofs by hand, the good old-fashioned way. It is easier to prove things by hand about Java programs than JavaScript programs, and it is easier still to prove things by hand about ML programs than Java programs.
I disagree. Prose based proofs can just as rigorous as proofs using code, or mathematical notation or images.
> I'm talking about writing proofs by hand, the good old-fashioned way. It is easier to prove things by hand about Java programs than JavaScript programs, and it is easier still to prove things by hand about ML programs than Java programs.
As am I! I think we might be talking passed each other a little.
Why is it easier to use a language like Java to formulate a proof exactly?
What are we talking about proving? The abstract algorithms being implemented or the implementations themselves? I was under the impression it was the former and I believe you are too but I'd prefer to be explicit.
You can use pictures in your proofs if you want. But the proofs have to be about the actual program you have written, rather than some pseudocode claimed without justification to be equivalent to it.
> Why is it easier to use a language like Java to formulate a proof exactly?
Proofs are written in the language of mathematics, not Java or any other programming language.
However, Java programs are easier to prove things about than JavaScript programs because Java has a richer static semantics that you can use to discharge parts of your proof obligation simply by checking whether your code is a legal Java program. For instance, you can associate to each final class a set of object invariants, defined in terms of its public methods. Java's static semantics is not powerful enough to actually establish these object invariants (you have to do that yourself), but it is powerful enough to prevent users of a final class from breaking invariants that have been established by its implementor (provided users don't use certain misfeatures of the Java language, like reflection).
> What are we talking about proving? The abstract algorithms being implemented or the implementations themselves?
Both. A high-level programming language ought to allow you to express algorithms directly, without distracting you with irrelevant details. (Of course, Java doesn't always do this.)