Come vengono implementate le funzioni di base in un linguaggio di programmazione se non sono integrate? [chiuso]

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

Di seguito è riportato un semplice codice C che converte i binari in decimali e viceversa. L'ho scritto molto tempo fa per un progetto in cui il target era un processore embedded e gli strumenti di sviluppo avevano uno stdlib che era way troppo grande per la ROM del firmware.

Avevamo un compilatore / linker C in grado di generare file eseguibili e dovevamo fare ciò che potevamo fare senza qualsiasi stdlib (che era un maiale). Quindi niente printf() né scanf() . Neanche un sprintf() o sscanf() . Ma noi ancora avevamo un'interfaccia utente e dovevamo convertire i numeri di base 10 in binari e viceversa. (Abbiamo creato anche la nostra utility malloc() -like e anche le nostre stesse funzioni matematiche trascendentali.)

Ecco come ho fatto (il programma main e le chiamate a stdlib erano lì per testare questa cosa sul mio mac, non per il codice incorporato). Inoltre, poiché alcuni sistemi di sviluppo precedenti non riconoscono " int64 " e " uint64 " e tipi simili, vengono utilizzati i tipi long long e unsigned long long e si presume che siano uguali. E si suppone che long sia 32 bit. Credo che potrei avere typedef ed 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] == '
#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] == '%pre%')
        {
        return -2;                              // there needs to be at least one good 
        }                                       // digit before terminating string

    unsigned long abs_bin = 0;
    while (i <= 64 && dec[i] != '%pre%')
        {
        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] != '%pre%')
        {
        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 = '%pre%';                        // 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
')
        {
        return -2;                              // there needs to be at least one good 
        }                                       // digit before terminating string

    unsigned long abs_bin = 0;
    while (i <= 64 && dec[i] != '%pre%')
        {
        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] != '%pre%')
        {
        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 = '%pre%';                        // 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

Potresti fare una lezione di linguaggio assembly. Chiarirebbe per voi come i dati sono effettivamente rappresentati in memoria. I tipi sono solo un costrutto astratto per semplificare il lavoro con i dati. Non è necessario per la programmazione. Devi solo concordare una rappresentazione.

Ad esempio, una delle rappresentazioni più semplici per una stringa è una matrice di caratteri con un nullo (zero) alla fine. Sai come lavorare con gli array, giusto? Sai come testare se un elemento di un array è zero, giusto? Sai come assegnare un elemento di un array a zero, giusto? È tutto ciò che devi sapere per essere in grado di trovare una sottostringa.

Che ne dici di interrogare per il tipo di alcuni dati, in un linguaggio tipizzato dinamicamente? Di nuovo, tutto ciò di cui hai bisogno è una rappresentazione. Forse lo rendi un struct con il primo elemento che è la dimensione dei dati, il secondo i dati effettivi, e il terzo è un array di caratteri terminato da null che contiene il nome del tipo. Sai come lavorare con le strutture, giusto? Abbiamo già discusso su come lavorare con una stringa con terminazione null. È tutto ciò che devi sapere per poter eseguire una query per un tipo.

Che ne dici di convertire tra i tipi, da una stringa a una int? Ancora una volta, sei d'accordo su una rappresentazione, che in questo caso sarebbe ASCII . Sai come guardare qualcosa in un tavolo, giusto? In questo caso, le cifre sono tutte convenientemente disposte consecutivamente, quindi tutto ciò che devi fare è sottrarre 48 per ottenere il valore intero di un personaggio. Per più cifre, tutto ciò che devi fare è un ciclo che si moltiplica per 10 e aggiunge il valore del prossimo carattere.

In altre parole, il processo generale è quello di fornire una rappresentazione in termini di ciò che è già definito nella lingua e usarlo per creare astrazioni di livello superiore.

In primo luogo, molte implementazioni compilate dei linguaggi di programmazione hanno builtin o intrinseche, cioè funzioni che sono note al compilatore e che sono compilate in un modo speciale.

Per C o C ++ compilato da GCC ci sono molti builtin funzioni . Ocaml ha funzioni esterne , ecc ....

Quindi, alcune implementazioni offrono un modo per usare il framework sottostante. Quindi GCC (che sta convertendo in assembler) è in grado di incorporare codice assembly , MELT (tradotto in C ++) è in grado di incorporare codice C ++ (usando code_chunk , defprimitive , defcmatcher ecc. ..), e così via.

Finalmente, le librerie standard delle lingue stanno usando alcuni livelli di implementazione sottostanti. In particolare, le librerie standard C utilizzano generalmente syscalls per richiamare le operazioni elementari fornite dal sistema operativo kernel .

BTW, utilizzando un sistema operativo gratuito (come GNU / Linux) e compilatore (come GCC) e libreria ( come GNU libc o musl-libc ) aiuta molto, dal momento che puoi sempre studiare il codice sorgente del software libero.

Leggi anche su omoiconico lingue, reflection , ....