How are basic functions implemented in a programming language if they are not built in? [closed]

Question

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.

Answer 1

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.

Answer 2

"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 "int64t" and "uint64t" 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;                                // an efficient way
            abs_bin += (abs_bin<<2);                      //  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;                      // an efficient way
        acc += (acc<<2);                //  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

Answer 3

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, ....