Современные языки программирования и платформа .NET: Лабораторные работы по курсу. I семестр

Министерство образования Российской Федерации Московский инженерно-физический институт (государственный университет) Факультет “Информационная Безопасность” Кафедра “Криптология и Дискретная математика”

Лабораторные работы по курсу «Современные языки программирования и платформа .NET» I семестр

Москва - 2003

2

СОДЕРЖАНИЕ Введение

3

Процедура установки SML.NET

4

Лабораторная работа 6. Базисные типы. Стандартные функции

6

Лабораторная работа 2. Функции SML для основных комбинаторов

12

Лабораторная работа 3. Рекурсивные вычисления

15

Лабораторная работа 4. Функции для синтаксического разбора простых языковых конструкций 19 Лабораторная работа 5. Реализация категориальной абстрактной машины

23

Лабораторная работа 6. Редукция ламбда-термов

26

Список литературы и учебных материалов

28

Приложение 1. Особенности инсталляции интегрированной разработки Visual Studio .NET

среды 29

3

Введение Целью данного практикума является получение практических навыков прикладного программирования, закрепление знаний, полученных на теоретической части курса, а также знакомство с платформой Microsoft .NET. Для выполнения лабораторных работ в рамках первого семестра необходимо следующее программное обеспечение: 1) 32-разрядная операционная система Microsoft Windows 98, ME, 2000, XP, 2003. 2) Интегрированная среда разработки Microsoft Visual Studio .NET 3) Средство разработки SML.NET. Код SML.NET может быть также откомпилирован на следующем программном обеспечении: 1) 32-разрядная операционная система Microsoft Windows 98, ME или 2000, XP, 2003. 2) Платформа разработки Microsoft.NET Framework SDK или Microsoft.NET Framework Redistr. 3) Средство разработки SML.NET.

4

Процедура установки SML.NET Для установки SML.NET в интегрированную среду разработки Visual Studio.NET требуется: 1. Распаковать файлы архива smlnet.tar.gz в директорию, куда Вы хотите установить компилятор SML.NET (например, C:\smlnet) 2. Запустить файл install.exe в корневой директории компилятора. (Внимание! После выполнения данной процедуры нельзя перемещать файлы компилятора в другую директорию для обеспечения корректной работы среды разработки) 3. Выполнить повторный вход в систему (в отдельных случаях может понадобится перезагрузка системы) для принятия изменений в переменных окружения. После выполнения данных процедур в меню создания проектов Visual Studio должен появиться выбор проектов SML.NET:

Для проверки правильности установки откройте пример решения, находящийся по адресу “Директория, где установлен компилятор SML.NET”/vs/demo/Life/Demo.sln и выполните его сборку В текущей версии поставки перед выполнением сборки демонстрационного примера необходимо вручную указать тип проекта –

5

“Клиент”. Для этого в окне Solution Explorer щелкните правой кнопкой мыши на пункте Client Project и выберите в выпадающем меню пункт Set as Startup Project. При правильной инсталляции сборка должна выполнится без ошибок, и при запуске решения должно появиться окно математической игры “Жизнь”. Для компиляции приложений на SML.NET также возможна установка для работы с .NET Framework. При этом требуется: 1. Распаковать файлы архива smlnet.tar.gz в директорию, куда Вы хотите установить компилятор SML.NET (например, C:\smlnet ) 2. Установить переменную окружения SMLNETPATH = “Директория, где находятся файлы компилятора SML.NET” (например, C:\smlnet ) 3. Добавить к переменной окружения PATH путь к директории с исполняемыми файлами SML.NET (например, C:\smlnet\bin ) Старт компилятора осуществляется запуском файла smlnet.bat находящимся в директории с исполняемыми фалами. Для проверки правильности установки можно ввести следующие команды source demos\sort export Sort make run

6

