It’s not procedural. You write what you want your infrastructure to look like in the case of CloudFormation yaml or JSON.
The first time you run your template it creates all of your infrastructure and is usually smart enough to figure out dependencies.
After you make changes to your template and run it again it knows based on the changes in your template whether it can modify the existing resources or whether it needs to delete and recreate your resources.
Procedural certainly can be "Infrastructure as code." It just isn't the most modern way to do it, due to additional complexity and the potential to be more error prone. I'd certainly prefer CloudFormation over writing a bunch of python/boto code, but it could be done.
Interestingly, Dockerfiles brought back a bunch of procedural configuration management. We had migrated to ansible for all our server-level configuration. But as we've adopted docker/containerization in recent years, simplifying our applications (now separate containers, rather than severs on common servers) has such a reduced level complexity such that simple docker files with `apt-get install foo` are much preferred.
The first time you run your template it creates all of your infrastructure and is usually smart enough to figure out dependencies.
After you make changes to your template and run it again it knows based on the changes in your template whether it can modify the existing resources or whether it needs to delete and recreate your resources.