Scheme/Tutorial/3: различия между версиями

Материал из ALT Linux Wiki
м Alterator/internals/3» переименована в «Scheme/Tutorial/3»)
м (вычитка)
 
(не показано 8 промежуточных версий 6 участников)
Строка 1: Строка 1:
[[Category:Sisyphus]]
Третья часть рассказа. Наверное, самая сложная, но если что-то будет неясно — ничего страшного, в следующих частях всё постепенно прояснится.
{{MovedFromFreesourceInfo|AltLinux/Sisyphus/Alterator/internals/3}}
 
Третья часть рассказа. Наверное самая сложная, но если что-то будет неясно - ничего страшного, в следующих частях всё постепенно прояснится.


==== 6 Несколько замечаний про функции ====
==== 6 Несколько замечаний про функции ====
В прошлый раз было подробно рассказано как описываются функции. Несколько полезных замечаний:
В прошлый раз было подробно рассказано, как описываются функции. Несколько полезных замечаний:


1. У длинного определения
1. У длинного определения
Строка 14: Строка 11:
<tt>(define (f) ... )</tt>
<tt>(define (f) ... )</tt>


2. Процедура является таким же полноправным типом данных как и числа и строки, поэтому их можно как передавать в качестве аргумента, так и возвращать в качестве ответа.
2. Процедура является таким же полноправным типом данных, как и числа и строки, поэтому их можно как передавать в качестве аргумента, так и возвращать в качестве ответа.
Вот, например, как можно было бы определить функцию "модуль числа":
Вот, например, как можно было бы определить функцию «модуль числа»:
<tt>(define (abs x) ((if (< x 0) - +) x))</tt>
<tt>(define (abs x) ((if (< x 0) - +) x))</tt>


Строка 35: Строка 32:
==== 7 О символах ====
==== 7 О символах ====


Из чего сделана переменная? Переменная -- это некоторое "имя" и "связь" между этим именем и каким-то объектом, и прежде всего именно "связь" (связи может не быть, а имена есть всегда). То есть можно рассматривать по отдельности: отдельно имя, и отдельно некоторая таблица, которая ставит соответствие между именами и объектами, на которые они ссылаются.
Из чего сделана переменная? Переменная — это некоторое «имя» и «связь» между этим именем и каким-то объектом, и прежде всего именно «связь» (связи может не быть, а имена есть всегда). То есть можно рассматривать по отдельности: отдельно имя, и отдельно некоторая таблица, которая ставит соответствие между именами и объектами, на которые они ссылаются.


<pre>(define a 4)</pre>
<pre>(define a 4)</pre>


Это значит есть, имя <tt>a</tt> и оно ссылается на объект - число <tt>4</tt>.
Это значит, есть имя <tt>a</tt> и оно ссылается на объект — число <tt>4</tt>.


Когда интерпретатор видит выражение <tt>(define b a)</tt>, он обнаруживает наличие имени <tt>a</tt>, а потом производит поиск в своей таблице имён, отмечает, что <tt>a</tt> ссылается на объект  - число <tt>4</tt> и производит подстановку, после которой выражение приобретает вид <tt>(define b 4)</tt>.
Когда интерпретатор видит выражение <tt>(define b a)</tt>, он обнаруживает наличие имени <tt>a</tt>, а потом производит поиск в своей таблице имён, отмечает, что <tt>a</tt> ссылается на объект — число <tt>4</tt> и производит подстановку, после которой выражение приобретает вид <tt>(define b 4)</tt>.


А что если мы хотим получить просто "имя"? Тогда мы говорим интерпретатору: пожалуйста, не надо размышлять над следующим выражением, дай мне его "как есть" - эта процедура носит имя <tt>quote</tt>.
А что если мы хотим получить просто «имя»? Тогда мы говорим интерпретатору: пожалуйста, не надо размышлять над следующим выражением, дай мне его «как есть» — эта процедура носит имя <tt>quote</tt>.
<tt>(define b (quote a))</tt> - назначит "имени" <tt>b</tt>, уже не не <tt>4</tt>, а просто "имя" <tt>a</tt>.
<tt>(define b (quote a))</tt> назначит «имени» <tt>b</tt> уже не <tt>4</tt>, а просто «имя» <tt>a</tt>.


