Lambda lift breaks recursive let definitions #111

gschare · 2022-09-22T17:46:17Z

In regression-tests/tests/hello13.ssl, the following function for printing a list of characters fails to compile. It complains that the puts__ variable is unbound, the error presumably originating when it is recursively called.

puts_ putc s =
  let puts__ ss =
        match ss
          Cons c s = putc c
                     puts__ s
          Nil = ()
  puts__ s

// TypeError (ErrorMsg "Unbound variable: Var (VarId puts__) (Type [])")

We should allow recursive nested functions a la Haskell. This could be achieved by adding the name to the environment at the moment it is declared, like letrec bindings in Racket or OCaml, but I'm not sure if would be negative consequences to that. We could also add an explicit rec keyword like those languages do, but the result might be aesthetically subpar.

See also #30 -- seems related.

The text was updated successfully, but these errors were encountered:

sedwards-lab · 2022-09-22T18:03:52Z

This is definitely a bug since top-level definitions can handle recursion and the local ones should, too. This may be a bug in the type checker. The question is why it's not working for local definitions yet working for top-level definitions. Is the type error being generated before or after lambda-lifting?

j-hui · 2022-09-22T18:10:58Z

I'll look into it

j-hui · 2022-09-22T18:22:10Z

I can't reproduce the TypeError shown. In fact, the code snippet shown was originally commented out; if I use that definition it, passes the typecheck, and only fails later on at the Codgen stage:

$ cat regression-tests/tests/hello13.ssl
putc_ (cout : &Int) c =
  after 1, cout <- c
  wait cout

eof_ (cout : &Int) _ =
  after 1, cout <- 0
  wait cout

type String
  Cons Int String
  Nil

/*
// old workaround definition
puts_ putc s =
  match s
    Cons c ss = putc c
                puts_ putc ss
    Nil = ()
*/

puts_ putc s =
  let puts__ ss =
        match ss
          Cons c s = putc c
                     puts__ s
          Nil = ()
  puts__ s

// Previously commented out, used to throw this error:
// TypeError (ErrorMsg "Unbound variable: Var (VarId puts__) (Type [])")

main cin cout =
  let putc = putc_ cout
  let puts = puts_ putc
  let eof = eof_ cout
  let hello = Cons 72 (Cons 101 (Cons 108 (Cons 108
                (Cons 111 (Cons 49 (Cons 51 (Cons 10 Nil)))))))
  puts hello
  eof ()

$ sslc regression-tests/tests/hello13.ssl
UnexpectedError (ErrorMsg "Pattern match failure in do expression at src/Codegen/Codegen.hs:529:3-8")

gschare · 2022-09-22T18:30:13Z

I tested using the regression-tests/runtests.sh script:

$ ./runtests.sh -k tests/hello13.ssl
hello13...FAILED
  failed: stack exec sslc -- tests/hello13.ssl > out/hello13.c
make -C ../lib/ssm build/libssm.a 1>&2
PLATFORM is simulation
# Valgrind is not available; compiling without it.
make: `build/libssm.a' is up to date.

###### Testing hello13
stack exec sslc -- tests/hello13.ssl > out/hello13.c
TypeError (ErrorMsg "Unbound variable: Var (VarId puts__) (Type [])")
###### FAILED

j-hui · 2022-09-22T18:31:27Z

@gschare did you modify hello13.ssl in any way? Also, can you confirm that you have the latest build of sslc?

j-hui · 2022-09-22T18:32:03Z

For what it's worth, I'm able to get the following output, right before Codegen:

puts__puts___anon0 (putc : (Int32 -> a1)) (puts__ : (String -> ())) (ss : String) -> () =
  __drop (
    __drop (
      __drop (
        match ss
          Cons __pat_anon0 __pat_anon1 = __drop (
                                           __dup (__pat_anon0)
                                           __drop (
                                             __dup (__pat_anon1)
                                             let s = __dup (__pat_anon1)
                                             __drop (
                                               let c = __dup (__pat_anon0)
                                               __drop (
                                                 let anon0_underscore = __dup (putc) (__dup (c))
                                                 __drop (
                                                   __dup (puts__) (__dup (s))
                                                 ) anon0_underscore
                                               ) c
                                             ) s
                                           ) __pat_anon1
                                         ) __pat_anon0
          Nil  = ()
      ) ss
    ) puts__
  ) putc

puts_ (putc : (Int32 -> a1)) (s : String) -> () =
  __drop (
    __drop (
      let puts__ = __dup (puts__puts___anon0) (__dup (putc)) (__dup (puts__))
      __drop (
        __dup (puts__) (__dup (s))
      ) puts__
    ) s
  ) putc

I suspect this line is what's causing the issue:

      let puts__ = __dup (puts__puts___anon0) (__dup (putc)) (__dup (puts__))

I'm not totally sure how that's being generated

sedwards-lab · 2022-09-22T18:32:23Z

Yes. Please make sure you're on the main branch, at the head (git pull) and have run stack build (runtests.sh doesn't automatically build the compiler)

gschare · 2022-09-22T18:35:13Z

@gschare did you modify hello13.ssl in any way? Also, can you confirm that you have the latest build of sslc?

My bad, I hadn't pulled the latest commits. Now I get the same error as you. I did the same modification you did to hello13.ssl, uncommenting the second definition of puts_ and commenting out the old one.

$ ./runtests.sh -k tests/hello13.ssl
hello13...FAILED
  failed: stack exec sslc -- tests/hello13.ssl > out/hello13.c
make -C ../lib/ssm clean 1>&2
PLATFORM is simulation
# Valgrind is not available; compiling without it.
rm -rf build
make -C ../lib/ssm EXTRA_CFLAGS="-DCONFIG_MEM_STATS" build/libssm.a 1>&2
PLATFORM is simulation
# Valgrind is not available; compiling without it.
mkdir -p build
cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-closure.o src/ssm-closure.c
cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-mem.o src/ssm-mem.c
cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-scheduler.o src/ssm-scheduler.c
cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-top-act.o src/ssm-top-act.c
rm -f build/libssm.a
ar -cr build/libssm.a build/ssm-closure.o build/ssm-mem.o build/ssm-scheduler.o build/ssm-top-act.o

###### Testing hello13
stack exec sslc -- tests/hello13.ssl > out/hello13.c
UnexpectedError (ErrorMsg "Pattern match failure in do expression at src/Codegen/Codegen.hs:529:3-8")
###### FAILED

j-hui · 2022-09-22T18:35:32Z

Scratch that, I think the problem comes from lambda lifting. From --dump-ir-typed (before lambda-lifting):

puts_ (putc : (Int32 -> a1)) (s : String) -> () =
  let puts__ = puts__puts___anon0 putc puts__
  puts__ s

It's not correctly handling the identifiers of recursive functions, which it believs is captured by closure.

j-hui · 2022-09-22T19:07:32Z

No problem, I figured (:. Pull again, I pushed another commit that should give you a slightly more informative error message there. I know what the bug is, will try to fix it this weekend

…

On Thu, Sep 22, 2022, 2:35 PM Gregory Schare ***@***.***> wrote: @gschare <https://github.com/gschare> did you modify hello13.ssl in any way? Also, can you confirm that you have the latest build of sslc? My bad, I hadn't pulled the latest commits. Now I get the same error as you. $ ./runtests.sh -k tests/hello13.ssl hello13...FAILED failed: stack exec sslc -- tests/hello13.ssl > out/hello13.c make -C ../lib/ssm clean 1>&2 PLATFORM is simulation # Valgrind is not available; compiling without it. rm -rf build make -C ../lib/ssm EXTRA_CFLAGS="-DCONFIG_MEM_STATS" build/libssm.a 1>&2 PLATFORM is simulation # Valgrind is not available; compiling without it. mkdir -p build cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-closure.o src/ssm-closure.c cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-mem.o src/ssm-mem.c cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-scheduler.o src/ssm-scheduler.c cc -g -Iinclude -O -Wall -pedantic -DCONFIG_MEM_STATS -std=c99 -c -o build/ssm-top-act.o src/ssm-top-act.c rm -f build/libssm.a ar -cr build/libssm.a build/ssm-closure.o build/ssm-mem.o build/ssm-scheduler.o build/ssm-top-act.o ###### Testing hello13 stack exec sslc -- tests/hello13.ssl > out/hello13.c UnexpectedError (ErrorMsg "Pattern match failure in do expression at src/Codegen/Codegen.hs:529:3-8") ###### FAILED — Reply to this email directly, view it on GitHub <#111 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC2A5DHLMHPVMNHCAXIEKC3V7SRGXANCNFSM6AAAAAAQTJAWT4> . You are receiving this because you were assigned.Message ID: ***@***.***>

j-hui · 2023-04-29T23:21:29Z

Closed by #152

j-hui self-assigned this Sep 22, 2022

j-hui changed the title ~~Allow recursive let functions~~ Lambda lift breaks recursive let definitions Oct 17, 2022

j-hui mentioned this issue Oct 17, 2022

Add name mangling pass to make VarIds globally unique #120

Merged

2 tasks

j-hui mentioned this issue Apr 18, 2023

Type annotated binders #150

Merged

j-hui added the bug Something isn't working label Apr 18, 2023

j-hui mentioned this issue Apr 28, 2023

Support recursion in lambda lifting pass #152

Merged

j-hui closed this as completed Apr 29, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Lambda lift breaks recursive let definitions #111

Lambda lift breaks recursive let definitions #111

gschare commented Sep 22, 2022 •

edited

Loading

sedwards-lab commented Sep 22, 2022

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022

gschare commented Sep 22, 2022

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022 •

edited

Loading

sedwards-lab commented Sep 22, 2022

gschare commented Sep 22, 2022 •

edited

Loading

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022 via email

j-hui commented Apr 29, 2023

Lambda lift breaks recursive let definitions #111

Lambda lift breaks recursive let definitions #111

Comments

gschare commented Sep 22, 2022 • edited Loading

sedwards-lab commented Sep 22, 2022

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022

gschare commented Sep 22, 2022

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022 • edited Loading

sedwards-lab commented Sep 22, 2022

gschare commented Sep 22, 2022 • edited Loading

j-hui commented Sep 22, 2022

j-hui commented Sep 22, 2022 via email

j-hui commented Apr 29, 2023

gschare commented Sep 22, 2022 •

edited

Loading

j-hui commented Sep 22, 2022 •

edited

Loading

gschare commented Sep 22, 2022 •

edited

Loading