OSDev

для всех
Текущее время: 25 ноя 2020, 07:51

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 285 ]  На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 29  След.
Автор Сообщение
СообщениеДобавлено: 14 фев 2015, 19:02 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Аналогия с числами Фибоначчи понятна, но лучше придумать на будущее какой-нибудь другой пример, так как мастер ФП сразу скажет, что давайте возведём специальную матрицу размером 2x2 в степень N и нужное нам число Фибоначчи будет лежать в заведомо выбранной ячейке. Матрица такая:
Код:
| 1 1 |
| 1 0 |

Мне больше нравится издеваться над сторонниками подхода "сверху вниз" задачами, в которых их подходом сжирается память. Почву из под ног выбивает любое линейное рекуррентное соотношение порядком больше тысячи и максимальным собственным значением больше 1. Когда нам нужен какой-нибудь десятитысячный член последовательности, возведение матрицы соотношения в степень убьёт даже RoadRunner, тогда как с помощью ИП я могу посчитать ответ на своём телефоне.

Кстати, каркасные дома строят (нормальные люди), удачно совмещая в себе оба подхода: фундамент, обвязка, стойки каркаса, затем крыша, а уже потом пол, стены и прочие элементы каркаса. То есть идут снизу вверх, а потом обратно сверху вниз. Потом в зависимости от вида отделки снова идут вверх (если отделка доской под "ёлочку") или вниз (если блок-хаус или имитация бруса).

Не знаю, зачем я всё это написал : ) Мне нравится, когда к аналогиям нельзя придраться, даже когда они мне понятны и я их поддерживаю.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 14 фев 2015, 19:27 

Зарегистрирован: 21 сен 2007, 17:24
Сообщения: 1088
Откуда: Балаково
Yoda писал(а):
При разработке принято говорить о наборе инструментов (toolchain). Но давайте подумаем. Функции линкера настолько просты, что входят даже в ассемблер NASM. Функции ассемблера достаточно просты по сравнению с функциями компилятора ЯВУ, так что многие компиляторы имеют встроенный ассемблер. Так зачем нам тогда нужен toolchain? Я предполагаю, что всю цепочку было бы разумней реализовать в виде единого исполняемого файла (как сейчас и поступают большинство вменяемых компиляторов). В таком случае можно легко избежать привязки к устаревшим объектным форматам.

Не совсем понял что подразумевается под цепочкой. От объектных файлов ни куда не деться, иначе придётся перекомпилировать множество исходных файлов после внесения каждой запятой. Хорошо конечно, когда одна программа - один исходник.
Yoda писал(а):
Нет, объём кода здесь ни при чём. Два подхода отличаются по самой своей сути, по логике мышления. Вот они:
Императивный: "У нас что-то есть. Что мы из этого можем получить?"
Функциональный: "Нам что-то нужно. Что нам нужно, чтобы это получить?"

Верно в том смысле, что ФЯ часто позволяет вычислить результат в прямой математической записи. Это позволяет использовать интерпретатор для быстрого получения результата как в калькуляторе, вводя отдельные формулы. Если вы написали рекурсивную программу, то и получите рекурсию. Кто вам виноват? И в ИЯ можно записать точно такой же алгоритм, и он так же зациклится.
Надо различать примеры для обучения или для простого вычисления, и реальное программирование. В программировании используются схожие с ИП способы использования переменных для хранения промежуточных сумм, но более хитро (или запутанно) - используя для этого дополнительные параметры функции. Я лично не программирую, но те кто программируют, никогда не жалуются, значит к этому можно привыкнуть :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 14 фев 2015, 20:17 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 963
Откуда: Дагоба
Zealint писал(а):
мастер ФП сразу скажет, что давайте возведём специальную матрицу размером 2x2 в степень N и нужное нам число Фибоначчи будет лежать в заведомо выбранной ячейке.

Для реального расчёта числа Фибоначчи я бы вообще использовал следующий очень эффективный (для больших значений) код:
Код:
double Fibo (int n) {
  double s5 = sqrt(5);
  return (power((1+s5)/2,n)-power((1-s5)/2,n))/s5;
}

парадоксально дающий целочисленный результат, несмотря на промежуточное использование иррациональных чисел. Дело в том, что и ваш и мой код уходят от первоначального определения последовательности и в некотором смысле являются "твиками" людей, которые знают свойства этих чисел чуть больше, чем среднестатистический человек. Если рядовому программисту дадут определение последовательности и поручат написать соответствующий код, большинство сделает это именно так. Кроме того, я же и указал традиционный способ решения подобных проблем в ФП. Пример выбран по двум причинам - он достаточно прост для понимания (не вдаваясь в высшую математику), но вместе с тем он наглядно демонстрирует разницу подходов и вероятные проблемы (не утверждая при этом, что эти проблемы не имеют решения!).

