3 ms·

Using JavaScript to teach the design of appropriate data structures and algorithms for a computational problem is bound to be an uphill battle. And anyone who

Using JavaScript to teach the design of appropriate data structures and algorithms for a computational problem is bound to be an uphill battle. 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.

iovrthoughtthis 9y ago
Why can't you use javascript in a data structure and algorithms course?
- catnaroek 9y ago
  You can, but it won't be as pleasant as using something more appropriate. Proofs are a big part of any decent data structures and algorithms course. 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.
  - iovrthoughtthis 9y ago
    What makes one language or another "more appropriate"?
    - catnaroek 9y ago
      Sorry, I edited my previous comment to clarify what I mean by “more appropriate”.
  - iovrthoughtthis 9y ago
    > Proofs are a big part of any decent data structures and algorithms course. 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.
    - catnaroek 9y ago
      > 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. 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.
      - iovrthoughtthis 9y ago
        > The proofs have to be related to the code. Otherwise, you're just inviting sloppiness and hand-waving. 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.
        catnaroek 9y ago
        > I disagree. Prose based proofs can just as rigorous as proofs using code, or mathematical notation or images. 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.)
JCSato 9y ago
"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?
- catnaroek 9y ago
  Did they give you a formal semantics for the language in which you implemented algorithms? Or did you merely “prove” things about informal descriptions of algorithms?
  - JCSato 9y ago
    No, proofs were usually done in an entirely separate class later, with the DSA classes focused on data structures (stacks, heaps, hash tables, etc.), sorting algorithms (merge sort, quicksort, etc.), and efficiency (e.g. using Big O). Such was the majority of the content in both cases, at least. 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?
    - catnaroek 9y ago
      > No, proofs were usually done in an entirely separate class later 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.

iovrthoughtthis 9y ago

Why can't you use javascript in a data structure and algorithms course?

catnaroek 9y ago
You can, but it won't be as pleasant as using something more appropriate. Proofs are a big part of any decent data structures and algorithms course. 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.
- iovrthoughtthis 9y ago
  What makes one language or another "more appropriate"?
  - catnaroek 9y ago
    Sorry, I edited my previous comment to clarify what I mean by “more appropriate”.
- iovrthoughtthis 9y ago
  > Proofs are a big part of any decent data structures and algorithms course. 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.
  - catnaroek 9y ago
    > 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. 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.
    - iovrthoughtthis 9y ago
      > The proofs have to be related to the code. Otherwise, you're just inviting sloppiness and hand-waving. 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.
      - catnaroek 9y ago
        > I disagree. Prose based proofs can just as rigorous as proofs using code, or mathematical notation or images. 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.)

JCSato 9y ago

"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?

catnaroek 9y ago
Did they give you a formal semantics for the language in which you implemented algorithms? Or did you merely “prove” things about informal descriptions of algorithms?
- JCSato 9y ago
  No, proofs were usually done in an entirely separate class later, with the DSA classes focused on data structures (stacks, heaps, hash tables, etc.), sorting algorithms (merge sort, quicksort, etc.), and efficiency (e.g. using Big O). Such was the majority of the content in both cases, at least. 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?
  - catnaroek 9y ago
    > No, proofs were usually done in an entirely separate class later 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.