Обсуждение возможных тем бакалаврских работ

[Ryukzak]

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

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

Причины, по которым выбрана данный стиль программирования.
- Наличие строгой математической модели в основание (лямда исчисление). Согласно которой можно строить вычислительный процесс.
- Высокая степень надежности кода, написанного на данных языках. (Это связано с тем, что все функции в системе, представляют из себя "чёрные ящики")
- Высокая скорость разработки.

В рамках бакалаврской работы планируется помимо описание проделанной работы и описанных выше пунктов.
- Описание основ лямбда исчисление.
- Написание модели интерпретатора гипотетического языка программирования, в котором будут реализованы все необходимые функции. На интерпретаторе будет проводиться моделирование исполнения кода. В частности соответствие формул реальной ситуации. (по сути, планируется что он будет представлять из себя специфическую форму лямбда абстракции, с возможностью именования функций.)

Хотелось бы услышать комментарии подобной задумки. Её осмысленности.

Уже существуют некоторые мысли на предмет реализации данных вещей, но пока они ещё слишком "сырые" для их изложения.

В качестве дальнейшего развития данной идеи может послужить создание интерпретатора байт кода гипотетического языка для одного из стендов SDK.

[Соратник слонопотама]

чо это?

[Интегральный вычислитель]

О, ФП рвется в массы

Тема достаточно интересная, с точки зрения теории, но на практике вряд ли реализуема. Хотя, как мне кажется, задачи управления, решаемые встроенными системами, хорошо ложатся на математическую модель лямбда исчисления.

[Ryukzak]

чо это?

К чему относится данный вопрос? К посту в целом? К его описанию интересующей темы для бакалаврской?

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

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

Преимущества, которые с моей точки зрения может принести применение этого стиля:
- возможность анализируя программный код получить корректную информацию о времени исполнения той или иной функции в зависимости от характера входных данных.
- в случае если возможно многопоточное исполнение, возможно распараллевание на ходу.
- остальные положительные стороны функционального программирования.

Надеюсь в этот раз удалось удачно изложить мысль.

О, ФП рвется в массы

Тема достаточно интересная, с точки зрения теории, но на практике вряд ли реализуема. Хотя, как мне кажется, задачи управления, решаемые встроенными системами, хорошо ложатся на математическую модель лямбда исчисления.

А почему вряд ли реализуемая? Есть же примеры так называемых редукционных вычислительных машин в которым оно реализовано практически в чистом виде. Увы, ничего кроме общего описания принципов работы данных систем я не видел.

[Интегральный вычислитель]

А почему вряд ли реализуемая? Есть же примеры так называемых редукционных вычислительных машин в которым оно реализовано практически в чистом виде. Увы, ничего кроме общего описания принципов работы данных систем я не видел.

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

[Ryukzak]

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

Мне представляется возможным достаточно сильно минимизировать затраты памяти на глубокие рекурсии, при помощи сочетания карирования и лени. (во время обработки больших линейных структур, при уходе в рекурсию в памяти можно свезти все хранимые данные к самой функции и хвосту элементов. В случае если идёт сборка воедино списков, аналогично.)

Аналогично, представляется возможность реализации циклов без огромного нагромождения в стеке.

А выделение памяти, возможно реализовать минуя использование сборщика мусора, так как все данные находятся в структуре исполняемого кода (которая динамически изменяется), и нет необходимости хранить какие-то данные, в другом месте. (А если и есть, то они статические) Дефрагментация не должна создавать сильные проблемы, так как все функции есть функции от 1-ой переменной, а следовательно, все функции могут быть расположены в простых таблицах, не требующих изысков при индексирование.

Поэтому практическое применение лямбда исчисления станет возможным, только если появится соответствующая аппаратура

Быть может я ошибаюсь, но мне кажется, что необходимое можно реализовать на ПЛИС. Если конечно я правильно представляю то, о чём говорю и его назначение (в основном не уверен именно в нём). Ведь само по себе лямбда исчисление достаточно просто, а следовательно возможно реализовать простой интерпретатор и быстрый интерпретатор. Вопросы же, где применить ленивые вычисление, а где жадное можно отдать компилятору.

