Comparative Productivity of Programming Languages

[visua...@rocketmail.com]

Today I read an Dr.Dobb's article named
"The Comparative Productivity of Programming Languages"

They say "The problem is that measuring productivity is invariably viewed as more of an art than scientific work... The key unit of measure is a function point, which is a measurable amount of functionality that can be determined during the requirements phase of a program... From this data, they can see how many hours it took to take each project to completion and how those hours mapped to languages, on projects that were primarily written in one language."

They list ASP (6.1), Visual Basic (8.5), Java (10.6), SQL (10.8), C++ (12.4), C (13.0), C# (15.5), PL/1 (14.2), COBOL (16.8), and ABAP (19.9) - numbers in brackets are the development hours per function point of software.
Source:
http://www.drdobbs.com/jvm/the-comparative-productivity-of-programm/240005881

I am wondering why Forth isn't in that list. In former years Dr.Dobb's wrote a lot about Forth.

[A. K.]

Because the list is utter nonsense.

We are very productive in assembler and C. COBOL f.ex. would bring our
product nowhere.

I am wondering why Brainf*ck isn't in that list. I mean they are talking
about art, aren't they?

:)

[Andrew Haley]

You have to take this with a huge pinch of salt. ASP is active server
pages, right?

Andrew.

[Rod Pemberton]

<visua...@rocketmail.com> wrote in message
news:2bebf6e6-dab7-4134...@googlegroups.com...

>
> Today I read an Dr.Dobb's article named
> "The Comparative Productivity of Programming Languages"
>

This is something that's discussed on comp.lang.misc. So, I added it.

> They say "The problem is that measuring productivity is invariably
> viewed as more of an art than scientific work... The key unit of
> measure is a function point, which is a measurable amount of
> functionality that can be determined during the requirements phase
> of a program... From this data, they can see how many hours it took
> to take each project to completion and how those hours mapped to
> languages, on projects that were primarily written in one language."
>
> They list ASP (6.1), Visual Basic (8.5), Java (10.6), SQL (10.8),
> C++ (12.4), C (13.0), C# (15.5), PL/1 (14.2), COBOL (16.8),
> and ABAP (19.9) - numbers in brackets are the development hours
> per function point of software. Source:
>
http://www.drdobbs.com/jvm/the-comparative-productivity-of-programm/240005881

Having programmed in C and a PL/1 variant, I can say PL/1 is just about
equally as powerful as C. I wouldn't say it is more so in any way. It has
areas where it is less effective and _one_ in which is better.

The numbers for C and PL/1 should be close, but I think PL/1 should rank a
bit lower than C. The numbers for C++ here rank C++ slightly better than C.
I think they should be reversed.

> I am wondering why Forth isn't in that list. In former years Dr.Dobb's
> wrote a lot about Forth.

This archived article includes Forth:
http://web.archive.org/web/20061231170804/http://www.theadvisors.com/langcomparison.htm

If you look at the function point rankings at that link, PL/1 ranks above C
by quite a bit. I think PL/1 should be slightly lower. The link above
seems more accurate, but still skewed. C++ ranks well above C and above
PL/1. I think that's just wrong. Forth ranks above both PL/1 and C. In
implementing my Forth interpreter, I've not seen anything in Forth that
would rank it that high, comparatively, to either C or PL/1.

So, the question is how accurate are the metrics of 'function points'
really? Those numbers are usually calculated from completed projects. But,
do they adjust for programmer skill and experience level? I doubt that they
do.


Rod Pemberton

[visua...@rocketmail.com]

On Wednesday, August 22, 2012 8:07:09 AM UTC-4, Rod Pemberton wrote:
> This archived article includes Forth: http://web.archive.org/web/20061231170804/http://www.theadvisors.com/langcomparison.htm

Thanks, Rod, for this interesting link.

Tables like these are still available for 125$ at SPR:
http://www.spr.com/programming-languages-table.html

I found an interesting quote at http://en.wikipedia.org/wiki/Capers_Jones

"High-quality software is not expensive. High-quality software is faster and
cheaper to build and maintain than low-quality software, from initial
development all the way through total cost of ownership."

Isn't that something?

[visua...@rocketmail.com]

On Wednesday, August 22, 2012 12:43:56 AM UTC-4, visua...@rocketmail.com wrote:
> Today I read an Dr.Dobb's article named "The Comparative Productivity of Programming Languages" ...

> I am wondering why Forth isn't in that list. In former years Dr.Dobb's
> wrote a lot about Forth.

DB.

[John Passaniti]

On Wednesday, August 22, 2012 4:35:01 AM UTC-4, Andrew Haley wrote:
> You have to take this with a huge pinch of salt. ASP
> is active server pages, right?

Because ASP (and ASP.NET) are cross-language web frameworks, saying you "program in ASP(.NET)" is a nearly-meaningless statement. ASP.NET programmers actually likely (these days) programming in VB.NET or C#. That kind of imprecision isn't limited to ASP programmers. Several times when I conducted job interviews and saw the applicant put "HTML" under programming languages they knew, I sighed and asked them to code a function that did something trivial (like add up the numbers 1 to 10). Most immediately wrote out something in JavaScript without skipping a beat. When I informed them that their code wasn't in HTML but in a different language called JavaScript, many just either looked at me blankly or said something like, "well yeah, they're the same thing, right?"

Whenever someone publishes a study or claim about how language X makes you Y times more productive, it causes everyone with a favorite language to flail around and make loads of assumptions about methodology and motive. Instead, it helps to go back to the source. And here, using function points is one reasonably objective factor to consider when evaluating productivity. It's only one, however, and it may or may not relate to how one chooses to work.

For me, I am far more productive when using interactive languages (not just Forth) because that reflects my work style and biases. But there are people who see no value in interactive languages, either because they've never used one or because they don't use it well.

And we see other language differences affecting programmers in other ways. Take for example the subject of typed versus untyped (or dynamically typed) languages. In this newsgroup, many discussions about typed languages present such languages as a straight-jacket where some totalitarian compiler prevents you from doing what you want. But when you move outside the realm of languages like C and into languages like Haskell and F# that have type inferencing and pattern matching and you view types very differently. But if your only experience with typed languages is something like C, then you just view types in the narrow context of safety and performance.

It goes on and on. Procedural languages versus functional languages. Generic data structures (like key/value stores) versus application-specific data structures. Class-based object orientation versus prototype-based objects. It doesn't really matter what dichotomy people bring up regarding productivity, you'll always find some people who think they are more productive with one instead of the other.

I wish people would just accept that there is no universal truth or single answer here. The reason why there are so many different programming languages is that there is more than one way to approach solving problems. Your productivity with any language is more a function of how well the problems you're trying to solve and the way you want to solve them are served by the language. And that's why programmers should learn multiple fundamentally different languages, so they can have at their disposal the right tool for the right job. Or alternatively, if they are using a language like Forth, knowing what tools they might want to add to Forth to make their jobs easier. (Put another way, it does no good for Forth to be a flexible and malleable language if the programmer doesn't have enough experience to know when it makes sense to extend Forth.)

[Anton Ertl]

John Passaniti <john.pa...@gmail.com> writes:
> And here, using function points is=
> one reasonably objective factor to consider when evaluating productivity. =
> It's only one, however, and it may or may not relate to how one chooses to=
> work.

When I was a student, I heard about function points and got the
impression that, say, an addition was one function point, which seemed
to me a metric that's specific to some piece of code, and to evaluate
how many function points one needs requires a similar amount of effort
as doing an implementation, so it did not appear useful as an estimate
of the complexity of the task.

These days we have Wikipedia, so I checked that, and it appears that
function points are useful for classical form-report applications,
where the required effort is mostly in the forms and reports and can
be estimated from the specification of the forms and reports. I can
see how that might work.

However, for other applications I have no idea how to determine
function points for them. For example, I wrote a comparison of
programming languages based on a case study of several parser
generators with varying functionality
<http://www.complang.tuwien.ac.at/anton/euroforth/ef99/ertl99.pdf>.

Given the differing functionality of the compared parser generators,
it would be useful for that kind of study to get a number that
represents the functionality and can be related to the SLOC (source
lines of code) metric for the implementation. Are function points
usable for this kind of application?

>And we see other language differences affecting programmers in other ways. =
> Take for example the subject of typed versus untyped (or dynamically typed=
>) languages. In this newsgroup, many discussions about typed languages pre=
>sent such languages as a straight-jacket where some totalitarian compiler p=
>revents you from doing what you want. But when you move outside the realm =
>of languages like C and into languages like Haskell and F# that have type i=

>nferencing and pattern matching and you view types very differently.

Really? My experience with Haskell is that I get type error messages
that are hard to comprehend.

Closer to comp.lang.forth, Factor has type inference; we had a little
workshop at the Forth-Tagung this year, where we should write a few
programs; the type checker constantly hindered me in achieving what I
wanted to do, and most others had a similar experience. Bernd found a
solution that was accepted, but when I tried to use his ideas for my
own program, I ran into the type checker again; I think that Bernd
just found a hole in the type checker.

OTOH, C type checking complicates things, but is still simple enough
that I can get out of C what I want (or maybe I just have more
experience with it). So, yes, Haskell type checking is different, but
not in the way you imply.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2012: http://www.euroforth.org/ef12/

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> Really? My experience with Haskell is that I get type error messages
> that are hard to comprehend.

GHC's error messages are often pretty bad, but they usually do result
from actual program errors that would make it into the executable if the
type checker hadn't found them, so they are worth it. As you get more
used to Haskell, it gets easier to just look at the line number that the
error message points to, and figure out what is wrong with the code by
inspection. The error message usually does tell you the particular
sub-expression that has gone wrong.

[John Passaniti]

On Thursday, August 23, 2012 10:50:54 AM UTC-4, Anton Ertl wrote:
> However, for other applications I have no idea

> how to determine function points for them. [...]

My point wasn't that function points are some ideal measure but that they are an /objective/ measurement. Unlike some of the more squishy subjective metrics some people use in these discussions about productivity, function points are something we can actually talk about. I don't know the specifics of how function points were calculated in this particular study, but it's reasonable to assume they are using one of the standard tools out there that produce such statistics.

So we can talk about function points-- where they make sense, where they don't, when they reflect something essential about code programmers write in a language, where it is meaningless, etc. If we were talking instead about polls of programmer's opinions or anecdotal accounts about how using language X they finished a job Y times faster, then there really isn't much of a conversation possible.

> Given the differing functionality of the compared
> parser generators, it would be useful for that kind
> of study to get a number that represents the
> functionality and can be related to the SLOC (source
> lines of code) metric for the implementation. Are
> function points usable for this kind of application?

Possibly, although for the purpose of determining productivity, I don't see much value in physical SLOC. Some languages are more vertical than others and unless people believe that hitting the return key is a major source of productivity loss, then it makes more sense to (consistently) measure logical SLOC instead:

: square ( x -- x^2 )
dup * ;

let square x = x * x

int square(int x) {
return x*x;
}

These trivial examples in Forth, F#, and C are to me all one logical SLOC.

Even better might be to come up with some kind of cognitive measure of the code. This is a bit more tricky, but I think it's possible. For example, here's a silly Forth function:

: sumRange ( low high -- sum )
1+ 0 -rot swap do i + loop ;

When I look at this code, I abstractly see five things:

1. A definition of a new word.
2. Setting up the loop bounds.
3. Preparing an accumulator.
4. A loop with ...
5 ... a simple one operation body.

So if I was to come up with a cognitive metric, I might say that sumRange had a count of 5; there are five distinct things happening in this code. Compare to Haskell:

sumRange low high = sum [low .. high]

1. Definition of a new function.
2. Generate list of range.
3. Sum list.

I'd say this has a cognitive count of 3. And I would say that in this trivial example, the Haskell programmer is more productive than the Forth programmer in the sense that there is less on the programmer's mind to express the same idea. Now, if this holds for larger non-trivial programs is a matter of debate and discussion, but the methodology I'm using here is objective.

> Really? My experience with Haskell is that I get
> type error messages that are hard to comprehend.

I find German-language text to be hard to comprehend, mostly because the only German I know comes from Einsturzende Neubauten lyrics. I'm guessing you don't have that problem.

> OTOH, C type checking complicates things, but is
> still simple enough that I can get out of C what
> I want (or maybe I just have more experience
> with it). So, yes, Haskell type checking is
> different, but not in the way you imply.

Incorrect. I specifically referenced pattern matching and type inference. There is no equivalent to either in C. Pattern matching (especially on discriminated unions) and related features (like data destructuring) use type information at run-time, which isn't even a concept in C.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Really? My experience with Haskell is that I get type error messages
>> that are hard to comprehend.
>
>GHC's error messages are often pretty bad, but they usually do result
>from actual program errors that would make it into the executable if the
>type checker hadn't found them, so they are worth it.

The Haskell system was actually Hugs, not GHC, but the quality of the
error messages is due to the type system, so I would not expect any
better from a different Haskell system: The system just sees some
puzzle pieces and infers the missing pieces itself. If the pieces I
give it belong to different puzzles, it will fail at puzzing it out,
and since the system does not know which of the given puzzle pieces
are wrong, the error messages are necessarily not very helpful.

Concerning being worth, I have far fewer type errors in Forth than in
Haskell. Maybe that just reflects my familiarity with the languages,
but I believe that this is due to the languages and their type
systems. Forth is designed to be usable without type checking,
whereas Haskell is designed for static type checking with type
inference.

>As you get more
>used to Haskell, it gets easier to just look at the line number that the
>error message points to, and figure out what is wrong with the code by
>inspection.

Yes, after a while I learned some patterns of the kind, that a
particular incomprehensible error message points to this kind of
frequent error.

Anyway, my conclusion is that, while type inference sounds cool in
theory, it has more disadvantages than advantages in practice. One of
the disadvantages probably is that it allows a complex type system
that would be totally impractical without type inference; and the
Haskell designers went that way.

[Anton Ertl]

John Passaniti <john.pa...@gmail.com> writes:
>On Thursday, August 23, 2012 10:50:54 AM UTC-4, Anton Ertl wrote:
>> However, for other applications I have no idea
>> how to determine function points for them. [...]

[...]
>So we can talk about function points-- where they make sense, where they do=
>n't, when they reflect something essential about code programmers write in =

>a language, where it is meaningless, etc.

Well, yes? That was my question. For which applications do they make
sense? Do they make sense for parser generators? How do I use them
there?

> If we were talking instead about=
> polls of programmer's opinions or anecdotal accounts about how using langu=
>age X they finished a job Y times faster, then there really isn't much of a=
> conversation possible.

Why not? Time seems to be at least as objective a metric as function
points.

>Possibly, although for the purpose of determining productivity, I don't see=
> much value in physical SLOC. Some languages are more vertical than others=
> and unless people believe that hitting the return key is a major source of=
> productivity loss, then it makes more sense to (consistently) measure logi=

>cal SLOC instead:
>
>: square ( x -- x^2 )
> dup * ;
>

>let square x =3D x * x

>
>int square(int x) {
> return x*x;
>}
>

>These trivial examples in Forth, F#, and C are to me all one logical SLOC. =

You are welcome to repeat the study I did with logical SLOC. Instead,
I just counted the physical SLOC, and for the two programs that I
looked at more closely, I looked at an example of equivalent code to
see how horizontal or vertical the code was written.

BTW, I would have loved to use time instead of SLOC, but I had no time
data.

>> Really? My experience with Haskell is that I get=20

>> type error messages that are hard to comprehend.
>

>I find German-language text to be hard to comprehend, mostly because the on=
>ly German I know comes from Einsturzende Neubauten lyrics. I'm guessing yo=

>u don't have that problem.

And?

>> OTOH, C type checking complicates things, but is=20
>> still simple enough that I can get out of C what=20
>> I want (or maybe I just have more experience=20
>> with it). So, yes, Haskell type checking is=20

>> different, but not in the way you imply.
>

>Incorrect. I specifically referenced pattern matching and type inference. =

> There is no equivalent to either in C.

Yes, that's probably the reason why C type checking is still simple
enough.

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> The Haskell system was actually Hugs, not GHC, but the quality of the
> error messages is due to the type system, so I would not expect any
> better from a different Haskell system

I suggest trying GHC. Its messages are better, though still not that
great. Nobody uses Hugs much any more, afaik.

> Concerning being worth, I have far fewer type errors in Forth than in
> Haskell.

Do you mean type errors that the compiler didn't notice? Forth of
course ignores type errors at compile time. I'd ask how many Forth
runtime errors would have been caught by Haskell's type system at
compile time. When I wrote my first nontrivial Forth program, I several
times said + when I meant F+, and of course the runtime happily added
the wrong two stack items, causing later crashes that I then had to
debug. That was much more annoying than just having the compiler flag
the error.

> Maybe that just reflects my familiarity with the languages,

That could be, though Haskell is just typed lambda calculus with syntax
sugar. If you erase all the types and syntax, you're left with
something like Scheme, modulo lazy evaluation. And it's quite easy to
make type errors in Scheme.

Haskell's type system makes it feasible to write maintainable code in a
quite abstract style involving higher-order functions, parametrized data
types, and so on. This can also be done in Forth or Scheme but it gets
confusing rather quickly. Having a computer keep track of the types
takes cognitive burden off of the programmer, and makes refactoring
easier (just fix the resulting type errors until the compiler stops
complaining, and you probably have working code).

> Anyway, my conclusion is that, while type inference sounds cool in
> theory, it has more disadvantages than advantages in practice. One of
> the disadvantages probably is that it allows a complex type system
> that would be totally impractical without type inference; and the
> Haskell designers went that way.

Preferred Haskell style is to write explicit type annotations on all
top-level functions, and this helps keep the error messages useful.
ML's type system is less fancy than Haskell's and I think it's more
practical in ML to not write any annotations and rely completely on
inference. Writing top-level annotations isn't all that bothersome, and
they serve as machine-checked documentation among other things.

Preferred Forth style also involves writing type annotations (stack
diagrams) on all functions. The compiler just doesn't bother checking
them.

[Doug Hoffman]

On 8/25/12 1:12 PM, Paul Rubin wrote:

> When I wrote my first nontrivial Forth program, I several
> times said + when I meant F+, and of course the runtime happily added
> the wrong two stack items, causing later crashes that I then had to
> debug. That was much more annoying than just having the compiler flag
> the error.

If you are writing short, factored words, and testing each word before
continuing then that "+ instead of F+" should have become immediately
apparent and so no problem at all to notice and fix. No type checker
needed if you follow the recommended Forth way of writing a program.

-Doug

[Paul Rubin]

Doug Hoffman <glid...@gmail.com> writes:
> If you are writing short, factored words, and testing each word before
> continuing then that "+ instead of F+" should have become immediately
> apparent and so no problem at all to notice and fix. No type checker
> needed if you follow the recommended Forth way of writing a program.

As I remember, it wasn't so immediately apparent what the problem was,
since the failure didn't occur til a little ways after the + happened.
And the symptom was that the program crashed without much clue about
what had happened. Of course fancy debugging tools would have made it
easier to trace and fix the problem, and it's not inherent in Forth that
the implementation I used didn't happen to have them. Looking at the
code now, its factoring doesn't seem too bad, though maybe it could be
better.

Anyway, if a type-checked language lets me write a page full of code and
fix the compile-time errors to usually get working program, while the
typeless counterpart makes me stop what I'm doing after basically every
single line to check for problems the type checker would have caught
automatically, I'd say the type checker has made itself worthwhile.

[Elizabeth D. Rather]

Unit-testing every definition pays off handsomely in saved debugging
time by catching all kinds of bugs, not just type errors.

And my experience is similar to Anton's, in that I make very few type
errors. This may be because I'm accustomed to matching the right
operators to the right data type, whereas folks who are used to
languages that do type inference are less conscious of it. But the
majority of errors (not only for me but for programmers I work with) are
logic/algorithm errors, and they're readily detected by unit testing
each definition. Takes seconds, can save hours!

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[Paul Rubin]

> Unit-testing every definition pays off handsomely in saved debugging
> time by catching all kinds of bugs, not just type errors.

You can think of compile-time type checking as automatic generation of a
wide class of unit tests. It doesn't eliminate the need for
manually-written tests, but it decreases it. The main idea of
programming computers is to offload work from humans to machines, so
automatic test generation seems like a win to me, at least from a
productivity point of view. I'd accept that Forth builds character, by
making the programmer think harder. I probably get something out of
that. The older saying was "assembly language programming is good for
the soul".

IMHO Haskell's type system makes it practical to program in a style that
while not impossible, would be much harder to manage in Forth.
Basically, one where functions create other functions on the fly, and
those functions create other functions and so on. From a Forth
perspective, we'd probably say that style is confusing and error-prone,
and therefore something bad to be avoided. In Haskell, it's beautiful
and it works, because the type system guides the construction and
prevents the programs from going wrong.

http://cdsmith.wordpress.com/2011/01/09/an-old-article-i-wrote/

is a good article about this stuff.

[jacko]

My language SL written in JavaME/SE (http://jarvar.googlecode.com) has some interesting type features. I would describe it as "weak" as possible typed. Full conversion of numeric types to the lowest representational form, and numbers as single characters, (being the same thing). As a necessity of system stability, some values must be "strong" and so only assignment of the same type is allowed. Also some things have to be "constant", for the same system stability reasons. This is opposite to the idea that things are constant for speed or compile time optimization.

I do not yet know how effective this language is yet. There is still much to decide. Such as IO forms, (constants vectorized) -> code minimized -> same resultant which have to be explored. The time it takes to do something already in another language is not a fit measure of language utility. Maybe the time it takes to bootstrap a compiler for (or translator to) a language in itself has some measure, but it's not the be and end all. SL is currently very small source, and binary.

Cheers Jacko

[Bernd Paysan]

Paul Rubin wrote:
> You can think of compile-time type checking as automatic generation of
> a
> wide class of unit tests. It doesn't eliminate the need for
> manually-written tests, but it decreases it. The main idea of
> programming computers is to offload work from humans to machines, so
> automatic test generation seems like a win to me, at least from a
> productivity point of view. I'd accept that Forth builds character,
> by
> making the programmer think harder.

Actually not. I think harder when I program in other languages, because
in Forth, I just try. The thing Forth tries to minimize is the time for
feedback. This is a psychological thing, if I program in Forth, I'm not
distracted, it's programming, and trying my program, nothing else. If I
program in C, I can start the compiler and then play a round of some
silly social network game, and come back, and the compiler might just
have finished. In the meantime, I forgot what I wanted to do.
Performance is a problem, even in 2012. Performance of C compilers, so
to speak. The build tool to compile Android is called "lunch", for
obvious reasons. If I would have to give a similar name for the build
process of bigForth, it would be "blink". You start it and it's done.
Which means that quickly doing some changes and seeing what they do to
the system is possible. You don't have to think, you just do it.

That also guides to my most-used debugging method: Inserting ~~ in
suspicious places. As I can rebuild everything quickly, when I have
troubles comprehending what happends inside a function, and unit testing
doesn't show it (or isn't easy, because I don't know which are the input
parameters that cause the crash), I insert ~~ and look.

> I probably get something out of
> that. The older saying was "assembly language programming is good for
> the soul".

Of course it is. You understand what the machine actually does.

> IMHO Haskell's type system makes it practical to program in a style
> that while not impossible, would be much harder to manage in Forth.
> Basically, one where functions create other functions on the fly, and
> those functions create other functions and so on. From a Forth
> perspective, we'd probably say that style is confusing and
> error-prone, and therefore something bad to be avoided.

I'm not sure why you claim it is error-prone and to be avoided. We do
this, we have tools for that like postpone, ]] [[, and create does>
(which can be said to be some sort of currying). It certainly has a
different, more fine-grained approach than the Haskell approach.

Forth is a programming language which tells you to avoid unnecessary
abstractions. Solve the problem, don't invent layers of layers in
between you and the problem (toilet paper style programming - "keep me
away from the shit").

> In Haskell, it's beautiful
> and it works, because the type system guides the construction and
> prevents the programs from going wrong.

No type system prevents programs from going wrong. It applies a number
of low-hanging fruit checks, while at the same time putting a
straitjacket onto the programmer. At least that's how I feel when I
program in a language with a strong type system. The compiler tells me
"no, you can't do this", and "no, you can't do that".

When the program finally compiles, the programmer is so happy that he
forgets to actually test the program.

> http://cdsmith.wordpress.com/2011/01/09/an-old-article-i-wrote/
>
> is a good article about this stuff.

Maybe, but some things in the article are silly and wrong. Performance
is not a problem? Come on. I'm constantly seeing software which is
slow as molasses, and fills memory faster than Samsung can make it (in
GB/s, and Samsung produces quite a lot of GB chips per second). It's
rarely the programming language which is too slow, it's the programmer
mentality, like "lunch" is an adequate time to recompile something. "It
used to be days". Yes, that was wrong, too.

What I think would be worth to do for analytic compilers which track
that information anyways: Have a stack effect checker. Warnings when it
doesn't match, please, it should compile, because running it (with
inserted ~~) will identify the problem quickly. Factor refuses to
compile when the stack effect is wrong or perceived wrong. There are
for sure cases where the compiler can't deduce the stack effect, but it
is correct, nonetheless. Programs can only check low-hanging fruits of
correctness.

Different programming languages have different approaches, and that's
reflected by their community. A Haskell programmer thinks in terms of
Haskell's type system and when learning Forth will try to put a
typechecker around Forth. That's not what makes Forth strong, Forth's
interactivity and abstraction avoidance is what makes it strong.
Interactivity is more than just a command line promt, it also means that
you can recompile quickly. "Blink", not "lunch".

Of course, adding features from other languages opens up new ways of
doing things. We have our experiments with StrongForth and Forth
typecheckers (typically written in Haskell ;-).

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[jacko]

Also now on github for those wishing to fork.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> The build tool to compile Android is called "lunch", for
> obvious reasons. If I would have to give a similar name for the build
> process of bigForth, it would be "blink".

Are you talking about compiling programs of similar size, on similar
hardware, with compilers that do similar levels of optimization? It's
certainly plausible that given more CPU power, fancy compilers will
use it to do more optimization and automation, rather than just doing
the same stuff as before and finishing sooner.

Maybe you should try TCC (tinycc.org) for development builds.
It's around 10x faster than GCC, though the output code is nowhere near
as optimized.

> That also guides to my most-used debugging method: Inserting ~~ in
> suspicious places.

This still takes a lot of runs of the program and possible creation of
new test cases, which can be pretty tedious.

>> IMHO Haskell's type system makes it practical to program in a style

>> that while not impossible, would be much harder to manage in Forth....
> I'm not sure why you claim it is error-prone and to be avoided....

> Forth is a programming language which tells you to avoid unnecessary
> abstractions.

Right, the reason it tells you to avoid unnecessary abstractions is that
using abstraction in Forth is error-prone. I wasn't thinking really of
postpone and create/does, but more of a style where you pass around
execution tokens a lot, and those xt's may take other xt's as arguments
to invoke over generic data structures, and so on. In Haskell, it's
natural to program that way, and the code still feels solid. In Scheme
or Python you can write basically the same code, but with no type system
watching over you, it feels like walking on a tightrope without a safety
net. I've programmed that way in Forth a little bit, but have been
advised against it.

> No type system prevents programs from going wrong.

Well, I'd say a well-typed program, including something like Lisp with
runtime type-checking, can at least have well-defined semantics, while
an untyped (e.g. Forth or C) program can go completely into the weeds if
there is a type error (such as a subscript overflow).

> It applies a number of low-hanging fruit checks,

Haskell typechecking can be quite powerful. I like this example:
https://gist.github.com/2659812

Explanation: Red-black trees are binary trees with the following
invariants:
1. Each internal node is colored either red or black.
All leaves are black and the root is black.
2. All children of red nodes must be black. Black nodes can
have children of either or both colors.
3. All paths from the root to the leaf contain the
same number of black nodes.

This means the tree is approximately balanced: any path from the root to
a leaf contains n black nodes, and between 0 and n red nodes, so the
worst case search depth is no more than 2x the best case. You can't get
a completely lopsided tree. To insert or delete a node, you have to do
somewhat complicated juggling operations ("tree rotations") to preserve
the invariants, and it's easy to make mistakes coding these operations.
The C++ implementation that I looked at has assert statements that check
at runtime that the code didn't hit some weird edge case that messed the
invariants up. Even after extensive testing, the assert statements are
still there in the program.

It turns out to be pretty straightforward to express those invariants as
a Haskell datatype (seen in the url above). Any value belonging to the
type must be a properly balanced tree. That means that the juggling
code cannot possibly mess up the invariants. Any attempt to make an
unbalanced tree will cause a type-checking error, and the program won't
compile. It would be pointless to have assert statements in the
executable since the compiler has statically verified that the asserted
conditions hold. I would not call this low-hanging fruit. It's a
sophisticated condition being checked, that's a source of bugs in other
real-world implementations, and the compiler verifies it to higher
confidence than even quite a lot of unit tests could give.

As an even more extreme example, Coq's type system is even stronger than
Haskell's: it can express any mathematical proposition, so it has to be
Turing complete, meaning it can't do inference and you have to manually
supply type derivations (which is tedious). But it can encode (for
example) the semantics of assembly code fragments (Hoare triples) as
types. So if you have a compiler optimization pass that is annotated to
take one fragment and returns another fragment of the same type, the Coq
typechecker is able to verify that the input and output have the same
semantics and the optimization pass has not introduced any semantic
bugs. I think I mentioned before, a sizable part of a C compiler has
been written that way (CompCert). This is not low hanging fruit at all.
It is probably the future, especially as better automation becomes
available for developing this sort of code.

> while at the same time putting a straitjacket onto the programmer. At
> least that's how I feel when I program in a language with a strong
> type system. The compiler tells me "no, you can't do this", and "no,
> you can't do that".

I never felt terribly straitjacketed programming in C, but I also felt
that the type system wasn't helping me that much. I was comfortable
programming with lots of void*'s, and programming in Lisp with runtime
types. Trying Haskell was really eye-opening for me. I'm a long way
from being a Haskell expert but I find it tremendously interesting and
different (whether that means "better" is of course a separate matter).

>> http://cdsmith.wordpress.com/2011/01/09/an-old-article-i-wrote/

> Performance is not a problem? Come on. I'm constantly seeing
> software which is slow as molasses,

He's talking about compiled code with runtime type checks, vs. compiled
code that has been statically checked but otherwise does the same stuff,
e.g. Lisp vs ML. If the compiler is any good, the performance
difference is usually a small constant factor, maybe just a few percent.
The large, order-of-magnitude slowdowns you're seeing in the examples
you mention are due to architectural issues in the slow programs.

> What I think would be worth to do for analytic compilers which track
> that information anyways: Have a stack effect checker.

Yes, that would have caught my + vs. F+ bugs. StrongForth does
that sort of checking as you're probably aware.

> Warnings when it doesn't match, please, it should compile, because
> running it (with inserted ~~) will identify the problem quickly.

GHC now has a command-line option that lets it produce executable code
even if the program has type errors. You then get a runtime error only
if the program tries to actually evaluate an ill-typed expression. This
turns out to be handy during development even though the compiler has
already told you where the errors are. It's sometimes useful to be able
test the successfully compiling parts of your program right away,
postponing dealing with the unsuccessful parts til later.

> Forth's interactivity and abstraction avoidance is what makes it
> strong. Interactivity is more than just a command line promt, it also
> means that you can recompile quickly. "Blink", not "lunch".

I sometimes like to imagine what it must have been like to program in
Forth or Lisp in the glory days of those languages. I'd be interested
in seeing a demo sometime (maybe on video) of someone hacking on Forth
code that does something complicated, using good interactive Forth
tools. When I started using Python, I found myself thinking "this is
what the old-time Maclisp hackers must have felt like". Haskell is
different, completely different, a vision as powerful as Lisp but unlike
anything that had been used for programming before. That in some sense
outweighs any difficulties involved in trying to actually use it. ;-)

[Elizabeth D. Rather]

On 8/25/12 7:44 PM, Paul Rubin wrote:
> Bernd Paysan <bernd....@gmx.de> writes:
>> The build tool to compile Android is called "lunch", for
>> obvious reasons. If I would have to give a similar name for the build
>> process of bigForth, it would be "blink".
>
> Are you talking about compiling programs of similar size, on similar
> hardware, with compilers that do similar levels of optimization? It's
> certainly plausible that given more CPU power, fancy compilers will
> use it to do more optimization and automation, rather than just doing
> the same stuff as before and finishing sooner.

Forth compilers have always been fast. Even with optimizing techniques
in modern Forths, they're many times faster than other compilers. I have
observed this many times, but don't know enough about the other
compilers to know why they are so slow.

>> That also guides to my most-used debugging method: Inserting ~~ in
>> suspicious places.
>
> This still takes a lot of runs of the program and possible creation of
> new test cases, which can be pretty tedious.

But it doesn't involve "creation of new test cases". It's as simple as
typing

n m foo .

...to test foo and look at its results.

...

>> Forth's interactivity and abstraction avoidance is what makes it

>> strong. Interactivity is more than just a command line prompt, it also

>> means that you can recompile quickly. "Blink", not "lunch".
>
> I sometimes like to imagine what it must have been like to program in
> Forth or Lisp in the glory days of those languages. I'd be interested
> in seeing a demo sometime (maybe on video) of someone hacking on Forth
> code that does something complicated, using good interactive Forth
> tools. When I started using Python, I found myself thinking "this is
> what the old-time Maclisp hackers must have felt like". Haskell is
> different, completely different, a vision as powerful as Lisp but unlike
> anything that had been used for programming before. That in some sense
> outweighs any difficulties involved in trying to actually use it. ;-)

