Scheme - Optimization of operator calls (fold in particular)

Author

Optimization of operator calls (fold in particular)

Terrence Brannon, Scheme Hacker

2004-07-12, 8:58 pm

If you read through the sample implementation of SRFI-1:

http://srfi.schemers.org/srfi-1/srfi-1-reference.scm

You will see the following for append-reverse()

;(define (append-reverse rev-head tail) (fold cons tail rev-head))

;;; Hand-inline the FOLD op for speed.

(define (append-reverse rev-head tail)
(let lp ((rev-head rev-head) (tail tail))
(if (null-list? rev-head) tail
(lp (cdr rev-head) (cons (car rev-head) tail)))))

======

My question is: do any Scheme implementations automatically "unroll" a call to
fold into the optimized version of the code that Olin had to hand-code?

A more general question is: do any functional languages do such automatic unrolling?

Marcin 'Qrczak' Kowalczyk

2004-07-13, 4:00 pm

On Mon, 12 Jul 2004 21:57:02 +0000, Terrence Brannon, Scheme Hacker wrote:

> A more general question is: do any functional languages do such automatic unrolling?

Glasgow Haskell Compiler does:

[qrczak ~]$ cat Test.hs
module Test where
appendReverse revHead tail = foldl (flip (:)) tail revHead
[qrczak ~]$ ghc -O -c -no-recomp -ddump-stg Test.hs

==================== STG syntax: ====================
Test.poly_lgo =
\r [z1 ds]
case ds of wild {
GHC.Base.: x xs1 ->
let { sat_s18B = NO_CCS GHC.Base.:! [x z1]; } in Test.poly_lgo sat_s18B xs1;
GHC.Base.[] -> z1;
};
SRT(Test.poly_lgo): []
Test.appendReverse = \r [revHead tail] Test.poly_lgo tail revHead;
SRT(Test.appendReverse): []

--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

Abdulaziz Ghuloum

2004-07-13, 4:00 pm

Terrence Brannon, Scheme Hacker wrote:
> If you read through the sample implementation of SRFI-1:
>
> http://srfi.schemers.org/srfi-1/srfi-1-reference.scm
>
> You will see the following for append-reverse()
>
>
> ;(define (append-reverse rev-head tail) (fold cons tail rev-head))
>
>
> ;;; Hand-inline the FOLD op for speed.
>
> (define (append-reverse rev-head tail)
> (let lp ((rev-head rev-head) (tail tail))
> (if (null-list? rev-head) tail
> (lp (cdr rev-head) (cons (car rev-head) tail)))))
>
>
> ======
>
> My question is: do any Scheme implementations automatically "unroll"
a call to
> fold into the optimized version of the code that Olin had to hand-code?
>
> A more general question is: do any functional languages do such
automatic unrolling?

This is not unrolling; but some implementations provide the means to
inline functions and primitives.

For example, Chez and even Petite Chez would compile the following
append-reverse definition:

(let ()
(import scheme) ; in order to use the primitive cons,null?,car,cdr
(define fold
(lambda (f accum list)
(letrec ([loop
(lambda (accum list)
(if (null? list)
accum
(loop (f (car list) accum)
(cdr list))))])
(loop accum list))))
(define append-reverse
(lambda (rev-head tail)
(fold cons tail rev-head)))
append-reverse)

into:

(letrec ([append-reverse
(lambda (rev-head tail)
(letrec ([loop
(lambda (accum list)
(if (#2%null? list)
accum
(loop (#2%cons (#2%car list) accum)
(#2%cdr list))))])
(loop tail rev-head)))])
append-reverse)

which is, I believe, what Olin's hand-coded program would expand to.

Aziz,,,

Sponsored Links