И.Г. Головин - Конспект лекций по курсу Языки программирования (1161120), страница 3
Текст из файла (страница 3)
Бэкус доказал, что такое разделение кода является источником очень высокойсложности языков программирования. В качестве альтернативы он предложилфункциональный стиль программирования – вообще без переменных, то есть без операцийприсваивания и без возможности присвоения данным имен.В качестве возражения тезисам Джона Бэкуса можно указать, что неимперативныепрограммы «более естественны» с аппаратной точки зрения.В последнее время функциональная парадигма возвращается в индустриальноепрограммирование. Объясняется это тем, что функциональная парадигма позволяетэффективно распараллелить вычисления.В 2006 году мощным процессором считался Intel Pentium 4 с тактовой частотой 4.06 ГГц.Сейчас, в 2012 году, частота мощных процессоров остается примерно той же, и повышениепроизводительности достигается за счет проведения вычислений параллельно нанескольких ядрах.ЗамечаниеСуперкомпьютер – это такой компьютер, который всего на однопоколение отстает от потребностей физиков.Однако, следует помнить, что у распараллеливания существуют ограничения.С параллельными вычислениями тесно связано понятие ленивых вычислений вфункциональных языках программирования.Пример (Lisp)(fun 1 arg1 … argN)Суть ленивые вычислений: arg вычисляется только тогда, когда он необходим.Таким образом, можно гарантировать, что аргументы независимы, а значит, их можновычислить параллельно.
В императивных же программах такие гарантии сложнееобеспечить из-за возникающих зависимостей между частями кода.Императивное программирование практически достигло предела возможногораспараллеливания.Заметим, что технологические аспекты часто не играют решающей роли прираспараллеливании чего-либо.Следующий язык, который мы рассмотрим в качестве примера – язык REFAL.12Пример (REFAL)Это единственный язык, который широко известен во всем мире ибыл придуман в СССР.Первая версия REFAL была создана в качестве метаязыка дляописания семантики других языков. Впоследстви он стал находитьпрактическое использование в качестве языка программирования.Семантика языка Рефал описывается в терминах виртуальноймашины, называемой «рефал-машина».
Машина имеет поле зрения, вкотором может находиться произвольное рефал-выражение, несодержащее рефал-переменных.Функции в базисном REFAL:имя {правило1правило2…правилоN}Правило состоит из образца и шаблона.На вход функции подаётся некоторое выражение; вычислениефункции состоит в сопоставлении выражения поочерёдно образцам,взятым из правило1, правило2, …, правилоN. Если очередноесопоставление проходит успешно, то на основании шаблона, взятогоиз того же предложения, формируется новое Рефал-выражение,которое и будет результатом функции.Образец состоит из скобок и переменных.Переменные, описываемые в образцах, описываются следующимобразом:s.1– один символ;v.1– произвольное непустое выражение;e.1– произвольное выражение.Язык REFAL можно использовать для XML-преобразований.Рассмотрим теперь наш стандартный пример на языке REFAL.Пример (REFAL)13reverse1 {s1 e1 = reverse1<e.1> s.1;=;}Вызов этой функции осуществляется так:$ENTRY GO {= Prout <reverse1<card>>;}ЛОГИЧЕСКАЯ ПАРАДИГМАЛогическую парадигму рассмотрим на примере, пожалуй, самого известного логическогоязыка – языка Prolog.Пример (Prolog)Prolog был изобретен в 1971 году.Prolog основана исчислении предикатов – исчислении высказыванийдля функций.Программы на Prolog оперируют с понятием факта.man(SOKRAT).SOKRAT является man.
man – предикат.∀ X p(X) ∈ p1(x) ∧p2(x) ∧…pn(x)Правила в Prolog формулируются следующим образом:p(x):- p1(x), p2(x), …, pn(x).и читаются так: p(x) истина, если p1(x), p2(x), …, pn(x)истина.Такие правила называются Хорновскии клаузами или дизъюнктамиХорна.?: - pp(x)Непоянтно, как доказать истинность этого предложения.Сложность вычислений линейно зависит от размера входных данных.Это означает, что существует линейный алгоритм определенияистинности.MAN(SOKRAT).MORTAL(X):-MAN(X)14?:-MORTAL(SOKRAT)Эта программа определяет, верно ли MORTAL(SOKRAT).В Prolog есть понятие списка.[a,b,c][a|b, c] ~ [a, b | c] ~ [a, b, c | [] ]| – символ для разделения головы и хвоста списка.append(l1, l2,l3)append([a,b],[c],[a,b,c])ответ: yes?:-append([a,b],[a,b|x], [a,b,c])ответ: no?:-append([a,b],[x|c], [a,b,c])ответ: no?:-append([a,b],[c|x], [a,b,c])ответ: []В процессе вычисления происходят отождествления, которые ивыводятся.Рассмотрим теперь наш пример на языке Prolog.reverse1([],[]).reverse1([x|y],z) :reverse1(y,w),append(w, x, z)?:-reverse1([a,b,c],x)Результат: [c, b, a]Существует множество подпарадигм в рамках вышеназванных Например, многие ЯПявляются мультипарадигменными.Пример (Lisp)SET,SETQ – процедурная составляющая языкаCLOS – объектно-ориеннтированное расширение).Будем рассматривать и говорить в основном об императивной и объектноориентированной парадигме, рассматривая языки C++, Java, C#.ПАРАЛЛЕЛЬНАЯ ПАРАДИГМАCSP – описание взаимодействия между параллельными процессами.15Почему не говорим про параллельные парадигмы?1.
Их будем рассматривать в других курсах2. При обсуждении параллельных парадигм возникает вопрос: что являетсяфундаментальным знанием? CSP реализует одну парадигму, Ocaml реализует другуюпарадигму, другие понятия. В параллельном программировании ещё не устоялисьуправляющие структуры. Фундаментальное знание выделить нельзя.Существует два подхода к параллельному программированию1.
Программист не задумывается о том, как распараллеливать программу.Здесь возникает вопрос: а должны ли мы учитывать особенности кэш-памяти идругие особенности машинной архитектуры? Например, есть мнение, что спискивообще не стоит использовать в программах, так как «наивная» реализация списковне адаптирована под кэш-архитектуру современных процессоров (часто возникаюткэш-промахи).2. Создание специальных библиотек и средств, чтобы сразу программировать напараллельность и явно использовать эти средстваС распараллеливанием связан критический прорыв в эффективности и производительностипрограмм.В программировании мы всё дальше и дальше уходим от свойств архитектуры, поэтомулогичнее первый подход: программист должен иметь возможность не работать спараллелизмом.Существует множество неразрешимых проблем при распараллеливании процедурныхпрограмм. Вообще, параллельное программирование для машин фон-неймановскойархитектуры является чрезвычайно сложным.Одна из важных задач – распараллеливание программ на языке FORTRAN для физиков.Другая важная задача – автоматическое распараллеливание, которое сильно усложняетпрограмму (процессоры INTEL распараллеливают вычисления на уровне выполненияпрограммы).Заметим, что если проводить вычисления на n процессорах, то выполняться не в n разбыстрее, а несколько медленнее, потому что существуют издержки на синхронизациюпроцессов.Возникает вопрос: какими должны быть средства, которые позволяют не задумываться опараллельном программировании? Для этого хорошо подходят функциональные языки.F(expr1, expr2, …, exprN) – можно вычислять параллельно, так как отсутствуетпонятие состоянияF(c++, a[i]) – результат зависит от того, в каком порядке выполнять.В функциональной парадигме отсутствует понятие состоянияВ языке Java есть замыкание.В замыкание могут входить только переменные которые потом не изменяют свое значение– это сделано для распараллеливания.16Существует понятие ленивые вычисления.
Ленивые вычисления вычисляются только тогда,когда есть необходимость в их.С помощью ленивых вычислений можно моделировать бесконечную последовательность(Python).В рамках процедурной парадигмы существует объектно-ориентированная парадигма.Чаще всего будем говорить о языках объектно-императивной парадигмы.Понятие «оператор» – характерно только для императивной парадигмы, понятия «данные»,«операция» – ко всем.ПРОБЛЕМНЫЕ ОБЛАСТИБудем сужать область рассмотрения по степени отчуждаемости результатапрограммирования.По-другому это можно сформулировать так: кому нужен результат программирования, ктобудет его использовать?ИГРОВОЕ ПРОГРАММИРОВАНИЕЗаметим, что игровое программирование не следует путать с программированием в игровойиндустрии.Игровое программирование другими словами – это программирование для себя.Частным случаем является программирование студентов – нет дальнейшего использованияпрограммы.
Реальные программы будут читаться другими программистами. Студенческиепрограммы просматривает преподаватель.Самым популярным языком для игрового программирования был BASIC. Его особаяпрелесть для игрового программирования – строчка вводилась, непосредственноинтерпретировалась и выполнялась, таким образом позволяя интерактивно исследоватьязык и обучаться ему.Пример (BASIC)Интерпретатор BASIC позволяет работать в интерактивномрежиме. Это интерпретируемый язык с инкрементной трансляцией.LET x = 5PRINT XFOR I=1, N----NEXT IНАУЧНОЕ ПРОГРАММИРОВАНИЕ17Это программы, которые пишутся в научных, исследовательских целях. Программированиес целью получения результата – после получения результата сама программа обычностановится не нужна.Степень отчуждаемости больше, чем при игровом программировании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
