Lazarus

Programming => General => Topic started by: VTwin on January 18, 2020, 03:28:18 am

Title: functional programming
Post by: VTwin on January 18, 2020, 03:28:18 am
I am trying to understand the buzz about "functional programming". It sounds like using functions without modifying parameters, and no global side effects. This sounds old school to me. Anyone care to elucidate?
Title: Re: functional programming
Post by: jamie on January 18, 2020, 03:31:21 am
Its just noise, don't worry about it!  :D


And if you didn't read about it, you never would of been concerned about it!

So slack off on the reading of these new twisted buzz words describing the past one's
Title: Re: functional programming
Post by: Martin_fr on January 18, 2020, 04:19:11 am
Well, there is always some buzz.
If you want some good background on the paradigm, then maybe this will help: https://www.youtube.com/watch?v=sqV3pL5x8PI


@jamie: nice pun.
Title: Re: functional programming
Post by: VTwin on January 18, 2020, 06:19:00 am
Thanks. I looked at  that that and other referees including:

https://youtu.be/0if71HOyVjY

which, to me, explained nothing useful. It sounds more like programming style, constant input with no side effects.

I imagine there is more to it, but I do not see any reason to spend more time on it.

Cheers

Title: Re: functional programming
Post by: ur_naz on January 18, 2020, 07:24:25 am
With FP you can always code in functional style or semi-functional style or near-functional style or none-functional style as well.
Title: Re: functional programming
Post by: julkas on January 18, 2020, 10:27:28 am
With FP you can always code in functional style ...
Style - yes. But it would be just mimic or bad parody.
Title: Re: functional programming
Post by: simone on January 18, 2020, 10:32:06 am
I am trying to understand the buzz about "functional programming". It sounds like using functions without modifying parameters, and no global side effects. This sounds old school to me. Anyone care to elucidate?

You are right. Indeed Lisp was born in 1958!
Title: Re: functional programming
Post by: PascalDragon on January 18, 2020, 11:12:34 am
I think an important part of functional programming is also function pointers to be first level citizens allowing them to be passed around easily (together with state), something that FPC will only gain once anonymous functions are implemented.
Title: Re: functional programming
Post by: MarkMLl on January 18, 2020, 11:13:54 am
I am trying to understand the buzz about "functional programming". It sounds like using functions without modifying parameters, and no global side effects. This sounds old school to me. Anyone care to elucidate?

You are right. Indeed Lisp was born in 1958!

As I understand it, there's also various things like generating functions on-the-fly.  LISP was invented by people who were peripherally involved with designing and standardising ALGOL but apparently didn't quite "get it", FORTH tackled the same problems some 20 years later. By now "The LISP Way" is so far from mainstream applications and system programming that I really don't see its relevance.

The first three chapters of http://web.engr.oregonstate.edu/~budd/Books/leda/ are freely available and offer a good comparison of several different programming styles. The examples might be heavy going but (writing as an engineer with limited tolerance of "fancy CS stuff") are worth reading through carefully.

MarkMLl
Title: Re: functional programming
Post by: jamie on January 18, 2020, 03:53:24 pm
Code: Pascal  [Select][+][-]
  1. Function Sum(inputs:array of integer):Integer;
  2. Var
  3.   V:Integer;
  4. Begin
  5.   Result:=0;
  6.   For V in inputs do Result+=V;
  7. End;
  8.  
  9. procedure TForm1.Button1Click(Sender: TObject);
  10. begin
  11.  Caption := Sum([1,2,3,4,5]).ToString;
  12. end;                        
  13.  
  14.  

Nothing new here ;)
Title: Re: functional programming
Post by: lucamar on January 18, 2020, 05:05:32 pm
Nothing new here ;)

I'm also a little bit lost with functional programming but I don't think your code quite qualifies as that ;)