Аналогично и с программной реализацией.

простых виртуальных машин типа IEC61131-3

Я правильно понял что это стандарт для виртуальной машины?

[Интегральный вычислитель]

А выделение памяти, возможно реализовать минуя использование сборщика мусора, так как все данные находятся в структуре исполняемого кода (которая динамически изменяется), и нет необходимости хранить какие-то данные, в другом месте.

Не понимаю что такое "динамически изменяющаяся структура исполняемого кода"

Быть может я ошибаюсь, но мне кажется, что необходимое можно реализовать на ПЛИС. Если конечно я правильно представляю то, о чём говорю и его назначение (в основном не уверен именно в нём). Ведь само по себе лямбда исчисление достаточно просто, а следовательно возможно реализовать простой интерпретатор и быстрый интерпретатор. Вопросы же, где применить ленивые вычисление, а где жадное можно отдать компилятору.

Затрудняюсь что-либо ответить. Мне пока сложно представить как должен работать такой специализированный вычислитель.

простых виртуальных машин типа IEC61131-3

Я правильно понял что это стандарт для виртуальной машины?

Стандарт для программирования промышленных контроллеров.

[Ryukzak]

динамически изменяющаяся структура исполняемого кода

Имелось в виду что в памяти стоит хранить только некоторую общность из лямбда термов. Каждый терм может представлять из себя либо переменную, либо константу, либо комбинацию (f(x) где f - изначально существующая функция), либо абстракцию (\x.f где f - некоторая функция, а x - свободная или связанная переменная). Подобная структура может быть представленна в виде бинарного дерева, причём бинарное дерево не может иметь "петли". Сам процесс выполнения программы сведён к редукции данного графа по заданным правилам. В результате теряется понятие исполняемого кода (это всего лишь изначальное состояние графа) и данных, так как они объеденены в единую сущность.

[Соратник слонопотама]

К чему относится данный вопрос? К посту в целом? К его описанию интересующей темы для бакалаврской?

Этот вопрос относится к тому, что не все здесь такие наукоёмкие =) Хотелось бы увидеть какой-нибудь простой пример (или ссылку на таковой) применения λ-исчисления, из которого бы явно следовали преимущества применения этого метода (ведь откуда-то взялась эта тема?). Также хочу заметить, что именно наличие простого и понятного примера сыграет значительную роль на защите бакалаврской; если же цель работы - поговорить о боге с использованием заумных абстракций, то перспективность оной внушает сомнения ))) И вообще, не поздновато ли выбирать тему бакалаврской в конце марта? Или это на будущий год только? )

[Ryukzak]

Хотелось бы увидеть какой-нибудь простой пример (или ссылку на таковой) применения λ-исчисления, из которого бы явно следовали преимущества применения этого метода (ведь откуда-то взялась эта тема?).

Привести простой и короткий пример здесь довольно сложно. Пожалуй наиболее классический пример выразительности лямбда исчисления - сортировка методом Хоара. [url]http://ru.wikipedia.org/wiki/Быстрая_сортировка[/url]
Стоит взглянуть на пример реализации приведённый на языке Haskell (чистый функциональный язык, который максимально близок лямбда ичислению, на сколько я сейчас могу судить). В принципе код на этом языке можно записать в чистом лямбда исчисление.

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

Крайне гибкая система типизации. Суть этого заключается в том, что у нас нет необходимости дублировать функции в зависимости от данных, к которым они применяются. К примеру для метода Хоара можно внести такое изменение в код.
qsort [] _ _ = []
qsort (x:xs) f1 f2 = qsort (filter (f1 x) xs) f1 f2 ++ [x] ++ qsort (filter (f2 x) xs) f1 f2
Где функции f1 и f2 - всего функции сравнения для требуемых типов данных. Или же возможно реализовать автоматическую выборку операций сравнения, если все данные тегировать. (в таком случае необходимо будет ввести понятие класса типа, где каждый тип данных в ходящий данный класс обязан будет иметь определённые функции) Подробнее о типизации можно прочитать в книгах по Haskell, в частности Душкин "Функциональное программирование на языке Haskell"