I know nothing of Haskell, but have seen Forth programmers "taming"
complex problems many times. I wish I had a video for you, it's very
instructive! The best Forth programmers are most productive without
using fancy tools, even when they are available. The effect is that they
are "communing" with the code, sort of "code whisperers", trying things,
making tiny adjustments, trying again, and the results come. Chuck once
described the effect as "synergistic". No one, or two, or even three
specific things, but an overall relationship between the programmer and
the code that makes the creativity flow and the results happen with what
seems to be amazing ease. The key is that each "try" is a blink. There
is never a perceptible pause.

In effect, what happens is that the intimate interactivity of Forth
opens a direct channel between the mind of the programmer and the
problem space that just *works*.

[Paul Rubin]

"Elizabeth D. Rather" <era...@forth.com> writes:
> But it doesn't involve "creation of new test cases". It's as simple as
> typing
> n m foo .
> ...to test foo and look at its results.

That's not realistic;

1) foo might be much more complicated (delegating most of the work to
smaller factors, but you have to test the overall operation). The
args and result could be complex data structures, it might not be
easy to check the output correctness by simple inspection, etc.

2) foo could interact with external hardware. Here's a situation I've
had to deal with (not in Forth though): foo is called when a
certain hardware event happens, and works fine if I simulate the
event, or generate a real event and watch foo do its thing. But if
there are too many of these events in a several minute period, some
kind of internal overload condition results and foo does the wrong
thing. This only happens on the target (embedded) hardware--my
development workstation is much too fast to trigger an overload.
So I have to get all the external hardware firing in order to make
foo fail while I log what it's doing. This is not instant--it
takes a few minutes every run. So minimizing the number of runs
speeds up debugging, and it would be really nice if I could debug
interactively.

> I wish I had a video for you, it's very instructive! The best Forth
> programmers are most productive without using fancy tools, even when
> they are available.

Yes. I'd also be interested in seeing one with vintage tools, like a
block editor with shadow screens for comments, etc.

[Elizabeth D. Rather]

On 8/25/12 9:36 PM, Paul Rubin wrote:
> "Elizabeth D. Rather" <era...@forth.com> writes:
>> But it doesn't involve "creation of new test cases". It's as simple as
>> typing
>> n m foo .
>> ...to test foo and look at its results.
>
> That's not realistic;
>
> 1) foo might be much more complicated (delegating most of the work to
> smaller factors, but you have to test the overall operation). The
> args and result could be complex data structures, it might not be
> easy to check the output correctness by simple inspection, etc.

If all of the smaller factors have been tested, including the components
that build the complex data structures, a lot of the work has been done.
But I agree, sometimes it's necessary to have code to test your results.

> 2) foo could interact with external hardware. Here's a situation I've
> had to deal with (not in Forth though): foo is called when a
> certain hardware event happens, and works fine if I simulate the
> event, or generate a real event and watch foo do its thing. But if
> there are too many of these events in a several minute period, some
> kind of internal overload condition results and foo does the wrong
> thing. This only happens on the target (embedded) hardware--my
> development workstation is much too fast to trigger an overload.
> So I have to get all the external hardware firing in order to make
> foo fail while I log what it's doing. This is not instant--it
> takes a few minutes every run. So minimizing the number of runs
> speeds up debugging, and it would be really nice if I could debug
> interactively.

Yes, of course, sometimes you need to set up hardware correctly for
testing. But if you've tested all the low-level parts of the operation,
it shouldn't be hard to set up an overload test.

>> I wish I had a video for you, it's very instructive! The best Forth
>> programmers are most productive without using fancy tools, even when
>> they are available.
>
> Yes. I'd also be interested in seeing one with vintage tools, like a
> block editor with shadow screens for comments, etc.

Actually, the programming process is virtually unchanged, even though
the details (e.g. using an external programmer's editor instead of the
integrated block editor) are different.

[Paul Rubin]

"Elizabeth D. Rather" <era...@forth.com> writes:
> Yes, of course, sometimes you need to set up hardware correctly for
> testing. But if you've tested all the low-level parts of the
> operation, it shouldn't be hard to set up an overload test.

The external hardware is something I didn't build and don't control and
that has no automation. I could in principle write code to simulate it
on but that would be weeks of development, not feasible under current
schedule and budget conditions. So I just have to operate the thing
manually, at the speed that it goes at. It's not too bad as long as I
don't have to do it too often.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:

>> Concerning being worth, I have far fewer type errors in Forth than in
>> Haskell.
>
>Do you mean type errors that the compiler didn't notice?

No, I mean that there are far fewer type errors in my Forth code than
type error messages for my Haskell code. Of course in Forth neither
the compiler nor the run-time system usually notices a type error, but
that's not what I claimed.

>When I wrote my first nontrivial Forth program, I several
>times said + when I meant F+, and of course the runtime happily added
>the wrong two stack items, causing later crashes that I then had to
>debug.

That's a type error, yes.

>Haskell's type system makes it feasible to write maintainable code in a
>quite abstract style involving higher-order functions, parametrized data
>types, and so on. This can also be done in Forth or Scheme but it gets
>confusing rather quickly.

I would have thought that it's the bread and butter of programming in
Scheme. Concerning parameterized data types, they are a solution for
a problem that you only have if you try to perform static type
checking.

> Having a computer keep track of the types
>takes cognitive burden off of the programmer,

I doubt that very much, because the programmer cannot write correct
programs if he does not keep track of the types himself.

> and makes refactoring
>easier (just fix the resulting type errors until the compiler stops
>complaining, and you probably have working code).

Yes, I can believe that.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>Doug Hoffman <glid...@gmail.com> writes:
>> If you are writing short, factored words, and testing each word before
>> continuing then that "+ instead of F+" should have become immediately
>> apparent and so no problem at all to notice and fix. No type checker
>> needed if you follow the recommended Forth way of writing a program.
>
>As I remember, it wasn't so immediately apparent what the problem was,
>since the failure didn't occur til a little ways after the + happened.
>And the symptom was that the program crashed without much clue about
>what had happened. Of course fancy debugging tools would have made it
>easier to trace and fix the problem, and it's not inherent in Forth that
>the implementation I used didn't happen to have them.

In my experience such a basic error as writing a + where there should
be an F+ shows up really quick, but maybe I avoid writing code where
it would not show up quickly.

Concerning fancy tools, I use the ~~ tracer (a more convenient variant
of what C programmers call printf debugging), and Gforth has
backtraces to let you know where an error happened. Some people like
a stepping debugger, but in my experience it's a good recipe for
wasting time. A back-stepping debugger with reverse watchpoints, now
that would be useful; apparently newer versions of gdb have that, but
I have not found the need for that yet.

>Anyway, if a type-checked language lets me write a page full of code and
>fix the compile-time errors to usually get working program, while the
>typeless counterpart makes me stop what I'm doing after basically every
>single line to check for problems the type checker would have caught
>automatically, I'd say the type checker has made itself worthwhile.

Why would I stop after every line? I typically write code until I
think it's time to test and debug, and then I start to test and debug.
While testing and debugging, it helps to have short words that can be
called individually.

[Bernd Paysan]

Paul Rubin wrote:
> Are you talking about compiling programs of similar size, on similar
> hardware, with compilers that do similar levels of optimization? It's
> certainly plausible that given more CPU power, fancy compilers will
> use it to do more optimization and automation, rather than just doing
> the same stuff as before and finishing sooner.

No, I'm comparing a bloated Java+C++ project to a non-bloated Forth
project. But even when I compare two non-bloated projects, GCC is
hellish slow.

> Maybe you should try TCC (tinycc.org) for development builds.
> It's around 10x faster than GCC, though the output code is nowhere
> near as optimized.

Unfortunately, TCC is also lacking features. And using a different
compiler for debug builds than for production builds is a bad idea - if
you run into bugs of the production build compiler, what do you do then?
The usual Forth approach to coding is making small incremental changes,
because then you don't have to search long for the reasons why it
doesn't work - it's very likely the small change you just did now.

>> That also guides to my most-used debugging method: Inserting ~~ in
>> suspicious places.
>
> This still takes a lot of runs of the program and possible creation of
> new test cases, which can be pretty tedious.

Well, it does not feel "a lot" if you can do these runs pretty quickly.

>>> IMHO Haskell's type system makes it practical to program in a style
>>> that while not impossible, would be much harder to manage in
>>> Forth....
>> I'm not sure why you claim it is error-prone and to be avoided....
>> Forth is a programming language which tells you to avoid unnecessary
>> abstractions.
>
> Right, the reason it tells you to avoid unnecessary abstractions is
> that using abstraction in Forth is error-prone.

No, that's not the case. You should avoid unnecessary abstractions
since they don't pay off. You can use necessary abstractions, and are
encouraged to do so.

> I wasn't thinking really
> of postpone and create/does, but more of a style where you pass around
> execution tokens a lot, and those xt's may take other xt's as
> arguments
> to invoke over generic data structures, and so on.

After I added quotations to my system, I started doing that regularly.
Not exactly as in Haskell, but MINOS, using an OOP system, does that
sort of stuff. Juggling around many things on the stack is bad Forth
code, so pass xts around that take another xts quite likely will result
in many parameters on the stack. Don't do that.

The OOP system I use in MINOS handles that: You pack the several xts
into one class, and use that. No need for several xts flying around,
the class framework wrap them up into one entity, which is much easier
to pass around.

> In Haskell, it's
> natural to program that way, and the code still feels solid. In
> Scheme or Python you can write basically the same code, but with no
> type system watching over you, it feels like walking on a tightrope
> without a safety net.

Don't fear the program crash! As I said, in a strong typed language, I
feel like in a straightjacket. I wouldn't walk a tightrope in such a
language, regardless of safety net or not.

> I've programmed that way in Forth a little bit, but have been
> advised against it.
>
>> No type system prevents programs from going wrong.
>
> Well, I'd say a well-typed program, including something like Lisp with
> runtime type-checking, can at least have well-defined semantics, while
> an untyped (e.g. Forth or C) program can go completely into the weeds
> if there is a type error (such as a subscript overflow).

A subscript overflow is not exactly a type error.

That's exactly what I don't like. This is a rather complicated thing,
and I'm sure neither of us will write a perfect program first time. As
I try to write incremental programs, my first approach to a r/b tree
would be a general tree program, and let the tree be as unbalanced as I
like. If this works, I would start adding balancing rotation
operations, one after the other (you know, there are several cases you
have to think about). Each of them is tested, but of course, the tree
will still be lopsided.

Maybe you can do that in Haskell, too, by just trying with the full
blown type, and doing the test runs with a reduced type information,
which doesn't care about balancing.

> It would be pointless to have assert statements in the
> executable since the compiler has statically verified that the
> asserted
> conditions hold. I would not call this low-hanging fruit. It's a
> sophisticated condition being checked, that's a source of bugs in
> other real-world implementations, and the compiler verifies it to
> higher confidence than even quite a lot of unit tests could give.
>
> As an even more extreme example, Coq's type system is even stronger
> than Haskell's: it can express any mathematical proposition, so it has
> to be Turing complete, meaning it can't do inference and you have to
> manually
> supply type derivations (which is tedious). But it can encode (for
> example) the semantics of assembly code fragments (Hoare triples) as
> types. So if you have a compiler optimization pass that is annotated
> to take one fragment and returns another fragment of the same type,
> the Coq typechecker is able to verify that the input and output have
> the same semantics and the optimization pass has not introduced any
> semantic
> bugs. I think I mentioned before, a sizable part of a C compiler has
> been written that way (CompCert). This is not low hanging fruit at
> all. It is probably the future, especially as better automation
> becomes available for developing this sort of code.

Calling this still a "type system" is a misnomer. Yes, this is no low-
hanging fruit, but as you said, it is also tedious to use. And if
that's useful during development depends on the error message. Let's
say I have a code transformation pattern

BEGIN code WHILE REPEAT -> BEGIN code UNTIL

to skip the empty part between WHILE and REPEAT, the transformation is
wrong, because the flag for WHILE means the opposit as for UNTIL. If
the code system tells me just "your transformation is wrong", then I
have no clue why, and can only guess. If I unit-test this thing, I'd
give it a simple task and look at the results, and since the results are
runable programs, I'll see why the two are different.

>> while at the same time putting a straitjacket onto the programmer.
>> At least that's how I feel when I program in a language with a strong
>> type system. The compiler tells me "no, you can't do this", and "no,
>> you can't do that".
>
> I never felt terribly straitjacketed programming in C, but I also felt
> that the type system wasn't helping me that much.

C has no really strong type system. A type mismatch usually results in
a warning, it doesn't even fail to compile. I'm not that much
complaining about C, C's type system is more a simple operator
overloading system than anything else.

> I was comfortable
> programming with lots of void*'s, and programming in Lisp with runtime
> types. Trying Haskell was really eye-opening for me. I'm a long way
> from being a Haskell expert but I find it tremendously interesting and
> different (whether that means "better" is of course a separate
> matter).

Yes, of course. It is quit different.

>>> http://cdsmith.wordpress.com/2011/01/09/an-old-article-i-wrote/
>> Performance is not a problem? Come on. I'm constantly seeing
>> software which is slow as molasses,
>
> He's talking about compiled code with runtime type checks, vs.
> compiled code that has been statically checked but otherwise does the
> same stuff,
> e.g. Lisp vs ML. If the compiler is any good, the performance
> difference is usually a small constant factor, maybe just a few
> percent. The large, order-of-magnitude slowdowns you're seeing in the
> examples you mention are due to architectural issues in the slow
> programs.

Yes. Usually several architectural issues stacked on each others, like
using a complicated delegate-style OOP program (nobody really wants to
solve the problem, so it gets delegated over and over again) on top of a
slow Java VM with a bad JIT - if there is a JIT at all.

>> What I think would be worth to do for analytic compilers which track
>> that information anyways: Have a stack effect checker.
>
> Yes, that would have caught my + vs. F+ bugs. StrongForth does
> that sort of checking as you're probably aware.

It does a bit more, and there's even a version which runs on top of
Gforth.

>> Warnings when it doesn't match, please, it should compile, because
>> running it (with inserted ~~) will identify the problem quickly.
>
> GHC now has a command-line option that lets it produce executable code
> even if the program has type errors. You then get a runtime error
> only
> if the program tries to actually evaluate an ill-typed expression.

Nice. This allows you to check what actually happens.

> This turns out to be handy during development even though the compiler
> has
> already told you where the errors are. It's sometimes useful to be
> able test the successfully compiling parts of your program right away,
> postponing dealing with the unsuccessful parts til later.

Given that fact, I'm less opposed than before. How useful is GHCi (the
interactive command line)?

>> Forth's interactivity and abstraction avoidance is what makes it
>> strong. Interactivity is more than just a command line promt, it
>> also
>> means that you can recompile quickly. "Blink", not "lunch".
>
> I sometimes like to imagine what it must have been like to program in
> Forth or Lisp in the glory days of those languages. I'd be interested
> in seeing a demo sometime (maybe on video) of someone hacking on Forth
> code that does something complicated, using good interactive Forth
> tools.

We Forthers really try hard to not do something complicated ;-). When I
implemented bigForth' fast dictionary search, I explored several
options, hashing and AVL trees. AVL trees were more complicated, and
they lost to hashing in every metric: Time to write, execution
performance, memory usage, and bugs to fix during development.

In many cases you have an option which is simple, fast, and correct.
Don't try to use the other option.

> When I started using Python, I found myself thinking "this is
> what the old-time Maclisp hackers must have felt like". Haskell is
> different, completely different, a vision as powerful as Lisp but
> unlike
> anything that had been used for programming before. That in some
> sense outweighs any difficulties involved in trying to actually use
> it. ;-)

I'm still wondering how useful that would be for me. The main
challanges in the programs I write are the outside world, not the inner
logic of the program. E.g. take my net2o flow control, which took me
quite some time to develop. The code for it is rather simple, and it
always was rather simple, didn't crash or anything. That's not the
challange. The challange is to fill a network with packets just fast
enough, so they don't pile up in buffers, but yet leave no unused
bandwidth under real world conditions, which means things like Wifi with
rapidly changing quality, competing with multiple TCP/IP, BitTorrent or
net2o itself. This was a serious issue which I underestimated, given
how bold other people were about their results (like LEDBAT). I thought
I could just copy that, but it turned out to be not good enough.

A type system won't help at all here. The type system will catch the
low hanging fruits like f+ vs. + or similar. I don't have problems with
those, these are "declinations", and something the human brain can
handle quite well (the grammar engine).

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> No, I'm comparing a bloated Java+C++ project to a non-bloated Forth
> project. But even when I compare two non-bloated projects, GCC is
> hellish slow.

Oh ok, yeah, but I'd even say these days that GCC is bloated.

> Unfortunately, TCC is also lacking features. And using a different
> compiler for debug builds than for production builds is a bad idea - if
> you run into bugs of the production build compiler, what do you do then?

I'd think you have to test your production builds very thoroughly in any
case. TCC might be useful for rapid development and initial testing.

I think if I did anything serious with C these days, I'd also want to
test it with KCC, a very slow interpreter designed to make sure that if
your program attempts undefined behavior (which is ridiculously easy in
C), it will crash with an error message, rather than doing something
unpredictable and going on its way. Some info:

http://blog.regehr.org/archives/523

That guy's blog has lots of other good stuff too, that all makes me want
to stay far away from C.

>> This still takes a lot of runs of the program

> Well, it does not feel "a lot" if you can do these runs pretty quickly.

Yeah, that isn't always completely feasible though.

>> style where you pass around execution tokens a lot, and those xt's

>> may take other xt's as arguments ...

> After I added quotations to my system, I started doing that regularly.

I have to wonder how much debugging headache that created. Was it
a problem?

> A subscript overflow is not exactly a type error.

I think subscript overflow is considered a type error in the type system
literature, because if p is a pointer to type Foo, then p+i also has
type pointer to Foo, but if i is out of range then p+i may actually
point to something other than an Foo.

>> Red-black trees are binary trees...

> That's exactly what I don't like. This is a rather complicated thing,
> and I'm sure neither of us will write a perfect program first time.

But the idea is that with the right language features, we -can- get
these programs perfect the first time, if we mean the first time we try
to actually run the program. Of course it may take a lot of tries to
get the compiler to stop flagging errors, before we can run the program
that first time.

>> a sizable part of a C compiler has been written that way (CompCert).

> Calling this still a "type system" is a misnomer.

But it really is a type system! It's the Haskell type system on enough
steroids that it can no longer do automatic inference and needs a lot of
manual help, but it's a type system in the purest sense. It's fantastic
and wonderful from a mathematical standpoint even if it's useless in
practice. The theory behind it (constructive type theory) was developed
by a philosophical logician (Per Martin-Löf) in the 1970's, propagated
from there through mathematical logic and into CS theory, and has just
started appearing in actual programming languages in the last decade or
so, so it's still bleeding edge. I haven't used it yet (so I probably
still have some misconceptions) but I've been reading about it, and one
of my goals is to build up some skill with it pretty soon. Right now
only a few nerds care about it, but I think it's going to become
pervasive and important as the technology matures. There are some
online books:

1. http://www.cis.upenn.edu/~bcpierce/sf/
2. http://adam.chlipala.net/cpdt/
3. http://www.paultaylor.eu/stable/Proofs+Types.html

The first is pretty readable and I've been looking at it, the second
goes into perhaps more depth, and the third is pure theory and I don't
understand it, but I mention it for completeness.

> If the code system tells me just "your transformation is wrong", then
> I have no clue why, and can only guess.

I think in practice it's not that hard to figure out where the error is
when the compiler complains. There are some interactive tools (an IDE
and some Emacs modes) that let you navigate the types from the inside
outward or some such. I saw a demo of one of them and the guy could
operate it pretty fast, but I don't know how to use it myself for now.

> Yes. Usually several architectural issues stacked on each others, like
> using a complicated delegate-style OOP program

The functional programming crowd seems pretty opposed to OOP, e.g.:
http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/
"Object-oriented programming is eliminated entirely from the introductory
curriculum, because it is both anti-modular and anti-parallel by its
very nature, and hence unsuitable for a modern CS curriculum."

That's from a CMU professor about their new intro programming course,
which uses ML. The guy is one of ML's designers and he doesn't like
Haskell either, so hmm... ;-)

>> test the successfully compiling parts of your program right away,
>> postponing dealing with the unsuccessful parts til later.
> Given that fact, I'm less opposed than before. How useful is GHCi (the
> interactive command line)?

It's pretty useful, especially the more recent versions that remove some
annoying restrictions of the older ones. It's still an interpreter
that's maybe 10x slower than running compiled code. There's an Emacs
mode that lets you write Haskell code in one window and run GHCi in
another window and quickly send Emacs buffers to GHCi, sort of like
gforth.el. I think one tends to develop in a less intensely interactive
manner than in Forth though, in part because more time is spent writing
out static descriptions in the form of types.

>> Haskell is different, completely different...

> I'm still wondering how useful that would be for me. The main

> challanges in the programs I write are the outside world...

Hmm, I'd say the issues you're dealing with area in an area that has
historically been rather hard to control with Haskell. Recently there
have been a bunch of attacks on the problem (called enumeratees,
conduits, etc.) that are improving the situation, but are still in a
state of rapid change and require building up a significant skill level
before they can be used at all. So as an immediate practical tool for
those purposes, Haskell might not be ready yet. You might look at
Erlang.

