Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[milo christiansen]

The only time I find dynamic typing useful is in scripting languages. There it is mostly only useful to simplify the type system and allow using maps as sort-of objects and other little tricks that make the language simpler.

For any language that will be used for "real work" I want static types, that said I love the way Go allows you to declare a variable with an inferred type, it save a great deal of time (would you prefer "a := f()" or "var a []map[string]func(int, int) bool = f()"? Provided "f" returns a "[]map[string]func(int, int) bool" both are equivalent.)


I other news the parser for my new scripting language, Cobalt, has produced its first valid AST today! The VM is done, as is a simple assembler (used to test the VM). As soon as I test the parser/lexer some more it is time for the last piece, the compiler.

Cobalt is based on my earlier Lua VM and compiler, but it has lots of little differences such as 0-based indexing, a more C-like syntax, better OO simulation, etc.

And yes, Cobalt is dynamically typed.  It is an embedded scripting language after all...

[breadman]

To be fair, at least C's type system is more sane than Perl's.

What's wrong with Perl's type system?

To start with, it has one namespace for scalar values (numbers and strings), another for list values, another for hash values, another for subroutines, and a really goofy one for things like file descriptors.  You identify the namespace you're using through the use of sigils prefixing the name, namely $, @, %, and &.  Yes, that means you can have five different things all named "foo" (though the last one is traditionally upper-cased).  And in case you think it's hypothetical, consider that the built-in variables $+, @+, and %+ have different but related meanings, as do @INC and %INC; $_ and @_; $ARGV, @ARGV, and ARGV; $! and %!; etc.

Then, assignments and functions have contexts related to those types, and each type has odd conversion rules for when it gets used in an unexpected context.  Except that some functions check the type of their parameter instead, with different functionality depending on what gets passed in.  In some cases, these conversion rules can be deliberately invoked through such astoundingly evocative syntax as $#.

Oh, and namespaces are marked differently when taking an index into a list or hash.  Then, the sigil used identifies the context of the indexed value, while the bracket type identifies the namespace of the data structure.  I've used the wrong sigil more often than I can count.  Then there are scalar references to data structures, with their own indexing conventions and creation syntax.  The difference between parens and square brackets can bite you in entirely unexpected ways.

And last I checked, objects are "blessed" hashes, with their own brand of weirdness.  But that's about the point where I discovered that networking and I/O would break when moving a script from one computer to another, and decided to learn Python.

I have literally never, in all my years of coding, thought to myself "gee, I really wish I could store either a number or a fruit basket in the same variable"

I have.  Not long ago, for example, while dealing with a Json data structure.  I ended up with a whole bunch of nearly duplicated code, one set for objects and another for arrays, because the former uses strings as keys, and the latter uses numbers.

Come to think of it, I wouldn't want to be doing my current xpath work with static types, either.

But you're right that the cases of a variable holding a single type are far more frequent.  I wouldn't even mind marking the exceptions explicitly, as long as the compiler doesn't make me explicitly mark the cases that it could reasonably infer.

Module support, of course, would actually make C++ programs compile a lot slower. Because the whole point of that is that you don't have to include header files, so the compiler is going to need to examine all CPP files for all other CPP files to check whether some definition somewhere is used. So it becomes an O(n²) problem with the number of cpp files that you have.

At the linker stage, if it decides to make that optimization, sure.  But that's an optimization that could be skipped for development, making compilation quite a bit faster.  With the right language semantics, compiling a file doesn't need to look at any other file anywhere; that's why Python compilation is so fast that you don't even notice it.  Alternatively, one could require that a module only import symbols explicitly exported by an already-compiled module, but circular dependencies are occasionally convenient.

A language with fast compile times, no typing and no header files is actually sacrificing a lot of runtime performance for developer ease of use. C/C++ are the languages aimed at maximum performance, and will always be needed, at least to implement all the shitty languages

This, though, is a decent argument.  Granted, we already sacrifice some runtime performance for dynamic linking; the language semantics could have been implemented in a way that sacrifices just a bit more to add parameter type expectations and type sizes.  That would also make it easier to make libraries compatible with programs compiled against an older version.

Using explicit header files is needed to get the optimized compilation of C++ to happen in a more reasonable time (by minimizing the amount of data each module needs to know about during compilation).

Unfortunately, explicit header files all too often include far, far more information than the compiler needs to compile a given module, and lead the compiler to assume things about the imported symbols that may or may not be true if their implementation later gets changed, or even if they were compiled by a different compiler.

Dynamically typed arrays add a lot of overhead there, since every time a value is accessed it has to check "what the hell am I looking at", and it has to store type information along with your values. Every. single. access.

With a strongly typed language it just stores the raw data and it can safely assume what things are at runtime, since all of the details were set in stone at compile time. Which means more speed and less memory requirements.

That assumption underlies so many security flaws it's not even funny.  I'd prefer that my program crash at runtime than do the wrong thing.

The only time I find dynamic typing useful is in scripting languages. There it is mostly only useful to simplify the type system and allow using maps as sort-of objects and other little tricks that make the language simpler.

For any language that will be used for "real work" I want static types, that said I love the way Go allows you to declare a variable with an inferred type, it save a great deal of time (would you prefer "a := f()" or "var a []map[string]func(int, int) bool = f()"? Provided "f" returns a "[]map[string]func(int, int) bool" both are equivalent.)

I keep meaning to look into Go.  I also hear that it gets async right; Python had the opportunity to go down that route, but instead decided to go down a route of explicitly marking routines that could call something asynchronous somewhere in the tree, and keeping its blocking routines alongside the async ones.

I other news the parser for my new scripting language, Cobalt, has produced its first valid AST today! The VM is done, as is a simple assembler (used to test the VM). As soon as I test the parser/lexer some more it is time for the last piece, the compiler.

Cobalt is based on my earlier Lua VM and compiler, but it has lots of little differences such as 0-based indexing, a more C-like syntax, better OO simulation, etc.

And yes, Cobalt is dynamically typed.  It is an embedded scripting language after all...

Congratulations!  Is it compatible enough to drop into a project that already uses Lua?

[milo christiansen]

I keep meaning to look into Go.  I also hear that it gets async right;

If by async you mean incredibly easy multi-threading then yes, very much yes.

Congratulations!  Is it compatible enough to drop into a project that already uses Lua?

Uhm... No. For starters I wrote it in Go, which means embeding n other languages would be difficult at best, and the API is completely different from standard Lua. That said the API is similar to my existing Lua VM (also written in Go), so switching is only a minor headache rather than a major project

I would like to write a C version at some point, but that would mean I would need to write a garbage collector (something I would like to try, but have never done).

Writing scripting languages is one of my hobbies, but most of the time I go for exotic syntaxes and other "fun" things. This is the first time I wrote a language for serious use (not counting the Lua port anyway).

[Skyrunner]

I'm more worried that sometimes the code will decide to return some completely different type to the one you're normally getting. When the return value is based on external data (e.g. user input) that's also a security risk.

So the main criticisms are that it's slow, it's bulky, it's insecure, and it's fairly random. You have to take extra measures to be sure that the type you're getting is the one you want, e.g. wrapping JavaScript function calls that have to return a number in ParseInt(), which fairly much defeats the purpose of having dynamic types.

All the "Indeed!"

I like to cheat by appending a + to the function to coerce it to a number.

+returnPossiblyNumber()

[itisnotlogical]

My college is going to host a group of high schoolers, and my STEM club is going to have a table. I want to create a few interactive CS demos, and one of the ideas I had was a password cracker. Visitors come up with a password and the program tries to crack it.

How can I give a semi-realistic demonstration without explaining every little thing about how actual password cracking works?

[Reelya]

I'm more worried that sometimes the code will decide to return some completely different type to the one you're normally getting. When the return value is based on external data (e.g. user input) that's also a security risk.

So the main criticisms are that it's slow, it's bulky, it's insecure, and it's fairly random. You have to take extra measures to be sure that the type you're getting is the one you want, e.g. wrapping JavaScript function calls that have to return a number in ParseInt(), which fairly much defeats the purpose of having dynamic types.

All the "Indeed!"

I like to cheat by appending a + to the function to coerce it to a number.

+returnPossiblyNumber()

or

"" + number

to force it to be a string

[Reelya]

btw, I made a little testing rig for double-linked-lists with either a possibly-null head/tail vs the one with the "dummy" head/tail. Pushing X amount of values to the linked lists for 10000 trials.

If you're pushing ~15+ items to the one with the dummy head, it's the fastest linked list 80+% of the time (testing error due to background processes etc).  For large linked lists (1000 items+) using a dummy head is from 4 ~ 6% faster than the basic version where you're doing the if-check for a null head for each push (more speed-up on longer lists).

I did two "null head" lists, one uses the basic if statements (if head == null), and the other uses optimized if-statements (assume non-null in the true branch). That one was the fastest for most list sizes under 14. There were a couple of weird "sweet spots" where the (if head == null) list was actually fastest, but if you went either 1 smaller or 1 bigger, the other one was fastest again, so it's due to a quirk such as memory or instruction cache alignment.

[Strife26]

Hell is other people's code.

[Reelya]

Had some niggles but got a nice bit of code working in C++ that could be useful to people:

Code: [Select]

#include <iostream>
#include <string>
#include <vector>
#include <thread>
#include <algorithm>

    struct parloop
    {
    public:
        parloop(int _numThreads, int _rangeStart, int _rangeEnd, void(*_lambda)(int)) //
            : numThreads(_numThreads), rangeStart(_rangeStart), rangeEnd(_rangeEnd), lambda(std::move(_lambda)) //
        {
            init();
            exit();
        }
    private:
        typedef void(*lambdaType)(int);
        std::vector<std::thread> myThreads;
        int numThreads, rangeStart, rangeEnd;
        lambdaType lambda;


        void init()
        {
            myThreads.resize(numThreads);

            for (int i = 0; i < numThreads; ++i)
            {
                myThreads[i] = std::thread(myThreadFunction, this, chunkStart(i), chunkEnd(i)); //
            }
        }

        void exit()
        {
            for (int i = 0; i < numThreads; ++i)
            {
                myThreads[i].join();
            }
        }

        int rangeJump()
        {
            return ceil(float(rangeEnd - rangeStart) / float(numThreads));
        }

        int chunkStart(int i)
        {
            return rangeJump() * i;
        }

        int chunkEnd(int i)
        {
            return std::min(rangeJump() * (i + 1) - 1, rangeEnd);
        }

        static void myThreadFunction(parloop *self, int start, int end) //
        {
            auto lambda = self->lambda;
            // we're just going to loop through the numbers and print them out
            for (int i = start; i <= end; ++i)
            {
                lambda(i); // commenting this out speeds things up back to normal
            }
        }

    };

    void doThing(int i) // "payload" of the lambda function
    {
    }

    int main()
    {
        auto start = timer.now();
        auto stop = timer.now();

        const int maxThreads = 8;
        std::vector<float> result(maxThreads + 1);

        // run 4 trials of each number of threads
        for (int x = 1; x <= 1000; ++x)
        {
            // test between 1-8 threads
            for (int numThreads = 1; numThreads <= maxThreads; ++numThreads)
            {
                start = timer.now();

                // this is the line of code which calls doThing in the loop

                parloop(numThreads, 0, 100000000, [](int i) { doThing(i); });

                stop = timer.now();

                float time = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start).count() / 1000000.0f;

                result[numThreads] += time;

                cout << numThreads << " Time = " << time << " ms " << result[numThreads] / result[1] * 100 << "%\n";
                //cout << "\t\tsimple list, time was " << deltaTime2 / 1000000.0f << " ms\n";
            }
            cout << std::endl;
        }

        cin.ignore();
        cin.get();
        return 0;
    }

Basically, it's a "function" (actually a class that you call like a function) that takes a number of threads, start index, finish index and a lambda, and performs that operation for each of the indexes. But split into X threads.

Code: [Select]

parloop(numThreads, startIndex, finishIndex, [](int i)
{
    doTheThing(i);
});
So you can really easily get nearly quad speedups on a 2-core processor (standard 2 threads per core) for processing every index in a large array with this, as long as the array processing is parralelizable. 8 threads is a good rule of thumb since you'll get nearly 8x speedup on a 4-core machine, and it's about the same as 4 threads on a 2-core machine anyway.

[McTraveller]

btw, I made a little testing rig for double-linked-lists with either a possibly-null head/tail vs the one with the "dummy" head/tail. Pushing X amount of values to the linked lists for 10000 trials.

If you're pushing ~15+ items to the one with the dummy head, it's the fastest linked list 80+% of the time (testing error due to background processes etc).  For large linked lists (1000 items+) using a dummy head is from 4 ~ 6% faster than the basic version where you're doing the if-check for a null head for each push (more speed-up on longer lists).