Высокая степень анализа кода на этапе компиляции. Это может позволить отловить огромное количество ошибок связанных с типизацией и проанализировать поведение программы во время исполнения (количество необходимой памяти, время исполнения).

Возможность применения ленивых [url]http://ru.wikipedia.org/wiki/Ленивые_вычисления[/url]. Это может сильно понизить количество выполняемых операций и уменьшить затраты памяти (стоит заметить не во всех случаях). Так же это позволяет использовать достаточно красивые конструкции бесконечных последовательностей во время программирования.

Лямбда исчисления не требует линейной последовательности при обработке. А следовательно, позволяет распаралеливать вычислительные процессы на этапе выполнения. Причём в данном случае не возникает проблем синхронизации, так как принцип аналогичен принципу распаралеливания рандеву.

Программа написанные на лямбда исчисление представляют из себя группы математических формул. А следовательно, к ним применимы все математические методы анализа. Так же математическая запись крайне элегантна.

В отличие от традиционного представления математических формул, существует возможность работы с функционалами (функциями которые могут использовать в качестве аргументов другие функции/функционалы и возвращать функции/функционалы как результаты). Это может сократить рассуждения в башню экспонент раз (Непейвода "основания программирования"). А следовательно, сложность описываемых алгоритмов заметно снижается.

Возможность записи лямбда исчисление через комбинаторную логику. Что позволяет решить многие проблемы вычисления лямбда выражений, и свести все используемые операции к простейшим. Что в конечном итоге может позволить реализовать всё на аппартном уровне.

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

если же цель работы - поговорить о боге с использованием заумных абстракций, то перспективность оной внушает сомнения

В работе большее внимание хотелось бы уделить именно теории. А практическое рассмотрение вопроса свезти к написанию модели вычислителя, работающего по проработанным принципам, и компилятора для него, что бы была возможность проанализировать теорию на практике.

И вообще, не поздновато ли выбирать тему бакалаврской в конце марта? Или это на будущий год только? )

Будущий год.

[Соратник слонопотама]

Насчет сути я ничего сказать не могу, зато могу сказать по поводу всего остального. Мне кажется, это довольно жёсткая тема для бакалаврской Если серьезно подходить к делу с расчетом получить полезные результаты, а не очередное никому не нужное бумагомарание, которое будет выброшено в мусорку сразу после защиты (как огромное количество бакалаврских, магистерских и т.д.), то, очевидно, потребуется серьезное напряжение и куча времени. Если учесть, что написание бакалаврской совмещено с учебой, то времени будет мало, даже если ты не работаешь. Реально оценивая опыт поколений, могу сказать, что существует большая вероятность того, что к "часу Ч" работа будет не готова, и придется городить потемкинские деревни, чтобы защититься (подгонять результаты, заменять исследования на копи-пэйст из популярной литературы и т.д.). Поэтому, если есть желание заниматься этим делом, то, во-первых, надо бы сделать реальный план работ (со сроками, для самоконтроля), да таким образом, чтоб каждый этап был относительно обособлен и пригоден для предъявления начальству в хоть сколько-нибудь законченом виде, во-вторых, умножить все эти сроки на три (коэффициент, приблизительно отражающий влияние непредвиденных обстоятельств на работу ), в-третьих, хоть как-нибудь сбалансировать теорию и практику, чтоб не остаться и без того, и без другого. Если действовать таким образом, то всегда можно будет сказать: вот мой план, вот то-то и то-то я сделал, вот результаты, а вот это я не успел, но продолжу при написании магистерской/инженерской

З.Ы. Ну и конечно всё, что претендует на научность, для кафедральных профессоров - как красная тряпка для быка

З.З.Ы. Кстати, не дурно было бы в качестве руководителя найти какого-нибудь ненормального математика из нормального универа

[kluchev]

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

[Ryukzak]

Если серьезно подходить к делу с расчетом получить полезные результаты, а не очередное никому не нужное бумагомарание

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