Лабораторная работа 1 Базисные типы. Стандартные функции Цель работы: Ознакомиться с ядром языка SML, стандартным набором функций, принципом построения функций и типов. Необходимые теоретические сведения: Язык SML изначально являлся интерактивным языком (т.е. при запуске компилятора пользователь получает доступ к командной строке, где введенные выражения немедленно компилируются, вычисляются и отображается результат, после чего был возможен ввод следующего выражения). SML.NET является полноценным .NET-языком и позволяет производить компиляцию программ в исполняемые файлы или динамические библиотеки .dll и создавать экспортируемые классы .NET для использования в проектах на других языках. Естественно, язык поддерживает импорт классов .NET. Функции и типы Функции в языке SML задаются в математическом смысле этого слова. При этом тип может быть как задан в явном виде fun square(x:int) = x*x так и опущен. В последнем случае тип задается неявно на этапе компиляции. Типы в SML образуются из множества базисных типов. Например, функция с аргументом int и результатом string, будет иметь тип int => string. Возможно также задание функции с использованием fn выражения square = fn x => x * x.

val

Базисные типы и функции. • bool – булев тип данных. В модуле bool над ним определены такие операции, как отрицание val not : bool -> bool, конверсия в строку val toString : bool -> string и конверсия из строки val fromString : string -> bool option. • word – тип данных – слово, представляет из себя целое число без знака, и как правило связывается с машинным представлением слова. В соответствующем модуле определены конверсии (например, val toInt : word -> int), арифметические (val + : word *

7

•

•

• •

word -> word) и логические (val > : word * word -> bool) операции. char – символьный тип данных. В модуле char также определены функции конверсии (val toString : char -> String.string) логические (val isDigit : char -> bool) и прочие. real – число с плавающей точкой. В модуле real определены операции преобразования (val toString : real -> string), сравнения (val >= : real * real -> bool), преобразования форматирования и точности (val maxFinite: real). int – целое число. string – строка символов.

Интерфейсные файлы с описанием всех типов данных и функций SML.NET можно найти в директории \src\basis компилятора. Типы, обьекты и методы .NET Таблица 1. Соответствие типов .NET и типов SML Тип .NET Тип C Тип SML.NET System.Boolean Bool bool System.Byte Byte Word8.word System.Char Char char System.Double Double real System.Single Float Real32.real System.Int32 Int int System.Int64 Long Int64.int System.Int16 Short Int16.int System.SByte Sbyte Int8.int System.String String string System.UInt16 Ushort Word16.word System.UInt32 Uint word System.UInt64 Ulong Word64.word System.Exception System.Exception exn System.Object Object object Кроме того, в SML.NET возможно сослаться на любой тип .NET, с использованием стандартного синтаксиса .NET, например, type XMLParser = string -> System.Xml.XmlDocument

8

