(Looking At) Functional Programming in Haskell

Janis König

ljrk@ljrk.org

September 28, 2023

about://me

ElleJay

Names: \(\{\text{ElleJay/lj}, \text{Leo}, \text{Janis}\}\)
Pronouns: \(\{\text{she/her}, \text{he/him}, \text{they/them}\}\)
Pls don’t use Leo with she/her or Janis with he/him though :-)

Fedi:
@ljrk@todon.eu

Mail:
ljrk@ljrk.org

Blog:
blog.ljrk.org

Recursion & Loops

function sum(N: number): number {
    let result: number = 0
    for (; N > 0; N--) {
        result += N
    }
    return (result)
}

function sum(N: number): number {
    if (N <= 1) { return (N) }
  
    let result = N + sum(N-1)
  
    return (result)
}

note: this is not tail recursive

Recursion & Loops

function sum(N: number): number {
    let result: number = 0
lp: if (N <= 0) { return (result) }
    result += N
    N--
    goto (lp)
}

function sum(N: number): number {
    if (N <= 1) { return (N) }
  
    let result = N + sum(N-1)
  
    return (result)
}

note: this is not tail recursive

Assembly: Loop

EXTERN printf
EXTERN atoi

SECTION .data
prn:    DB `suml: %ld\n\0`

SECTION .text

; param rdi:   64 bit integer
; returns rax: 64 bit integer
suml:   MOV rax, rdi
.loop:  CMP rdi, 0
        JLE .end

        SUB rdi, 1
        ADD rax, rdi
        JMP .loop
.end:   RET

GLOBAL  main
main:   CMP rdi, 2
        MOV rax, 1
        JNE .end

        MOV rdi, [rsi+8]
        CALL atoi

        MOV rdi, rax
        CALL suml

        MOV rdi, prn
        MOV rsi, rax
        MOV rax, 0
        CALL printf

        MOV rax, 0
.end:   RET

SECTION .note.GNU-stack noalloc noexec nowrite progbits

$ ./suml 1
suml: 1
$ ./suml 2
suml: 3
$ ./suml 3
suml: 6

Assembly: Recursion

EXTERN printf
EXTERN atoi

SECTION .data
prn:    DB `sumr: %ld\n\0`

SECTION .text

sumr:   CMP rdi, 0
        CMOVLE rax, rdi
        JLE .end

        MOV rax, rdi
        SUB rdi, 1
        PUSH rax
        CALL sumr
        POP rdi
        ADD rax, rdi
.end:   RET

GLOBAL  main
main:   CMP rdi, 2
        MOV rax, 1
        JNE .end

        MOV rdi, [rsi+8]
        CALL atoi

        MOV rdi, rax
        CALL sumr

        MOV rdi, prn
        MOV rsi, rax
        MOV rax, 0
        CALL printf

        MOV rax, 0
.end:   RET

SECTION .note.GNU-stack noalloc noexec nowrite progbits

$ ./sumr 1
sumr: 1
$ ./sumr 2
sumr: 3
$ ./sumr 3
sumr: 6

Assembly: Tail Recursion

EXTERN printf
EXTERN atoi

SECTION .data
prn:    DB `sumtr: %ld\n\0`

SECTION .text

sumtr:  MOV rax, rdi
.rec:   CMP rdi, 0
        JLE .end

        SUB rdi, 1
        ADD rax, rdi
        PUSH rdi
        CALL .rec
   ;JMP .rec
        POP rdi
.end:   RET

GLOBAL  main
main:   CMP rdi, 2
        MOV rax, 1
        JNE .end

        MOV rdi, [rsi+8]
        CALL atoi

        MOV rdi, rax
        CALL sumtr

        MOV rdi, prn
        MOV rsi, rax
        MOV rax, 0
        CALL printf

        MOV rax, 0
.end:   RET

SECTION .note.GNU-stack noalloc noexec nowrite progbits

$ ./sumtr 1
sumtr: 1
$ ./sumtr 2
sumtr: 3
$ ./sumtr 3
sumtr: 6

Performance Comparison

Recursion

sumr: 125000250000

real    0m0.007s
user    0m0.003s
sys 0m0.004s

Tail-Call Recursion

sumtr: 125000250000

real    0m0.007s
user    0m0.004s
sys 0m0.003s

Without PUSH/POP:

sumtr: 125000250000

real    0m0.005s
user    0m0.004s
sys 0m0.001s

Tail Call Eliminated:

sumtr: 125000250000

real    0m0.001s
user    0m0.001s
sys 0m0.000s

Loop

suml: 125000250000

real    0m0.001s
user    0m0.001s
sys 0m0.000s

Fold Left and Fold Right

FoldL

   [1,2,3,4].foldl(|a, b| -> a+b, 0)
 = (((0+1)+2)+3)+4

adds front to back
can start adding right away
pushes intermediate results

   [1,2,3,4].foldl(|a, b| -> a+b, 0)
 = [2,3,4].foldl(|a, b| -> a+b, 0+1)
 = [3,4].foldl(|a, b| -> a+b, (0+1)+2)
 = [4].foldl(|a, b| -> a+b, ((0+1)+2)+3)
 = [].foldl(|a, b| -> a+b, (((0+1)+2)+3)+4)
 = (((0+1)+2)+3)+4

FoldR

   [1,2,3,4].foldr(|a, b| -> a+b, 0)
 = 1+(2+(3+(4+0)))

starts adding from end
builds expression first
pushes arguments to stack

   [1,2,3,4].foldr(|a, b| -> a+b, 0)
 = 1+[2,3,4].foldr(|a, b| -> a+b, 0)
 = 1+(2+[3,4].foldr(|a, b| -> a+b, 0))
 = 1+(2+(3+[4].foldr(|a, b| -> a+b, 0)))
 = 1+(2+(3+(4+[].foldr(|a, b| -> a+b, 0))))
 = 1+(2+(3+(4+0))))

Assembly: FoldR

foldr:  CMP rdx, 0
        CMOVLE rax, rsi
        JBE .end

        MOV rax, [rcx]
        SUB rdx, 1
        ADD rcx, 8

; rax: list[0]
; rdi: fn
; rsi: init
; rdx: n-1
; rcx: list[1:]
        PUSH rdi
        PUSH rax
        CALL foldr
        MOV rsi, rax
        POP rdi
        POP rax

; rdi: list[0]
; rsi: foldr fn init list[1:]
; rax: fn
        CALL rax
.end:   RET

Assembly: FoldL

foldl:  CMP rdx, 0
        CMOVLE rax, rsi
; rax: result
        JBE .end

 ;
        PUSH rdi
        MOV rax, rdi
        MOV rdi, rsi
        MOV rsi, [rcx]

; rdi: init
; rsi: list[0]
; rax: fn
; rdx: n
; rcx: list
        PUSH rdx
        PUSH rcx
        CALL rax
        MOV rsi, rax
        POP rcx
        POP rdx
        POP rdi
 ;

        SUB rdx, 1
        ADD rcx, 8
; rdi: fn
; rsi: fn init list[0]
; rdx: n-1
; rcx: list[1:]
        CALL foldl
; rax: result
.end:   RET

Assembly: FoldL Tail Call

foldl:  CMP rdx, 0
        CMOVLE rax, rsi
; rax: result
        JBE .end

 ;
        PUSH rdi
        MOV rax, rdi
        MOV rdi, rsi
        MOV rsi, [rcx]

; rdi: init
; rsi: list[0]
; rax: fn
; rdx: n
; rcx: list
        PUSH rdx
        PUSH rcx
        CALL rax
        MOV rsi, rax
        POP rcx
        POP rdx
        POP rdi
 ;

        SUB rdx, 1
        ADD rcx, 8