Of course, my (small) understanding comes basically from the Wikipedia article (https://en.wikipedia.org/wiki/Functional_programming), nothing more fancy. :D
Title: Re: functional programming
Post by: Leledumbo on January 18, 2020, 06:22:46 pm
I am trying to understand the buzz about "functional programming". It sounds like using functions without modifying parameters, and no global side effects. This sounds old school to me. Anyone care to elucidate?
Partially it can be viewed that way, but functional programming can be viewed in a wider way. The go to language for functional programming, Haskell, is one of very few that implements functional programming as pure as possible.

First, order of evaluation is undefined, the compiler should be able to generate code that evaluate either way it considers the most efficient. e.g. if you do:
Code: Haskell  [Select][+][-]
  1. y = f x a b
  2.  
there's no guarantee whether x, a or b will be evaluated first. In fact, it's possible that none might be evaluated due to the next feature.

Second, it enforces lazy evaluation, i.e. an expression will never be evaluated until the time its value is required. e.g.:
Code: Haskell  [Select][+][-]
  1. y = f (x + 1) (z * 5)
  2.  
if either `x + 1` or `z + 5` isn't immediately needed, they will be passed around as is, as an expression. Even better:
Code: Haskell  [Select][+][-]
  1. y = f (x + 1) (z * 5)
  2. f a b = g (a - 1) (b / 5)
  3.  
will also evaluate neither `a - 1` nor `b / 5`. But once you add:
Code: Haskell  [Select][+][-]
  1. y = f (x + 1) (z * 5)
  2. f a b = g (a - 1) (b / 5)
  3. g a b = a + b
  4.  
all of those expressions will be calculated in one go, possibly at compile time depending on the values or at least curried to be the simplest expression ever. So instead of 1 assignment over 2 functions the compiler will only generate a single expression:
Code: Haskell  [Select][+][-]
  1. y = x + z
  2.  

Last but not least, (almost) full type inference (since sometimes you still have to specify one as the generic candidates might be too generic). This is not really possible in imperative languages due to the types are implemented (Haskell's type system could be a language in its own).

Some bits of functional programming can indeed be stolen and have been stolen by many imperative languages, such as: list comprehension, first class functions, etc.
Title: Re: functional programming
Post by: Otto on January 18, 2020, 06:48:41 pm
Among the few programming languages that I usually use, C# is one that shows a constant tendency to introduce novelties. It introduced the possibility of using functional programming and then, to simplify its syntax, introduced the Lambda expression (In my opinion, they are useful from an expressive point of view, but they are not indispensable).
Searching the internet, with reliable search engines (duckduckgo.com) you can find useful examples.

Functional-programming-in-Csharp https://www.codeproject.com/Articles/375166/Functional-programming-in-Csharp (https://www.codeproject.com/Articles/375166/Functional-programming-in-Csharp)

Otto.
Title: Re: functional programming
Post by: simone on January 18, 2020, 07:15:04 pm
Functional programming has its hype in this period. In truth, it is a revival, not a novelty, given that the functional one is the first invented paradigm.

Personally I don't believe that pure functional languages can be used on a large scale in software production, but certainly presents interesting aspects for some contexts. For this reason, the current trend is to add functional characteristics to languages ​​that are not. Java and C # have followed this path. Even Delphi, though in a more limited way.

I would like to have the first class functions in FreePascal, in particular the possibility of using anonymous functions and closures.
Title: Re: functional programming
Post by: MarkMLl on January 18, 2020, 07:21:06 pm
In truth, it is a revival, not a novelty, given that the functional one is the first invented paradigm.

How do you work that out? Straight imperative programming preceded functional, since it is the paradigm that underlies- among others assembly- and machine-code programming, and was explored by Babbage et al. in the mid C19th.

MarkMLl
Title: Re: functional programming
Post by: simone on January 18, 2020, 07:35:17 pm
I'm talking about computer science, not automatic calculation or programmable mechanical machines. I refer to the Lambda calculus of Alonzo Church, which precedes the Turing machine.
Title: Re: functional programming
Post by: VTwin on January 18, 2020, 07:54:19 pm
Interesting discussion.

@Leledumbo
That does require quite a different mindset than I am used to. Is that more about Haskell, or functional programming in general?

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.

I guess anonymous functions are another significant piece of it though. Apparently in Delphi, but not in Free Pascal yet?

@simone
Apparently Turing was one of Church's PhD students.
Title: Re: functional programming
Post by: simone on January 18, 2020, 08:01:13 pm
@VTwin
Yes.

@MarkMLI
However, leaving theoretical issues for a while, Fortran (imperative) was born in 1954, where Lisp (functional) in 1958. Thus, from this point of view, you are right :)
Title: Re: functional programming
Post by: VTwin on January 18, 2020, 08:27:13 pm
I used Lisp, actually AutoLISP, for a while in the 80s. The joke was that it stood for Lost In Stupid Parentheses. :) I had no idea at the time it was a "functional" language.
Title: Re: functional programming
Post by: PascalDragon on January 18, 2020, 08:45:31 pm
I would like to have the first class functions in FreePascal, in particular the possibility of using anonymous functions and closures.

I guess anonymous functions are another significant piece of it though. Apparently in Delphi, but not in Free Pascal yet?

It's a work in progress (https://lists.freepascal.org/pipermail/fpc-devel/2019-December/042256.html).
Title: Re: functional programming
Post by: simone on January 18, 2020, 08:52:55 pm
@VTwin

Parentheses (and prefix notation) also discouraged me when I studied Lisp at university. However, not all functional languages ​​have such a strong use of parentheses. For example language that derive from ML (Haskell is one of these), that I prefer because are statically typed (conversely from Lisp, Scheme and others, that are dynamically typed).


@PascalDragon
Thanks for update. Good news for me.
Title: Re: functional programming
Post by: skalogryz on January 18, 2020, 10:15:30 pm
I would like to have the first class functions in FreePascal, in particular the possibility of using anonymous functions and closures.
Speaking of stateless way of development.
Could one explain on how to test an anonymous function and/or closure?

Here's what I mean. For a regular "stateless" (or "pure"), yet NAMED function
Code: Pascal  [Select][+][-]
  1. function foo(args...): integer;
  2.  
I can clearly create a stand-alone test and verify that it returns the expected results.
(It's quite often desired for regression testing, when the implementation of foo() changes this way or another... i.e. different optimizations).

But when using an anonymous function / closure... creating a test seems to be problematic, because the entire function body needs to be copied over to the test itself.
Title: Re: functional programming
Post by: VTwin on January 18, 2020, 10:43:25 pm
Well, there is always some buzz.
If you want some good background on the paradigm, then maybe this will help: https://www.youtube.com/watch?v=sqV3pL5x8PI

Thanks. Nice video, well explained.

As an educator, I appreciate someone who can explain something in 10 minutes, as opposed to someone who drones on for half an hour or more without conveying any information. Too much of my life has been expended on the latter.
Title: Re: functional programming
Post by: simone on January 18, 2020, 11:05:23 pm
[But when using an anonymous function / closure... creating a test seems to be problematic, because the entire function body needs to be copied over to the test itself.

Your question is interesting and the response it's not trivial.

A black box test would require, also for an anonymous function, an external behavior that must be observable. For example, in the following very simple code:

(from http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/devcommon/anonymousmethods_xml.html)

Code: Pascal  [Select][+][-]
  1. function MakeAdder(y: Integer): TFuncOfInt;
  2. begin
  3. Result := { start anonymous method } function(x: Integer)
  4.   begin
  5.     Result := x + y;
  6.   end; { end anonymous method }
  7. end;

You can test the anonymous method using the Result variable of MakeAdder, to which it is assigned. 

Title: Re: functional programming
Post by: PascalDragon on January 18, 2020, 11:21:26 pm
I would like to have the first class functions in FreePascal, in particular the possibility of using anonymous functions and closures.
Speaking of stateless way of development.
Could one explain on how to test an anonymous function and/or closure?
You have the same problems with nested functions today already. Essentially there is no good way to test them.
Though in comparison to nested functions you could pass them to the caller and then have the test harnish invoke them using RTTI (closures are essentially interfaces with a single Invoke method).
Title: Re: functional programming
Post by: MarkMLl on January 19, 2020, 10:02:06 am
I'm talking about computer science, not automatic calculation or programmable mechanical machines. I refer to the Lambda calculus of Alonzo Church, which precedes the Turing machine.

So what you mean to say is that the term "functional programming" was coined by computer science at its inception to describe what Lisp does. I quite simply don't buy it as a description of the real world.

(Slightly later) Sorry, I've just seen your

> However, leaving theoretical issues for a while, Fortran (imperative) was born in 1954, where Lisp (functional) in 1958. Thus, from this point of view, you are right :)

I'd also say that I'm not /completely/ hostile to this sort of thing, and I've seen some quite interesting work which used Lisp as a low-level stepping stone to something that more closely resembled what today we'd call a "real" language. But I've studied the history of early programming languages sufficiently to be able to see exactly "where McCarthy was coming from" and what he was trying to do, and while I don't deny that some interesting work has come out of the Lisp camp it was, basically a dead-end approach: in much the same way that intersting concepts came out of Modula-2 while the language itself was a dead end.

MarkMLl
Title: Re: functional programming
Post by: simone on January 19, 2020, 11:37:29 am
So what you mean to say is that the term "functional programming" was coined by computer science at its inception to describe what Lisp does. I quite simply don't buy it as a description of the real world.

Functional prgramming is a computational model that arises from lambda calculus, older than Turing's machine model.

(Slightly later) Sorry, I've just seen your

> However, leaving theoretical issues for a while, Fortran (imperative) was born in 1954, where Lisp (functional) in 1958. Thus, from this point of view, you are right :)

I'd also say that I'm not /completely/ hostile to this sort of thing, and I've seen some quite interesting work which used Lisp as a low-level stepping stone to something that more closely resembled what today we'd call a "real" language. But I've studied the history of early programming languages sufficiently to be able to see exactly "where McCarthy was coming from" and what he was trying to do, and while I don't deny that some interesting work has come out of the Lisp camp it was, basically a dead-end approach: in much the same way that intersting concepts came out of Modula-2 while the language itself was a dead end.

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.


Title: Re: functional programming
Post by: Ñuño_Martínez on January 19, 2020, 01:12:52 pm
Well, there is always some buzz.
If you want some good background on the paradigm, then maybe this will help: https://www.youtube.com/watch?v=sqV3pL5x8PI
The video explains quite well what functional programming is, but the Java example is horrific.  Beside I don't understand why people use Java or other C-style languages to explain algorithms, you should use a language you know. But even fixing the bugs, the implementation of the SUM function is wrong in 3 or more ways.

Code: Pascal  [Select][+][-]
  1. Function Sum(inputs:array of integer):Integer;
  2. Var
  3.   V:Integer;
  4. Begin
  5.   Result:=0;
  6.   For V in inputs do Result+=V;
  7. End;
  8.  
  9. procedure TForm1.Button1Click(Sender: TObject);
  10. begin
  11.  Caption := Sum([1,2,3,4,5]).ToString;
  12. end;                        
  13.  
  14.  

Nothing new here ;)

I think it can be done better (I mean, more functional):
Code: Pascal  [Select][+][-]
  1. { FIXED: as PascalDragon noticed I used HIGH and LOW in the wrong way. }
  2. FUNCTION Sum (CONST Values: ARRAY OF INTEGER): INTEGER;
  3. BEGIN
  4.   IF Length (Values) = 1 THEN
  5.     RESULT := Values[LOW (Values)]
  6.   ELSE
  7.     RESULT := Sum (Slice (Values, Length (Values) - 1) + Values[HIGH (Values)]
  8. END;
  9.  

[side note] I think the RTL needs the SliceR function, same than Slice but using the right side.
Title: Re: functional programming
Post by: julkas on January 19, 2020, 01:18:41 pm
http://learnyouahaskell.com/introduction
Title: Re: functional programming
Post by: simone on January 19, 2020, 01:39:15 pm
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.  

I agree. Indeed, this is the equivalent in Haskell (from: https://stackoverflow.com/questions/51279298/haskell-sum-up-the-first-n-elements-of-a-list).

Code: Haskell  [Select][+][-]
  1. sumList :: [Int] -> Int
  2. sumList [] = 0
  3. sumList (x:xs) = x + sumList xs
Title: Re: functional programming
Post by: MarkMLl 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
Title: Re: functional programming
Post by: PascalDragon 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 (https://www.freepascal.org/docs-html/current/ref/refsu68.html#x180-20200014.4.5) 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.
Title: Re: functional programming
Post by: howardpc 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;
Title: Re: functional programming
Post by: avk 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?
 
Title: Re: functional programming
Post by: julkas 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
Title: Re: functional programming
Post by: avk on January 20, 2020, 12:52:32 pm
Have you succeeded to make it work?
Title: Re: functional programming
Post by: julkas 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 :-(
Title: Re: functional programming
Post by: PascalDragon 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)
Title: Re: functional programming
Post by: VTwin 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.
Title: Re: functional programming
Post by: avk 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.  
Title: Re: functional programming
Post by: MarkMLl 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
Title: Re: functional programming
Post by: PascalDragon 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?
Title: Re: functional programming
Post by: Leledumbo 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?
Title: Re: functional programming
Post by: PascalDragon 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.
Title: Re: functional programming
Post by: avk 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
Title: Re: functional programming
Post by: PascalDragon on January 21, 2020, 02:59:39 pm
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
Updated my version as well.  :-[ It indeed works correctly now.  :)
Title: Re: functional programming
Post by: PascalDragon on January 21, 2020, 11:03:12 pm
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.
Implemented in r44012 (https://svn.freepascal.org/cgi-bin/viewvc.cgi?view=revision&revision=44012). :)

Please note that there is still another restriction (for the foreseeable future): managed types. If a parameter is an AnsiString, UnicodeString, interface, dynamic array, managed record or a record containing one of these types then the optimization won't be applied.
Title: Re: functional programming
Post by: avk on January 22, 2020, 04:54:35 am
Thank you very much.
Title: Re: functional programming
Post by: Ñuño_Martínez on January 22, 2020, 11:53:22 am
You have two errors in there: you need to use Values[LOW(Values)] and Values[HIGH(Values)].
Doh! %) I've fixed it.  Maybe I'm not the genius I though. :-[

Behold the slice operator (it's documented here (https://www.freepascal.org/docs-html/current/ref/refsu68.html#x180-20200014.4.5) at the bottom):
Code: Pascal  [Select][+][-]
  1. function SumR(const Values: array of Integer): Integer;
  2. begin
  3.   if Length(Values) = 1 then
  4.     SumR := Values[Low(Values)]
  5.   else
  6.     SumR := SumR(Values[1..High(Values)]) + Values[Low(Values)];
  7. end;
  8.  
Thanks for the tip. Didn't know it was possible. I wonder if Delphi supports that too.
TinyPortal © 2005-2018