Recent

Author Topic: functional programming  (Read 9208 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6647
Re: functional programming
« Reply #30 on: January 19, 2020, 02:56:37 pm »
In spite of the appearance, we probably have similar ideas. Although the 'basically a dead-end approach' statement about Lisp seems too severe to me.

The way I see it, there are five fundamental notations: ALGOL, APL, Forth, Lisp and Smalltalk. Of those, only ALGOL (hence Pascal, C and the rest) "do the expected thing" when presented with the algebraic notation taught to schoolchildren for the last couple of hundred years, and I think it says a lot that when there were competing suggestions for Ada- at a time when Lisp et al. had a substantially higher profile than today- all of the proposals were ALGOL-based despite that not- as far as I'm aware- being a precondition.

I think that the most important thing to appreciate is that in the mid-to-late-50s when Lisp was concieved, few people were confident that ALGOL was viable and even fewer knew how to write an ALGOL compiler: machines of that era rarely had hardware stack support and recursion etc. tended to be messy (Grau's parser had /way/ too many data structures). Both McCarthy (Lisp) and Moore (Forth) tackled the "what's better than using assembler" problem with the fundamental assumption that a compiler would not be available for their chosen target, but these days fairly efficient compilers are available for just about anything and a significant peoportion of even embedded microcontrollers have more resources that the early mainframes and minis.

MarkMLl
« Last Edit: January 19, 2020, 04:30:38 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5444
  • Compiler Developer
Re: functional programming
« Reply #31 on: January 20, 2020, 09:21:19 am »
I think it can be done better (I mean, more functional):
Code: Pascal  [Select][+][-]
  1. FUNCTION Sum (CONST Values: ARRAY OF INTEGER): INTEGER;
  2. BEGIN
  3.   IF Length (Values) = 1 THEN
  4.     RESULT := LOW (Values)
  5.   ELSE
  6.     RESULT := Sum (Slice (Values, Length (Values) - 1) + HIGH (Values)
  7. END;
  8.  

You have two errors in there: you need to use Values[LOW(Values)] and Values[HIGH(Values)].

[side note] I think the RTL needs the SliceR function, same than Slice but using the right side.

Behold the slice operator (it's documented here at the bottom):
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 1 then
  4.     SumL := Values[Low(Values)]
  5.   else
  6.     SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  7. end;
  8.  
  9. function SumR(const Values: array of Integer): Integer;
  10. begin
  11.   if Length(Values) = 1 then
  12.     SumR := Values[Low(Values)]
  13.   else
  14.     SumR := SumR(Values[1..High(Values)]) + Values[Low(Values)];
  15. end;
  16.  
  17. begin
  18.   Writeln(SumL([1, 2, 3, 4]));
  19.   Writeln(SumR([1, 2, 3, 4]));
  20. end.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: functional programming
« Reply #32 on: January 20, 2020, 10:09:40 am »
SumL (and likewise SumR) would be safer if made as follows:

Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   case Length(Values) of
  4.     0: SumL := 0;
  5.     1: SumL := Values[Low(Values)];
  6.     else
  7.       SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  8.   end;
  9. end;

avk

  • Hero Member
  • *****
  • Posts: 752
Re: functional programming
« Reply #33 on: January 20, 2020, 11:34:23 am »
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 1 then
  4.     SumL := Values[Low(Values)]
  5.   else
  6.     SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  7. end;
  8.   ...
  9.  
And what will return SumL([])?
As for me it's better
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 0 then exit(0);
  4.   SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  5. end;  
  6.  
But all this is purely theoretical entertainment, since the FPC is not able to optimize tail recursion, right?
 

julkas

  • Guest
Re: functional programming
« Reply #34 on: January 20, 2020, 12:23:52 pm »
But all this is purely theoretical entertainment, since the FPC is not able to optimize tail recursion, right?

FPC has {$OPTIMIZATION TAILREC} - https://www.freepascal.org/docs-html/3.0.0/prog/progsu58.html#x65-640001.2.58

avk

  • Hero Member
  • *****
  • Posts: 752
Re: functional programming
« Reply #35 on: January 20, 2020, 12:52:32 pm »
Have you succeeded to make it work?

julkas

  • Guest
Re: functional programming
« Reply #36 on: January 20, 2020, 07:40:19 pm »
Have you succeeded to make it work?
If you have problem with tail recursion optimization give code example please.
BTW. I use recursion , but it's not tail :-(

PascalDragon

  • Hero Member
  • *****
  • Posts: 5444
  • Compiler Developer
Re: functional programming
« Reply #37 on: January 20, 2020, 09:09:34 pm »
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 1 then
  4.     SumL := Values[Low(Values)]
  5.   else
  6.     SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  7. end;
  8.   ...
  9.  
And what will return SumL([])?
As for me it's better
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 0 then exit(0);
  4.   SumL := SumL(Values[0..High(Values) - 1]) + Values[High(Values)];
  5. end;  
  6.  
But all this is purely theoretical entertainment, since the FPC is not able to optimize tail recursion, right?
 

1. I wanted to highlight the use of the range operator to Ñuño_Martínez.

2. Your example would not support tail recursion (and it's also not proper functional). The following would allow for tail recursion:

Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2.  
  3.   function SumInt(const Values: array of Integer; Res: Integer): Integer;
  4.   begin
  5.     if Length(Values) = 0 then
  6.       SumInt := Res
  7.     else
  8.       SumInt := SumInt(Values[0..High(Values) - 1], Res + Values[High(Values)]);
  9.   end;
  10.  
  11. begin
  12.   SumL := SumInt(Values, 0);
  13. end;  
  14.  

3. FPC does support tail recursion using -Ootailrec or {$OPTIMIZATION TAILREC} as mentioned by julkas, however due to restrictions in the compiler (constant and by-value open arrays are not supported) you need to adjust the code a bit:

Code: Pascal  [Select][+][-]
  1. function SumL(Values: array of Integer): Integer;
  2.  
  3.   function SumInt(var Values: array of Integer; Res: Integer): Integer;
  4.   begin
  5.     if Length(Values) = 0 then
  6.       SumInt := Res
  7.     else
  8.       SumInt := SumInt(Values[0..High(Values) - 1], Res + Values[High(Values)]);
  9.   end;
  10.  
  11. begin
  12.   SumL := SumInt(Values, 0);
  13. end;
  14.  

This will result in the following assembly code for SumInt:

Code: ASM  [Select][+][-]
  1. .section .text.n_p$ttailop_$$_suml$array_of_smallint$$smallint,"ax"
  2. .seh_endproc
  3. .Lc7:
  4.  
  5. .section .text.n_p$ttailop$_$suml$array_of_smallint$$smallint_$$_sumint$array_of_smallint$smallint$$smallint,"ax"
  6.         .balign 16,0x90
  7. .globl  P$TTAILOP$_$SUML$array_of_SMALLINT$$SMALLINT_$$_SUMINT$array_of_SMALLINT$SMALLINT$$SMALLINT
  8. P$TTAILOP$_$SUML$array_of_SMALLINT$$SMALLINT_$$_SUMINT$array_of_SMALLINT$SMALLINT$$SMALLINT:
  9. .Lc13:
  10. .seh_proc P$TTAILOP$_$SUML$array_of_SMALLINT$$SMALLINT_$$_SUMINT$array_of_SMALLINT$SMALLINT$$SMALLINT
  11. # [14] begin
  12.         pushq   %rbp
  13. .seh_pushreg %rbp
  14. .Lc14:
  15. .Lc15:
  16.         movq    %rsp,%rbp
  17. .Lc16:
  18.         leaq    -80(%rsp),%rsp
  19. .seh_stackalloc 80
  20. .seh_endprologue
  21. # Var Values located at rbp-8, size=OS_64
  22. # Var Res located at rbp-16, size=OS_S16
  23. # Var $highVALUES located at rbp-24, size=OS_S64
  24. # Var $parentfp located at rbp-32, size=OS_64
  25. # Var $result located at rbp-36, size=OS_S16
  26.         movq    %rcx,-32(%rbp)
  27.         movq    %rdx,-8(%rbp)
  28.         movq    %r8,-24(%rbp)
  29.         movw    %r9w,-16(%rbp)
  30. .Lj14:
  31. # [15] if Length(Values) = 0 then
  32.         movq    -24(%rbp),%rax
  33.         leaq    1(%rax),%rax
  34.         testq   %rax,%rax
  35.         je      .Lj15
  36.         jmp     .Lj16
  37. .Lj15:
  38. # [16] SumInt := Res
  39.         movw    -16(%rbp),%ax
  40.         movw    %ax,-36(%rbp)
  41.         jmp     .Lj17
  42.         .p2align 4,,10
  43.         .p2align 3
  44. .Lj16:
  45. # [18] SumInt := SumInt(Values[0..High(Values) - 1], Res + Values[High(Values)]);
  46.         movq    -8(%rbp),%rax
  47.         movq    -24(%rbp),%rdx
  48.         movswl  (%rax,%rdx,2),%eax
  49.         movswl  -16(%rbp),%edx
  50.         leal    (%eax,%edx),%eax
  51.         movq    -24(%rbp),%rdx
  52.         leaq    -1(%rdx),%rdx
  53.         movq    -8(%rbp),%rcx
  54.         movq    -32(%rbp),%r8
  55.         movw    %ax,-16(%rbp)
  56.         movq    %rdx,-24(%rbp)
  57.         movq    %rcx,-8(%rbp)
  58.         movq    %r8,-32(%rbp)
  59.         jmp     .Lj14
  60. .Lj17:
  61. # [19] end;
  62.         movswl  -36(%rbp),%eax
  63.         nop
  64.         leaq    (%rbp),%rsp
  65.         popq    %rbp
  66.         ret
  67. .seh_endproc
  68. .Lc12:
  69.  

(Edit: fixed an error in the declaration of SumL in the first example)
« Last Edit: January 20, 2020, 10:21:00 pm by PascalDragon »

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: functional programming
« Reply #38 on: January 21, 2020, 01:46:33 am »
The way I see it, there are five fundamental notations: ALGOL, APL, Forth, Lisp and Smalltalk. Of those, only ALGOL (hence Pascal, C and the rest) "do the expected thing" when presented with the algebraic notation taught to schoolchildren for the last couple of hundred years, and I think it says a lot that when there were competing suggestions for Ada- at a time when Lisp et al. had a substantially higher profile than today- all of the proposals were ALGOL-based despite that not- as far as I'm aware- being a precondition.

Where does Fortran fit into your scheme? If Turbo Pascal had not been developed, I'd likely still be using Fortran.
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

avk

  • Hero Member
  • *****
  • Posts: 752
Re: functional programming
« Reply #39 on: January 21, 2020, 07:37:57 am »
@PascalDragon, thanks a lot.
Indeed, I tested with the const parameter:
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2.   function Sum(const a: array of Integer; v0: Integer): Integer;
  3.   begin
  4.     if Length(a) = 0 then exit(v0);
  5.     Sum := Sum(a[0..High(a) - 1], v0 + a[High(a)]);
  6.   end;
  7. begin
  8.   Result := Sum(Values, 0);
  9. end;
  10.  
Now with the var parameter it works on Win64 compiler. Does this seem to be somehow documented?
However, the Win32 compiler persistently generates recursive code:
Code: ASM  [Select][+][-]
  1. P$TAIL_REC$_$SUML$array_of_LONGINT$$LONGINT_$$_SUM$array_of_LONGINT$LONGINT$$LONGINT:
  2. ; [10] begin
  3.                 push    ebp
  4.                 mov     ebp,esp
  5.                 lea     esp,dword ptr [esp-4]
  6.                 push    ebx
  7.                 push    esi
  8. ; Var $parentfp located at ebp-4, size=OS_32
  9. ; Var $result located in register ebx
  10.                 mov     dword ptr [ebp-4],eax
  11. ; Var a located in register edx
  12. ; Var $highA located in register ecx
  13.                 mov     eax,dword ptr [ebp+8]
  14. ; Var v0 located in register eax
  15. ; [11] if Length(a) = 0 then exit(v0);
  16.                 lea     ebx,dword ptr [ecx+1]
  17.                 test    ebx,ebx
  18.                 jne     @@j8
  19.                 mov     ebx,eax
  20.                 jmp     @@j5
  21. @@j8:
  22. ; Peephole Optimization: MovLea2Add done
  23. ; [12] Sum := Sum(a[0..High(a) - 1], v0 + a[High(a)]);
  24.                 add     eax,dword ptr [edx+ecx*4]
  25.                 push    eax
  26. ; Peephole Optimization: Lea2Sub done
  27.                 sub     ecx,1
  28.                 mov     eax,dword ptr [ebp-4]
  29.                 call    P$TAIL_REC$_$SUML$array_of_LONGINT$$LONGINT_$$_SUM$array_of_LONGINT$LONGINT$$LONGINT
  30.                 mov     ebx,eax
  31. @@j5:
  32. ; [13] end;
  33.                 mov     eax,ebx
  34.                 pop     esi
  35.                 pop     ebx
  36.                 mov     esp,ebp
  37.                 pop     ebp
  38.                 ret     4
  39. _CODE           ENDS
  40.  

MarkMLl

  • Hero Member
  • *****
  • Posts: 6647
Re: functional programming
« Reply #40 on: January 21, 2020, 09:16:40 am »
The way I see it, there are five fundamental notations: ALGOL, APL, Forth, Lisp and Smalltalk. Of those, only ALGOL (hence Pascal, C and the rest) "do the expected thing" when presented with the algebraic notation taught to schoolchildren for the last couple of hundred years, and I think it says a lot that when there were competing suggestions for Ada- at a time when Lisp et al. had a substantially higher profile than today- all of the proposals were ALGOL-based despite that not- as far as I'm aware- being a precondition.

Where does Fortran fit into your scheme? If Turbo Pascal had not been developed, I'd likely still be using Fortran.

Effectively a variant of ALGOL. Granted it started off with very little in the way of structure, but FORTRAN devotees make a great deal of the fact that over the years it's tried to keep up with mainstream ideas... as do the devotees of COBOL etc.

However the main point I was trying to make related to operator precedence etc., where ALGOL uses infix notation with precedence much as it's taught in school, but the rest- APL, Forth, Lisp and Smalltalk- depart from it in various ways. And purely-functional programming is similarly wierd.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5444
  • Compiler Developer
Re: functional programming
« Reply #41 on: January 21, 2020, 09:59:00 am »
@PascalDragon, thanks a lot.
Indeed, I tested with the const parameter:
Code: Pascal  [Select][+][-]
  1. function SumL(const Values: array of Integer): Integer;
  2.   function Sum(const a: array of Integer; v0: Integer): Integer;
  3.   begin
  4.     if Length(a) = 0 then exit(v0);
  5.     Sum := Sum(a[0..High(a) - 1], v0 + a[High(a)]);
  6.   end;
  7. begin
  8.   Result := Sum(Values, 0);
  9. end;
  10.  
Now with the var parameter it works on Win64 compiler. Does this seem to be somehow documented?

No, as these things change/improve with each version. E.g. yesterday Florian helped me to work out how to get constant and by-value open array parameters working as well, so that will probably soon be in trunk (and maybe 3.2) as well. ;)

However, the Win32 compiler persistently generates recursive code:
Code: ASM  [Select][+][-]
  1. P$TAIL_REC$_$SUML$array_of_LONGINT$$LONGINT_$$_SUM$array_of_LONGINT$LONGINT$$LONGINT:
  2. ; [10] begin
  3.                 push    ebp
  4.                 mov     ebp,esp
  5.                 lea     esp,dword ptr [esp-4]
  6.                 push    ebx
  7.                 push    esi
  8. ; Var $parentfp located at ebp-4, size=OS_32
  9. ; Var $result located in register ebx
  10.                 mov     dword ptr [ebp-4],eax
  11. ; Var a located in register edx
  12. ; Var $highA located in register ecx
  13.                 mov     eax,dword ptr [ebp+8]
  14. ; Var v0 located in register eax
  15. ; [11] if Length(a) = 0 then exit(v0);
  16.                 lea     ebx,dword ptr [ecx+1]
  17.                 test    ebx,ebx
  18.                 jne     @@j8
  19.                 mov     ebx,eax
  20.                 jmp     @@j5
  21. @@j8:
  22. ; Peephole Optimization: MovLea2Add done
  23. ; [12] Sum := Sum(a[0..High(a) - 1], v0 + a[High(a)]);
  24.                 add     eax,dword ptr [edx+ecx*4]
  25.                 push    eax
  26. ; Peephole Optimization: Lea2Sub done
  27.                 sub     ecx,1
  28.                 mov     eax,dword ptr [ebp-4]
  29.                 call    P$TAIL_REC$_$SUML$array_of_LONGINT$$LONGINT_$$_SUM$array_of_LONGINT$LONGINT$$LONGINT
  30.                 mov     ebx,eax
  31. @@j5:
  32. ; [13] end;
  33.                 mov     eax,ebx
  34.                 pop     esi
  35.                 pop     ebx
  36.                 mov     esp,ebp
  37.                 pop     ebp
  38.                 ret     4
  39. _CODE           ENDS
  40.  

That appears to be a bug detecting the tail call correctly. Would you please report it?

Leledumbo

  • Hero Member
  • *****
  • Posts: 8744
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: functional programming
« Reply #42 on: January 21, 2020, 10:00:09 am »
Man' I've been left quite far.
@Leledumbo
That does require quite a different mindset than I am used to. Is that more about Haskell, or functional programming in general?
Which one? Lazy evaluation is somewhat tied to functional programming, but not all functional programming languages implement it. Meanwhile, it's possible to implement it in imperative language, but will not look as natural as in functional language. e.g.: this is a function returning infinite list of fibonacci numbers:
Code: Haskell  [Select][+][-]
  1. fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
  2.  
very clear that if you implement it blindly in imperative programming, it will only result in infinite recursion, right? Due to lazy evaluation, you can indeed do the infinite recursion, or:
Code: Haskell  [Select][+][-]
  1. first10FibonacciNumbers = take 10 fibs
  2.  
and first10FibonacciNumbers will be a list of first 10 fibonacci numbers. I'll leave it up to you how in imperative language this should be done.
I just watched a short video on lambda calculus, the way they presented a function, a black box with input and output, is how I normally try to write a function.
Yes, as how it's defined in math. The blackbox, however, is not a series of command or steps to produce output based on input, but an expression, just like in math. And expression is the core of functional programming. As I've shown previously, not all functions will be compiled into functions in assembly. They can be eliminated completely or simplified as far as possible even into a simple value assignment only (if the function call can be executed at compile time).
I guess anonymous functions are another significant piece of it though. Apparently in Delphi, but not in Free Pascal yet?
WIP and partially working in trunk, AFAIK. Or is it still in separate branch?

PascalDragon

  • Hero Member
  • *****
  • Posts: 5444
  • Compiler Developer
Re: functional programming
« Reply #43 on: January 21, 2020, 10:02:17 am »
I guess anonymous functions are another significant piece of it though. Apparently in Delphi, but not in Free Pascal yet?
WIP and partially working in trunk, AFAIK. Or is it still in separate branch?
The later.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: functional programming
« Reply #44 on: January 21, 2020, 11:32:09 am »
No, as these things change/improve with each version. E.g. yesterday Florian helped me to work out how to get constant and by-value open array parameters working as well, so that will probably soon be in trunk (and maybe 3.2) as well. ;)
Good news.

That appears to be a bug detecting the tail call correctly. Would you please report it?
Just tested SumL against i386-win32 rev.44002 - works as expected. :D

 

TinyPortal © 2005-2018