29 octombrie 2014

Recursivitate in limbajul PROC (EOPL 3) | Simulating recursivity in PROC language, Eopl3

PROC nu suportă recursivitatea.
Pentru a o simula, se folosește artificiul numit y-combinator și se creează un caz de test  în  tests.scm  pentru fiecare operație dorită.


1) Suma nr. 1 ... N

    (sum-1-to-N
"let p = proc(f) proc(x)
    if zero?(x) then 0 else -(((f f) -(x,1)), -(0,x))
in ((p p) 10)" 55)


2) Numerele Fibonacci:  fibo (N) = fibo (N-1) + fibo(N-2)

    (fibonacci "
let p = proc(f) proc(x)
    if zero?(x) then 0 else if zero?(-(x,1)) then 1 else -( ((f  f) -(x,1)), -(0, ((f f) -(x, 2))))
in ((p p) 10)
    " 55)


3) Înmulțirea a două numere

    (x*y
"let p = proc(f) proc(x) proc(y) proc(z)
    if zero?(z) then x else ((((f f) -(x, -(0,y))) y) -(z, 1))
in ((((p p) 0) 6) 7)" 42)


4) Factorial: N! = 1 * 2 * ... * N

    (factorial
"let multipl = proc(a) proc(b)
    let p = proc(f) proc(x) proc(y) proc(z)
        if zero?(z) then x else ((((f f) -(x, -(0,y))) y) -(z, 1))
    in ((((p p) 0) a) b)
in
    let fun = proc (f) proc(x)
        if zero?(-(x,1)) then 1 else ((multipl x) ((f f) -(x,1)))
    in ((fun fun) 5)" 120)

Niciun comentariu: