Последние записи

made in programmersforum 4

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

1st
Июл

Введение в Sсheme. Часть 1

Posted by Chas under Журнал, Статьи

Краткое описание функционального языка программирования Sсheme. Рассчитано на программистов, имеющих навыки программирования в императивном стиле.

by Utkin

В 1970 году Гай Стил (Guy L. Steele) и Джеральд Сассман (Gerald Jay Sussman) из Массачусетского технологического института начали работу на новым языком программирования. Тогда Джеральд Сассман уже имел ученую степень, а его помощник Гай Стил являлся студентом данного института. В 1975 году работы были закончены и получили свое дальнейшее воплощение в принципах работы СБИС (в 1978 году) и CAD-системах. Идеи, положенные в эти работы, позже использовались для конструирования элементов космических аппаратов и проведения экспериментов в космосе (с использованием элементов искусственного интеллекта). В 1984 году большое количество версий в разных институтах заставило разработчиков выработать единый стандарт (при участии Массачусетского технологического института и университета Индианы). Такие серьезные сферы дали хороший старт языку, однако его распространение сдерживалось низкой скоростью интерпретации. В 90-х годах прошлого века были разработаны новые технологии компиляции, что позволило повысить эффективность Scheme путем компиляции в байт-код и машинные коды (хотя экспериментальные компиляторы со Scheme существовали и ранее). На данный момент производительность Scheme в целом выше, чем у Java (учитывая, что языки разных стилей, то такое сравнение условно).

<h3 style=»margin-left: 0px; padding-left: 0px;»>Scheme («скиим»)</h3>

это функциональный язык программирования, диалект Лиспа. Особенности: разумный минимализм, интерактивность, однородность синтаксиса (лисповые списки), высокий уровень абстрагирования, возможность писать программы оторванные от конкретной платформы, «строгий» язык (требует придерживаться определенного стиля), позволяет использовать разные парадигмы программирования и много чего еще особенного.

В дальнейшем будем рассматривать язык на примере PLT Scheme. Данная среда выбрана не случайно (имеются десятки других). Она бесплатна, имеет широкое распространение, большой набор библиотек и позволяет компилировать программы в exe-файлы. Взять можно отсюда: http://www.plt-scheme.org/ IDE в PLT Scheme называется DrScheme, имеет минималистический вид, однако содержит практически все, что необходимо для работы программиста. Редактор имеет два окна – первое для записи программы, второе информационное и окно интерактивного режима – команды языка, введенные в него, исполняются немедленно.

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

<h3 style=»margin-left: 0px; padding-left: 0px;»>Синтаксические элементы и что еще обязательно нужно знать</h3>

Прежде чем, начать описание синтаксических элементов следует обратить внимание на некоторые вещи. Все вычисления, в процедурах, аргументах всегда осуществляются слева направо. Язык имеет поддержку типов, однако, типизация скрытая (динамический контроль типов). Объекты (включая процедуры – сама программа также может являться объектом данных) имеют неразрушаемую природу, однако переполнение памяти не возникает за счет того, что объекты могут быть перезаписаны, в случае, если больше не будут участвовать в вычислительном процессе. На данный момент все реализации Scheme используют хвостовую рекурсию, это позволяет выделять на выполнение рекурсионных вызовов ограниченный размер памяти. Такие вызовы позволяют не использовать специализированные операции цикла (могут быть получены за счет автоматического преобразования хвостовой рекурсии в итерации). Все функции являются самостоятельными объектами (могут создаваться динамически, сохранены в структурах данных, возвращены как результаты функций и т.д.). Примером таких языков являются Common Lisp и ML. Параметры процедур всегда передаются по значению (в противовес Haskell, который позволяет откладывать вычисление параметра, до тех пор, пока он не потребуется явно).

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

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

Пример.
(+ 2 2) Результатом будет 4.
(+ 2 (* 2 2)) Результатом будет 6.

Особенностью такой записи является тот факт, что операция может быть применена к неограниченному количеству входящих параметров, можно написать и (+ 2 2 2 2 2 2 2 2 2 2 2) (сравните 2 + 2). Это приводит к тому, что программы, написанные на Scheme, могут являться данными для других программ написанных на Scheme. Для функциональных языков программирования является традицией писать интерпретаторы/компиляторы с них на этих же языках программирования.