I did two "null head" lists, one uses the basic if statements (if head == null), and the other uses optimized if-statements (assume non-null in the true branch). That one was the fastest for most list sizes under 14. There were a couple of weird "sweet spots" where the (if head == null) list was actually fastest, but if you went either 1 smaller or 1 bigger, the other one was fastest again, so it's due to a quirk such as memory or instruction cache alignment.

I'm curious about this one - don't you still have to check if a node's previous pointer is equal to the dummy head? I guess maybe that has to do only with delete or inserts not at the head/tail.

If you are really interested in speed, you can actually try something like the following, but it depends on the cost of a cached compare vs. a cached function call (C-like pseudocode):

Code: [Select]

struct List
{
     Node* head;
     Node* tail;
     void (*insert)(List* list, void* item);
};

void List_add_item(List* list, void* item) // private
{
    list->tail->next = new Node;
    list->tail->next->item = item;
    list->tail = list->tail->next;
}

void List_add_first_item(List* list, void* item) // private
{
    list->head = list->tail = new Node;
    list->head->item = item;
    list->insert = List_add_item;
}

void List_init(List* list) // public
{
   list->insert = List_add_first_item;
}

void List_add(List* list, void* item) // public
{
  list->insert(list,item);
}

EDIT: if you are *really* interested in speed though, you have a fixed-length list, because new/malloc and friends are SLOW.

[breadman]

I'm curious about this one - don't you still have to check if a node's previous pointer is equal to the dummy head? I guess maybe that has to do only with delete or inserts not at the head/tail.

Nope.  The point of the dummy head is that all of the real data is in the middle of the linked list, so none of it is a special case.  So when you delete the first node in the list, you set the second node's previous pointer to the first node's previous pointer, just like any other delete, but this time the previous pointer just happens to point to the dummy head.

All other cases where you might want to check whether you're at a dummy node can be prevented by storing the length of the list, and checking against that before running an operation.  Then your only real problem is ensuring that the sudden death of a thread can't cause an operation to be partially completed.  (That's probably impossible for a linked list, but good luck!)

[McTraveller]

I'm curious about this one - don't you still have to check if a node's previous pointer is equal to the dummy head? I guess maybe that has to do only with delete or inserts not at the head/tail.

Nope.  The point of the dummy head...

I was trying to reason through it in my head without drawing it out... apparently my "in the head reasoning" is not what it used to be

So yeah, the dummy head/tail is pretty nifty actually, and the cost of two nodes is basically nothing in terms of memory... why am I just now learning about dummy head/tail nodes!?!  I'm kind of ashamed really - I've been programming for 20 years now     

[milo christiansen]

Don't feel bad, I've never heard of them either.

I rarely use linked lists, but next time I do dummy nodes will be on my list of things to remember.

[TheBiggerFish]

That is new, yes.

[Reelya]

kek, i cracked it. I've put together a single linked list in C++ that you can store just about anything in, e.g. arbitrary structures or primitives in the same list.

The way i did it was by not having a template parameter on the actual list class. I made a non-templatized list, then created an inherited "node" type that has a template parameter, then, there's a template on the push function which creates a new "node<T>" based on whatever you throw in there based on implicit template parameter resolution. But in this case, the templated class is in fact a child of the regular nodes, so they can daisy-chain into the linked list without any issues.

The "child" node has a function that stringifies the name of the data type, and I put the string in a static variable, so it's only run once per type of object you put in, so every int for example points at the same string that says "int". I had to add a template specialization so that it could handle char* and strings however, since it would only want to store the pointers for those, so I had to override it for those cases. So you can read the name of the stored types to know what each node is holding. And the only extra overhead compared to a normal linked list is about 8 bytes per node (4 byte pointer to the typename, 4 bytes sizeof).

Spoiler (click to show/hide)

Code: [Select]

template <typename T> const char* Type() {    static const char *s = typeid(T).name(); return s; }

class listMulti
{
public:
    class nodeBase
    {
    public:
        nodeBase *prev, *next;
        nodeBase() : prev(0), next(0) {}
        virtual const char *getType() = 0;
        virtual void *getData() = 0;
        int size;
    };

    template <typename T> class node : public nodeBase
    {
        const char *type;
        T data;
    public:
        node(T _data) : type(Type<T>()), data(_data)
        {
            size = sizeof(data);
        }
        ~node()
        {
            delete data;
        }
        const char *getType() { return type;  }
        void *getData() { return &data; }
    };

    template <> class node<const char*> : public nodeBase
    {
        const char *type;
        char *data;
    public:
        node(const char *_data) : type(Type<const char*>())
        {   
            size = strlen(_data) + 1;
            data = new char[size];
            //for (int i = 0; i < size + 1; ++i) data[i] = 0;
            strcpy_s(data, size, _data);
        }
        ~node()
        {
            delete data;
        }
        const char *getType() { return type; }
        void *getData() { return data; }
    };

    template <typename T> friend class listOptimized;

public:
    nodeBase *head, *tail;
    unsigned int count;

    listMulti() : count(0)
    {
        head = new node<int>(0);
        tail = new node<int>(0);
        head->next = tail;
        tail->prev = head;
    }

    ~listMulti()
    {
        nodeBase *temp;
        while (head)
        {
            temp = head->next;
            delete head;
            head = temp;
        }
    }

private:
    void insertAfter(nodeBase *oldNode, nodeBase *newNode) // this function should be private
    {
        newNode->prev = oldNode;
        newNode->next = oldNode->next;
        oldNode->next->prev = newNode;
        oldNode->next = newNode;
        count++;
    }

    nodeBase *removeNode(nodeBase *node)
    {
        if (node != nullptr)
        {
            // remove node
            node->prev->next = node->next;
            node->next->prev = node->prev;
            count--;
        }
    }

public:
    template <typename T> void push(T data)
    {
        nodeBase *node = NODE(data);
        insertAfter(head, node);
    }

    template <> void push<std::string>(std::string data)
    {
        push(data.c_str());
    }

    void push(nodeBase *node)
    {
        insertAfter(head, node);
    }

    void pushback(nodeBase *node)
    {
        insertAfter(tail->prev, node);
    }

    nodeBase *pop()
    {
        if (head->next != tail)
        {
            return(removeNode(head->next));
        }
    }

    nodeBase *popback()
    {
        if (tail->prev != head)
        {
            return(removeNode(tail->prev));
        }
    }

    nodeBase *getNodeAt(unsigned int location)
    {
        nodeBase *node = head->next;

        while (location > 0 && node != tail)
        {
            node = node->next;
            location--;
        }

        if(node != tail)
            return node;
        else
            return nullptr;
    }

    void insert(unsigned int location, nodeBase *node)
    {
        nodeBase *oldNode = getNodeAt(location);
        if (oldNode != nullptr)
        {
            insertAfter(oldNode, node);
        }
    }

    nodeBase *remove(int location)
    {
        nodeBase *node = getNodeAt(location);
        return removeNode(node);
    }

    template <typename T> static nodeBase *NODE(const T& data)
    {
        nodeBase *n = new node<T>(data);
        return (n);
    }

    void showDataAt(int index)
    {
        nodeBase *n = getNodeAt(index);
        if (n != nullptr)
        {
            const char *type = getNodeAt(index)->getType();
            void *address = getNodeAt(index)->getData();

            std::cout << type << "( " << n->size << " bytes ) ";

            if ( type == Type<float>())
            {
                std::cout << " = " << *(float *)(address) << std::endl;
            }
            else if (type == Type<double>())
            {
                std::cout << " = " << *(double *)(address) << std::endl;
            }
            else if (type == Type<char const *>())
            {
                std::cout << " = " << (const char *)address << std::endl;
            }
            else
            {
                std::cout << " = " << *(int *)address << std::endl;
            }
        }
    }
};

And here's some test data to show you that you can in fact push literally anything into this list and get back the data later:

Code: [Select]

    struct Cat { int whiskers = 1000; };
    Cat cat;

    int main()
    {
        listMulti list1;

        list1.push(44);
        list1.push(2.0423423432f);
        list1.push("drugs");
        list1.push(std::string("hello"));
        list1.push(bool(true));
        list1.push(2.4545);
        list1.push('a');
        list1.push(short(66));
        list1.push([] { int a, b; });
        list1.push([] { int a; });

        struct Dog { int legs[4]{ 9,9,9,9 }; char tail{ 't' }; };
        Dog dog;
        list1.push(dog);
        list1.push(cat);

        std::cout << "count = " << list1.count << std::endl;

        for (int i = 0; i < list1.count; ++i)
        {
            list1.showDataAt(i);
        }

        std::cin.ignore();
        std::cin.get();
        return 0;
    }