That said, I've put a lot of effort into studying Haskell and its
surrounding infrastructure (e.g. I've learned a fair amount of logic) in
the past few years, and I think it's been worth it from a mental clarity
point of view, even if I don't end up using it directly for practical
programming. It's the same sort of benefit that one gets from
practicing some assembly coding, except from the opposite direction:
assembler is too low-level for most everyday use, and Haskell may be too
high-level, but knowing either brings increased clarity to the practical
stuff in the middle. Similar things have long been said about Lisp.

> The challange is to fill a network with packets just fast enough, so
> they don't pile up in buffers, but yet leave no unused bandwidth under
> real world conditions, which means things like Wifi with rapidly
> changing quality, competing with multiple TCP/IP, BitTorrent or net2o
> itself.

But this sounds like a computational problem, tracking the capacity
and contents of all those channels, and periodically deciding what
to do next. Haskell may be fine for that.

> A type system won't help at all here. The type system will catch the
> low hanging fruits like f+ vs. + or similar.

Really, I think that underestimates how expressive and useful a serious
type system is. Here is a cool paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.5859&rep=rep1&type=pdf

The author read a Google publication about its parallel MapReduce
framework, which gave an overview in which some details were unclear.
And by describing the understandable parts as Haskell types, he was able
to use the Haskell typechecker to figure out stuff that wasn't clear in
the Google paper.

Anecdote: the best programmer I know (the initial author of GCC and
Emacs--you know who I mean) likes to tell about when he first put
automatic parenthesis balancing into Emacs, so that when you type a
right-paren, the cursor momentarily bounces back to the matching
left-paren. He said that before he implemented that feature, he didn't
have too bad a time writing properly nested Lisp code manually, but
after using the new automatic balancing for a few days, he lost the
ability to do it by hand. And his conclusion was that this purely
mechanical skill had been tying up a significant amount of his
brainpower that he could now use for more productive purposes.

It's the same way IMHO with programming language features. The more
they do for you automatically, the more your own ability is freed up to
do stuff that can't be automated.

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>Do you mean type errors that the compiler didn't notice?
> No, I mean that there are far fewer type errors in my Forth code than
> type error messages for my Haskell code.

That could be a matter of differing programming styles between the two
languages. Like in Forth, if you have a value denoting an optional
string parameter, you might encode it as a null pointer if the string is
not present; or maybe you'd pass it as a struct with some kind of flag
indicating presence or absence. If there is some sort of error in
passing this around, it's not a type error, it's just a runtime bug. In
Haskell, you'd use a type of Maybe String, and then there are
potentially type errors that in Forth would just be bugs.

Then again it could be a matter of what you're used to.

>>quite abstract style involving higher-order functions...

> I would have thought that it's the bread and butter of programming in
> Scheme.

I think it's even more so in Haskell. Like the way one usually handles
iteration with map or fold instead of with recursion. I haven't seen
that much Scheme code written by experts though.

> I doubt that very much, because the programmer cannot write correct
> programs if he does not keep track of the types himself.

Yes of course you have to think about the types, but (compared to a
typeless language) you can let up a little on vigilance towards them and
devote your attention to other aspects of the program, since the
typechecker will catch the errors automatically. It's just like
interactively trying things in Forth except it's at compile time. You
can write some code that looks reasonable, then throw it at the
typechecker to see what happens, instead of agonizing over it checking
all the type assignments by hand.

Also, types can get very complicated, like in that red-black tree
example, where types track everything that happens to a complex data
structure through a complicated function. The corresponding situation
in Forth might be to treat stack effects as types, so some internal word
in the program may be operating on a stack dozens of levels deep, with a
hypothetical type checker keeping track of the whole stack contents so
it could (maybe only sometimes) statically detect overflow. A human
normally wouldn't track that carefully.

[Paul E. Bennett]

Elizabeth D. Rather wrote:

[%X]

>> Anyway, if a type-checked language lets me write a page full of code and
>> fix the compile-time errors to usually get working program, while the
>> typeless counterpart makes me stop what I'm doing after basically every
>> single line to check for problems the type checker would have caught
>> automatically, I'd say the type checker has made itself worthwhile.
>
> Unit-testing every definition pays off handsomely in saved debugging
> time by catching all kinds of bugs, not just type errors.
>
> And my experience is similar to Anton's, in that I make very few type
> errors. This may be because I'm accustomed to matching the right
> operators to the right data type, whereas folks who are used to
> languages that do type inference are less conscious of it. But the
> majority of errors (not only for me but for programmers I work with) are
> logic/algorithm errors, and they're readily detected by unit testing
> each definition. Takes seconds, can save hours!

Writing a whole page of code at a time just has the wrong feel to doing the
job right. Concentrate on the correctness of one function at a time, review
the intent (as expressed in the glossary text you wrote to specify what was
to happen) and test each word as you complete it (ensuring it meets the
specification of the glossary). On this basis I built the techniques for
certification of Forth code to ensure compliance with specification. No real
hunting required for the hidden bugs as you should expunge them as you go to
ensure they are not introduced in the first place. Of course, you need to
really concentrate on getting the specification right first.

--
********************************************************************
Paul E. Bennett...............<email://Paul_E....@topmail.co.uk>
Forth based HIDECS Consultancy
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-510979
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

[Mark Wills]

On Aug 27, 12:14 pm, "Paul E. Bennett" <Paul_E.Benn...@topmail.co.uk>
wrote:

> Paul E. Bennett...............<email://Paul_E.Benn...@topmail.co.uk>

> Forth based HIDECS Consultancy
> Mob: +44 (0)7811-639972
> Tel: +44 (0)1235-510979
> Going Forth Safely ..... EBA.www.electric-boat-association.org.uk..

> ********************************************************************- Hide quoted text -
>
> - Show quoted text -

Agreed. And you also have to accept that you can't get your
documentation 100% perfect up-front. It's just a fact of life that
you'll discover something during the physical implementation that may
require you to add a new function (perhaps to handle an unanticipated
exception, for example) that will require you to re-vist and update
your documentation.

It's not Necessarily a design failure. It's just reality!

We spend weeks working on up-front software documentation. Working in
the mission-critical oil and gas business, it's just a normal part of
the design process. We're pretty good at it (we can design to SIL-1 on
our in-house designed and manufactured controllers) but we still come
across issues that we failed to anticipate, despite numerous peer
reviews and design reviews! They're never show-stoppers, but there's
always a gotcha lurking in there somewhere!

[Paul E. Bennett]

Mark Wills wrote:

[%X]

>> Writing a whole page of code at a time just has the wrong feel to doing
>> the job right. Concentrate on the correctness of one function at a time,
>> review the intent (as expressed in the glossary text you wrote to specify
>> what was to happen) and test each word as you complete it (ensuring it
>> meets the specification of the glossary). On this basis I built the
>> techniques for certification of Forth code to ensure compliance with
>> specification. No real hunting required for the hidden bugs as you should
>> expunge them as you go to ensure they are not introduced in the first
>> place. Of course, you need to really concentrate on getting the
>> specification right first.

> Agreed. And you also have to accept that you can't get your
> documentation 100% perfect up-front. It's just a fact of life that
> you'll discover something during the physical implementation that may
> require you to add a new function (perhaps to handle an unanticipated
> exception, for example) that will require you to re-vist and update
> your documentation.

This is so true too. I estimate that you will probably visit each part of
the system 3 times during development (especially working on critical
systems).

> It's not Necessarily a design failure. It's just reality!
>
> We spend weeks working on up-front software documentation. Working in
> the mission-critical oil and gas business, it's just a normal part of
> the design process.

Do you have a good grasp of the total concept at that time or is the
specification still a collection of "I would like" type items? I have seen
many organisations that do the up-front documentation on half baked design
specs that still have lots of un-answered questions. The trick is usually to
be a lot clearer about the full explicit requirements that will mean mission
success early enough, even if all the fine details haven't yet emerged. This
may take a number of review sessions that truly walk the problem space
before the design really begins.

> We're pretty good at it (we can design to SIL-1 on
> our in-house designed and manufactured controllers) but we still come
> across issues that we failed to anticipate, despite numerous peer
> reviews and design reviews! They're never show-stoppers, but there's
> always a gotcha lurking in there somewhere!

There is no reason why you shouldn't deal with SIL-3 or SIL-4 requirements
if you are able to improve your early design and development processes.
Eliminate the systematic bugs before they get into the system design and you
save a lot of time, effort and money in the later stages.

--
********************************************************************
Paul E. Bennett...............<email://Paul_E....@topmail.co.uk>

[Doug Hoffman]

On 8/25/12 6:09 PM, Paul Rubin wrote:
> Doug Hoffman <glid...@gmail.com> writes:

>> If you are ... testing each word [ or unit , added 8/27 dbh ] before

>> continuing then that "+ instead of F+" should have become immediately

>> apparent...

> As I remember, it wasn't so immediately apparent what the problem was,
> since the failure didn't occur til a little ways after the + happened.
> And the symptom was that the program crashed without much clue about
> what had happened.

Interesting and surprising to hear that.

> Anyway, if a type-checked language lets me write a page full of code and
> fix the compile-time errors to usually get working program, while the
> typeless counterpart makes me stop what I'm doing after basically every
> single line to check for problems

No. Stopping after every line isn't exactly necessary. Depends on the
length of your words and what you would consider a coherent/testable
unit (may be several words as a group).

> the type checker would have caught
> automatically, I'd say the type checker has made itself worthwhile.

You might want to try StrongForth. Though it doesn't seem to have
gained much traction.

-Doug

[Paul Rubin]

Doug Hoffman <glid...@gmail.com> writes:
>> And the symptom was that the program crashed without much clue about
>> what had happened.
> Interesting and surprising to hear that.

Well, the issue probably would have been obvious to a more experienced
Forth user--I remember staring at the code for a while and seeing
nothing wrong, and having to go to some effort to debug the crash, and
as mentioned it took a couple of repeats for the lesson to sink in.

> No. Stopping after every line isn't exactly necessary. Depends on
> the length of your words and what you would consider a
> coherent/testable unit (may be several words as a group).

Most of my words are one line. Testing several as a group does seem to
make more sense.

> You might want to try StrongForth. Though it doesn't seem to have
> gained much traction.

Yeah, if I were doing anything serious with Forth I suppose I'd consider
it. For just fooling around as I'm doing, regular Forth's lack of
safety probably builds character ;-).

[Andrew Haley]

Paul Rubin <no.e...@nospam.invalid> wrote:
> The functional programming crowd seems pretty opposed to OOP, e.g.:
> http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/
> "Object-oriented programming is eliminated entirely from the
> introductory curriculum, because it is both anti-modular and
> anti-parallel by its very nature, and hence unsuitable for a
> modern CS curriculum."
>
> That's from a CMU professor about their new intro programming course,
> which uses ML. The guy is one of ML's designers and he doesn't like
> Haskell either, so hmm... ;-)

As far as I can tell from that article and the following discussion,
its justification is mostly in terms of formal methods: formal methods
haven't made much progress with OO, so OO must be bad. (Yes, I'm
oversimplifying.) And the claims that functional programming is more
parallel than OO are a bit much. How do threads in Concurrent Haskell
communicate? Through shared state, just as threads in imperative and
object-oriented languages do. I don't know of another way do do it.
Of course, you can functions like map and reduce on top of threads,
but you don't need functional languages for that.

One thing I agree with: Java isn't a great language for introductory
programming courses, not because it is object-oriented (that's good)
but because it requires some boilerplate. Compare

class HelloWorld {
static public void main( String args[] ) {
System.out.println( "Hello, World!" );
}
}

and Python

print "Hello, World!"

not to mention

.( Hello, World!)

No contest!

Andrew.

[Bernd Paysan]

Paul Rubin wrote:
> Oh ok, yeah, but I'd even say these days that GCC is bloated.

I mean it is hellish slow to compile a non-bloated project. GCC+bloated
project=lunch. Actually, I compiled Android from source over night,
because I don't have the same sort of computing power as Google ;-).
This feels like programming was 40 years ago on mainframes - at the time
where Forth was invented.

>>> style where you pass around execution tokens a lot, and those xt's
>>> may take other xt's as arguments ...
>> After I added quotations to my system, I started doing that
>> regularly.
>
> I have to wonder how much debugging headache that created. Was it
> a problem?

No. The quotations are short, and you can only test them in context, so
you just run the thing in context, it's no problem that the quotation
has no name and can't be called directly on the command line. It does
not make that much sense as stand-alone program. A quotation should be
short, and use tested factors (which then have names).

You debug quotations with ~~ statements inserted at interesting places
if necessary (most quotations are right first time, because they should
deliberately be simple).

>> A subscript overflow is not exactly a type error.
>
> I think subscript overflow is considered a type error in the type
> system literature, because if p is a pointer to type Foo, then p+i
> also has type pointer to Foo, but if i is out of range then p+i may
> actually point to something other than an Foo.

I'd rather say an array with index [0..n] has a subtype of int as index,
but that is an algebraic constraint. You had this example with the type
system that allowed a lot of algebraic constraints, but I would not call
that a type system anymore. It's more a formal verification system,
following the same sort of algebra you use for type systems. The self-
advertizing of Coq also says it's a formal proof management system.

>>> Red-black trees are binary trees...
>> That's exactly what I don't like. This is a rather complicated
>> thing, and I'm sure neither of us will write a perfect program first
>> time.
>
> But the idea is that with the right language features, we -can- get
> these programs perfect the first time, if we mean the first time we
> try to actually run the program.

Indeed. But it's the attitude of "running the code is to be done as
late as possible". You should not do that, at least not in Forth. You
should start writing a program, and when you get to the point where you
actually can try something (which is early), you should let it run. It
is rewarding to get something done, even if it is little, and a process
that is rewarding the programmier is improving productivity and makes it
more fun to write programs.

Humans are motivated by positive feedback, so fun is important. It's
frustrating to only see error messages from the compiler. When I'd be
writing an r/b tree program, the first step would be to insert nodes and
print the tree. Hey, great, I can insert nodes and print a tree. It's
not balanced, but I can now add tree rotation operations. And print the
rotated tree. It's a hands-on experience. The program does something
in all stages of development, though it is not perfect at the first run.

> Of course it may take a lot of tries to
> get the compiler to stop flagging errors, before we can run the
> program that first time.

Yes, but that's not "right first time". A program is "right first time"
if - after internal debugging - it gets out error-free to the customer.
What happens in between the first keystroke and the release to customer
is entirely yours.

This sort of "getting the program to finally compile" is frustrating for
me, and what I observed from other people is that after it finally
compiles, they are happy when it sort-of-runs, and are not interested in
more debugging.

> Right now
> only a few nerds care about it, but I think it's going to become
> pervasive and important as the technology matures. There are some
> online books:
>
> 1. http://www.cis.upenn.edu/~bcpierce/sf/
> 2. http://adam.chlipala.net/cpdt/
> 3. http://www.paultaylor.eu/stable/Proofs+Types.html
>
> The first is pretty readable and I've been looking at it, the second
> goes into perhaps more depth, and the third is pure theory and I don't
> understand it, but I mention it for completeness.

Thanks for the links.

>> Yes. Usually several architectural issues stacked on each others,
>> like using a complicated delegate-style OOP program
>
> The functional programming crowd seems pretty opposed to OOP, e.g.:
> http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-
freshmen/
> "Object-oriented programming is eliminated entirely from the
> introductory curriculum, because it is both anti-modular and
> anti-parallel by its very nature, and hence unsuitable for a
> modern CS curriculum."
>
> That's from a CMU professor about their new intro programming course,
> which uses ML. The guy is one of ML's designers and he doesn't like
> Haskell either, so hmm... ;-)

Maybe a bit biased ;-).

>> Given that fact, I'm less opposed than before. How useful is GHCi
>> (the interactive command line)?
>
> It's pretty useful, especially the more recent versions that remove
> some
> annoying restrictions of the older ones. It's still an interpreter
> that's maybe 10x slower than running compiled code. There's an Emacs
> mode that lets you write Haskell code in one window and run GHCi in
> another window and quickly send Emacs buffers to GHCi, sort of like
> gforth.el.

Nice. The fact that it still doesn't have an incremental compiler is a
bit lame ;-).

>> The challange is to fill a network with packets just fast enough, so
>> they don't pile up in buffers, but yet leave no unused bandwidth
>> under real world conditions, which means things like Wifi with
>> rapidly changing quality, competing with multiple TCP/IP, BitTorrent
>> or net2o itself.
>
> But this sounds like a computational problem, tracking the capacity
> and contents of all those channels, and periodically deciding what
> to do next. Haskell may be fine for that.

The problem is: The buffers won't tell you. At least not as long as
they are IP routers, not net2o switches - and even those won't tell you
the whole story, because telling means network traffic. The network
should be used for the actual data, management (including flow control)
should be minimized in bandwidth.

The resulting program I have is fairly trivial, and it should be
possible to implement it in whatever programming language you like,
given you have a precise real-time clock and access to a socket
interface.

> Anecdote: the best programmer I know (the initial author of GCC and
> Emacs--you know who I mean) likes to tell about when he first put
> automatic parenthesis balancing into Emacs, so that when you type a
> right-paren, the cursor momentarily bounces back to the matching
> left-paren. He said that before he implemented that feature, he
> didn't have too bad a time writing properly nested Lisp code manually,
> but after using the new automatic balancing for a few days, he lost
> the
> ability to do it by hand. And his conclusion was that this purely
> mechanical skill had been tying up a significant amount of his
> brainpower that he could now use for more productive purposes.

Hehe. Yes, that's a defect of Lisp, which makes it hard to use. Some
derivatives used ] to close all brackets, which is somewhat helpful.

> It's the same way IMHO with programming language features. The more
> they do for you automatically, the more your own ability is freed up
> to do stuff that can't be automated.

As Forther, I like to automate things, but especially those things that
helps me to reduce typing. That's why we extend the compiler. On the
other hand, Forth does not automate the stack, which is something pretty
basic, and almost every other language automates the stack. We don't,
and we have a reason for not doing so. It clearly does consume
brainpower by not doing so, but it encourages factoring, which is worth
the price.

[Bernd Paysan]

Andrew Haley wrote:
> One thing I agree with: Java isn't a great language for introductory
> programming courses, not because it is object-oriented (that's good)
> but because it requires some boilerplate. Compare
>
> class HelloWorld {
> static public void main( String args[] ) {
> System.out.println( "Hello, World!" );
> }
> }
>
> and Python
>
> print "Hello, World!"
>
> not to mention
>
> .( Hello, World!)
>
> No contest!

Java is a bit inconsistent there in that you don't need to import
java.lang.system to do that. I would have expected so, but apparently,
System is accessible even without a boiler plate.

[Elizabeth D. Rather]

On 8/25/12 7:44 PM, Paul Rubin wrote:

...

>>> IMHO Haskell's type system makes it practical to program in a style
>>> that while not impossible, would be much harder to manage in Forth....
>> I'm not sure why you claim it is error-prone and to be avoided....
>> Forth is a programming language which tells you to avoid unnecessary
>> abstractions.
>
> Right, the reason it tells you to avoid unnecessary abstractions is that
> using abstraction in Forth is error-prone. I wasn't thinking really of
> postpone and create/does, but more of a style where you pass around
> execution tokens a lot, and those xt's may take other xt's as arguments
> to invoke over generic data structures, and so on. In Haskell, it's
> natural to program that way, and the code still feels solid. In Scheme
> or Python you can write basically the same code, but with no type system
> watching over you, it feels like walking on a tightrope without a safety
> net. I've programmed that way in Forth a little bit, but have been
> advised against it.

I meant to comment on this last week, but got distracted.

I don't like "a style where you pass around execution tokens a lot, and

those xt's may take other xt's as arguments to invoke over generic data

structures, and so on" but my reasons have nothing to do with data types
or type checking, pro or con. It's just not a natural style for Forth.
Most of the time, words are to be called, not treated as data. To be
sure, there are times when explicit use of an xt is appropriate (with
CATCH, with DEFERs, and in indexable tables of function pointers,
mainly), but those are very specific application needs. The examples of
that sort of thing I've seen posted here all strike me as wildly
unreadable and unnecessarily obscure, and usually quite inefficient.

[Paul Rubin]

Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>> The functional programming crowd seems pretty opposed to OOP, e.g.:
>> http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/

> As far as I can tell from that article and the following discussion,

> its justification is mostly in terms of formal methods...

I hear similar things from other FP folks, and it may be partly
tribalism, but additional objections are 1) subtype polymorphism is
messy compared with Haskell's bounded polymorphism; 2) inheritance
making the program flow confusing; 3) the usual gripes about mutable
state, especially mutable state spread all over the place.

> And the claims that functional programming is more parallel than OO
> are a bit much. How do threads in Concurrent Haskell communicate?
> Through shared state,

Ah, but one does not need Concurrent Haskell to get parallel execution.
Haskellers distinguish between concurrency (multiple threads of
execution to deal with non-deterministic, asynchronous inputs from the
outside world) and parallelism (using multiple CPU cores simultaneously
to do a deterministic computation faster). Concurrent threads will
usually communicate through MVars (or STM), and yeah, these are mutable
cells, but typically there'd be a very small number of them per thread
for communications purposes, and the stuff happening within a thread
wouldn't involve mutation the way OO programs usually have objects
changing state everywhere.

Haskell parallelism doesn't require any visible mutation or threads at
all, e.g. the "par" combinator: x `par` y advises the compiler that it
can likely get some speedup by computing x and y in parallel, but the
result is exactly the same as if they were done sequentially. The
programmer doesn't have to deal with any interthread communication,
state, locks, etc. at all. See:

http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores

for how it works. There are similarly things like parMap which is like
map but runs in parallel in CPU threads, and some stuff in progress that
can spin out parallel vector operations to a GPU, again with almost no
fuss to the programmer, no visible shared state, etc.

> and Python
> print "Hello, World!"

Unfortunately this breaks in Python 3 :-(

> not to mention
> .( Hello, World!)

Hmm,

: hw .( Hello, World!) ; Hello, World! ok
hw ok

;-)

[Paul Rubin]

Paul Rubin <no.e...@nospam.invalid> writes:
>> its justification is mostly in terms of formal methods...
> I hear similar things from other FP folks

Self-followup:

1) Clarification, by "similar" I just mean anti-OO sentiment in general,
not related to formal methods.

2) Also meant to add: one of the arguments for fancy static type systems
(stated explicitly in Pierce's book "Types and programming languages")
is that the types amount to lightweight formal methods, that can be used
without much fuss in everyday programming. They are no longer huge,
tedious, special purpose machinery used only for ultra-critical
high-budget applications like spacecraft. The red-black tree example I
gave earlier (GADT's verify the red-black tree invariants) is
illustrative of this.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> I mean it is hellish slow to compile a non-bloated project. GCC+bloated
> project=lunch.

Maybe C++ is partly to blame, because of header bloat, template bloat,
etc. Here is an interesting rant about how fast Turbo Pascal was,
attributing the speed (compared with C++) in part to language
differences:

http://prog21.dadgum.com/47.html

Ocaml's compiler is supposed to also be fast, though I haven't used it.

> You had this example with the type system that allowed a lot of
> algebraic constraints, but I would not call that a type system
> anymore. It's more a formal verification system, following the same
> sort of algebra you use for type systems. The self- advertizing of
> Coq also says it's a formal proof management system.

Well, people can call things whatever they want, but it's quite standard
terminology in the PLT community that these things are type systems; and
there is an amazing correspondence (the Curry-Howard correspondence)
between type systems and proof systems: types represent propositions and
programs represent proofs.

As an extreme example (this is handwaving, but I think has at least some
resemblance to reality): say you've got a type X representing planar
maps (as in "map of Europe"), and a type Y representing those maps with
an assignment of one of 4 colors to each country, such that countries
sharing borders have different colors. The famous 4-color map theorem
says (in one way to phrase it) that there exists a function F, whose
input type is X and whose output type is Y, i.e. given any map this
function will produce a 4-coloring for the map.

What this means is if you can actually code a function with such a type
signature and get it through the Coq type checker, then Coq has verified
that you have exhibited the asked-for function F, i.e. you have proved
the 4-color theorem, just by getting F to type-check, without having to
actually run it. The actual Coq proof of the 4-color theorem[1] is very
complicated, but I think it basically amounts to writing a function with
a certain signature and getting it to type-check.

> Humans are motivated by positive feedback, so fun is important. It's
> frustrating to only see error messages from the compiler.

But the error messages are feedback too (hey, a new motto, "GHC, the
compiler where fixing type errors is fun!!"). Anyway, of course one
does develop incrementally in practice. Get one thing to work (and
typecheck), get the next thing to work, etc.

> Yes, but that's not "right first time". A program is "right first time"
> if - after internal debugging - it gets out error-free to the customer.

There's another aspect: how do you convince the customer (or anyone
else) of the absence of errors? Of course you can fail to find test
cases that give wrong results, but that doesn't substitute for a
deductive process saying that no failure cases exist. Say there's a
spot in the code that will obviously crash if x=0, but that's ok, you've
got some sound but non-trivial reasoning showing that x>0 whenever that
spot is reached. Maybe you have to explain this reasoning in code
review, and perhaps you write a longish comment explaining it. Someone
else perhaps carefully reads the comment, checking all the claims in the
comment against the code to make sure they are valid.

Now the customer asks for a new feature, that you implement with a code
change. What happened to the validity of that comment? It has to be
checked again, burning somebody's time (maybe yours) every time the code
changes, and that ignores the possibility of making a mistake the 37th
time you check the comment.

That's what I think is one of the interesting visions is of Haskell (not
currently achieved in practice, but something to aim for). In
traditional programming, you reason in your head to figure out the
computation process, implement the process as code, but the reasoning is
at best written down as a comment. This is the "semantic gap" between
"what the programmer knows and what the language allows to be
stated".[2] In an idealized typed FP, the reasoning is written down as
part of the code, so the compiler can check it every time you recompile.

I believe from other people's reports and from (limited) personal
experience that Haskell is superior to Python in the following common
situation:

1) write and debug compplicated program. Deliver to customer.
2) Project is finished, so go work on other things.
3) 1 year later, customer asks for a new feature, and you have by now
forgotten most of how the program works. You have to patch it
without introducing bugs.

I can't compare it with Forth (not enough experience) but I have to
wonder if the situation is comparable. Automatic tests help, but they
aren't a silver bullet.

> I observed from other people is that after it finally compiles, they
> are happy when it sort-of-runs, and are not interested in more debugging.

That's a situation one might see with beginning programmers using Java
or something like that, but it's much different with experienced
programmers and Haskell-like languages.

> Nice. The fact that it still doesn't have an incremental compiler is a
> bit lame ;-).

Usually your program is in reasonable-sized, separately compiled
modules, so when hacking with ghci you're only recompiling the module
that you're actively working on. At least on a modern pc, this is fast
enough in practice.

> The problem is: The buffers won't tell you. At least not as long as
> they are IP routers, not net2o switches - and even those won't tell you
> the whole story, because telling means network traffic.

I guess I still don't understand this: you mean you want to model the
travel of packets in flight, so you can dynamically adjust things to
prevent congestion even in places outside your network that you can't
observe directly? That sounds cool but difficult.

Well, there is a joke FAQ built into the Haskell IRC bot, where no
matter what you ask, the bot replies "The answer is: yes! Haskell can
do that." This sounds like one of those types of problems. ;-).

[1] http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf
[2] https://personal.cis.strath.ac.uk/patricia.johann/popl08.pdf

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> In my experience such a basic error as writing a + where there should
> be an F+ shows up really quick, but maybe I avoid writing code where
> it would not show up quickly.

I think it took a while for me to debug because I hadn't yet gotten used
to hitting that kind of error.

> Some people like a stepping debugger, but in my experience it's a good
> recipe for wasting time. A back-stepping debugger with reverse
> watchpoints, now that would be useful

I find single stepping to be very helpful. I haven't tried a
back-stepping debugger but I can remember having wanted such a thing.

> Why would I stop after every line?

Other people on this newsgroup have been advising me to test each word
before writing the next one. Most of my words are 1 line. Yeah in
practice I tend to write several words before testing. It's certainly
seems true that testing in very small units helps quickly narrow what
part of the code is probably going wrong. Better diagnostics make that
narrowing less important, so I can code and test larger units, speeding
up development.

[Andrew Haley]

Bernd Paysan <bernd....@gmx.de> wrote:
> Andrew Haley wrote:
>> One thing I agree with: Java isn't a great language for introductory
>> programming courses, not because it is object-oriented (that's good)
>> but because it requires some boilerplate. Compare
>>
>> class HelloWorld {
>> static public void main( String args[] ) {
>> System.out.println( "Hello, World!" );
>> }
>> }
>>
>> and Python
>>
>> print "Hello, World!"
>>
>> not to mention
>>
>> .( Hello, World!)
>>
>> No contest!
>
> Java is a bit inconsistent there in that you don't need to import
> java.lang.system to do that. I would have expected so, but apparently,
> System is accessible even without a boiler plate.

You don't have to import java.lang.anything. That seems reasonable
enough.

Andrew.

[Andrew Haley]

Paul Rubin <no.e...@nospam.invalid> wrote:
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>> The functional programming crowd seems pretty opposed to OOP, e.g.:
>>> http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/
>> As far as I can tell from that article and the following discussion,
>> its justification is mostly in terms of formal methods...
>
> I hear similar things from other FP folks, and it may be partly
> tribalism, but additional objections are 1) subtype polymorphism is
> messy compared with Haskell's bounded polymorphism; 2) inheritance
> making the program flow confusing; 3) the usual gripes about mutable
> state, especially mutable state spread all over the place.
>
>> And the claims that functional programming is more parallel than OO
>> are a bit much. How do threads in Concurrent Haskell communicate?
>> Through shared state,
>
> Ah, but one does not need Concurrent Haskell to get parallel
> execution.

No, of course not: you can put the parallelism into a library if you
have an embarassingly parallel problem. But that's true of many
languages.

> Haskell parallelism doesn't require any visible mutation or threads
> at all, e.g. the "par" combinator: x `par` y advises the compiler
> that it can likely get some speedup by computing x and y in
> parallel, but the result is exactly the same as if they were done
> sequentially. The programmer doesn't have to deal with any
> interthread communication, state, locks, etc. at all.

Well, yes. Just like fork/join in Cilk plus. I think that the
parallel advantages of functional programming may have been oversold.
Sure, there are theoretical advantages, but do they actually result in
greater use of parallelism in practical applications?

>> not to mention
>> .( Hello, World!)
>
> Hmm,
>
> : hw .( Hello, World!) ; Hello, World! ok
> hw ok
>
> ;-)

Huh!? That's just a bug.

Andrew.

[Paul Rubin]

Andrew Haley <andr...@littlepinkcloud.invalid> writes:
> No, of course not: you can put the parallelism into a library if you
> have an embarassingly parallel problem. But that's true of many
> languages.

I think GHC's parallelization capabilities go beyond "embarassingly
parallel" (computations that are obviously independent). For example,
memoization in an imperative language usually works by updating some
kind of table to stored memoized values, and if you want to do this in
parallel you face the usual hassles of locks or maybe STM. In Haskell,
memoization is done with lazy evaluation and the GHC implemention of
this is already thread-safe, so you can memoize in a parallel program
without adding headaches.

> Well, yes. Just like fork/join in Cilk plus.

It looks like you have to be very careful in Cilk to make sure that the
parallel computations don't interfere with each other. Functional
purity in Haskell makes it easy to statically guarantee this. It
wouldn't surprise me if Cilk applications end up using functional-style
data structures instead of traditional imperative ones in places,
because of this non-interference.

> I think that the parallel advantages of functional programming may
> have been oversold. Sure, there are theoretical advantages, but do
> they actually result in greater use of parallelism in practical
> applications?

