Заметки о преподавании парадигм программирования1

Вид материала

Статья

Содержание Императивная парадигма программирования Функциональная парадигма программирования Логическая парадигма программирования

Подобный материал:

• Программа вступительного экзамена в магистратуру по образовательной программе 040200., 204.37kb.
• Омерзительная Америка Заметки украинского эмигранта, 329.64kb.
• Интерпретация научных парадигм как языковых игр, 134.82kb.
• «Применение информационных технологий в преподавании английского языка», 353.53kb.
• Интегративный подход в преподавании курса, 80.22kb.
• «Вы привыкли работать в ненормированном рабочем дне, не так ли?», 47.97kb.
• Конференция массовые коммуникации: интеграция научных парадигм (12 марта 2012 года,, 21.79kb.
• Учебно-тематический план программы курсов повышения квалификации «Русская филология:, 18.49kb.
• Н. Д. Потапова “Что есть истина?”: критика следственных показаний и смена исторических, 786.3kb.
• Книга Ф. И. Буслаева «О преподавании отечественного языка» (1844 г.), 40.2kb.

Заметки о преподавании

парадигм программирования¹

Шилов Н.В.

Введение

Поводом для этих заметок послужила статья в журнале для старшеклассников и учителей «Потенциал», в которой (по мнению автора и редакции журнала) «в сжатой форме рассказывается про функциональный подход к описанию вычислительных процессов ..., а также про применение этого подхода в информатике в функциональной парадигме программирования» с примерами функциональных программ на языке Haskall [Душкин, 2009]. Цель благая тем более, что на русском языке фактически нет научно-популярной литературы по функциональному программированию и другим парадигмам программирования, отличным от императивного.

Такая цель не могла оставить равнодушным, так как автору данных заметок приходится знакомить с понятием о разных парадигмах программирования (включая функциональное программирование) студентов-математиков разного уровня: от первого курса до магистратуры. Но трудно передать меру разочарования, которое пришлось испытать после знакомства со статьей: так НЕЛЬЗЯ знакомить ни школьников, ни учителей, ни студентов с функциональным программированием. В этой статье не объяснено ни что такое «парадигма программирования», ни что существуют десятки парадигм программирования, ни основы синтаксиса и семантики языка Haskell (ни кто такой Haskell Carry), ни слова не сказано про другие функциональные языки программирования...

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

О парадигмах программирования

Согласно Т. Куну [Кун, 2003], парадигма – это метод, подход к формулировке задач (проблем) и путей их решения. Само слово «парадигма» греческого происхождения и означает «пример», «образец», а в общефилософском смысле обозначает категорию, состоящую из сущностей с общими характеристиками.

Первым, кто явно ввел в употребление понятие «парадигма программирования» был Роберт Флойд в лекции в 1978 г. по случаю присуждения ему премии им. Тьюринга [Флойд, 1993]. По-видимому, ранее это понятие использовалось в компьютерных науках лишь эпизодически. По крайней мере, в своей лекции сам Р. Флойда ссылается только на известную диссертацию Т. Куна по философии науки вообще, которая была опубликована в 1970 г.

Широко известен плакат History of Programming Languages, подготовленный издательством O’REILL². Полная версия плаката имеет длину около 6м и содержит сведения о хронологии и влиянии друг на друга 2500 языков программирования и отражает хронологию и взаимное влияние друг на друга наиболее значимых языков программирования. Хронология на этом плакате представлена осью времени (в верхней части плаката), влияние языков друг на друга – цветными линиями.

Заметим, однако, что этот плакат можно принять за основу «путеводителя» в мире языков программирования лишь на начальном этапе становления программирования и информационно-вычислительных технологий (первые 10-15 лет начиная с 1950 г.). В это время компьютерных языков было немного, и почти все они³ были языками императивного программирования фон-неймановских вычислительных устройств. Поэтому за основу классификации в этот период можно было принять хронологию появления и взаимного влияния языков.

Но уже с конца 1960-х годов путеводитель в стиле плаката O'REILLY становится неприемлемым, так как в это время наряду с языками последовательного императивного программирования появились языки параллельного программирования, языки декларативного программирования (прежде всего продукционного и функционального); в середине 1970-х – начале 1980-х годов родилось несколько новых «программирований» – логическое и объектно-ориентированное в том числе.

Для специалистов очевидно, что все перечисленные «программирования» – это (в соответствии с Т. Куном и Р. Флойдом) исторически сложившиеся парадигмы программирования, т. е. разные способы ставить и решать задачи. Однако для студентов, начинающих изучение программирования, знакомых только с одним-двумя языками императивного программирования, все другие (кроме императивного) способы постановки и решения программистских задач просто неведомы. Необходимость знакомить их с многообразием парадигм программирования диктуется как соображениями истории науки, технологии и техники, так и более важными причинами.

Это, прежде всего, содействие в выборе языка программирования из существующих для новых проектов в области информационных систем и технологий; разработка новых языков, отвечающих новым потребностям и парадигмам⁴; и, наконец, образование.

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

Такой разный факториал

Теперь мы кратко познакомим с опытом преподавания понятия о парадигмах программирования на первом курсе Механико-математического факультета Новосибирского государственного университета. Курс программирования читается во втором семестре, базовый язык программирования Си, другие языки не изучаются. Однако понятие императивного Pascal-подобного псевдокода вводится на самой первой лекции для документирования алгоритмов, которые потом предстоит кодировать на семинарских и практических занятиях на языке Си. А на второй лекции студенты знакомятся с некоторыми другими парадигмами программирования и соответствующим им вариантам псевдокода.

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

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

Императивная парадигма программирования

• «Императивный» - от латинского «командный».
  
• Императивная постановка задачи: факториал натурального числа n – это произведение всех натуральных чисел от 1 до n.
  
• Императивный псевдокод состоит из команд (операторов над памятью):
  

1: var n, f : integer ;

2: input(n) ;

3: f:= 1 ;

4: if n = 1 then goto 8 ;

5: f:= f*n ;

6: n:= n-1 ;

7: goto 4 ;

8: output(f) ;

9: end.

• Команды преобразуют «ячейки памяти» ЭВМ.
  
• Запуск императивной программы соответствует размещению ее в памяти и последовательному исполнению команд начиная с первой.
  
• Например, вычисление факториала числа 3 может быть представлено следующей последовательностью моментальных состояний памяти ЭВМ:
  

Номер ячейки	1 - для номера команды	2	3	...	...	...
Момент времени
1	1	выделена для n	выделена для f	Свободная память
2	2	3	выделена для f	Свободная память
3	3	3	1	Свободная память
4	4	3	1	Свободная память
5	5	3	3	Свободная память
6	6	2	3	Свободная память
7	7	2	3	Свободная память
8	4	2	3	Свободная память
9	5	2	6	Свободная память
10	6	1	6	Свободная память
11	7	1	6	Свободная память
12	4	1	6	Свободная память
13	8	1	6	Свободная память
14	9	Свободная память

Функциональная парадигма программирования

• В функциональной парадигме постановка задачи и решение задачи – определения функции, а вычисление – это цепочка равенств, где каждое следующее получается из предыдущего в результате применения функции к аргументу (или аргументам).
  
• Функциональная постановка задачи: факториал – это функция F, которая каждому натуральному числу сопоставляет натуральное число и удовлетворяет следующему тождеству:
  

F(x) = если x=1 то 1 иначе x*F(x-1).

• Функциональный псевдокод состоит из одного определения функции F, но включает два «клауза»:
  

F : 1  1 ;

x  x* F(x -1) .

• Приведённая программа означает, что если конкретное значение аргумента функции F может быть отождествлено с 1, то значение функции F на этом аргументе равно 1; в противном случае надо значение функции F на этом аргументе равно значению аргумента, умноженному на значение функции F на декременте⁶ аргумента.
  
• Никаких ячеек памяти нет, но есть память, в которой хранится функциональная программа.
  
• Вызов функциональной программы состоит в применении одной из функций программы к конкретному значению аргумента.
  
• Вычисление вызванной функциональной программы – это цепочка равенств, начинающаяся с вызова этой программы, заканчивающаяся значением.
  
• Например, вычисление факториала числа 3:
  

F(3) = (3 нельзя отождествить с 1, но можно с x) =

= 3 * F(3 – 1) = 3 * F(2) = (2 нельзя отождествить с 1, но можно с x) =

= 3 * (2 * F(2 – 1) ) = 3 * (2 * F(1) ) = (1 отождествимо с 1) =

= 3 * (2 * 1 ) = 3 * 2 = 6.

Логическая парадигма программирования

• В логической парадигме постановка задачи и решение задачи – аксиоматическое определение отношения между аргументами и результатами, а вычисление – это поиск доказательства.
  
• Логическое определение факториал: отношение P(m, n)  «число m является факториалом числа n» определяется следующими двумя аксиомами:
  

P(1, 1) ;

P(m/n, n-1)  P(m, n).

• Функциональный псевдокод состоит из одного факта и одного правила:
  

P (1 1) ;

P(m, n) :: P(m/n, n-1).

• Вызов логической программы – это один из предикатов этой программы, в который подставлены значения некоторых аргументов (т. е. фактические параметры вместо формальных), а значения некоторых аргументов предстоит определить так, что при их подстановке получится утверждение, доказуемое в аксиоматике, соответствующей этой логической программе.
  
• Унификация двух выражений, в логическом программировании – это подбор значений переменных в этих выражениях, при котором оба выражения синтаксически совпадут.
  
• Вычисление по логической программе – это это поиск «кратчайшего» доказательства с использованием унификации. Никаких ячеек памяти нет, но есть память, в которой хранится сама логическая программа.
  
• Например, вычисление факториала числа 3:
  

P(m, 3) :: P((m/3), 3 – 1) так как P(m, 3) невозможно унифицировать с фактом P(1, 1) :: P((m/3), 2) так как (3-1) есть 2 :: P(((m/3)/2), 2 – 1) так как P((m.3), 2) невозможно унифицировать с фактом P(1, 1) :: P(((m/3)/2), 1) так как (2-1) есть 1 :: ((m/3)/2) может быть 1 так как P(((m/3)/2), 1) можно унифицировать с фактом P(1, 1) :: (m/3) может быть 2 поскольку ((m/3)/2) может быть 1 :: m может быть 6 поскольку (m/3) может быть 2.

Вместо заключения

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

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

Многообразие компьютерных языков является распределенным хранилищем научного знания о парадигмах, опыте и истории применения информационных технологий. Для усвоения студентами этого знания необходимо иметь разумную систему классификации компьютерных языков и парадигм, с современной технической поддержкой. Подход к созданию такой классификации, основанный на построении открытой темпоральной прикладной онтологии предметной области компьютерных языков, намечен в работах [Андреева и др., 2008] и [Anureev at al., 2008].

Литература

[Душкин, 2009] Душкин Р.В. Функциональный подход в программировании. Потенциал, 2009, №8, стр.47-55.

[Кун, 2003] Кун Т. Структура научных революций. Издательство АСТ, 2003.

[Флойд, 1993] Флойд Р. О парадигмах программирования. В кн.: Лекции лауреатов премии Тьюринга. М: Мир, 1993.

[McCarthy, 1960] McCarthy J. Recursive Functions of Symbolic Expressions and Their Computation by Machine. Communications of ACM. 1960, v.3 (4).

[Андреева и др., 2008] Андреева Т.А., Ануреев И.С., Бодин Е.В., Городняя Л.В., Марчук А.Г., Мурзин Ф.А., Шилов Н.В. Компьютерные языки как форма и средство представления, порождения и анализа научных и профессиональных знаний. Труды XV Всероссийской научно-методической конференции «Телематика-2008». Санкт-Петербург. 2008.

[Anureev at al., 2008] Anureev I.S., Bodin E.V., Gorodnyaya L.V., Marchuk A.G., Murzin F.A., Shilov N.V. On the Problem of Computer Language Classification. Joint NCC&IIS Bulletin, Series Computer Science. 2008, v. 27.