Lambda lift breaks recursive let definitions

[gschare]

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.

[sedwards-lab]

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]

I'll look into it

[j-hui]

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]

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]

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

[j-hui]

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]

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]

@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]

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]

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 https://github.com/ssm-lang/sslang/issues/111#issuecomment-1255404647, or unsubscribe https://github.com/notifications/unsubscribe-auth/AC2A5DHLMHPVMNHCAXIEKC3V7SRGXANCNFSM6AAAAAAQTJAWT4 . You are receiving this because you were assigned.Message ID: @.***>

[j-hui]

Closed by #152