The notion from 20 years ago that FPL compilers were going to
parallelize stuff automatically (with no programmer advice or
annotations) seems to have failed, so I suppose it was oversold in that
sense. The overhead of dispatching calculations to multiple cores
outweighs the parallel speedup if the calculations are small, which the
compiler can't tell. Adding a few annotations at good parallization
opportunities gets around this problem, and is safe and easy compared to
imperative approaches. So it seems to me that there is more low-hanging
fruit available. I think it's not in widespread use yet mostly because
it is still pretty new.

>> : hw .( Hello, World!) ; Hello, World! ok
>> hw ok
>> ;-)
>
> Huh!? That's just a bug.

It looks like .( does what it's supposed to. It just surprised me and
it wasn't the equivalent of Python's print statement. I expected
something more like
." Hello, World!"

[Andrew Haley]

Paul Rubin <no.e...@nospam.invalid> wrote:
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>> No, of course not: you can put the parallelism into a library if you
>> have an embarassingly parallel problem. But that's true of many
>> languages.
>
> I think GHC's parallelization capabilities go beyond "embarassingly
> parallel" (computations that are obviously independent). For
> example, memoization in an imperative language usually works by
> updating some kind of table to stored memoized values, and if you
> want to do this in parallel you face the usual hassles of locks or
> maybe STM. In Haskell, memoization is done with lazy evaluation and
> the GHC implemention of this is already thread-safe, so you can
> memoize in a parallel program without adding headaches.

Well, yes, so you use STM for memoization. Where, exactly, is the
problem? I must be missing something.

>> Well, yes. Just like fork/join in Cilk plus.
>
> It looks like you have to be very careful in Cilk to make sure that
> the parallel computations don't interfere with each other.

I wouldn't have thought so: fork/join is for computations that can be
partitioned in some way. Of course, the partitioning has to be
correct.

> Functional purity in Haskell makes it easy to statically guarantee
> this. It wouldn't surprise me if Cilk applications end up using
> functional-style data structures instead of traditional imperative
> ones in places, because of this non-interference.

To the extent that functional-style data structures make sense, yes,
of course. I presume "functional-style" means write-once or some kind
of copy on write, which is well established.

>> I think that the parallel advantages of functional programming may
>> have been oversold. Sure, there are theoretical advantages, but do
>> they actually result in greater use of parallelism in practical
>> applications?
>
> The notion from 20 years ago that FPL compilers were going to
> parallelize stuff automatically (with no programmer advice or
> annotations) seems to have failed, so I suppose it was oversold in
> that sense. The overhead of dispatching calculations to multiple
> cores outweighs the parallel speedup if the calculations are small,
> which the compiler can't tell. Adding a few annotations at good
> parallization opportunities gets around this problem, and is safe
> and easy compared to imperative approaches.

But no easier than fork/join apart from the claim that "you have to be
very careful" of which I am not totally convinced. AFAIK functional
languages have no advantages over imperative languages in the area of
concurrency except the aforementioned checking. Of course proponents
of bondage and discipline languages will argue that everything is much
easier because we're protected from ourselves.

> So it seems to me that there is more low-hanging fruit available. I
> think it's not in widespread use yet mostly because it is still
> pretty new.

Perhaps. I've been massively impressed by the speed at which GCC is
adopting fork/join and transactions, and I suspect that it will have
alot more impact on real-world concurrency.

>>> : hw .( Hello, World!) ; Hello, World! ok
>>> hw ok
>>> ;-)
>>
>> Huh!? That's just a bug.
>
> It looks like .( does what it's supposed to.

Well, yes: the bug is in your program.

> It just surprised me and it wasn't the equivalent of Python's print
> statement.

Not exactly, no. These are just "Hello, World" programs in various
languages. All they have to do is print "Hello, World".

Andrew.

[Bernd Paysan]

Paul Rubin wrote:
> Well, people can call things whatever they want, but it's quite
> standard terminology in the PLT community that these things are type
> systems; and there is an amazing correspondence (the Curry-Howard
> correspondence) between type systems and proof systems: types
> represent propositions and programs represent proofs.

I don't think of types as such. A data type is a particular
representation of your data. You can have bytes, words, floats,
addresses, and combinations/tuples of those like strings (which starts
at an address, has a length, and a bunch of bytes/characters froming the
string).

> The actual Coq proof of the 4-color theorem[1] is
> very complicated, but I think it basically amounts to writing a
> function with a certain signature and getting it to type-check.

Coq's proof system is similar to other formal proof systems (the ones
formalized in the late 20th of the previous century).

>> Humans are motivated by positive feedback, so fun is important. It's
>> frustrating to only see error messages from the compiler.
>
> But the error messages are feedback too (hey, a new motto, "GHC, the
> compiler where fixing type errors is fun!!"). Anyway, of course one
> does develop incrementally in practice. Get one thing to work (and
> typecheck), get the next thing to work, etc.

No, an error message is a negative feedback, it tells you "you did
something wrong".

>> Yes, but that's not "right first time". A program is "right first
>> time" if - after internal debugging - it gets out error-free to the
>> customer.
>
> There's another aspect: how do you convince the customer (or anyone
> else) of the absence of errors? Of course you can fail to find test
> cases that give wrong results, but that doesn't substitute for a
> deductive process saying that no failure cases exist.

I once had a customer who told me that he didn't believe the Shannon
Theorem. Well, I said, you can prove that it is correct. But that
didn't bother him much. Note also that Knuth once wrote "Beware: I have
proved this program currect, but didn't test it". The deducing process
is alway an equivalence check: The program and the specified conditions
are (after transformation) equivalent. The specification of the
conditions is just as bug-prone as the program itself (or even more), so
proving equivalence does not prove absense of bugs.

Almost 20 years ago, I had attended to a CS course which had as topic
"complex systems", and was really about using theoreme provers to aid
program development. Not as nice as Coq, but similar in spirit. The
language to specify conditions was more cumbersome to use and more
error-prone as to actually write the program and test it.

> Say there's a
> spot in the code that will obviously crash if x=0, but that's ok,
> you've got some sound but non-trivial reasoning showing that x>0
> whenever that
> spot is reached. Maybe you have to explain this reasoning in code
> review, and perhaps you write a longish comment explaining it.
> Someone else perhaps carefully reads the comment, checking all the
> claims in the comment against the code to make sure they are valid.

You shouldn't have non-trivial reasonings for that. Trivial reasonings
are ok, e.g. x is a pointer, and you don't pass null pointers around,
only allocated objects.

> Now the customer asks for a new feature, that you implement with a
> code
> change. What happened to the validity of that comment? It has to be
> checked again, burning somebody's time (maybe yours) every time the
> code changes, and that ignores the possibility of making a mistake the
> 37th time you check the comment.
>
> That's what I think is one of the interesting visions is of Haskell
> (not
> currently achieved in practice, but something to aim for). In
> traditional programming, you reason in your head to figure out the
> computation process, implement the process as code, but the reasoning
> is
> at best written down as a comment. This is the "semantic gap" between
> "what the programmer knows and what the language allows to be
> stated".[2] In an idealized typed FP, the reasoning is written down as
> part of the code, so the compiler can check it every time you
> recompile.

This is where I think it becomes silly. If you can write your reasoning
down in a formalized language, you should be able to get a working
program from that (e.g. using the methods Prolog uses). I also don't
think there is a semantic gap between programmer knowledge and program,
there usually is a semantic gap between what the programmer thinks is
sufficient to describe the problem, and what is actually needed to
implement it. The difference between idea and realization.

> I believe from other people's reports and from (limited) personal
> experience that Haskell is superior to Python in the following common
> situation:
>
> 1) write and debug compplicated program. Deliver to customer.
> 2) Project is finished, so go work on other things.
> 3) 1 year later, customer asks for a new feature, and you have by
> now
> forgotten most of how the program works. You have to patch it
> without introducing bugs.

If you have forgotten how most of your program works, adding a new
feature is futile. Well, at least in Forth, because there, you have
created a sort-of domain specific language, in which you will have to
write your new feature, as well. If you forgot how that works, you
won't be able to.

On the other hand, well organized programs don't fall apart when you
change things. The last really old project I've resurrected was an
eleven year old battery monitor simulator, and the request was to change
the waveform viewer to one I had done a year before, because the newer
one looked nicer (it was for a demo at Apple, and they have designers,
not engineers ;-). So I ripped the old waveform viewer out, put the new
one in, and with a small amount of testing, the program worked.

The key of success for this is to create components which are loosely
coupled, and not a tightly coupled mess which you can't untangle a year
later. I don't think it's a matter of programming language, you can
write bad programs in every language. Though, some programs make it
easier for bad programmers to be learned, and I'd say, Haskell is really
driving bad programmers to Python and PHP.

> I can't compare it with Forth (not enough experience) but I have to
> wonder if the situation is comparable. Automatic tests help, but they
> aren't a silver bullet.

But automated proofs are no silver bullet, either. Essentially, there
is no silver bullet.

> That's a situation one might see with beginning programmers using Java
> or something like that, but it's much different with experienced
> programmers and Haskell-like languages.

But then, you have a self-selected group of better programmers. Brooks
found that in his small test group, bad vs. good was by a factor of 20
apart. Having a self-selected group of good programmers is just
awesome. It's way more important than the programming language (though,
of course, good programmers select their own tools).

>> Nice. The fact that it still doesn't have an incremental compiler is
>> a bit lame ;-).
>
> Usually your program is in reasonable-sized, separately compiled
> modules, so when hacking with ghci you're only recompiling the module
> that you're actively working on. At least on a modern pc, this is
> fast enough in practice.

In Forth, you don't have to think about which part of the program you
are working at, it's fast enough to recompile the whole program, even if
the program is pretty large.

>> The problem is: The buffers won't tell you. At least not as long as
>> they are IP routers, not net2o switches - and even those won't tell
>> you the whole story, because telling means network traffic.
>
> I guess I still don't understand this: you mean you want to model the
> travel of packets in flight, so you can dynamically adjust things to
> prevent congestion even in places outside your network that you can't
> observe directly? That sounds cool but difficult.

Yes, but that's the requirement for an Internet protocol. The key to
success of course is to take the observable part of the data, and use
that. The observable part is the time when each packet arrives at the
destination, and that timing information is then used to do some
relatively simple calculations about what actuall packet rate is
achievable.

> Well, there is a joke FAQ built into the Haskell IRC bot, where no
> matter what you ask, the bot replies "The answer is: yes! Haskell can
> do that." This sounds like one of those types of problems. ;-).

Well, it's not about being able to do that, the code to do this
congestion control is actually rather trivial. What I said is that
having some typechecking in this quite trivial code isn't helpful. The
tough part is finding some quite trivial code which does avoid
congestions, and to do that, you need to look at what your program
actually does. This is trivial stuff, either: you just print out the
observed values, pass them to gnuplot, and view the plot.

Haskell would probably give me some headaches with the low-level code,
where I just need to get nanoseconds from the OS timer, and pack bytes
together into a packet to be send at the given time through a network
socket, but it should have no problem to compute the sending rate.

[Josh Grams]

Doug Hoffman wrote: <503b9703$0$292$1472...@news.sunsite.dk>

My impression of StrongForth is that it's an experimental/toy system,
not one intended for serious use. When Stephan came out with
StrongForth.f and I tried it, I quickly gave up because it choked on
several pieces of perfectly valid code which it simply didn't have the
type signatures to handle.

I had the impression that it would be relatively trivial to "finish" it
so that it was much more comfortable to use, but figured it was a really
bad sign that the author didn't care enough to do it in the first
place... And the code wasn't particularly well organized or readable to
my eye.

I still think it would be really cool to take the concept and produce a
clean, extensible static type checking library. I think you could do a
lot of neat things with it without it being too obtrusive.

--Josh

[jacko]

Everything has it's place. I think systems are built in layers.

1) Machine code.
2) Assembly.
3) C, as the insecure cast acceptable, [] memory sequential indexing, and real control over byte ordering with a malloc. I would say forth can fit here.
4) A type abstraction language, with security proofs and restrictions on what can and can not be allocated or indexed into. Java fits here, although I would by choice have null removed and require a static null item declarator. Haskill could also fit here, even with it's higher order functions.
5) A weak typed all cast auto attempt script language, with underlying hidden types to ensure continual REPL or incremental operation without restart. Maybe even a reverse switch, and an execution buffer.
6) A strong functional interjection language, where available modules (auto profile space time optimized) are suggested to replace "intent code". The logic engine could even supply useful names for the possible behaviour which are detected at various "diagnosed effect entry points".
7) The far future..... where coders are metal and bank managers have no status.

Cheers Jacko

[Doug Hoffman]

Perhaps. Every time I go back and take another look at it, as I did
just now, StrongForth seems like extra work for no benefit-of-value at
least to me. Maybe I'm just not being open-minded enough...

-Doug

[Paul Rubin]

Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>In Haskell, memoization is done with lazy evaluatio

> Well, yes, so you use STM for memoization. Where, exactly, is the
> problem? I must be missing something.

Hmm, maybe you're right; I'm not sure. There is a potentially bad
performance bottleneck with STM if there's a big memoization table that
you're updating a lot of parts of simultaneously from different threads.
GHC's approach relies on the immutability of values in Haskell, so two
threads might update the same cell with no locks, but it's with the same
value so it's ok. I guess you could also write imperative code that way
though, so I'll have to ask the #haskell folks if there's more to it
than that. I know there has to be some special hair in GHC's garbage
collector for it, but maybe it's less of a big deal than I thought.

> I wouldn't have thought so: [Cilk] fork/join is for computations that

> can be partitioned in some way. Of course, the partitioning has to be
> correct.

By comparison, Haskell's "par" annotations can be inserted anywhere in a
program with no effect on the computed result. If you choose
un-judiciously where to put them, you might get a slowdown instead of a
speedup, but you won't introduce weird bugs. There is a cool tool
"ThreadScope" that shows how much parallelism actually results, so you
can tune it. I think Cilk might have something similar, though.

> To the extent that functional-style data structures make sense, yes,
> of course. I presume "functional-style" means write-once or some kind
> of copy on write, which is well established.

Yes, a classic example is using AVL or red-black trees instead of hash
tables for associative maps. The idea is you can "copy" an AVL tree
while adding or deleting a value in O(log n) operations, with the new
tree sharing most of the old tree's structure. There's a good book
"Purely Functional Data Structures" by Chris Okasaki with more examples.

> AFAIK functional languages have no advantages over imperative
> languages in the area of concurrency except the aforementioned
> checking.

Of course functional languages are implemented with imperative machinery
under the hood, so with enough effort you can always write imperative
code that does the same stuff as functional code. FPL's just make
writing parallel code safer and more convenient, which actually does
matter quite a lot of the time.

Did you ever look at Tim Sweeney's slides about future programming
languages? I think I've posted the url before:

http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/sweeny.pdf

It was one of the things that got me interested in Haskell.

> Of course proponents of bondage and discipline languages will argue
> that everything is much easier because we're protected from ourselves.

Rather than "B&D" I prefer to think of it as "let the compiler figure
this out so I don't have to". It's just like if I have an unbalanced
parenthesis in a C program, I'm better off having it flagged at compile
time than causing a runtime crash.

> Perhaps. I've been massively impressed by the speed at which GCC is
> adopting fork/join and transactions, and I suspect that it will have
> alot more impact on real-world concurrency.

Maybe so. It takes a lot more work (or at least a lot more SLOC) to do
something in C than in Haskell, but it could be that the applications
where parallelism has the most impact (like supercomputing, or MapReduce
running across whole data centers) are also the ones that justify the
higher development budgets that it takes to use C. My hope from Haskell
(maybe not realistic) is to get programmer productivity comparable to
Python with performance comparable to Java and reliability superior to
both. Low-hassle, safe parallelism from simple constructs is a big win
in that context. In the most performance critical applications, C and
C++ will probably continue to dominate.

I do think it's awesome that Cilk is now part of GCC, which I only just
found out.

>> It looks like .( does what it's supposed to.
> Well, yes: the bug is in your program.

Yeah, I hadn't seen .( before, so I tried it and got a surprise. No big
deal.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> I don't think of types as such. A data type is a particular
> representation of your data.

The way I used the term is consistent with the academic literature on
the subject, though I can accept that academic literature isn't
necessarily the whole story.

> You can have bytes, words, floats, addresses, and combinations/tuples
> of those like strings (which starts at an address, has a length, and a
> bunch of bytes/characters froming the string).

If you add discriminated unions (sum types) and parametrized types (like
List<T> in C++), you get approximately the ML type system. Haskell adds
additional hair but is along the same lines. Coq adds types
parametrized by runtime values, so Day<month> could mean "integer in the
range 1..31" if the month is January, but "integer in the range 1..28"
for month=February. That means you have to supply static manual proofs
about what the runtime values can be, in order for Coq type-check at
compile time. It turns out that with this system, Coq types can express
basically any property that can be written down in math.

> Coq's proof system is similar to other formal proof systems (the ones
> formalized in the late 20th of the previous century).

You mean 1995-2000? Yeah I suppose so (Agda, Epigram, Cayenne, etc.)
They're different from older systems in that they are proof assistants
and programming languages at the same time.

>> But the error messages are feedback too (hey, a new motto, "GHC, the
>> compiler where fixing type errors is fun!!").

> No, an error message is a negative feedback, it tells you "you did
> something wrong".

I mean really, some people are really into it. There's a Haskell blog
whose title is "The power of types compels you":

The types. At first, they helped me to write programs, then it turned
into an obsession. Compulsive need to turn every possible programming
error into statically checked type error, consumed my soul. Soon, it
was impossible for me to code anymore - inability to express the
proper solution in types and constant strive for perfection rendered
me unable to accept inferior solutions.

Would I stop myself, three years ago, from writing the first fold? Of
course not, I choose to believe what I was programmed to believe.

OK, enough of that, it probably wasn't funny anyway.
(http://paczesiowa.blogspot.com/2010_01_01_archive.html)

I think the further levels of Haskell type hackery are like the hairy
end of C++ template metaprogramming, i.e. not really sane, but people
like to see if it can be done. It seems to make more sense to use a
fundamentally more powerful system like Coq, at the cost of having to do
more of the derivations manually. But, right now this stuff is still
beyond my depth.

> The specification of the conditions is just as bug-prone as the
> program itself (or even more), so proving equivalence does not prove
> absense of bugs.

I think that's more true in the hardware control or human interaction
world, than in the purely computational world. It's far easier to
state Fermat's Last Theorem (the specification) than it is to prove it
(the program).

>> you've got some sound but non-trivial reasoning showing that x>0

> You shouldn't have non-trivial reasonings for that. Trivial reasonings
> are ok, e.g. x is a pointer, and you don't pass null pointers around,
> only allocated objects.

Every nontrivial algorithm uses nontrivial reasoning, or else the
algorithm would itself be trivial. Do you mean we should only use
trivial algorithms?

>
> This is where I think it becomes silly. If you can write your reasoning
> down in a formalized language, you should be able to get a working
> program from that (e.g. using the methods Prolog uses).

That's a far, far harder problem, that nobody has much clue about right
now. It amounts to automated theorem proving. Prolog simply uses
exponential search with some unreliable heuristics, so on non-trivial
problems it just won't finish in a practical amount of time. By
comparison, machine-checking the correctness of a human-created proof is
much better understood by now.

> I also don't think there is a semantic gap between programmer
> knowledge and program,

If the programmer can explain or document worthwhile facts about
the program that aren't formally part of the code, then that knowledge
is part of the semantic gap.

> If you have forgotten how most of your program works, adding a new
> feature is futile.

Of course programmers are required all the time to add new features to
unfamiliar legacy code. If you wrote the code yourself and forgot
most of the details, you're still a few steps ahead of someone who has
never seen the code before.

> The key of success for this is to create components which are loosely
> coupled, and not a tightly coupled mess which you can't untangle a year
> later. I don't think it's a matter of programming language, you can
> write bad programs in every language.

Generally it takes an iterative process to write the code and
concurrently clarify one's thoughts. It's great to be able to make some
additional iterative cleanup passes after the code is working, but
schedule and budget pressure don't always permit this. One has
to be a bit tactical in deciding when and what to refactor.

> Though, some programs make it easier for bad programmers to be
> learned, and I'd say, Haskell is really driving bad programmers to
> Python and PHP.

I'm not sure what you mean by this. PHP certainly has a lot of crap
code written by low-skill programmers, while getting past Haskell's
early learning curve takes quite a lot of effort. Haskell programmers
tend to be extremely skillful, which is one of the things that attracts
me to the Haskell community. (Forth is the same way, which is part of
why I still hang around here). I don't know of anyone switching from
Haskell to Python or PHP; it's always the other direction.

>> Automatic tests help, but they aren't a silver bullet.
> But automated proofs are no silver bullet, either. Essentially, there
> is no silver bullet.

This guy claims there is something like Moore's law for programmer
productivity: http://people.cs.umass.edu/~yannis/law.html
Why would this be? Languages would seem to have something to do with
it.

Types are no silver bullet, but they're a useful tool that IME do some
of the same work that test automation does. In that situation I
described (I recently had to add some new features to an old Python
program) I was able to add the new code quickly, but made some errors
that added some debugging time. It wasn't a huge amount, but it was
enough to be a nuisance, and types would have caught the problem
instantly.

>> That's a situation one might see with beginning programmers using Java

> But then, you have a self-selected group of better programmers.

No really, I just can't imagine someone writing a nerd blog about the
Java type system like the Haskell one I gave above (and there are quite
a few more like it). Haskellers aren't just self-selected good
programmers, they're self-selected for being into types! So yes, they
enjoy fixing type errors and writing their code so that impermissible
operations will result in type errors. There's an old article on
the subject:
http://www.lucacardelli.name/Papers/TypefulProg.pdf
it includes dynamic types as being typeful, as opposed to something like
Forth which is untyped.

> [Forth is] fast enough to recompile the whole program, even if the
> program is pretty large.
Yeah, GHC isn't anywhere near that fast. Separate compilation works
well enough though.

> Haskell would probably give me some headaches with the low-level code,
> where I just need to get nanoseconds from the OS timer, and pack bytes
> together into a packet to be send at the given time through a network
> socket, but it should have no problem to compute the sending rate.

Just reading the system timer and writing bytes at a given time is no
problem. If you need consistent sub-millisecond accuracy, random GC
delays might get in the way of that, but you could queue the packets
through a separate real-time process.

[Andrew Haley]

Paul Rubin <no.e...@nospam.invalid> wrote:
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>In Haskell, memoization is done with lazy evaluatio
>> Well, yes, so you use STM for memoization. Where, exactly, is the
>> problem? I must be missing something.
>
> Hmm, maybe you're right; I'm not sure. There is a potentially bad
> performance bottleneck with STM if there's a big memoization table
> that you're updating a lot of parts of simultaneously from different
> threads.

I don't think so. STM can be as fine-grained as you like, and if it's
sufficiently fine-grained you're not going to get any peformance
bottleneck. If multiple threads are trying to update the same value,
the transaction manager will back some of them off and allow others to
proceed. It is true that STM has substantial overhead on current
computer architectures, but IMO that problem is temporary: new
hardware has the support we need.

> GHC's approach relies on the immutability of values in Haskell, so
> two threads might update the same cell with no locks, but it's with
> the same value so it's ok. I guess you could also write imperative
> code that way though, so I'll have to ask the #haskell folks if
> there's more to it than that.

If it's just a matter of updating one pointer or maybe a pair of them,
then yes you can do it. But of course everything that Haskell does is
imperative under the table, you just have to dig deep enough. :-)

>> AFAIK functional languages have no advantages over imperative
>> languages in the area of concurrency except the aforementioned
>> checking.
>
> Of course functional languages are implemented with imperative machinery
> under the hood, so with enough effort you can always write imperative
> code that does the same stuff as functional code. FPL's just make
> writing parallel code safer and more convenient, which actually does
> matter quite a lot of the time.

Well, that's the claim. AFAICS it's the same claim that the
functional people make for everything else. I guess I should learn
Haskell, but I only have one life.

> Did you ever look at Tim Sweeney's slides about future programming
> languages? I think I've posted the url before:
>
> http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/sweeny.pdf

Yes, I've seen it before, thanks. There's a lot to like about it. I
understand why referential transaparency helps, but as soon as you've
got interprocess communication referential transaparency goes out of
the window. I *am* convinced that transactions are a huge
breakthrough: that's beyond doubt IMO.

One thing we can say for certain is that a particular style is very
helpful with concurrent programming. This style involves immutable
objects and secure mechanisms such as transactions where state must be
shared.

[Aside: as far as I can tell, transactional memory solves completely
the famous "Inheritance Anomaly" whereby inheritance makes it
difficult to subclass without breaking synchronization. Despite the
fact that hundreds of papers and some theses have been written about
this problem, few people seem to have noticed. Perhaps I'm missing
something.]

Andrew.


Satoshi Matsuoka, Akinori Yonezawa: Analysis of Inheritance Anomaly in
Object-Oriented Concurrent Programming Languages,
in G. Agha, A. Yonezawa, P. Wegner, eds., Research Directions in
Concurrent Object-Oriented Programming, MIT Press, 1993.

[Paul Rubin]

Paul Rubin <no.e...@nospam.invalid> writes:
> If you add discriminated unions (sum types) and parametrized types (like
> List<T> in C++), you get approximately the ML type system.

Oops, silly me, I forgot to add function types. If X and Y are types,
then X -> Y is a type, denoting functions from X to Y. Of course C also
has types like that.

[Bernd Paysan]

Paul Rubin wrote:
>> Coq's proof system is similar to other formal proof systems (the ones
>> formalized in the late 20th of the previous century).
>
> You mean 1995-2000?

No, the systems were formalized before 1930. We got Kurt Gödel's
wonderful proof of incompleteness out of that formalization. Coq adds
enough expressive power to its "type" system that it comes under the
same sort of formalized proof systems. Ah, and the 1995-2000 frame is
indeed where enough progress was done on automated proof systems to
actually try using it in a programming language. But that's the proof
system side.

>> No, an error message is a negative feedback, it tells you "you did
>> something wrong".
>
> I mean really, some people are really into it. There's a Haskell blog
> whose title is "The power of types compels you":
>
> The types. At first, they helped me to write programs, then it
> turned into an obsession. Compulsive need to turn every possible
> programming error into statically checked type error, consumed my
> soul. Soon, it was impossible for me to code anymore - inability to
> express the proper solution in types and constant strive for
> perfection rendered me unable to accept inferior solutions.
>
> Would I stop myself, three years ago, from writing the first fold?
> Of course not, I choose to believe what I was programmed to
> believe.
>
> OK, enough of that, it probably wasn't funny anyway.
> (http://paczesiowa.blogspot.com/2010_01_01_archive.html)

This poor soul should read Gödel's proof of incompleteness, following by
Turing's proof of the unsolvable halting problem as examples that you
simply can't do that - or you are restricting yourself too much.

>> The specification of the conditions is just as bug-prone as the
>> program itself (or even more), so proving equivalence does not prove
>> absense of bugs.
>
> I think that's more true in the hardware control or human interaction
> world, than in the purely computational world. It's far easier to
> state Fermat's Last Theorem (the specification) than it is to prove it
> (the program).

That's a particular odd example, real-world examples are not that odd.
The usual problem is that you don't have much trouble writing down
necessary conditions, but they usually aren't sufficient. The same
problem as with testing.

>>> you've got some sound but non-trivial reasoning showing that x>0
>> You shouldn't have non-trivial reasonings for that. Trivial
>> reasonings are ok, e.g. x is a pointer, and you don't pass null
>> pointers around, only allocated objects.
>
> Every nontrivial algorithm uses nontrivial reasoning, or else the
> algorithm would itself be trivial. Do you mean we should only use
> trivial algorithms?

Of course. Debugging is said to be twice as hard, so you should only
write code that is so easy that you yourself can debug it. Proving your
code is correct is even worse. So try to keep your code trivial. If
your customer likes to have things done which can't be done with trivial
code, try to figure out how close you can get to your customer's wishes
with trivial code, and negotiate the rest away.

>> This is where I think it becomes silly. If you can write your
>> reasoning down in a formalized language, you should be able to get a
>> working program from that (e.g. using the methods Prolog uses).
>
> That's a far, far harder problem, that nobody has much clue about
> right
> now. It amounts to automated theorem proving. Prolog simply uses
> exponential search with some unreliable heuristics, so on non-trivial
> problems it just won't finish in a practical amount of time.

Indeed. You shouldn't do non-trivial problems, see above.

> By
> comparison, machine-checking the correctness of a human-created proof
> is much better understood by now.

Yes. The hard work is left to the human.

>> I also don't think there is a semantic gap between programmer
>> knowledge and program,
>
> If the programmer can explain or document worthwhile facts about
> the program that aren't formally part of the code, then that knowledge
> is part of the semantic gap.

The "do what I mean" programming language is yet another problem which
we don't have any idea how to implement it. We have means of adding the
typical formal knowledge a programmer has to a program, which are

a) assertions - the programmer knows which assumptions he thinks hold
true

b) examples - the programmer knows input->output relations for exemplary
data. We call this test cases.

Systems like Coq add a third layer:

c) proofs - the programmer knows proofs for correctness of his program.

>> If you have forgotten how most of your program works, adding a new
>> feature is futile.
>
> Of course programmers are required all the time to add new features to
> unfamiliar legacy code. If you wrote the code yourself and forgot
> most of the details, you're still a few steps ahead of someone who has
> never seen the code before.

And they curse about that, and the typical reaction to this request is
"the code must be rewritten from scratch, as it is an unmaintainable
mess" :-).

>> Though, some programs make it easier for bad programmers to be
>> learned, and I'd say, Haskell is really driving bad programmers to
>> Python and PHP.
>
> I'm not sure what you mean by this. PHP certainly has a lot of crap
> code written by low-skill programmers, while getting past Haskell's
> early learning curve takes quite a lot of effort.

Yes, that's what I mean.

> Haskell programmers
> tend to be extremely skillful, which is one of the things that
> attracts
> me to the Haskell community. (Forth is the same way, which is part of
> why I still hang around here). I don't know of anyone switching from
> Haskell to Python or PHP; it's always the other direction.

Hehe.

>>> Automatic tests help, but they aren't a silver bullet.
>> But automated proofs are no silver bullet, either. Essentially,
>> there is no silver bullet.
>
> This guy claims there is something like Moore's law for programmer
> productivity: http://people.cs.umass.edu/~yannis/law.html
> Why would this be? Languages would seem to have something to do with
> it.

Languages, methodologies, and response times of our machines. One thing
that is particular about Forth is that the machine responds to the
programmer in real time (i.e. fast enough that the human doesn't have to
wait for the machine). This sort of response is now available for more
programming languages than it used to be, because our machines are
faster now.

>> Haskell would probably give me some headaches with the low-level
>> code, where I just need to get nanoseconds from the OS timer, and
>> pack bytes together into a packet to be send at the given time
>> through a network socket, but it should have no problem to compute
>> the sending rate.
>
> Just reading the system timer and writing bytes at a given time is no
> problem. If you need consistent sub-millisecond accuracy, random GC
> delays might get in the way of that, but you could queue the packets
> through a separate real-time process.

No, random delays are not actually a problem, as we see random delays
like that in the rest of the network, too - and I don't use real-time
processes now, either. Any other process can interfere. This sort of
hickups are part of the problem space.

[Bernd Paysan]

Or Forth. When we say, that Forth is untyped, we mean Forth is not
typechecked. It's not actually untyped. We write the function type as
"essential" comment into the functions we write, and name it "stack
effect".

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
>>> Coq's proof system is similar to other formal proof systems

> ...the systems were formalized before 1930. Coq adds

> enough expressive power to its "type" system that it comes under the
> same sort of formalized proof systems.

Hmm, Coq is really quite a bit different than a Hilbert-style deductive
system if that's what you mean. There have been significant
mathematical advances in proof theory between the 1920's and now. After
Gödel we got Gentzen's sequent calculus (mid 1930's), then the
Curry-Howard correspondence (1950's?), then intuitionistic
(constructive) type theory (1970's), and Coq is basically an elaboration
on that. Girard's book "Proofs and types" that I linked earlier goes
into the theory of this, but as mentioned, I haven't read it and it's a
bit too technical for me at the moment.

>> Compulsive need to turn every possible programming error into
>> statically checked type error, consumed my soul

> This poor soul should read Gödel's proof of incompleteness, following by
> Turing's proof of the unsolvable halting problem as examples that you
> simply can't do that - or you are restricting yourself too much.

Well of course he was joking, but really, undecidability usually isn't
an issue for what he was talking about. Usually when we write a
program, we have some hopefully-sound reasoning (usually informal)
saying why the program should work as intended. "Proving" is simply a
matter of writing the reasoning down, sometimes formally.

>>> The specification of the conditions is just as bug-prone

> That's a particular odd example, real-world examples are not that odd.

We could start with simple conditions like "this subscript will not
overflow", "this program will not multiply two pointers together and
dereference the result", etc. The red-black tree from earlier is
another example.

> Of course. Debugging is said to be twice as hard,

You know, I think debugging is not as hard as it used to be, mostly
because of type safety (including through runtime checks rather than
static types). Java code and C++ code are fairly resemblant to each
other, and they take about equally long to write, but Java debugging
time seems to be much shorter, because when a program goes wrong there
is usually an immediate error and stack dump. There's no pointer errors
silently corrupting memory, causing difficult debugging sessions.

>> It amounts to automated theorem proving. Prolog simply uses
>> exponential search with some unreliable heuristics,

> Indeed. You shouldn't do non-trivial problems, see above.

Eh? Humans are better at reasoning than Prolog is, so it's just a
matter of choosing algorithms that you can reason about.

>> that knowledge is part of the semantic gap.
> The "do what I mean" programming language is yet another problem which
> we don't have any idea how to implement it.

We don't know how to program "do what I mean". We've always known how
to program "do what I say". We're now entering an era where we can
program "this is what I mean" in a machine-understandable way, even
though we don't expect the computer to automatically turn that meaning
into actions. This is new, and it means when we supply the instructions
along with the meaning, the computer can now check that carrying out the
instructions will lead to the desired end result.

It's still highly tedious, but it's one of those things like speech
recognition, that was useless a decade or two ago but has been improving
steadily since then.

> And they curse about that, and the typical reaction to this request is
> "the code must be rewritten from scratch, as it is an unmaintainable
> mess" :-).

Nah, programs have varying amount of cruft in them and sometimes benefit
from incremental refactoring, but it's usually possible to make a patch.
5+ years ago someone told me Google's main search application was around
100 MLOC of C++. That's not a candidate for rewriting all at once.
People they hire are expected to sit down and deal with the existing
code.

> about Forth is that the machine responds to the programmer in real
> time (i.e. fast enough that the human doesn't have to wait for the
> machine).

Yeah, that's most helpful in situations where you want to poke at an
unfamiliar interface and see how it works. Other situations, it's ok to
think for a while, then write code in a text editor, then use a batch
compiler. Of course having to wait long periods for results is bad.
Compiling speed doesn't always help, if (e.g.) the program takes 2
seconds to compile and overnight to run. Big compute clusters help ;-).

> No, random delays are not actually a problem,

Haskell is probably workable then. You might also like Erlang, which
has Lisp-style runtime typing, and built-in distribution and fault
recovery methods.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
>>If X and Y are types, then X -> Y is a type, denoting functions from X
>>to Y. Of course C also has types like that.
>
> Or Forth. When we say, that Forth is untyped, we mean Forth is not
> typechecked. It's not actually untyped. We write the function type as
> "essential" comment into the functions we write, and name it "stack
> effect".

It's untyped in the sense that the compiler doesn't know about the
types: they are solely in the mind of the programmer and in the comment,
i.e. part of the "semantic gap" mentioned earlier.

FWIW, Forth's "types" aren't that precise about functions, e.g.:

: triple ( n -- n ) 3 * ;
: do-twice ( n xt -- n ) swap over execute swap execute ;
: times-9 ( n -- n ) ['] triple do-twice ;

In Haskell, we'd give do-twice a type like

Integer -> (Integer -> Integer) -> Integer

i.e. something like ( n ( n -- n ) -- n ) in pseudo-Forth notation.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:

>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Why would I stop after every line?
>
>Other people on this newsgroup have been advising me to test each word
>before writing the next one. Most of my words are 1 line.

And what benefit would a stepping debugger have in that scenario?

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2012: http://www.euroforth.org/ef12/

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:

>Bernd Paysan <bernd....@gmx.de> writes:
>> Yes, but that's not "right first time". A program is "right first time"
>> if - after internal debugging - it gets out error-free to the customer.
>
>There's another aspect: how do you convince the customer (or anyone
>else) of the absence of errors?

Why should I? Do customers care? They prefer to use (and buy) the
good-enough software that's available now and has some other benefits
(e.g., compatibility, glitz) over supposedly-perfect software that's
available next year and costs a fortune.

Moreover, even with formal methods and whatnot there is no guaranteed
error-free program as far as the custormer is concerned because formal
methods only can show that the code implements the specification, but
not that the specification is correct or that the requirements are
correct.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>2) Also meant to add: one of the arguments for fancy static type systems
>(stated explicitly in Pierce's book "Types and programming languages")
>is that the types amount to lightweight formal methods, that can be used
>without much fuss in everyday programming. They are no longer huge,
>tedious, special purpose machinery used only for ultra-critical
>high-budget applications like spacecraft. The red-black tree example I
>gave earlier (GADT's verify the red-black tree invariants) is
>illustrative of this.

Not at all. I have never implemented a balanced tree, and I guess
most other programmers have not, either, or only as an exercise. For
every potential use I have encountered there has been a less complex
and usually more efficient data structure (usually a hash table).

So, the example illustrates that Haskell's type system may help me
with a problem that I have never encountered. Not very convincing as
far as real-world usage is concerned. The example gets categorized as
"cool, but useless".

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Most of my words are 1 line.
> And what benefit would a stepping debugger have in that scenario?

Eh? It's very helpful to execute one step at a time to see where the
word is going wrong, e.g. with a conditional breakpoint in a loop (~~
can spew too much output), examining variables (not just the stack)
during execution, etc.

>>There's another aspect: how do you convince the customer (or anyone
>>else) of the absence of errors?
>Why should I? Do customers care?

1) Besides customers you may also have to convince your co-workers (code
review) and yourself. It's certainly common enough (at least for me) to
write some code, test it and see that it seems to work, but be left with
doubts that my testing may have missed an obscure case.

2) Yes customers do care. I worked on a financial product and customers
(banks) did technical audits on us several times, particularly on our
security stuff. They asked what we did to prevent various specific
failures and we had to answer convincingly.

I'm not saying static types would have helped the above cases all that
much, but it tells me that incorporating reasoning about correctness
into programs is a sensible aspirational goal.

> Moreover, even with formal methods and whatnot there is no guaranteed

> error-free program ... because formal methods only can show that the

> code implements the specification, but not that the specification is
> correct or that the requirements are correct.

Sure, but that's mostly a red herring. Of course it's near-impossible
to write a spec that captures ALL the desired behavior of a program.
Type systems instead let you assert the absence of specific incorrect
behaviors, which still helps a lot. "This program must never
dereference a null pointer for any input" is simple enough to specify
and easy for a reasonable type system to ensure, but decades of C
program failures show it's very hard to supply by pure design and
testing. Thus the saying "the last good thing written in C was
Schubert's Ninth Symphony". ;-).

> I have never implemented a balanced tree... For every potential use I

> have encountered there has been a less complex and usually more
> efficient data structure (usually a hash table).

They're useful and I keep wanting them in Python. They let you access
(i.e. add, delete, lookup) arbitrary keys, and also traverse the keys in
order. A real-world example where I wanted this is a priority queue
where you can update elements (think of an alarm clock with N updateable
alarms). Databases are another frequent application (B-trees).
Balanced trees also guarantee O(log n) access and update, which stops
some real-world denial of service attacks that have happened in internet
programs, based on triggering hash collisions on purpose. And,
persistent versions make it easy to take snapshots as updates happen,
which is handy in concurrent programs among other places.

> So, the example illustrates that Haskell's type system may help me
> with a problem that I have never encountered. Not very convincing as
> far as real-world usage is concerned. The example gets categorized as
> "cool, but useless".

I thought it was amazing how easy it was to write a type signature that
captured the red-black tree invariants. I don't have a sense of how
hard it was for that guy to write the code that went with the signature.
It might have actually been too difficult for everyday programming. It
still seems significant as an example of emerging technology not quite
ready for prime time, in addition to being cool.

[Elizabeth D. Rather]

On 8/30/12 7:43 AM, Paul Rubin wrote:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> Most of my words are 1 line.
>> And what benefit would a stepping debugger have in that scenario?
>
> Eh? It's very helpful to execute one step at a time to see where the
> word is going wrong, e.g. with a conditional breakpoint in a loop (~~
> can spew too much output), examining variables (not just the stack)
> during execution, etc.

Ok, we're talking about debugging a 1-line (or very short) definition.
Here's how I do it:

1. Test it by giving it reasonable inputs and examining the outputs.
2. If it gives a wrong answer, error message, or other indication of
trouble, I look at it. Since it is very small, usually the error becomes
apparent, so I fix it and repeat #1.
3. In the rare case when the error is still elusive, I type through the
definition, looking at the stack. If there's a loop, I type through the
body of the loop (remember, this is a 1-line definition!). A very common
source of trouble is stack overflow or underflow in a loop; this will
reveal what's happening.
4. When the definition appears to work, I write a test word that takes
it through a reasonable range of input values and run that.

Now, obviously when there is hardware involved the method differs. I
always test the hardware first, which in Forth you can do interactively
with little or no actual code. Examine ports using C@ (or a custom P@ if
code is required to read a port), write to control or data registers
using C! or P!, to prove that the device responds appropriately.

Then I test the code using the 4 steps above, supplying reasonably dummy
data. Then I put it all together.

This is all preliminary testing at low levels of an application, of
course. As the application develops, similar procedures apply to higher
level processes.

>>> There's another aspect: how do you convince the customer (or anyone
>>> else) of the absence of errors?
>> Why should I? Do customers care?
>
> 1) Besides customers you may also have to convince your co-workers (code
> review) and yourself. It's certainly common enough (at least for me) to
> write some code, test it and see that it seems to work, but be left with
> doubts that my testing may have missed an obscure case.
>
> 2) Yes customers do care. I worked on a financial product and customers
> (banks) did technical audits on us several times, particularly on our
> security stuff. They asked what we did to prevent various specific
> failures and we had to answer convincingly.

I'm thinking of all the tales we hear about versions of Windows and
other big programs released with upwards of 100,000 known bugs!

But, for sure there are applications where you really do need a high
degree of confidence in the correctness of the code. Paul Bennett (a clf
regular) has written some papers on certifying Forth programs. What you
need in these cases are well-designed, thorough test suites to apply to
major sections of the program, and the program overall.

> I'm not saying static types would have helped the above cases all that
> much, but it tells me that incorporating reasoning about correctness
> into programs is a sensible aspirational goal.

Absolutely, "incorporating reasoning about correctness into programs is
a sensible aspirational goal." But type checking has little to do with
this. Of all the major programs I've been involved in developing and
testing, errors of type have simply not been issues for which elaborate
type checking compilers would be any help. That kind of check may be
appropriate in a programming style that involves pages of code, but not
short Forth definitions.

...

>> I have never implemented a balanced tree... For every potential use I
>> have encountered there has been a less complex and usually more
>> efficient data structure (usually a hash table).
>
> They're useful and I keep wanting them in Python. They let you access
> (i.e. add, delete, lookup) arbitrary keys, and also traverse the keys in
> order. A real-world example where I wanted this is a priority queue
> where you can update elements (think of an alarm clock with N updateable
> alarms). Databases are another frequent application (B-trees).
> Balanced trees also guarantee O(log n) access and update, which stops
> some real-world denial of service attacks that have happened in internet
> programs, based on triggering hash collisions on purpose. And,
> persistent versions make it easy to take snapshots as updates happen,
> which is handy in concurrent programs among other places.

The database system in polyFORTH had a B-tree option for a while. I can
remember one application in which it was useful. But I think of things
like that as library functions that may be appropriate in certain
applications, not language features.

[Bernd Paysan]

Paul Rubin wrote:
> It's untyped in the sense that the compiler doesn't know about the
> types: they are solely in the mind of the programmer and in the
> comment, i.e. part of the "semantic gap" mentioned earlier.

With our "do what I say" philosophy, there is indeed a semantic gap,
between "what I mean" and "what I say". The semantics of the Forth
compiler is close to that of the hardware, i.e. the thing is an
imperative state machine with an array of bytes called "memory", and a
few registers like sp/rp/ip.

The complaint by the semantic gap idea is that people don't express
their toughts in terms of such a state machine, and higher level
languages allow them to express their thought in a different way, which
then is compiled to state machine code.

However, the world of mathematical functions is no less alien to us
humans than the world of state machines. IMHO, the mathematical
background of Computer Science is what is driving functional programming
languages and proof systems: That's their "home turf".

For us Forthers, with our mantra "avoid unnecessary abstractions", it is
an abstraction with dubious value. It takes you away from the machine,
and when you write code for the machine, it may be just in the way.

> FWIW, Forth's "types" aren't that precise about functions, e.g.:
>
> : triple ( n -- n ) 3 * ;
> : do-twice ( n xt -- n ) swap over execute swap execute ;
> : times-9 ( n -- n ) ['] triple do-twice ;
>
> In Haskell, we'd give do-twice a type like
>
> Integer -> (Integer -> Integer) -> Integer
>
> i.e. something like ( n ( n -- n ) -- n ) in pseudo-Forth notation.

Well, xt is a placeholder type, if you document carefully, you would
document what xt does. However, "do-twice" should be written

: do-twice ( i*x xt -- k*x ) >r r@ execute r> execute ;
\ xt's stack effect is ( i*x -- j*x ) so that
\ when applied to j*x it gives k*x

for good reasons. That way, you can define

: f4* ( r -- r ) ['] f2* do-twice ;

and the documented rule of the stack effect of xt for do-twice is that
it is transitive (i.e. you can apply it to its own output). This is
even allowed when the function reduces something:

: +3 ( n1 n2 n3 -- nsum ) ['] + do-twice ;

: !+ ( x addr -- addr' ) dup cell+ >r ! r> ;
: 2! ( d addr -- ) ['] !+ do-twice drop ;

The rule of thumb for higher-order Forth words (i.e. words that take an
xt) is that you

a) specify the stack effect of that xt and
b) you allow the word to access the stack beneath.

I.e. the higher order function is not allowed to keep things on the
stack below the parameters for which it calls xt.

Static typing languages like C++ use templates for that, but the result
is code explosion, because the compiler recompiles that whenever you use
a new type.

[Bernd Paysan]

Paul Rubin wrote:
>> Moreover, even with formal methods and whatnot there is no guaranteed
>> error-free program ... because formal methods only can show that the
>> code implements the specification, but not that the specification is
>> correct or that the requirements are correct.
>
> Sure, but that's mostly a red herring. Of course it's near-impossible
> to write a spec that captures ALL the desired behavior of a program.

No, the real world fact is that it is near-impossible to write a spec
that is even close to what the customer really wants - other than in "do
what I mean" notation. E.g. the project I worked on two years ago was a
battery monitor, and the customer wanted things like "accurate to about
1%" and "below 10µA current budget", "smaller number is better". Yes,
the latter is partly a software requirement, as this thing was running
on a b16 processor, and the current consumption can go up to milliamps
if the CPU runs all the time at high clock speed.

> Type systems instead let you assert the absence of specific incorrect
> behaviors, which still helps a lot. "This program must never
> dereference a null pointer for any input" is simple enough to specify
> and easy for a reasonable type system to ensure, but decades of C
> program failures show it's very hard to supply by pure design and
> testing. Thus the saying "the last good thing written in C was
> Schubert's Ninth Symphony". ;-).

But C's main problem is one fundamental mistake: buffers are passed
around as pointers, without length. This is a direct invitation to
buffer overflows. The problem of C is not just a lack of type
information, it is the lack of a very vital information: the lack of
knowing how big a buffer actually is.

Forth doesn't know about types, but its buffer operations all know about
the size of the buffer.

>> I have never implemented a balanced tree... For every potential use I
>> have encountered there has been a less complex and usually more
>> efficient data structure (usually a hash table).
>
> They're useful and I keep wanting them in Python. They let you access
> (i.e. add, delete, lookup) arbitrary keys, and also traverse the keys
> in order.

In what order? Alphabetical order? Does that matter? Do you really
want all fruits from apples to bananas listed? We use alphabetical
orders to quickly index things, like a dictionary or an address book.

> A real-world example where I wanted this is a priority queue
> where you can update elements (think of an alarm clock with N
> updateable alarms).

Yes, that is an example where you have an order over the entries which
actually matters.

> Databases are another frequent application (B-trees).

Database implementers like B-trees particularly, because they can easily
be made transaction-safe. I.e. when you do a transaction, you copy the
parts of the tree which contain the new state, and then you only update
the root pointer - or, when you have to unroll your transaction, you
just throw away these copies. As databases often have several indices
per table, transactions have to update all of them, and this should not
be costly.

> Balanced trees also guarantee O(log n) access and update, which stops
> some real-world denial of service attacks that have happened in
> internet programs, based on triggering hash collisions on purpose.

The other way to deal with that problem is to have a unique hash
function, which the attacker can't create hash collisions for (for being
"unique", something quite simple is completely sufficient: xor all
strings with the same secret).

For me, this sort of B-trees or priority queues are problems which you
face during university, because they are popular data structures. In
"real life", they don't happen that often. If you really need them, you
write them once, and then they are part of your toolbox. The priority
queue I wrote (for MINOS) didn't get a complicated data structure,
because the usual case is that there aren't many events waiting.
Therefore, just having an array and direct insert was both the quickest
to write *and* the most performant. It is O(n), but the constant
overhead is very low.

I've made some thought about how I would implement the priority queue of
a gate-level simulator, and my preferred data structure would be an
array with a fixed time scale, because each element has a delay (e.g. at
least an inverter delay), so if your fixed time scale is less than the
minimum delay, you can perform the operations in arbitrary order (no
finer grain for sorting needed).

So in reality, you quite often have opportunities to slightly change the
requirements so that you can use a much easier solution.

With the "constant time scale per schedule bucket = minimum delay"
equation mentioned above, I'd be curious how that would look in Coq.
It's provable, the proof is that whatever data you update, the next
update it triggers must not go to the same bucket, because execution
inside the same bucket is not ordered. That's stuff I think you can
reason about without writing down much stuff, but making it formal so
that an assisted proof system like Coq can proof you do meet the
requirements of a full-blown priority queue under these constraints: I
think that's pretty hard. After all, the delay data is not part of the
program, you read in the delay annotations, extract the minimum delay,
and use that value as scheduler bucket delta-t.

[gavino_himself]

On Sunday, August 26, 2012 2:20:15 PM UTC-7, Bernd Paysan wrote:
> Paul Rubin wrote:
>
> > Are you talking about compiling programs of similar size, on similar
>
> > hardware, with compilers that do similar levels of optimization? It's
>
> > certainly plausible that given more CPU power, fancy compilers will
>
> > use it to do more optimization and automation, rather than just doing
>
> > the same stuff as before and finishing sooner.
>
>
>
> No, I'm comparing a bloated Java+C++ project to a non-bloated Forth
>
> project. But even when I compare two non-bloated projects, GCC is
>
> hellish slow.
>
>
>
> > Maybe you should try TCC (tinycc.org) for development builds.
>
> > It's around 10x faster than GCC, though the output code is nowhere
>
> > near as optimized.
>
>
>
> Unfortunately, TCC is also lacking features. And using a different
>
> compiler for debug builds than for production builds is a bad idea - if
>
> you run into bugs of the production build compiler, what do you do then?
>
> The usual Forth approach to coding is making small incremental changes,
>
> because then you don't have to search long for the reasons why it
>
> doesn't work - it's very likely the small change you just did now.
>
>
>
> >> That also guides to my most-used debugging method: Inserting ~~ in
>
> >> suspicious places.
>
> >
>
> > This still takes a lot of runs of the program and possible creation of
>
> > new test cases, which can be pretty tedious.
>
>
>
> Well, it does not feel "a lot" if you can do these runs pretty quickly.
>
>
>
> >>> IMHO Haskell's type system makes it practical to program in a style
>
> >>> that while not impossible, would be much harder to manage in
>
> >>> Forth....
>
> >> I'm not sure why you claim it is error-prone and to be avoided....
>
> >> Forth is a programming language which tells you to avoid unnecessary
>
> >> abstractions.
>
> >
>
> > Right, the reason it tells you to avoid unnecessary abstractions is
>
> > that using abstraction in Forth is error-prone.
>
>
>
> No, that's not the case. You should avoid unnecessary abstractions
>
> since they don't pay off. You can use necessary abstractions, and are
>
> encouraged to do so.
>
>
>
> > I wasn't thinking really
>
> > of postpone and create/does, but more of a style where you pass around
>
> > execution tokens a lot, and those xt's may take other xt's as
>
> > arguments
>
> > to invoke over generic data structures, and so on.
>
>
>
> After I added quotations to my system, I started doing that regularly.
>
> Not exactly as in Haskell, but MINOS, using an OOP system, does that
>
> sort of stuff. Juggling around many things on the stack is bad Forth
>
> code, so pass xts around that take another xts quite likely will result
>
> in many parameters on the stack. Don't do that.
>
>
>
> The OOP system I use in MINOS handles that: You pack the several xts
>
> into one class, and use that. No need for several xts flying around,
>
> the class framework wrap them up into one entity, which is much easier
>
> to pass around.
>
>
>
> > In Haskell, it's
>
> > natural to program that way, and the code still feels solid. In
>
> > Scheme or Python you can write basically the same code, but with no
>
> > type system watching over you, it feels like walking on a tightrope
>
> > without a safety net.
>
>
>
> Don't fear the program crash! As I said, in a strong typed language, I
>
> feel like in a straightjacket. I wouldn't walk a tightrope in such a
>
> language, regardless of safety net or not.
>
>
>
> > I've programmed that way in Forth a little bit, but have been
>
> > advised against it.
>
> >
>
> >> No type system prevents programs from going wrong.
>
> >
>
> > Well, I'd say a well-typed program, including something like Lisp with
>
> > runtime type-checking, can at least have well-defined semantics, while
>
> > an untyped (e.g. Forth or C) program can go completely into the weeds
>
> > if there is a type error (such as a subscript overflow).
>
>
>
> A subscript overflow is not exactly a type error.
>
>
>
> >> It applies a number of low-hanging fruit checks,
>
> >
>
> > Haskell typechecking can be quite powerful. I like this example:
>
> > https://gist.github.com/2659812
>
> >
>
> > Explanation: Red-black trees are binary trees with the following
>
> > invariants:
>
> > 1. Each internal node is colored either red or black.
>
> > All leaves are black and the root is black.
>
> > 2. All children of red nodes must be black. Black nodes can
>
> > have children of either or both colors.
>
> > 3. All paths from the root to the leaf contain the
>
> > same number of black nodes.
>
> >
>
> > This means the tree is approximately balanced: any path from the root
>
> > to a leaf contains n black nodes, and between 0 and n red nodes, so
>
> > the
>
> > worst case search depth is no more than 2x the best case. You can't
>
> > get
>
> > a completely lopsided tree. To insert or delete a node, you have to
>
> > do somewhat complicated juggling operations ("tree rotations") to
>
> > preserve the invariants, and it's easy to make mistakes coding these
>
> > operations. The C++ implementation that I looked at has assert
>
> > statements that check at runtime that the code didn't hit some weird
>
> > edge case that messed the
>
> > invariants up. Even after extensive testing, the assert statements
>
> > are still there in the program.
>
> >
>
> > It turns out to be pretty straightforward to express those invariants
>
> > as
>
> > a Haskell datatype (seen in the url above). Any value belonging to
>
> > the
>
> > type must be a properly balanced tree. That means that the juggling
>
> > code cannot possibly mess up the invariants. Any attempt to make an
>
> > unbalanced tree will cause a type-checking error, and the program
>
> > won't
>
> > compile.
>
>
>
> That's exactly what I don't like. This is a rather complicated thing,
>
> and I'm sure neither of us will write a perfect program first time. As
>
> I try to write incremental programs, my first approach to a r/b tree
>
> would be a general tree program, and let the tree be as unbalanced as I
>
> like. If this works, I would start adding balancing rotation
>
> operations, one after the other (you know, there are several cases you
>
> have to think about). Each of them is tested, but of course, the tree
>
> will still be lopsided.
>
>
>
> Maybe you can do that in Haskell, too, by just trying with the full
>
> blown type, and doing the test runs with a reduced type information,
>
> which doesn't care about balancing.
>
>
>
> > It would be pointless to have assert statements in the
>
> > executable since the compiler has statically verified that the
>
> > asserted
>
> > conditions hold. I would not call this low-hanging fruit. It's a
>
> > sophisticated condition being checked, that's a source of bugs in
>
> > other real-world implementations, and the compiler verifies it to
>
> > higher confidence than even quite a lot of unit tests could give.
>
> >
>
> > As an even more extreme example, Coq's type system is even stronger
>
> > than Haskell's: it can express any mathematical proposition, so it has
>
> > to be Turing complete, meaning it can't do inference and you have to
>
> > manually
>
> > supply type derivations (which is tedious). But it can encode (for
>
> > example) the semantics of assembly code fragments (Hoare triples) as
>
> > types. So if you have a compiler optimization pass that is annotated
>
> > to take one fragment and returns another fragment of the same type,
>
> > the Coq typechecker is able to verify that the input and output have
>
> > the same semantics and the optimization pass has not introduced any
>
> > semantic
>
> > bugs. I think I mentioned before, a sizable part of a C compiler has
>
> > been written that way (CompCert). This is not low hanging fruit at
>
> > all. It is probably the future, especially as better automation
>
> > becomes available for developing this sort of code.
>
>
>
> Calling this still a "type system" is a misnomer. Yes, this is no low-
>
> hanging fruit, but as you said, it is also tedious to use. And if
>
> that's useful during development depends on the error message. Let's
>
> say I have a code transformation pattern
>
>
>
> BEGIN code WHILE REPEAT -> BEGIN code UNTIL
>
>
>
> to skip the empty part between WHILE and REPEAT, the transformation is
>
> wrong, because the flag for WHILE means the opposit as for UNTIL. If
>
> the code system tells me just "your transformation is wrong", then I
>
> have no clue why, and can only guess. If I unit-test this thing, I'd
>
> give it a simple task and look at the results, and since the results are
>
> runable programs, I'll see why the two are different.
>
>
>
> >> while at the same time putting a straitjacket onto the programmer.
>
> >> At least that's how I feel when I program in a language with a strong
>
> >> type system. The compiler tells me "no, you can't do this", and "no,
>
> >> you can't do that".
>
> >
>
> > I never felt terribly straitjacketed programming in C, but I also felt
>
> > that the type system wasn't helping me that much.
>
>
>
> C has no really strong type system. A type mismatch usually results in
>
> a warning, it doesn't even fail to compile. I'm not that much
>
> complaining about C, C's type system is more a simple operator
>
> overloading system than anything else.
>
>
>
> > I was comfortable
>
> > programming with lots of void*'s, and programming in Lisp with runtime
>
> > types. Trying Haskell was really eye-opening for me. I'm a long way
>
> > from being a Haskell expert but I find it tremendously interesting and
>
> > different (whether that means "better" is of course a separate
>
> > matter).
>
>
>
> Yes, of course. It is quit different.
>
>
>
> >>> http://cdsmith.wordpress.com/2011/01/09/an-old-article-i-wrote/
>
> >> Performance is not a problem? Come on. I'm constantly seeing
>
> >> software which is slow as molasses,
>
> >
>
> > He's talking about compiled code with runtime type checks, vs.
>
> > compiled code that has been statically checked but otherwise does the
>
> > same stuff,
>
> > e.g. Lisp vs ML. If the compiler is any good, the performance
>
> > difference is usually a small constant factor, maybe just a few
>
> > percent. The large, order-of-magnitude slowdowns you're seeing in the
>
> > examples you mention are due to architectural issues in the slow
>
> > programs.
>
>
>
> Yes. Usually several architectural issues stacked on each others, like
>
> using a complicated delegate-style OOP program (nobody really wants to
>
> solve the problem, so it gets delegated over and over again) on top of a
>
> slow Java VM with a bad JIT - if there is a JIT at all.
>
>
>
> >> What I think would be worth to do for analytic compilers which track
>
> >> that information anyways: Have a stack effect checker.
>
> >
>
> > Yes, that would have caught my + vs. F+ bugs. StrongForth does
>
> > that sort of checking as you're probably aware.
>
>
>
> It does a bit more, and there's even a version which runs on top of
>
> Gforth.
>
>
>
> >> Warnings when it doesn't match, please, it should compile, because
>
> >> running it (with inserted ~~) will identify the problem quickly.
>
> >
>
> > GHC now has a command-line option that lets it produce executable code
>
> > even if the program has type errors. You then get a runtime error
>
> > only
>
> > if the program tries to actually evaluate an ill-typed expression.
>
>
>
> Nice. This allows you to check what actually happens.
>
>
>
> > This turns out to be handy during development even though the compiler
>
> > has
>
> > already told you where the errors are. It's sometimes useful to be
>
> > able test the successfully compiling parts of your program right away,
>
> > postponing dealing with the unsuccessful parts til later.
>
>
>
> Given that fact, I'm less opposed than before. How useful is GHCi (the
>
> interactive command line)?
>
>
>
> >> Forth's interactivity and abstraction avoidance is what makes it
>
> >> strong. Interactivity is more than just a command line promt, it
>
> >> also
>
> >> means that you can recompile quickly. "Blink", not "lunch".
>
> >
>
> > I sometimes like to imagine what it must have been like to program in
>
> > Forth or Lisp in the glory days of those languages. I'd be interested
>
> > in seeing a demo sometime (maybe on video) of someone hacking on Forth
>
> > code that does something complicated, using good interactive Forth
>
> > tools.
>
>
>
> We Forthers really try hard to not do something complicated ;-). When I
>
> implemented bigForth' fast dictionary search, I explored several
>
> options, hashing and AVL trees. AVL trees were more complicated, and
>
> they lost to hashing in every metric: Time to write, execution
>
> performance, memory usage, and bugs to fix during development.
>
>
>
> In many cases you have an option which is simple, fast, and correct.
>
> Don't try to use the other option.
>
>
>
> > When I started using Python, I found myself thinking "this is
>
> > what the old-time Maclisp hackers must have felt like". Haskell is
>
> > different, completely different, a vision as powerful as Lisp but
>
> > unlike
>
> > anything that had been used for programming before. That in some
>
> > sense outweighs any difficulties involved in trying to actually use
>
> > it. ;-)
>
>
>
> I'm still wondering how useful that would be for me. The main
>
> challanges in the programs I write are the outside world, not the inner
>
> logic of the program. E.g. take my net2o flow control, which took me
>
> quite some time to develop. The code for it is rather simple, and it
>
> always was rather simple, didn't crash or anything. That's not the
>
> challange. The challange is to fill a network with packets just fast
>
> enough, so they don't pile up in buffers, but yet leave no unused
>
> bandwidth under real world conditions, which means things like Wifi with
>
> rapidly changing quality, competing with multiple TCP/IP, BitTorrent or
>
> net2o itself. This was a serious issue which I underestimated, given
>
> how bold other people were about their results (like LEDBAT). I thought
>
> I could just copy that, but it turned out to be not good enough.
>
>
>
> A type system won't help at all here. The type system will catch the
>
> low hanging fruits like f+ vs. + or similar. I don't have problems with
>
> those, these are "declinations", and something the human brain can
>
> handle quite well (the grammar engine).