Следующая программа приводит пример использования типов SML и типов .NET: structure builtintypes_demo = struct fun main () = ( print ( "cosh(1.2) = " ^ Real.toString(System.Math.Cosh(1.2)) ^ "\n"); print ( "System.Int32.MinValue = " ^ Int.toString(System.Int32.MinValue) ^ "\n"); print(valOf(System.Char.GetUnicodeCategory(#"Z").#ToStr ing())) ) end Создание проектов SML.NET в Visual Studio Выберите опцию – New->Project в меню File или в начальном «мастере». В появившемся окне выберите SML.NET Application. После подтверждения выбора система разработки автоматически создаст файлы:

1. Файл исходного кода (расширение .sml). Данный файл содержит сгенерированный оболочкой шаблон программы на SML с объявлением функции main с пустой реализацией.

2. Файл опций компилятора (script.smlnet) . Данный файл содержит опции вызова компилятора, и может быть применен для построения специфических приложений. Дополнительная информация о опциях компилятора содержится в файле Readme.txt, автоматически генерируемом при создании проекта, и в документации к компилятору.

9

Контрольные вопросы 1. В чем состоят основные особенности языка программирования SML? 2. Что понимается под термином «язык функционального программирования»? 3. Что означают слова «интерактивный язык»? 4. Какие возможности доказывают, что реализация языка программирования SML для среды разработки .NET является полнофункциональной? 5. В чем состоит сходство математической функции и функции в языке программирования? 6. В чем состоит различие между математической функцией и функцией в языке программирования? 7. Возможно ли явное описание типа в языке программирования SML? 8. Допустимо ли неявное описание типа в языке программирования SML? 9. Привести пример явного описания типа в языке программирования SML. 10. Привести пример неявного определения типа в языке программирования SML. 11. Что понимается в языке программирования SML под базисным типом? 12. Каким образом в языке программирования SML формируются производные типы? 13. Привести примеры базисных типов языка программирования SML. 14. Привести примеры производных типов языка программирования SML. 15. Привести пример описания данных логического (булева) типа. 16. Перечислить основные операции над логическими данными. Привести пример описания данных целого без знака (слова). 17. Перечислить основные операции над данными типа целое без знака (слово). 18. Привести пример описания данных символьного типа. 28. Перечислить основные операции над символьными данными. 20. Привести пример описания данных вещественного (с плавающей точкой) типа. 21. Перечислить основные операции над вещественными данными. 22. Привести пример описания данных целого типа. 23. Привести пример описания данных строкового типа. 24. В какой директории (по умолчанию) хранятся файлы с описанием типов данных и функций над ними для языка программирования SML.NET? 25. Каким образом осуществляется ссылка из языка программирования SML на стандартные типы .NET? Привести пример.

10

26. Каковы этапы создания проектов на языке программирования SML.NET в Microsoft Visual Studio? 27. Какие виды файлов автоматически создаются средой разработки? 28. Какая информация хранится в файле с расширением .sml? Привести пример. 28. Какая информация хранится в файле script.smlnet? Варианты заданий 1. Реализовать функцию вычисления суммы двух целых чисел 2. Реализовать функцию вычисления разности двух целых чисел 3. Реализовать функцию вычисления произведения двух целых чисел 4. Реализовать функцию вычисления частного двух целых чисел 5. Реализовать функцию вычисления суммы двух вещественных чисел 6. Реализовать функцию вычисления разности двух вещественных чисел 7. Реализовать функцию вычисления произведения двух вещественных чисел 8. Реализовать функцию вычисления частного двух

вещественных

чисел 9. Реализовать функцию возведения целого числа в квадрат целого числа в квадрат 10. Реализовать функцию возведения в квадрат суммы двух целых чисел 11. Реализовать функцию возведения в квадрат разности двух целых чисел 12. Реализовать функцию возведения в квадрат произведения двух целых чисел 13. Реализовать функцию возведения в квадрат частного двух целых чисел 14. Реализовать функцию возведения в квадрат суммы двух вещественных чисел 15. Реализовать функцию возведения в квадрат разности двух вещественных чисел 16. Реализовать функцию возведения в квадрат произведения двух вещественных чисел 17. Реализовать функцию возведения в квадрат частного двух вещественных чисел 18. Реализовать функцию возведения в куб целого числа 28. Реализовать функцию возведения в куб суммы двух целых чисел 20. Реализовать функцию возведения в куб разности двух целых чисел 21. Реализовать функцию возведения в куб произведения двух целых чисел 22. Реализовать функцию возведения в куб частного двух целых чисел

11

23. Реализовать функцию возведения в куб суммы двух вещественных чисел 24. Реализовать функцию возведения в куб разности двух вещественных чисел 25. Реализовать функцию возведения в куб произведения двух вещественных чисел 26. Реализовать функцию возведения в куб частного двух вещественных чисел

Порядок выполнения работы: 1) 2) 3) 4)

Сформулировать формальную постановку задачи. Записать типы получаемых функций. Реализовать программу на SML в соответствии с вариантом исполнения. Подготовить отчет в твердой копии и в электронном виде.

12

Лабораторная работа 2 Функции SML для основных комбинаторов Цель работы: Получить представление об отображении комбинаторной логики на язык SML. Необходимые теоретические сведения: По определению комбинатор – это терм, не содержащий свободных переменных. Например, если в законе коммутативности x+y=y+x определить alpha(x,y)=x+y и (Cf)(x,y)=f(xy), то коммутативность можно будет записать в виде alpha = C alpha. Комбинаторная логика наиболее естественным образом отображается на языки функционального программирования. Запись басисных комбинаторов I K S ( Ix=x, Sxyz= xz(yz), Kxy=x) на SML будет выгядеть так: fun Ix = x; fun Kxy = x; fun Sxyz = xz(yz); Контрольные вопросы 1. Что понимается под термином «свободная переменная»? 2. Что понимается под термином «связанная переменная»? 3. Сформулируйте определение комбинатора. 4. Что называют комбинаторной логикой? 5. Какие операции допустимы над комбинаторными термами? 6. Как понимается операция аппликации в комбинаторной логике?

13

7. Почему формальную систему комбинаторной логики возможно отобразить на конструкции языка функционального программирования? 8. Какие свойства комбинаторной логики обеспечивают естественность отображения термов в функции языка программирования? 9. Приведите примеры комбинаторов. 10. Что понимается под термином «базис»? 11. Какие комбинаторы называются базисными? 12. Существует ли минимальный набор комбинаторов, который является базисным? 13. Сколько существует различных базисов? Конечно ли их число? 14. Сколько существует различных минимальных базисов? Конечно ли их число? 15. Приведите пример базисного набора комбинаторов. 16. Приведите пример минимального базисного набора комбинаторов. 17. Что означает термин «комбинаторная характеристика (объекта)»? 18. Приведите комбинаторную характеристику для комбинатора K. 28. Приведите комбинаторную характеристику для комбинатора S 20. Приведите комбинаторную характеристику для комбинатора I. 21. Приведите функцию языка программирования SML для комбинатора K. 22. Приведите функцию языка программирования SML для комбинатора S. 23. Приведите функцию языка программирования SML для комбинатора I. 24. Какие аксиомы и правила вывода комбинаторной логики позволяют строить новые комбинаторы? 25. Какие аксиомы и правила вывода комбинаторной логики позволяют строить цепочки вывода соотношений? 26. Какие аксиомы и правила вывода комбинаторной логики позволяют доказывать теоремы? Варианты заданий Выразить в базисе {K,S} комбинаторы с заданными характеристиками, убедиться в справедливости произведенных преобразований: 1. I, где Ia = a; 2. B, где B abc = a(bc); 3. C, где C abc = acb; 4. W, где W ab = abb; 5. Ψ, где Ψ abcd = a(bc)(bd); 6. C[2], где C[2] abcd = acdb; 7. C[2], где C[2] abcd = adbc; 8. B2, где B2 abcd = a(bcd);

14

9. Y, где Ya = a (Ya); 10. C[3], где C[3] abcde = acdeb; 11. C[3], где C[3] abcde = aebcd; 12. B3, где B3 abcde = a(bcde); 13. Φ, где Φ abcd = a(bd)(cd); Выразить в характеристиками, преобразований:

базисе {B,C,S} комбинаторы убедиться в справедливости

с заданными произведенных

14. I, где Ia = a; 15. K, где K ab = a; 16. S, где S abc = ac(bc); 17. W, где W ab = abb; 18. Ψ, где Ψ abcd = a(bc)(bd); 28. C[2], где C[2] abcd = acdb; 20. C[2], где C[2] abcd = adbc; 21. B2, где B2 abcd = a(bcd); 22. Y, где Ya = a (Ya); 23. C[3], где C[3] abcde = acdeb; 24. C[3], где C[3] abcde = aebcd; 25. B3, где B3 abcde = a(bcde); 26. Φ, где Φ abcd = a(bd)(cd).

Порядок выполнения работы: 1) Сформулировать формальную постановку задачи, записать правила вывода. 2) Реализовать программу на SML в соответствии с вариантом исполнения. 3) Подготовить отчет в твердой копии и в электронном виде

15

Лабораторная работа 3 Рекурсивные вычисления Цель работы: Целью данной работы является ознакомление с принципами работы механизма рекурсии. Необходимые теоретические сведения: Рекурсивно определенная функция содержит в своем определении ссылку на саму эту функцию. Одним из случаев примемения индукции в математике являются индуктивные определения и доказательства. Индукция в SML выполняется так же легко, как и в обычной математике. Например, определение факториала: 1. Начало индукции: 0!=1 2. Шаг индукции: n!=n*(n-1)! на SML выглядит так:

Пользуясь условным оператором if then else функцию факториала можно выразить как fun factorial n = if (n<2) then 1 else n * factorial(n-1);

16

Рекурсивно можно определять не только функции, но и типы. Например, тип-список можно записать как datatype slist = nil | element of char * slist;

Контрольные вопросы 1. Что понимается под термином «рекурсия»? 2. Что понимается под термином «рекурсивная функция»? 3. Что понимается под термином «рекурсивное определение»? 4. В чем состоит аналогия между рекурсивным и индуктивным определениями? 5. В каких случаях в математике применяется индукция? 6. Насколько существенны различия в представлении рекурсии в математике и языке программирования SML? 7. Из каких частей состоят индуктивные определения? 8. Что понимается под термином «базис индукции»? 9. Что понимается под термином «шаг индукции»? 10. Приведите пример базиса индукции. 11. Приведите пример шага индукции. 12. Приведите пример базиса индукции в коде программы на языке SML. 13. Приведите пример шага индукции в коде программы на языке SML. 14. Приведите пример индуктивного определения в математике. 15. Приведите пример рекурсивной функции на языке программирования SML. 16. Возможно ли использовать индукцию для построения определения типа данных? 17. Возможно ли использовать рекурсию для построения определения типа данных? 18. Приведите пример определения типа данных по индукции. 28. Приведите пример определения типа данных посредством рекурсии. 20. Насколько целесообразно задавать определения рекурсивного типа посредством индукции? 21. Насколько целесообразно обрабатывать рекурсивные типы посредством рекурсивных функций (в частности, на языке программирования SML)? 22. Какие рекурсивные типы данных Вам известны?

17

23. Приведите пример словесного определения рекурсивного типа данных. 24. Приведите пример индуктивного определения рекурсивного типа данных. 25. Приведите пример рекурсивного определения рекурсивного типа данных посредством функции на языке программирования SML.

Варианты заданий Реализовать на языке SML следующие рекурсивные функции: 1. Предшествования для целых чисел. 2. Следования для целых чисел. 3. Суммы первых N чисел натурального ряда. 4. Произведения первых N чисел натурального ряда (факториала). 5. Вычисления чисел Фибоначчи. 6. Решения задачи о размещении 8 ферзей на шахматной доске 8х8 так, чтобы никакой из них они не «бил» другого. 7. Решения задачи о «Ханойских башнях». 8. Упорядочения массива. 9. Обхода двоичного дерева слева. 10. Обхода двоичного дерева справа. 11. «Балансировки» двоичного дерева 12. Подсчета количества элементов двоичного дерева. 13. Упорядочения списка. 14. Вставки элементов в упорядоченный список. 15. Вставки элементов в «сбалансированное» двоичное дерево. 16. Наибольшего общего делителя по алгоритму Евклида. 17. Суммы N элементов арифметической прогрессии. 18. Суммы N элементов геометрической прогрессии. 28. Решения задачи о ханойских башнях (перемещение диска со стержня А на стержень В отображать посредством вывода текста АÆВ). 20. Суммы элементов списка. 21. Инвертирования списка. 22. Произведения с использованием только функции сложения. 23. Суммы с использованием только функции прибавления единицы.

18

Порядок выполнения работы: 1) Сформулировать формальную постановку задачи, записать правила вывода. 2) Реализовать программу на SML в соответствии с вариантом исполнения. 3) Подготовить отчет в твердой копии и в электронном виде

19

Лабораторная работа 4 Функции для синтаксического разбора простых языковых конструкций Цель работы: Целью данной работы является ознакомление с механизмами синтаксического разбора (parsing) простых языковых конструкций. Необходимые теоретические сведения: Целью синтаксического анализа является разбор строки символов на отдельные составляющие элементы согласно набору синтаксических правил. Например, простую скобочную запись a(bc) можно представить как в виде аппликации a Æ (b Æ c), так и в виде двоичного дерева. Рассмотрим простой случай разбора аппликативного выражения, записанного в виде бесскобочного выражения: Создадим рекурсивный тип – бинарное дерево: datatype tree = Atom of string | Comb of tree * tree Примем за минимальную синтаксическую единицу один символ, и будем считать, что строка представляет из себя последовательную аппликацию с ассоциацией влево ( fxyz ): fun Parse [next] = Atom next | Parse (next::rest) = Comb(Atom next, Parse rest); В результате выполнения Parse["f", "x", "y", "z"] мы получим val it = Comb (Atom “f”,Comb (Atom “x”,Comb (Atom “y”,Atom “z”))) : tree В аналогичном случае с ассоциацией влево ситуация будет несколько сложнее.

20

Запишем основные правила для синтаксического разбора: 1. f преобразуется в Atom “f” 2. fx преобразуется в Comb(Atom ”f”, Atom “x”) 3. fxy преобразуется в Comb(Comb(Atom “f”, Atom “x”), Atom “y”) Запись этих правил на SML будет выглядеть следующим образом: fun Parser t [] = t | Parser t (next::rest) = Parser (Comb(t, Atom next)) rest; fun Parse [next] = Atom next | Parse (next::rest) = Parser (Atom next) rest; Parse["f", "x", "y", "z"]; Контрольные вопросы 1. Что понимается под термином «синтаксис языка программирования»? 2. Чем отличается синтаксис языка программирования от семантики? 3. Что означает термин «синтаксический разбор»? 4. Что означает термин «синтаксический анализ»? 5. Применим ли термин «синтаксический разбор» к языку программирования в целом? 6. Применим ли термин «синтаксический разбор» к программе на том или ином языке программирования? 7. Применим ли термин «синтаксический разбор» к отдельным конструкциям языка программирования? 8. В чем состоит цель синтаксического анализа программы или конструкции языка программирования? 9. Что понимается под синтаксическими правилами (или, иначе, под правилами синтаксического анализа)? 10. Приведите пример синтаксического правила. 11. Какие способы представления скобочной записи конструкций языка программирования Вам известны? 12. Возможно ли представление скобочной записи конструкций языка программирования в форме аппликации? 13. Возможно ли представление скобочной записи конструкций языка программирования в форме дерева (в частности, двоичного дерева)? 14. Поясните соответствие представлений скобочной записи конструкций языка программирования в форме аппликации и двоичного дерева.

21

15. Приведите пример представления скобочной записи конструкций языка программирования в форме аппликации. 16. Приведите пример представления скобочной записи конструкций языка программирования в форме двоичного дерева. 17. Является ли рекурсивным описание типа, представляющего двоичное дерево на языке программирования SML? 18. Является ли рекурсивным описание типа, представляющего произвольное дерево на языке программирования SML? 28. Приведите пример описания типа, представляющего двоичное дерево на языке программирования SML. 20. Какой языковой объект можно принять за минимальную синтаксическую единицу (атом)? 21. Каким образом выполняется процедура синтаксического разбора аппликативных конструкций на языке программирования SML с ассоциацией влево? 22. Каким образом выполняется процедура синтаксического разбора аппликативных конструкций на языке программирования SML с ассоциацией вправо? 23. В чем состоит различие процедур синтаксического разбора аппликативных конструкций на языке программирования SML с ассоциацией влево и вправо? 24. Приведите пример синтаксического разбора аппликативной конструкции на языке программирования SML с ассоциацией влево. 25. Приведите пример синтаксического разбора аппликативной конструкции на языке программирования SML с ассоциацией вправо. 26. Перечислите основные правила синтаксического разбора аппликативных выражений языка программирования SML. 27. Представьте текст элементарной программы на языке программирования SML, которая реализует основные правила синтаксического разбора аппликативных выражений.

Варианты заданий Реализовать функцию на языке программирования SML, которая выполняет синтаксический разбор следующего аппликативного выражения по ассоциации влево с построением бинарного дерева: 1. a(bc) 2. ac(bc) 3. (ac)(bc) 4. (ab)(c(de)) 5. a(b(cd)(ef)) 6. a(b(cd)(ef)g)

22

7. a(b((cd)(ef)) 8. (a(bc(de)f)gh) 9. abb(cdd(e)fg) 10. (ab(c(de))f(g(hi))j) Реализовать функцию на языке программирования SML, которая выполняет синтаксический разбор следующего аппликативного выражения по ассоциации вправо с построением бинарного дерева: 11. a(bc) 12. ac(bc) 13. (ac)(bc) 14. (ab)(c(de)) 15. a(b(cd)(ef)) 16. a(b(cd)(ef)g) 17. a(b((cd)(ef)) 18. (a(bc(de)f)gh) 28. abb(cdd(e)fg) 20. (ab(c(de))f(g(hi))j)

Порядок выполнения работы: 1) Сформулировать формальную постановку задачи, записать правила вывода. 2) В качестве целевого типа взять бинарное дерево вида: tree = Nil | Atom of string | Comb of tree * tree; 3) Реализовать программу на SML в соответствии с вариантом исполнения. 4) Подготовить отчет в твердой копии и в электронном виде