Zealint писал(а):
Кстати, каркасные дома строят (нормальные люди), удачно совмещая в себе оба подхода...

Так ведь и я говорю, что ФП заставило изменить множество вещей в ИП, т.е. да, есть сильное обратное влияние, и в этом состоит грандиозная польза ФП. Но в качестве основы для своих целей я предпочитаю ИП.

Zealint писал(а):
Мне нравится, когда к аналогиям нельзя придраться, даже когда они мне понятны и я их поддерживаю.

Может быть тогда предложите аналогию, столь же простую и понятную, как ряд Фибоначчи?
Я бы тоже предпочёл иметь пример, к которому нельзя придраться, однако, большинство проблем из области математики и CS может иметь несколько разных решений.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 14 фев 2015, 20:46 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 963
Откуда: Дагоба
Himik писал(а):
Не совсем понял что подразумевается под цепочкой.

Всё, что осуществляет следующую последовательность преобразований src (-> asm) -> obj (-> lib) -> exe.

Himik писал(а):
От объектных файлов ни куда не деться, иначе придётся перекомпилировать множество исходных файлов после внесения каждой запятой.

Да, верно. Поэтому скорей всего никуда не деться от name mangling в объектниках, а также от возможной несовместимости вызовов между разными языками.

Himik писал(а):
Хорошо конечно, когда одна программа - один исходник.

Да можно и много исходников, но в компиляции в один заход.

Himik писал(а):
Верно в том смысле, что ФЯ часто позволяет вычислить результат в прямой математической записи. Это позволяет использовать интерпретатор для быстрого получения результата как в калькуляторе, вводя отдельные формулы. Если вы написали рекурсивную программу, то и получите рекурсию. Кто вам виноват? И в ИЯ можно записать точно такой же алгоритм, и он так же зациклится.

Так я не говорю, что кто-то виноват и не утверждаю, что в ИП невозможно программирование в категориях ФП (рекурсивные вызовы). Очень даже возможно! Другое дело, что компиляторы функциональных языков активно используют хвостовую рекурсию (которая, кстати, также возможна в императивных языках!) и побуждают программиста мыслить именно в указанной категории.

Himik писал(а):
Надо различать примеры для обучения или для простого вычисления, и реальное программирование. В программировании используются схожие с ИП способы использования переменных для хранения промежуточных сумм

Я ведь говорю то же самое. Чистое ФП невозможно, поэтому реальные языки так или иначе используют уловки из ИП. Т.е. взаимопроникновение двух концепций не просто происходит - оно неизбежно.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 08:33 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Yoda писал(а):
парадоксально дающий целочисленный результат, несмотря на промежуточное использование иррациональных чисел.

Ничего парадоксального. Берутся изначально целые числа, а затем серия манипуляций, приводящая к иррациональным числам. А сама по себе формула - это символическая запись обратного процесса сбора иррациональных чисел в целые. Неудивительно, что мы получаем целое число в конце, если с него и начали вывод формулы. Также неудивительно, что помножив корень из двух на синус Pi/4 вы получите единицу из чисто геометрических соображений, хотя в выражении участвуют трансцендентные числа.

Yoda писал(а):
Может быть тогда предложите аналогию, столь же простую и понятную, как ряд Фибоначчи?
Я бы тоже предпочёл иметь пример, к которому нельзя придраться, однако, большинство проблем из области математики и CS может иметь несколько разных решений.

Я пытался подумать над этим вопросом, но пришёл к неутешительным выводам. Такой аналогии выдумать не получится, поскольку в программировании (как я его понимаю) нет ни чистого ИП, ни чистого ФП. Всегда идёт смесь этих подходов. Даже на ассемблере когда пишешь, пытаешься где-то применить функциональный подход к логике написания программы, максимально разделяя участки кода на независимые конструкции-псевдофункции (через метки и jmp или call/ret). Получается как бы не совсем ФП, но и не совсем ИП. Пытаясь придумывать аналогии типа "ФП-программист сначала кладёт столовые приборы на стол, а потом готовит под них еду" мы критикуем чистый ФП подход, пытаясь критиковать ИП аналогиями вроде "ИП-программист начинает тушить пожар ещё до того, как он начался", мы критикуем чистый ИП подход, что неправильно.

Правильно исходить из практики. Я вот ни разу не видел решения ни одной труднорешаемой задачи, которое работало бы быстрее на ФП языке, чем на ИП, когда за основу берётся одинаковый метод решения.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 12:15 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Yoda писал(а):
Для реального расчёта числа Фибоначчи я бы вообще использовал следующий очень эффективный (для больших значений) код:
Код:
double Fibo (int n) {
  double s5 = sqrt(5);
  return (power((1+s5)/2,n)-power((1-s5)/2,n))/s5;
}


