LINUX.ORG.RU

Scheme + functional programming


0

0

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

В sicp предлагается вариант некого подобия ОО, это бы выглядело так:

(define make-sequence
  (lambda (values-list)
    (lambda (message)
      (cond
       ((equal? message 'add)
        (lambda (number)
          (make-sequence
           (map (lambda (value) (+ value number))
                values-list))))
       ((equal? message 'scale)
        (lambda (number)
          (make-sequence
           (map (lambda (value) (* value number))
                values-list))))
       (else
        (display "Wrong message for make-sequence"))))))

И потом использование:

(define s (make-sequence (list 0 1 2 3)))

((s 'add)   4)
((s 'scale) 2)

Но, что-то, меня смущает эта псевдо-диспетчеризация :) А если мне надо будет миллион раз вызвать (s 'add), он ведь будет миллион раз делать cond, хотя я же явно ему указываю, что я хочу.

С другой стороны, мне явно надо определять нужные операции внутри make-sequence, чтобы получить замыкание, иначе придется все параметры передавать еще куда-то дальше, а если их не один, а десять, это тоже накладно :(

Сходу я придумал такой вариант, с возвращением списка замыканий:

(define make-sequence
  (lambda (values-list)
    (list
     (lambda (number)
       (make-sequence
        (map (lambda (value) (+ value number))
             values-list)))
     (lambda (number)
       (make-sequence
        (map (lambda (value) (* value number))
             values-list))))))

(define sequence-add
  (lambda (sequence number)
    ((car sequence) number)))

(define sequence-scale
  (lambda (sequence number)
    ((cadr sequence) number)))

И использование:

(define s (make-sequence (list 0 1 2 3)))

(sequence-add   s 4)
(sequence-scale s 2)

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

Есть какая-нибудь устоявшаяся практика в реализации таких вещей?

Re: Scheme + functional programming

1. замени cond хэшем или упорядоченным списком.

2. возвращай не список, а массив (или вектор - не помню как там в схеме называется), тогда временная сложность поиска элемента по индексу будет O(1) вместо O(N).

Begemoth ★★★★★ ()

Re: Scheme + functional programming

> Изучаю сейчас сабж, и у меня возникли некоторые затруднения. 
Предположим, передо мной стоит простая задача: реализовать операции 
добавления числа и умножения на число некой последовательности чисел. 
Как это грамотно сделать с точки зрения функционального 
программирования? 

(define (add-list x list)
  (map (lambda (y) (+ x y)) list))

(define (mul-list x list)
  (map (lambda (y) (* x y)) list))

или 

(define (op-list func) 
  (lambda (x list)
    (map (lambda (y) (func x y)) list)))

(define add-list (op-list +))
(define mul-list (op-list *))

Это функциональный подход. Как потом ты эти функции будешь 
использовать - напрямую или завернешь в какой-то обобщенный API
- зависит от требований конкретной программы.

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от Begemoth

Re: Scheme + functional programming

> 1. замени cond хэшем или упорядоченным списком.

Тоже имхо какая-то полумера :) Зачем мне рыться в хеше, если я точно знаю какое замыкание я хочу вызвать.

> 2. возвращай не список, а массив (или вектор - не помню как там в схеме называется), тогда временная сложность поиска элемента по индексу будет O(1) вместо O(N).

Это вариант, кстати, я уже думал над ним :) Но все действия над вектором деструктивные, так что это уже не функциональное программирование получается :(

> (define (op-list func) (lambda (x list) (map (lambda (y) (func x y)) list)))

С этим тоже понятно, но тут нет замыкания для параметров. А если, кроме последовательности, мне надо будет передавать еще какую-нибудь ее длину, и плюс еще пять параметров, то внутреняя лябмда станет некрасивой -- (lambda (x list length param0 param1 ...) :(

swizard ()
Ответ на: Re: Scheme + functional programming от Begemoth

Re: Scheme + functional programming

> (define (op-list func) (lambda (x list) (map (lambda (y) (func x y)) list)))

Кстати, этот вариант не будет в схеме работать, потому что там одно пространство имен для функций и переменных, а list -- это функция :)

swizard ()
Ответ на: Re: Scheme + functional programming от swizard

Re: Scheme + functional programming

А это тоже не будет:

(let ((foo (lambda (x) (+ x 1)))
  (let ((foo (foo 2)))
    foo))

?

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от swizard

Re: Scheme + functional programming

> Тоже имхо какая-то полумера :) Зачем мне рыться в хеше, если я точно знаю какое замыкание я хочу вызвать.

Все зависит от требований к объектной модели. Этот подход используется, например, в Objective-C (а также ЕМНИП Python, Ruby). Он позволяет добавлять методы к существующим классам, ну и на тему MOP можно извратиться :-)

> Это вариант, кстати, я уже думал над ним :) Но все действия над вектором деструктивные, так что это уже не функциональное программирование получается :(

Все? vector-set! только!

> С этим тоже понятно, но тут нет замыкания для параметров. А если, кроме последовательности, мне надо будет передавать еще какую-нибудь ее длину, и плюс еще пять параметров, то внутреняя лябмда станет некрасивой -- (lambda (x list length param0 param1 ...) :(

А вот это уже abstract data types :-) Напиши для начала макры для структур. Поверх них - определи наследование структур. Ну и в конце добавь виртуальные методы (через массив).

ЕМНИП в guile есть аналог CLOS, причем практически полностью сделанный на макрах. Можно еще посмотреть на реализацию CLOS.

Вот еще: ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1014.pdf ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-602.pdf

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от Begemoth

Re: Scheme + functional programming

> А это тоже не будет:

> (let ((foo (lambda (x) (+ x 1))) (let ((foo (foo 2))) foo))

Черт, был не совсем прав :) И то и то работать будет, но в первом случае переопределится list, и использовать его как функцию внутри лямбды уже не получится.

> Все зависит от требований к объектной модели. Этот подход используется, например, в Objective-C (а также ЕМНИП Python, Ruby). Он позволяет добавлять методы к существующим классам, ну и на тему MOP можно извратиться :-)

Да, но ведь это неминуемо влечет за собой снижение производительности :( Конкретно мне ооп, получается, нужен совсем в минимуме, все остальное достаточно удобно решается самой схемой

> А вот это уже abstract data types :-) Напиши для начала макры для структур. Поверх них - определи наследование структур...

Большое спасибо за ссылки, сейчас сделал что-то подобное Soft Objects на макрах :) Очень удобно, хотя главной моей проблемы это не решило -- как сделать замыкание глобально видимым, чтобы можно было быстро до него добраться. Пока реализовал это через вектор, но буду еще думать :)

swizard ()
Ответ на: Re: Scheme + functional programming от swizard

Re: Scheme + functional programming

Какие черты ООП тебе нужны? А то не представляя твоей задачи сложно что-либо посоветовать :-)

По поводу ООП и ФП - погугли на тему ООП в Haskell. Вообще ФП более мощная штука, чем ООП и невсегда нужно применять привычные(?) (ООП в смысле) приемы проектирования.

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от Begemoth

Re: Scheme + functional programming

> Вообще ФП более мощная штука, чем ООП и невсегда нужно применять привычные(?) (ООП в смысле) приемы проектирования.

Ага, я и пытаюсь сейчас отойти от привычной мне парадигмы и освоить фп. 

Вот у меня сейчас более конкретная задача -- в процессе осваивания схемы я сделал симулятор back-propagation нейросети. Без деструктивных операций, но совсем без применения привычного ооп у меня не получилось -- например:

(define make-processing-unit
  (lambda (input-weights
           weights-deltas
           activate-func
           learn-filter
           output-value
           error-value)
    (lambda (m)
      (cond ((equal? m 'propagate) ...)
            ((equal? m 'adjust-weights) ...)
            ((equal? m 'set-error) ...) 
  ...))

Я пока не могу взять в толк, как это дело разбить на независимые функции, без необходимости тащить в параметрах каждой input-weights, weights-deltas и прочее :( 
С замыканиями получается удобно, но чтобы вытащить эти замыкания "наружу" из make-processing-unit, нужна либо диспетчеризация, либо список, либо надо использовать деструктивные операции. 
При обучении сети тот же make-processing-unit может многие тысячи раз вызываться, и затраты на диспетчера сообщений уже начинают напрягать :(

swizard ()
Ответ на: Re: Scheme + functional programming от swizard

Re: Scheme + functional programming

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

type processing_unit = { 
   input_weight : float list; 
   weight_deltas  : float list;
   (* и т.д. *)
}

в схеме нужно ввести соглашение о том, что значения processing-unit имеют вид:

#(processing-unit input-weights weights-deltas ... )

далее процедуры оперирующие значениями processing-unit будут иметь вид:

(define (processing-unit-propagate pu)
  (if (not (eq (vector-ref pu 0) 'processing-unit))
    (error "not a processing-unit"))
  (let ((input-weights (vector-ref pu 1))
        (weights-deltas (vector-ref pu 2)
        ;; и т.д.
        )
     ;; тут код...
     ))

Еще можно сделать так:

(define (make-processing-unit input-weights
           weights-deltas
           activate-func
           learn-filter
           output-value
           error-value)
   (lambda (i)
     (case i 
       (0 input-weights)
       (1 weights-deltas)
       ;; и т.д.
     )))

Так лучше скрыта структура, но эффективноть будет ниже.

Вообще есть такая штука SRFI (Scheme Request for Implementation srfi.schemers.org) называется. Реализации схемы поддерживают некоторое подмножество этих спецификаций (из тех, что я использовал в mzscheme реализовано много SRFI). Кроме того есть и собственные (реализаций) аналоги defstruct из Common Lisp.

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от swizard

Re: Scheme + functional programming

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

Begemoth ★★★★★ ()
Ответ на: Re: Scheme + functional programming от Begemoth

Re: Scheme + functional programming

> Т.к. в схеме типизация динамическая, что там не нужны кортежи - достаточно списков или векторов.

Блин, точно :) Что-то я не додумался до такого элементарного решения, спасибо =)

> Еще можно сделать так:

Я сейчас попроще сделал, макрос define-struct

(define-struct processing-unit (weights activate-func learn-filter output-value error-value))

который раскрывается в

(define make-processing-unit (...

(define processing-unit-weights (lambda (processing-unit) (...

(define processing-unit-activate-func (lambda (processing-unit) (...

...

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

swizard ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.