Implementation of linked list in Carbon

[pmqtt]

Hello folks,
I try to implement a linked list in carbon... For the reason, to check how powerfull is the language in current state...

But I find many hurdles by the implementation!

First, Carbon has no null or nil value. Ok, I have try to solve it with using choice and declare my own NIL...

choice Node{
    Item(NodeItem*),
    NIL
}

class NodeItem{
    var value:i32;
    var next: Node*;
}

But here is the problem, that is impossible. Because NodeItem or Node should be forward declared.
I think we should thinking about such problems and how to solve it.

Best regrads!

[jonmeow]

Carbon's equivalent for null will likely be Optional. See https://github.com/carbon-language/carbon-lang/blob/trunk/docs/design/README.md#pointer-types

Bear in mind that Carbon is still being built, and this won't work yet.

[freedxmgxd]

johmeow, I really like that's not null on Carbon, but how they will interpot with C++ that has null?

[cdmaczane]

Will Optional have overhead like it does in C++? Null is a pretty fundamental tool in systems code.

[pmqtt]

Overhead? You have in both cases to check is valid, or not ?

[jonmeow]

@freedxmgxd (sorry I missed this before):

I really like that's not null on Carbon, but how they will interpot with C++ that has null?

We'll have control over the interop boundary, so we'd likely use the rule of:

C++ T* <-> Carbon Optional(T*)
C++ T& <-> Carbon T*

Will Optional have overhead like it does in C++? Null is a pretty fundamental tool in systems code.

Normally std::optional is roughly a pointer internally. The underlying premise would be to special-case Optional(T*) within Carbon to remove overhead (e.g., even though T* isn't nullable, maybe we store null for this use-case). I think this is the kind of thing we'd do to get performance while still maintaining syntax.

[pmqtt]

Hi folks,
with the PR #2042 it is possible to implement Optional and this is how a simple chained list looks in Carbon. I think for the state Carbon currently has, it doesn't look bad.

package ExplorerTest api;

class ListElement{
    fn Create(value: i32)->ListElement{
        return {
            .element = Optional(i32).Create(value),
            .next = Optional(ListElement*).CreateEmpty()
        };
    }
    fn set[addr me: Self*] (value: Optional(ListElement*)){
        (*me).next = value;
    }
    var element: Optional(i32);
    var next: Optional(ListElement*);
}

class List{
    fn Create() -> List{
        return {.next = Optional(ListElement*).CreateEmpty() };
    }
    fn insert[addr me: Self*] (value: i32){
        if( not (*me).next.has_value() ){
            (*me).next = Optional(ListElement*).Create( heap.New(ListElement.Create(value)) );
            return;
        }
        var iter: Optional(ListElement*) = (*me).next;
        var node: auto = (iter.get());
        while((*node).next){
            iter = (*node).next;
            node = (iter.get());
        }
        var v : ListElement* = iter.get();
        var x: Optional(ListElement*) = Optional(ListElement*).Create( heap.New(ListElement.Create(value) ));
        (*v).set(x);
    }
    fn print[me: Self] (){
        var iter: Optional(ListElement*) = me.next;
        while(iter){
            var node: auto = *(iter.get());
            Print("{0}",node.element.get());
            var node_ptr: auto = iter.get();
            iter = node.next;
        }
    }
    fn clean[addr me: Self*] (){
        var head: auto = (*me).next;
        while(head){
            var tmp: auto = head;
            head = (*head.get()).next;
            heap.Delete(tmp.get());
        }
        (*me).next= Optional(ListElement*).CreateEmpty();
    }
    var next: Optional(ListElement*);
}

fn Main() -> i32{
    var list: List = List.Create();
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.print();
    list.clean();
    list.print();
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.print();
    return 0;
}

[xuanswe]

Hm, do you think the syntax Optional(T*) is too verbose?
What could be the reason not to have something "similar" to Kotlin: T??

[geoffromer]

Well, one reason Carbon doesn't have that syntax is that nobody has proposed it yet :-)

One potential concern I'd have is that it would mean we probably couldn't use postfix ? as a Rust-style error-propagation operator. That said, some folks have been arguing that if we have that, it should be a prefix operator anyway.

[xuanswe]

Thanks for the info!
I only mean a "similar" syntax because I don't know if there's already a meaning of ? in Carbon :-)