Я подумал немного и пришёл к выводу, что быстрота этого алгоритма по сравнению с возведением матрицы в степень неочевидна. Но проверить это можно только на практике. Если угодно, можно запустить соревнование : ) Посчитать точно число Фибоначчи с некоторым номером. Номер подобрать так, чтобы была очевидна разница в скорости программ. Вы пишите формулу, а я с матрицей. Я не знаю, что получится в итоге.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 12:42 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
Yoda писал(а):
Поэтому скорей всего никуда не деться от name mangling в объектниках, а также от возможной несовместимости вызовов между разными языками.

Это только в том случае, если существующие объектники принимать за догму и не предлагать ничего нового. В успешном системном программировании непременно должна быть ставка на технологическое лидерство. В руках ведь системные технологии, черт побери! Мужик сказал -- мужик сделал.

Вот, скажем, Borland в Delphi 4 ввела перегружаемые (overloaded) процедуры и одновременно поменяла формат OMF, который перестал быть совместимым с чем-либо. Точных сведений нет, но я предполагаю, что эти решения тесным образом связаны. Хотели сделать мини-революцию. Это был тот период, когда они переименовались в Inprise. Не получилось. Финансовую сторону обсуждать не будем, но а с технической -- число нововведений было невелико, критическую массу им набрать не удалось.

Если в разрабатываемом языке будет достаточно нововведений, свой формат объектного файла обязателен. Существующие можно поддерживать ради совместимости.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 14:09 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1404
Freeman писал(а):
Вот, скажем, Borland в Delphi 4 ввела перегружаемые (overloaded) процедуры и одновременно поменяла формат OMF, который перестал быть совместимым с чем-либо. Точных сведений нет, но я предполагаю, что эти решения тесным образом связаны


Уместно было бы вспомнить, что не только в Дельфях, но и в ДОСовском Турбо Паскале отдельные модули исходного текста (unit'ы) компилировались в отдельные файлы, которые, по сути, были "высокоуровневыми объектниками": там содержалась вся информация о типах и т.п., что позволяло компилятору и его компоновщику объединять разные модули в одну программу, выполняя полный контроль типов и т.п. по правилам Паскаля, и при этом не страдать извращениями вроде name mangling. Последнее, по сути, вызвано желанием не отказываться от существующего низкоуровневого формата объектных файлов, изначально рассчитанного исключительно на ассемблерные программы.

Ну а разработчики компилятора Ады в составе GCC пошли другим путём. Они не могли отказаться от генерации ассемблерного кода, а из него -- обычного объектного, поскольку это навязывается самим GCC. Поэтому фронт-энд Ады генерирует дополнительный файл на каждый транслируемый модуль, который содержит информацию о типах и т.д. и используется специальной программой связывания (gnatbind), которая выполняет часть работы нормального компоновщика -- хотя собственно сборка выполняемого файла из кучи объектников выполняется обычным низкоуровневым компоновщиком, не способным самостоятельно ничего толком проверить. Т.е. здесь имеем костыль другого рода.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 14:58 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
SII писал(а):
Уместно было бы вспомнить, что не только в Дельфях, но и в ДОСовском Турбо Паскале отдельные модули исходного текста (unit'ы) компилировались в отдельные файлы, которые, по сути, были "высокоуровневыми объектниками"

Вот, блин, а! В моем предыдущем ответе был еще один абзац -- как раз про TPU/DCU, но я признал его маргинальным и перед отправкой вычеркнул. :oops:

В дополнение к Аде могу вставить пять копеек и про FreePascal. Он тоже связан совместимостью с инструментарием GNU, поэтому в PPU-файлах хранится только специфичная для Паскаля инфа, а стандартный объектник лежит рядом в .o-файле. Как и в Аде (предполагаю), это делается для того, чтобы получить исполнимый файл вызовом одной команды, безо всяких там makefile. Это и есть модульность.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 15 фев 2015, 15:12 

Зарегистрирован: 31 окт 2011, 18:20
Сообщения: 230
Если использовать подход промежуточного представления аля LLVM, думаю, можно отказаться от традиционных объектников. Вместо этого можно сгенерировать код промежуточного представления, содержащего в себе всё, что нужно для сборки нескольких файлов в один проект, потом собрать все эти файлы в один результирующий и транслировать внутреннее представление в ассемблер (с оптимизацией, конечно). Так мы и уменьшаем количество работы по "перекомпиляции всех исходников после изменения каждой запятой", и при этом не занимаемся извращениями в попытках связать уже скомпилированные файлы в один большой.
Также это промежуточное представление, на мой взгляд, можно было бы хранить не в виде самопального машинного кода (ленты команд), а в виде дерева: в каждом узле хранить тип, оператор и ссылки на его аргументы, которые тоже являются узлами. Конечно работа по сборке результирующего файла из кучи модулей усложнится по сравнению с объектниками, но зато можно будет выполнить очень качественную оптимизацию всей собранной программы.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 285 ]  На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 29  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB