Welcome!

By registering with us, you'll be able to discuss, share and private message with other members of our community.

SignUp Now!

Implementing Lambda Calculus

ivan.moony

Bronze Coder
implementing lambda calculus

Anyone knows good resources on how to efficiently implement untyped lambda calculus?

I mean, it's pretty clear how to do it somehow to an average programmer, but since it's an old paradigm used in existing functional languages for fifty years, are there pitfalls to avoid, or hints to follow on efficient implementation?

base idea

Do you ever feel CSS + HTML + Javascript is a bit cumbersome relict that only got bloated with specific fixes over last thirty or so years? I'm currently working on a neat replacement for those, based only on lambda calculus. Functions are cornerstone of lambda calculus. Function application is a broadly unrecognized powerful formation with a property that all the laying out of HTML elements could entirely be replaced by functions. And since functions may be used for result computation, along simply passing parameters, functions may completely replace CSS + HTML + Javascript system.

I'll try to explain it comparing CSS + HTML code to function embracing code:

HTML:
... other contents goes here ...
<a href='someaddress' style='color:blue; font:Arial 10px'>sometext</a>
... other contents goes here ...

The above code, containing multiple syntax components for CSS + HTML, could be expressed by the following built-in functions (I'm gonna use a custom lambda calculus syntax I plan to use in my project):

Code:
... other contents go here ...
(
    (
        <a>
        <- (<href> <- 'someaddress')
        <- (<color> <- blue)
        <- (
            <font>
            <- (<name> <- Arial)
            <- (<size> <- 10px)
        )
    )
    <- sometext
)
... other contents go here ...

The operator <- applies parameters from its right side to function from its left side. All the functions from the example are predefined parts of user interface for laying out contents, internally defined by currying. The code already shows some uniform appearance comparing to its CSS + HTML equivalent using more complex syntax.

Thinking further, Lambda calculus allows us to push boundaries towards scripting without need for Javascript.

To form a new UI functions we can reuse later, we form expressions like:
Code:
<lnk> ->         // currying parameter 1
<txt> ->         // currying parameter 2
(
    (
        <a>
        <- (<href> <- <lnk>)        //applying parameter 1
        <- (<color> <- blue)
        <- (
            <font>
            <- (<name> <- Arial)
            <- (<size> <- 10px)
        )
    )
    <- <txt>                        // applying parameter 2
)

In the above example, our function is defined by currying, using function formation operator: ->.

To use this function, we apply its definition to our new example:
Code:
(
    <myLink> ->                                 // here we accept a parameter for later reuse
    (
        ... other contents go here ...
        (
            <myLink>                            //reusing <myLink> for laying out the first link
            <- 'someaddress1'
            <- sometext1
        )
        ... other contents go here ...
        (
            <myLink>                            //reusing <myLink> for laying out the second link
            <- 'someaddress2'
            <- sometext2
        )
        ... other contents go here ...
    )
) <- (... definition from above ...)            // here we apply the above function as the parameter

resume

To resume, all the examples are based on function abstraction operator -> and function application operator <-. These operators correspond to their exact equivalents in lambda calculus, semantics are the same, only syntax is different. Compare this simplicity and minimalism to syntax currently used in CSS + HTML + Javascript, noting that it is equally powerful due to the fact that lambda calculus represents Turing complete language embodiment. This is not my invention, lambda calculus exists for almost 90 years now, and is basis for functional languages like Haskell, but I think things are overcomplicated in those languages. This is my attempt to simplify its use, and to apply it to web browser technology.

requesting feedback

What are your thoughts? Do you like it? Do you hate it? Do you have any suggestions? Do you have any critics? Do you see any flaws? I'd appreciate any comment, even from less experienced programmers, could this -> + <- system even compare to the current CSS + HTML + Javascript technology, and would you prefer the proposed technology to the current mainstream web browser technology?
 
Last edited:
Not sure of the <- paradigm: roughly equal to the equals (= or :=) operator? I can see your influence from functional programming, and I could only look over the Haskell language (https://en.wikipedia.org/wiki/Haskell_(programming_language)) as reference, not that I have much experience with that way of doing things (but if I ever get the time I'd like to learn it).

Conceptually it sounds like a good idea. Things that come to mind:
  • being able to clearly determine scope and precedence (maybe it would make sense once you get a grasp of it).
  • getting people used to being able to express intent and for other people to understand it
  • the ability to still handle procedural (ie Javascript) code
but would you look at developing this so it transpiles to the HTML equivalent?

Most recently the web stuff I have seen has mostly been ReactJS (which is very little), which has it's own way of dealing with web pages, almost to the point where it looks like its own language. I think that's where a large part of the industry's at at the moment: what are your thoughts on ReactJS?
 
Krusty, thank you for interesting comments.

Not sure of the <- paradigm: roughly equal to the equals (= or :=) operator? I can see your influence from functional programming, and I could only look over the Haskell language (https://en.wikipedia.org/wiki/Haskell_(programming_language)) as reference, not that I have much experience with that way of doing things (but if I ever get the time I'd like to learn it).

You don't need to understand Haskell to understand lambda calculus. It's the other way around. Haskell is entirely based on lambda calculus, extending it in its own way. My plans are to use exactly lambda calculus without any extensions, which I find enough for any computation task, including laying out web pages. The simpler, the better.

To take a look, lambda calculus expressions are one of the following:
  • x [variable]
  • (λx.M) [lambda abstraction - from expression M extract x and make it a parameter of formed function]
  • (M N) [lambda application - apply value N (may be a function) to function M]
Equivalently to the above, I just changed the sytax, writing:
  • <x> [variable]
  • <x> -> M [abstraction - associates to the right, i.e. <x> -> <y> -> <z> -> some-exp is the same as (<x> -> (<y> -> (<z> -> some-exp)))]
  • M <- N [application - associates to the left, i.e. some-fun <- <x> <- <y> <- <z> is the same as (((some-fun <- <x>) <- <y>) <- <z>)]
Let me explain semantics on an example: if we know how to interpret an expression x + y then expression <x> -> <y> -> (<x> + <y>) is a function formed by abstraction. To apply parameters to this function, we write (<x> -> <y> -> (<x> + <y>)) <- 2 <- 3, in which 2 substitutes for <x> and 3 substitutes for <y>. These two evaluation steps are written: (<y> -> (2 + <y>)) <- 3 and then 2 + 3, and that's it. This is everything that is related to lambda calculus, and now it is up to us to interpret 2 + 3 as we want.

In fact, lambda calculus is a substitution system, and instead on math, my plans are to use it on forming HTML equivalent output. I say HTML equivalent because I want to replace CSS + HTML conglomerate by basic drawing elements which are composed using only lambda functions. For example, we start from words, rectangles, polygons and circles (being internally defined functions to output vector graphics), and we are able to express functions that draw compositions like text flows, tables, styled drawings, record layouts, or templates as whole whole page renderings. Some basic math calculations are also supposed to be understood internally, enabling us to draw elements relative to passed parameters, or other elements. This would turn lambda calculus into a procedural graphics engine used to lay out web pages.

Conceptually it sounds like a good idea. Things that come to mind:

  • being able to clearly determine scope and precedence (maybe it would make sense once you get a grasp of it).
  • getting people used to being able to express intent and for other people to understand it
  • the ability to still handle procedural (ie Javascript) code

Scope is entirely controlled by round braces. Expressing intent and understanding it is up to being familiar with paradigm. It's like in procedural programming: complicated algorithms would be hard to read, but they can be packed inside functions, which ease their use. About handling js code, I think I'll pass for now. If I was to support anything easily enough, that would be Web Assembly because of its speed. I used to have some thoughts on a language used to syntactically and semantically express any other language, but I think I'll concentrate on UI part for now.

but would you look at developing this so it transpiles to the HTML equivalent?

Lambda calculus is actually a transpilation language (remember substitution? It relates to term rewriting). It can transpile to whatever can be drawn on screen. I choose my own vector graphics.

Most recently the web stuff I have seen has mostly been ReactJS (which is very little), which has it's own way of dealing with web pages, almost to the point where it looks like its own language. I think that's where a large part of the industry's at at the moment: what are your thoughts on ReactJS?

I took a fast skim, and ReactJS seems like a good thing. It relates to XSLT, which I find to be a good direction to go. If I'm not mistaken, XSLT should already be supported natively by major browsers for a while now. But I hope to provide an alternative for it.

The language I'm proposing is like ReactJS, only it is a self contained language, while it transpiles not to HTML DOM, but to my own simpler vector graphics format that I plan to draw in browser canvas via separate, hidden javascript. Web page designer will never see CSS, HTML, nor Javascript to be able to compose pages or their templates.
 
Last edited:

New Threads

Latest posts

Buy us a coffee!

Back
Top Bottom