"имена" являются одним из типов данных схемы и называются символами.
«имена» являются одним из типов данных схемы и называются символами.
У длинного варианта записи <tt>(quote объект)</tt> существует сокращенный: <tt>'объект</tt>
У длинного варианта записи <tt>(quote объект)</tt> существует сокращенный: <tt>'объект</tt> — то есть можно написать так: <tt>(define b 'a)</tt>
То есть можно написать так: <tt>(define b 'a)</tt>


Чтобы ещё лучше прочувствовать символы, запустим интерпретатор. Мы будем вводить выражения, а он будет писать, во что они проинтерпретировались:
Чтобы ещё лучше прочувствовать символы, запустим интерпретатор. Мы будем вводить выражения, а он будет писать, во что они проинтерпретировались (пакет ''gambit''):
<pre>$ gambsc
<pre>$ gsc
Gambit Version 4.0 beta 12
Gambit v4.5.3


> (define a 5)
> (define a 5)
Строка 69: Строка 65:
></pre>
></pre>


Обратите внимание на то что переменной <tt>b</tt> нет (точнее связи нет), но "имя" <tt>b</tt> без связи с чем-либо замечательно интерпретируется.
Обратите внимание на то, что переменной <tt>b</tt> нет (точнее, связи нет), но «имя» <tt>b</tt> без связи с чем-либо замечательно интерпретируется.


Не сильно огорчайтесь, если чего-то сейчас не ясно, всё прояснится, когда мы чуть глубже поймём, как работает интерпретатор.
Не сильно огорчайтесь, если что-то сейчас неясно — всё прояснится, когда мы чуть глубже поймём, как работает интерпретатор.


==== 8 Универсальный клей ====
==== 8 Универсальный клей ====


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


Scheme предлагает только один способ сделать составной тип - объединение двух объектов в пару.
Scheme предлагает только один способ сделать составной тип — объединение двух объектов в пару.
Делается это так:
Делается это так:
<pre>(cons 3 4) ; "создать пару из 3 и 4"
<pre>(cons 3 4) ; "создать пару из 3 и 4"
(cons "aaa" "bbb")</pre>
(cons "aaa" "bbb")</pre>
Доступ к первому и второму элементу пар обеспечивают функции <tt>car</tt> и <tt>cdr</tt>: // ''где-то видел мнемоническую историю...''
Доступ к первому и второму элементу пар обеспечивают функции <tt>car</tt> и <tt>cdr</tt>: // CAR (Contents of Address Register), CDR (Contents of Decrement Register). На этих регистрах вычислительной машины IBM 605 автор Лиспа Джон Маккарти хранил голову и хвост списка в первой реализации Лисп-системы.
<pre>(define a (cons 'first 'second))
<pre>(define a (cons 'first 'second))
(car a) ; получить первый элемент пары, то есть "имя" "first"
(car a) ; получить первый элемент пары, то есть "имя" "first"
Строка 87: Строка 83:


Пары вполне достаточно, чтобы создать такую известную структуру как односвязный список.
Пары вполне достаточно, чтобы создать такую известную структуру как односвязный список.
Для этого первый элемент пары будет ссылаться на содержимое элемента списка, а второй - на следующий элемент списка. Последний элемент списка должен ссылаться на "никого нет", мы для этого введём специальное имя <tt>()</tt>.  
Для этого первый элемент пары будет ссылаться на содержимое элемента списка, а второй — на следующий элемент списка. Последний элемент списка должен ссылаться на «никого нет», мы для этого введём специальное имя <tt>()</tt>.


Вот например так создаётся список из двух элементов, содержащих <tt>3</tt> и <tt>4</tt>:
Вот, например, так создаётся список из двух элементов, содержащих <tt>3</tt> и <tt>4</tt>:
<pre>(define elem2 (cons 4 '() )) ; второй элемент содержит 4 и ссылается на "никого больше нет"
<pre>(define elem2 (cons 4 '() )) ; второй элемент содержит 4 и ссылается на "никого больше нет"
(define elem1 (cons 3 elem2)) ; первый элемент содержит 3 и ссылается на второй</pre>
(define elem1 (cons 3 elem2)) ; первый элемент содержит 3 и ссылается на второй</pre>


В "развернутом виде" это выглядит так:
В «развернутом виде» это выглядит так:
<tt>(define elem1 (cons 3 (cons 4 '())))</tt>
<tt>(define elem1 (cons 3 (cons 4 '())))</tt>


Строка 99: Строка 95:
<tt>(cons 1 (cons 2 (cons 3 '())))</tt>
<tt>(cons 1 (cons 2 (cons 3 '())))</tt>


Как видно конструкция очень громоздкая, поэтому есть более короткий вариант:
Как видно, конструкция очень громоздкая, поэтому есть более короткий вариант:
<tt>(list 1 2 3)</tt>
<tt>(list 1 2 3)</tt>


Строка 108: Строка 104:
(cdr a) ; получить "хвост", то есть ссылку на второй элемент
(cdr a) ; получить "хвост", то есть ссылку на второй элемент
(car (cdr a)) ; получить содержимое второго элемента
(car (cdr a)) ; получить содержимое второго элемента
(cdr (cdr a)) ; получить "хвост" после второго элемента, то есть третий элемент</pre>
(cdr (cdr a)) ; получить "хвост" после второго элемента, то есть ссылку на третий элемент
(car (cdr (cdr a))) ; получить третий элемент</pre>


Опять-таки для веера из <tt>car</tt> и <tt>cdr</tt> существует сокращенные варианты записи:
Опять-таки для веера из <tt>car</tt> и <tt>cdr</tt> существует сокращенные варианты записи:


вместо (car (car .. - (caar ..
вместо (car (car .. — (caar ..
вместо (car (cdr .. - (cadr ..
вместо (car (cdr .. — (cadr ..
вместо (car (cdr (cdr ... - (caddr ..
вместо (car (cdr (cdr … — (caddr ..
вместо (car (car (cdr ... - (caadr ..
вместо (car (car (cdr … — (caadr ..
вместо (car (cdr (cdr (cdr .. - (cadddr ..
вместо (car (cdr (cdr (cdr .. — (cadddr ..


Надеюсь что уловили закономерность? Впрочем пользоваться этим скорее всего не придётся. В нашем примере:
Надеюсь, уловили закономерность? Впрочем, пользоваться этим, скорее всего, не придётся. В нашем примере:
<pre>(cadr a) ; получить содержимое второго элемента
<pre>(cadr a) ; получить содержимое второго элемента
(caddr a) ; получить содержимое третьего элемента
(caddr a) ; получить содержимое третьего элемента
(cdddr a) ; получить "хвост" третьего элемента, то есть "никого нет" или символ "()".</pre>
(cdddr a) ; получить "хвост" третьего элемента, то есть ссылку на
"никого нет" или символ "()".</pre>
 
'''[[Scheme/Tutorial/4|далее>>]]'''


[[Alterator/internals/4|Продолжение будет ...]]
{{Category navigation|title=Scheme|category=Scheme|sortkey=Tutorial}}

Текущая версия от 11:33, 11 мая 2012

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

6 Несколько замечаний про функции

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

1. У длинного определения (define f (lambda (x y) ... )) есть более короткая форма (define (f x y) ... ) если процедура без аргументов, то определение в упрощённой форме будет выглядеть как: (define (f) ... )

2. Процедура является таким же полноправным типом данных, как и числа и строки, поэтому их можно как передавать в качестве аргумента, так и возвращать в качестве ответа. Вот, например, как можно было бы определить функцию «модуль числа»: (define (abs x) ((if (< x 0) - +) x))

3. Дополнение к предыдущему. Если вас не смущает сведение выражения:

(define a (+ 1 2))
(* a 5)

к:

(* (+ 1 2) 5)

то не должно смущать и сведение:

(define f (lambda (x) (+ x x))
(g f)

к:

(g (lambda (x) (+ x x)))

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

7 О символах

Из чего сделана переменная? Переменная — это некоторое «имя» и «связь» между этим именем и каким-то объектом, и прежде всего именно «связь» (связи может не быть, а имена есть всегда). То есть можно рассматривать по отдельности: отдельно имя, и отдельно некоторая таблица, которая ставит соответствие между именами и объектами, на которые они ссылаются.

(define a 4)

Это значит, есть имя a и оно ссылается на объект — число 4.

Когда интерпретатор видит выражение (define b a), он обнаруживает наличие имени a, а потом производит поиск в своей таблице имён, отмечает, что a ссылается на объект — число 4 и производит подстановку, после которой выражение приобретает вид (define b 4).

А что если мы хотим получить просто «имя»? Тогда мы говорим интерпретатору: пожалуйста, не надо размышлять над следующим выражением, дай мне его «как есть» — эта процедура носит имя quote. (define b (quote a)) назначит «имени» b уже не 4, а просто «имя» a.

«имена» являются одним из типов данных схемы и называются символами. У длинного варианта записи (quote объект) существует сокращенный: 'объект — то есть можно написать так: (define b 'a)

Чтобы ещё лучше прочувствовать символы, запустим интерпретатор. Мы будем вводить выражения, а он будет писать, во что они проинтерпретировались (пакет gambit):

$ gsc 
Gambit v4.5.3

> (define a 5)
> 5
5
> a
5
> 'a
a
>
> b
*** ERROR IN (console)@5.1 -- Unbound variable: b
1> 
> 'b
b
>

Обратите внимание на то, что переменной b нет (точнее, связи нет), но «имя» b без связи с чем-либо замечательно интерпретируется.

Не сильно огорчайтесь, если что-то сейчас неясно — всё прояснится, когда мы чуть глубже поймём, как работает интерпретатор.

8 Универсальный клей

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

Scheme предлагает только один способ сделать составной тип — объединение двух объектов в пару. Делается это так:

(cons 3 4) ; "создать пару из 3 и 4"
(cons "aaa" "bbb")

Доступ к первому и второму элементу пар обеспечивают функции car и cdr: // CAR (Contents of Address Register), CDR (Contents of Decrement Register). На этих регистрах вычислительной машины IBM 605 автор Лиспа Джон Маккарти хранил голову и хвост списка в первой реализации Лисп-системы.

(define a (cons 'first 'second))
(car a) ; получить первый элемент пары, то есть "имя" "first"
(cdr a) ; получить второй элемент пары, то есть "имя" "second"

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

Вот, например, так создаётся список из двух элементов, содержащих 3 и 4:

(define elem2 (cons 4 '() )) ; второй элемент содержит 4 и ссылается на "никого больше нет"
(define elem1 (cons 3 elem2)) ; первый элемент содержит 3 и ссылается на второй

В «развернутом виде» это выглядит так: (define elem1 (cons 3 (cons 4 '())))

Если захотим сделать список из трёх элементов 1, 2 и 3, то надо написать: (cons 1 (cons 2 (cons 3 '())))

Как видно, конструкция очень громоздкая, поэтому есть более короткий вариант: (list 1 2 3)

Поскольку список склеен из пар, то и работать с ним можно при помощи при помощи тех же car и cdr. (define a (list 1 2 3))

(car a) ; получить содержимое первого элемента
(cdr a) ; получить "хвост", то есть ссылку на второй элемент
(car (cdr a)) ; получить содержимое второго элемента
(cdr (cdr a)) ; получить "хвост" после второго элемента, то есть ссылку на третий элемент
(car (cdr (cdr a))) ; получить третий элемент

Опять-таки для веера из car и cdr существует сокращенные варианты записи:

вместо (car (car .. — (caar .. вместо (car (cdr .. — (cadr .. вместо (car (cdr (cdr … — (caddr .. вместо (car (car (cdr … — (caadr .. вместо (car (cdr (cdr (cdr .. — (cadddr ..

Надеюсь, уловили закономерность? Впрочем, пользоваться этим, скорее всего, не придётся. В нашем примере:

(cadr a) ; получить содержимое второго элемента
(caddr a) ; получить содержимое третьего элемента
(cdddr a) ; получить "хвост" третьего элемента, то есть ссылку на 
"никого нет" или символ "()".

далее>>