О языке программирования Scheme

  0. Небольшое вступление.

  Данная заметка посвящена языку программирования(ЯП) Scheme.

  В сети достаточно информации по этому ЯП, например весьма неплохое руководство http://www.scheme.com/tspl2d
(часть описанных мною примеров взяты частично или полностью из этого руководства), кроме того при желании можно найти небезызвестную книгу "Structure and Implementation of Computer Programs" (SICP), являющуюся одной из лучших книг по программированию вообще и по Scheme в частности. Поэтому целью данной заметки является не очередное "пересказывание" этих трудов, а скорее попытка объяснить Scheme, его особенности, возможности так сказать "на пальцах". В частности я буду описывать, что сам уже смог понять, узнать о Scheme и программировании.

  Scheme как и Lisp является мультипарадигменным языком программирования "почти без синтаксиса", разработанный в Массачуссетском Институте Технологий. Некоторые называют Scheme языком функционального программирования(ФП), приравнивая таким образом его к чисто функциональным языкам на подобии Haskell, однако, несмотря на то, что Scheme позволяет писать код в стиле ФП, такое приравнивание некорректно. Более точное и подробное описание языка вы можете найти в Википедии, там же найдете и еще некоторые полезные ссылки.

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

  1. Немного о "почти отсутствующем синтаксисе".

  В отличие от более распространенных и привычных ЯП, таких как C, C++, Pascal, Java, PHP и т. д., в Scheme и Lisp используется префиксная запись функций и операторов, а также огромное количество скобок, что может отпугнуть новичков от изучения языка, однако чем дальше вы зайдете в изучении Scheme, тем больше вы будете понимать, что это очень удобная форма записи, открывающая большие возможности для манипулирования кодом и данными. Впрочем не исключен эффект еще большего отторжения =). В этом случае взгляните на Forth, где используется польская, постфиксная нотация, она вам покажется еще более непривычной, и отталкивающей =).

  Итак, вот несколько примеров программ на Scheme:

(* 1 2 3 4 5)  ; Произведение чисел от 1 до 5

(define (square x)  ; Объявление функции возведения в квадрат как
  (* x x))          ;   произведение аргумента на самого себя

(define (abs x)  ; Объявление функции модуля:
  (if (< x 0)    ;   особая форма if вычисляет первый аргумент (функцию <, сравнивающую значение аргумента x с нулем) и
      (- x)      ;     возвращает результат вычисления второго аргумента, если первый вернул #t (истину) или
      x))        ;     третьего в противном случае


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

(funcname arg1 arg2 arg3 ... argN) 

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

(define (is func)             ; Объявление функции is от func как
  (lambda (a b) (func a b)))  ;   возвращающую функцию от a, b, вычисляющую функцию func от a, b
(define greater? (is >))
(let ((x 1) (y 2))
  (greater? x y))


  Исключениями являются только особые формы (в данном примере это define и if), которые определяются макросами и тем не менее незначительно отличаются от формы вызова функции. Символ ; означает начало комментария, весь текст, находящийся за ним и до конца строка игнорируется интерпретатором.
  Вот и почти весь синтаксис. Некоторые другие "знаки препинания", отличающиеся от вышеуказанной формы синтаксиса и являющиеся в большинстве своем "синтаксическим сахаром" мы рассмотрим позже, по мере необходимости.

  2. Немного о списках.

  Основной структурой данных в Scheme, как и в Lisp, является список. Основные функции работы со списками:

(cons 1 2)                      ; возвращает пару значений: (1 . 2)
(cons 1 '())                    ; возвращает список из одного элемента: (1)
(list 1 2 3)                    ; Возвращает список значений: (1 2 3)
(cons 1 (cons 2 (cons 3 '())))  ; возвращает список значений: (1 2 3)
(car (list 1 2 3))              ; возвращает значение первого элемента(головы) списка (1 2 3): 1
(cdr (list 1 2 3))              ; возвращает список, начинающийся со второго элемента(хвост) списка (1 2 3): (2 3)


  Конструкция '() обозначает пустой список, символ ' же обозначает цитирование и является синтаксическим сахаром для особой формы (quote ...). Например вызов функции

(list 1 2 3)  ; можно заменить на конструкцию:
'(1 2 3)

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

(let ((x 1) (y 2) (z 3))   ; Пусть x = 1, y = 2, z = 3, тогда:
  (list x y z))            ;   вернет список значений переменных x, y и z: (1 2 3)
(let ((x 1) (y 2) (z 3))
  '(x y z))                ; вернет список символов x y и z: (x y z)

  3. О макросах.

  Макросы позволяют создавать новые особые формы, расширяя тем самым синтаксис языка. Например:

(define-syntax my-if           ; Объявляем имя синтаксической конструкции
  (syntax-rules (then else)    ; описываем правила: в первом списке -- (then else) --
                               ;   перечисляем слова, которые будут невычисляемыми, а ля "зарезервированные слова"
                               ; в последующих списках описываются шаблоны, которые будет обрабатывать макросом
                               ;   и собственно обработчики:

    ((_ condition then on-true else on-false)  ; здесь описываем шаблон конструкции: _ -- сюда подставляется имя макроса,
                               ;   можно написать my-if вместо _ , без разницы
                               ;   then и else как мы описали раньше просто слово,
                               ;   condition, on-true и on-false -- так сказать локальные переменные макроса,
                               ;   выражения, переданные в них -- вычисляемые
     (if condition on-true on-false))  ; а это обработчик шаблона. шаблонов может быть несколько, например можно добавить еще 2:
    ((_ condition then on-true)
     (if condition on-true))
    ((_ condition else on-false)
     (if (not condition) on-false))
))                             ; здесь закрываем списки особых форм syntax-rules и define-syntax.

; теперь мы можем пользоваться придуманным макросом:
(my-if (> 2 4) then (display "Y\n") else (display "N\n"))
(my-if (> 4 2) then (display "Y\n"))
(my-if (> 4 2) else (display "Y\n"))


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

  Еще один пример, показывающий реализацию операторов i++, i--, x += y, x -= y, x *= y и x /= y, содержащий в том числе и элементы метапрограммирования: макрос make-op сам создает для нас макросы, определяющие четыре последних оператора:

(define-syntax make
  (syntax-rules ()
    ((_ op func)
     (define-syntax op
       (syntax-rules ()
     ((_ x y)
      (begin (set! x (func x y)) x)))))))

(make += +)
(make -= -)
(make *= *)
(make /= /)

(define-syntax ++
  (syntax-rules ()
    ((_ i)
     (begin (set! i (+ i 1)) i))))

(define-syntax --
  (syntax-rules ()
    ((_ i)
     (begin (set! i (- i 1)) i))))

;--------------------------------
; Пробуем работу:

(define x1 2)
(define x2 3)
(message "x1 = " x1 "; x2 = " x2)
(++ x1)
(+= x2 (-- x2))
(message "x1 = " x1 "; x2 = " x2)
(+= x1 x2) (message "x1 = " x1)
(*= x1 x2) (message "x1 = " x1)
(-= x1 x2) (message "x1 = " x1)
(/= x1 x2) (message "x1 = " x1)

  4. О карринге, замыканиях и функциях высшего порядка.

  Теперь примерчик с каррингом (приведение функции n аргументов к функции одного аргумента, возвращающей функцию n-1 аргументов) и функций высшего порядка (функции, оперирующие другими функциями):

(define (make-val-list v0 dv vN)
  (define (make-list v)
    (if (= v vN)
    (cons v '())
    (cons v (make-list (+ v dv)))))
  (make-list v0))

(define A-list (make-val-list 1 1 3))
(define x-list (make-val-list 0.2 0.1 1.2))

(define (y A)
  (lambda (x) (- (* A x) (tan (* pi (/ x 4))))))

(define y-list (map (lambda (A)
              (map (y A) x-list))
            A-list))

(display (map (lambda (ls) (apply max ls)) y-list))


  В данном коде функция-от(x,A) сведена к функции y(A), возвращающей функцию-от(х), т.е. ее можно было бы применять так:

(let ((A1 1) (x1 0.2))
  ((y A1) x1))


  Карринг очень похож на замыкание как я понял, только замыкание проявляется в следующих действиях:

(define y1 (y 1)) ; создаст функцию (y1 x) = (- (* 1 x) (tan (* pi (/ x 4))))
(define y2 (y 2)) ; создаст функцию (y1 x) = (- (* 2 x) (tan (* pi (/ x 4))))
(y1 x1)
(y2 x1)


  В примере применялись функции высшего порядка map и apply, они работают следующим образом:

  1) map применяет переданую ей в качестве переданного аргумента функцию к каждому элементу списка, переданного вторым аргументом, и возвращает список значений-результаттов применения, например

(define test-list '(-2 1 7 0 -5 4))
(map abs test-list)                  ; вернет список абсолютных величин значений списка test-list: (2 1 7 0 5 4)


  2) apply применяет переданную ей в качестве первого аргумента функцию ко всем элементам списка, переданного вторым аргументом,
как буд-то они (элементы списка) являются параметрами переданной функции, например функции

(max -2 1 7 0 -5 4)  ; \
(+ -2 1 7 0 -5 4)    ; _вернут максимальное значение и сумму значений переданных в качестве параметров соответственно.

однако попытка вызвать их таким образом:

(max test-list)      : \
(+ test-list)        ; _выдаст ошибку.


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

(apply max test-list)  ; \
(apply + test-list)    ; _эквивалентны выражениям
(max -2 1 7 0 -5 4)    ; \
(+ -2 1 7 0 -5 4)      ; _соответственно.


  И в завершении вернемся к каррингу. Как видно из описания функции map, она может оперировать только функциями одной переменной. Вот тут-то к нам и приходят на помощь карринг и замыкания =).

  5. Немного о функциях и макросах с произвольным количеством аргументов.

  Как вы уже заметили, некоторые функции и формы могут принимать произвольное количество аргументов, например:

(+ 1 2 3)
(+ 1 2 3 4)
(and exp1 exp2)
(and exp1 exp2 exp3 exp4)


  Чтобы создать подобную функцию, необходимо использовать точечную запись аргументов, например:

(define (message head . tail)
  (display head)
  (for-each display tail)
  (newline))


  В таком определении функции первый аргумент будет передаваться в нее непосредственно, параметром head, а все остальные -- списком tail. Здесь используется еще одна функция высшего порядка for-each, которая применяет функцию, переданную в качестве первого аргумента к каждому элементу списка, переданного вторым аргументом, но в отличие от функции map не возвращает никакого значения. теперь можно так применять функцию message:

(message "Hello World!")
(let ((world "World"))
  (message "Hello " world "!"))


  Определить форму, принимающую произвольное количество аргумента, можно подобным образом:

(define-syntax and
  (syntax-rules ()
    ((_) #t)
    ((_ e) e)
    ((_ e1 e2 e3 ...)
     (if e1 (and e2 e3 ...) #f))))


  Тогда можно будет использовать новую форму таким образом:

(let ((x     2)
      (x-min 1)
      (x-max 3))
  (and (> x x-min)
       (< x x-max)
       (not (= x 0))))




  На этом я завершаю свой обзор. Надеюсь он оказался/окажется для кого-то полезным, для кого-то интересным. =)

похожие страницы

  1. Программирование для дебилов - это реальность
  2. О языке программирования Scheme. Часть вторая.
  3. Государственная политика в области СПО
  4. Полезные ссылки
  5. На сайте президента России ошибки по Фрейду

#1:

Ну и форматирование

ответить  2009-02-26 22:02:45 

#2:  korvin:

да, с форматированием я тут пока не освоился

ответить  2009-02-27 14:48:55 

#3:

Определить форму, принимающую произвольное количество аргумента
Макросы не обязательны, есть запись вида (lambda args body...), при вызове в args попадает список всех аргументов, по суте тоже что и точечьная нотация, только позволяет вызывать совсем уже произвольное кол-во аргументов (включая 0). Отсюда выходит макрос case-lambda, который является удобным сахарком, типа:
(define foo
(case-lambda
(() 'bar)
((x y) (+ x y))))

ответить  2009-03-09 00:46:02 

#4:  korvin:

ну все-таки функция с произвольным количеством параметров -- это не то же самое, что и макрос с произвольным количеством параметров, но вообще за форму (lambda args body) спасибо, я что-то даже не подумал, что так можно =)

ответить  2009-03-09 10:46:40 

#5:

Зря Вы на о Forth'е так нелестно отозвались. Очень интересный язык. Единственный его недостаток (а также достоинство!) -- это его простота. Из-за этого свои реализации Forth'а вместе с библиотеками пишут все, кому не лень. В результате, сколько-нибудь сложная программа, написанная на одной реализации с большо

ответить  2012-09-03 09:27:28 

#6:

прошу прощение за разрыв комментария

... с большой вероятностью не заработает на другой реализации. Похожая проблема есть и у Scheme.

ответить  2012-09-03 09:28:56