23

Лабораторная работа 5 Реализация категориальной абстрактной машины Цель работы: Практически ознакомиться с принципами реализации категориальной абстрактной машины (КАМ) на примере избранных фрагментов реализации. Необходимые теоретические сведения Структурно категориальная абстрактная машина состоит из тройки , где T – терм как структурированное значение, например, граф, C – код, S – стек или дамп. Основными инструкциями КАМ являются следующие: Fst Snd < , > ε Λ ‘ car cdr push swap cons app cur quote. На SML эти инструкции можно записать в виде: fun Fst(x,_)=x; fun Snd(_,y)=y;

Контрольные вопросы 1. Что означает термин «абстрактная машина»? 2. Как понимается термин «категория»? 3. В чем состоит смысл названия «категориальная абстрактная машина»? 4. Сколько объектов включает в себя состояние категориальной абстрактной машины? 5. Какие объекты определяют состояние категориальной абстрактной машины? 6. Что обозначает слово «терм»? 7. Как понимается термин «стек» применительно к категориальной абстрактной машине? 8. Что такое КАМ-код или код категориальной абстрактной машины?

24

9. Перечислите основные инструкции абстрактной машины. 10. Какая функция языка программирования КАМ под названием Fst? 11. Какая функция языка программирования КАМ под названием Snd? 12. Какая функция языка программирования КАМ под названием “<”? 13. Какая функция языка программирования КАМ под названием “>”? 14. Какая функция языка программирования КАМ под названием ε? 15. Какая функция языка программирования КАМ под названием Λ? 16. Какая функция языка программирования КАМ под названием “ ‘ ”? 17. Какая функция языка программирования КАМ под названием car? 18. Какая функция языка программирования КАМ под названием cdr? 28. Какая функция языка программирования КАМ под названием push? 20. Какая функция языка программирования КАМ под названием swap? 21. Какая функция языка программирования КАМ под названием cons? 22. Какая функция языка программирования КАМ под названием app? 23. Какая функция языка программирования КАМ под названием cur? 24. Какая функция языка программирования КАМ под названием quote?

языка

категориальной

SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду SML реализует команду

Варианты заданий Реализовав необходимые инструкции КАМ (Fst, Snd, “<”, “>”, ε, Λ, “ ‘ ”, car, cdr, push, swap, cons, app, cur, quote), после преобразования в ламбдавыражение и КАМ-код, провести максимально возможное число шагов преобразования кода и при возможности вычислить значение терма: 1. 1+2 2. 2+3 3. 2-1

25

4. 5*2 5. 1! 6. 1+2+3 7. 2*3 8. 1*2*3 9. 2! 10. 2+4 11. 3+4 12. 5-2 13. 3-2 14. 2*3*4 15. 3*5*7 16. 4! 17. 1+2+3+4 18. 2+3+4+5 28. 3*4*5 20. 5!

Порядок выполнения работы: 1) Сформулировать формальную постановку задачи, записать правила вывода. 2) Реализовать программу на SML в соответствии с вариантом исполнения. 3) Подготовить отчет в твердой копии и в электронном виде.

26

Лабораторная работа 6 Редукция ламбда-термов Цель работы: Практически изучить механизм редукции ламбда-термов на примере вариантов, реализующих разбор случаев при бета-редукции. Необходимые теоретические сведения Терм вида (λx.M)N означает оператор λx.M, приложенный к аргументу N. Бета-редукцией исходного терма будет интерпретация его в точке N, выполненная соответственно заменой связанной переменной x на N : (λx.M)N = [N/x]M. Контрольные вопросы 1. Что означает термин «ламбда-терм»? 2. Как понимается процедура редукции ламбда-термов? 3. Какие виды редукции термов существуют в ламбда-исчислении? 4. В чем состоит особенность бета-редукции ламбда-термов? 5. В чем заключается смысл операции редукции ламбда-термов? 6. В каких случаях редукция ламбда-термов приносит практическую пользу? 7. Возможно ли проиллюстрировать операцию бета-редукции графически? 8. В чем состоит практическое значение использования механизма редукция графов для моделирования бета-редукции ламбда-термов? 9. Какие возможные случаи структуры ламбда-термов необходимо рассмотреть для осуществления бета-редукции произвольного ламбдавыражения? 10. Как связана бета-редукция с операцией замены переменных в ламбда-выражениях? 11. Что означает термин «свободная переменная»? 12. Что означает термин «связанная переменная»? 13. Что означает термин «редекс»? 14. Как следует понимать слова «бета-нормальная форма» применительно к ламбда-выражению? 15. Какие аксиомы ламбда-исчисления Вам известны? 16. Какие правила вывода ламбда-исчисления Вам известны? 17. Опишите алгоритм бета-нормализации функции (т.е. приведения функции к бета-нормальной форме).

