Re: grassroots level SPARK Initiation

[Paul Rubin <no.email@nospam.invalid>]

Mehdi Saada <00120260a@gmail.com> writes:
> I am trying both Gries' Science of Programming and Enderton's
> introduction to logic.... I quickly hated the second as, as has been
> said, it's QUITE not the right orientation, indeed.  It casts
> everything in nonsensical mumbo-jumbo (to be polite ;-) ) whereas a
> down-to-earth - and finitist - approach would use primarily basic
> field agebra, multisets and operations on them to model logical
> reasoning.

Most math is fundamentally about reasoning about infinite sets, such the
integers.  The area within math that deals with finite sets is called
combinatorics and it is hard.  SPARK almost certainly deals with
infinite models.  You might want to prove that a function never crashes
for any sequence of inputs, so you have to quantity over all possible
sequences, of which there are infinitely many.

Finiteness actually makes things harder.  Like if you write a program
that does some calculations with integers, you can prove the algorithm's
correctness using the rules of arithmetic (commutative law, induction,
bla bla bla).  E.g. maybe the algorithm computes some number N and then
does something with its successor N+1.  In math that is fine, every
number has a successor, but that's because the integers are an infinite
set.  If you want to stay with finite sets, you can't say "ok I have N
so I'll compute N+1 and use it for whatever".  You have to *also* prove
that N is small enough that computing N+1 won't result in arithmetic
overflow.

I guess I can sympathize if you didn't like Enderton's book.  I liked it
but I agree that it used a lot of weird symbols whose meanings took
getting used to, etc.  Plus, it's possibly too oriented towards abstract
math and maybe even philosophy.  It's been a long time since I used it
so maybe I'm forgetting.  I typed "logic for computer science" into web
search and found tons of plausible looking books.  Maybe you could try
one of those.

Wikipedia has an article on natural deduction, though I don't know how
it compares with whatever you looked at:

https://en.wikipedia.org/wiki/Natural_deduction

See if you like this better than Enderton's book (it is less mathematical):

https://www.fecundity.com/codex/forallx.pdf
Info page: https://www.fecundity.com/logic/