2

The lowest levels of a programming language's library functions are always obscure and often have no code that looks like it even remotely does anything. Some languages have these functions like getting substrings, converting between data types, querying a variable's data type, and so forth implemented as part of their standard libraries, but I can't imagine how these low-level functions can be expressed using said language. How are these things achieved? I'm not asking for how it is done with all languages, but rather what the general method of doing this is conceptually.

closed as unclear what you're asking by user40980, GlenH7, Doval, gnat, amon Mar 23 '15 at 22:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    This question is very broad. Probably, the magic in the functions you have looked at is buried under some layers of indirection into native code or compiler intrinsics. – 5gon12eder Mar 23 '15 at 0:23
  • 3
    Its different for C vs Java vs Python vs Perl vs Lisp vs Ruby... there is no general method for built ins. – user40980 Mar 23 '15 at 0:36
  • 4
    @Melab, asking for the general method is what makes it broad. There is no general method, every language does things a bit differently. – Winston Ewert Mar 23 '15 at 0:37
  • 2
    strlen is part of string.h and the standard library (though some compilers (gcc) may handle it as a builtin... but thats an implementation not a language thing), not a built in. ToString in C# is part of the Object contract (and not a built in at all). Do you have any other examples of built ins? – user40980 Mar 23 '15 at 1:03
  • 1
    @Melab: study the source code of musl-libc -which is very readable- or of GNU glibc if you want to know how functions like printf are implemented in standard C libraries – Basile Starynkevitch Mar 23 '15 at 7:53
6

"I'm incapable of imagining things like how the code to convert a string to a number or a number to a string would be written."

Below is simple C code that converts binary to decimal and back again. I wrote it long ago for a project in which the target was an embedded processor and the development tools had a stdlib that was way too big for the firmware ROM.

We had a C compiler/linker that could generate executables and we needed to do what we could do without any stdlib (which was a pig). So no printf() nor scanf(). Not even an sprintf() nor sscanf(). But we still had a user interface and had to convert base-10 numbers into binary and back. (We made up our own malloc()-like utility also and our own transcendental math functions too.)

So this was how I did it (the main program and calls to stdlib were there for testing this thing on my mac, not for the embedded code). Also, because some older dev systems don't recognize "int64" and "uint64" and similar types, the types long long and unsigned long long are used and assumed to be the same. And long is assumed to be 32 bits. I guess I could have typedefed it.

#include <stdlib.h>
#include <stdio.h>

// returns an error code, 0 if no error,
// -1 if too big, -2 for other formatting errors
int decimal_to_binary(char *dec, long *bin)
    {
    int i = 0;

    int past_leading_space = 0;
    while (i <= 64 && !past_leading_space)        // first get past leading spaces
        {
        if (dec[i] == ' ')
            {
            i++;
            }
         else
            {
            past_leading_space = 1;
            }
        }
    if (!past_leading_space)
        {
        return -2;                                // 64 leading spaces does not a number make
        }
    // at this point the only legitimate remaining
    // chars are decimal digits or a leading plus or minus sign

    int negative = 0;
    if (dec[i] == '-')
        {
        negative = 1;
        i++;
        }
     else if (dec[i] == '+')
        {
        i++;                                    // do nothing but go on to next char
        }
    // now the only legitimate chars are decimal digits
    if (dec[i] == '\0')
        {
        return -2;                              // there needs to be at least one good 
        }                                       // digit before terminating string

    unsigned long abs_bin = 0;
    while (i <= 64 && dec[i] != '\0')
        {
        if ( dec[i] >= '0' && dec[i] <= '9' )
            {
            if (abs_bin > 214748364)
                {
                return -1;                                // this is going to be too big
                }
            abs_bin <<= 1;
            abs_bin += (abs_bin<<2);                      // an efficient way to multiply by 10
//          abs_bin *= 10;                                // previous value gets bumped to the left one digit...                
            abs_bin += (unsigned long)(dec[i] - '0');     // ... and a new digit appended to the right
            i++;
            }
         else
            {
            return -2;                                    // not a legit digit in text string
            }
        }

    if (dec[i] != '\0')
        {
        return -2;                                // not terminated string in 64 chars
        }

    if (negative)
        {
        if (abs_bin > 2147483648)
            {
            return -1;                            // too big
            }
        *bin = -(long)abs_bin;
        }
     else
        {
        if (abs_bin > 2147483647)
            {
            return -1;                            // too big
            }
        *bin = (long)abs_bin;
        }

    return 0;
    }


void binary_to_decimal(char *dec, long bin)
    {
    unsigned long long acc;                // 64-bit unsigned integer

    if (bin < 0)
        {
        *(dec++) = '-';                    // leading minus sign
        bin = -bin;                        // make bin value positive
        }

    acc = 989312855LL*(unsigned long)bin;        // very nearly 0.2303423488 * 2^32
    acc += 0x00000000FFFFFFFFLL;                 // we need to round up
    acc >>= 32;
    acc += 57646075LL*(unsigned long)bin;
    // (2^59)/(10^10)  =  57646075.2303423488  =  57646075 + (989312854.979825)/(2^32)  

    int past_leading_zeros = 0;
    for (int i=9; i>=0; i--)            // maximum number of digits is 10
        {
        acc <<= 1;
        acc += (acc<<2);                // an efficient way to multiply by 10
//      acc *= 10;

        unsigned int digit = (unsigned int)(acc >> 59);        // the digit we want is in bits 59 - 62

        if (digit > 0)
            {
            past_leading_zeros = 1;
            }

        if (past_leading_zeros)
            {
            *(dec++) = '0' + digit;
            }

//      printf(" i = %d, acc = 0x%016llx \n", i, acc<<1);    // put digit into upper 4 bits to be easily read

        acc &= 0x07FFFFFFFFFFFFFFLL;    // mask off this digit and go on to the next digit
        }

    if (!past_leading_zeros)            // if all digits are zero ...
        {
        *(dec++) = '0';                 // ... put in at least one zero digit
        }

    *dec = '\0';                        // terminate string
    }


#if 1

int main (int argc, const char* argv[])
    {
    char dec[64];
    long bin, result1, result2;
    unsigned long num_errors;
    long long long_long_bin;

    num_errors = 0;
    for (long_long_bin=-2147483648LL; long_long_bin<=2147483647LL; long_long_bin++)
        {
        bin = (long)long_long_bin;
        if ((bin&0x00FFFFFFL) == 0)
            {
            printf("bin = %ld \n", bin);        // this is to tell us that things are moving along
            }
        binary_to_decimal(dec, bin);
        decimal_to_binary(dec, &result1);
        sscanf(dec, "%ld", &result2);            // decimal_to_binary() should do the same as this sscanf()

        if (bin != result1 || bin != result2)
            {
            num_errors++;
            printf("bin = %ld, result1 = %ld, result2 = %ld, num_errors = %ld, dec = %s \n",
                bin, result1, result2, num_errors, dec);
            }
        }

    printf("num_errors = %ld \n", num_errors);

    return 0;
    }

#else

int main (int argc, const char* argv[])
    {
    char dec[64];
    long bin;

    printf("bin = ");
    scanf("%ld", &bin);
    while (bin != 0)
        {
        binary_to_decimal(dec, bin);
        printf("dec = %s \n", dec);
        printf("bin = ");
        scanf("%ld", &bin);
        }

    return 0;
    }

#endif
  • 2
    Do you always indent like that? It's very unorthodox, but not unreadable at all. Maybe we focus to much on details at times... – monocell Mar 23 '15 at 9:12
  • 3
    That style used to be very common. It is not that unorthodox. See en.wikipedia.org/wiki/Indent_style#Whitesmiths_style – Steven Burnap Mar 23 '15 at 13:46
  • @monocell part of the indent confusion is the use of tabs in the code while Stack Exchange code block format really wants spaces. This is causing the first indent level to not be depicted as such. – user40980 Mar 23 '15 at 15:15
  • 1
    Robert, I moved some of the comments around a little bit (and wrapped others) to try to keep the text from having excessive horizontal scrolling. Some of it is still there (the horizontal scrolling). With SE markdown, tabs often make more of a mess than spaces (it tries to have a 4 space indent level, but isn't always successful at interpreting that style from the source). The best thing to do would be to convert the tabs to spaces in an editor first, then make sure they're all looking correct, and then post it. – user40980 Mar 23 '15 at 15:26
  • that's fine @MichaelT. i personally dunno most of the markup (or is it "markdown") tricks in SE. personally, besides quote chars, i would italicize quotes, just to make sure people understand that they're different from my words. – robert bristow-johnson Mar 23 '15 at 23:11
4

You might do well to take an assembly language class. It would clarify for you how data is actually represented in memory. Types are just an abstract construct to make working with data easier. You don't need them for programming. You just need to agree on a representation.

For example, one of the simpler representations for a string is an array of characters with a null (zero) at the end. You know how to work with arrays, right? You know how to test if an element of an array is zero, right? You know how to assign an element of an array to zero, right? That's all you need to know to be able to find a substring.

How about querying for some data's type, in a dynamically-typed language? Again, all you need is a representation. Maybe you make it a struct with the first element being the size of the data, the second being the actual data, and the third being a null-terminated character array containing the name of the type. You know how to work with structs, right? We already discussed how to work with a null-terminated string. That's all you need to know to be able to query for a type.

How about converting between types, say from a string to an int? Again, you just agree on a representation, which in this case would be ASCII. You know how to look something up in a table, right? In this case, the digits are all conveniently arranged consecutively, so all you have to do is subtract 48 to get one character's integer value. For multiple digits, all you have to do is a loop that multiplies by 10 and adds the next character's value.

In other words, the general process is to come up with some representation in terms of what is already defined in the language, and use that to create higher-level abstractions.

1

First, many compiled implementations of programming languages have builtins or intrinsics, that is functions which are known to the compiler and which are compiled in a special way.

For C or C++ compiled by GCC there are many builtin functions. Ocaml has external functions, etc....

Then, some implementations offer some way to use the underlying framework. So GCC (which is translating to assembler) is able to embed assembly code, MELT (translated to C++) is able to embed C++ code (using code_chunk, defprimitive, defcmatcher etc...), and so on.

At last, standard libraries of the languages are using some underlying implementation layer. In particular, C standard libraries are generally using syscalls to invoke elementary operations provided by the operating system kernel.

BTW, using a free software operating system (like GNU/Linux) and compiler (like GCC) and library (like GNU libc or musl-libc) helps a lot, since you can always study the source code of free software.

Read also about homoiconic languages, reflection, ....

Not the answer you're looking for? Browse other questions tagged or ask your own question.