> 1 <

Автор Сообщение

entrix

Members


Статус

5 сообщений

Где: Russia
Род занятий:
Возраст:

#1879   2010-04-25 22:12 GMT+3 часа(ов)      
Такая вот тема.

Попался в поле зрения так называемый комбинатор Y .

Так вот, как работает, например, вот такая комбинация для вычисления длины списка

 (define Y-list
(lambda (l)
((lambda (le)
(le le l))
(lambda (le l)
(if (null? l)
0
(+ 1 (le le (cdr l))))))))



Понять не сложно, но вот как работает такой код.

  (define Y
(lambda (le)
((lambda (f)
(le (lambda (x) ((f f) x))))
(lambda (f)
(le (lambda (x) ((f f) x)))))))



Я до конца понять не смог.
Можно ли сиспользовать это определение y-комбинатора для вычисления факториала или длины списка,

Например,

 (define listing
(lambda (le)
(if (null? l)
0
(+ 1 (le (cdr l))))))


зависает в рекурсии.

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1881   2010-04-26 02:12 GMT+3 часа(ов)      
;Y-list эквивалентна рекурсивной f
(define (f l)
(if (null? l)
0
(+ 1 (f (cdr l)))))
 
;Y эквивалентна g
(define (g le)
(le (lambda (x) ((g le) x))))
 
;вспомогательная функция для факториала
(define (le f)
(lambda (k) (if (zero? k) 1 (* k (f (- k 1))))))
 
(define fact (g le))
 
;вспомогательная функция для count
(define (le f)
(lambda (l) (if (null? l) 0 (+ 1 (f (cdr l))))))
 
(define count (g le))

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1883   2010-04-26 02:37 GMT+3 часа(ов)      
>;Y эквивалентна g
Следовательно, Вы можете заменить в (define fact (g le)) и (define count (g le)) g на свое Y, результат будет один и тот же. g я использовал для того, чтобы Вы быстрее поняли как работает Y.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#1884   2010-04-26 03:27 GMT+3 часа(ов)      
> (define (counter init)
(let ((count init))
(lambda(msg)
(case msg
((++) (set! count (+ count 1)))
((value) count)))))
> (define Y-counter (counter 0))
> (define (y x)
(let ((f (lambda (closure)
(x (lambda args
(Y-counter '++)
(apply (closure closure) args))))))
(f f)))
> (define (length l)
((y (lambda (length)
(lambda (l len)
(if (null? l)
len
(length (cdr l) (+ len 1)))))) l 0))
> (length (vector->list (make-vector 90)))
90
> (Y-counter 'value)
90

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 5

#2004   2010-05-09 01:13 GMT+3 часа(ов)      
Почитал вот эту статейку:
http://ru.wikibooks.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D1%8B_%E2%80%94_%D1%8D%D1%82%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE!
Штука интересная. Наляпал нечто вроде интерпретатора:
 
;S: "Sxyz -> xz(yz)"
;K: "Kxy -> x"
;I: "Ix -> x"
;B: "Bxyz -> x(yz)"
;C: "Cxyz -> xzy"
;W: "Wxy -> xyy"
 
(defmacro def-basic-cmbt(name args &body body)
`(progn
(defun ,name ,args
(declare (ignorable ,@args))
,@body)
(setf (get :comb-args-count ',name) ,(length args))))
 
(def-basic-cmbt s (x y z)
"Sxyz -> xz(yz)"
(list x z
(list y z)))
 
(def-basic-cmbt k (x y)
"Kxy -> x"
(list x))
 
;===========================================================================================================
 
;---
(defun normalize (args)
(if (symbolp (first args))
args
(normalize (append (car args)
(cdr args)))))
 
(defun run (args)
(let* ((args (normalize args))
(fn (car args))
(args-count (get :comb-args-count fn)))
(if (null args-count) ; if first arg isn't defined combinator
(cons (first args)
(run-1 (cdr args)))
(if (< (1- (length args))
args-count)
args ; if invalid number of arguments - return itself
(let* ((fn-args (subseq args 1 (1+ args-count)))
(rest (subseq args (1+ args-count))))
(run (append (apply fn fn-args)
rest)))))))
 
(defun run-1(args)
(mapcar #'(lambda(x)
(if (consp x)
(run x)
x))
args))
 
;---
 
 
(defmacro calc-comb(&rest args)
`(run ',args))
 
;===========================================================================================================
 
(defmacro define-combinator (name args-count &body body)
(let ((gensyms
(loop for i below args-count collect (gensym))))
`(def-basic-cmbt ,name ,gensyms
(run (append ',body `(,,@gensyms))))))
 
(defmacro define-comb-alias(newname oldname)
`(define-combinator ,newname ,(get :comb-args-count oldname)
,oldname))
 
(define-combinator i 1
s k k)
 
(define-combinator b 3
s (k s) k)
 
(define-combinator c 3
s ((s (k s) k)(s (k s) k) s) (k k))
 
(define-combinator w 2
s s (k (s k k)))
 
(define-comb-alias cmb-true k)
 
(define-comb-alias cmb-if i)
 
(define-combinator cmb-false 1
k i)
 
(define-combinator cmb-or 2
c cmb-if cmb-true)
 
(define-combinator cmb-and 2
b (c c cmb-false) cmb-if)
 
(define-combinator cmb-not 1
c (c cmb-if cmb-false) cmb-true)
 
(define-combinator cmb-pair 2
b c (c i))
 
(define-combinator cmb-head 1
c i cmb-true)
 
(define-combinator cmb-tail 1
c i cmb-false)
 
;>>>
 
 

Например можно так:
(calc-comb c i (s b) (k i)) ;=>(I)
(calc-comb cmb-head (cmb-pair h t)) ;=>(h)
(calc-comb cmb-tail (cmb-pair h t)) ;=>(t)
 
(calc-comb cmb-or cmb-true cmb-false) ;=>(cmb-true)
(calc-comb cmb-and cmb-true cmb-false) ;=> (cmb-false)
 
(calc-comb cmb-if cmb-true x y) ;=>(X)
(calc-comb cmb-if cmb-false x y) ;=>(Y)
 


Но нумералы Черча ниасилил:
(calc-comb c i (s b) (s b (k i)) (s b (k i))) ;=>
(S B (((K I) ((((K K) I) (S B)) (S B (K I)))) (S B (K I))))
Где-то туплю.
c i (s b) == +
(s b (k i)) == 1
(s b (s b (k i))) == 2
Ведь должно быть что-то вроде (sb(sb(ki)))
Нет?

отредактировал(а) Fallen_s4e: 2010-05-09 01:31 GMT+3 часа(ов)

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 5

#2012   2010-05-09 22:17 GMT+3 часа(ов)      
Неужели никому не интересно/не знает комбинатор. логику?)
Хоть подскажите что и где чтить=)

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2017   2010-05-10 18:31 GMT+3 часа(ов)      
Цитата
Fallen_s4e :
Неужели никому не интересно/не знает комбинатор. логику?)
Хоть подскажите что и где чтить=)

А чем помочь?
Если необходимо преобразовать(выразить)
C I (S B) (S B (K I)) (S B (K I)) = S B (S B (K I)),
то можете посмотреть на мое решение

C I (S B) (S B (K I)) (S B (K I))
= C
I (S B (K I)) (S B) (S B (K I))
= I
(S B (K I)) (S B) (S B (K I))
= S
B (S B) ((K I) (S B)) (S B (K I))
= B
(S B) (((K I) (S B)) (S B (K I)))


т.е. C I (S B) (S B (K I)) (S B (K I)) = (S B) (((K I) (S B)) (S B (K I)))

Избавимся от скобок
((K I) (S B)) (S B (K I)) = K I (S B) (S B (K I))

K I (S B) (S B (K I))
= K
I (S B (K I))
= I
(S B (K I))

Тогда
K I (S B) (S B (K I)) = (S B (K I))


Собрав все вместе получим
C I (S B) (S B (K I)) (S B (K I)) = S B (S B (K I))

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2018   2010-05-10 19:08 GMT+3 часа(ов)      
Цитата
Fallen_s4e :
Но нумералы Черча ниасилил:
(calc-comb c i (s b) (s b (k i)) (s b (k i))) ;=>
(S B (((K I) ((((K K) I) (S B)) (S B (K I)))) (S B (K I))))
Где-то туплю.
c i (s b) == +
(s b (k i)) == 1
(s b (s b (k i))) == 2
Ведь должно быть что-то вроде (sb(sb(ki)))
Нет?

А Вы абсолютно уверены, что тупите?
Попробуйте доказать
(S B (((K I) ((((K K) I) (S B)) (S B (K I)))) (S B (K I)))) = (S B (S B (K I)))

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 5

#2019   2010-05-10 21:11 GMT+3 часа(ов)      
Блин, конечно тупил, когда вопрос задавал. Мне и в голову почему-то не пришло, что они могут быть равны(думал в кодировке дело).=)
Разобрался, заодно узнав пару трюков счета. Спасибо!)

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2022   2010-05-11 01:26 GMT+3 часа(ов)      
А у меня вот возникла следующая идея: а почему бы не написать интерпретатор языка программирования основанного на комбинаторной логике, например, для веб-разработки? Эта идея может показаться безумной, но она вполне осуществима.

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 5

#2023   2010-05-11 01:41 GMT+3 часа(ов)      
Мне тяжело представить как этот язык может быть полезен, разве что в аппаратной реализации для каких-то очень узких целей.
числа кодируются так, что в лучшем случае перевести в число занимает O(n). Десять тыщь в квадрате не дождаться(хотя на основе может не означать ограничиться этим и добавить нормальную поддержку чисел).
Но писать интерпретатор мне понравилось=)
Идея интересна, но в чем плюс такого языка? Расширяемость? Да, кстати очень фортом веет(хотя я не очень хорошо его знаю).
Как бы то ни было, думаю было бы интересно.=)

PS:Добавил поддержку чисел:

FIX:
(defun run (args)
(let* ((args (normalize args))
(fn (car args))
(args-count (get :comb-args-count fn)))
(if (or (null args-count) ; if first arg isn't defined combinator
(< (1- (length args)) ; or invalid number of arguments
args-count))
(cons (first args)
(run-1 (cdr args)))
(let* ((fn-args (subseq args 1 (1+ args-count)))
(rest (subseq args (1+ args-count))))
(run (append (apply fn fn-args)
rest))))))


(defun cmb-to-num(&rest cmb-exprs)
"(expr x1 x2)=(x2) -> 0
(expr x1 x2)=(x1 (x2)) -> 1
(expr x1 x2)=(x1 (x1 (x2))) -> 2 ..."
(let* ((gs (list (gensym) (gensym)))
(res (run (append (copy-list cmb-exprs) gs))))
(labels ((err(x)(error (format nil "cmb-expr ~a not a number!" x)))
(lbl(x)
(when (> (length x) 2)
(err cmb-exprs))
(cond ((eql (first x) (second gs)) 0)
((eql (first x) (first gs)) (1+ (lbl (second x))))
(t (err cmb-exprs)))))
(multiple-value-bind(resnum error)
(ignore-errors (lbl res))
(if error
(err cmb-exprs)
resnum)))))

(defun num-to-cmb(num)
(if (= num 0)
(list 'k 'i)
(list 's 'b (num-to-cmb (1- num)))))

(defmacro calc-comb(&rest args) ; rewrited
(labels ((lbl(x)
(cond ((consp x) (mapcar #'lbl x))
((symbolp x) x)
((numberp x) (num-to-cmb x))
(t (error (format nil "Unknown type ~a" x))))))
`(run ',(lbl args))))
(cmb-to-num (calc-comb cmb-+ 4 3)) ;=>7
(cmb-to-num (calc-comb cmb-* 4 3)) ;=>12
(cmb-to-num (calc-comb cmb-^ 4 3)) ;=>64

отредактировал(а) Fallen_s4e: 2010-05-11 02:09 GMT+3 часа(ов)

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2024   2010-05-11 02:01 GMT+3 часа(ов)      
>числа кодируются так, что в лучшем случае перевести в число занимает O(n).
Это в теории, а на практике никто не запрещает добавить аппаратную поддержку чисел, как это сделал Маккарти, ведь чистому лиспу не нужны числа, т.к. их можно вывести через нумералы Черча.

>Идея интересна, но в чем плюс такого языка?
Он будет выглядеть как Форт наоборот. Это Вы правильно подметили)

>PS:Добавил поддержку чисел:
Когда освобожусь, постараюсь протестировать.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2025   2010-05-11 02:12 GMT+3 часа(ов)      
Да, и с реализацией поддержки "расширенного" метапрограммирования, я думаю, не возникнет серьезных проблем.

Fallen_s4e

Members


Статус

114 сообщений
http://lisper.ru
Где: Zimbabwe lisper.ru
Род занятий: fallen_s4e
Возраст: 5

#2026   2010-05-11 02:47 GMT+3 часа(ов)      
Цитата
ведь чистому лиспу не нужны числа

Действительно.

Что значит расширенное метапрограммирование? Оно будет поддерживаться так же естественно как и в Форте и реализовывать это будет не сложно, это да.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#2029   2010-05-11 21:26 GMT+3 часа(ов)      
>Что значит расширенное метапрограммирование?
Я имел ввиду наличие специальных макросов, способных к перезаписи термов. Они должны вписываться в сам язык, т.е. сначала необходимо продумать его семантику.
> 1 <


Онлайн :

0 пользователь(ей), 28 гость(ей) :




Реклама на сайте: