Recent

Author Topic: Functional programming in Pascal  (Read 7375 times)

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 635
Re: Functional programming in Pascal
« Reply #30 on: June 27, 2019, 09:50:28 pm »
Ok, I understand. Thanks for explaining it. I do understand the possibilities.

So, you can store the state and call it later. This is only really useful if it accesses external (outside the instance) data or devices, because otherwise you could have simply stored the result.

With the C# WCF analogues, the main problem was it becoming desynced, most often because one or more of those external memory locations or devices went into a different state between creation and execution. Mutexes don't fix that.

How would you debug them, especially when you pass them to a different process?

Interesting to see how you are implementing this complex feature.

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: Functional programming in Pascal
« Reply #31 on: June 28, 2019, 12:16:44 am »
This library: https://github.com/avk959/LGenerics is IMO a great example of what can be done with FPC generics, and contains quite a bit of functional-esque stuff for arrays/e.t.c. similar to what's being asked about here.

Behind the scenes it's an interface with only an Invoke() method that's implemented by a class instance. This class instance is shared by all anonymous functions of a single scope. Though this is all an implementation detail.

While I certainly want anonymous functions in FPC sooner than later, I really wish they weren't implemented this way (which not only makes them un-inlinable but also requires heap allocation.)

Hopefully that can be optimized / remedied at some point after the initial implementation is merged, though. Having FPC be able to inline normal procvars would be a nice also.
« Last Edit: June 28, 2019, 12:26:26 am by Akira1364 »

rsz

  • New Member
  • *
  • Posts: 13
Re: Functional programming in Pascal
« Reply #32 on: June 28, 2019, 12:24:00 am »
Btw, about the readability:

A few years ago, I was working on a C# ASP.NET webapp. And the lead designer spend his time with Resharping all the source code. And he turned on all the options. So, when I made some beautiful, readable and maintainable code, he turned it in an unreadable and unmaintainable mess of nested LINQ queries (Lambda functions, or anonymous functions).

Every language feature can be abused, that does not inherently make it bad. Bad programmers will write bad code in any language. I used LINQ at my last job and I know it can make code more readable if done right. Just off the top of my head, you can remove a double nested for loop by using LINQs SelectMany.

I personally don't believe ObjectPascal should become a functional language. That being said, I can see certain language features from functional languages that may make sense to implement. Anonymous functions and type inference are ones that I can think of.

e.g. anonymous function with lambda syntax is clear and concise.
Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<MyObject>
  4. begin
  5.   L.Sort(lambda (a, b) as Result := a.X > b.X);
  6. end;
  7.  

e.g. type inference.
Code: Pascal  [Select]
  1. generic function DoStuff<T>(a, b: T): T;
  2. begin
  3.   Result := a + b;
  4. end;
  5.  
  6. procedure MyProcedure;
  7. var
  8.   A, B, X: Integer;
  9. begin
  10.   A := 1;
  11.   B := 2;
  12.   X := DoStuff(A, B);  // no need to specialize DoStuff, compiler can infer type and specialize automatically.
  13. end;
  14.  

People always state goto in C as a feature that gets abused, but even goto has legitimate uses ;D. Here is a legitimate example (I don't like C):
Code: C  [Select]
  1. void myfunc() {
  2.     MyContext a, b, c;
  3.     a = create_context();
  4.     b = create_context();
  5.     c = create_context();
  6.     if(!a) goto end;
  7.     if(!b) goto cleanup_a;
  8.     if(!c) goto cleanup_b;
  9.     // do stuff
  10.     if(do_stuff(a) != 0) {
  11.         // failed!
  12.         goto cleanup;
  13.     }
  14.     // do more stuff
  15. cleanup:
  16. cleanup_c:
  17.     destroy_context(c);
  18. cleanup_b:
  19.     destroy_context(b);
  20. cleanup_a:
  21.     destroy_context(a);
  22. end:
  23. }

« Last Edit: June 28, 2019, 12:34:02 am by rsz »

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: Functional programming in Pascal
« Reply #33 on: June 28, 2019, 12:57:26 am »
e.g. type inference.
Code: Pascal  [Select]
  1. generic function DoStuff<T>(a, b: T): T;
  2. begin
  3.   Result := a + b;
  4. end;
  5.  
  6. procedure MyProcedure;
  7. var
  8.   A, B, X: Integer;
  9. begin
  10.   A := 1;
  11.   B := 2;
  12.   X := DoStuff(A, B);  // no need to specialize DoStuff, compiler can infer type and specialize automatically.
  13. end;
  14.  

That kind of type inference for generics is actually already fully implemented, BTW. It's currently just waiting on being merged to trunk.

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 635
Re: Functional programming in Pascal
« Reply #34 on: June 28, 2019, 01:02:52 am »
e.g. anonymous function with lambda syntax is clear and concise.
Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<MyObject>
  4. begin
  5.   L.Sort(lambda (a, b) as Result := a.X > b.X);
  6. end;

What bothers me most about Lambda functions is, that their syntax is entirely different from everything around it. It is a second, embedded language.

Like, you have two vars, a and b, but they're not actual vars. They are like magic. Consider this instead:

Code: Pascal  [Select]
  1. for s in MyStringList do
  2.   ..

It's clear what is happening here. You might even have to write the enumerator yourself. There is a one-on-one relation.

And in your example, you could simply write:

Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<MyObject>
  4. begin
  5.   L.Sort;
  6. end;

That would have the exact same effect.

Edit: If you REALLY want Lambda functions, do it like this:

Code: Pascal  [Select]
  1. for s1, s2 in MyStringList step 1 do
  2.   ..
« Last Edit: June 28, 2019, 01:14:07 am by SymbolicFrank »

rsz

  • New Member
  • *
  • Posts: 13
Re: Functional programming in Pascal
« Reply #35 on: June 28, 2019, 01:28:57 am »
That kind of type inference for generics is actually already fully implemented, BTW. It's currently just waiting on being merged to trunk.

Nice  8-).

What bothers me most about Lambda functions is, that their syntax is entirely different from everything around it. It is a second, embedded language.

Like, you have two vars, a and b, but they're not actual vars. They are like magic. Consider this instead:

I don't quite understand. Imagine the sort function calling another function 'Compare' which takes two arguments, a and b. Under the hood that lambda is no different than a function with 2 parameters, a and b.
I think the syntax with 'lambda' and the 'as' suits pascal, but maybe someone can come up with a better pascal-esque syntax for lambdas that would fit even better into the language?

And in your example, you could simply write:

Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<MyObject>
  4. begin
  5.   L.Sort;
  6. end;

That would have the exact same effect.

It's not the same, I am sorting the list by the member 'X'. I could use a different lambda and sort the List by the member 'Y' or even member 'Z' instead, for example.
Imagine you have a list of 'Person' but you want to sort them by age or by company position:

Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<Person>
  4. begin
  5.   L.Sort(lambda (a, b) as Result := a.Age > b.Age);
  6.   // or
  7.   L.Sort(lambda (a, b) as Result := a.Position > b.Position);
  8. end;
  9.  

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 635
Re: Functional programming in Pascal
« Reply #36 on: June 28, 2019, 02:20:09 am »
Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<Person>
  4. begin
  5.   L.Sort(lambda (a, b) as Result := a.Age > b.Age);
  6.   // or
  7.   L.Sort(lambda (a, b) as Result := a.Position > b.Position);
  8. end;
  9.  

Ok. Let's rewrite that:

Code: Pascal  [Select]
  1. procedure MyProcedure(var L: TMyList<Person>);
  2. begin
  3.   L.Sort('Age');
  4.   // or
  5.   L.Sort('Position');
  6. end;
  7.  
« Last Edit: June 28, 2019, 02:23:19 am by SymbolicFrank »

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: Functional programming in Pascal
« Reply #37 on: June 28, 2019, 04:31:21 am »
Code: Pascal  [Select]
  1. procedure MyProcedure(var L: TMyList<Person>);
  2. begin
  3.   L.Sort('Age');
  4.   // or
  5.   L.Sort('Position');
  6. end;
  7.  

What exactly is this supposed to be doing?

PascalDragon

  • Hero Member
  • *****
  • Posts: 673
  • Compiler Developer
Re: Functional programming in Pascal
« Reply #38 on: June 28, 2019, 09:19:46 am »
Behind the scenes it's an interface with only an Invoke() method that's implemented by a class instance. This class instance is shared by all anonymous functions of a single scope. Though this is all an implementation detail.

While I certainly want anonymous functions in FPC sooner than later, I really wish they weren't implemented this way (which not only makes them un-inlinable but also requires heap allocation.)

Hopefully that can be optimized / remedied at some point after the initial implementation is merged, though. Having FPC be able to inline normal procvars would be a nice also.
It is needed for Delphi compatibility as there is code out there that (ab)uses this implementation detail. Also it's necessary for the lifetime management of the state (it *could* be done some other way, but why implement something new if existing functionality can be used).

The inlining is also only useful in a very small number of cases. Most often anonymous functions are passed to other functions/classes (e.g. as the Execute function for TThread) and then you can not inline anymore as you're essentially dealing with function pointers then. In my opinion it's wasted time to add support for inlining anonymous functions.

I think the syntax with 'lambda' and the 'as' suits pascal, but maybe someone can come up with a better pascal-esque syntax for lambdas that would fit even better into the language?
There needs to be some keyword that lets the compiler decide whether it should parse a lambda function or not. I already have enough problems with implementing Delphi generic specialization with their oh so ambiguous syntax (especially as generic types can be overloaded with constants and variables).

Code: Pascal  [Select]
  1. procedure MyProcedure;
  2. var
  3.   L: MyList; // TMyList<Person>
  4. begin
  5.   L.Sort(lambda (a, b) as Result := a.Age > b.Age);
  6.   // or
  7.   L.Sort(lambda (a, b) as Result := a.Position > b.Position);
  8. end;
  9.  
Please note that the idea is that the right side of the as is an expression, not a statement, so it would be
Code: Pascal  [Select]
  1. lambda (a, b) as a.Age > a.Age

What bothers me most about Lambda functions is, that their syntax is entirely different from everything around it. It is a second, embedded language.
They consist of Pascal expressions, so what exactly is a second language here?

Like, you have two vars, a and b, but they're not actual vars. They are like magic.
No, they're parameters. It's simply part of the lambda's syntax:

Code: [Select]
LAMBDA::=lambda [(LAMBDABPARAMS)] as EXPR
LAMBDAPARAMS::=LAMBDAPARAM[;LAMBDAPARAMS]
LAMBDAPARAM::=IDENTLIST[:TYPE]
IDENTLIST::=IDENTIFIER[,IDENTIFIER]

Edit: If you REALLY want Lambda functions, do it like this:

Code: Pascal  [Select]
  1. for s1, s2 in MyStringList step 1 do
  2.   ..
This is not a lambda function. It's seems you still don't get the conceptual idea behind lambdas/anonymous functions.

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 635
Re: Functional programming in Pascal
« Reply #39 on: June 28, 2019, 09:45:37 am »
Code: Pascal  [Select]
  1. procedure MyProcedure(var L: TMyList<Person>);
  2. begin
  3.   L.Sort('Age');
  4.   // or
  5.   L.Sort('Position');
  6. end;
  7.  

What exactly is this supposed to be doing?

That is a good question  :D

What is Person? Is it a record or a class? If the latter, are Age and Position fields or properties? And if fields, are they public? So, you need compiler magic to figure out what they are and how to handle them. It is the same with the Lambda functions.

In my example, it is the analogue of the FieldByName function. Or like a named indexer.

Anyway, whatever. The chances of me working in a team on a Free Pascal project are slim, so it doesn't matter to me. I can still write the programs in the way I want.

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: Functional programming in Pascal
« Reply #40 on: June 28, 2019, 03:43:50 pm »
It is needed for Delphi compatibility as there is code out there that (ab)uses this implementation detail. Also it's necessary for the lifetime management of the state (it *could* be done some other way, but why implement something new if existing functionality can be used).

The inlining is also only useful in a very small number of cases. Most often anonymous functions are passed to other functions/classes (e.g. as the Execute function for TThread) and then you can not inline anymore as you're essentially dealing with function pointers then. In my opinion it's wasted time to add support for inlining anonymous functions.

I'm fully aware it's required for Delphi compatibility, and I did not mean that it should never work that way.

What I meant was that a function or procedure that takes an anonymous function as an argument, and specifically does not capture state but simply makes use of the return value, is negatively impacted performance-wise if the anonymous function still requires heap allocation no matter what.

The "tmaptest" example you yourself posted in this thread is a perfect example of something that has absolutely no reason to create and destroy a hidden interface instance if implemented with anonymous methods (and indeed would actually have better performance as you wrote it, because while function pointers can't currently be inlined in FPC, they at least also do not allocate anything.)

It is simply not true that there is any legitimate technical reason that function pointers cannot be inlined, though. I can't really think of a compiler for any "native" language other than FPC (and Delphi) that doesn't do so. (I've actually looked into what it would take to implement it in FPC myself, and the only thing that seems to make it difficult at all is the fact that "procvardefs" have an overly-limited amount of information associated with them versus "procdefs".)

For example, here's a small C++ proram showing that both C++11 lambdas and also "classic" function pointers are indeed fully inlineable:
https://godbolt.org/z/BPdOI6

Edit:

The same program in Swift: https://godbolt.org/z/72uzPw
And in Rust: https://godbolt.org/z/7h0ssB
Also in C (with no anonymous function obviously, just the function pointer): https://godbolt.org/z/hX76pQ
And lastly in D: https://godbolt.org/z/N5o46p

In all cases, no heap allocation is required for the non-capturing anonymous function, and the use of both it as well as the "normal" function pointer is inlined completely.
« Last Edit: June 28, 2019, 06:16:23 pm by Akira1364 »

PascalDragon

  • Hero Member
  • *****
  • Posts: 673
  • Compiler Developer
Re: Functional programming in Pascal
« Reply #41 on: June 29, 2019, 09:59:33 pm »
What I meant was that a function or procedure that takes an anonymous function as an argument, and specifically does not capture state but simply makes use of the return value, is negatively impacted performance-wise if the anonymous function still requires heap allocation no matter what.
But the code that gets passed such an anonymous function can not differentiate whether the function got state or not. In fact in one case it can be called with a function reference that has state and in another with one that doesn't. So there is only one way that the code calling the anonymous function can call said function: by treating the function reference as an interface and calling Invoke.
ONLY if the compiler could proof that ONLY anonymous functions without state are passed to that other code could it change the function reference to a mere function pointer.
This restricts the scope of such an optimization quite a bit:
- the code would all need to reside in the implementation section of a unit (or completely inside the main program file)
- or all units are compiled as part of a WPO pass cause as soon as one participating function is part of the interface section the compiler must not do such optimizations as the unit might be used as part of a program where a function with state is passed in

It is simply not true that there is any legitimate technical reason that function pointers cannot be inlined, though. I can't really think of a compiler for any "native" language other than FPC (and Delphi) that doesn't do so. (I've actually looked into what it would take to implement it in FPC myself, and the only thing that seems to make it difficult at all is the fact that "procvardefs" have an overly-limited amount of information associated with them versus "procdefs".)

For example, here's a small C++ proram showing that both C++11 lambdas and also "classic" function pointers are indeed fully inlineable:
https://godbolt.org/z/BPdOI6
Yes, there is a technical reason: namely if the compiler can not proof that it can simplify it. Your example is an explicit situation where it would also be possible in FPC (if the compiler would support it). Even your example would however fail if you'd split the functions across compilation units (with Link Time Code Generation or whatever the term is for LLVM disabled).
These examples however are highly restricted (see my points mentioned above). And no, only because C++ compilers are able to do this does not mean that FPC can do this as well, because both languages involve different compilation concepts (we have precompiled units with a defined interface while in C++ you only have header files that are essentially "external" declarations). The unit concept simply prohibits some optimizations, because units can be shared between programs (Visual Studio for example complains if you share the immediate build directory (where the .obj files are put in) is shared between projects, because one project might overwrite the other project's files).

The same program in Swift: https://godbolt.org/z/72uzPw
And in Rust: https://godbolt.org/z/7h0ssB
Also in C (with no anonymous function obviously, just the function pointer): https://godbolt.org/z/hX76pQ
And lastly in D: https://godbolt.org/z/N5o46p

In all cases, no heap allocation is required for the non-capturing anonymous function, and the use of both it as well as the "normal" function pointer is inlined completely.
Again same problem as in C++. As soon as you get to more real world examples and also apply the conceptual restrictions of Object Pascal that all breaks apart.

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: Functional programming in Pascal
« Reply #42 on: June 30, 2019, 12:23:48 am »
Again same problem as in C++. As soon as you get to more real world examples and also apply the conceptual restrictions of Object Pascal that all breaks apart.

You've made fair enough points here I suppose. However, I don't think any of them really indicate that nobody should ever even attempt to implement any of it. I'm still quite confident that given some amount of API tweaking / unification for "procdefs" and "procvardefs" in FPC that it would really not be very difficult to enable callbacks / function pointers / event handlers / whatever you want to call them to be inlined, at the very least.

The compiler ultimately has to know exactly what it's really calling, so the issue is largely centered around making that information easily accessible to the parts of it that check whether or not an inline-marked method can actually be inlined at all, e.t.c.

I might take another look at getting at least basic support for that up and running myself sometime in the next little while, because it's something I think would have extremely far-reaching end-user benefits.
« Last Edit: June 30, 2019, 12:30:50 am by Akira1364 »

PascalDragon

  • Hero Member
  • *****
  • Posts: 673
  • Compiler Developer
Re: Functional programming in Pascal
« Reply #43 on: June 30, 2019, 10:47:46 am »
As long as you remember the restrictions, feel free to play around with it.  ;)

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 635
Re: Functional programming in Pascal
« Reply #44 on: June 30, 2019, 11:59:27 am »
it's something I think would have extremely far-reaching end-user benefits.

Could you elaborate?