>
>
>
> --
>
> Bernd Paysan
>
> "If you want it done right, you have to do it yourself"
>
> http://bernd-paysan.de/

How do you know which abstractions are needed and which are not?
Is the lisp and haskell claim that abstraction is most important hollow?
Are abstractions not needed many times?

[Elizabeth D. Rather]

On 8/30/12 5:08 PM, gavino_himself wrote:
...

> How do you know which abstractions are needed and which are not?
> Is the lisp and haskell claim that abstraction is most important hollow?
> Are abstractions not needed many times?
>

It all depends on the needs of the application. Some applications
benefit more from abstractions than others.

[Rod Pemberton]

"Bernd Paysan" <bernd....@gmx.de> wrote in message
news:2250796.Q...@sunwukong.fritz.box...

[...]

> But C's main problem is one fundamental mistake: buffers are passed
> around as pointers, without length.

If you knew anything about C, you'd know that the length of a buffer is
always known. It's either in the declaration of the buffer, or was needed
to allocate the buffer dynamicly, or is available with sizeof() or strlen()
etc. Whether or not the length is available when needed is a programmer
implementation issue.

> This is a direct invitation to buffer overflows.

That doesn't follow.

C's buffer overflows are the result of:

1) unlimited keyboard input functions
2) delimited buffers without the required delimiter
3) abuse of the single stack (common, not required) used for
control-flow, parameters, and data

How is Forth any different?

C doesn't require a stack, but most use one in order to:
a) implement recursion of procedures
b) reduce memory allocation requirements

> The problem of C is not just a lack of type information, it is
> the lack of a very vital information: the lack of knowing how
> big a buffer actually is.
>

Example 1) - static allocation

#define BSIZ 32
char buf[BSIZ];

len0=BSIZ;
len1=sizeof(buf);


Example 2) - dynamic allocation

#define BSIZ 32
char str[]="ABCDEF";

len0=BSIZ;
malloc(len0);

len1=80*sizeof(char);
malloc(len1);

len2=10*strlen(str);
malloc(len2);


The length is needed to allocate a buffer, staticly or dynamicly. The
length is known from then on, or can be determined by using the
appropriate function or size operator.

> Forth doesn't know about types, but its buffer operations
> all know about the size of the buffer.

Which "buffer operations" in C don't?


The few memory functions in C operate on any data and are passed a length.
Their data is not delimited. So, they require a length.

The many string functions in C operate on strings, which in C is an array of
characters delimited by C's definition of a byte, set to all bits cleared
(zero). Other C string functions operate on strings delimited by other
characters.

> The other way to deal with that problem is to have a unique hash
> function, which the attacker can't create hash collisions for (for being
> "unique", something quite simple is completely sufficient: xor all
> strings with the same secret).

There is no guarantee that for two non-XOR'd strings which are hash
collisions that their two XOR'd strings won't be hash collisions also. If
the hash function has low collisions, then it's unlikely the XOR'd strings
will collide, but that's also true for the non-XOR'd strings. If the hash
function has high collisions (for simplicity, or speed etc.), then it's
likely the XOR'd strings will collide too, but that's also true for the
non-XOR'd strings. Even with a low collision hash function, I think the
idea of XOR-ing is a bad idea. For a set of non-XOR'd strings, collisions
will occur for certain strings. With a set of XOR'd strings, collisions
will occur for certain strings too. I.e., the probability or frequency of
collisions is the same. The XOR has no effect on that probability. The
hash function hasn't changed. A certain percentage will collide. So, all I
believe XOR-ing will do is change which inputs collide, but it won't reduce
the frequency of the collisions. If this works for you, it's because the
strings are limited in the numeric range of their characters, and you've
shifted which hash collisions occur via the use of XOR-ing "secret" string.
The reason why I think this is a bad idea is because you've effectively
tuned the hash to produce low collisions for a _specific_ set of input
strings and a _specific_ "secret" string. However, both that input set of
strings and "secret" string can be changed. If they are changed, the hash
needs to be retuned. What needs to be done instead of XOR-ing is to
increase the randomness of the string data. String data has a narrow
numeric range of values. An array of randomized data with a larger range
than the character range can be used to translate the the strings'
characters to the random data prior to the hash.


Rod Pemberton

[Andrew Haley]

Rod Pemberton <do_no...@notemailnot.cmm> wrote:
> "Bernd Paysan" <bernd....@gmx.de> wrote in message
> news:2250796.Q...@sunwukong.fritz.box...
>
> [...]
>
>> But C's main problem is one fundamental mistake: buffers are passed
>> around as pointers, without length.
>
> If you knew anything about C, you'd know that the length of a buffer
> is always known. It's either in the declaration of the buffer, or
> was needed to allocate the buffer dynamicly, or is available with
> sizeof() or strlen() etc. Whether or not the length is available
> when needed is a programmer implementation issue.

Well, yes. It's the "programmer implementation issue" that Bernd is
talking about. It's the fact that if someone passes you an int[] you
can't say "How big is this?" Yes, you can insist that they also pass
you the size, but that doesn't change the fact that the language
doesn't.

>> The other way to deal with that problem is to have a unique hash
>> function, which the attacker can't create hash collisions for (for being
>> "unique", something quite simple is completely sufficient: xor all
>> strings with the same secret).
>
> There is no guarantee that for two non-XOR'd strings which are hash
> collisions that their two XOR'd strings won't be hash collisions
> also. If the hash function has low collisions, then it's unlikely
> the XOR'd strings will collide, but that's also true for the
> non-XOR'd strings.

You're missing the point. The idea of the unique hash function is not
to make collisions impossible but to make them unpredictable: the
scenario is one where the attacker knows the hash function and
deliberately creates collisions.

Andrew.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> : do-twice ( i*x xt -- k*x ) >r r@ execute r> execute ;
> \ xt's stack effect is ( i*x -- j*x ) so that
> \ when applied to j*x it gives k*x
>
> for good reasons. That way, you can define
>
> : f4* ( r -- r ) ['] f2* do-twice ;

Oh thanks, I like this, writing do-twice that way means it's independent
of the xt's stack effect.

> I.e. the higher order function is not allowed to keep things on the
> stack below the parameters for which it calls xt.

So my version temporarily had the stack in the state ( xt n xt ) which
wasn't so good because of the xt behind the n. I guess avoiding that is
a good general guideline. Of course there will still be stuff on the
stack from do-twice's caller.

> Static typing languages like C++ use templates for that, but the result
> is code explosion, because the compiler recompiles that whenever you use
> a new type.

I think it does that either for C compatibility, or to generate the
fastest possible code. It could in principle (unless there's some
C++-specific issue preventing it) use an OO-like dispatch based on the
argument type instead. GHC does something like that, taking a
minor speed hit to avoid duplicating so much code.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>Bernd Paysan <bernd....@gmx.de> writes:

>> I.e. the higher order function is not allowed to keep things on the
>> stack below the parameters for which it calls xt.
>
>So my version temporarily had the stack in the state ( xt n xt ) which
>wasn't so good because of the xt behind the n. I guess avoiding that is
>a good general guideline. Of course there will still be stuff on the
>stack from do-twice's caller.

Yes, the idea of that principle is to allow to pass data from the
caller to the xt (and back) through the data stack. Of course, if the
caller is a higher-order word itself, it should follow that principle
itself.

>> Static typing languages like C++ use templates for that, but the result
>> is code explosion, because the compiler recompiles that whenever you use
>> a new type.
>
>I think it does that either for C compatibility, or to generate the
>fastest possible code. It could in principle (unless there's some
>C++-specific issue preventing it) use an OO-like dispatch based on the
>argument type instead.

Yes, there is at least one C++-specific issue preventing it: In
general data structures in C++ are not implemented in a way that
allows this. There would be more boxing needed to allow a
one-implementation-fits-all approach. There may be other issues.

[Mark Wills]

On Aug 30, 9:42 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
> But C's main problem is one fundamental mistake: buffers are passed
> around as pointers, without length.  This is a direct invitation to
> buffer overflows.  The problem of C is not just a lack of type
> information, it is the lack of a very vital information: the lack of
> knowing how big a buffer actually is.
>
> Forth doesn't know about types, but its buffer operations all know about
> the size of the buffer.
>

Hmmm... I'm going to have to call you on that one, Bernd!

CALL!

I agree re C's shortcomings, but I don't see that Forth is any better:

CREATE BUFFER 300 CHARS ALLOT

How a does a subsequent definition referencing BUFFER know how big
BUFFER is? Remember: Forth sets you free. You're free to fuck up in
any way you want ;-) This is blessing or curse. Just depends on
personal preference and experience, I suppose.

If we had a dedicated word for creating buffers that took a parameter
on creation then the problem would be essentially solved:

: BUFFER ( interpretation: size "name" -- children: -- address size)
CREATE DUP , ALLOT ALIGN DOES> DUP @ SWAP 1 CELLS+ SWAP ;

Well, 'solved' in the sense that children of BUFFER report their
allocation size on the stack, in addition to their buffer address when
referenced, so there would be no excuse for lazy programmers to allow
their code to read/write beyond the end of a buffer.

The above makes their usage in loops reasonably 'safe':

100 BUFFER MyBuf
: SeeBuffer MyBuf 0 DO DUP I + C@ . LOOP DROP ;

That's probably as safe as we can get without using dedicated buffer
fetch and store words/primitives that do bounds checks.

It's nice that we can 'roll our own' buffer handling words such as the
above, however, there's nothing about the above that couldn't be
reproduced in C with a simple struct, which makes me think that C's
somewhat bad reputation (with regard to buffer overflows/overruns) is
not really down to the languge itself, but rather just pure lazy
programming!

I have previously lamented over the lack of 'true' buffers in Forth,
but the ease with which one can roll their own is possibly why it is
an area that hasn't been standardised.

[Anton Ertl]

Mark Wills <markrob...@yahoo.co.uk> writes:

>On Aug 30, 9:42=A0pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
>> Forth doesn't know about types, but its buffer operations all know about
>> the size of the buffer.
>>
>
>Hmmm... I'm going to have to call you on that one, Bernd!
>
>CALL!
>
>I agree re C's shortcomings, but I don't see that Forth is any better:
>
>CREATE BUFFER 300 CHARS ALLOT
>
>How a does a subsequent definition referencing BUFFER know how big
>BUFFER is?

You pass the length. The difference is that Forth-94 words all take
the length, while C has standard functions like gets(), strcpy(),
strcat() that are not passed the size of the target buffer. For
gets() there is no way to use it safely, but at least there is the
replacement fgets(). OTOH, while strcpy() and strcat() can be used
safely in theory, this is quite cumbersome, so it is often not done,
or not done correctly, and they are the source of many buffer
overflows.

In Forth-200x there is a word that writes a varying amount of data to
memory without passing a data size:

|XC!+ ( xchar xc-addr1 -- xc-addr2 ) XCHAR
|Stores the xchar at xc-addr1. xc-addr2 points to the first memory
|location after the stored xchar.

The justification is that the size of the written data is limited to
four bytes; and there is also an alternative that should be safer
against buffer overflows:

|XC!+? ( xchar xc-addr1 u1 -- xc-addr2 u2 flag ) XCHAR
|Stores the xchar into the string buffer specified by xc-addr1 u1.
|xc-addr2 u2 is the remaining string buffer. If the xchar did fit into
|the buffer, flag is true, otherwise flag is false, and xc-addr2 u2
|equal xc-addr1 u1. XC!+? is safe for buffer overflows.

[Coos Haak]

Op Fri, 31 Aug 2012 03:29:38 -0700 (PDT) schreef Mark Wills:

<snip>

>: BUFFER ( interpretation: size "name" -- children: -- address size)
> CREATE DUP , ALLOT ALIGN DOES> DUP @ SWAP 1 CELLS+ SWAP ;

Why use ALIGN here? If this word is followed by a word that uses CREATE
then its data field is always aligned, like the data comma'ed (DUP ,)
Perhaps you wanted .. DUP , ALIGNED ALLOT DOES> ..

--
Coos

CHForth, 16 bit DOS applications
http://home.hccnet.nl/j.j.haak/forth.html

[Rod Pemberton]

"Anton Ertl" <an...@mips.complang.tuwien.ac.at> wrote in message
news:2012Aug3...@mips.complang.tuwien.ac.at...

> Mark Wills <markrob...@yahoo.co.uk> writes:
> >On Aug 30, 9:42=A0pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:

...

> >> Forth doesn't know about types, but its buffer operations all know
> >> about the size of the buffer.
> >

> >How a does a subsequent definition referencing BUFFER know how big
> >BUFFER is?
>
> You pass the length. The difference is that Forth-94 words all take

> the length, [...]

Ok.

> [...] while C has standard functions like gets(), strcpy(),

> strcat() that are not passed the size of the target buffer. For
> gets() there is no way to use it safely, but at least there is the
> replacement fgets().

False.

You seem to have a trivial or cursory understanding of the issue.

1) gets() is only unsafe when passed input which exceeds the input buffer's
length. The standard input stream in C is redirectable to inputs other than
the potentially unlimited input from the user's keyboard. I.e., a file
where the data line lengths are known in advance to fit within the input
buffer.

2) fgets() is unsafe too. It can also be passed input which exceeds the
input buffer's length. There is nothing requiring the length passed to
fgets() to be smaller or no more than the size of the input buffer.

> OTOH, while strcpy() and strcat() can be used safely in theory,
> this is quite cumbersome, so it is often not done, or not done

> correctly, [...]

False.

They are not cumbersome nor frequently misused. I've never had a need for
strncpy() or strncat() or other "safety" functions to prevent buffer
overflows. You shouldn't get buffer overflows if you make sure the input
buffer is large enough, and avoid using gets().

> [...] and they are the source of many buffer overflows.

False.

They _can_ be the source of _some_ buffer overflows. I think you're basing
this claim of "many" on the fact that someone created strlcpy() and
strlcat(). Whether they are the source of many, or whether "many" is
reserved for gets() is debatable. I've not seen gets() used much, although
it's decried as the major problem.

FYI, some years ago a security paper identified these as issues in C:

1) 15 C functions suffer buffer overflow problems:
gets() cuserid() scanf() fscanf() sscanf() vscanf() vsscanf() vfscanf()
sprintf() strcat() strcpy() streadd() strecpy() vsprintf() strtrns()

2) 8 C functions suffer from format string vulnerabilities
printf() fprintf() sprintf() snprintf() vprintf() vfprintf() vsprintf()
vsnprintf()


Except for gets(), the functions above with buffer overflows shouldn't have
buffer overflows if used correctly with a large enough buffer.

The functions above with format string vulnerabilities affect the majority
of C implementations since most use a common stack for both control-flow and
other data to implement recursion. These exploits modify the control-flow
data on the stack. The solution to that is to *not* fix the functions. The
solution is to use two stacks, ala Forth. Unlike Forth, C doesn't need to
allow users access to any control-flow. So, by simply by providing a
separate control-flow stack, the most damaging of C's exploits stop
occuring.


But, I don't see how any of this is that much different from Forth. Forth
has a number of problems that can be exploited too. Allowing users to
directly access the control-flow stack via >R R> R@ allows for a variety
control-flow attacks. This is much easier to do in Forth than in C. Forth
provides the mechanism to do so cleanly. C must be abused to do so.
ALLOTing negative quantities could allow for dictionary attacks. Use of '
(tick) returning the execution address of dictionary words could allow for a
dictionary attacks too. Use of ! (store) without ALLOT or , (comma) into
the dictionary could allow for executable code to be stored and "hidden"
there temporarily and therefore go undetected.


Rod Pemberton

[Rod Pemberton]

"Andrew Haley" <andr...@littlepinkcloud.invalid> wrote in message
news:b-mdnS3hM6567d3N...@supernews.com...

> Rod Pemberton <do_no...@notemailnot.cmm> wrote:
> > "Bernd Paysan" <bernd....@gmx.de> wrote in message
> > news:2250796.Q...@sunwukong.fritz.box...

[...]

> >> But C's main problem is one fundamental mistake: buffers are passed
> >> around as pointers, without length.
> >
> > If you knew anything about C, you'd know that the length of a buffer
> > is always known. It's either in the declaration of the buffer, or
> > was needed to allocate the buffer dynamicly, or is available with
> > sizeof() or strlen() etc. Whether or not the length is available
> > when needed is a programmer implementation issue.
>
> Well, yes. It's the "programmer implementation issue" that Bernd is
> talking about. It's the fact that if someone passes you an int[] you
> can't say "How big is this?" Yes, you can insist that they also pass
> you the size, but that doesn't change the fact that the language
> doesn't.
>

So? Why should the language? Forth doesn't do a bunch of stuff that C does
for the user. Forth requires the user to do so: stack mainenance,
allocation, etc. So, how is Forth any better than C? IMO, this is a "black
pot calling the black kettle 'black'" issue.

> >> The other way to deal with that problem is to have a unique hash
> >> function, which the attacker can't create hash collisions for (for
> >> being "unique", something quite simple is completely sufficient:
> >> xor all strings with the same secret).
> >
> > There is no guarantee that for two non-XOR'd strings which are hash
> > collisions that their two XOR'd strings won't be hash collisions
> > also. If the hash function has low collisions, then it's unlikely
> > the XOR'd strings will collide, but that's also true for the
> > non-XOR'd strings.
>
> You're missing the point. The idea of the unique hash function is not
> to make collisions impossible but to make them unpredictable: the
> scenario is one where the attacker knows the hash function and
> deliberately creates collisions.
>

What value does that have?

After working through the conlusion further below, I can only see XOR-ing of
being of very minimal use in preventing some type of pre-computed dictionary
attacks involving hash collisions. That's if the use of XOR-ing is kept
secret, is indeterminable, and the attacker isn't intelligent enough to
determine what is being done. If the attacker knows the hash function and
they aren't obtaining the desired collisions, they know something has
changed. Since the XOR secret is used on all inputs, if the attacker has
the hash values for the host under attack, he only need try numerous secret
strings until the hash values begin to match. So, even when using a secret
XOR, one must keep the hash values secret too. IIRC, *nix style hosts don't
or (didn't) keep the resulting hash lists secret for it's password file.

But, there is an even simpler method than XOR-ing to do that. There is no
need to XOR. Use a "salt":
http://en.wikipedia.org/wiki/Salt_(cryptography)


How I came to the conclusion that XOR-ing is of minimal use:

There is no need to make collisions "unpredictable" if collisions aren't a
problem in some manner. I.e., making collisions "unpredictable" means there
is some problem with collisions. The best solution in that case is to
reduce the input set and use a hash with a lower frequency or probability of
collisions, i.e., a better hash and/or a larger sized hash value.

If the attacker knows which hash function is being used, then the attacker
knows the entire set of input strings too. Shifting the input set via XOR
doesn't eliminate or reduce the overall frequency or probability of
collisions generated by the hash. So, the probability that the shifted set
collides is the same as the unshifted set. If collisions are occuring at
the same rate and those collisions are causing some problem, all the
attacker has to do is run the entire input set until he or she finds
alternate collisions. Of course, the input set is comprised of limited
range character data. So, shifting may reduce collisions overall (or may
increase collisions), but it won't change the frequency or probability that
collisions will occur. I.e., some collisions are still likely to occur.
The attacker just needs to find them. But, that is no different from the
original set of strings.


Rod Pemberton

[Bernd Paysan]

Rod Pemberton wrote:
> So? Why should the language? Forth doesn't do a bunch of stuff that
> C does
> for the user. Forth requires the user to do so: stack mainenance,
> allocation, etc. So, how is Forth any better than C? IMO, this is a
> "black pot calling the black kettle 'black'" issue.

Yes, you don't get stack underflows in C. You get stack overflows in C
just as in Forth as error condition - catching both stack under- and
overflow is done by guard pages, and therefore not a real issue. You
get buffer overflows in C due to the brain-damaged stdlib functions
which don't check for buffer size, and these buffer overflows even allow
you to overwrite your return address, which is the common attack vector.
You can't do that in Forth for two reasons:

a) The return stack is in a separate memory region, ideally guarded by
unmapped pages (as in Gforth).

b) your buffer writing words aren't prone to overflow as in C.

However you can shoot yourself into your own foot in many ways in Forth.

But, if you have words writing into buffers, there are only two sane
ways of doing it:

a) the word knows the buffer size, and can stop writing before the
buffer overflows
b) the word can expand the buffer so that the data will fit.

Insane is

c) neither, which is why this language is called C ;-).

>> You're missing the point. The idea of the unique hash function is
>> not to make collisions impossible but to make them unpredictable: the
>> scenario is one where the attacker knows the hash function and
>> deliberately creates collisions.
>>
>
> What value does that have?
>
> After working through the conlusion further below, I can only see
> XOR-ing of being of very minimal use in preventing some type of
> pre-computed dictionary
> attacks involving hash collisions. That's if the use of XOR-ing is
> kept secret, is indeterminable, and the attacker isn't intelligent
> enough to
> determine what is being done.

Nope. The only thing you have to keep secret is the actual value you
are xoring with.

> If the attacker knows the hash function
> and they aren't obtaining the desired collisions, they know something
> has
> changed. Since the XOR secret is used on all inputs, if the attacker
> has the hash values for the host under attack, he only need try
> numerous secret
> strings until the hash values begin to match.

Yes. And how does he know that they match? The point of these hash
attacks is to fill the hash with single, pretty long chain, and then use
the degenerated performance of that hash to slow down the machine under
attack. The attacker does not actually have any way to deterine how the
hash looks like except for the timing of the attacked machine.

> So, even when using a
> secret
> XOR, one must keep the hash values secret too.

That's what even PHP on a server does (and PHP does a lot of stupid
things). You can't force it to print out the hash table for inspection
if your attack is working or not.

> IIRC, *nix style hosts
> don't or (didn't) keep the resulting hash lists secret for it's
> password file.

You are confusing things...

> But, there is an even simpler method than XOR-ing to do that. There
> is no
> need to XOR. Use a "salt":
> http://en.wikipedia.org/wiki/Salt_(cryptography)

That's solving a quite different problem. You can't use salt in a
key,value hash table. You can (and should) have salt in a password
hash. IMHO, you actually should not use password authentication in the
21st century, as we have much better public key authentication, where
stealing a whole shitload of pubkeys from a server doesn't give you
anything useful. That's why they are called public keys: They don't
have to be hidden.

Passwords are shared secrets, and they have to be kept secret; adding
salt is helping a bit, but dictionary attacks still work on salted
hashs. Most people use words from dictionaries as passwords, and maybe
add a single digit.

> How I came to the conclusion that XOR-ing is of minimal use:
>
> There is no need to make collisions "unpredictable" if collisions
> aren't a
> problem in some manner. I.e., making collisions "unpredictable" means
> there
> is some problem with collisions. The best solution in that case is to
> reduce the input set and use a hash with a lower frequency or
> probability of collisions, i.e., a better hash and/or a larger sized
> hash value.

No. The attack against PHP servers work, because the hashing method is
kown. A better hash function doesn't help, because the attacker
deliberately uses keys that have the same hash value. Regardless how
good your hash function is, as it reduces the key to some small number,
there will be colissions.

> If the attacker knows which hash function is being used, then the
> attacker
> knows the entire set of input strings too. Shifting the input set via
> XOR doesn't eliminate or reduce the overall frequency or probability
> of
> collisions generated by the hash.

No. But it makes it impossible for the attacker to know the hash
function.

> So, the probability that the
> shifted set
> collides is the same as the unshifted set. If collisions are occuring
> at the same rate and those collisions are causing some problem, all
> the attacker has to do is run the entire input set until he or she
> finds
> alternate collisions. Of course, the input set is comprised of
> limited
> range character data. So, shifting may reduce collisions overall (or
> may increase collisions), but it won't change the frequency or
> probability that
> collisions will occur. I.e., some collisions are still likely to
> occur.

Hash collisions per se are not the problem. The problem is that the
attacker deliberately creates a lot of colissions that end up in exactly
the same bucket. And then asks for the values in that hash table (which
is really a list now). That takes too long, so the server is having
troubles responding in time.

> The attacker just needs to find them. But, that is no different from
> the original set of strings.

The difference is that for the orginal set of strings, the attacker can
find colissions on his own computer by just enumerating possible
strings, and filling them into a hash table - e.g. if your hash-table
has 1024 entries, you have a hit rate of just below 0.1%. Just add a
million strings to the PHP hash table, print it out bucket by bucket,
and you have 1024 different chains of about 1000 matching strings.

Now try that on a remote web server where you don't precisely know how
the hash function works (even if you know that it uses the xor method),
and you also can't inspect the hash table.

As usual, to exploit this problem in PHP, you need two bugs together:

a) PHP allows the attacker to insert values in a hash table and probe
that hash table, which both is not really necessary

b) PHP does use one particular hash algorithm

b) is common practice, and the bug in PHP was closed by changing a). We
are discussing here what you can do when changing a) is not an option
(when you absolutely need the other side to inject arbitrary keys into
your hash table). You either go to some deterministic search (b-tree or
such), *or* you create your malleable hash function.

The common theme from CS people who are in trees and merge sort
typically is to point out that hash table and quicksort can degenerate
to bad performance when deliberately attacked, so their general
performance advantage is lost. And the response is that you can
mitigate that thread by making the actual hash function hard to guess
(in a cryptographic sense hard), and by making the pivot choice of
quicksort hard to guess (using random pivot selection). Both is quite
trivial, and closes that threat model, without the same performance hit
as going to a deterministic upper bound architecture, which is always
slower, even when you aren't under attack.

[Elizabeth D. Rather]

On 8/31/12 12:29 AM, Mark Wills wrote:
...

> If we had a dedicated word for creating buffers that took a parameter
> on creation then the problem would be essentially solved:
>
> : BUFFER ( interpretation: size "name" -- children: -- address size)
> CREATE DUP , ALLOT ALIGN DOES> DUP @ SWAP 1 CELLS+ SWAP ;
>
> Well, 'solved' in the sense that children of BUFFER report their
> allocation size on the stack, in addition to their buffer address when
> referenced, so there would be no excuse for lazy programmers to allow
> their code to read/write beyond the end of a buffer.
>
> The above makes their usage in loops reasonably 'safe':
>
> 100 BUFFER MyBuf
> : SeeBuffer MyBuf 0 DO DUP I + C@ . LOOP DROP ;
>
> That's probably as safe as we can get without using dedicated buffer
> fetch and store words/primitives that do bounds checks.

Here's a simpler way (cell-wise example):

: BUFFER ( size -- ) CREATE DUP , CELLS ALLOT
DOES> ( i -- a ) DUP @ >R ( i a ) OVER 0 R> WITHIN IF \ Legal
SWAP 1+ CELLS + ELSE 10 THROW THEN ;

This takes an index and returns the indexed cell's address. Example:

10 CONSTANT SIZE
SIZE BUFFER MY-STUFF

: SHOW ( -- ) SIZE 0 DO I MY-STUFF @ . LOOP ;

Then you always supply the index, and the check will be provided.
Doesn't require external variables or error-checking routines. You
should, of course, define your throw code as a nicely named constant.

Of course you aren't prevented from saying:

0 MY-STUFF 100 ERASE

...but you're protected against most common errors.

> It's nice that we can 'roll our own' buffer handling words such as the
> above, however, there's nothing about the above that couldn't be
> reproduced in C with a simple struct, which makes me think that C's
> somewhat bad reputation (with regard to buffer overflows/overruns) is
> not really down to the languge itself, but rather just pure lazy
> programming!
>
> I have previously lamented over the lack of 'true' buffers in Forth,
> but the ease with which one can roll their own is possibly why it is
> an area that hasn't been standardised.

Bingo, that's exactly why. Every particular situation has slightly
different needs and constraints, and you can tailor your buffer designs
specifically to those.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> Nope. The only thing you have to keep secret is the actual value you
> are xoring with.

Xoring with some constant is not necessarily good enough (it amounts to
initializing the hash calculation with a fixed secret value):

http://www.eng.tau.ac.il/~yash/C2_039_Wool.pdf

The original Crosby and Wallach paper suggested a fancier approach using
universal hashing (i.e. with crypto primitives). That's slower on
regular CPU's but with AES hardware showing up in recent x86's, maybe
it's the best way, if you want to stay with hash tables.

[Anton Ertl]

Bernd Paysan <bernd....@gmx.de> writes:
>> But, there is an even simpler method than XOR-ing to do that. There
>> is no
>> need to XOR. Use a "salt":
>> http://en.wikipedia.org/wiki/Salt_(cryptography)
>
>That's solving a quite different problem. You can't use salt in a
>key,value hash table.

Not the per-key salt anyway. But if you prepend the same salt to all
strings, it has the same effect as your XOR.

>The common theme from CS people who are in trees and merge sort
>typically is to point out that hash table and quicksort can degenerate
>to bad performance when deliberately attacked, so their general
>performance advantage is lost. And the response is that you can
>mitigate that thread by making the actual hash function hard to guess
>(in a cryptographic sense hard), and by making the pivot choice of
>quicksort hard to guess (using random pivot selection). Both is quite
>trivial, and closes that threat model, without the same performance hit
>as going to a deterministic upper bound architecture, which is always
>slower, even when you aren't under attack.

I have read that mergesort is faster than quicksort, but more
memory-consuming, and that glibc's qsort uses mergesort for
small-enough arrays, and quicksort for the larger ones (probably with
mergesort again for the small-enough sub-arrays).

[Anton Ertl]

Cryptographic hashes won't help at all against the attack described in
the paper above (and the paper already mentions that in the abstract),
and the reason is explained by Bernd and by footnote 2 of the paper
above: Whatever the hash function is, if you only have 2^10 or 2^13
buckets, it is easy to find values that collide in the hash table.

However, the attack works by using exhaustive search over the possible
secret values. The authors claim it is realistic for secret values of
13-14 bits (it needs about 1000 packets per possible secret value).
I, of course would use a full word (32 or 64 bits) as a secret value,
and I don't think that an exhaustive search against that is realistic
(it would require sending about 2^42 packets, which will take a long
time). Actually, in their conclusion the authors write "Thus, it
seems that a random value of 32 bits would render this attack
impractical with today's technology."

[Anton Ertl]

"Rod Pemberton" <do_no...@notemailnot.cmm> writes:
>"Anton Ertl" <an...@mips.complang.tuwien.ac.at> wrote in message
>news:2012Aug3...@mips.complang.tuwien.ac.at...

>2) fgets() is unsafe too. It can also be passed input which exceeds the
>input buffer's length. There is nothing requiring the length passed to
>fgets() to be smaller or no more than the size of the input buffer.
>
>> OTOH, while strcpy() and strcat() can be used safely in theory,
>> this is quite cumbersome, so it is often not done, or not done
>> correctly, [...]
>
>False.
>
>They are not cumbersome nor frequently misused. I've never had a need for
>strncpy() or strncat() or other "safety" functions to prevent buffer
>overflows.

Sure, strncpy() and strncat() suck even more than strcpy() and strcat().

>> [...] and they are the source of many buffer overflows.
>
>False.
>
>They _can_ be the source of _some_ buffer overflows. I think you're basing
>this claim of "many" on the fact that someone created strlcpy() and
>strlcat().

I am actually basing this on reading reports on vulnerabilities that
mentioned unsafe use of strcpy() or strcat() as cause for the
vulnerability. At first I wondered why these functions would cause a
buffer overflow, given that the source string(s) is/are already in
memory and have passed the input checks on the inputs, but after some
time, I saw how typical C idioms might lead to such vulnerabilities.

>The solution to that is to *not* fix the functions. The
>solution is to use two stacks, ala Forth.

That will make attacks a little harder, but is not a proper solution.
As long as there are arbitrarily indirect pointers to code (and the
code is eventually executed through that indirection chain), a buffer
overflow that can manipulate such a pointer can make the program try
to execute code at any address. An example of such an indirect
pointer is the class pointer in C++ objects; in C, and function
pointers, pointers to structs that contain (among other things) a
function pointer, pointers to structs that contain pointers like the
one described above, etc.

>But, I don't see how any of this is that much different from Forth. Forth
>has a number of problems that can be exploited too. Allowing users to
>directly access the control-flow stack via >R R> R@ allows for a variety
>control-flow attacks.

>R R> R@ accesses the return stack, not the control-flow stack.

If you let write your application such that an untrusted end user can
manipulate the return stack arbitrarily, sure, you have opened up a
big hole. Most applications don't allow arbitrary manipulations of
the return stack to end-users, though.

If the development personell is not trusted, then Forth is definitely
not the right language for the project, but I doubt that any
general-purpose programming can be done in such a setting, whatever
the language. I guess that paranoid organizations have developed
methods to ensure they can trust the development personell as a whole,
even though they trust no single one person, but that's a pretty
exotic setting.

[Bernd Paysan]

Anton Ertl wrote:
>>That's solving a quite different problem. You can't use salt in a
>>key,value hash table.
>
> Not the per-key salt anyway. But if you prepend the same salt to all
> strings, it has the same effect as your XOR.

If your hash algorithm actually is cryptographically strong, yes. Many
fast hash algorithms however have easy pre-image attacks, i.e. if you
know the hashes of both the salt and the key itself, you can compute the
hash of the combined part. Especially if the keys collide, they also
will collide with whatever salt you add. Nothing gained.

There might be hash algorithms where the XOR method does not gain
anything, either. So well, you have to check if it actually works. If
your hash has no pre-image problems, you can use the "same salt"-
approach.

>>The common theme from CS people who are in trees and merge sort
>>typically is to point out that hash table and quicksort can degenerate
>>to bad performance when deliberately attacked, so their general
>>performance advantage is lost. And the response is that you can
>>mitigate that thread by making the actual hash function hard to guess
>>(in a cryptographic sense hard), and by making the pivot choice of
>>quicksort hard to guess (using random pivot selection). Both is quite
>>trivial, and closes that threat model, without the same performance
>>hit as going to a deterministic upper bound architecture, which is
>>always slower, even when you aren't under attack.
>
> I have read that mergesort is faster than quicksort, but more
> memory-consuming, and that glibc's qsort uses mergesort for
> small-enough arrays, and quicksort for the larger ones (probably with
> mergesort again for the small-enough sub-arrays).

Not sure if that's true. Quicksort is in-place sorting, which means it
consumes less memory. Less memory means also less bandwidth required,
and better use of the cache hierarchy. I've read complaints that
quicksort's memory access pattern is "wrong", while mergesort gets it
"right", but both do unit-stride sequential access, and the actual data
(strings) pointed by these pointers is random access for boths.
Quicksort has sequential access in reverse direction on one end, which
might hurt (prefetch algorithms often assume that you go upwards). The
only unpredictable access in improved quicksort is the random pivot
access (for obvious reasons it is unpredictable).

For quicksort, you need two running pointers, for mergesort, three.
Otherwise, the number of operations per step are quite similar.

AFAIK, the argument for qsort in glibc being a merge sort is that it is
easier to hack mergesort to detect partially sorted fields, and use the
detection to not sort them at all (which overall is cheaper). This is
because mergesort first breaks the data into chunks and then sorts them,
having sorted sub-arrays, while quicksort puts data into two bins, and
only the last stage or recursion produces a total order. Pre-sorted
sub-arrays will be split during quicksort.

However, the only reasonable way to apply this would be to have
mergesort used for larger arrays, and quicksort for the small ones,
where you know they aren't pre-sorted.

[Bernd Paysan]

Rod Pemberton wrote:
> But, I don't see how any of this is that much different from Forth.
> Forth
> has a number of problems that can be exploited too. Allowing users to
> directly access the control-flow stack via >R R> R@ allows for a
> variety
> control-flow attacks. This is much easier to do in Forth than in C.

That's silly. If you allow an attacker to compile arbitrary Forth code
while running the program, he won't need to use control-flow tricks to
gain control. The point in C is that you can gain control by simply
having an unexpectedly large field somewhere in a file or an input
stream, and boom, your program goes astray.

> Forth
> provides the mechanism to do so cleanly. C must be abused to do so.

Indeed, in C you couldn't even do what I described above: Let the
attacker compile arbitrary code from source. In Forth, you can. If you
deliberately want to expose the compiler to the end user, yes, it's
possible. If you do, you better should sandbox the complete program.

> ALLOTing negative quantities could allow for dictionary attacks. Use
> of ' (tick) returning the execution address of dictionary words could
> allow for a
> dictionary attacks too. Use of ! (store) without ALLOT or , (comma)
> into the dictionary could allow for executable code to be stored and
> "hidden" there temporarily and therefore go undetected.

And you allow input from unknown origin to do all these things?

[Anton Ertl]

Bernd Paysan <bernd....@gmx.de> writes:

>Anton Ertl wrote:
>> Not the per-key salt anyway. But if you prepend the same salt to all
>> strings, it has the same effect as your XOR.
>
>If your hash algorithm actually is cryptographically strong, yes. Many
>fast hash algorithms however have easy pre-image attacks, i.e. if you
>know the hashes of both the salt and the key itself, you can compute the
>hash of the combined part. Especially if the keys collide, they also
>will collide with whatever salt you add. Nothing gained.

That means that, if "uvw" and "xyz" collide, so will "abcuvw" and
"abcxyz"? Does not sound like a good hash function to me. Which hash
function behaves that way?

>> I have read that mergesort is faster than quicksort, but more
>> memory-consuming, and that glibc's qsort uses mergesort for
>> small-enough arrays, and quicksort for the larger ones (probably with
>> mergesort again for the small-enough sub-arrays).
>
>Not sure if that's true. Quicksort is in-place sorting, which means it
>consumes less memory. Less memory means also less bandwidth required,
>and better use of the cache hierarchy.

There are some numbers at
<http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html>. It
seems that it depends on the actual sizes which is faster.

[Bernd Paysan]

Anton Ertl wrote:
> That means that, if "uvw" and "xyz" collide, so will "abcuvw" and
> "abcxyz"? Does not sound like a good hash function to me. Which hash
> function behaves that way?

Gforth's hashkey, at least when the same rotation factor is chosen for
all strings (and for longer strings, the rotation factor tends to be 5,
though as for short strings we use different rotation factors, and
there, different string lengths won't collide).

> There are some numbers at
> <http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html>. It
> seems that it depends on the actual sizes which is faster.

Apparently, the backward stride access hurts on the Pentium 3. As
noted, this depends on the CPU, and is not so easy to determine. For
large arrays, allocating a buffer and then not really freeing it (free()
does not give the memory back to the OS) is really awful, as mentioned.
In-place is a must there.

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
>> "This program must never dereference a null pointer for any input" is
>> simple enough to specify

> But C's main problem is one fundamental mistake: buffers are passed
> around as pointers, without length.

Leaving aside the tangent about subscript checking (which is a difficult
problem in any language), remember the example I gave was about null
pointers, not subscript errors. Java checks subscripts, but it also has
null pointers and null pointer exceptions (NPE). ML and Haskell get rid
of NPE by using option types instead of null pointers.

Similarly for array subscripts: in FP style, one typically does array
operations using higher-order functions like map and fold, eliminating
quite a few potential subscript errors by simply getting rid of the
subscripts. There are of course places where subscripts are still
needed, and those are subject to the usual hazards.

>> [Balanced trees] let you ... traverse the keys in order.

> In what order? Alphabetical order? Does that matter? Do you really
> want all fruits from apples to bananas listed?

Sure, that is very normal in query systems. Think of a bug tracker
where you can view all the open bugs in order of newest first, most
recently updated first, highest priority first, name of reporter
(alphabetical), name of person assigned to fix the bug, etc. Most of
those fields can be updated at any time.

> Database implementers like B-trees particularly, because they can easily
> be made transaction-safe. I.e. when you do a transaction, you copy the
> parts of the tree which contain the new state, and then you only update
> the root pointer

Yes, this is similar to the persistence feature of AVL or red-black
trees as used in functional programming.

> For me, this sort of B-trees or priority queues are problems which you
> face during university, because they are popular data structures. In
> "real life", they don't happen that often. If you really need them, you
> write them once, and then they are part of your toolbox.

Why would I write them even once? There are highly tuned library
implementations already, so I use those, and I do use them often.

> The priority queue I wrote (for MINOS) didn't get a complicated data
> structure, because the usual case is that there aren't many events

> waiting. .... It is O(n), but the constant overhead is very low.

Yeah, that's something like what I ended up doing in the Python program
I mentioned. It's good enough for the program's current workload, so
fine. But I'd prefer to have been able to call a library routine that
did the right thing even for large N. I've been wondering, for example,
how Forth multitaskers handle event scheduling when there are a large
number of tasks, and how many tasks the traditional systems typically
ran. It certainly seems realistic to want to handle N>10000 in today's
high concurrency systems.

> I've made some thought about how I would implement the priority queue of
> a gate-level simulator, and my preferred data structure would be an
> array with a fixed time scale,

If you don't have to reschedule events after they've been added, it
sounds best to use a traditional binary heap. Those are space-efficient
and easy to implement. The Python library doc has a reasonable
description of how they work ("theory" section at end):

http://docs.python.org/library/heapq.html

> if your fixed time scale is less than the minimum delay..

> With the "constant time scale per schedule bucket = minimum delay"
> equation mentioned above, I'd be curious how that would look in Coq.

I'm not sure I understand the problem, but it sounds like:
1) you want to have buckets of size h, which means that if there's
an event at time t0, the next bucket starts at t1 for some
t1 <= t0+h.
2) if the event at time t0 spawns a new event, the new event is
at time t0+dt for some dt>=h.

This doesn't sound terribly hard to formalize. Then, given dt>=h, you
want to prove t0+dt>=t0+h, which should be trivial in any reasonable
proof system. I don't yet know how to actually do anything like that in
Coq, though.

There is an article "The Seventeen Provers of the World" showing proofs
that sqrt(2) is irrational in that many systems:

http://www.cs.ru.nl/~freek/comparison/

[Elizabeth D. Rather]

On 9/1/12 4:49 AM, Anton Ertl wrote:
> "Rod Pemberton" <do_no...@notemailnot.cmm> writes:
...

>> But, I don't see how any of this is that much different from Forth. Forth
>> has a number of problems that can be exploited too. Allowing users to
>> directly access the control-flow stack via >R R> R@ allows for a variety
>> control-flow attacks.
>
>> R R> R@ accesses the return stack, not the control-flow stack.
>
> If you let write your application such that an untrusted end user can
> manipulate the return stack arbitrarily, sure, you have opened up a
> big hole. Most applications don't allow arbitrary manipulations of
> the return stack to end-users, though.
>
> If the development personell is not trusted, then Forth is definitely
> not the right language for the project, but I doubt that any
> general-purpose programming can be done in such a setting, whatever
> the language. I guess that paranoid organizations have developed
> methods to ensure they can trust the development personell as a whole,
> even though they trust no single one person, but that's a pretty
> exotic setting.

In general, Forth applications should not (and most do not) allow user
access to the Forth interpreter or compiler. There are many ways to
achieve this with complete security, ranging from a sealed wordlist at
the top of the application to removing these features from a
cross-compiled program altogether.

[Bernd Paysan]

Paul Rubin wrote:
> Leaving aside the tangent about subscript checking (which is a
> difficult problem in any language), remember the example I gave was
> about null
> pointers, not subscript errors. Java checks subscripts, but it also
> has
> null pointers and null pointer exceptions (NPE). ML and Haskell get
> rid of NPE by using option types instead of null pointers.

C somewhat has NPEs, too, through signals and setsigjmp. C's exception
handling is not really up to date ;-). Lisp-like languages always had a
NIL thing, which wasn't quite the same as a null pointer.

> Similarly for array subscripts: in FP style, one typically does array
> operations using higher-order functions like map and fold, eliminating
> quite a few potential subscript errors by simply getting rid of the
> subscripts.

Yes, that's generally a good idea to do it that way. In Forth, we use
"design patterns" like

( addr u ) bounds ?DO
I ...
<size> +LOOP

which aren't prone to off-by-one errors like C's

for(i=0; i<n; i++) {
...
}

statement (many people write "i<=n", because they count from 1..n, but
in fact, C counts from 0..n-1).

> There are of course places where subscripts are still
> needed, and those are subject to the usual hazards.

Of course. Either prove that the index always will match the bound or
check...

>>> [Balanced trees] let you ... traverse the keys in order.
>> In what order? Alphabetical order? Does that matter? Do you really
>> want all fruits from apples to bananas listed?
>
> Sure, that is very normal in query systems. Think of a bug tracker
> where you can view all the open bugs in order of newest first, most
> recently updated first, highest priority first, name of reporter
> (alphabetical), name of person assigned to fix the bug, etc. Most of
> those fields can be updated at any time.

Yes, but that are sorted indices, which remain sorted all the time, so
all you need is to have a insert and delete operation into them which
isn't costly.

Example: Forth's dictionary has a "newest first" order, not only in
search, but also when you list it with WORDS. So in Gforth, we keep the
linked list of all words as "index" into the dictionary. Access goes
through the hash, though. Such an index is quite compact (one cell per
item), and if you want to list all apples to bananas, you search for
apples and bananas in the hash, and then walk the "sorted by name" list
starting with apples until you match bananas.

You might use a B-tree or some similar data structure to keep these
indices sorted, but you don't actually use them to search for elements,
because the hash is faster.

> Why would I write them even once? There are highly tuned library
> implementations already, so I use those, and I do use them often.

Yes, in fact, usually, you treat such building blocks as given. In
Forth maybe not... so you may need to write them *once*.

> Yeah, that's something like what I ended up doing in the Python
> program
> I mentioned. It's good enough for the program's current workload, so
> fine. But I'd prefer to have been able to call a library routine that
> did the right thing even for large N.

Even when it's the wrong thing for small N? The small-N priority queue
has a very small constant overhead, and very small code size, so it is
better for small Ns than a binary heap.

> I've been wondering, for
> example, how Forth multitaskers handle event scheduling when there are
> a large number of tasks, and how many tasks the traditional systems
> typically
> ran. It certainly seems realistic to want to handle N>10000 in
> today's high concurrency systems.

The traditional Forth multitaskers ran on single-core systems. The one
I wrote for bigForth has two double-linked queues: active and sleeping,
so event scheduling (wake up a task) is a O(1) operation. Traditional
multitaskers are round-robin, so there is not much need for locks or
similar thoughts. If you want single core, but many tasks (each of
which does only a little thing and then goes to sleep again), the
traditional Forth multitasker is much better than POSIX threads, which
aren't all that lightweight.

> If you don't have to reschedule events after they've been added, it
> sounds best to use a traditional binary heap. Those are
> space-efficient
> and easy to implement. The Python library doc has a reasonable
> description of how they work ("theory" section at end):
>
> http://docs.python.org/library/heapq.html

Yes, they also have the nice property that you don't have to care about
their balance, only to reestablish the invariance. A heap is partially
sorted, i.e. you don't actually know where the largest element is, but
you always know where the smallest element is. Maybe I should write one
this evening, it's always useful to have such data structures at hand.

>> if your fixed time scale is less than the minimum delay..
>> With the "constant time scale per schedule bucket = minimum delay"
>> equation mentioned above, I'd be curious how that would look in Coq.
>
> I'm not sure I understand the problem, but it sounds like:
> 1) you want to have buckets of size h, which means that if there's
> an event at time t0, the next bucket starts at t1 for some
> t1 <= t0+h.
> 2) if the event at time t0 spawns a new event, the new event is
> at time t0+dt for some dt>=h.
>
> This doesn't sound terribly hard to formalize. Then, given dt>=h, you
> want to prove t0+dt>=t0+h, which should be trivial in any reasonable
> proof system. I don't yet know how to actually do anything like that
> in Coq, though.

Yes, I think it should not be hard to formalize, which is why I would be
courious how it looks in Coq.

> There is an article "The Seventeen Provers of the World" showing
> proofs that sqrt(2) is irrational in that many systems:
>
> http://www.cs.ru.nl/~freek/comparison/

Nice comparison.

[Rod Pemberton]

"Anton Ertl" <an...@mips.complang.tuwien.ac.at> wrote in message

news:2012Sep...@mips.complang.tuwien.ac.at...

> "Rod Pemberton" <do_no...@notemailnot.cmm> writes:
> >"Anton Ertl" <an...@mips.complang.tuwien.ac.at> wrote in message
> >news:2012Aug3...@mips.complang.tuwien.ac.at...

...

> >> [...] and they are the source of many buffer overflows.
> >
> >False.
> >
> >They _can_ be the source of _some_ buffer overflows. I think you're
> > basing this claim of "many" on the fact that someone created strlcpy()
> > and strlcat().
>
> I am actually basing this on reading reports on vulnerabilities that
> mentioned unsafe use of strcpy() or strcat() as cause for the
> vulnerability. At first I wondered why these functions would cause a
> buffer overflow, given that the source string(s) is/are already in
> memory and have passed the input checks on the inputs, but after some
> time, I saw how typical C idioms might lead to such vulnerabilities.

From what I've seen, Forth's faults appear to be almost identical to those
you believe are dangerous for C.

Are you saying I can't CMOVE> doesn't copy into a buffer of unknown size
just like C's strcpy()? CMOVE> doesn't take a size for the destination
buffer. It takes a size for the source buffer. Look it up. I.e., someone
can overflow the destination in Forth just like in C. Where's Forth fixed
version of CMOVE> ?

> >The solution to that is to *not* fix the functions. The
> >solution is to use two stacks, ala Forth.
>
> That will make attacks a little harder, but is not a proper solution.

Given the constraint of someone designing a new language, I'd agree that it
isn't a proper solution to the problem. However, it is a proper solution to
a language which has been in use for at least four decades. It doesn't
interfere with the existing language.

I seem to recall you and others here making the same basic argument in
regards to "preserve the existing name" when asked why Forth creates new
odd names for updated versions of Forth words.

> As long as there are arbitrarily indirect pointers to code (and the
> code is eventually executed through that indirection chain), a buffer
> overflow that can manipulate such a pointer can make the program try
> to execute code at any address.

How is the XT from ' (tick) any different from a function pointer in C?

How is storing an XT in a word to be executed any different from a function
pointer in a struct in C? If it's changed by being overwritten it can
execute any arbitrary Forth code and non-Forth code too.

This Chinese attributed proverb comes to mind:
"Don't complain about the snow on your neighbor's roof when your own
doorstep is unclean.".

I.e., it seems like you're complaining about C's problems when Forth has the
same problems.

Also, that comes with the constraint that there is no protection of code
spaces from being written with data, and data spaces being prevented from
executing code. That was true for decades, but not anymore. Modern
microprocessor architectures have execution prevention.

> > But, I don't see how any of this is that much different from Forth.
> > Forth has a number of problems that can be exploited too. Allowing
> > users to directly access the control-flow stack via >R R> R@ allows
> > for a variety control-flow attacks.
>
> >R R> R@ accesses the return stack, not the control-flow stack.
>

... which is typically the control-flow stack for Forth interpreters.

Let's say you have two users: one with a C compiler on an OS coded in C and
another with a Forth compiler on an OS coded in Forth (assume one exists).
C doesn't provide direct access to it's control-flow. One must abuse C
functions to create a breach. Forth typically did (or does) provide direct
access via R> >R to control-flow. I.e., no abuse needed.

> If you let write your application such that an untrusted end user can
> manipulate the return stack arbitrarily, sure, you have opened up a
> big hole.

That's true for C too, in the sense that the end user can't manipulate C's
control flow for a compiled application, if coded correctly. Someone has to
make a mistake, or the OS allows untrusted code.

