All Questions
Tagged with programming-languages functional-programming
89 questions
0
votes
0
answers
38
views
Why [b] → Int < a → Int holds according to the contravariant manner for function types but length is a counter example for that
In the paper Practical type inference for arbitrary-rank types, the covariance and contravariance rules are essential when dealing with function types. Covariance applies to the return types of ...
- 31
2
votes
1
answer
52
views
Is there any reference materials on complexity analysis for lazy languages?
Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell?
I know how laziness is implemented and how it can be expanded and ...
2
votes
1
answer
68
views
Is there any formalization of GADTs implemented in OCaml?
There are papers that describe how generalized algebraic datatypes (GADTs) are encoded in core Haskell (System FC)[1][2], but I could not find any documentation on how OCaml formalizes/implements/...
- 659
0
votes
0
answers
37
views
Programming language implementation challenge: is recursion harder than HOFs, or vice versa?
(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to ...
- 189
4
votes
1
answer
280
views
Is “x' = f(x)” a programming paradigm?
I'm the author of GateBoy (a gate-level simulation of the original Game Boy hardware) and Metron (a C++ to Verilog translation tool). One big issue I had to work around for both projects is the ...
- 76
0
votes
0
answers
60
views
Question about complexity of two topics in programming language theory
I am a student who is currently finishing second year of university mathematics. This summer I have to choose a topic for my diploma. Because I am particularly interested in computer science I am ...
- 203
7
votes
1
answer
2k
views
What exactly is the relation between Haskell and category theory?
In articles or Quora posts about category theory, I often find mentions of the programming language Haskell. I have little knowledge of category theory and even less of programming. Could someone ...
- 261
10
votes
4
answers
4k
views
What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
I’m a CS senior with and Individual Study period this coming semester, and I’ve decided I’d like to learn more about Programming Language Concepts. More specifically, different programming paradigms, ...
- 119
1
vote
0
answers
98
views
Shallow Binding with static scope, is it possible?
I'm new in programming, I'm currently studying programming languages.
I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
3
votes
2
answers
141
views
Semantics and implementation of side effects
From a practical point of view, how do functional languages with formally specified semantics (like ML) handle side effects like printing? I'm aware of things like the IO monad in Haskell but I'm ...
- 357
8
votes
2
answers
166
views
Does the concept of "side-effect" predate functional programming?
When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
- 241
5
votes
2
answers
333
views
Regarding Backus' Commentary on von Neumann-style Programming
in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says
To help assemble the overall result from single words [von Neumann ie.
conventional mutation-...
- 209
2
votes
0
answers
107
views
What's the meaning of linguistics?
In the programming language theory world, there are two important terminologies, i.e syntax, and semantics.
I can understand these two terminologies:
syntax is about sentence's structure (e.g. a valid ...
- 295
2
votes
3
answers
142
views
Uncurrying and Polymorphism
How do we uncurry functions when they are polymorphic? For example, is it possible to uncurry the following types? If so what is the uncurried type?
$\forall X. X \rightarrow int \rightarrow X$ ?
$...
- 31
2
votes
0
answers
123
views
Compiling an impure language into a pure stack-based language
For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as <...
- 275
1
vote
2
answers
200
views
resource on translating imperative programs to functional programs
I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional ...
- 4,122
0
votes
2
answers
221
views
Does the callback concept of programming have any basis in computer science?
Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative ...
user109446
-1
votes
2
answers
137
views
Applying FP/Categorical terminology to non-FP languages
In my continuing effort to finally wrap my brain around advanced FP/categorical concepts, I've been reading dozens of articles and tutorials; what I have concluded is that:
1) Category Theory and ...
- 141
1
vote
2
answers
153
views
If declarative programming is possible at the instruction/action level?
I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if ...
- 2,305
6
votes
1
answer
404
views
Why does higher-order abstract syntax need an inverse to define catamorphisms?
In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of ...
- 304
2
votes
1
answer
52
views
Can most programs (except the IO part) be re-written as a sequence of matrix operations?
I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
- 141
1
vote
2
answers
118
views
Can we always transform a set of lines to a function?
If I have n lines in a programming language like Python (globally or inside a function):
...
- 135
-2
votes
1
answer
253
views
2
votes
1
answer
65
views
Are the definitions of constructs in terms of lambda terms issues in implementation/design or uses of functional languages?
In Lambda Calculus, natural numbers, boolean values, list processing functions, recursion, if function are defined in terms of lambda terms. For example, natural numbers are defined as Church numerals,...
- 5,015
1
vote
0
answers
103
views
What is the difference between self-rewriting program and program-with-updates-and-restart
I am reading about Goedel machine http://people.idsia.ch/~juergen/goedelmachine.html and especially the article about possible implementation (in the Scheme language) of this machine http://people....
- 1,401
13
votes
1
answer
342
views
Is the IO monad technically incorrect?
On the haskell wiki there is the following example of conditional usage of the IO monad (see here).
...
- 233
3
votes
1
answer
3k
views
Why are both caller-save registers and callee save registers needed?
I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller ...
- 163
0
votes
0
answers
35
views
Trying to determine Fixed Points
I'm basically trying to solve 4.2
(Taken from Semantics with Applications)
As I see it, the functional F will be defined like so:
...
- 123
4
votes
2
answers
257
views
Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
- 185
3
votes
1
answer
45
views
"Immediate" method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":
x=1
x=f(x);
x=f(x);
We can rewrite this in "immutable style" without changing the higher-level structure of ...
- 4,122
5
votes
3
answers
311
views
How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:
In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$ T {...
- 4,122
1
vote
1
answer
65
views
Generalization of Functors to other datatypes?
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$,...
- 4,122
1
vote
0
answers
47
views
Reasons for why x - 1 and x -1 gives different result in some languages [closed]
I assume the reason space makes a difference in F# is due to reserving a certain function, when minus is in front of a number without space, however what are the reasons for this? I can't seem to find ...
- 11
0
votes
1
answer
93
views
Composition of compostion as a functor
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type ...
- 1,190
0
votes
1
answer
2k
views
First-order vs Higher-order Programs
Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages?
My understanding so far is that Functional Languages (most) use ...
- 103
2
votes
2
answers
111
views
How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?
I wanted to show:
$$ (\lambda x . (\lambda y.x))yx \equiv_{\beta} y $$
the definition of beta equivalence is on page 17 of these notes.
I did a few attempts but got different things like $x$. I ...
- 3,090
2
votes
1
answer
144
views
How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?
How do we show $$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$$?
I was going through the slides here and it asked to do the above but by page 16 of the slides we have not ...
- 3,090
2
votes
4
answers
700
views
How does one formally show that two lambda functions are $\alpha$ equivalent?
I was going through the following slides and I wanted to show the following:
$$ \lambda x. x \equiv_{\alpha} \lambda y . y$$
formally. They define a an $\alpha$-conversion on page 15 as follows:
$$ ...
- 3,090
-2
votes
1
answer
270
views
Erlang- Creating a function which only adds/subtracts positive integers
I want to create a function which allows me to input a list, and then add all of the positive numbers from the list together, leaving any that are negative.
([3,1,-1])
For example only 3 and 1 would ...
4
votes
3
answers
276
views
Is it possible to make a language that can build upon itself perfectly?
First of all, note that I'll have to explain my thoughts in a layman's terms.
There are so many high-level programming languages out there that compete with each other. This means we have to build ...
- 337
3
votes
1
answer
203
views
Can we implement every algorithm using only immutable variables?
Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?
- 131
1
vote
0
answers
128
views
Design considerations for a language to support automatic parallelization [closed]
Automatic parallelization isn't a new thing by any means, and lots of questions have been asked about whether Java or C or C++ or a host of other languages or specific compilers (gcc 5 v 6, clang, ...
- 111
1
vote
2
answers
670
views
Mutation considered harmful, but is there a safe set
Functional programming does not have mutation. Mutation is usually harmful, however mutation is sometimes beneficial. e.g. Creating a [random number] generator.
In the same way that ...
- 138
5
votes
2
answers
666
views
Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?
Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?
More specifically if I call a function foo(x) that ...
- 283
4
votes
1
answer
434
views
Type Inference and Generalization
I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:
...
- 215
7
votes
2
answers
791
views
Higher-ranked polymorphism without explicit application or subtyping?
So, I'm familiar with two main strategies of having higher-ranked polymorphism in a language:
System-F style polymorphism, where functions are explicitly typed, and instantiation happens explicitly ...
- 30.1k
1
vote
0
answers
111
views
Is an inputless program redundant?
Are there useful programs that don't take inputs from a user, environment etc. such as key input, or the current time?
A program that computed/printed out predefined data could be turned into a file, ...
- 291
11
votes
1
answer
713
views
Alternatives to Defunctionalization
Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order ...
- 361
6
votes
1
answer
667
views
Lazy concatenative functional language
Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?
I see some problems that I will explain with few examples. I will use a prefix instead of a ...
- 485
11
votes
3
answers
4k
views
Are the words "expression" and "term" interchangeable in programming language theory?
When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of ...
- 245