27

18. Провести бета-редукцию выражения: lx.x. 28. Провести бета-редукцию выражения: (lx.x) 3. 20. Провести бета-редукцию выражения: (lxy.x) 1.

Варианты заданий На основе самостоятельно созданной функции, приводящей строку символов к бета-нормальной (т.е. не содержащей бета-редексов) форме, произвести бета редукцию выражения: 1.λx.x 1 2. λx.(xy) 2 3. (λx. λy. xy) 3 4. λx.(xy) 4 5. λx.(yx) 5 6. (λx. λy. yx) 6 7. (λx. λy. x (xy)) 7 8. (λx. λy. x (yx)) 8 9. (λx. λy. λz. x(yz)) 9 10. (λx. λy. λz. x(zy)) 10 11. (λx. λy. λz. z(xy)) 11 12. (λx. λy. λz. y(xz)) 12 13. (λx. λy. λz. y(xz)) 13 14. (λy. λx. λz. x(zy)) 14 15. (λy. λx. λz. z(xy)) 15 16. (λy. λx. λz. y(xz)) 16 17. (λy. λx. λz. y(xz)) 17 18. (λz. λx. λy. z(xy)) 18 28. (λz. λx. λy. y(xz)) 28 20. (λz. λx. λy. y(xz)) 20

Порядок выполнения работы: 1) Сформулировать формальную постановку задачи, записать правила вывода. 2) Реализовать программу на SML в соответствии с вариантом исполнения. 3) Подготовить отчет в твердой копии и в электронном виде.

28

Список литературы и учебных материалов 1. The Standard /manpages.html

ML

Basis

Library,

http://www.standardml.org/Basis

2. Gilmore S. Programming in Standard ML ’97: A Tutorial Introduction. The University of Edinburgh, 2897. 3. Harper R. Programming in Standard ML. Carnegie Mellon University, 2001. 4. Вольфенгаген В., ‘Конструкции языков программирования’, Москва, 2001.

29

Приложение 1. Особенности инсталляции интегрированной среды разработки Visual Studio .NET Требования к аппаратному обеспечению: 1. Процессор Минимум: Pentium II 450 MHz и выше Рекомендовано: Pentium III 600MHz и выше 2. Оперативная память Минимум: Windows 2000 Professional — 96 MB Windows 2000 Server — 282 MB Windows NT4.0 Workstation — 64 MB Windows NT 4.0 Server — 160 MB Windows XP Professional — 160 MB Рекомендовано: Windows 2000 Professional — 128 MB Windows 2000 Server — 256 MB Windows NT4.0 Workstation — 96 MB Windows NT 4.0 Server — 282 MB Windows XP Professional — 282 MB 3. Свободное место на жестком диске: На системном разделе — 500 MB На раздел, куда будет выполнена установка — 3 GB 4. Дисковод CD-ROM или DVD-ROM 5. Разрешение экрана Минимум: 800 x 600, 256 цветов Рекомендовано: 1024x768, 16 битный цвет 6. Манипулятор мышь или аналогичный ему …

30

Требования к программному обеспечению: 1.

Операционная система Windows® 2000, Windows XP, или Windows NT 4.03 2. Права пользователя: Для установки Visual Studio .NET необходимо иметь административные привилегии на компьютер, на который производится установка. Для последующей работы с Visual Studio административные привилегии не требуются. Дополнительные сведения о процессе установки можно найти в файлах readme, находящихся в корне первого (а в случае с DVD версией единственного) диска установочного комплекта Visual Studio .NET.