News for hackers. Stuff that matters.
Re:Programming Algorithms in Lisp: Data Structures by OskarS on Wednesday August 07, 2019 @03:06AM (#20632547)
> To implement an arbitrary data structure, these languages provide a special mechanism called records, structs, objects, etc. The proper name for it would be "tuple". It is the data structure that consists of a number of fields each one holding either a primitive value, another tuple or a pointer to another tuple of any type. This way a tuple can represent any structure, including nested and recursive ones. In the context of type theory, such structures are called sum types

Wait, what? Tuples aren't sum types, they're product types. Like, they're the "cartesian product" of some other types. A sum type would be like a tagged union (or Rust enum) where something can be either one type or the other. I haven't studied a lot of algebraic type theory, but Wikipedia agrees with me on that point [0]

Seems like a fairly elementary mistake in an article of this kind...

EDIT: also, this, a few paragraphs down:

> Moreover, in C++ the pass-by-reference has two flavors: pass the pointer (a common approach) and pass by what's actually called a reference, which is a syntax sugar over pointers that allows accessing the argument with non-pointer syntax (dot instead of arrow)

Pass-by-reference in C++ is most certainly not just syntactic sugar for passing in a pointer. A compiler may implement it that way (or it may not), but it's totally wrong to say that passing by reference is just syntactic sugar so you don't have to use arrow notation. The most obvious differences is that a reference can never be null, it can't be changed to point to some other object, you can't do pointer arithmetic to it and you always dereference it when use it. Also: in idiomatic C++, "passing by reference" is far more common than "passing by pointer".

I'm going to stop reading this article now. I don't have a lot of faith that this person really knows what they're talking about.

[0]: https://en.wikipedia.org/wiki/Algebraic_data_type

Re:Programming Algorithms in Lisp: Data Structures by vseloved on Wednesday August 07, 2019 @03:41AM (#20632694)
> Wait, what? Tuples aren't sum types, they're product types.

Thanks for the correction. As I wrote in the introduction, there will be some errors in these beta-version chapters that are published on the blog (as I, obviously, don't have correctors and reviewers), so I'm thankful to all who notice and point those.

> it's totally wrong to say that passing by reference is just syntactic sugar

OK, I'd say that it's still syntactic sugar with some benefits :) But I don't agree that it's totally wrong. Some of the things you mentioned are just side-effects (that you can't do pointer arithmetic or pass a null pointer. Actually, it seems that you can with some jiggling: https://stackoverflow.com/questions/8571078/pass-by-pointer-...). The point I wanted to make is that pass-by-reference is mostly the same thing. It's, actually, quite a confusing topic (as are many C++ solutions) that was not properly presented to me when I stduied it in school, and this book neither tries to present it, but I had to, at least, mention it here as I was talking about different passing styles.

Re:Programming Algorithms in Lisp: Data Structures by OskarS on Wednesday August 07, 2019 @03:58AM (#20632770)
It's not mostly the same thing, the difference is pretty significant both in practice and in a "type-theoretic" sense. I get what you're saying, that "pass by reference" and "pass by pointer" are both methods to pass an object into a function without copying, but they are very different. An article like this where the whole point is to talk about these things at a more fundamental level, it is bad to claim that they are.
Re:Programming Algorithms in Lisp: Data Structures by vseloved on Wednesday August 07, 2019 @04:13AM (#20632818)
The point of the article is not to talk about low-level specifics of some language, apart, from, maybe, Lisp sometimes. But, surely, not C++ (although, if you could provide a link with a good and accessible explanation of the differences of the 2 styles I'd add it as a reference for further reading). Stil, I don't see that fundamental difference that you mention. If the differences originate from the points that you listed in the original comments can you, please, make the link more explicit? I understand pass-by-reference as being a slightly higher-level and safer C++ alternative to C's direct pointer-based style. But, surely, I may be missing something. But, it seems that the people who answered the SO question I linked are also missing it. For example, here's a quote: "Basically, references and pointers are not very different from an implementation point of view, the main (and very important) difference is in the philosophy: a reference is the object itself, just with a different name."
Re:Programming Algorithms in Lisp: Data Structures by pjmlp on Wednesday August 07, 2019 @04:45AM (#20632954)
Here is pass by reference and pass by pointer in Pascal.

    type

    Point = record
        x, y : integer
    end;

    procedure ByPointer(p : ^Point);
    begin
        p^.x := 12
    end;

    procedure ByReference(var p : Point);
    begin
        p.x := 12;
        p.y := 33
    end;

    procedure example
    var
      p : Point
    begin
       p.x := 23;
       p.y := 28;
       WriteLn('The point is ', p.x, ' ', p.y);

       ByPointer(@p)
       WriteLn('The point is ', p.x, ' ', p.y);

       p.x := 23;
       p.y := 28;
       WriteLn('The point is ', p.x, ' ', p.y);

       ByReference(p)
       WriteLn('The point is ', p.x, ' ', p.y);
    end;

Actually the concept is already exposed in Algol, a couple of years before C was even an idea.
Re:Programming Algorithms in Lisp: Data Structures by vseloved on Wednesday August 07, 2019 @04:55AM (#20632991)
good point, so, here, it is exactly syntax sugar as, unlike in C++, nothing else except syntax is different from the pointer-based version. Not to mention that, in the article, I was mentioning the general concept that has one (and single) variant, in C and Java, and 2 in Pascal or C++
Re:Programming Algorithms in Lisp: Data Structures by pjmlp on Wednesday August 07, 2019 @07:19AM (#20633668)
Actually it is more than syntax sugar.

I should have provided a better example, this is impossible to do languages like Java and in C requires explicit double indirection to fake how reference types work.

    type
        Point = record
            x, y : integer
        end;


    procedure ByPointer(p : ^Point)
    begin
        New(p);
        p.x := 12
    end;

    procedure ByReference(var p : ^Point)
    begin
        if p <> nil then
           Dispose(p)
        end;
        New(p);
        p^.x := 12;
        p^.y := 33
    end;

    procedure example
    var
      p : ^Point
    begin
       New(p);
       p^.x := 23;
       p^.y := 28;
       WriteLn('The point is ', p^.x, ' ', p^.y, ' at ', p);

       ByPointer(p)
       WriteLn('The point is ', p^.x, ' ', p^.y, ' at ', p);

       p^.x := 23;
       p^.y := 28;
       WriteLn('The point is ', p^.x, ' ', p^.y, ' at ', p);

       ByReference(p);
       WriteLn('The point is ', p^.x, ' ', p^.y, ' at ', p);  (* here p will point to the one allocated in ByReference *)
       Dispose(p);
    end;
Re:Programming Algorithms in Lisp: Data Structures by jstimpfle on Wednesday August 07, 2019 @08:43AM (#20634145)
> Actually it is more than syntax sugar.

Where? I see only syntax sugar. The catchy phrase from the Google C++ style guide is stuck in my head: references have value syntax but pointer semantics. And that's it (and that's why I think references are mostly a bad idea).

> C requires explicit double indirection

Your 2nd example is no different, it's still just "indirection" (value syntax but pointer semantics!). If what you are indirecting is itself a pointer type (as in your 2nd example), then yes, there technically is a "double indirection", but that's besides the point.

> impossible to do in languages like Java

actually, "in every memory safe language there is". You can do this in Pascal because Pascal is really just C-style systems programming. With a few features like references and ARC that pretend otherwise but quickly fall flat on their head.

Re:Programming Algorithms in Lisp: Data Structures by pjmlp on Wednesday August 07, 2019 @10:36AM (#20635052)
Ok I might have to give in with the syntax sugar part, but safety?

Here is my example in C#. So now C# is unsafe?

    class Point
    {
        public int x, y;
    }


    static class CSharpIsUnsafe {
        static void ByPointer(Point p)
        {
            p = new Point();
            p.x = 12;
        }

        static void ByReference(ref Point p)
        {
            p = new Point();
            p.x = 12;
            p.y = 33;
        }
        
        public static void Main(string[] args)
        {
           p = new Point();
           p.x = 23;
           p.y = 28;
           Console.WriteLn($"The point is {p.x} {p.y}");
           

           ByPointer(p)
           Console.WriteLn($"The point is {p.x} {p.y}");

           p.x = 23;
           p.y = 28;
           Console.WriteLn($"The point is {p.x} {p.y}");

           ByReference(ref p);
           Console.WriteLn($"The point is {p.x} {p.y}");
        }
    }
Re:Programming Algorithms in Lisp: Data Structures by jstimpfle on Wednesday August 07, 2019 @03:48PM (#20638180)
I guess it might very well be safe. I don't know C# very well, but I'd assume that ref is sort of a proxy that

1) under the hood stores an (object) reference to the lowest structural ancestor that is GC'ed, as well as an offset from that object to the ref'ed property.

2) is itself GC'ed

Escape analysis might in some cases optimize out the GC'ing of the ref, but that of course doesn't work if the ref does escape.

Something like that, but in any case it's something very different than the Pascal/C++ examples we've talked about.

Re:Programming Algorithms in Lisp: Data Structures by pjmlp on Wednesday August 07, 2019 @05:11PM (#20639127)
The generated code is similar as how a C++ compiler would do it.

Easy to check with VS Assembly visualizer or WinDbg alongside SOS.dll.

D, Ada, CLU, Mesa, Mesa/Cedar, Algol, PL/I, PL/S, PL.8, Delphi, Dylan, .NET, Swift, Oberon, Oberon-2, Component Pascal, Active Oberon, QuickBasic, Turbo Basic are just a couple of examples of languages allowing for pass by value and pass by reference, some of them also quite safe.

And then there is also call by name introduced alongside Algol.

Re:Programming Algorithms in Lisp: Data Structures by vseloved on Wednesday August 07, 2019 @04:24AM (#20632870)
And here's another quote from this very much upvoted answer (https://stackoverflow.com/a/596750/977052): "A reference can be thought of as a constant pointer (not to be confused with a pointer to a constant value!) with automatic indirection, ie the compiler will apply the * operator for you."