PLT Scheme не делает разницы между идентификаторами, набранными в разных регистрах. В тоже время правила образования идентификаторов может различаться для разных версий и реализаций языка, однако есть общее требование – идентификатор не должен начинаться с цифры. Примеры идентификаторов:

lambda

q

list-&gt;vector

soup

+

V17a

&lt;=?

a34kTMNs

the-word-recursion-has-many-meanings

Для идентификаторов разрешено использовать символы. Можно использовать, например, такой идентификатор ——>, однако по соглашению фрагмент -> делит идентификатор на две части и говорит о преобразовании типа, например list->vector для функции может трактоваться как преобразование списка в вектор (элементы которого являются элементами списка). Помимо пробелов и переходов на новую строку допускается также использовать символы табуляции, все эти элементы обычно используются для улучшения восприятия текста программы и в качестве разделителей лексем языка.

Одним из важных понятий языка является понятие представления объектов. Если в программе, это всего лишь поток символов, то внутренне объект может представляться совершенно иным способом. Далее, представление объектов не обязательно уникально, так число 28 может быть представлено как #e28.000 или #x1c. Список (1 2) можно представить как (01 02) или (1. (2. ())) Здесь () является пустым списком. Однако, список (+ 1 2) не является эквивалентом числа 3, это список, состоящий из трех элементов (результат вычисления которого является числом 3). С одной стороны, это может путать на начальном этапе знакомства с языком, но с другой это источник его мощи, данные могут являться программой, программа может являться данными.

Переменные перед использованием должны быть объявлены: (define x 28) В данном случае мы определяем переменную х со значением 28. В Дальнейшем допускается неоднократное переопределение (например, (define x 38)).

Точка с запятой (;) служит для обозначения комментария, который продолжается до конца строки и является неисполняемым оператором языка. Поэтому комментарии посреди лексемы языка не допускаются.

Небольшой пример:

;;; процедура FACT вычисляет факториал

;;; из неотрицательного целого числа.

(define fact

(lambda (n)

(if (= n 0)

1 ;Base case: return 1

(* n (fact (- n 1))))))

Вызов факториала (fact 100) даст результат:
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272
23758251185210916864000000000000000000000000

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

Существует соглашение, по которому предикаты (элементы, возвращающие значения Истина/Ложь) должны именоваться с вопросительным знаком на конце.

Ну и еще что нужно знать об основных синтаксических элементах: *. + — могут использоваться в идентификаторах (например, предыдущем примере мы могли бы обозначить идентификатор функции как fact+ или fact+1).

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

Чтобы было понятней, объявим такую функцию:

(define (prostoX x) ( quote x))

Вызовем ее

(prostoX 100) Результат будет х, а не 100

(quote a) Результат a

(quote #(a b c)) Результат #(a b c)

(quote (+ 1 2)) Результат (+ 1 2), а не 3

'(quote a) Результат (quote a)

Можно заставить Scheme вычислять частично, для этого используется запятая:

`(list ,(+ 1 2) 4) Результат (list 3 4), то есть выражение перед запятой (+1 2) было вычислено.

Более сложный пример

(let ((name 'a)) `(list ,name ',name)) Результат (list a (quote a))

Числовые, символьные, строковые и булевые константы «квотировать» не допускается.
Символ двойной кавычки (”) используется для ограничения строковых констант.
Символ обратного слеша (\) используется в строковых константах.
[ ] { } | Левые и правые квадратные скобки, изогнутые скобки и вертикальный штрих зарезервированы для возможных будущих расширений языка.

Символ шарп (#) используется для множества целей в зависимости от символа, который немедленно следует за этим:

<ul><li>#t #f — обозначение булевых констант;</li>
<li> # \ — вводит символьную константу;</li>
<li> #( — вводит векторную константу;</li>
<li> #e #i #b #o #d #x — используются для обозначения чисел.</li></ul>

Объявление процедур:

(lambda <formals> <body>)
<Formals> — список формальных параметров
<Body> — последовательность из одного или более выражений.
Лямбда-выражение считается процедурой, не имеющей имени. Результат(ы) последнего выражения в теле будет возвращен как результат(ы) вызова процедуры.
(lambda (x) (+ x x)) Есть описание процедуры без имени, имеющий один входящий параметр и возвращающий удвоенное значение переменной х.
((lambda (x) (+ x x)) 4) Результат 8 (последнее выражение, передано в процедуру)

Определим такую функцию

(define reverse-subtract

(lambda (x y) (- y x)))

Ее вызов с параметрами (reverse-subtract 7 10) Результат результат 3 (для последнего выражения происходит обмен параметров в списке). Таким образом, сначала определяется безымянная процедура с двумя входящими параметрами х и y. Ее задача вычитать из y x. Далее, ей просто присваивается имя reverse-subtract, которую мы и вызвали с параметрами 7 и 10. х получает значение 7, у соответственно 10, затем мы вычитаем из y x тело (- у х), то есть (- 10 7). Результатом будет 3.

Определим следующую функцию:

(define add4

(let ((x 4))

(lambda (y) (+ x y))))

Ее вызов с параметрами (add4 6) Результат 10. Обратите внимание – внутри функции определяется локальная переменная х, имеющая значение 4. Данная переменная существует только в рамках add4.

Lambda удобно использовать для образования хвостовой рекурсии – один из важнейших элементов функционального программирования. Для императивного программирования хвостовую рекурсию можно выразить через цикл. Также lambda в связке с define можно рассматривать как аналог механизма интерфейсов ООП.

Допускается и короткая форма функций, без использования процедур lambda: (define (имя параметры) (тело_функции)). Определим функцию возведения в квадрат: (define (square x) (* x x)). Вызовем ее (square 10), в результате получим 100. Вызовем ее еще раз (Square 10.5), в результате получим 110.25. Код может следовать сразу друг за другом без всяких приведений типов и никаких фокусов с параметризацией здесь не требуется совершенно. Хотелось бы на этом заострить внимание: то, что в последнее время привносится как новая веха ООП – параметризация, существует в функциональном программировании чуть ли не с момента его возникновения. Однако в функциональном программировании оно представлено на совершенно ином уровне.

Еще один момент, касающийся идентификаторов – в PLT Scheme все идентификаторы могут содержать дополнительные символы. Это значит, что вместо square можно смело определить функцию КВАДРАТ, и вообще можно переписать практически все ключевые элементы языка, используя национальный алфавит.

Условные выражения представляются в следующих формах:

(if <тест> <следствие> <альтернативный_вариант>)

Здесь все просто и аналогично другим языкам программирования:

(if (&gt; 3 2) 'да 'нет) Результат да (обратите внимание на одинарные кавычки)

(if (&gt; 2 3) 'да 'нет) Результат нет

(if (&gt; 3 2)

(-3 2)

(+ 3 2)) Результат 1 (3 больше 2? Если да, то выполним (- 3 2), то есть получим в итоге 1).

Можно использовать также cond:

(cond ((&gt; 3 2) 'больше)

((&lt;3 2) 'меньше)) Результат больше

(cond ((&gt; 3 3) 'больше)

((&lt;3 3) 'меньше)

(else 'равно)) Результат равно

Общая форма: (cond выражение1 выражение2 … выражениеN), где выражение состоит из ((условие) (действие)). Ветвь else будет выполнена в случае, если ни одно из предыдущих условий не было выполнено. Cond аналогична множественному использованию if (изначально конструкции if не было, и все условия обсчитывали через cond). В качестве задания: попробуйте выразить if через использование cond.

Давайте рассмотрим такой фрагмент программы:

(define (PAIR (a b)

(lambda (msg)

(case msg ; конструкция case для каждого значения msg

; выполняет соответствующее действие

((first) a) ; если сообщение – символ first, возвратить a

((second) b))))

В зависимости от msg будет возвращено соответствующее значение, то есть фактически полностью соответствует case из императивных языков (таких как С++ или Дельфи). Case аналогично cond поддерживает else – ветвь которая будет обязательно выполнена в случае, если ни одна из предыдущих выполнена не была.

Можно составлять сложные условия за счет грамотного использования and и or:

(and (= 2 2) (&gt; 2 1)) Результат #t (истина). 2=2 и 2&gt;1? Истина

(and (= 2 2) (&lt; 2 1)) Результат #f (ложь). 2=2 и 2&lt;1? Ложь

(and 1 2 'c '(f g)) Результат (f g) (список не вычисляется из-за одинарных кавычек)

(and) Результат #t

(and (&lt; 2 2) (= 2 2)) Результат #f

Выражения оцениваются слева направо до первого ложного утверждения. Если все утверждения верны, то возвращается последний входящий параметр функции (у нас это пример со списком (f g)). Если and не имеет входящих утверждений, будет возращено #t (истина).

(or (= 2 2) (&gt; 2 1)) Результат #t

(or (= 2 2) (&lt; 2 1)) Результат #t

(or #f #f #f) Результат #f

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

(define x 2)

(set! x 4)

(+ x 1)

Результат 5. Ничто нам не мешает переопределить переменную x через define, но все же необходимо помнить, что define не эквивалентно set! (хотя в нашем случае и приводит к одному результату). Разница заключается в том, что define связывает идентификатор переменной с ее новым значением (предыдущее значение переменной будет уничтожено в результате сборки мусора), а set! присваивает значение уже существующей. Вообще, следует учитывать, что имя переменной и ее значения связаны не напрямую между собой. В частности, это проявляется в том, что переменная может существовать по имени, без значения (проявляется, например, при операции quote). При этом нет точных рамок между именем переменной и именем функции. И через define имя переменной можно переопределить как имя функции.

Теперь рассмотрим более подробно конструкцию let. Собственно у нее ее два родственника let* и letrec с тем же синтаксисом (let ((определение_переменной1) (определение_переменнойN)) (тело)). Разница в них только в уровнях видимости связанных ими переменных. Это позволяет строить блочные структуры на манер принятый в структурном программировании. Короткая форма такова: (let (определение переменной) выражение), где определение переменной выглядит все в том же списочном стиле (переменная значение).

Определим такую функцию

(define reverse-subtract

(lambda (x y) (- y x)))

Определим следующую функцию:

(define add4

(let ((x 4))

(lambda (y) (+ x y))))

Условные выражения представляются в следующих формах:

(if <тест> <следствие> <альтернативный_вариант>)

Здесь все просто и аналогично другим языкам программирования:

(if (&gt; 3 2) 'да 'нет) Результат да (обратите внимание на одинарные кавычки)

(if (&gt; 2 3) 'да 'нет) Результат нет

(if (&gt; 3 2)

(-3 2)

(+ 3 2)) Результат 1 (3 больше 2? Если да, то выполним (- 3 2), то есть получим в итоге 1).

Можно использовать также cond:

(cond ((&gt; 3 2) 'больше)

((&lt;3 2) 'меньше)) Результат больше

(cond ((&gt; 3 3) 'больше)

((&lt;3 3) 'меньше)

(else 'равно)) Результат равно

Давайте рассмотрим такой фрагмент программы:

(define (PAIR (a b)

(lambda (msg)

(case msg ; конструкция case для каждого значения msg

; выполняет соответствующее действие

((first) a) ; если сообщение – символ first, возвратить a

((second) b))))

Можно составлять сложные условия за счет грамотного использования and и or:

(and (= 2 2) (&gt; 2 1)) Результат #t (истина). 2=2 и 2&gt;1? Истина

(and (= 2 2) (&lt; 2 1)) Результат #f (ложь). 2=2 и 2&lt;1? Ложь

(and 1 2 'c '(f g)) Результат (f g) (список не вычисляется из-за одинарных кавычек)

(and) Результат #t

(and (&lt; 2 2) (= 2 2)) Результат #f

(or (= 2 2) (&gt; 2 1)) Результат #t

(or (= 2 2) (&lt; 2 1)) Результат #t

(or #f #f #f) Результат #f

(define x 2)

(set! x 4)

(+ x 1)[/c

(let ((x 2)) (* x 2)) Результат 4. Создаем переменную х=2, умножаем на 2 и передаем значение. Сам х при выходе из данного выражения будет разрушен. Let позволяет создавать сколько угодно переменных, действие которых будет распространяться исключительно на тело определения (при этом в рамках одного определения не допускается использовать несколько переменных с одинаковыми идентификаторами).
(let ((x 2) (y 3))

(* x y)) Результат 6
(let ((x 2) (y 3))

(let ((x 7)

(z (+ x y)))

(* z x)))

Результат 35. В первом блоке определим х=2, у=3, переходим к исполнению тела let. Создадим второй х со значением 7, затем определяем еще одну переменную второго блока z, которая будет равна x+y (число 5) первого блока (поскольку х второго блока имеет силу только в теле второго блока, но не на этапе определения переменных этого же блока). Приступаем к исполнению тела второго блока – умножаем 5 (в данном случае, переменная z) на 7 (переменная х второго блока). Результат 35.

Как видно из примера, допускается неограниченная глубина вложенности let, внутри каждого определения допускается свободное повторение идентификаторов по отношению к другим let. В Scheme let часто используется как аналог программных скобок ({-}, begin-end) императивных языков программирования. Как правило, let используется чаще родственных ей let* и letrec.

Рассмотрим пример с let*

(let ((x 2) (y 3))

(let* ((x 7)

(z (+ x y)))

(* z x)))

Результат 70. В первом блоке определим х=2 и у=3. Далее конструкция let* определяет переменную х=7, действие которой распространяется на все определения переменных справа и на тело let*, таким образом, z=7 (новый х)+3 (у из первого блока)=10. Приступаем к выполнению тела let* - z (число 10) умножаем на х блока let* (число 7). Результат 70.

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

(letrec ((even?

(lambda (n)

(if (zero? n)

#t

(odd? (- n 1)))))

(odd?

(lambda (n)

(if (zero? n)

#f

(even? (- n 1))))))

(even? 88))

Данный пример определяет четность числа (#t, если четное). Как видно из примера, even? может вычисляться в зависимости от входящего числа через рекурсию. Еще один момент – если Вы заметили, то even? это должна быть переменная или функция, имеющая булевый тип, а 88 есть число (в рамках Scheme – не важно какое, считайте, что все числа есть комплексные величины). Здесь видна работа letrec, для тела вычисляется even? определенная не как переменная, а как функция (через lambda). Letrec часто используют для получения значения переменной через рекурсионные вызовы. Эта конструкция имеет один подводный камень – поскольку все параметры передаются по значению, должны существовать однозначные условия для получения результата. Никаких двусмысленностей в letrec быть не должно (могут возникнуть, в частности, при комбинациях родственников letrec, let и let*).

Одной из важных особенностью функциональных языков программирования является концепция функций – иными словами процедуры в обычном понимании в функциональном программировании быть не должно. Выражения и функции получают параметры и передают результат. Однако на практике часто возникают ситуации, когда результат либо не требуется, либо не определен, либо просто не имеет смысла. Самым простым примером является вывод информации на экран. Какой результат может в данном случае получить функция вывода сообщения на экран? В тоже время отсутствие результата (либо возникновение ситуации, когда результат работы функции определить невозможно) может привести программу к краху – следующая функция не сможет получить входящий параметр (либо не сможет определить что это за параметр). Явление, при котором функция проявляет себя каким-либо образом помимо передачи результата, называется побочными эффектами (явлениями). В чистом функциональном программировании побочных явлений быть не должно в принципе (например, побочным эффектом является присваивание переменной какого-либо значения, создание объектов без их непосредственной передачи (так себя ведет define), ввод и вывод данных и т.д.). Специально для решения подобных проблем существует конструкция (begin (выражение1) … (выражениеN)), все вычисления в которой осуществляются последовательно и строго слева направо. Особенностью данной конструкции является результат – он всегда будет возвращен для последнего выражения.

Пример:

(define x 0)

(begin (set! x 5)

(+ x 1)) Результат 6 (5+1)

(begin (display "4 plus 1 equals ")
(display (+ 4 1))) Результат 5 (4+1), проигнорировав результаты вывода на экран посредством display (при этом сама строка будет напечатана). Begin также удобно использовать при создании законченных блоков, содержащих несколько выражений (например в If или cond) как замена let, с той лишь разницей, что для данного блока новых переменных не создается (соответственно и не разрушаются).

Рассмотрим итерации. Хотя хвостовая рекурсия может быть преобразована в цикл (при правильном ее составлении), циклы в Scheme существуют также и в общей форме. Один из них:

(do ((&lt;переменная1&gt; &lt;инициализатор_переменной1&gt; &lt;шаг_приращения1&gt;)

...)

(&lt;тест&gt; &lt;выражение&gt; ...)

&lt;операторы_языка&gt; ...)

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

(do ((vec (make-vector 5))

(i 0 (+ i 1)))

((= i 5) vec)

(vector-set! vec i i)) Результат вектор #(0 1 2 3 4), здесь создается вектор и переменная i
(let ((x '(1 3 5 7 9)))

(do ((x x (cdr x))

(sum 0 (+ sum (car x))))

((null? x) sum)))

Результат 25, проводиться подсчет списка. Здесь создается две переменные х (обратите внимание, переменная цикла инициализируется переменной, объявленной через let) и sum.

Также если рассмотреть конструкцию let более внимательно, то можно обнаружить, что с помощью нее также можно формировать итеративные процессы. Для этого определяемую переменную можно представить как функцию (через ее инициализатор) и вызывать ее для каждого упоминания в теле let (через условные операторы cond или if).

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

В Scheme отложить вычисление можно через (delay (выражение)). Выражение вычислено не будет до конструкции force (синтаксис аналогичен). Force требует немедленного вычисления выражения (обычно используется в связке с delay).

Как видите, между delay и force может находиться произвольное число выражений, лишь бы p по-прежнему оставалось актуальным (то есть в нашем случае force должно наступить в рамках let, иначе после p перестанет существовать). На самом деле пользоваться delay и force легко, главное чтобы каждое обращение к не вычисленному параметру сопровождалось force.

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

Теперь fact можно вызывать как под старым именем, так и под именем mmm. Scheme обладает мощными средствами для образования новых возможностей языка на основе макроопределения ключевых слов (не просто синтаксическая замена), но в связи со сложностью и большим объемом материала мы далее макросы рассматривать не будем. Если есть желание, то описание работы с макросами можно найти в большой и подробной справке по PLT Scheme (справочная система называется Help Desk).

И традиционная строчка кода:

<h3 style="margin-left: 0px; padding-left: 0px;">Список сокращенных обозначений и терминов, использованных в статье</h3>

СБИС – сверхбольшие интегральные схемы.

CAD - Computer Aided Design - компьютерная поддержка конструирования, предполагает объемное и плоское геометрическое моделирование, инженерный анализ на расчётных моделях высокого уровня, оценку проектных решений, получение чертежей.

Java – язык программирования.

Хвостовая рекурсия – вид рекурсии, когда вызов функцией самой себя осуществляется в конце ее работы (используется для оптимизации (в частности уменьшает объем требуемой для рекурсионных вызовов памяти за счет автоматического преобразования рекурсии к итерационному виду).

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

Лексема – последовательность допустимых символов языка программирования, имеющая смысл для транслятора. Транслятор рассматривает программу как последовательность лексем.

Сборка мусора - одна из форм автоматического управления памятью. Специальный код, называемый сборщиком мусора (garbage collector), периодически освобождает память, удаляя объекты, которые уже не будут востребованы приложением – то есть производит сборку мусора.

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

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

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

Указатели – переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения – нулевого адреса. Значение нулевого адреса не является реальным адресом и используется только для обозначения того, что указатель в данный момент не может использоваться для обращения ни к какой ячейке памяти.

Инфекционность – свойство объекта распространять свои свойства (включая и инфекционность) на другие объекты в результате каких-либо действий.

Рациональное число (лат. ratio – отношение, деление, дробь) – число, представляемое обыкновенной дробью m/n, где числитель m – целое число, а знаменатель n – натуральное число. Такую дробь следует понимать как результат деления m на n, даже если нацело разделить не удаётся. В реальной жизни рациональные числа используются для счёта частей некоторых целых, но делимых объектов, например, тортов или других продуктов, разрезаемых на несколько частей, или для грубой оценки пространственных отношений протяжённых объектов.

Иррациональное число – это вещественное число, которое не является рациональным, то есть которое не может быть представленным в виде дроби m/n, где m – целое число, n – натуральное число.

Натуральное число – числа, возникающие естественным образом при счёте (как в смысле перечисления, так и в смысле исчисления).

Реальное, или действительное число (англ. real number, нем. reelle Zahl, лат. numerus realis) – математическая абстракция, возникшая из потребности измерения геометрических и физических непрерывных величин окружающего мира, а также проведения таких операций как извлечение корня, вычисление логарифмов, решение алгебраических уравнений [2].

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

Продолжение следует ...

Статья из четвёртого выпуска <a href="http://procoder.info/" title="перейти по ссылке">журнала "ПРОграммист".</a>

Последние записи

made in programmersforum 4

Введение в Sсheme. Часть 1

Похожие статьи

Купить рекламу на сайте за 1000 руб

пишите сюда - alarforum@yandex.ru