flat assembler
Message board for the users of flat assembler.

flat assembler > Main > Lazy evaluation concept

Author
Thread Post new topic Reply to topic
Mino



Joined: 14 Jan 2018
Posts: 160
Hello Smile

I was very interested in functional programming in its last days, and one of the principles seemed confusing to me: lazy evaluation.
Basically, it is the fact that an expression is only limited in its evaluation by the data that is subsequently sent to it.
In theory, this is relatively easy to understand. However, the generated assembler codes seem to me to be much more complicated, in the sense that I don't find them very logical.

Here is an example in Haskell:

Code:
module Example where
add a b = a + b
foo = add 8 2
    


For those who would not understand, we just define an "add" function that takes two arguments, and returns the result of their sum. The last instruction therefore uses this function (add arg1 arg2).

A corresponding code in C-like would probably generate this in assembler:

Code:
add:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        mov     edx, DWORD PTR [rbp-4]
        mov     eax, DWORD PTR [rbp-8]
        add     eax, edx
        pop     rbp
        ret
; main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     esi, 2
        mov     edi, 8
        call    add
        mov     DWORD PTR [rbp-4], eax
        mov     eax, 0
        leave
        ret
    


However, this was not my surprise when I compiled this Haskell code, and got this assembler code:

Code:
Example_add_closure:
        .quad   Example_add_info
Example_add_info:
        leaq -24(%rbp),%rax
        cmpq %r15,%rax
        jb .Lc19M
        movq $stg_ap_pp_info,-24(%rbp)
        movq %rsi,-16(%rbp)
        movq %rdi,-8(%rbp)
        addq $-24,%rbp
        jmp base_GHCziNum_zp_info
.Lc19M:
        movl $Example_add_closure,%ebx
        jmp *-8(%r13)
s19G_closure:
        .quad   integerzmgmp_GHCziIntegerziType_Szh_con_info
        .quad   2
s19F_closure:
        .quad   integerzmgmp_GHCziIntegerziType_Szh_con_info
        .quad   8
Example_foo_closure:
        .quad   Example_foo_info
        .quad   0
        .quad   0
        .quad   0
Example_foo_info:
        leaq -40(%rbp),%rax
        cmpq %r15,%rax
        jb .Lc1a5
        subq $8,%rsp
        movq %r13,%rax
        movq %rbx,%rsi
        movq %rax,%rdi
        xorl %eax,%eax
        call newCAF
        addq $8,%rsp
        testq %rax,%rax
        je .Lc1a3
        movq $stg_bh_upd_frame_info,-16(%rbp)
        movq %rax,-8(%rbp)
        movl $base_GHCziNum_zdfNumInteger_closure,%r14d
        movq $stg_ap_pp_info,-40(%rbp)
        movq $s19F_closure+1,-32(%rbp)
        movq $s19G_closure+1,-24(%rbp)
        addq $-40,%rbp
        jmp base_GHCziNum_zp_info
.Lc1a3:
        jmp *(%rbx)
.Lc1a5:
        jmp *-16(%r13)
r19b_bytes:
        .asciz "main"
r19n_closure:
        .quad   ghczmprim_GHCziTypes_TrNameS_con_info
        .quad   r19b_bytes
r19o_bytes:
        .asciz "Example"
r19p_closure:
        .quad   ghczmprim_GHCziTypes_TrNameS_con_info
        .quad   r19o_bytes
Example_zdtrModule_closure:
        .quad   ghczmprim_GHCziTypes_Module_con_info
        .quad   r19n_closure+1
        .quad   r19p_closure+1
        .quad   3
S1a7_srt:
        .quad   base_GHCziNum_zdfNumInteger_closure
        .quad   s19F_closure
        .quad   s19G_closure
1:
2:
    


"foo" doesn't even use the function defined above....

I'm sorry, it's not really a fasm-related question, but if you could tell me a little more about how this code works, I would be delighted Smile

Thank you very much.

_________________
The best way to predict the future is to invent it.
Post 24 Oct 2018, 14:10
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 125
Is the assembly complete? What happens at


Code:
base_GHCziNum_zp_info    


I just got ghc installed on this computer and haven't yet built a working example. It looks like the params are the second member into
Code:
s19G_closure:    

and
Code:
s19F_closure:    


It may be a bit easier reading in Intel syntax: https://stackoverflow.com/questions/15529785/how-to-generate-intel-assembler-syntax-from-ghc-of-haskell

Was just curious about this topic, but will take a deeper look tomorrow if there's time. Good luck
Post 25 Oct 2018, 00:50
View user's profile Send private message Reply with quote
Mino



Joined: 14 Jan 2018
Posts: 160
I must admit that I don't really understand this code.
Here is a link from which you can test: https://godbolt.org/z/dXi__D

Thank you for link Wink

_________________
The best way to predict the future is to invent it.
Post 25 Oct 2018, 19:49
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 125
Apparently, you're not alone:

https://news.ycombinator.com/item?id=13182726

Quote:

MichaelBurge on Dec 15, 2016 [-]

If you've never done it before, try stepping through a Haskell program compiled with a recent GHC. The control flow is pretty weird.



astrange on Dec 15, 2016 [-]

You can follow ghc's compilation with '-v5'. Alas, I've never liked the way it compiles - full of unpredictable jumps, makes no sense at asm level, and just doesn't look a good modern CPU citizen.
Of course I am only a minor Haskell learner but jhc could do whole-program compilation with readable assembly.


My computer has some disk problems and won't start this week. My tablet doesn't yet have Linux either. But once it works again, I might try jhc. Last time I tried running that Haskell through ghc it wouldn't compile, so I'll have to find a working example. It was getting hung up on something trivial if I remember correctly, so may have just been a typo on my part.
Post 04 Nov 2018, 14:31
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2659
Location: dank orb
I imagine the actual addition is done by "base_GHCziNum_zp_info" or rather after it. It's a data driven approach with multiple stacks. The compiler probably splits data and execution streams to provide better error reporting and recovery, as well as automatic garbage collection. Possibly multiple data streams.
Post 04 Nov 2018, 16:13
View user's profile Send private message Visit poster's website Reply with quote
Mino



Joined: 14 Jan 2018
Posts: 160
@bitRAKE: It's possible, yes. But I don't know any more than you do ^^

@donn: I fully agree with these quotes. The code generated by GHC (I have never tried JHC) is really unreadable. It's a spaghetti code. If this is for a simple addition, imagine the code generated for a program that is a little more complex...

In my opinion, it's due to the lazy evaluation, but personally I think it's Haskell's devs who are lazy at the idea of generating a readable code Very Happy

_________________
The best way to predict the future is to invent it.
Post 04 Nov 2018, 17:20
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16097
Location: Transylbonia
The AT&T syntax isn't helping either. But I don't see any lazy evaluation here. Just normal code to check the stack, retrieve the values and then ... jmp somewhere to do the addition. Since the addition code isn't shown then we don't really know what it is doing.
Post 04 Nov 2018, 18:24
View user's profile Send private message Visit poster's website Reply with quote
Mino



Joined: 14 Jan 2018
Posts: 160
Haskell is defined as performing lazily, however. I think, it just has to be an abstraction for this case....
Post 04 Nov 2018, 21:06
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16097
Location: Transylbonia
My understanding of lazy evaluation is that if an earlier test condition is false then the remainder of the tests can be skipped. But the code there doesn't have any tests, the addition is always needed to be done when the function is executed.

I agree that the generated code is ugly, but I think that is a different matter not related to any evaluation methodology.
Post 04 Nov 2018, 21:19
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2018, Tomasz Grysztar.

Powered by rwasa.