; rdi: fn
; rsi: fn init list[0]
; rdx: n-1
; rcx: list[1:]
        CALL foldl
; rax: result
.end:   RET

Assembly: FoldL Tail Call Elimination

foldl:  CMP rdx, 0
        CMOVLE rax, rsi
; rax: result
        JBE .end

  ;
        PUSH rdi
        MOV rax, rdi
        MOV rdi, rsi
        MOV rsi, [rcx]

; rdi: init
; rsi: list[0]
; rax: fn
; rdx: n
; rcx: list
        PUSH rdx
        PUSH rcx
        CALL rax
        MOV rsi, rax
        POP rcx
        POP rdx
        POP rdi
  ;

        SUB rdx, 1
        ADD rcx, 8
; rdi: fn
; rsi: fn init list[0]
; rdx: n-1
; rcx: list[1:]
        CALL foldl
; rax: result
.end:   RET

foldll: CMP rdx, 0
        CMOVLE rax, rsi
; rax: result
        JBE .end

        MOV r8, rdi
        ;PUSH rdi
        MOV rax, rdi
        MOV rdi, rsi
        MOV rsi, [rcx]

; rdi: init
; rsi: list[0]
; rax: fn
; rdx: n
; rcx: list
        ;PUSH rdx
        ;PUSH rcx
        CALL rax
        MOV rsi, rax
        ;POP rcx
        ;POP rdx
        ;POP rdi
        MOV rdi, r8

        SUB rdx, 1
        ADD rcx, 8
; rdi: fn
; rsi: fn init list[0]
; rdx: n-1
; rcx: list[1:]
        JMP foldll
; rax: result
.end:   RET

Performance?

foldr: 500000

real    0m0.000s
user    0m0.000s
sys 0m0.000s

foldl: 500000

real    0m0.000s
user    0m0.000s
sys 0m0.000s

foldll: 500000

real    0m0.000s
user    0m0.000s
sys 0m0.000s

Performance!

Record perf(1) events:

perf record -o meow.syscap ./meow $(seq 1 120000) && \
perf report -s sym,srcline --stdio -i meow.syscap

Radically reduced number of events:

Version	# Event
Fold Right (Recursive)	11689523
Fold Left (Tail Recursive)	10050866
Fold Left (Tail Call Eliminated)	6905606

Performance!

Overhead	Symbol	Source:Line
12.62%	`foldr`	foldr.asm:46
11.57%	`__GI_strtoll`
11.42%	`foldr`	foldr.asm:45
6.91%	`__GI_____strtoll_l_internal`
6.90%	`foldr`	foldr.asm:43
6.61%	`0xffffffff9b001917`
6.61%	`add`	foldr.asm:23
6.25%	`main.fill`	foldr.asm:100
5.95%	`__GI_____strtoll_l_internal`
…	…

Performance!

Overhead	Symbol	Source:Line
28.79%	`foldl.end`	foldl.asm:62
10.11%	`__GI_strtoll`
9.92%	`__GI_____strtoll_l_internal`
9.85%	`__GI_____strtoll_l_internal`
9.68%	`atoi@plt`
9.57%	`atoi`
9.44%	`__GI_____strtoll_l_internal`
9.44%	`__GI_____strtoll_l_internal`
3.05%	`__GI___tunables_init`
…	…

Performance!

Overhead	Symbol	Source:Line
17.24%	`__GI_strtoll`
16.52%	`__GI_____strtoll_l_internal`
15.62%	`atoi@plt`
15.25%	`__GI_____strtoll_l_internal`
15.15%	`__GI_____strtoll_l_internal`
15.04%	`__GI_____strtoll_l_internal`
4.97%	`__GI___tunables_init`
0.21%	`_start`
0.01%	`0xffffffff9b001917`

Addendum: Lazy Evaluation

What happens to foldl when it evaluates lazily?