> Most applications don't allow arbitrary manipulations of
> the return stack to end-users, though.

That's true for C too, in the sense that the end user can't manipulate C's
control flow for a compiled application, if coded correctly. Someone has to
make a mistake, or the OS allows untrusted code.


Rod Pemberton

[Rod Pemberton]

"Bernd Paysan" <bernd....@gmx.de> wrote in message

news:2390503.S...@sunwukong.fritz.box...

> Rod Pemberton wrote:
> > So? Why should the language? Forth doesn't do a bunch of stuff that
> > C does
> > for the user. Forth requires the user to do so: stack mainenance,
> > allocation, etc. So, how is Forth any better than C? IMO, this is a
> > "black pot calling the black kettle 'black'" issue.
>
> Yes, you don't get stack underflows in C. You get stack overflows in C
> just as in Forth as error condition - catching both stack under- and
> overflow is done by guard pages, and therefore not a real issue.

...

> You get buffer overflows in C due to the brain-damaged stdlib

> functions which don't check for buffer size, [...]

It's not an error with the implementation of the function. It's an error
with the implementation of the code.

Isn't that what you said about stuff overwriting dictionary space?

Can C functions be made which work for novices and idiots? Yes.

> [...] and these buffer overflows even allow you to overwrite your

> return address, which is the common attack vector.

I mentioned this already. I'll repeat. That's not always true. It's true
for *most* C implementations. It's true for C implementations which use a
stack for both data and control-flow. C doesn't require the use of a stack,
nor does C require that control-flow and non control-flow be placed
together.

> You can't do that in Forth for two reasons:
>
> a) The return stack is in a separate memory region, ideally guarded by
> unmapped pages (as in Gforth).
>
> b) your buffer writing words aren't prone to overflow as in C.
>

Except for gets(), C isn't prone to overflow.

So, Forth doesn't have KEY ... ?

Are you saying I can't place KEY in a LOOP and C, (c-comma) until I consume
all dictionary space and maybe space beyond that?

Are you saying I CMOVE> doesn't copy into a buffer of unknown space

just like C's strcpy()?

> However you can shoot yourself into your own foot in many ways in Forth.
>
> But, if you have words writing into buffers, there are only two sane
> ways of doing it:
>
> a) the word knows the buffer size, and can stop writing before the
> buffer overflows
> b) the word can expand the buffer so that the data will fit.
>

CMOVE> knows neither. CMOVE> knows the source buffer length, but *not*
the destination. The destination size is not one of CMOVE>'s parameters.
This is no different from strcpy() in C which Anton just decried as one of
C's most horrid problems... Is CMOVE> one of Forth's most horrid problems?

> Insane is
>
> c) neither, which is why this language is called C ;-).
>

You're clearly not familiar with C's functions. C's string and memory
functions either 1) know the source buffer size or 2) know the size of the
string being copied. What they don't generally know is the destination
buffer's size. That's where the overflow occurs. What they also don't know
is whether a string has been properly terminated or not. But, that's
generally not an issue, unless the programmer constructs a string or has an
invalid pointer.

Given CMOVE> etc, I don't see how that is any different from Forth.

> >> You're missing the point. The idea of the unique hash function is
> >> not to make collisions impossible but to make them unpredictable: the
> >> scenario is one where the attacker knows the hash function and
> >> deliberately creates collisions.
> >>
> >
> > What value does that have?
> >
> > After working through the conlusion further below, I can only see
> > XOR-ing of being of very minimal use in preventing some type of
> > pre-computed dictionary attacks involving hash collisions. That's if
> > the use of XOR-ing is kept secret, is indeterminable, and the attacker
> > isn't intelligent enough to determine what is being done.
>
> Nope. The only thing you have to keep secret is the actual value you
> are xoring with.
>

If the attacker knows you're using XOR, all he has to do is generate
"secret" strings until hashes for a couple other input strings match. You
have to keep the hash values secret also.

> > If the attacker knows the hash function and they aren't obtaining the
> > desired collisions, they know something has changed. Since the XOR
> > secret is used on all inputs, if the attacker has the hash values for
> > the host under attack, he only need try numerous secret strings until
> > the hash values begin to match.
>
> Yes. And how does he know that they match?

He already knows what they are:
"... if the attacker has the hash values for the host under attack ..."

> The point of these hash attacks is to fill the hash with single, pretty
> long chain, and then use the degenerated performance of that hash
> to slow down the machine under attack.

Why would he use the machine under attack to generate the hash values? He
knows the hash function. I'm assuming he knows the hash values too. He can
use any machine to generate more hash values.

> The attacker does not actually have any way to deterine how the
> hash looks like except for the timing of the attacked machine.

I thought someone said the hash function was known to the attacker.

> IMHO, you actually should not use password authentication in the

> 21st century, as we have much better public key authentication, [...]

True.

> [...] where stealing a whole shitload of pubkeys from a server doesn't

> give you anything useful. That's why they are called public keys: They
> don't have to be hidden.

That's generally true. I don't know if that's entirely true. IIRC, there
was a PK encryption method was broken.

The hash values can be used to help reveal which function is used, if it's a
standard hash function. The size of the hash values and the values
themselves can be used to provide information. This is similar to the
frequency analysis of letters. Actually, this is similar to your PHP a)
problem you mentioned [snipped]. Of course, modifying a standard hash
function is a bad idea. It could make it weak enough to crack. So, most
attackers are only going to expect standard, proven hash functions to be
used.

> Passwords are shared secrets, and they have to be kept secret; adding
> salt is helping a bit, but dictionary attacks still work on salted
> hashs. Most people use words from dictionaries as passwords, and maybe
> add a single digit.

Most attackers know that.

> > How I came to the conclusion that XOR-ing is of minimal use:
> >
> > There is no need to make collisions "unpredictable" if collisions
> > aren't a problem in some manner. I.e., making collisions
> > "unpredictable" means there is some problem with collisions. The
> > best solution in that case is to reduce the input set and use a hash
> > with a lower frequency or probability of collisions, i.e., a better
> > hash and/or a larger sized hash value.
>
> No. The attack against PHP servers work, because the hashing method is
> kown. A better hash function doesn't help, because the attacker
> deliberately uses keys that have the same hash value.

...

> Regardless how good your hash function is, as it reduces the key
> to some small number, there will be colissions.

Without something like a "salt" or a large range hash, then you'll get
collisions with shorter input strings. Is that what you mean?

> > If the attacker knows which hash function is being used, then the
> > attacker knows the entire set of input strings too. Shifting the input
> > set via XOR doesn't eliminate or reduce the overall frequency or
> > probability of collisions generated by the hash.
>
> No. But it makes it impossible for the attacker to know the hash
> function.

I was pretty sure someone said the hash function was known.

> > So, the probability that the shifted set
> > collides is the same as the unshifted set. If collisions are occuring
> > at the same rate and those collisions are causing some problem, all
> > the attacker has to do is run the entire input set until he or she
> > finds alternate collisions. Of course, the input set is comprised of
> > limited range character data. So, shifting may reduce collisions
> > overall (or may increase collisions), but it won't change the frequency
> > or probability that collisions will occur. I.e., some collisions are
> > still likely to occur.
>
> Hash collisions per se are not the problem. The problem is that the
> attacker deliberately creates a lot of colissions that end up in exactly
> the same bucket. And then asks for the values in that hash table (which
> is really a list now). That takes too long, so the server is having
> troubles responding in time.
>

Once in the same code for the collision bucket, XOR the original string with
a second secret. Hash the second XOR'd version of the string. Hopefully,
that will generate few or no collisions for the strings in that particular
bucket list.

Alternately, you could also use two different hash functions, or multiple
salt's per string with the same hash function, etc.


Rod Pemberton

[Rod Pemberton]

"Bernd Paysan" <bernd....@gmx.de> wrote in message

news:2093985.0...@sunwukong.fritz.box...

> Rod Pemberton wrote:
> > But, I don't see how any of this is that much different from Forth.
> > Forth
> > has a number of problems that can be exploited too. Allowing users to
> > directly access the control-flow stack via >R R> R@ allows for a
> > variety
> > control-flow attacks. This is much easier to do in Forth than in C.
>
> That's silly. If you allow an attacker to compile arbitrary Forth code
> while running the program, he won't need to use control-flow tricks to
> gain control.

The same is true of C.

You've changed the meaning of "gain control" above from that below. Above,
you mean to gain control in any sense, but below you mean in the sense of
taking control away from an operating system or application.

> The point in C is that you can gain control by simply
> having an unexpectedly large field somewhere in a file
> or an input stream, and boom, your program goes astray.

That's true for C only if someone made a coding mistake, or uses gets(). If
coded correctly, that doesn't happen, except for gets().

Forth has unbounded user input too: KEY. Forth uses addresses to identify
buffers and code: PAD, address returned by words created by VARIABLE etc.

Anton just complained about function pointers in C being abused. E.g., how
is ' (tick) any different from a function pointer in C?

I'm clearly not familiar with all of Forth, and especially not ANSI Forth.
However, it seems to me that Forth has almost identical issues to C and a
few more.

> > ALLOTing negative quantities could allow for dictionary attacks. Use
> > of ' (tick) returning the execution address of dictionary words could
> > allow for a
> > dictionary attacks too. Use of ! (store) without ALLOT or , (comma)
> > into the dictionary could allow for executable code to be stored and
> > "hidden" there temporarily and therefore go undetected.
>
> And you allow input from unknown origin to do all these things?
>

If it's interpreted Forth, how do you not?

If it's compiled Forth and the end user has access to the compiler, how do
you not?


Rod Pemberton

[Rod Pemberton]

"Bernd Paysan" <bernd....@gmx.de> wrote in message

news:2000935.V...@sunwukong.fritz.box...
...

> which aren't prone to off-by-one errors like C's
>
> for(i=0; i<n; i++) {
> ...
> }
>
> statement

C's for() statement is not off-by-one. Who types the "i=0" and "i<n"? The
programmer does.

> (many people write "i<=n", because they count from 1..n,
>

Programmer's who expect 1...n when coding 0...n by using "i=0" and "i<=n"
are off-by-one. Those who want 1...n should do:

for(i=1; i<=n; i++) {
...
}

> [...] but in fact, C counts from 0..n-1).

That's not fact at all. C's for() doesn't count.

You're thinking of C's arrays which start indexing at zero. Some
programmers have mental problems understanding that the indexing doesn't
start at one.

But as for for(), it's the programmer who controls all aspects of for()'s
start and stop conditions. The programmer can select exactly what they
want:

0 ... n-1 i=0; i<n
0 ... n i=0; i<=n
1 ... n i=1; i<=n
1 ... n-1 i=1; i<n
x ... y i=x; i<=y
etc.

The third argument can be set to do all sorts of complex stuff, or simple
increment and decrement.


Rod Pemberton

[Paul Rubin]

Bernd Paysan <bernd....@gmx.de> writes:
> C somewhat has NPEs, too, through signals and setsigjmp. C's exception
> handling is not really up to date ;-).

Well, it's the null pointer dereference that causes the problem; what I
was getting at about Java NPE's is that Java also has null pointers
(though it handles them with exceptions instead of undefined behavior).

> Lisp-like languages always had a
> NIL thing, which wasn't quite the same as a null pointer.

Right, and that causes hassles and crashes all the time. It's almost as
bad as a null pointer. It's very common in Lisp programs for programs
to crash because they got nil when expecting a non-nil value. The
Python equivalent is None and there's something like it in Ruby.

The most common Haskell error of that sort is when you try to examine
the first element of a list that is unexpectedly empty. You get
something like an NPE. But Haskellers don't say "ok, this is the
Haskell equivalent of NPE, just avoid it through vigilance". They hate
the phenomenon and are constantly trying to invent ways to make it
impossible, with varying results.

> Yes, but that are sorted indices, which remain sorted all the time, so
> all you need is to have a insert and delete operation into them which
> isn't costly.

What's a non-costly way of inserting or deleting an element into a
sorted index? We're back to balanced trees, I think.

> You might use a B-tree or some similar data structure to keep these
> indices sorted, but you don't actually use them to search for elements,
> because the hash is faster.

Hmm, yeah, you could probably save some cycles that way in some
situations, though it may be a premature optimization a lot of the time.

> The small-N priority queue has a very small constant overhead, and
> very small code size, so it is better for small Ns than a binary heap.

Messing with the queue typically won't be a significant cpu burner when
N is small, so optimizing for that case is again often likely to be
premature. Binary heaps are likely to be pretty fast even for small N
anyway. I agree balanced trees would likely have significantly worse
overhead.

[Bernd Paysan]

Rod Pemberton wrote:
> Can C functions be made which work for novices and idiots? Yes.

But K&R didn't. However, there are idiots who don't understand why
K&R's ideas were stupid.

>> [...] and these buffer overflows even allow you to overwrite your
>> return address, which is the common attack vector.
>
> I mentioned this already. I'll repeat. That's not always true. It's
> true for *most* C implementations.

That's what's relevant. You can even have a "strong C" which does check
buffers for you, even though normal C doesn't. The pointers of such a C
are a bit weird, or you use segments like AS/400.

>> You can't do that in Forth for two reasons:
>>
>> a) The return stack is in a separate memory region, ideally guarded
>> by unmapped pages (as in Gforth).
>>
>> b) your buffer writing words aren't prone to overflow as in C.
>>
>
> Except for gets(), C isn't prone to overflow.

And strcat and sprintf, and and and.

> So, Forth doesn't have KEY ... ?

KEY returns a single value, on the stack.

> Are you saying I can't place KEY in a LOOP and C, (c-comma) until I
> consume all dictionary space and maybe space beyond that?

Yes, in Forth you are entitled to shoot yourself into your foot.

> Are you saying I CMOVE> doesn't copy into a buffer of unknown space
> just like C's strcpy()?

Well, with CMOVE>, the programmer needs to know in advance how many
bytes to copy. With strcpy, you don't know in advance, you only know
the two pointers.

I know that it is difficult to understand how much C is wrong, so
difficult that people who wanted to fix the problems of strcat came up
with strncat. strncat transfers up to n bytes from the source to the
end of the string at dest. Well, you don't actually know where the end
of that string actually is, so strncat is not that helpful. It would
have been *much* better if strncat had specified the maximum buffer size
of the dest buffer. Therefore the advice to use strncat is:

strncat(dest, src, sizeof(dest)-strlen(dest)-1)

Can you remember that, including the additional -1? This sort of
stupidity is a recipie for disaster.

strncpy is also stupidly designed to fill up the entire buffer with
zeros. WTF? As usual, people now depend on this stupid behavior, so
it's difficult to change...

> CMOVE> knows neither. CMOVE> knows the source buffer length, but
> *not*
> the destination. The destination size is not one of CMOVE>'s
> parameters.

CMOVE>'s destination size is equal to CMOVE>'s source size. Unlike
strncat, which has a source size specified, but not a destination
size...

> This is no different from strcpy() in C which Anton just
> decried as one of
> C's most horrid problems... Is CMOVE> one of Forth's most horrid
> problems?

Not at all. Well, we use MOVE nowadays, because manually checking for
which direction to move data hasn't been such a good design decision.

>> Insane is
>>
>> c) neither, which is why this language is called C ;-).
>>
>
> You're clearly not familiar with C's functions.

Or maybe you are not understanding the problem.

> C's string and memory
> functions either 1) know the source buffer size or 2) know the size of
> the string being copied.

No, they figure it out as they go. The problem with C's functions is
that what amount of data they actually move is a surprise to the
programmer, unless he computes it with strlen() before.

> What they don't generally know is the
> destination buffer's size.

Which actually is what they should know.

> Given CMOVE> etc, I don't see how that is any different from Forth.

This is because you don't understand. All Forth words that copy data
have a specification how much data they copy (at most). READ-LINE (the
equivalent to gets), ACCEPT, MOVE, etc.

> If the attacker knows you're using XOR, all he has to do is generate
> "secret" strings until hashes for a couple other input strings match.
> You have to keep the hash values secret also.

Yes, of course. That's no problem, as the attacker only can feed data
into the hash, but has no way to closely examine the hash.

>> Yes. And how does he know that they match?
>
> He already knows what they are:
> "... if the attacker has the hash values for the host under attack
> ..."

This is not the attack we are looking at. The attacker does not have
these values.

>> The point of these hash attacks is to fill the hash with single,
>> pretty long chain, and then use the degenerated performance of that
>> hash to slow down the machine under attack.
>
> Why would he use the machine under attack to generate the hash values?

Because *that*s the attack vector. Come on, I'm really getting bored
now. I'm talking about *this* exploit:

https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4885

> He knows the hash function.

No, he woudn't, because he doesn't know the secret XOR value.

> I'm assuming he knows the hash values too.
> He can use any machine to generate more hash values.

It isn't fun to discuss with you, because you are always completely
missing the point.

[Bernd Paysan]

Rod Pemberton wrote:
> Forth has unbounded user input too: KEY

KEY is definitely bounded to return exactly *one* key input.

[Bernd Paysan]

Paul Rubin wrote:

> Bernd Paysan <bernd....@gmx.de> writes:
>> C somewhat has NPEs, too, through signals and setsigjmp. C's
>> exception handling is not really up to date ;-).
>
> Well, it's the null pointer dereference that causes the problem; what
> I was getting at about Java NPE's is that Java also has null pointers
> (though it handles them with exceptions instead of undefined
> behavior).

That's what you get in a POSIX environment with a signal handler and
corresponding setjmp: defined behavior, even in C. Or in Gforth, where
a 0 @ responds with a -9 throw.

>> Yes, but that are sorted indices, which remain sorted all the time,
>> so all you need is to have a insert and delete operation into them
>> which isn't costly.
>
> What's a non-costly way of inserting or deleting an element into a
> sorted index? We're back to balanced trees, I think.

Yes.

>> You might use a B-tree or some similar data structure to keep these
>> indices sorted, but you don't actually use them to search for
>> elements, because the hash is faster.
>
> Hmm, yeah, you could probably save some cycles that way in some
> situations, though it may be a premature optimization a lot of the
> time.

If your have a million entries, your hash query is in the order of 20
times faster than your balanced binary tree. Most data bases have much
more selects than inserts, so a faster select is a good idea.

As my current "larger" project is net2o, I'm thinging about the
following situation: You have a trillion objects (files, images),
indexed by unique identifiers. You now want to query your distributed
database for the whereabout of one of these objects. Distributed as in
worldwide, i.e. the worst case timing for one single operation is in the
few hundred millisecond range. I'd use a DHT, and a secure hash as
unique identifier. I'm definitely sure I don't want a b-tree for that.
I'm also quite sure I don't want any total order over the objects, only
over small subsets of them.

>> The small-N priority queue has a very small constant overhead, and
>> very small code size, so it is better for small Ns than a binary
>> heap.
>
> Messing with the queue typically won't be a significant cpu burner
> when N is small, so optimizing for that case is again often likely to
> be
> premature. Binary heaps are likely to be pretty fast even for small N
> anyway. I agree balanced trees would likely have significantly worse
> overhead.

I've written a binary heap now, it is considerably more code than the
O(n) code. I'd like to make a few benchmarks, before I post
comparisons. The main source of bugs was that all more detailed
descriptions count from 1..n, while Forth of course counts from 0..n-1.

[Rod Pemberton]

"Bernd Paysan" <bernd....@gmx.de> wrote in message

news:3906156.Y...@sunwukong.fritz.box...

> Rod Pemberton wrote:
> > Can C functions be made which work for novices and idiots? Yes.
>
> But K&R didn't. However, there are idiots who don't understand why
> K&R's ideas were stupid.

IMO, their ideas weren't and aren't. E.g., they studied counted strings in
a number of languages prior to selecting terminated strings for C, which
their B language already used. One of their papers describes why. Their
papers, and also Thompson's, discuss other differences too, and the
rationale behind their decisions.

> > So, Forth doesn't have KEY ... ?
>
> KEY returns a single value, on the stack.
>
> > Are you saying I can't place KEY in a LOOP and C, (c-comma) until I
> > consume all dictionary space and maybe space beyond that?
>
> Yes, in Forth you are entitled to shoot yourself into your foot.

Are you now agreeing that C, (c-comma) is a "buffer writing word" which
_is_ "prone to overflow"?

> > Are you saying I CMOVE> doesn't copy into a buffer of unknown space
> > just like C's strcpy()?
>
> Well, with CMOVE>, the programmer needs to know in advance how many
> bytes to copy.

Perhaps, I should've compared with strncpy() instead of strcpy(). It's
closest to CMOVE> . That comparison would've been more accurate. But,
strncpy() also copies into a buffer of unknown size, just like CMOVE>.

> With strcpy, you don't know in advance, you only know
> the two pointers.
>

That's not true. strcpy() is not for non-strings. So, you can call
strlen(), if you don't already have the size from the declaration, a
#define, or malloc().

> I know that it is difficult to understand how much C is wrong, so
> difficult that people who wanted to fix the problems of strcat came up
> with strncat.

Did you mean strlcat() and strlcpy()? They were created to fix supposed
problems with C's functions.

strncat(), strncpy(), strncmp() are a part of ANSI C (1989/90). They
actually pre-date ANSI C though. I'd have to check to see if they are a
part of K&R C, or came somewhere inbetween, or were even earlier.

> strncat transfers up to n bytes from the source to the
> end of the string at dest. Well, you don't actually know where the end
> of that string actually is, so strncat is not that helpful. It would
> have been *much* better if strncat had specified the maximum buffer size
> of the dest buffer. Therefore the advice to use strncat is:
>
> strncat(dest, src, sizeof(dest)-strlen(dest)-1)
>

Wow, someone made that difficult...

If you know dest is sufficiently large and where n<=strlen(src), then:

strncat(dest, src, n);

Generally, n is less than strlen(src), i.e., n<strlen(src). Why? Well, if
n equals strlen(src), i.e. n=strlen(src), then you use strcat().

Of course, you will need to make sure 'dest' is terminated, if you intend to
use it as a string:

dest[MAX]='\0'; /* MAX is a #define for dest's maximum size */

The key is making sure dest is sufficiently large. This is easy to do
except for unlimited gets() input. Most input functions limit what they
read, like the 'n' string functions.

> strncpy is also stupidly designed to fill up the entire buffer with
> zeros. WTF? As usual, people now depend on this stupid behavior,
> so it's difficult to change...
>

By "entire buffer" do you mean 'dest'? If so, then that's not correct.
strncpy() only zero pad's if the strlen() of 'src' is less than the third
argument which I've called 'n'. For that situation, strncpy() pad's dest
with zero's upto 'n'. The size of 'dest' may be larger or smaller than 'n'.

E.g., (all unconfirmed)

dest="dddddddddd" for 10 chars
src="ssssssssss" for 10 chars
n=5
10>=5 so strncpy() won't zero pad
strncpy will only copy 5 of 10 chars from src
strncpy() result should be: "sssssddddd"

dest="dddddddddd" for 10 chars
src="sssss" for 5 chars
n=5
5>=5 so strncpy() won't zero pad
strncpy() result should be: "sssssddddd"

dest="dddddddddd" for 10 chars
src="sss" for 3 chars
n=5
3<5 so strncpy() zero pad's the difference
strncpy() result should be: "sss00ddddd" - using '0' for '\0'

dest="ddddd" for 5 chars
src="ssssssssss" for 10 chars
n=7
10>=7 so strncpy() won't zero pad
strncpy() result should be: "sssssss"
'dest' buffer overflowed by 2


Yes, I looked at 'the manual' to construct those examples. I mostly use
non-'n' string functions, without issue. 'the manual' is Harbison and
Steele's "C: A Reference Manual", 3rd ed., 1991.

> > CMOVE> knows neither. CMOVE> knows the source buffer length, but
> > *not* the destination. The destination size is not one of CMOVE>'s
> > parameters.
>
> CMOVE>'s destination size is equal to CMOVE>'s source size.

Where do you get that?

The size of the destination buffer is not known by CMOVE>. The _user_
specifies how much to copy. The size of the destination buffer is not
passed to the Forth words. It's unknown. I.e., the user can overflow the
destination buffer. E.g., if the destination buffer is 50 characters and
you tell CMOVE> to copy 100 characters, buffer overflow ...

There is nothing in Forth-94 saying CMOVE> allocates the destination buffer
based on the size passed to it. In fact, if CMOVE> did allocate the
destination buffer, it couldn't be passed a pointer for 'caddr-2' since
there is no way to determine if sufficient free space exists at 'c-addr2'.
Secondly, allocating a buffer for 'c-addr2' would break historical usage of
CMOVE>.

> >> Insane is
> >>
> >> c) neither, which is why this language is called C ;-).
> >>
> >
> > You're clearly not familiar with C's functions.
>
> Or maybe you are not understanding the problem.
>

I learned C in the early 90s. Excluding gets(), I've never seen this
problem. I've read that the problem exists. I've seen a variety of
solutions for the problem. I'm now getting an earful from Forth programmers
about the problem... Now, I feel much like Ms. Rather, i.e., saying
something has never been needed or a cause of any real problem in decades of
Forth...

> > C's string and memory functions either 1) know the source buffer
> > size or 2) know the size of the string being copied.
>
> No, they figure it out as they go. The problem with C's functions is
> that what amount of data they actually move is a surprise to the
> programmer, unless he computes it with strlen() before.
>

The size is always known. Where is the "surprise"?

I went over this previously. A #define, a declaration, a return from
malloc(), sizeof() or strlen() are all able to provide the needed
information.

> > What they don't generally know is the
> > destination buffer's size.
>
> Which actually is what they should know.
>

No. If programmed correctly, there is no need. The buffer will be
sufficiently large to handle what is written to it.

> > Given CMOVE> etc, I don't see how that is any different from Forth.
>
> This is because you don't understand. All Forth words that copy data
> have a specification how much data they copy (at most).

How is that any different from strncpy(), strncat(), strncmp() which you
just claimed are problems? Those C functions have a specification of

how much data they copy (at most).

> READ-LINE (the equivalent to gets), ACCEPT, MOVE, etc.

Those and CMOVE> and CMOVE all have the same issue as C's strncpy() etc.

> Come on, I'm really getting bored
> now. I'm talking about *this* exploit:
>
> https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4885
>

Well, that's new. I admit jump into the thread in the middle, but I can't
find any mention of that previously in this thread by you. So, how would I
have known that? Did someone else bring it up?

I don't see why the double hash method I mentioned at the end of the last
post wouldn't resolve their issue, unless they require a single hash value
for some reason...

They stated that an O(n) response instead of O(1) is a result of the
collisions. They also state that substrings and meet-in-the-middle methods

were allowing the attacker to create collisions. So, for both of those
reasons, it's clear to me that their problem is the need of a hash function
with fewer collisions. I already mentioned that. Or, they need to change
something with their "salt" or XOR method, or whatever they're using, so
that substrings and meet-in-the-middle methods don't work. Concatenating
short strings into larger ones is simple to do. That might prevent the
substring problem. I think a "salt" definately would. However, it seems
really strange to me that a meet-in-the-middle method - without knowing
exactly what that means - would work. Generally, hash functions generate
values which don't correlate nicely with the input or with anything. The
values appear widely distributed, widely spaced, and "randomly" distributed.
An exception would be a perfect hash. So, how does someone generate strings
which they can use to create meet-in-the-middle hash collisions?

What hash function do they use?


I'm not sure if these are the type of hash functions they need, but these
two public hash functions are good:

Austin Appleby's MurmurHash2
Bob Jenkins' hashlittle() from lookup3.c

Most other publicly (about 50) available hash functions are not good:
https://groups.google.com/group/comp.lang.misc/msg/a37141ec795b97fb


Rod Pemberton

[Andrew Haley]

Bernd Paysan <bernd....@gmx.de> wrote:

> Anton Ertl wrote:
>> I have read that mergesort is faster than quicksort, but more
>> memory-consuming, and that glibc's qsort uses mergesort for
>> small-enough arrays, and quicksort for the larger ones (probably with
>> mergesort again for the small-enough sub-arrays).
>
> Not sure if that's true. Quicksort is in-place sorting, which means it
> consumes less memory. Less memory means also less bandwidth required,
> and better use of the cache hierarchy. I've read complaints that
> quicksort's memory access pattern is "wrong", while mergesort gets it
> "right", but both do unit-stride sequential access, and the actual data
> (strings) pointed by these pointers is random access for boths.
> Quicksort has sequential access in reverse direction on one end, which
> might hurt (prefetch algorithms often assume that you go upwards). The
> only unpredictable access in improved quicksort is the random pivot
> access (for obvious reasons it is unpredictable).
>
> For quicksort, you need two running pointers, for mergesort, three.
> Otherwise, the number of operations per step are quite similar.

I think that's not really true. The inner loop can be reduced to

repeat
j <- j - 1
until A[j] <= pivot

repeat
i <- i - 1
until A[i] >= pivot

if i < j
exchange A[i] <-> A[j]
else
exit

We don't have to check the indices i and j while scanning: this is why
quicksort is fast.

Andrew.