Время, в принципе есть. По поводу поставить сроки - прекрасно понимаю, что в любом случае требуется. В принципе, основываясь на словах Довгого и Платунова, просто теоретическое рассмотрение вопроса уже должно потянуть на приличную бакалаврскую.

[url]З.Ы. Ну и конечно всё, что претендует на научность, для кафедральных профессоров - как красная тряпка для быка [/url]

В данном случае довольно сложный вопрос, так как в данную область серьёзно врятли кто-то закапывался. Да и имхо довольно спорно, насколько это научность. Просто работа планируется в рамках отдельно взятого раздела логики (дискретной матиматики или чего-то ещё).

[url]З.З.Ы. Кстати, не дурно было бы в качестве руководителя найти какого-нибудь ненормального математика из нормального универа [/url]

А к кому из наших преподавателей можно податься? В принципе хотелось бы к Ключеву, тк понравился его стиль работы, но создалось впечатление, что он излишне безучастен в подобных вопросах. Предлагал Довгий к ниму пойти с темой о "Редукционных ЭВМ", что есть некоторая часть интересующего вопроса. Может есть кто-то более близкий к интересующей теме?

[url]Бакалаврская работа - квалификационная работа, решение задачи в бакалаврской не цель, а средство.[/url]

А насколько может быть критично для результата защиты, если по итогу работа придёт к выводу, что подобная модель малоэффективна в данной отрасли? Ведь отрицательный результат, тоже результат вроде как...

[kluchev]

А к кому из наших преподавателей можно податься? В принципе хотелось бы к Ключеву, тк понравился его стиль работы, но создалось впечатление, что он излишне безучастен в подобных вопросах.

Я не безучастен, просто я банально устал

А насколько может быть критично для результата защиты, если по итогу работа придёт к выводу, что подобная модель малоэффективна в данной отрасли? Ведь отрицательный результат, тоже результат вроде как...

Отрицательный результат - тоже результат. Вопрос только в глубине проработки. Мне кажется, что ответ на вопрос такого уровня тянет на докторскую диссертацию.
(c) "А мужики то и не знают..."

[Соратник слонопотама]

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

А насколько может быть критично для результата защиты, если по итогу работа придёт к выводу, что подобная модель малоэффективна в данной отрасли? Ведь отрицательный результат, тоже результат вроде как...

я думаю, что ничего криминального в том, что ты берешься за какое-никакое исследование и не знаешь, какие получишь результаты. однако, если скажешь, что подобная модель малоэффективна, приготовь весомые аргументы =)))

просто теоретическое рассмотрение вопроса уже должно потянуть на приличную бакалаврскую

им виднее.... я и сам бы почитал, если было бы нармальна написано

В данном случае довольно сложный вопрос, так как в данную область серьёзно врятли кто-то закапывался. Да и имхо довольно спорно, насколько это научность. Просто работа планируется в рамках отдельно взятого раздела логики (дискретной матиматики или чего-то ещё)

да как ты не понимаешь, что то, что они ничего в этом, возможно, не понимают - это и есть твой самый страшный грех )))) насчот научности... если ты в бакалаврской ограничишься теоретическим рассмотрением вопроса на сегодняшнем уровне развития - это одно, если начнешь строить какие-то модели и что-то на них изучать - совсем другое ))

А к кому из наших преподавателей можно податься? В принципе хотелось бы к Ключеву, тк понравился его стиль работы, но создалось впечатление, что он излишне безучастен в подобных вопросах. Предлагал Довгий к ниму пойти с темой о "Редукционных ЭВМ", что есть некоторая часть интересующего вопроса. Может есть кто-то более близкий к интересующей теме?

Может и есть, надо искать среди программистов - на ИТиПе или на кафедре ИПМ (не к ночи будь помянута). По слухам, с большой вероятностью лямбда-исчислением занимаюца на кафедре информатики мат-меха ЛГУ (у меня приятель там на соседней кафедре аспирант), можешь попробовать поискать там, если не боишься )))) http://www.math.spbu.ru