Re: Data structure design again

> 2013/12/11 Jan Wielemaker <[email protected]>
>
>> On 12/11/2013 05:52 AM, Richard A. O'Keefe wrote:
>>
>>> Someone is bound to freak out at the idea of representing
>>>
>>
>> +1
>>
>>
>>  [:x | x + 1] as block(lambda([x],[],call(+,var(x),[integer(1)])))
>>> but I've tried it without the outer discriminator and it makes
>>> writing the code so error prone it's not worth it.  In any case,
>>>
>>
>> Languages are in my opinion always a compromise between the human and
>> the machine. Humans like something concise and intuitive.

But we are not designing a language for people!
Smalltalk was designed long ago and I'm not trying to change it.

This is the *ABSTRACT SYNTAX TREE* we are talking about,
*NOT* a source language for people to enter.

>> Having to write
>> "integer(1)" is a lot of work as well as hard to read as you have to
>> process all this text and brackets.

"Having to write integer(1)" is a gross misunderstanding.
THIS IS THE OUTPUT OF A PARSER, not the input to it.

> It also makes it hard to give a
>> good layout to larger structures.

Not in the least.  Remember, THIS IS AN INTERNAL *PROCESSING*
FORMAT, NOT SOMETHING PEOPLE ACTUALLY READ OR WRITE.

portray(nil) :-
    write('nil').
portray(false) :-
    write('false').
portray(true) :-
    write('true').
portray(integer(I)) :-
    write(I).
portray(float(F)) :-
    write(F).
portray(symbol(S)) :-
    write('#'), write(S).
portray(string(S)) :-
    write('"'), write(S), write('"').
portray(array(_)) :-
    write('#(...)').
portray(bytes(_)) :-
    write('#[...]').
portray(const(X)) :-
    print(X).
portray(var(V)) :-
    write(V).
portray(if(E,B1,B2)) :-
    write('('),
    print(E),
    write(' ifTrue: '), print(B1),
    write(' ifFalse: '), print(B2),
    write(')').
portray(while(B1,E,B2)) :-
    write('('),
    B1 = lambda(Vs,Es,Ef),
    append(Es, [Ef], El),
    print(lambda(Vs,El,E)),
    write(' whileTrue: '),
    print(B2),
    write(')').
portray(let(B,[])) :- !,
    write('('),
    print(B), write(' value'),
    write(')').
portray(let(B,Es)) :-
    write('('),
    print(B),
    (   member(E, Es),
        write(' value: '), print(E),
        fail ; true
    ),
    write(')').
portray(call(F,E,[])) :- !,
    write('('),
    print(E),
    write(' '),
    write(F),
    write(')').
portray(call(F,E,[E2])) :- !,
    write('('),
    print(E),
    write(' '), write(F), write(' '),
    print(E2),
    write(')').
portray(call(F,E,Es)) :-
    write('('),
    print(E),
    write('perform: #'), write(F),
    (   member(E, Es),
        write(' with: '), print(E),
        fail ; true
    ),
    write(')').
portray(block(B)) :-
    print(B).
portray(lambda(Vs,Es,E)) :-
    write('['),
    (   member(V, Vs),
        write(':'), write(V), write(' '),
        fail ; true
    ),
    (   Vs == [] -> true
    ;   write('| ')
    ),
    (   member(S, Es),
        print(S), write('. '),
        fail ; true
    ),
    print(E),
    write(']').

It should be obvious how to combine that with the pretty-printer
of your choice.  (Mind you, the documentation of pretty-printing
libraries is generally so bad that it's hard to plug *anything*
into them.)

Load that into SWI Prolog, and

?- E = block(lambda([x],[],call(+,var(x),[integer(1)]))), print(E).
[:x | (x + 1)]

Remember the mantra:

    AN I/O FORMAT IS NOT A PROCESSING FORMAT IS NOT AN I/O FORMAT.

Processing formats *shouldn't* be designed to let human beings
read and write large amounts of the stuff because human beings
*shouldn't* be reading and writing large amounts of the stuff.
You use parsers to convert human-oriented stuff into processing
formats (source code => abstract syntax trees) and unparsers
to convert processing formats to human-oriented stuff.

The cuts in the code above exist *only* because of non-uniform
quirks in Smalltalk syntax.  (Given a valid input, the output
here is valid Smalltalk.)  For example, the syntax of blocks is

    block --> '[' {statement '.'}* [expression] ']'
            | '[' (':' argument)+ '|' {statement '.'}* [expression] ']'

where the '|' must be present if and only if there is at least one
argument.  The *processing* format does not include that weirdness,
making it much easier to *process*.



>> Well, we already knew we disagree on these things when discussing mark
>> down ...

There was an interesting discussion of Markdown in the blog
of the science fiction author Charles Stross.  The conclusion is
that Markdown is *way* better for writing than Microsoft Word
but there are *way* too many incompatible dialects of it.

>> All I want to achieve is to reduce the number of cases where we
>> _force_ people to use this verbose syntax to define their data or DSL
>> representation.

You are once again confusing an *I/O FORMAT* (what people read and
write) with a *PROCESSING FORMAT*.

I am *ONLY* talking about *PROCESSING* formats.

>>  the *proportional* overhead is slight.
>>>
>>
>> For atomic data about a factor 3.

Remember, I was *specifically* talking about the example
block(lambda([x],[],call(+,var(x),[integer(1)]))),
which is an unusually small block.

Unfortunately, the code I wrote for determining the size of a term
has been broken by SWI 7.  However, the code I wrote for SWI  tells
me that

    FOR THE EXAMPLE I SPECIFICALLY REFERRED TO,
    wrapping block(...) around the lambda(...) term
    increased its size by

        TEN PERCENT.

As for atomic data, the parser caches these things,
so that all occurrences of integer(1) are the *same* term,
so the space overhead is 3*0 for a total of 0.

> The leafs often atomic and that is
>> where most of the space goes.

Which is why it pays for the parser to cache them so
that there is no duplication.  As it happens, the parser
caches
 - all numbers
 - all strings
 - all symbols
so the amortised space overhead is *ZERO*.

Unfortunately it is impossible to express this in the type language.

Before you say "but oh, people aren't going to factor out all
occurrences of integer(1)", remember that I am talking specifically
and only about *PROCESSING* formats.