Алгоритмите НЕ са еднакви на различните езици
от Етър Алали
На въпроса дали алгоритмите са еднакви за всички езици за програмиране, моят опростен отговор е „Не“. Но всъщност е много по-нюансирано от това.
Често „Не“ е прекалено опростяване. Използвах го тази седмица като TL;DR, но си струва да се отбележат основните принципи зад него.
Алгоритмите в една и съща програмна парадигма са естествено структурирани еднакво. Следователно ограничаването на парадигмата естествено ограничава езика. Останалият отговор на останалите е понякога.
Заден план
Изчислението е математическо упражнение. Това е метаматематически инвариант. Така че ще го оставя там :)
Всички езици за програмиране редуцират по някакъв начин четимото от човека съдържание до машинен код. Естеството на 3GL и по-нови е синтактичната редовност. Не се справя много добре с превода на естествен език, който е непоследователен в употребата си, директно в машинен код.
Алгоритъм, изразен в математическа форма, ще има някакъв „еквивалент“ в език за програмиране. За да го постигнем, ние интуитивно ограничаваме „математическото“ пространство в това на парадигмата с подходяща символика и го картографираме в ключови думи на езика.
Doff Ye Cap to Godel?
Първата теорема за непълнотата на Годел доказва, че математиката не може да бъде едновременно пълна и последователна по едно и също време. С повечето правила за последователност на езиците за програмиране. За да постигнем последователност (концепция за цикъл, използвана в една част на редактора, е същата като цикъл, използван в друга), трябва да се откажем от пълнотата, което е добре, тъй като езикът така или иначе е обикновена граматика. Не всяка комбинация от терминален знак е валидна. Следователно, естествено е непълен. Ще стане :)
Картографиране на различни парадигми
Конструкцията за цикъл по подразбиране в, да речем, функционалното програмиране е рекурсия. Това се съпоставя много близо до математически естествени структури, наречени рекурентни отношения.
Например:
Представен е на функционални езици като Haskell:
factorial 0 = 1 factorial t = t * factorial(t-1)
За разлика от това, докато можете да направите нещо подобно като C# метод:
// Stuff above
public int factorial( int t ) {
return t == 0? 1 : t * factorial( t — 1 );
}
Много, ако не и повечето хора, които съм срещал по време на моите пословични пътувания, всъщност пишат тази итеративна версия:
public int factorial( int t ) {
int result = 1;
for( int i = t; i > 0; i — ) {
result *= i;
}
return result;
}
В този случай и двете имат една и съща комбинаторна времева сложност, но рекурсивната функция заема малко повече памет (за съхраняване на рамката на стека на функцията). В по-напреднали случаи (напр. двоични, n-арни дървета) начинът, по който го пишете, фундаментално променя времевата сложност на алгоритъма.
Освен това не е задължително да има начин за дефиниране на математически конструкции в изчислителни езици. Компютрите дори технически се борят с дроби. Всъщност Excel не изчислява или съхранява дроби „правилно“ през цялото време.
Резюме
Този проблем често е между парадигмите. Всъщност в декларативните езици е още по-лошо, тъй като обикновено няма определена концепция за цикъл, нито присвояване на променливи. Езици като XSL, TSQL и PL/SQL и дори полуфункционални езици като SML използват нестандартни операции, за да позволят присвояване. Като курсори, „избиране“ в променлива, цикли while и т.н. Следователно, когато е въведена програмна конструкция, това е опит да се направи по-пълна (може да се твърди, че е прекалено пълна. Понякога се губи последователност и се въвеждат странични ефекти в не -езиците за странични ефекти са рискови). И все пак има достатъчно припокриване, за да се абстрахират понятията и да се учи от математиката надолу.
Харесахте ли тази статия? Не забравяйте да уцелите сърцето си и да споделите това с приятелите си. Особено това е важна тема, която вашите приятели и семейство трябва да знаят.
