search

Demuirgos / Lambda-Calculus

A simple Programming Language Compiler to Lambda-Calculus, with a Lambda-Runtime
MIT License
13 stars 3 forks source link

Unknown Bug : Stack Overflow on correct terminating expression #25

Open Demuirgos opened 2 years ago

Demuirgos commented 2 years ago

let tail := (h::t) => t in let head := (h::t) => h in head([1, 2]) expected output : 1 i.e : λb.λc.(b c) actual output :

Stack overflow.
Repeat 11 times:
--------------------------------
   at Interpreter+occurs@46.Invoke(System.String, Expression)
--------------------------------
   at Interpreter+substitute@90.Invoke(Expression, System.String, Expression)
   at System.Runtime.CompilerServices.RuntimeHelpers.DispatchTailCalls(IntPtr, Void (IntPtr, IntPtr, System.Runtime.CompilerServices.PortableTailCallFrame*), IntPtr)
   at Microsoft.FSharp.Core.OptimizedClosures+Invoke@3297-1[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[Microsoft.FSharp.Core.FSharpResult`2[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], FSharp.Core, Version=6.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a]].Invoke(System.__Canon, System.__Canon)
   at Interpreter+result@110.Invoke(System.String)
   at Microsoft.FSharp.Core.OptionModule.Map[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[Microsoft.FSharp.Core.FSharpResult`2[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], FSharp.Core, Version=6.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,Microsoft.FSharp.Core.FSharpResult`2<System.__Canon,System.__Canon>>, Microsoft.FSharp.Core.FSharpOption`1<System.__Canon>)
   at Interpreter+substitute@90.Invoke(Expression, System.String, Expression)
   at System.Runtime.CompilerServices.RuntimeHelpers.DispatchTailCalls(IntPtr, Void (IntPtr, IntPtr, System.Runtime.CompilerServices.PortableTailCallFrame*), IntPtr)
   at Microsoft.FSharp.Core.OptimizedClosures+Invoke@3297-1[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[Microsoft.FSharp.Core.FSharpResult`2[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], FSharp.Core, Version=6.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a]].Invoke(System.__Canon, System.__Canon)
   at Interpreter+result@110.Invoke(System.String)
   at Microsoft.FSharp.Core.OptionModule.Map[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[Microsoft.FSharp.Core.FSharpResult`2[[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=6.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], FSharp.Core, Version=6.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,Microsoft.FSharp.Core.FSharpResult`2<System.__Canon,System.__Canon>>, Microsoft.FSharp.Core.FSharpOption`1<System.__Canon>)
   at Interpreter+substitute@90.Invoke(Expression, System.String, Expression)
   at System.Runtime.CompilerServices.RuntimeHelpers.DispatchTailCalls(IntPtr, Void (IntPtr, IntPtr, System.Runtime.CompilerServices.PortableTailCallFrame*), IntPtr)
   at Microsoft.FSharp.Core.OptimizedClosu...
Demuirgos commented 2 years ago

Non tail recursive substitute function causes StackOverFlow exception : explore Continuation passing, trampoline recursion or accumulators.