3 ms·

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

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.)

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.)